Re: RSA and Number Theory

From: Scott Contini (contini@matmail.com)
Date: 02/13/03 

From: contini@matmail.com (Scott Contini)
Date: 12 Feb 2003 15:02:54 -0800

>
> It may be the case that e^8 was not congruent to 1 mod phi(n) but you
> still recovered the plaintext. In that case, e^8 is congruent to 1 modulo
> a (most likely) large divisor of phi(n) . The same type of factoring
> attack may apply here, though it is not guaranteed to succeed.
>

I just tested my conjectures using Magma, and the above paragraph
turns out
to be the case. Specifically, we have:

e^8 == 1276490454721 mod phi(n)
where phi(n) = 1571065175040.

The value 24547893360 is a large divisor of phi(n).
and e^8 == 1 mod 24547893360.

Let's see if we can factor the number (assuming we did not know
phi(n)).

The idea is similar to what is used in the strong-pseudo
prime/miller-rabin
test. First compute ee = (e^8 - 1)/2^k where k is the highest
power of 2
that you can divide out. In this case, k = 6 .

We have

ee = 3060929930688885646506837890282423365318413122524110259185778497329815777638169\
128795

Then compute pt^[ 2^j * ee ] mod n for values of j from 0..k
until you
get 1. This happens at j = 6 . That means s = pt^[ 2^5 * ee ] mod
n is a
square root of 1. If it is a nontrivial square root, we can factor n
.
We compute it, and it turns out to be : s = 1282307137219.

We know s^2 == 1 mod n . So (s-1)*(s+1) == 0 mod n . Compute
GCD(s-1, n)
to see if it is a prime factor. It turns out to indeed be the case.
The
prime factor is 534697.

Bottom line: you can (with at least 50% chance) factor n whenever
you find
a plaintext that cycles much sooner than expected, but this does not
work for
trivial plaintexts such as 1 and -1.

Scott

Quantcast