RSA算法使用心得.doc

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=(Md)%n就得到了加密后的消息c 设m=(ce)%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=47q=59这样n=p*q=2773t=(p-1)*(q-1)=2668寻找e 满足ebits + 7) / 8 - 11;2，数据补偿RSA核心加密算法加密的数据长度为modulusLen = (publicKey-bits + 7) / 8;那么要补偿11位的数据(很多算法加密结果不一样的原因大都是由这个原因引起的) 其中第1，2（为模式）以后的210为0xff11位为0具体的算法见 vss2DevelopmentFrameworkProductc+ commonencryptrsarsa.c3，核心算法1，大数运算大数的加减乘除方法，详细参见vss2DevelopmentFrameworkProductc+commonencryptrsann.c2, 高阶求模(me 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 = am mod pq, c = br mod pq, 则 c = a mod pq (补充 如果 pq=a 0 那么 c=a)证明的过程:证明的过程, 会用到费马小定理, 叙述如下: m 是任一质数, n 是任一整数, 则 nm = n mod m 注意注释 写法的意思同( (nm) 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 = br = (am)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 的倍