阅读 454

密码学之RSA加密算法

前言

以下是iOS签名原理系列的文章链接

  1. 密码学之RSA加密算法
  2. Hash与对称加密算法
  3. 理解iOS签名原理

本篇是这个系列的第1篇,下面进入正题

1. 密码学

1.1 什么是密码学?

密码学是研究编制密码和破译密码的技术科学。在现代特别指对信息以及其传输的数学性研究,常被认为是数学和计算机科学的分支,和信息论也密切相关。

在这里简述一下密码学的发展历史。

1.2 密码学的发展历史

  1. 在1976年以前,所有的加密方法都是同一种模式:加密、解密使用同一种规则(密钥)。在交互数据的时候,彼此通信的双方就必须将规则告诉对方,否则没法解密。这种加密方式被称为 对称加密算法(symmetric encryption algorithm)

  2. 1976年,两位美国计算机学家 迪菲(Whitfield Diffie)赫尔曼(Martin Hellman) 提出了一种建立密钥的方法,其产生的密钥可用于加密、密钥管理或任何其它的加密方式。这被称为“迪菲赫尔曼密钥交换”算法,简称 D-H算法。D-H算法启发了其他科学家。人们意识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。

  3. 1977年三位麻省理工学院的数学家 罗纳德·李维斯特(Ron Rivest)阿迪·萨莫尔(Adi Shamir)伦纳德·阿德曼(Leonard Adleman) 一起设计了一种算法,可以实现非对称加密。(所谓非对称,就是指该算法需要一对密钥,即公钥(public key)私钥(private key),且两密钥不同,使用其中一个加密,则需要用另一个才能解密)。这个算法用他们三个人的名字命名,叫做 RSA算法

RSA算法的影响是巨大的,毫不夸张地说,只要有计算机网络的地方,就有RSA算法。这种算法非常可靠,密钥越长,它就越难破解。

接下来,我们需要学习几个数学概念,这有助于我们理解RSA加密算法。

2. 几个数学概念

2.1 取模运算(mod)

即求余运算,是在整数运算中求一个整数A除以另一个整数B的余数的运算,且不考虑运算的商。在计算机程序设计中也有mod运算,其格式为: mod(A, B),即是两个数值作除法运算后的余数。

注意:

  1. 当A、B为同号时,即同为正整数或负整数时,mod运算与我们熟悉的%运算相同,可当作是%运算;
    如,3 mode 17 = 3 % 17 = 3;-5 mod -3 = -5 % -3 = -2
  2. A、B异号时,mod运算与%运算不同,在这里不作详细赘述,感兴趣的同学可自行查阅相关资料。

2.2 互质关系

如果两个正整数,除了1之外,没有其它公因数,我们就称这两个数存在互质关系,即这两个数互质。
关于互质关系,不难得到以下几个结论:

  1. 任意两个 不同的质数 互质。比如11和23互质,11和11不互质。
  2. 一个是质数,另一个只要不是前者的倍数,两者就构成互质关系。比如5和12互质。
  3. 一个质数与任意一个比它小的数互质。比如11和8。
  4. 1和任意一个大于1的自然数互质。比如1和99。
  5. p是大于1的整数,则p和p-1互质。比如10和9。

注意: 两个正整数互质,意思是这两个整数存在互质关系,即没有1之外的其它公因数,并不意味着这两个数是质数。比如9和10互质,但是9和10均为合数。

2.3 欧拉函数

对于一个正整数n,小于n且和n互质的正整数的个数,计算这个值的方法叫做欧拉函数,记做:φ(n)。欧拉函数通式为

\phi(n)=n({1}-{1\over{p_1}})({1}-{1\over{p_2}})...({1}-{1\over{p_k}})

其中,p1、p2、...、pk为n的质因数。
如12=2*2*3,2和3为12的质因数,则φ(12)=12*(1-1/2)(1-1/3)=4。 关于欧拉函数,同样有几个推论:

  1. 特别声明,如果n=1,则φ(1)=1,因为1与任何数(包括它本身)形成互质关系。
  2. 当n是质数的时候,φ(n)=n-1。如φ(7)=6,即1、2、3、4、5、6均与7互质。
  3. 如果n可以分解成两个互质的整数之积,如n=a*b,则φ(n)=φ(a)*φ(b)。 如φ(56)=φ(7)*φ(8)=24; 注意,φ(49)≠φ(7)*φ(7) => φ(49)≠36,因为7与7不互质。事实上,φ(49)=42。
  4. 由2和3可以得到,如果n=a*b,且a、b均为质数,则φ(n)=(a-1)*(b-1)。如φ(35)=φ(5)*φ(7)=24;
  5. 如果n=pk(其中p为质数,k为大于1的整数),则φ(n)=φ(pk)=pk-pk-1=(p-1)pk-1。如φ(49)=φ(72)=(7-1)*71=42。

