您正在使用较旧版本的浏览器。为了获得最佳 MSN 中文网体验,请使用受支持的版本

算法浅谈 | 没有它,信息安全将是一片荒芜……

Microsoft 徽标 Microsoft 2022/6/9 微软(亚洲)互联网工程院 · AI智汇学院

编者按:

计算机领域常用的RSA加密算法具有非常高的稳定性,发明至今,世界上仍然没有可靠的攻击它的方法。有人说,RSA加密算法是地球上最重要的算法,如果没有 RSA加密算法,现在的网络世界将毫无安全可言,更不可能有现在的网上交易。

© Getty

今天,微软智汇学院就将给大家讲讲RSA加密算法。其理论基础是一系列严格的数学推导过程,但原理并不难懂,甚至主要和我们小学就学过的质数、约数和质因数分解有关。

(更多来自微软智汇学院的精彩内容,请戳这里~)


RSA加密算法

RSA加密算法非常有名,在计算机领域的应用非常广泛,几乎是一般用户在信息加密时的首选。

它是一种非对称加密演算法,名字来源于它的三个发明人——罗纳德·李维斯特(RonRivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)——名字的首字母缩写。

这三人在1977年一起提出了RSA算法,当时他们都在麻省理工学院工作。

虽然已经被发明了四十多年,但是至今世界上仍然没有可靠的攻击它的方法。在技术瞬息万变的今天,这样的稳定性尤其难能可贵。

RSA为什么这么保险呢?当然和它的实现原理有关系,我们要了解RSA,就需要掌握它的理论基础。

作为加密算法,RSA的原理实际上就是一系列非常严格的数学推导过程。一说到数学可能有人又要头疼了,数学啊,很难吧?

其实,并不难。

RSA算法背后的数学概念

最近笔者给一位小学生检查数学作业,由此得知他们已经在学习下面这些概念:

余数:如果有两个整数a和b,a除以b不能除尽,那么a中不能除尽的部分就是。比如11除以5,商是2,余数是1。

MOD函数:求余数的函数,mod(11,5)就是对11除以5求余数。

约数:又称因数,如果有两个整数a和b,a除以b能除尽,那么b就是a的约数,比如,2÷1=2,2÷2=1,2的约数就是1和2。

因数分解:把一个正整数写成几个约数的乘积。

公约数:有几个整数,它们都有一个相同的约数,那么这个约数就是这几个整数的公约数,比如2的约数是1和2,4的约数是1、2和4,6的约数是1、2、3、6,2、4和6的公约数就是1和2。

质数:一个大于1的自然数,除了1和它本身,再没有别的约数了,那么这个数就是质数。比如2,它大于1,只有1和2两个约数,它就是质数。

互质:两个整数,只有1一个公约数,这两个整数就是互质整数。比如2和3,它们的公约数只有1,它们就是互质的。

有了这些概念做基础,其实就已经可以看懂RSA算法的推导过程了。现在我们一起来看一看吧——

RSA算法原理

RSA算法包括四个阶段:密钥生成,密钥发布,加密和解密。前两个阶段属于加密算法准备,后两个阶段则属于加密算法使用。

下面我们分别来看这四个阶段:

  1)密钥生成

这里说的密钥又分为公钥和私钥两个部分,各对应两个数字,公钥为 n 和 e,私钥为 n 和 d。

因为公钥和私钥的 n 是同一个 n,因此,其实RSA的密钥总共涉及三个数字:n,e 和 d,它们都是非常非常大的正整数。

它们是通过以下步骤生成的:

  • Step1.1:选择两个质数 p 和 q.
  • Step1.2:计算出 p 和 q 的积 n:n = p·q。
  • Step1.3:计算n的卡迈克尔函数λ(n)。

卡迈克尔函数,n 的卡迈克尔函数计作 λ(n),定义为:对任意正整数 n,它的卡迈克尔函数λ(n) 是满足如下条件的最小的正整数:这个正整数 m 使得 am ≡ 1 (mod n),其中 a 是 1 到 m 之间任意一个与 m 互质的整数。

这里的 ≡ 是同余符号——同余是数论中的一种等价关系,当两个整数除以同一个正整数,若得相同余数,则二整数同余。

