RSA原理与实例
RSA原理与实例
青木河 发表于2年前
RSA原理与实例
  • 发表于 2年前
  • 阅读 457
  • 收藏 12
  • 点赞 4
  • 评论 3

移动开发云端新模式探索实践 >>>   

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:如果文中有瑕疵或者错误,欢迎各位吐槽

标签: rsa
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 178
博文 16
码字总数 11393
评论 (3)
木兰宿莽
79
紫电清霜
居然不上首页,没天理,宝宝我不服~
青木河

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

居然不上首页,没天理,宝宝我不服~
你都看完了?
×
青木河
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: