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.