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] [3] [4] 下一页