Re: forward secrecy in mixmaster

[ghio@c2.net (Matthew Ghio)]

Lance Cottrell <loki@infonex.com> wrote:

> Our options will open up alot when the patent expires next year.

> I agree it does not make much difference mathematically, but one DH modulus
> always makes me uneasy. DH is still patented though. I think I will continue
> to use RSAREF, but compose the standard so the protocol supports unlimited
> key sizes.

RSAREF does not give you a license to use DH because RSA does not have a
licence to use DH.  So basically you can use whatever library you want and
it doesn't change your position legally.  I believe I read that in the
Schafly-RSA-Cylink lawsuit, the judge issued an injunction barring Cylink
from suing anyone else for patent infringement until the current case is
resolved.  The judge will probably throw out the patent - Anyone know when
the next hearing in this case is?

Mathematically, a common modulus does make a difference, because you can
do precomputations on the modulus.  This generally involves finding the
discrete logarithms of many small primes modulo p.  For example, if you
solved (by exhaustive search) the values of a,b,c,d,e... such that, mod p,
g^a=2, g^b=3, g^c=5, g^d=7, g^e=11, and so on, then you could compute the
discrete logs of larger numbers by factoring them into small primes.  For
example, if you wanted to take the discrete log of, oh, say, 339570, that
would be a+2b+c+3d+e, since 339570=2*(3^2)*5*(7^3)*11.  The logarithm of a
product is the sum of the logarithms of the factors.  What happens if you
want to take the discrete log of a number you can't factor?  Let's suppose
you want the discrete log of 257.  Well, you can't factor that because
it's prime.  But, since we're working modulo p, 257=p+257.  So you can
try factoring p+257, or 2p+257, or 3p+257, etc. until you find a number
that factors nicely into some combination of the primes that you do have.
Of course, the more small primes you collect, the easier it is to find
such numbers, thus the more small primes you collect, the easier it is to
find more small primes. :)

In light of the above, it should be apparent that users should not share
a common modulus, even if they use different generators (you can take the
discrete log of one generator to the other, once you crack one of them).
Thus it is wise for each user to create their own prime number modulus
before they generate their key.

Oh, one final thing - (actually two final things) - If the modulus is not
prime, and the attacker can factor the modulus, then the discrete log
problem becomes somewhat easier because of the Chinese Remainder Theorem.
Also, the ability to do arbitrary discrete logs modulo p, where p is a
product and not prime, implies the ability to factor p.  (Think about it
for awhile. ;-)  Overall tho, the discrete log problem is believed to be
slightly harder than factoring.