2.4 欧拉定理

欧拉定理指的是,如果两个互质的正整数m和n,那么m的φ(n)次方减去1,可以被n整除。即,

\mathbf{m}^{\phi(n)}\mod\mathbf{n}\equiv1

如7和3互质,7φ(3) mod 3 = 72 mod 3 = 1

  1. 费马小定理:当n为质数的时候,则有 mn-1 mod n ≡ 1
  2. 欧拉定理是RSA算法的核心,理解了这个定理,就理解了RSA算法。

n1.3-2

2.5 模反元素

如果两个正整数m和n互质,那么一定可以找到整数d,使得md-1能被n整除,那么d就是m相对于n的模反元素。即

\mathbf{m}\mathbf{d}\mod\mathbf{n}\equiv1

由上式,可得 d=(kn+1)/m

欧拉定理可以证明上式。由于m和n互质,那么m和n必满足欧拉定理,即 mφ(n) mod n ≡ 1, 令d=mφ(n)-1,即得证!

如,3和5互质,当,k为大于等于1的整数,不难求出当k=4时,得到d=3,即3(d)就是11(e)相对于8(x)的一个模反元素。

3. RSA加密算法

介绍完以上几个数学概念,我们详细介绍一下RSA加密算法。

3.1 RSA加密算法原理

RSA使用不同的加密密钥与解密密钥,是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。其原理是基于大数难以分解,即两个大素数相乘容易,但逆向得到一个由两个大质数相乘得到的更大数的因子则很困难。除了暴力破解,目前还没有其它有效的方法。换而言之,RSA加密算法的可靠性,取决于对极大整数做因式分解的难度。假如有人找到一种快速因数分解的算法(或者量子计算机技术快速发展?),那么RSA的可靠性就会极度下降。但就目前而言,1024位RSA基本安全,2048位是极其安全的。

举例来说,你可以对33进行因式分解(3*11),但是你没法对下面这个整数进行因式分解

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413
复制代码

它等于这样两个质数的乘积:

33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917
复制代码

3.2 密钥生成的步骤

我们通过一个例子,来理解RSA加密算法。假如甲和乙两人进行通信。其流程如下:

  1. 甲选择两个不相等的质数p和q,甲选择了3和11,即p=3,q=11。
    注意:实际应用中,这两个质数越大,就越难破解。
  2. 甲计算得到p和q的乘积n,即n=33
    n的长度就是密钥长度,33写成二进制是100001,一共有6位,所以这个密钥是6位。
  3. 甲计算n的欧拉函数φ(n),得到φ(n) = (p-1)(q-1) = 20
  4. 随机选一个整数e,满足1 < e < φ(n),且e与φ(n)互质。甲选择了13。
  5. 再计算e相对于φ(n)的模反元素d。将e、φ(n)代入公式ed=kφ(n)+1,得到13d=20k+1,此二元一次方程可以用 “扩展欧几里得算法” 求解,此处省略过程。总之,甲算出一组整数解为(d,k)=(17,11),即d=17
  6. n和e封装成公钥,n和d封装成私钥。即公钥是(33,13),私钥是(33,17) 注意:实际应用中,公钥和私钥的数据都采用 ASN.1 格式表达。

3.3 RSA加密算法的可靠性分析

上述步骤共出现6个数字:p:3、q:11、n:33、φ(n):20、e:13、d:17。其中,公钥用了两个,即(n和e),其余四个数字不公开。这些数字中最关键的是d,因为n和d组成了私钥,一旦d泄露,就等于私钥泄露。

讨论:在已知公钥(n,e)的情况下,推导d

由于d是e相对于φ(n)的模反元素,满足ed mod φ(n) ≡ 1,要想求出d,必须知道e和φ(n)。
又由φ(n) = (p-1)(q-1),只有知道p和q,才能求出φ(n)。
而n = pq,只有将n因式分解,才能算出p和q。

结论:如果n可以被因式分解,d就可以算出,也就意味着私钥被破解。因此,RSA加密算法的可靠性,取决于对极大整数做因式分解的难度。

3.4 加密和解密

有了公钥和私钥,就可以进行通信了。

  1. 假设乙要向甲发送信息m,他需要用甲的公钥(n,e)即(33,13)对m进行加密,得到密文c。加密规则为:me mod n ≡ c,假设m为6,则c=18。于是,乙将18发给了甲。
  2. 甲收到了乙发送过来的信息,即18,也就是c的值,并用自己的私钥(n,d)即(33,17)进行解密。解密规则为:cd mod n ≡ m,即m=6。因此,甲知道了乙发送过来的原文是6。

