文档章节

RSA原理与实例

青木河
 青木河
发布于 2016/03/02 16:14
字数 2453
阅读 519
收藏 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:如果文中有瑕疵或者错误,欢迎各位吐槽

© 著作权归作者所有

共有 人打赏支持
青木河
粉丝 179
博文 27
码字总数 11567
作品 0
海淀
程序员
加载中

评论(3)

青木河
青木河

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

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

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

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

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

yufenghang
2013/11/04
0
0
[安全] 关于 RSA 算法的原理与实践

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

长平狐
2012/11/19
750
0
RSA算法理论学习解惑――复制粘贴RSA私钥导致tengine出错深入解析

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

fenghui.zfh
06/10
0
0
RSA公钥文件解密密文的原理分析

前言   最近在学习RSA加解密过程中遇到一个这样的难题:假设已知publickey公钥文件和加密后的密文flag,如何对其密文进行解密,转换成明文~~ 分析   对于rsa算法的公钥与私钥的产生,我们...

Angel_Kitty
08/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

基于TP5的微信的公众号获取登录用户信息

之前讲过微信的公众号自动登录的菜单配置,这次记录一下在TP5项目中获取自动登录的用户信息并存到数据库的操作 基本的流程为:微信设置自动登录的菜单—>访问的URL指定的函数里获取用户信息—...

月夜中徘徊
今天
0
0
youTrack

package jetbrains.teamsys.license.runtime; 计算lis package jetbrains.ring.license.reader; 验证lis 安装后先不要生成lis,要把相关文件进行替换 ring-license-checker-1.0.41.jar char......

max佩恩
今天
0
0
12.17 Nginx负载均衡

Nginx负载均衡 下面的dig看到可以返回2个IP,就是解析出来的IP,这样我们可以做负载均衡。 dig www.qq.com 1.vim /usr/local/nginx/conf/vhost/fuzai.conf 2.添加如下配置 upstream qq //定义...

芬野de博客
今天
0
0
SSE(Server Send Event 服务端发送事件)

package com.example.demo.controller;import org.springframework.stereotype.Controller;import org.springframework.web.bind.annotation.RequestMapping;import org.springframe......

Canaan_
今天
0
0
jvm调优

1.jvm运行模式 client模式:启动快,占用内存少,jit编译器生成代码的速度也更快. server模式:主要优势在于代码优化功能,这个功能对于服务器应用而言尤其重要. tiered server模式:结合了client与...

Funcy1122
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部