文档章节

RSA原理与实例

青木河
 青木河
发布于 2016/03/02 16:14
字数 2453
阅读 627
收藏 12
rsa

1 数学概念

1.1 质数

质数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。

例如,15=3*5,所以15不是质数;12=6*2=4*3,所以12也不是质数;13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个质数。

质数也称为“素数”。

1.2 互质数

互质数为数学中的一种概念,公因数只有1的两个非零自然数,叫做互质数。

关于互质数,有以下定理:

(1)两个质数一定是互质数。例如,2与7、13与19。

(2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3与10、5与 26。

(3)1不是质数也不是合数,它和任何一个自然数在一起都是互质数。如1和9908。

(4)相邻的两个自然数是互质数。如 15与 16。

(5)相邻的两个奇数是互质数。如 49与 51。

(6)大数是质数的两个数是互质数。如97与88。

(7)小数是质数,大数不是小数的倍数的两个数是互质数。如 7和 16。

1.3 取模运算

一个整数m,以n为模做取模运算,记作 m mod n。

怎样做呢?让m去被n整除,只取所得的余数作为结果,就叫做取模运算。

例如,10 mod 3=1;26 mod 6=2;28 mod 2 =0等等。 

1.4 同余符号

两个整数a,b,若它们以整数n为模,做取模运算,所得的余数相等,则称a,b对于模n同余。记作 a≡b mod n。

比如26 ≡ 14 mod 12

PS: ”≡“,非”=“

2 RSA算法描述

(1)选择一对不同的、足够大的互质数p,q。

(2)计算n=pq。

(3)计算f(n)=(p-1)(q-1),同时对p, q严加保密,不让任何人知道。

(4)随机找一个与f(n)互质的数e,且1<e<f(n)。

(5)计算d,使得de≡1 mod f(n)。 显而易见,不管f(n)取什么值,符号右边1 mod f(n)的结果都等于1;符号的左边d与e的乘积做模运算后的结果也必须等于1。这就需要计算出d的值,让这个同余等式能够成立。

(6)公钥KU=(n,e),私钥KR=(n,d)。

(7)加密时,先将明文变换成0至n-1的一个整数M。若明文较长,可先分割成适当的组,然后再进行交换。

设原文为M,密文为C,则加密过程为:

解密过程为:

PS: ”=“,非”≡“

回顾上面的密钥生成步骤,一共出现六个数字:

p
q
n
f(n)
e
d

3 RSA实例

在这篇科普小文章里,不可能对RSA算法的正确性作严格的数学证明,但我们可以通过一个简单的例子来理解RSA的工作原理。为了便于计算。在以下实例中只选取小数值的素数p,q,以及e,假设用户A需要将明文“key”通过RSA加密后传递给用户B。(灰色为不公开的数据,绿色为需要公开的数据)

3.1 设计公钥KU=(n,e),私钥KR=(n,d)

(1)p=3,q=11

(2)n=pq=3x11=33

(3)f(n)=(p-1)(q-1)=2×10=20

(4)随机取e=3(3与20互质),则e×d≡1 mod f(n),即3×d≡1 mod 20

d怎么取呢?可以用试算的办法来寻找。试算结果如下:

通过试算我们找到,当d=7时,e×d≡1 mod f(n)同余等式成立。因此,可令d=7。

(5)从而我们可以设计出一对公私密钥,加密密钥(公钥)为:KU =(n,e)=(33,3),解密密钥(私钥)为:KR =(n,d)=(33,7)。

3.2 英文数字化

将明文信息数字化,假定明文英文字母编码表为按字母顺序排列数值,即:

则得到分组后明文”key“信息为:11,05,25。

3.3 明文加密

用户A用公钥KU(33,3) 将数字化明文信息加密成密文。

因此,得到相应的密文信息为:11,26,16。

3.4 密文解密

用户B用私钥KR(33,7)将密文解密成明文。

用户B得到明文信息为:11,05,25。根据上面的编码表将其转换为英文,我们又得到了恢复后的原文“key”。 

RSA的原理就可以这么简单地解释!当然,实际运用要比这复杂得多。p、q、e的选取、公钥私钥的生成,加密解密模指数运算都有一定的计算程序,需要仰仗计算机高速完成。

4 RSA的安全性

为什么RSA密码难于破解?

在RSA密码应用中,公钥KU是被公开的,即e和n的数值可以被第三方窃听者得到。破解RSA密码的问题就是从已知的e和n的数值(n等于pq),想法求出d的数值,这样就可以得到私钥来破解密文。

从上文中的公式:de≡1 mod f(n)≡1 mod ((p-1)(q-1))) ≡ 1 mod (pq-(p+q)+1) ≡ 1 mod (n-(p+q)+1) 可以看出,n,e已知,密码破解的实质问题是:

只要求出p和q的值,我们就能求出d的值而得到私钥。

当p和q是一个大素数的时候,从它们的积pq去分解因子p和q,这是一个公认的数学难题。

比如当pq的乘积n转换为2进制表示,位数达到1024位时,迄今为止还没有人能够利用任何计算工具去完成分解因子的任务(目前被破解的最长RSA密钥是768个二进制位,因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全)。因此,RSA从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。

然而,虽然RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。

此外,RSA的缺点还有:

A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。

B)分组长度太大,为保证安全性,n 至少也要 600 bits 以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。

因此,使用RSA只能加密少量数据,大量的数据加密还要靠对称密码算法。


5 RSA选用小公钥指数(e)

