RSA加密算法

背景

在众目睽睽之下，如何秘密地与你心爱的女神交流呢？

现在假设坐在后排的你想和教室靠前排的女神表白，内容是：

The love that I have. Of the life that I have. Is yours and yours and yours.

你需要将内容写在纸条上，让中间的同学帮你传给女神，中间的同学不一定可信，意味着他们可能会偷看你的情书，所以你要用某种方式秘密地与女神传递信息。你们都可以使用计算机作为辅助工具。

思考

你可能会想到使用某种方法加密，比如base64编个码不就很难辨认了吗？很遗憾，作为网安院的学生，一眼看出是base64也不是什么很难的事情。那就用密钥加密呢？似乎也不行，要么其他人看不懂（当然你的女神也应该看不懂并且报告老师你骚扰她），要么就把密钥一起送过去所有人也都知道了密钥……乍一看好像无解了呢？

难道你的表白计划泡汤了？

人类的智慧不允许你这么放弃！我们尝试将难题留给别人，比如分解一个很大的整数是一件极其耗时的事情：

比如$114514=2\times 31\times 1847$。

什么？你觉得还挺快的？那么这个数呢？

n = 23220619839642624127208804329329079289273497927351564011985292026254914394833691542552890810511751239656361686073628273309390314881604580204429708461587512500636158161303419916259271078173864800267063540526943181173708108324471815782985626723198144643256432774984884880698594364583949485749575467318173034467846143380574145455195152793742611717169602237969286580028662721065495380192815175057945420182742366791661416822623915523868590710387635935179876275147056396018527260488459333051132720558953142984038635223793992651637708150494964785475065404568844039983381403909341302098773533325080910057845573898984314246089

我赌你肯定不知道，用电脑也不一定算得出来是：

p1 = 138376604533530412400239558340424700312412702699022481119357799054715877829291635290832719835033140580690053865677079316241919169166375123691917675235979462772103681398725285808551041924624882840901583892858174270714471366531758975241868470938138238307005782651296179579961869801841395682782645916848523771439
p2 = 167807411649676462546661119644113081915542378755778327057156191284453150887662343414908916953154897183613548083558919410359642450001343644814021159828724844730881111955050992398535063409828169462180970629537792676998647880110463527555034040871485964361418080481113059959410616446772218038141157051007091689351

于是你可以认为只有生成这个数的人知道怎么分解。

实践

那么我们可以这样做：

• 你：写纸条告诉女神叫她做这些事情

  1. 生成两个超级大的素数$p,q$.
  2. 计算乘积$n=pq$，以及$n$的欧拉函数$\phi (n)=(p-1)(q-1)$
  3. 选择一个数$e$，要满足两个条件：$gcd(e,\phi (n))=1$和$1<e<\phi (n)$
  4. 把$n,e$发给你

• 女神：考虑到你还可以信赖，于是照做了

  n = 23220619839642624127208804329329079289273497927351564011985292026254914394833691542552890810511751239656361686073628273309390314881604580204429708461587512500636158161303419916259271078173864800267063540526943181173708108324471815782985626723198144643256432774984884880698594364583949485749575467318173034467846143380574145455195152793742611717169602237969286580028662721065495380192815175057945420182742366791661416822623915523868590710387635935179876275147056396018527260488459333051132720558953142984038635223793992651637708150494964785475065404568844039983381403909341302098773533325080910057845573898984314246089
  e = 65537
  

• 你：收到了$n,e$，接下来就是编码、加密

  1. 将你要发的话编码：(就是个很简单的大端对齐的ASC码而已)

     m = 350251451480057815969538344558525321373340889419321544637307514448267230505444585631297632836814333623846253375180424533076043802839008147842270112359930874450493955056760675951080238
     

  2. 计算密文$c=m^e\mathrm{mod}n$

     c = 5561071861747835664705185440041811474814922914520261960359086942842327680331733718508972762428553700896857496213502429059564297724325410881053081595671745136437931682185318756226632192293055657056092227289830191526927938690002785555906982577736278698531153117146710265980434639242383080889643248497310960593249456649480988706457430769041236899389679225086516470654357175220056589941100568218624868107376854624301529705154488997056121050281762484034563225348774259021366200999886635125934793563872128467522744523002151826342297264090462234790267214232546032869208814823546928447005293811658052142478937375635750191686
     

  3. 把$c$写在纸上，让别人传给女神

• 女神：收到了$c$，接下来就是解密

  1. 计算$d=\mathrm{inverse}(e,\phi (n))$，其实$d$就是满足$ed\equiv 1(\mathrm{mod}\phi (n))$的一个数而已，需要注意的是，这个$d$只有她自己知道

     d = 21446573979485909309549551033069703669373404787258955546416066135911164202195452173134664094485196187442201700688721170993750030666394940869648141556371090096640167439823244999483859169047469923251985231366951046835292305062488045063767337314115441586528401908385111949413093624796168002386770878080611162798422169771679868048009928751191482907090924247124858076662199409049308544102322019854416512944937570166867090869068932110694314217793636969937187134720612355125284732832787056314908244496070776644006768159293566929498685724860864708035296090738294043863380684853253852735409698026131276184046794855748968330473
     

  2. 计算明文$m=c^d\mathrm{mod}n$

     m = 350251451480057815969538344558525321373340889419321544637307514448267230505444585631297632836814333623846253375180424533076043802839008147842270112359930874450493955056760675951080238
     

  3. 按照编码的方法，获得原先的文本：

     The love that I have. Of the life that I have. Is yours and yours and yours.
     

