(#rsa4newbies)

(v1.0) by Lucifer48 [Immortal Descendants]

(September 30th, 1999)

Ron

How it works

RSA in 8 lines

Let's play a little

Conclusion

Assuming that

GCD(a,b) = GCD(b,a) = GCD(b, a mod b) and GCD(c,0) = cWe say that a and b are prime each other (or a is prime

d = inv(e) [(p-1)*(q-1)] <=> d = inv(e) inThese four lines are equivalent.<=> e*d = 1 [(p-1)*(q-1)] <=> d = e^-1 mod ((p-1)*(q-1))Z/(p-1)(q-1)Z

More practically, we can use the theorem of

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

Umod ((p-1)*(q-1)) = inv(e) = e^-1

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)Then, it is easy to get1 = 12*13 - 5*31You see:inv(13)=12(in)Z/31Z

The public key is:

The private key is:

C = M^e [n]

M = C^d [n]

C^d = (M^e)^d = M^(ed) and, e*d = 1 [(p-1)*(q-1)] <=> ed - 1 = k*(p-1)*(q-1)kis inand then, M^(ed) = M^(k*(p-1)*(q-1) + 1) AssumingN*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

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

n = p * q(p et q are prime each other) GCD(e,(p-1)*(q-1)) = 1d = 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

For all these calculation, i have used the program

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] //Timingout[5]= {13.35 Second, {{22801763489, 1}, {22801763513, 1}}} in[6]:=Needs["NumberTheory`FactorIntegerECM`"]in[7]:=$Packagesout[7]= {NumberTheory`FactorIntegerECM`, Global`, System`} in[8]:=FactorIntegerECM[519920418755535776857] //Timingout[8]= {3.07 Second, 22801763513} in[9]:=breakRSA[x_]:= Module[{i}, i=FactorIntegerECM[x]; List[i, x/i] ]in[10]:=breakRSA[519920418755535776857] //Timingout[10]= {3.07 Second, {22801763513, 22801763489}}

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

The RSA system is not perfect, its slowness is its main deficiency. The choice of

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

(c) Lucifer48. All rights reserved & reversed