所以式子 am ≡ 1 (mod n) 表示:a的m次幂除以n之后的余数为1,又可以称作:am 和1对于模n同余。

在这里还需要了解另一个函数:

欧拉函数,n的欧拉函数计作φ(n),定义为:对任意正整数n,它的欧拉函数就是在小于或等于n的正整数里与n互质的数字的个数。

φ(n) 分不同情况来看:

a) 如果n=1,那么φ(1)=1

b) 如果n是质数,那么φ(n)=n-1

c)如果n是一个质数p的k次方,即n=pk,那么φ(n)=φ(pk)= pk- pk-1

d)如果n是两个互质的数p和q的乘积,那么φ(n)=φ(p) ⋅φ(q)

当 n 为1、2、4、奇质数的次幂、奇质数的次幂的两倍时,λ(n) 为 φ(n),当 n 为2、4以外的2的次幂时,λ(n) 为 φ(n) 的一半:

因为:

(i) 欧拉函数的情况 c);

(ii)正整数 n 可写作它的质因数的积。

因此对于任意正整数n,它的卡迈克尔函数 λ(n )是 n 的质因数的卡迈克尔函数的最小公倍数,记作:

 

其中:p1 < p2 <... < pk 是质数,而 r1, r2,..., rk 是正整数。

还有,因为 n 为两个质数 p 和 q 的积,所以 n 的卡迈克尔函数等于 p 和 q 的卡迈克尔函数的最小公倍数,计作 λ(n) = lcm(λ(p), λ(q)) 。

又因为根据 欧拉函数的情况 c)可得:λ(p) = φ(p) = p – 1且 λ(q) = φ(q) = q − 1。因此,λ(n) = lcm(p − 1, q − 1)。

也就是说,这一步要计算 p-1 和 q-1 的最小公倍数。

  • Step1.4:选择一个正整数e,满足:1 < e < λ(n) ,并且 e 和 λ(n) 互质。
  • Step1.5:确定 e 的模反元素 d。

模反元素:如果有两个互质的正整数a和n,那一定可以找到一个整数b,能让 ab - 1 能被 n 整除,也就是说ab除以n的余数是1,记作 ab ≡ 1(mod n)。数学家们已经利用欧拉定理也能证明模反元素的存在。

也就是说 d 满足:d ≡ e−1 (mod λ(n)) ,即 ed ≡ 1 (mod λ(n))。

至此,第一阶段完成。在这一阶段,Step1.2 生成的 n 和 Step1.4 生成的 e 组成了公钥:(n,e);而 Step1.2 生成的 n 和 Step1.5 生成的 d 组成了私钥:(n,d)。

  2)密钥发布

密钥生成之后,公钥被公之于众,任何人都可以获取并使用,而私钥则被保留在特定的,被允许解读加密信息的人手中。

  3)加密

加密只需要用到公钥(n,e),当人们想要用RSA算法加密一段信息时,需要按以下步骤进行:

  • Step 3.1:将信息按照约定的方法转化为一个正整数m,满足 0 ≤ m < n 。

此处的将信息转化为数字的方法也是公开的,如果信息实在太多也可以考虑分段,每段分别转化为一个大于等于0,小于n的正整数。

  • Step 3.2:计算c = mod(me, n),c就是加密后的密文。 加密完成,将生成的密文传递给要送达的人。

  4) 解密

收到密文的人,如果手中有私钥(n,d),就可以开始解密了,方法如下:

  • Step 4.1:计算 m = mod(cd, n),m就是原本的原文。

RSA加密全过程实例

下面我们来看一个例子:

  1) 密钥生成

  • 1.1:我们选择 p = 61 和 q = 53.
  • 1.2:计算n = 61 × 53 =3233.
  • 1.3:计算λ(n) = λ(3233) = Icm(60, 52) = 780.
  • 1.4: 选择 e,需满足 1 < e <780,且 e 和780互质。

我们选择 e = 17.

  • 1.5:求e的模反元素d,使得 ed ≡ 1 mod λ(n),也就是17d ≡ 1 mod 780.

求 17d = 780 h + 1 ,其中h为正整数。

