| Ok, I see that many people can't pass the RSA
shallenge, so I decided to write this paper
just for help you to understand how to crack
a low-prime-values RSA cipher.
The RSA Power encryption is in the start, in
the values that the user chouse to put in p
and q, but before we beginning - how RSA
works?
In the first step, the user need to choose two
numbers (P and Q) that most be primes:
P=11
Q=17
Then, he multiply them together:
N=P*Q
N=11*17 =>
[N=187]
After that, he calculate the Phi(n) by Euler
function: Phi(N)=(P-1)(Q-1)
[Phi(N)=(11-1)(17-1) =>
Phi(N)=160]
Now he choose a new number (E) that small from
n: E=7
Now, he can start with the encryption by:
C=M^E (mod N)
M=PlainText, in ASCII
N,E=Public Key.
Then he send "C" - the cipher.
To pull out the M from C, he need to calculate
the "D" - the private key, by:
E * D = 1 (mod (P-1)*(Q-1) )
he know all what he need: E, P and Q.
E=7.
P=11.
Q=17.
so, D equal to:
E * D = 1 (mod (P-1)*(P-1) ) =>
7 * D = 1 (mod Phi(N)) =>
7 * D = 1 (160) =>
D = 23
Now, after he got the d, he can start with
the encryption by: M = C^D (mod N)
M= Plaintext.
C=Ciphertext.
D=Private key.
N=P*Q
and pull out the M - the original massage!
Now, after we understand how this cipher
works, we can start how to break it:
There are some ways to break this cipher,
but part of them needs that the user will
be near to the machine (like the "Timing
attack"), but here we can make kind of
"Cycling attack".
How it works? RSA base on the fact that if
C = M^E (mod N)
then must be number (K) that make:
C^E^K = C (mod N).
and if we find this K (by brutal force or
etc') that return to us the same value that
M^E (mod N) returned - we can pull out the
original massage.
But, if we see that N it not so large (in
our level N=851) so, we can try to make
some program that calculate the P and Q that
together give us N.
We need some primes numbers list (type in
google) and make some brute-force that
multiply the primes, one by one and equal
the value to the public key.
like this:
PrimeAry=[2,3,5,7,11,13,17,19...]
n=VictimPublicKey
FOR a FROM 1 TO SIZE TO N/2 DO
FOR b FROM 1 TO SIZE OF N/2 DO
IF (PrimeAry[a]*PrimeAry[b]=n) THEN
p=PrimeAry[A]
q=PrimeAry[B]
RETURNE q,p
END IF
NEXT b
NEXT a
By this way we can reveal the prime numbers
(P and Q) that will give us N.
After we got q and p we need to find the E
(the part of the Public Key) and after we
got the E, we just need to calculate the D
by Euler function:
E * D = 1 ( mod (P-1)*(Q-1) )
or
E * D = 1 ( mod (Phi(N))
and than we have all the values
that we need to do:
M=C^D (mod N)
C= Ciphertext.
D= Private Key.
N= Public Key.
and pull out the M (our massage...)
Good luck! |