文档章节

RSA原理与实例

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

© 著作权归作者所有

共有 人打赏支持
青木河
粉丝 180
博文 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加解密及签名算法的技术原理及其Go语言实现

  对称加密中,加密和解密使用相同的密钥,因此必须向解密者配送密钥,即密钥配送问题。而非对称加密中,由于加密和解密分别使用公钥和私钥,而公钥是公开的,因此可以规避密钥配送问题。非...

莫名2013
01/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

精通Spring Boot——第十二篇:分页查询功能的实现

本文将介绍如何实现分页查询功能,推荐使用github的pagehelper插件实现(事实上大家基本都是这么干的),但本文的实现方式和大多数不同,废话少说,现在就带着大家看看区别在哪里。 先看pom...

developlee的潇洒人生
30分钟前
3
0
平淡的秋招之路

1. 概述 在八月中旬之前,我还没有秋招这个概念,认为找工作就是通过学校举办的招聘会。后来慢慢的了解到,由于学校实力的问题,许多好的公司只会去门当户对的学校进行招聘。我们学校只是一个...

firepation
33分钟前
1
0
设置布局中的子控件不可用

RelativeLayout R2 = findViewById(R.id.act_menu_level2_rl); //设置当前R2中的子控件不可用 int childCount = R2.getChildCount(); ......

lanyu96
44分钟前
2
0
分布式系统中处理参数配置的 4 种方案

一个系统中包含有各种各样的配置信息,如一个日志文件需要配置以下几个信息。 日志文件生成主目录 日志文件名称,不同的日志级别对应不同的文件 当前日志级别 还有其他各种业务参数、系统参数...

Java技术栈
45分钟前
3
0
MongoDB的使用学习之(七)MongoDB的聚合查询(两种方式)附项目源码

MongoDB的使用学习之(七)MongoDB的聚合查询(两种方式)附项目源码 先来张在路上…… 铛铛铛……项目源码下载地址:http://files.cnblogs.com/ontheroad_lee/MongoDBDemo.rar 此项目是用M...

Airship
51分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部