至此,“加密-解密”的过程就完成了。

思考:为什么解密规则是 cd mod n ≡ m

3.5 解密规则的证明

根据加密规则 me mod n ≡ c,得到 c ≡ me - kn
将其代入我们要证明的解密规则,可得到:
(me - kn)d mod n ≡ m
它等同于证明: med mod n ≡ m
又由于d为e相对于φ(n)的模反元素,故ed mod φ(n) ≡ 1,即ed = k*φ(n)+1,将ed代入上式得:
mkφ(n)+1 mod n ≡ m,(k为大于等于1的整数)
因此,上式得证则解密规则成立!

在此,我们再梳理一下加-解密过程中的这几个数字:p:3、q:11、n:33、φ(n):20、e:13、d:17、明文m:6、密文c:18。

  1. n为两个质数p和q的乘积,则n与以上除了p、q、n之外的任意数互质。(实际运用中,p和q为大质数,从而保证了n被破解的难度很大);
  2. e满足1 < e < φ(n),并且与φ(n)互质,d为e相对于φ(n)的模反元素,即ed=kφ(n)+1

接下来,分成两种情况证明解密。

  • m与n互质时
  1. 根据欧拉定理,mφ(n) mod n ≡ 1
  2. 由于1^k≡11*m≡m,对两边表达式进行k次幂运算后,再各乘以m,得到 mkφ(n)+1 mod n ≡ m,得证!
  3. 即m和n互质时,解密规则成立。
  • m与n不互质时
  1. 由于n为两个质数(p和q)的乘积,故m必为其中一个质数的倍数,在此取m=kp
  2. 根据欧拉定理,有 (kp)φ(q) mod q ≡ 1
  3. 由于1^[hφ(p)]≡11*(kp)≡kp,得到 (kp)hφ(n)+1 mod q ≡ kp
  4. ed=kφ(n)+1,代入上式可得 (kp)ed mod q ≡ kp,故 (kp)ed ≡ tq + kp(思考t和p的关系)
    t和p的关系:由上式得到 (kp)ed mod t ≡ kp ,显然,t必然能被p整除,即 t=t'p
  5. 因此,(kp)ed ≡ t'pq + kp,由于m=kpn=pq,所以 med mod n ≡ m,得证!即,m和n不互质时,解密规则也成立!

综上,无论明文m是什么内容,都能通过加密规则:me mod n ≡ c 生成密文c,再由解密规则:cd mod n ≡ m 得到明文m。

3.6 RSA算法的特点

通过对RSA算法原理、流程的验算分析,不难得出以下几个结论:

  1. RSA算法不需要进行密钥传递,安全性高。
  2. RSA算法的加密解密效率不高,一般应用于处理小数据。
    如加密KEY、数字签名等。

4. 示例

讲了半天RSA算法的理论知识,是时候展示真正的技术了。接下来,我们用终端来玩一下RSA吧。

由于Mac系统内置OpenSSL(开源加密库),所以我们可以直接在终端上使用命令来玩RSA。
OpenSSL中RSA算法的常用指令主要有三个:

genrsa,生成并输入一个RSA私钥
rsautl,使用RSA密钥进行加密、解密、签名和验证等运算
rsa,处理RSA密钥的格式转换问题。

操作流程如下:

  1. 生成一个长度为1024位的RSA私钥
openssl genrsa -out private.pem 1024
复制代码

结果如下:

  • 对私钥内容感兴趣的同学可以用下面的命令将私钥转换成明文。
openssl rsa -in private.pem -text -out private.txt
复制代码

自行打开private.txt文件即可,这里不作文件内容说明。

  1. 从私钥中提取公钥
openssl rsa -in private.pem -pubout -out public.pem
复制代码

结果如下:

  1. 假设明文文件内容是

  2. 对明文文件进行 公钥加密私钥解密

通过公钥进行加密

openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt
复制代码

通过私钥进行解密

openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
复制代码

结果如下:

解密后的文件dec.txt内容正好是【密码:helloRSA123456】,与明文内容一致。至此,RSA算法流程结束。

注意:也可用 私钥加密公钥解密,如:
1). 通过私钥进行加密
openssl rsautl -sign -in message.txt -inkey private.pem -out enc.txt
2). 通过公钥进行解密
openssl rsautl -verify -in enc.txt -inkey public.pem -pubin -out dec.txt

5. 参考资料

文末

本文github