R.S.A.
(#rsa4newbies)

(v1.2) par Lucifer48 [Immortal Descendants]
(5 Février 2000)

Ron Rivest, Adi Shamir et Leonard Adleman ont inventé ce système en 1978. Il est basé sur la difficulté de factoriser un nombre qui est le produit de deux nombres premiers.

Sommaire:

   Principe du RSA
   RSA en 8 lignes
   Un peu de pratique
   Conclusion
RSA 由 从事发明这个方法在1987年。这个方法的难点来自因式分解（把复杂计算分解为基本运算）一个数字招致（引出）两个素数计算。

摘要:

   RSA 原理
   8个符号线索在RSA中
   一个小的实践
   总结

RSA 原理

Soient p et q, deux nombres premiers. Posons: n = p * q

Remarque: Il est conseillé de choisir des grands nombres premiers. En effet, il est facile de retrouver p et q lorque n est petit...

用两个很大的质数，p 和 q，计算它们的乘积 n = pq；n 是模数。选择一个比 n 小的数 e，它与 (p - 1)(q - 1) 互为质数，即，除了 1 以外，e 和 (p - 1)(q - 1) 没有其它的公因数。找到另一个数 d，使 (ed - 1) 能被 (p - 1)(q - 1) 整除。值 e 和 d 分别称为公共指数和私有指数。公钥是这一对数 (n, e)；私钥是这一对数 (n, d)。

Remarque: 这个 PGCD (GCD 是 英语 Greatest Common Divisor最大公约数) 我们利用(古希腊数学家).欧几里得的, 欧几里得几何学 Ansi:

PGCD(a,b) = PGCD(b,a) = PGCD(b, a mod b)
et PGCD(c,0) = c

我们现在提出a 和 b 之间的关系 PGCD(a,b)=1. 在这里是也可能找出: a 存在于早期的 b.

Remarque2: 它们仅仅是倒置的来自 Z/(p-1)(q-1)Z 存在于最初的 e. 阅读这个次序可以更好地了解.

e 是非常重要的，因为它是明确的译码. 推出关键的 d  (notons la 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))

利用这4个符号

我们将获得相反的 e:

e * U + ((p-1)*(q-1)) * V = PGCD(e,(p-1)*(q-1)) = 1         (U et V sont des entiers)

et donc,

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

事例:

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

PGCD(31,13)= 1;31 and 13 进入它们

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

和关于: inv(13)=12 (in Z/31Z)

容易的引出 d.

公共钥匙: (e,n).
私有钥匙: (d,n).

Encryption: 它通知 M 加密一个数属于 Z/nZ (严格的说来自 n).

C = M^e [n]

Remarque: w 属于 Z/nZ 无论是否 w < n.

Décryption: 这是非常自然的.

M = C^d [n]

C^d = (M^e)^d = M^(ed)
de plus, e*d = 1 [(p-1)*(q-1)] <=> ed - 1 = k*(p-1)*(q-1)    k est dans N*
par suite, M^(ed) = M^(k*(p-1)*(q-1) + 1)
Posons u= k*(p-1)*(q-1) + 1
si M^u = M [p] et M^u = M [q] alors, M^u = M [p*q]
et comme n=p*q, il s'ensuit que
C^d = M

Remarque: On aurait pu aussi utiliser le théorème d'Euler (mais n'est pas valable tout le temps):

Si PGCD((p-1)*(q-1),M) = 1 alors M^((p-1)*(q-1)) = 1
et donc, M^(k*(p-1)*(q-1) + 1) = M.1^k = M = C^d
(valable uniquement si (p-1)*(q-1) et M sont premiers entre eux)

RSA en 8 lignes

n = p * q  (p et q sont premiers)
PGCD(e,(p-1)*(q-1)) = 1
d = e^-1 mod ((p-1)*(q-1))
(e,n): clef publique.
(d,n): clef privée.
p et q ne servent plus...
M^e mod n = M_crypté  (M < n)
M_crypté^d mod n = M

Un peu de pratique

Pour tous les calculs, j'ai utilisé le logiciel Mathematica. Petit aperçu:

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}}
in[11]:=
GCD[31,13]
out[11]=
1
in[12]:=
ExtendedGCD[31,13]
out[11]=
{1, {-5, 12}}

Remarque (重要的): 对于计算它们的类型: a^b [n] (b 正数), ne surtout pas utiliser la fonction Mod[a^b, n] mais PowerMod[a,b,n] qui est carrément plus rapide.

Quelques exemples:

  *

p = 113 ; q = 541 ; n = p * q = 61133 ; (p-1)*(q-1) = 60480.
Je choisis e = 121 (GCD[121,60480]=1)
inv(e) = 57481 (inférieur à (p-1)*(q-1)) donc d = 57481.
Pour crypter M=1234567890, je dois donc découper M en petits morceaux de longueur
inférieur à n (4 est ici le 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
Pour décrypter, je découpe le message (crypté) en morceaux de longueur n (ici 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.
Je choisis e = 213889 (GCD[213889,28267260]=1)
inv(e) = 2241409 (inférieur à (p-1)*(q-1)) donc d = 2241409.
M ="Hello world" = 7210110810811132119111114108100, je découpe en morceaux de longueur 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
On découpe le C en morceaux de 8 chiffres.
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.
Je choisis e = 17 (GCD[17,532699428]=1)
inv(e) = 62670521 (inférieur à (p-1)*(q-1)) donc d = 62670521.
M = 123
C = M^e [n] =       123^17       [532762673] = 270099428
M = C^d [n] = 270099428^62670521 [532762673] = 123

in[1]:=
solveRSA[n_, e_]:= Module[{j},  j=breakRSA[n]; PowerMod[e, -1, (First[j]-1)*(Last[j]-1)]]
in[2]:=
solveRSA[532762673, 17]
out[2]=
Out[12]= 62670521

总结
[一下总结明天再译] [来朋友了]

RSA确实存在着这样的一个不完美体系，它是不确定的存在缺陷于它的基础原理，他选择来自 e and d 的算法没有成熟存在着反相的偶然性，无论如何，在这里它是令人惊讶的简单，脆弱。
告诫一些程序尽量不要使用它来加密数据，尽管反相的推断它存在着很大的偶然性，在这里它还是表现得很脆弱。[下面是感谢的话，我不译了]
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

况有狂朋怪侣，遇当歌、对酒竞留连。那堪酒醒，又闻空阶，夜雨频滴。嗟因循、久作天涯客。