您的位置：首页 → 精文荟萃 → 破解文章 → RSA 原理

RSA 原理

时间：2004/10/15 0:49:00来源：本站整理作者：蓝点我要评论(0)

　

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

　　　　
　　　　
　　　　　
　　　　
　　　　
　　　　　

相关阅读 Windows错误代码大全 Windows错误代码查询激活windows有什么用Mac QQ和Windows QQ聊天记录怎么合并 Mac QQ和Windows QQ聊天记录Windows 10自动更新怎么关闭 如何关闭Windows 10自动更新windows 10 rs4快速预览版17017下载错误问题Win10秋季创意者更新16291更新了什么 win10 16291更新内容windows10秋季创意者更新时间 windows10秋季创意者更新内容kb3150513补丁更新了什么 Windows 10补丁kb3150513是什么

文章评论

查看所有0条评论>>

发表评论

我来说两句...

提交评论