RSArsa加密算法 c有那么牛吗

来源：蜘蛛抓取(WebSpider) 时间：2016-11-30 07:43 标签： rsa算法c语言实现
1720人阅读
编程之美（29）
数学（19）
本文由&@&出品，转载请注明出处。&
文章链接：&
目前世界上最重要的算法RSA的数学原理摘要
1至6是从阮一峰的博文（见参考链接）中抽出来的，算是自己理解这个算法的一个记录吧。
1、欧拉函数φ(n)：小余等于n的正整数中，与n互质的数的个数
2、欧拉定理：如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：a^φ(n) ≡ 1(mod n)
导出费马小定理: 假设正整数a与质数p互质，因为p为质数,φ(p)=p-1，则欧拉定理可以写成a^(p-1) ≡ 1(mod p)
3、模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
欧拉定理可以用来证明模反元素必然存在：a^φ(n) = a*a^[φ(n)-1] ≡ 1(mod n)，可以看到，a^[φ(n)-1]，就是a的模反元素。
4、推论：随机质数p、q，p*q = n, &φ(n) = (p-1)*(q-1), &随机选择一个整数e, &1 & e & φ(n)，且e与φ(n)互质，计算e对于φ(n)的模反元素d，使得 ed ≡ 1 (mod φ(n))。这种条件下，如果正整数m&n且m^e≡c(mod n)，一定有c^d≡m(mod n)。 & 【这条推论才是实际RSA应用的基础，证明见参考链接二】
5、加解密应用：
1）使用公钥(n,e)加密明文m(m&n)：从m^e≡c(mod n)计算出c.
2）使用私钥(n,d)解密密文c：从c^d≡m(mod n)计算出m.
6、可靠性分析：
在只公开公钥(n,e)的情况下，计算d需要知道φ(n)，继而需要知道p、q，而由p、q知道n很容易，但是n分解成p、q很难，所以p、q足够大时暂时还未被破解。
千言万语汇成一句话：p q , n = p*q , ed = 1 (mod φ(n)) , m^e ≡ c (mod n) =& c^d ≡ m (mod n)
7、实际应用中的补足(Padding)和算法性能优化：
补足待补充；
优化：实际应用中，e比较小，求得的d比较大。解密时计算c^d比较慢。根据中国剩余定理，c^d mod n =&c^d mod (p*q)& = &(c^dp mod p) *( c^dq mod q)， dp = d mod (p-1) ，dq = d mod (q-1)
参考链接：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：699747次
积分：5985
积分：5985
排名：第3142名
原创：173篇
转载：80篇
评论：116条
文章：13篇
阅读：13472
文章：18篇
阅读：296587
文章：23篇
阅读：33294
阅读：3796
文章：14篇
阅读：40096
文章：24篇
阅读：21468
(2)(2)(2)(2)(8)(27)(2)(8)(7)(23)(1)(5)(7)(3)(10)(2)(1)(4)(5)(2)(5)(8)(4)(2)(1)(12)(8)(2)(2)(2)(1)(6)(4)(5)(9)(8)(4)(2)(3)(5)(2)(3)(1)(1)(3)(8)(1)(3)(4)(1)(4)(6)(4)(1)

我要回帖

更多关于 rsa算法c语言实现 的文章

 

随机推荐