http://www.sufeinet.com/plugin.php?id=keke_group

苏飞论坛

 找回密码
 马上注册

QQ登录

只需一步,快速开始

分布式系统框架(V2.0) 轻松承载百亿数据,千万流量!讨论专区 - 源码下载 - 官方教程

HttpHelper爬虫框架(V2.7-含.netcore) HttpHelper官方出品,爬虫框架讨论区 - 源码下载 - 在线测试和代码生成

HttpHelper爬虫类(V2.0) 开源的爬虫类,支持多种模式和属性 源码 - 代码生成器 - 讨论区 - 教程- 例子

查看: 6079|回复: 3

[加密/解密] RSA公钥密码算法的原理及实现

[复制链接]
发表于 2015-5-6 16:46:57 | 显示全部楼层 |阅读模式
最近发现腾讯的webQQ加密算法更改了,所以就看了一下腾讯的加密算法,以前总体的来说就是二进制、八进制、十六进制转换、md5转换、移位运算<<等混合操作来加密。查看新的加密文件mq_comm.js时发现新的算法可能是用RSA Encryption相关算法来实现的。RSA算法应该在几年前就遇到过很多次,但每次都因为复杂的数论知识而没看懂其算法(这也验证了编程的核心是算法,算法的核心是数学的思维,同时也回答了纯数字有什么用的问题。),这次静下心来仔细看了一下,将学习成果总结如下:(下面的文章,遇到不懂的地方可以先了解大概,然后继续看,后面会有详细介绍。看完再回头研究。)
(感谢阮一峰http://www.ruanyifeng.com/blog/archives.html ,最新查找的东西几乎都是在他的网络日志中找到的。无论是设计模式还是加密算法。)

美国麻省理工学院的Rivest、Shamir 和 Adleman 实现了非对称加密算法,用他们名字命名叫RSA算法。是目前使用最广最优秀的加密算法,几乎有网络的地方就要用到它。

对称加密算法DES:加密,解密采用同一密钥。

非对称加密算法RSA:加密采用公钥,解密用私钥,公钥解不开。


一、加密,解密过程。

假设:n=3233,e=17,d=2753

公钥(n,e) =(3233,17),私钥(n,d)=(3233, 2753)


6、加密:公钥(n,e) =(3233,17),加密公式:me ≡ c (mod n)

已知明文m,公钥n,e,求密文c.

eg:明文m=65,加密为密文C=2790

m=65à代入公式:6517 ≡ 2790 (mod 3233)à c=2790


7、解密:私钥(n,d)=(3233, 2753),解密公式:cd ≡ m (mod n)

已知密文c,私钥n,d,求明文m。

密文C=2790,解密为明文m=65

c=2790à带入公式27902753 ≡ 65 (mod 3233)àm=65


二、密钥生成:

1、任选两质数p,q。

2、模数n=p*q。

3、欧拉函数φ(n)=(p-1)(q-1)。

4、随机数e,满足1< e < φ(n),且e与φ(n) 互质

5、模逆d,公式ed ≡ 1 (mod φ(n))


eg: p=61,q=53,n=3233,φ(n)=3120,e=17,d=2753

1、p=61,q=53

2、n = 61×53 = 3233

3、φ(3233)=60×52=3120

4、e=17

5、d=2753

说明:

1、p、q越大,越难破解。

2、n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

4、在1到3120之间,随机选择了17。实际中,常常选择65537。

5、计算e对于φ(n)的模反元素d。使得ed被φ(n)除的余数为1。

d计算步骤:ed ≡ 1 (modφ(n))èed - 1 = kφ(n)èex + φ(n)y = 1已知e=17,φ(n)=3120è17x + 3120y = 1 "扩展欧几里得算法"(x,y)=(2753,-15)è即d=2753。

6、实际中,公钥和私钥的数据都采用ASN.1格式表达。

m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

如果要加密大于n的整数,有两种解决方法:①把长信息分割成若干段短消息,每段分别加密;②先选择一种"对称性加密算法"(如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

三、私钥解密证明

为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子:

  cd ≡ m (mod n)

因为,根据加密规则

  me ≡ c (mod n)

于是,c可以写成下面的形式:

  c = me - kn

将c代入要我们要证明的那个解密规则:

  (me - kn)d ≡ m (mod n)

它等同于求证

  med ≡ m (mod n)

由于

  ed ≡ 1 (mod φ(n))

所以

  ed = hφ(n)+1

将ed代入:

  mhφ(n)+1 ≡ m (mod n)

接下来,分成两种情况证明上面这个式子。

(1)m与n互质。

根据欧拉定理,此时

  mφ(n) ≡ 1 (mod n)

得到

  (mφ(n))h × m ≡ m (mod n)

原式得到证明。

(2)m与n不是互质关系。

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。

以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

  (kp)q-1 ≡ 1 (mod q)

进一步得到

  [(kp)q-1]h(p-1) × kp ≡ kp (mod q)

  (kp)ed ≡ kp (mod q)

将它改写成下面的等式

  (kp)ed = tq + kp

这时t必然能被p整除,即 t=t'p

  (kp)ed = t'pq + kp

因为 m=kp,n=pq,所以

  med ≡ m (mod n)

原式得到证明。

说明:1、由于n等于质数p和q的乘积,所以m必然等于kp或kq

因为m与n不是互质关系,说明m与n有共同的公因子g,假设m=hg,由于n=pq,p与q互质,n只有p和q两个因子,所以g和h必然有一个等于q或者p, 所以才有结论“m必然等于kp或kq”

2、t=t'p

因为(kp)ed = tq + kp,=>(p)ed*(k)ed = tq + kp,=>

(p)ed*(k)ed - kp = tq,=>

p[(p)(ed-1)*(k)ed - k ] = tq,

左边是p的倍数,那右边必然也是p的倍数。因为p与q互质,所以t必然是p倍数,即 t=t'p

3、m与n互质。根据欧拉定理,此时mφ(n) ≡ 1 (mod n)

怎么得到(mφ(n))h × m ≡ m (mod n)”?

mφ(n) ≡ 1 (mod n) => mφ(n) = K n +1 , k为自然数

(kn + 1)^h 展开多项式,除了1以外,全部含有kn, 所以其他项都能被n整除而余1.

推出 (mφ(n))h ≡ 1 (mod n)

设(mφ(n))h=r1*n+1,然后(mφ(n))h*m=(r1*n+1)*m,这个和n的余数就是m。




1. 开通SVIP会员,免费下载本站所有源码,不限次数据,不限时间
2. 加官方QQ群,加官方微信群获取更多资源和帮助
3. 找站长苏飞做网站、商城、CRM、小程序、App、爬虫相关、项目外包等点这里
 楼主| 发表于 2015-5-6 16:54:48 | 显示全部楼层
宝座!
回复

使用道具 举报

 楼主| 发表于 2015-5-6 16:56:34 | 显示全部楼层
:):):):):):):):):):):):):):):):):):)
发表于 2015-5-6 23:45:10 | 显示全部楼层
膜拜中....!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 马上注册

本版积分规则

QQ|手机版|小黑屋|手机版|联系我们|关于我们|广告合作|苏飞论坛 ( 豫ICP备18043678号-2)

GMT+8, 2024-12-23 04:44

© 2014-2021

快速回复 返回顶部 返回列表