一周一定理No.4 RSA解密算法


在一些关于谍战卧底的影视作品中,常常可以看到一些传递关键情报的紧张镜头,受环境所限,通常他们都是用文字传递,比如周星驰电影《国产凌凌漆》里的接头情报就这样(是不是有点浪漫):



可实际上,这种一目了然的情报一旦被敌方截获,是非常危险的。比如,在现代战争中,几乎绝不可能用这种冒险而缓慢的方式传递情报。那么,有没有比较安全的方式来传递情报呢?


确实有的,而且几乎你每天都在用,比如你在用支付宝,微信、银行卡,邮箱时,用密码登录就是相对安全的(前提是别人不知道你的密码)。这个安全性依赖于著名的RSA加密


今天,我们就来介绍这个简单而有效的公钥密码机制,只需要一点点的初等数论就可以把RSA讲清楚。而且,由于我们在第2期和第3期已经分别介绍了求一术欧拉定理,RSA早就是呼之欲出了(心有灵犀的读者也早就想到了RSA与欧拉定理的关联,已经有两次留言提到了RSA)!


首先,为了不直接传递文字,我们需要建立文字与数字(这就是坐标)的一一对应(一个字典),这一点是很容易办到的,我们可以26个拉丁字母


a,  b, c, d, ……,x,  y,  z 


依次对应于数字


 11,12,13,14,……,34, 35,36


为了下面给出一个完整的例子,这里我们给出整个文字——数字字典如下:


1.png


有了这个字典,我们就可以不用传递文字(words),而改为传递数字(numbers)了。例如,我要传递一个信息


六点北校打排球


可以用朴素的方式,先化成汉语拼音(请原谅我英文不好,不过可以想见,汉语拼音比英文更有效),这就转化成下述拉丁文字


liu dian bei xiao da pai qiu


进一步转化成数字就得到:


221931 14191124 121519 34191125 1411 261119 271931    (*)


