RSA - 歐拉數(shù)定理

yuanchengjun

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;
……

2，歐拉數(shù)定理
一個數(shù)n，比n小且與n互質(zhì)的數(shù)的個數(shù)為歐拉數(shù)，記做∮(n)；同時，這∮(n)個素數(shù)集合，記做Z(n)。

定理：如果m < n，且與n互質(zhì)，那么：
m^∮(n) mod n = 1;

證明：
設Z(n) = {x1, x2, x3, ... x∮(n)}
構造集合s = {(x1 * m) mod n, (x2 * m) mod n, (x3 * m) mod n, ... (x∮(n) * m) mod n};

先證明兩個集合相等：
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)每個元素相乘等于s每個元素相乘。
(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為素數(shù)，那么：
∮(n) = (p - q) * (q - 1);

構造 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，一般用于驗證簽名：
m = (c^e) mod n

4，RSA二進制數(shù)據(jù) 和 大數(shù)之間轉(zhuǎn)換，以及 加密填充
參考：RFC2313(PKCS #1 v1.5)

轉(zhuǎn)換：
先輸入的在左側(cè)的是數(shù)的高位，是一個字節(jié)一個字節(jié)的。
每個字節(jié)表示8位的即 0~(2^8 - 1)，
RFC2313中OCT String，8進制字符串。


填充

如果是公鑰操作：
00 02 非零隨機數(shù) 00 原文

如果私鑰操作：
00 01 FF FF FF ... FF FF 00 原文

[ 本帖最后由 yuanchengjun 于 2008-4-15 21:06 編輯 ]