当前位置:网站首页> 科技>正文

rsa加密算法属于

发布于:2020-05-11 18:12:44发布者:天晴网友

RSA加密算法是最常用的非对称加密算法,CFCA在证书服务中离不了它。但是有不少新来的同事对它不太了解,恰好看到一本书中作者用实例对它进行了简化而生动的描述,使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。

RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。

RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。

RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表:

可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解RSA加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到:

一、 什么是“素数”?

素数是这样的整数,它除了能表示为它自己和1的乘积以外,不能表示为任何其它两个整数的乘积。例如,15=3*5,所以15不是素数;又如,12=6*2=4*3,所以12也不是素数。另一方面,13除了等于13*1以外,不能表示为其它任何两个整数的乘积,所以13是一个素数。素数也称为“质数”。

二、什么是“互质数”(或“互素数”)?

小学数学教材对互质数是这样定义的:“公约数只有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。

(8)两个数都是合数(二数差又较大),小数所有的质因数,都不是大数的约数,这两个数是互质数。如357与715,357=3×7×17,而3、7和17都不是715的约数,这两个数为互质数。等等。

三、什么是模指数运算?

指数运算谁都懂,不必说了,先说说模运算。模运算是整数运算,有一个整数m,以n为模做模运算,即m mod n。怎样做呢?让m去被n整除,只取所得的余数作为结果,就叫做模运算。例如,10 mod 3=1;26 mod 6=2;28 mod 2 =0等等。

模指数运算就是先做指数运算,取其结果再做模运算。如

好,现在开始正式讲解RSA加密算法。

算法描述:

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

(2)计算n=pq。

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

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

(5)计算d,使得de≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n)

这里要解释一下,≡是数论中表示同余的符号。公式中,≡符号的左边必须和符号右边同余,也就是两边模运算结果相同。显而易见,不管f(n)取什么值,符号右边1 mod f(n)的结果都等于1;符号的左边d与e的乘积做模运算后的结果也必须等于1。这就需要计算出d的值,让这个同余等式能够成立。

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

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

(8)解密过程为:

实例描述:

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

(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=7时,e×d≡1 mod f(n)同余等式成立。因此,可令d=7。从而我们可以设计出一对公私密钥,加密密钥(公钥)为:KU =(e,n)=(3,33),解密密钥(私钥)为:KR =(d,n)=(7,33)。

(2)英文数字化。

将明文信息数字化,并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值,即:

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

(3)明文加密

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

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

(4)密文解密。

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

,即:

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

你看,它的原理就可以这么简单地解释!

当然,实际运用要比这复杂得多,由于RSA算法的公钥私钥的长度(模长度)要到1024位甚至2048位才能保证安全,因此,p、q、e的选取、公钥私钥的生成,加密解密模指数运算都有一定的计算程序,需要仰仗计算机高速完成。

点击展开全文
相关数码科技+更多
  • 电脑文件夹怎么加密

    重要文件存放在电脑上不想让别人看到,这个时候就需要设置密码了,那如何给文件夹设置密码呢?下面小编就来介绍一下给文件设置密码的方法! 01 找到需要加密的文件夹 右击选择属性

  • zip解压密码

    当以前加密过的RAR/ZIP压缩文件密码怎么也想不起来了,而加密的RAR/ZIP压缩文件里面的资料又非常重要怎么办呢,我们可以使用Advanced Archive Password Recovery密码恢复软件对RAR压缩文件加密

  • 苹果7怎么给软件加密码

    苹果7怎么给软件加密码? 手机上打开设置,点击通用,找到并点击访问限制,点击启用访问限制,输入密码,选择要加密的软件,打开软件右侧的按钮即可。

  • 苹果照片怎么加密

    苹果照片怎么加密?下面我们来看看吧。 苹果手机本身不具备相册加密功能,需借助第三方应用程序进行相册加密 打开应用程序App Store,在App Store的顶部搜索栏中输入腾讯手机管家进行

  • 给U盘加密的方法

    很多人都喜欢用U盘存储重要的文件,所以U盘的安全性越来越受到我们的重视。那么我们如何给U盘加密呢,现在小编就来告诉大家给U盘加密的方法。 U盘加密可分为两种类型 1:硬件、

  • 苹果手机隐藏照片怎么加密

    苹果手机隐藏照片怎么加密 ?一起来了解一下。 苹果手机隐藏的照片是无法加密的,只能选择隐藏或加密。 01 打开手机照片,进入页面,找到要隐藏的照片进入 02 点击左下角的分享图

文章评论