yes, but the attack does not work (efficiently). We analyzed
it together with Ariel Futoransky and Calos Sarraute and
judged it highly impractical (no complexity estimates could
be found on the post/news). Later we read a mail which was
signed by Rivest himself in which he said that the attack was
of a complexity worse than a brute force attack.

To understand more precisely, this attack finds cycles
of the form 1,2,2^2,...2^x,1. This integer x sheds info
about the private exponent, e.g. (x+1) serves as a private
exponent for a number of ciphertexts (but not all, only the
ones in the uncovered cycle) and is sometimes but not
always a multiple of the private exponent. Doing this
implies that --when using 1024 bits keys-- you have to
check if a number of size 2^1024, e.g. 2^(2^1024), is
congruent to 1 modulo the public exponent n. Hence you
at least need to store 2^1024 digits in your computer
which is a more than a lot.

Ariel Waissbein

Andre Delafontaine wrote:
> The following link was sent to me this morning.
> Has anybody heard about this, gotten any more info?
> Is this TRUE? :-)
> Andre
> --
>              andre.delafontaine at
>   F20 DSS: BD75 66D9 5B2C 66CE 9158  BB27 B199 59CE D117 4E9F
>    F16 RSA: F8 04 FE 50 02 B5 03 02  F6 87 C7 8D F9 2E B8 58

===========[ CORE Seguridad de la Informacion S.A. ]=========
Ariel Waissbein
Researcher - Corelabs


I was scared. Petrified. Because (x) hearing voices isn't like
catching a cold, you can't get rid of it with lemmon tea (y)
it's inside, it is not some naevus, an epidermal blemish you
can cover up or cauterise (z) I had no control over it. It was
there of its own volition, just stopped in and (zz) I was going
-Tibor Fischer ``TheThought Gang"

--- For a personal reply use [EMAIL PROTECTED]

Reply via email to