RSA算法使用心得
RSA
1,RSA
RSA算法是非对称算法,使用大数分解原理得到，主要过程主要用到费马小定理，
详细数学证明见附加信息
2,RSA
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
能够将其分解 从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法求得d。
:
找两个素数:
p=47
q=59
这样
n=p*q=2773
t=(p-1)*(q-1)=2668
寻找e 满足ebits + 7) / 8 - 11;
2
RSA核心加密算法加密的数据长度为
modulusLen = (publicKey->bits + 7) / 8;
那么要补偿11位的数据(
)
其中第1，2（为模式）
以后的2－10为0xff
11位为0
具体的算法见
vss2\Development\Framework\Product\c++ common\encrypt\rsa\rsa.c
3
1
大数的加减乘除方法，详细参见
vss2\Development\Framework\Product\c++common\encrypt\rsa\n
n.c
2, (m^e mod n)
a = (b * c) % d <==> ( (a % d )*( c % d) ) % d
可以使用分解成(b *c) % d
运算次数可以分解为log(c)
3
,
4
1,一种方法是与加密过程类似解密 使用解密密钥
2,
:
p, q , rm == 1 mod (p-1)(q-1),
a, b == a^m mod pq, c == b^r mod pq,
c == a mod pq ( pq>=a > 0 c==a)
:
证明的过程, 会用到费马小定理, 叙述如下: m 是任一质数, n 是任一整数, 则 n^m == n mod m
注意注释 写法的意思同( (n^m) mod m ) = (n mod m ) )
(换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m) 运用一些基本的群论的知识, 就可以很容易地证出费马小定理的........
证明
因为 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整数
因为在 modulo 中是 preserve 乘法的 (x == y mod z and u == v mod z => xu == yv mod z),
所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq
1. 如果 a 不是 p 的倍数, 也不是 q 的倍数时,
则 a^(p-1) == 1 mod p (费马小定理) => a^(k(p-1)(q-1)) == 1 mod p
a^(q-1) == 1 mod q (费马小定理) => a^(k(p-1)(q-1)) == 1 mod q
所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1
即 a^(k(p-1)(q-1)) == 1 mod pq
=> c == a^(k(p-1)(q-1)+1) == a mod pq
2. 如果 a 是 p 的倍数, 但不是 q 的倍数时,
则 a^(q-1) == 1 mod q (费马小定理)
=> a^(k(p-1)(q-1)) == 1 mod q
=> c == a^(k(p-1)(q-1)+1) == a mod q
=> q | c - a
因 p | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod p
=> p | c - a
所以, pq | c - a => c == a mod pq
3. 如果 a 是 q 的倍数, 但不是 p 的倍数时, 证明同上
4. 如果 a 同时是 p 和 q 的倍数时,
则 pq | a
=> c == a^(k(p-1)(q-1)+1) == 0 mod pq
=> pq | c - a
=> c == a mod pq
浙公网安备 33021202002483