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, ...).