求得d = 413,验算:413 ×17 = 780 × 9 + 1,d成立。

我们生成了公钥 (n = 3233, e =17),和私钥 (n = 3233, d =413).

  2)密钥发布

公布公钥,将密钥交给我们要通信的朋友。

  3)加密

原文为m(正整数),计算:c = mod(me, n).

假设m = 65, 则c = mod(6517, 3233) = 2790.

原文 65,通过公钥加密得到密文 2790。将其交给有私钥的人。

  4) 解密

计算m = mod (cd, n) 得到原文。

密文为2790,则m = mod(2790413, 3233) = 65

密文为2790,通过私钥解密得到原文65。

以上就是RSA的整个运作过程。

RSA算法原理推导

为什么这个加密解密过程能够有效?为什么当 c = mod (me,n) 时,就一定有m = mod(cd, n)呢?

首先, 根据 Step 3.2 可知:me ≡ c (mod n),根据同余关系保持基本运算的性质,有 cd ≡ (me)d = med (mod n),也就是 cd ≡ med (mod n)

其次,因为 ed ≡ 1 (mod λ(n)),即 ed - 1 ≡ 0 (mod λ(n)),也就是说ed - 1 可以被λ(n) 整除。

又因为 λ(n) = lcm(p − 1, q − 1) ,也就是 λ(n) 可以被 p -1 和 q-1 整除,因此有 ed - 1 = h(p -1) = k(q-1), h和k都是非负整数。

于是有:med = m⋅m (ed-1)= m (m (p-1) ) h

根据Step1.3 中 φ(p) = p – 1,med = m (m (p-1) ) h = m (mφ (p) ) h

因为 p 是质数,所以如果 m 要么是 p 的倍数,要么与 p 互质——

i)若 m 是 p 的倍数,则 med 也是 p 的倍数, med ≡ 0 ≡ m (mod p) ;

ii)若 m 与 p 互质,根据欧拉定理则有 mφ(p) ≡ 1 (mod p)

欧拉定理:两个互质的正整数 a 和 b, aφ(b) ≡1 (mod b)。

于是,有 med = m · mφ (p) ≡ m (mod p),即 med ≡ m (mod p)

综合i)和ii)有:med ≡ m (mod p) .

同理,可证明 med ≡ m (mod q).

根据中国剩余定理,med ≡ m (mod p) 和 med ≡ m (mod q) 同时成立,等同于 med ≡ m (mod pq) 成立,又因为 pq = n,因此,我们得以证明:med ≡ m (mod n)

然后,根据同余的传递性,有 cd ≡ med ≡ m (mod n)。且已知 m < n,所以mod(cd , n)= m,这也就是为什么 Step 4.1 能够求出m的原因。

为什么RSA难于破解?

这件事我们不妨反过来想,如果我们要破解RSA加密文件,我们需要什么?

我们需要私钥,私钥包括两个部分:n 和 d,n 就是公钥中的 n,所以我们唯一需要知道的就是 d。

那么我们能不能自己把 d 求出来呢?理论上是可行的。

因为 ed ≡ 1 mod λ(n),e 是已知的,且 λ(n) = lcm(p − 1, q − 1),因此,我们只需要知道 p - 1 和 q - 1 就好了。

n = p·q,那么我们只要对 n 进行质因数分解,找到它的最大质因数就可以了。

可是,实际操作起来,却不那么容易。

如果 p 和 q 很大,n 就会更大。而大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。

只有短的 RSA 钥匙才可能被暴力方式破解。迄今为止,世界上还没有任何可靠的攻击RSA算法的方式。

只要其钥匙的长度足够长,用 RSA 加密的信息,就可以认为在事实上是不能被破解的。

没想到吧,小学数学课上就学过的质数、余数、质因数分解竟然这么有用,居然就在生活中时时处处保护着我们的信息安全。

--END--

了解更多来自微软智汇学院的精彩内容,欢迎点击👇:

AI 入行那些事 | 两分钟了解人工智能的 “三生三世”

科普 | 一文读懂大大大大大数据

AI前沿 | 计算机如何正确识别人脸?




image beaconimage beaconimage beacon