RSA - 欧拉数定理

yuanchengjun

1，余数性质
(a^b) mod n = ((a mod n) ^ b ) mod n;
(a * b) mod n = ((a mod n) * (b mod n)) mod n;
……

2，欧拉数定理
一个数n，比n小且与n互质的数的个数为欧拉数，记做∮(n)；同时，这∮(n)个素数集合，记做Z(n)。

定理：如果m < n，且与n互质，那么：
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互质，m和n互质，那么xi * n mon n 也和 n 互质。所以：
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整数。

指定 n = p * q，p, q为素数，那么：
∮(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二进制数据 和 大数之间转换，以及 加密填充
参考：RFC2313(PKCS #1 v1.5)

转换：
先输入的在左侧的是数的高位，是一个字节一个字节的。
每个字节表示8位的即 0~(2^8 - 1)，
RFC2313中OCT String，8进制字符串。


填充

如果是公钥操作：
00 02 非零随机数 00 原文

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

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