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:

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 astonishing simplicity system.

I'd like to say that, i have tried to explain things the most easily 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 improove 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, ...).


(c) Lucifer48. All rights reserved & reversed