为保证信息不易被人识破,我们要进一步这些数字进行加密(Encryption,然后再传递出去。这个加密,通常用一个函数(函数,即数字到数字的映射)来实现,一个方便(是指对加密和解密都方便)的函数是由MIT计算机科学实验室与数学系的三位学者Ron Rivest, Adi ShamirLeonard Adleman 1978年(恰好40年)提出的,很简单。由于他们姓氏的首字母分别为R,S,A,所以这个加密简称为RSA加密


2.jpg

从左到右:Adi Shamir,Ron RivestLeonard Adleman


RSA建议,选取两个不同的素数 p,q, 令 m=pq是它们的乘积,再选取一个与φ(m)=(p-1)(q-1)互素的正整数k, 那么由参数m, k给出的RSA加密函数就是


3.jpg


注意,这里取最小正剩余。简单地说,这个加密函数就是对自变量x在模m的意义下取k次幂。通常来说,k次幂会迅速变得很大从而很难计算(主要是存储引起的困难),但在模m的意义下,它始终在一个有限范围,而且有一个很简单的算法(逐次平方法,参见[1]第16章),让计算机来处理这个事情最好不过。



比如说,如果我们选取 p=2017, q=2027, 那么m=p*q=2017*2027=4088459,

φ(m)=(p-1)(q-1)=2016*2026= 4084416,从而若我们选取k=5,即可保证它与

φ(m)互素。


现在我们来利用由(1)(其中m,k如上选取)对(*)这一串数字加密,我们这样操作,由于现在m=4088459是一个七位数,我们将(*)中的数字划分为6位数,从而(*)中的数字分成了以下8个数字(最后一个是两位数,不过没关系):


221931, 141911,241215,193419,112514,112611,192719,31  


我们标记为 


5.jpg


现在我们依次计算出这些数字经过RSA函数(1)加密之后得到的各个数(其实我是用软件算的)

6.jpg

从而我们就得到加密之后的信息如下:


3188615 3342219 2262164 1266684 3169145 0892482 2320876 0009938


这些数字就是接收方(比如说红方或间谍)接收到的信息。显然,要读出发送方(比如说蓝方或同志)本身要传递的信息,就需要解密(Decryption


简单地说,解密——即破解密码,就是要求出加密函数的反函数(因此,本质上,前面用到的加密函数不能随便选,至少要保证是单射,否则解密会有麻烦——因为,若加密函数是多对一的,其反函数就是一对多,难免有歧义)。特别地,对RSA解密,就是要求出RSA函数(1)的反函数,换言之,就是要在模m意义下对一个整数开k次方。这个问题怎么解决呢?RSA指出,有一个漂亮的算法,它本质上就是求一术。为提醒你这是一个定理专栏,我们把它写成一个定理(见[1]第17章算法17.1):


6.jpg


:与这个算法精神一致的,是求解常系数线性微分方程的一个代数方法,见教你一招第3期(化非齐次常系数线性微分方程为代数同余方程)。本质上,这里存在着从整数到多项式的一个类比,我们将在以后某一期详细展开。



由于我们之前做好了铺垫,所以这个定理(毋宁说是算法)的证明写起来也非常简洁的,我们一并抄过来,如下:

7.jpg


根据上述算法,我们很容易对RSA解密,只要我们能够求出Step1的φ(m)。假如,你是蓝方(我方)的同志,你不仅知道m, 而且知道m=pq是两个不同素数p,q的乘积,那么φ(m)=φ(p)φ(q)=(p-1)(q-1)自然就知道了,而接下来的Step2与Step3是非常简单的。比如,接着前面的例子,你现在知道p=2017,q=2027,k=5, 那么你要解的方程就是

8.jpg


其中b依次取

3188615, 3342219, 2262164 ,1266684 ,3169145, 892482, 2320876 ,9938

这八个(接收到的)数字,我们依次记为

9.jpg


要还原我想传递的信息,你就要对i=1,2,3,4,5,6,7,8求解方程


10.jpg


下面我们就来实践一下RSA解密算法:



11.jpg

12.jpg

于是,我们就得到了原始的信息

221931 141911 241215 193419 112514 112611 192719 31  


利用文字——数字字典,可以将这一信息还原为


liudianbeixiaodapaiqiu


从中不难拼出汉字


六点北校打排球


这就是一开头我想要传递的信息。


请注意,我们上面走过的整个过程 

汉字→拼音→数字→加密数字→ 发送/接收→解密数字→拼音→汉字

都可以用简单的算法实现,因此全部可以交给计算机。这就是为什么你在生活中处处在应用加密解密,却没有觉察到的原因所在。你只需要输入初始的数据就可以了,后面的步骤都由设计好的程序来完成了!


另一方面,如果你不是我方同志(从而不知道m的素因子分解),但你截取了我传送的情报

13.jpg

那么,即便我公开 m 与 k 的值,你可能也无法破译密码。


原因在于,RSA解密的第一步是求出φ(m)。而对一个很大的数m,按定义来计算其欧拉函数φ(m)是不切实际的,对计算机来说也是如此。你要求出φ(m),就需要知道m的素因子分解,而至今都没有发现将一个大数做素因子分解的有效算法(至少对经典的计算机是如此,对量子计算机虽然存在有效的算法,但其硬件——量子计算机——本身都还在起步阶段)。正是这一点,保证了RSA密码的安全性。推而广之,任何其他的加密函数(参见[3])都可以用,只要能确保其解密很困难(从而保证其安全)。这个思路似乎很好地诠释了老子的名言:


有之以为利,无之以为用。




致谢:本文的计算应用了http://www.wolframalpha.com/,特表感谢。对这个软件创始人Wolfram的一个介绍,可见和乐数学的推送文章

教孩子真正的数学|数学软件创始人Wolfram




延伸阅读


[1]J. H. Silverman,《数论概论》(第4版),孙智伟等译,机械工业出版社,2016年。

[2]大栗博司,《用数学的语言看世界》,尤斌斌译,人民邮电出版社,2017年。

[3]Susan Loepp, William K. Wootters, 《信息保护:从经典纠错到量子密码》,吕欣等译,电子工业出版社,2008年。

[4]一周一定理No.2  求一术与方程术

[5]一周一定理No.3 欧拉定理

[6]教你一招第3期(化非齐次常系数线性微分方程为代数同余方程)




0.245046s