two definitions of RSA?
in [Cryptography]
|
Prev: Method and Logic
Next: Frustration with mathematics
From: Rainer Urian on 30 Jan 2010 06:30 Hello, I am wondering if there are two different definitions of RSA keys. One definition states that one should calculate the secret exponent d as (1) e*d = 1 mod phi(n) (= (p-1)*(q-1)) The other states that (2) e*d = 1 mod lcm(p-1,q-1) Both definitions lead to different d values I know that this is doesn't matter for RSA based cryptographic operations. But it makes a difference if one will calculate CRT parameters from n,e and d If d is defined accoring to (1) one can use a direct calculation for determining p and q On the other hand, if d is defined according to (2) one must use a more complicated probabilistic algorithm. Definition (2) is used by German SECCOS smartcard operating system. Can anyone tell me if definition (2) also used in other places? Thanks, Rainer
From: Tom St Denis on 30 Jan 2010 08:07 On Jan 30, 6:30 am, "Rainer Urian" <rai...(a)urian.eu> wrote: > Hello, > I am wondering if there are two different definitions of RSA keys. > > One definition states that one should calculate the secret exponent d as > (1) e*d = 1 mod phi(n) (= (p-1)*(q-1)) > > The other states that > (2) e*d = 1 mod lcm(p-1,q-1) > > Both definitions lead to different d values > I know that this is doesn't matter for RSA based cryptographic operations.. > But it makes a difference if one will calculate CRT parameters from n,e > and d > If d is defined accoring to (1) one can use a direct calculation for > determining p and q > On the other hand, if d is defined according to (2) one must use a more > complicated probabilistic algorithm. > > Definition (2) is used by German SECCOS smartcard operating system. > Can anyone tell me if definition (2) also used in other places? e*d1 == 1 mod phi and e*d2 == 1 mod lcm Then d1 == d2 mod order of the multiplicative group modulo pq They may be different values just like 2 and 9 are, but mod 7 they're congruent. You could plug 9 into the same equation you would 2 and get the same value modulo 7. Tom
From: Thomas Pornin on 30 Jan 2010 09:36 According to Rainer Urian <rainer(a)urian.eu>: > Both definitions lead to different d values Actually for a given modulus n and public exponent e, there are an infinity of possible secret exponents 'd' which all yield the same results in the RSA computations: they generate the same signatures, decrypt the same messages, and so on. Hence, "the" private exponent is really "a wide family of functionally equivalent private exponent" and the private key holder is free to use whichever member of that families it sees fit. What makes 'd' a proper private exponent (i.e. a member of the family of private exponents) is that both following conditions hold: d is an inverse of e modulo p-1 d is an inverse of e modulo q-1 Those two conditions, together, are equivalent to: e*d = 1 mod lcm(p-1,q-1) (eq. 1) Among the proper private exponents, some, but not all, also satisfy the following: e*d = 1 mod (p-1)*(q-1) (eq. 2) which was the way RSA was first described. Every value 'd' which satisfies equation 2 automatically satisfies equation 1, so there is no problem in sticking to equation 2. Since the private key holder is free to use whichever proper private exponent it wishes, some implementers have tried to select one which allows better performance. With usual exponentiation algorithms, shorter private exponents are better, but private exponents with many zeroes and few ones are good too; depending on the exponentiation algorithm actually used, one may get slightly better performance by searching for a longer but "emptier" candidate for d. Overall, gains are not big. From the outside (e.g. the point of view of anyone who verifies the produced signatures) the actual choice of d is completely invisible. > But it makes a difference if one will calculate CRT parameters from > n,e and d If d is defined accoring to (1) one can use a direct > calculation for determining p and q In practical situations, the private key, as stored, includes not only n and d, but also p and q, and some other parameters. See PKCS#1 for a description of a private key storage format which includes n, e, d, p, q, d mod p-1, d mod q-1 and 1/q mod p. --Thomas Pornin
From: Rainer Urian on 30 Jan 2010 09:59 > In practical situations, the private key, as stored, includes not only n > and d, but also p and q, and some other parameters. See PKCS#1 for a > description of a private key storage format which includes n, e, d, > p, q, d mod p-1, d mod q-1 and 1/q mod p. Yes, but I have the situation that only n,d,e are known and the cryptographic device needs CRT parameters. Calculating p,q from n,e,d is simple if de = 1 mod phi(n). It is merely solving a quadratic equation in Z. But calculating p,q from if de = 1 mod lcm(p-1,q-1) is rather more involved. One needs a probabilistic algorithm (which I don't know its name but I think its folklore knowledge) Rainer
From: Mok-Kong Shen on 30 Jan 2010 12:08
Rainer Urian wrote: > Calculating p,q from n,e,d is simple if de = 1 mod phi(n). It is merely > solving a quadratic equation in Z. Could you please tell how to do that by solving one (single) quadratic equation in Z? Thanks, M. K. Shen |