RSA算法使用心得.docVIP

RSA算法使用心得 一、算法基础 1,RSA算法基础 RSA算法是非对称算法,使用大数分解原理得到，主要过程主要用到费马小定理，详细数学证明见附加信息 2,RSA算法描述 找两素数p和q 取n=p*q 取t=(p-1)*(q-1) 取任何一个数e,要求满足et并且e与t互素（就是最大公因数1） 取d*e%t==1 即(e * d) % ((p-1)*(q-1)) == 1 这样最终得到三个数： n d e 设消息为数M (M n) 设c=(M^d)%n就得到了加密后的消息c 设m=(c^e)%n则 m == M，从而完成对c的解密。 注：^表示次方,上面两式中的d和e可以互换。具体过程看证明 3,RSA算法举例 在非对称加密中： n d两个数构成公钥，可以告诉别人； n e两个数构成私钥，e自己保留，不让任何人知道。 给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。 别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。 rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解 从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法求得d。 二、举例: 找两个素数: p=47 q=59 这样 n=p*q=2773 t=(p-1)*(q-1)=2668 寻找e 满足et并且e和t互素 找到e=63 寻找d 使e*d%t ==1 得到 d=847 那么 n=2773 d=847 n=2773 e=63 取加密 c＝465perl -Mbigint -e print 465**847%2773 结果为1118 使用解密结果 perl -Mbigint -e print 1118**63%2773 结果为465 这里一般在加密过程之中 取e=65537 三、应用OpenSSL库里的RSA函数过程 1，加密分组 使用RSA加密的分组长度为 modulusLen = (publicKey-bits + 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\nn.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