咨询热线:400-000-3720 中文 | English
RSA数据加密算法之原理篇 发布时间:2015/8/27

本站前面已经对RSA数据加密算法做了简单介绍,想必各位已经对此有了基础的了解。
那么我们下面就进入今天的正题-RSA数据加密算法的原理

首先复习下RSA用到的几个数学概念
1、互质数
质数,就是除了1和它本身外,不能被其他自然数(质数)整除,比如23 它不能被2~22之间任意一个数整除。

互质数,两个数的公因数只有1的两个非零自然数,叫做互质数,比如11和13。

2、模指数运算
模运算属于整数运算,去一个正整数M,以N为模做运算 既:M mod n。此运算是让M除以N,只取余数作为结果。
举例说明:5 mod 2=1 再比如20 mod 3=2等等

模指数运算就是先做指数运算,取其结果在做模运算
举例说明 5^3 mod 7=125 mod 7=6

熟悉了这两个概念之后就好理解RSA加密算法了

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)。这个公式也可以表达为d ≡e-1 mod f(n).
(解释:≡是数论中表示同余的符号,两个整数a、b,若它们除以整数m所得的余数相等,则称a与b对于模m同余或a同余于b模m,记作 a≡b (mod m)
6、公钥KU=(e,n),私钥KR=(d,n)。
7、加密时,先将明文变换成0至n-1的一个整数M。若明文较长,可先分割成适当的组,然后再进行交换。设密文为C,则加密过程为:。C≡M^e(mod n).
8、解密过程为:M≡C^d(mod n)

举例:
为了便于更直观的演示RSA的原理,以下例子选取比较小的质数来做运算。
在以下实例中只选取小数值的素数p,q,以及e,假设用户甲需要将明文“key”通过RSA加密后传递给用户乙,过程如下:
1、设定公私密钥(e,n)和(d,n)。
令p=3,q=11,得出n=p×q=3×11=33;f(n)=(p-1)(q-1)=2×10=20;取e=3,(3与20互质)则e×d≡1 mod f(n),即3×d≡1 mod 20。
d怎样取值呢?可以用试算的办法来寻找。试算结果如下:

 d  e*d  e*d mod(p-1)(q-1)
 1  3  3
 2  6  6
 3  9  9
 4  12  12
 5  15  15
 6  18  18
 7  21  1
 8  24  3

通过试算我们找到,当d=7时,e×d≡1 mod f(n)同余等式成立。因此,可令d=7。从而我们可以设计出一对公私密钥,加密密钥(公钥)为:KU =(e,n)=(3,33),解密密钥(私钥)为:KR =(d,n)=(7,33)。
2、英文数字化。
  将明文信息数字化,并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值,即:

 字母  a  b  c  d  e  g  h  i  j  k  l  m
 码值  01  02  03  04  05  06  07  08 09  10  11  12  13 
 字母 n p q  y
 码值  14 15  16  17  18  19  20  21  22  23  24  25  26 

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


3、明文加密


用户甲加密密钥(3,33) 将数字化明文分组信息加密成密文。由C≡Me(mod n)得:

M1≡(C1)^d (mod n)=11^7(mod 33)=11

M2≡(C2)^d (mod n)=31^7(mod 33)=05

M3≡(C3)^d (mod n)=16^7(mod 33)=25

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


4、密文解密

用户乙收到密文,若将其解密,只需要计算,即:

M1≡(C1)^d (mod n)=11^7(mod 33)=11

M2≡(C2)^d (mod n)=31^7(mod 33)=05

M3≡(C3)^d (mod n)=16^7(mod 33)=25

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

以上就是RSA数据加密的简例算法过程,只要有基础的高数知识,基本都能看懂。
当然了 ,实际在方案上的应用要比以上例子复杂太多!原因是 RSA数据加密算法的模长度要到1024位才能保证安全,这些高密度运算全由计算机来高效的完成。

 

推荐阅读:

凤凰卫士RSA数据加密算法简介

通过上述有关企业信息安全和数据安全等加密相同资讯的介绍,大家对于这此有一定的了解和认识,安腾加密软件希望您在日后的工作中,如有文件加密软件、文档加密软件、图纸加密软件、文件加密、数据加密、文档安全分发、数据安全、文件防泄密、信息反泄密、数据安全等需求,欢迎随时访问安腾加密软件的官网:http://www.iten.com.cn 或拨打热线:400-000-3720 联系我们。