標(biāo)題: RSA - 歐拉數(shù)定理 [打印本頁(yè)] 作者: yuanchengjun 時(shí)間: 2008-04-15 20:23 標(biāo)題: RSA - 歐拉數(shù)定理 1，余數(shù)性質(zhì)
(a^b) mod n = ((a mod n) ^ b ) mod n;
(a * b) mod n = ((a mod n) * (b mod n)) mod n;
……
證明：
設(shè)Z(n) = {x1, x2, x3, ... x∮(n)}
構(gòu)造集合s = {(x1 * m) mod n, (x2 * m) mod n, (x3 * m) mod n, ... (x∮(n) * m) mod n};
先證明兩個(gè)集合相等：
1，任取xi, xj, i != j, 那么 xi != xj, 也即 xi mod n != xj mod n，所以：
(xi * m) mod n != (xj * m) mod n;
2，xi 和 n互質(zhì)，m和n互質(zhì)，那么xi * n mon n 也和 n 互質(zhì)。所以：
s = Z(n);
所以：Z(n)每個(gè)元素相乘等于s每個(gè)元素相乘。
(x1 * x2 * x3 ... x∮(n)) mod n =
(((x1 * m) mod n) * ((x2 * m) mod n) * ((x3 * m) mod n) * ... * ((x∮(n) * m) mod n)) mod n;
右邊 = (((x1 * x2 * x3 ... x∮(n)) mod n) * (m^x∮(n) mod n)) mod n;
兩邊約掉(x1 * x2 * x3 ... x∮(n)) mod n，得到：
1 = m^x∮(n) mod n;
3，RSA
由 2 變換一下，得到：
m^(k * ∮(n) + 1) mod n = m;
k為任意大于0整數(shù)。
指定 n = p * q，p, q為素?cái)?shù)，那么：
∮(n) = (p - q) * (q - 1);
構(gòu)造 e * d = k * (p - 1) * (q - 1) + 1，那么：
m^(e * d) mod n = m;
變換一下，得到：
((m^e) mod n)^d mod n = m;
令：
c = (m^e) mod n;
那么：
m = (c^d) mond n
取(d, n)為私鑰，那么(e, n)為公鑰。
m為明文，c為密文。
公鑰(e, n) 加密 明文m，得到密文c，一般用于加密：
c = (m^e) mod n
私鑰(d, n) 解密 密文c，得到明文m，一般用于解密：
m = (c^d) mod n
私鑰(d, n) 加密 明文m，得到密文c，一般用于簽名：
c = (m^d) mod n
公鑰(e, n) 解密 密文c，得到明文 m，一般用于驗(yàn)證簽名：
m = (c^e) mod n