详解RSA算法基本原理

最后编辑于 2019年11月22日 开发

刘超同学最近肯定是工作不饱和,因为他竟然有时间写这么一篇关于RSA的文章。但也有可能是发了财了,心血来潮所致。不过写的还是不错的。

想要刘超请客的同学们请关注他的微信公众号: 代码时光机

前言

作为一个码农,为了保证网络传输的安全,经常会在代码中使用RSA算法(或其他单向陷门函数进行加密)。为了更深刻的理解RSA到底是什么,它又是如何保证信息安全的,所以最近特意研究了一下,把心得和体会分享给大家。也许有不对的地方,欢迎指正,也希望对未知世界充满好奇的你,在探索中成长。

历史

引用阮一峰的描述:
1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。

预备知识

首先,要对几个基础的概念或定理有所了解,否则很难了解RSA算法的本质。接下来简单说明一下,大概分为以下几个知识点:

质数
费马小定理
欧拉φ函数(以及欧拉φ函数的两个重要特性)
费马-欧拉定理

下面分别简单介绍一下:

质数(素数):

质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

简单来说,就是不能再进行分解的数,就叫质数。比如11,13,17,除了1和它本身,不再包含任何自然数因数。

费马小定理

如果p是一个质数,而整数a不是p的倍数,则有a^(p-1)≡1(mod p)。
证明过程感兴趣的可以看杨辉三角形
简单来说一下费马小定理的同余式是如何来的:
正常情况下费马小定理是:

a^p-a=p的倍数

我们把变量A提出来,写成如下形式:

a(a^(p-1)-1)=p的倍数

这个时候关键的来了,如果我们假设,a不是p的倍数,所以a对p的倍数是没有影响的,则可以省略,变成:

a^(p-1)-1=p的倍数

当两边同时除以P,则变为:

a^(p-1)/p-1/p=整数

这个式子代表什么?代表A^(P-1)和1对P是同余的,所以可以改写成同余式,即:

a^(p-1)≡1(mod p)

所以当a不是p的倍数式,我们把费马小定理写成:

a^(p-1)≡1(mod p)

欧拉φ函数

在数论,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目

看起来比较绕,其实很简单。就是对于给定的正整数N,从1到N有多少个数是与之互质的。(互质可以简单理解为两个整数的最大公约数为1,即为互质)

举个例子:

φ(5)=4 (1,2,3,4这4个数与5互质)
φ(8)=4 (1,3,5,7这4个数与8互质)

欧拉函数有两个特性,需要理解:

1.欧拉函数是积性函数

简单的可以理解为:φ(mn)=φ(m) * φ(n) ,但是有个大前提,就是m与n必须互素。

举个例子:φ(12)=4(1,5,7,11与之互素) φ(3)φ(4)=22=4 满足φ(mn)=φ(m) * φ(n)

2.当n为素数,则φ(n)=n-1

这个很好理解了,因为素数除了1和它本身,就没有任何因子了。比如φ(11)=10

费马-欧拉定理

由于费马小定理给出的P一定是素数,不够范式化,所以欧拉在此基础上进行了升级,使其具有通用性。

在数论中,欧拉定理,(也称费马-欧拉定理)是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互质,则:

a^(φ(n))≡1(mod n)

其实从这里可以看出,当n为素数时,根据欧拉φ函数,可以改写成a^(p-1)≡1(mod p),即我们上面刚刚说过的费马小定理。可见欧拉让费马小定理更通用。

RSA加解密过程

先讲解RSA中公钥和私钥的生成:

  1. 首先定义两个质数p,q。

  2. 定义n=pq,定义r=φ(n),根据欧拉φ函数的特性,φ(n)=φ(q)φ(p)=(p-1)*(q-1)

  3. 定义e,e<r,且e和r互质

  4. 公钥为(N,e)

  5. 定义d,使其满足ed-1=r的倍数,也可以理解为ed/r的余数要等于1,也可以称之为模逆元。

  6. 私钥为(N,d)

作为码农,可能看代码更好理解:


Image credit: 刘超

有了公钥和私钥,就可以开始加解密了。我们先抛出结论,再来证明

加密函数:m为传输的内容,c为加密结果(n和e是公钥)

m^e - c = n的倍数(也可以写成同余式 m^e ≡ c (mod n))

解密函数:c为加密后的内容,s为解密后的结果(n和d是私钥)

c^d - s = n的倍数 (也可以写成同余式 c^d ≡ s (mod n))

继续上代码,来完成加解密:(前提m必须小于<n,如果比n大,要拆分分段来传输)


Image credit: 刘超

程序输出的结果:

公钥为(6557,641) 私钥为(6557,2285)
密文:39
解密:666

RSA加解密原理

我们来验证一下,加密公式是如何推导出解密公式的。也就是尝试把

加密公式(m^e - c = n的倍数) 推导出 解密公式 (c^d - s = n的倍数),且保证原文m等于解密后的原文s

我们先把加密公式改写一下:

c=m^e + n的倍数 (由于N的倍数可以是正负数,所以加减号对结果是没有影响的)

我们两边同时d次方,则变成:

c^d=m^(ed)+n的倍数

ed是什么?见我们上面的定义d(第五条),ed=r的倍数+1,所以等式可以改写:
(这个式子是有所简化的,因为等号右边的d次其他的项都和n的倍数合并了,因为他们都是n的倍数,所以就没有再写。)

c^d=m^(1+r的倍数)+n的倍数

把m的1+r的倍数再改写一下:

c^d=m(m^(r的倍数))+n的倍数

根据r的定义,可以改写成φ(n)的倍数:

c^d=m(m^(φ(n)的倍数))+n的倍数

重点来了,根据费马-欧拉定理,m^φ(n)的倍数 = n的倍数+1,再改写下原来的等式:

c^d=m(n的倍数+1)+n的倍数

再把m乘进去,合并同类项后,如图:

c^d=m+n的倍数

这个时候再看看解密公式(c^d - s = n的倍数),证毕!

感悟

RSA算法主要是根据两个大素数相乘来完成秘钥生成的。所以挑选的两个素数一定要够大才足够安全。RSA算法自身的风险性在于以后会不会研究出一个算法,可以快速对于一个大数进行分解。

还有对于RSA Padding Attack并不是很了解,还是要学习。

欢迎大家关注点赞,持续学习,一起成长。

致谢:

了解RSA算法主要是通过以下的文章/视频,讲的非常详细也很有趣,强烈建议大家阅读和观看

妈咪说-RSA算法详解:
https://www.bilibili.com/video/av35557954

阮一峰-RSA算法详解:
https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

登录注册后才能评论。