(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)
|