security of single rsa bits

Hamdi Tounsi (hamdi@ati.tn)
Thu, 16 Jul 1998 10:00:07 +0200

• Next message: Cicero: "Re: Random Data from Geiger Counter"
• Previous message: Bill Frantz: "Re: One real life secure random generator"

hi all coders
as you know, the security of single rsa bits came into light again after

the recent pkcs#1 attack which recovers the plaintext from ciphertext
using partial information about the plaintext (results of queries to an
oracle)
the basic method for inverting rsa used by alexi, chor, goldreich and
schnorr (RSA/Rabin bits are 1/2 +1/poly(log N) secure) is based upon :
plaintext : x
ciphertext c
select a,b from Z/N at random ( /N denotes modulo N)
compute the GCD([ax]/N,[bx]/N), which yields g such that [gx]/N =
GCD([ax/N],[bx/N])
the gcd computation uses a parity routine which given y and E(x)
(ciphertext), queries an oracle to determine the least significant bit
of (yx)

the rsa inversion procedure is based upon the fact that if [ax]/N and
[bx]/N are relatively prime, then their GCd which is [gx]/N is equal to
one. this fact can be detected since we can easily compute E([gx]/N)
which will be equal to one if [gx]/N is equal to one. in this cas the
plaintext x is recovered x = g**-1 /N

any comments ?

hamdi

• Next message: Cicero: "Re: Random Data from Geiger Counter"
• Previous message: Bill Frantz: "Re: One real life secure random generator"