RSA 原理

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

（出处：赢政天下收集整理）

相关文章：

·ASProtect的加密算法初步分析

·加密算法之RSA算法

·加密算法之DES算法

·加密算法之ElGamal算法

·加密算法之DSA算法

·加密算法之MD5算法

·加密算法之BLOWFISH算法

·ECC加密算法入门介绍

相关软件：

·共享软件加密算法库 V3.2

→ 特别推荐

→ 热点TOP10

我为人人《《==》》人人为我

关于我们 |

帮助(？)

| 广告服务 |

版权声明 |

商业合作 |

发展历程 |

加盟我们 |

联系我们

Copyright © 1999-2003

winzheng.com All Rights Reserved.

繁体版:由华琦数码技术提供

Powered

by:MeSky.Net