实践很成功，女神知道你要说什么了。

分析

为什么这样一番奇怪的操作就可以加密你和女神的消息了呢？

我们不妨从中间人的视角看看发生了什么，现在假设我们是传纸条的人：

• 看到了那个帅哥叫一个漂亮姐姐自己生成一堆数
• 看到了漂亮姐姐发回给帅哥的两个数，根据上一条消息你知道这两个数分别是$n,e$
• 看到了帅哥发了一个莫名其妙的数给漂亮姐姐
• 看到漂亮姐姐的脸红了，我们很不舒服

我们甚至知道他们在用RSA加密。知道的参数有$n,e,c$，但是要获得明文$c$还需要一个参数$d$，而我们知道$d$这个数一直在漂亮姐姐的手上，从来没有告诉过别人。想要求出$d$就需要求出$e$和$\phi (n)$，前者我们知道，那么就需要知道后者，而想要知道后者就需要知道$p,q$。说白了这不就是要分解辣么大的$n$吗？

说着简单，分解$n$就可以知道他们说了什么，但是太长了分解不出来……所以不知道他们在说什么（，不对，女孩子脸红了，难道说？）

所以，这种加密方式的安全性被转移到了一个数学难题上，只要这个数学难题没有快捷的方法解，那么这种加密的方式就是安全的。

总结

---

我们把漂亮姐姐发出的两个数字$n,e$称作“公钥”，而只有漂亮姐姐自己知道的$d$也连同$n$一起称为“私钥”。

其他人将信息编码，用公钥加密得到密文，将密文发回给接收者，接收者用自己的私钥解密重新得到明文信息。

这样看上去很神奇的密码体系称为“公钥密码”。

这种密码体系的安全性依赖于$n$分解的难度，现在大家都在用的电脑还不具有快速分解一个大整数的能力，所以一直以来都是很安全的，但是一旦有新型的计算机广泛使用，这种密码体系会瞬间变得不安全。令人担忧的是，不同于电子计算机的量子计算机就具有这样的能力，不过现在还并没有广泛使用，相关技术尚未成熟，我们还大可放心地再使用一段时间这样的加密算法。

正确性证明

我们只需要搞清楚为什么$c^d\mathrm{mod}n$的结果恰好又等于$m$就行了。下面开始证明：

由加密的步骤，可知：

$$\begin{gathered} \because c=m^e\mathrm{mod}n \\ \therefore c\equiv m^e(\mathrm{mod}n) \end{gathered}$$

由同余的性质，有:

$$c^d\equiv m^{ed}(\mathrm{mod}n)$$

由$d$的来源，我们知道$ed=k\phi (n)+1,(k\in \mathbf{N})$，那么:

$$c^d\equiv m^{k\phi (n)+1}(\mathrm{mod}n)$$

上面式子的右侧是不是恰好与$m$同余呢？我们要分两种情况讨论：

• $m$和$n$互素：

  先来看一下欧拉定理：若$a,b$互素，有:$a^{\phi (b)}\equiv 1(\mathrm{mod}b)$，换到这里就有：

  $$m^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

  由同余式性质的性质，有：

  $$\begin{gathered} m^{k\phi (n)}\equiv 1^k\equiv 1(\mathrm{mod}n) \\ {m}^{k\phi (n)+1}\equiv m(\mathrm{mod}n) \end{gathered}$$

  我们再把这些代回分情况讨论前的式子：

  $$c^d\equiv m(\mathrm{mod}n)$$

  考虑到$m$的取值范围：$0<m<n$，有$m=c^d\mathrm{mod}n$，故原式成立，可以还原出密文

• $m$和$n$不互素：

  还是和之前一样，考虑下面的式子是否成立：

  $$m^{k\phi (n)+1}\equiv ?m(\mathrm{mod}n)$$

  既然它们不互素，而且$n$有两个素数因子$p,q$，那么这两个素因子之一也是$m$的因子，不妨记$m=hp$，因为$m<n$，

  所以$h<q$，$q$是素数，那么$h,q$一定互素，$m=hp$也与$q$互素，由欧拉定理，我们有：

  $$m^{\phi (q)}\equiv 1(\mathrm{mod}q)$$

  由同余的性质，有：

  $$\begin{gathered} m^{k\phi (p)\cdot \phi (q)}\equiv 1(\mathrm{mod}q) \\ {m}^{k\phi (n)+1}\equiv m(\mathrm{mod}q) \\ q\mid m^{k\phi (n)+1}-m \end{gathered}$$

  注意到最后一个式子右侧可以提出$m$，并且上面假设了$m$是$p$的倍数，又有$p,q$互素，所以式子右侧也是$n$的倍数：

  $$m^{k\phi (n)+1}\equiv m(\mathrm{mod}n)$$

  故原式成立。

所以，我们成功证明了RSA算法的正确性。用公钥加密的密文只能由私钥解密，并且！不知道你有没有注意到$d$的生成方式

$$ed\equiv 1(\mathrm{mod}\phi (n))$$

说明$e,d$两个人的地位是一样的，那么反过来，用公钥加密的密文，一定只能用私钥解密。