现有的大部分RSA算法实现都遵循PKCS#1 v2.1/v1.5 (2002/1993)。根据PKCS#1的建议,公钥指数e是可以选取较小的素数3或65537(=2^16+1)。这样选取主要是为了提高加密或签名验证的性能,因为3或65537分别只需要2或17次模乘运算,而一个随机选择的e(假设n是1024-bit)则大约需要1000次。这种选用小公钥指数的方法使用户相信RSA在签名验证和加密操作方面确实要比“以高效著称的ECC”还要高效很多。

然而在选用小公钥指数时,有很多人则更倾向于选e=65537而不是e=3,他们认为3“似乎不安全”,然而又给不出所以然。在“正确使用”RSA算法的情况下,至今为止还没有发现公开的攻击方法能有效攻击e=3。

6 加密解密 VS 验证签名

6.1 公钥和私钥的对立性

根据上述RSA算法的描述,可以知道:公钥指数e是可以随机选择的一个质数,且根据 e×d≡1 mod f(n)试算出私钥指数d。

上面实例中,我们选择了e=3,d=7,且 3 x 7 ≡1 mod 20,公钥(33,3),私钥(33,7) ;如果我们选择e=7,d=3,那么7 x 3=1 mod 20仍成立,此时公钥就是(33,7),私钥是(33,3)。

后续的加密解密步骤仍能正确执行。

所以,RSA算法中,公钥和私钥是一个相对的概念。一个作为公钥,另一个就是私钥,具有对立性。分发给公共持有的,便被叫做公钥;私持不公布的,便被叫做私钥。

根据公钥和私钥的对立性,可知:

(1)公钥加密明文后,私钥可以解密出来;

(2)私钥加密明文后,公钥可以解密出来;

6.2 加密解密 VS 验证签名

客户端持有公钥,将消息加密后,公开密文,因为只有服务端有私钥,所以也只有服务端能解密出明文。这个过程叫做加密解密。

服务端持有密钥,讲消息加密后,公开密文和明文,因为客户端都有公钥,都能解密出明文,然后客户端比较“解密得到的明文”和“接收到的明文”是否相等。如果相等,则说明内容未被篡改;如果不相等,则说明内容被篡改。用私钥加密的明文,也叫做签名。这个过程叫做验证签名。


PS:如果文中有瑕疵或者错误,欢迎各位吐槽

© 著作权归作者所有

共有 人打赏支持
上一篇: IDEA
青木河
粉丝 180
博文 30
码字总数 11660
作品 0
海淀
程序员
私信 提问
加载中

评论(3)

青木河
青木河

引用来自“紫电清霜”的评论

居然不上首页,没天理,宝宝我不服~
你都看完了?
紫电清霜
紫电清霜
居然不上首页,没天理,宝宝我不服~
木兰宿莽
木兰宿莽
79
Java使用模数、公钥指数、私钥指数进行RSA加解密

关于模数n、公钥指数e、私钥指数d的相关概念推荐阮老师的这两篇文章。 RSA算法原理(一) RSA算法原理(二) 简单说一下,模数n就是随机选取的两个质数p,q的乘积,并且n的长度就是秘钥的长度...

老佛爷
2018/01/27
0
0
快速理解RSA算法(转载,不错哦)

用实例讲解RSA加密算法 RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, LeonardAdleman的名字首字母命名,这个算法经受...

yufenghang
2013/11/04
0
0
RSA算法理论学习解惑――复制粘贴RSA私钥导致tengine出错深入解析

原创文章:来自RSA算法理论学习解惑――复制粘贴RSA私钥导致tengine出错深入解析 tengine的代码中使用了RSAcheckkey函数进行RSA私钥格式正确性检查,有一次加载私钥测试时tengine reload失败。...

fenghui.zfh
2018/06/10
0
0
[安全] 关于 RSA 算法的原理与实践

当代信息网络发展至今,覆盖面已经非常广泛,广大用户使用这个互联网络来分享信息,搜索资料,进行商业交易等等,可以说是无处不在,也因为这样,这个领域中的信息安全也就变得越来越重要。在...

长平狐
2012/11/19
841
0
RSA算法原理(二)

RSA算法原理(二) 作者: 阮一峰 日期: 2013年7月 4日 上一次,我介绍了一些数论知识。 有了这些知识,我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。 六、密钥生成的步骤 我们...

扁-哥
2013/07/09
78
0

没有更多内容

加载失败,请刷新页面

加载更多

JS数组去重的几种常见方法

一、简单的去重方法 // 最简单数组去重法/** 新建一新数组,遍历传入数组,值不在新数组就push进该新数组中* IE8以下不支持数组的indexOf方法* */function uniq(array){ var ...

Jack088
24分钟前
1
0
kafka 集群监控 (kafka Manager)

一、监控kafka工具有很多,但是对于运维人员来说kafka Manager 就可以了 二、下载kafkaManager 编译安装 地址https://github.com/yahoo/kafka-manager 三、下下来的是源码 需要在开始安装官方...

雁南飞丶
25分钟前
1
0
php开发环境搭建

一、wamp环境搭建 安装apache 安装mysql 解压php 在httpd.conf中配置apache,让apache支持php #加载php作为apache的一个模块 LoadModule php5_module "d:/server/php/php5apache2_4.dll" 5. ......

lujc
27分钟前
0
0
java+testng接口测试

最近写了三个接口,很不想写了,觉得好麻烦呀,用postman比这个简洁多了,为什么要写代码呀,为都要学习代码呀呀,我现在还没觉得手写代码比用工具工作上优势体现在哪里了~~知道的告诉我下...

EvanDev
36分钟前
1
0
反向代理(内网穿透)工具Ngrok安装

ngrok是一个反向代理工具,1.x版本源码开源;可以自己搭建一个服务来使用,将本地的web或tcp服务通过公共端口和外部建立一个安全通道,这样就可以通过外网直接访问本地对应的服务,在进行微信...

zerokb-小浪
43分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部