Cracking Tutorial, (c) Lucifer48 / ID

R.S.A.
(#rsa4newbies)

(v1.0) by Lucifer48 [Immortal Descendants]
(September 30th, 1999)

Ron Rivest, Adi Shamir and Leonard Adleman have created this system in 1978. It is based on the difficulty of factoring a big number, which is the multiplication of two primes.

Contents:

How it works
RSA in 8 lines
Let's play a little
Conclusion

How it works

Assuming that p and q are two prime numbers. And n = p * q

Remark: It is advised to choose big primes. It is easy to find p and q when n is small...

n is the second part of the key (public and private). We must now find a number e, such as e and (p-1)*(q-1) are primes each other.

Remark: The GCD (PGCD in french) is the Greater Common Divisor. To find the gcd of two positive integers, we use Euclid's algo. So:

GCD(a,b) = GCD(b,a) = GCD(b, a mod b)
and GCD(c,0) = c

We say that a and b are prime each other (or a is prime with b) if GCD(a,b)=1.

Remark2: The only inversable items of Z/(p-1)(q-1)Z are the items primes with e. Read below for better understanding.

e is very important, because it will be used for the encryption. Let's compute now the first part of the private key (noticed d).

    d = inv(e) [(p-1)*(q-1)]
<=> d = inv(e) in Z/(p-1)(q-1)Z
<=> e*d = 1 [(p-1)*(q-1)]
<=> d = e^-1 mod ((p-1)*(q-1))

These four lines are equivalent.

More practically, we can use the theorem of Bezout to get the inverse of e:

e * U + ((p-1)*(q-1)) * V = GCD(e,(p-1)*(q-1)) = 1         (U and V are integer)

and then,

U mod ((p-1)*(q-1)) = inv(e) = e^-1

Example: Manual use of the theorem of Bezout:

31 div 13 = 2 remainder 5
13 div 05 = 2 remainder 3
05 div 03 = 1 remainder 1
02 div 01 = 2 remainder 0

GCD(31,13)= 1

1 = 3 - 2
1 = 3 - (5 - 3)
1 = 3*2 - 5
1 = 2*(13 - 5*2) - 5
1 = 2*13 - 4*5 - 5
1 = 2*13 - 5*5
1 = 2*13 -5*(31 - 13*2)
1 = 12*13 - 5*31

You see: inv(13)=12 (in Z/31Z)

Then, it is easy to get d.

The public key is: (e,n).
The private key is: (d,n).

Encryption: The message M to encode must be a number which belong to Z/nZ (share the text converted in number in small blocks of length strictly inferior to the number of digits of n).

 C = M^e [n]

Remark: w belong to Z/nZ if w < n.

DΘcryption: It is very simple too.

 M = C^d [n]

Remark: The message should have been encrypted with d and decrypted with e.

Why it works? Short demonstration. The following calculus are performed in Z/nZ.

C^d = (M^e)^d = M^(ed)
and, e*d = 1 [(p-1)*(q-1)] <=> ed - 1 = k*(p-1)*(q-1)    k is in N*
and then, M^(ed) = M^(k*(p-1)*(q-1) + 1)
Assuming u= k*(p-1)*(q-1) + 1
if M^u = M [p] and M^u = M [q] then, M^u = M [p*q]
and as n=p*q, so
C^d = M

Remark: We could also use the Euler's theorem (not always valid):

If GCD((p-1)*(q-1),M) = 1 then M^((p-1)*(q-1)) = 1
and so, M^(k*(p-1)*(q-1) + 1) = M.1^k = M = C^d
(solely valid if (p-1)*(q-1) and M are prime each other)

RSA in 8 lines

n = p * q  (p et q are prime each other)
GCD(e,(p-1)*(q-1)) = 1
d = e^-1 mod ((p-1)*(q-1))
(e,n): public key.
(d,n): private key.
p and q are no longer useful.
M^e mod n = M_crypted  (M < n)
M_crypted^d mod n = M

Let's play a little

For all these calculation, i have used the program Mathematica. Small preview:

in[1]:=
 PrimeQ[2000]
out[1]=
 False
in[2]:=
 { Prime[1], Prime[2], Prime[3], Prime[4], Prime[2000] }
out[2]=
 { 2, 3, 5, 7, 17389 }
in[3]:=
 PowerMod[157,-1,2668]
out[3]=
 17
in[4]:=
 Mod[1234^31,466883]
out[4]=
 446798
in[5]:=
 FactorInteger[519920418755535776857] //Timing
out[5]=
 {13.35 Second, {{22801763489, 1}, {22801763513, 1}}}
in[6]:=
 Needs["NumberTheory`FactorIntegerECM`"]
in[7]:=
 $Packages
out[7]=
 {NumberTheory`FactorIntegerECM`, Global`, System`}
in[8]:=
 FactorIntegerECM[519920418755535776857] //Timing
out[8]=
 {3.07 Second, 22801763513}
in[9]:=
 breakRSA[x_]:= Module[{i}, i=FactorIntegerECM[x]; List[i, x/i] ]
in[10]:=
 breakRSA[519920418755535776857] //Timing
out[10]=
 {3.07 Second, {22801763513, 22801763489}}

Few examples:

p = 113 ; q = 541 ; n = p * q = 61133 ; (p-1)*(q-1) = 60480.
I choose e = 121 (GCD[121,60480]=1)
inv(e) = 57481 (inferoir to (p-1)*(q-1)) so d = 57481.
For encryption: M=1234567890, i must share M in few blocks of length inferior to n
(4 is here the maximum): M1=1234, M2=5678, M3=90.
C1 = M1^e [n] = 1234^121 [61133] = 40691
C2 = M2^e [n] = 5678^121 [61133] = 19203
C3 = M3^e [n] =   90^121 [61133] = 32121
C = 406911920332121
For decryption, i share the (crypted) message in blocks of length equal to n (here 5).
M1 = C1^d [n] = 40691^57481 [61133] = 1234
M2 = C2^d [n] = 19203^57481 [61133] = 5678
M3 = C3^d [n] = 32121^57481 [61133] = 90
M = 1234567890

p = 3571 ; q = 7919 ; n = p * q = 28278749 ; (p-1)*(q-1) = 28267260.
I choose e = 213889 (GCD[213889,28267260]=1)
inv(e) = 2241409 (inferior to (p-1)*(q-1)) so d = 2241409.
M ="Hello world" = 7210110810811132119111114108100, i share in blocks of length 7:
M1 = 7210110, M2 = 8108111, M3 = 3211911, M4 = 1114108, M5 = 100.
C1 = M1^e [n] = 7210110^213889 [28278749] = 12840449
C2 = M2^e [n] = 8108111^213889 [28278749] = 16339096
C3 = M3^e [n] = 3211911^213889 [28278749] = 25181491
C4 = M4^e [n] = 1114108^213889 [28278749] = 24666021
C5 = M5^e [n] =     100^213889 [28278949] = 17846443
C = 1284044916339096251814912466602117846443
I share C in blocks of 8 digits.
M1 = C1^d [n] = 12840449^2241409 [28278749] = 7210110
M2 = C2^d [n] = 16339096^2241409 [28278749] = 8108111
M3 = C3^d [n] = 25181491^2241409 [28278749] = 3211911
M4 = C4^d [n] = 24666021^2241409 [28278749] = 1114108
M5 = C5^d [n] = 17846443^2241409 [28278749] = 100
M = 7210110810811132119111114108100

p = 10007 ; q = 53239 ; n = p * q = 532762673 ; (p-1)*(q-1) = 532699428.
I choose e = 17 (GCD[17,532699428]=1)
inv(e) = 62670521 (inferior to (p-1)*(q-1)) so d = 62670521.
M = 123
C = M^e [n] =       123^17       [532762673] = 270099428
M = C^d [n] = 270099428^62670521 [532762673] = 123

Conclusion

The RSA system is not perfect, its slowness is its main deficiency. The choice of e and d must not be done at random. However, it is an astonishingly simple system.

I'd like to say that, I have tried to explain things in easiest way possible, keeping some strictness with writing; I hope that mathematicians won't be scandalized by reading this ;) However, if there is a mistake or something imprecise (even for correcting my lame english), thanks to mail me (according to you that my demonstration is a little incomplete...) ; I would be glad to improve this essay :)

Greetings: All ID members (Volatility, Torn@do, alpine, ...), SiFLyiNG, Eternal Bliss, ACiD BuRN, Duelist, LaZaRuS, ... and wonderful people in #cracking4newbies & #win32asm (WazerPup, X-Calibre, MisterE, ...).