分析密码学中的数学原理

这两天看到《数学之美》中讲到的计算机中的数学模型,以及《What is Mathematics》的数论,看的心痒痒。今天懒癌暂时被抑制住了,我就要分析一下,密码学中的数学模型!

我们依据RSA加密算法的基本特性(也是很多加密算法的共同点):

  • 它们都有两个完全不同的样式,一个用于加密,一个用于解密。
  • 两个看上去无关的钥匙,在数学上是有联系的。

现在,我们先使用相对简单的RSA算法来表明公钥的原理,并给Vision加密和解密。
首先,先将Vision变成一串数字,以它的ASCII值为例:
$$X=086105115105111110$$(每三位代表一个字母)做明码,针对这个明码来设计一个密码系统。

  • 找两个很大的素数$P$和$Q$,越大越好,比如100位长的,计算他们的乘积(因为越大越难分解)
    $N=P\times Q$
    $M=(P-1)\times (Q-1)$

  • 找一个与$M$互素的整数$E$(互素,$M$与$E$除了1之外没有公约数)

  • 找一个整数$D$,使得$E\times D\ mod\ M=1$ (费马小定理)

费马小定理:如果p是任意一个不能整除整数a的素数,则满足:
$$a^{p-1}\equiv 1(mod\ p)$$

现在这样一个密码系统就已经设计好了。其中$E$是公钥(用于加密),$D$是私钥(用于解密),联系公钥和秘钥的乘积$N$是公开的。
现在我们对要加密的数据进行加密:
$$X^E\ mod\ N=Y$$
加密,完成!现在没有密钥$D$神仙也不能从$Y$中解密出$X$(运算量太大,从$N$中分解出$P$和$Q$就要算上好多年)
可以使用密钥就可以轻而易举地从$Y$中得到$X$
$$Y^D\ mod\ N=X$$
基本流程如下:

可以看出,公钥加密的好处:

  • 简单,就是一些乘除开方。
  • 可靠,很难逆向破解,公钥只能用来加密,加密后非密钥不能解密。
  • 灵活,可以产生很多公钥和密钥的组合分配给不同的加密者。

世界上没有不能破解的密码,关键是它能保证在多长时间内不被破解。

要破解公钥加密的方式,迄今为止最有效的办法还是分解$N$,通过$N$逆向分解出$P$和$Q$,这也是$N$和$Q$一定要找非常大的素数的原因,因为素数的重要性就在于:每一个整数都能表示为素数的乘积,除了次序可以任意排列外,一个数N的素因子分解是唯一的。意思是要在大数$N$的所有素因子中组合出$P$和$Q$满足$P\times Q=N$,因为选择的$P$和$Q$都是极大的素数,所以,这个计算量是不可估量的,就算由计算机穷举每一种可能性,也要很久,实际上就是再拼计算机的计算速度。

总结:其实加密运算用到的最重要的概念就是素数,这才是加密算法中的根本,在于其难分解性。
其实数学的很多知识都是如此,看起来没有什么大用,但实际上,用处很大,就拿搜索引擎来说吧,究其本质也是布尔运算,但是其中也掺杂了很多技术。
最后一句感叹:数学,学以致用才好!

参考资料
《数学之美》(由电视剧《暗算》所想到的 — 谈谈原理)
《什么是数学:对思想和方法的基本研究》(素数章节)

全文完,若有不足之处请评论指正。
本文标题:分析密码学中的数学原理
文章作者:ZhaLiPeng
发布时间:2015年09月09日 18时19分
本文字数:本文一共有929字
原始链接:https://imzlp.me/posts/30891/
许可协议: CC BY-NC-SA 4.0
转载请保留原文链接及作者信息,谢谢!
您的捐赠将鼓励我继续创作!