密码学原理和数学模型的重要性

Comments: 2 Comments
Published on: 2012 年 03 月 06 日

昨天看完了google黑板报数学之美系列二十三篇。根据自己的记忆和理解想写写其中两篇《谈谈密码学原理》和《数学模型的重要性》。还有很多别的喜欢的内容,比如中文分词、信息论、分类器、搜索引擎相关的等等。这里就先说这两篇。 数学之美系列里讲的很多问题都有具体的数学模型,所以这个系列一直也有强调一个简单准确的数学模型有多么重要。

谈数学模型的重要性全篇举了天文学的例子,首先说的是托勒密,提出地心说的那位。他建立了一个大圆套小圆的模型来描述太阳系行星的运行轨迹,用了四十个这样的圆,比较复杂,但是很精确的描述了所有行星的运行轨迹,其模型在一千五百年后的今天也仅才误差一周左右。

纠正这个模型不是在基础环上再多套一些环,哥白尼发现如果以太阳为中心,那么只需要8-10个环就能比较好的描述太阳系行星的运行轨迹,“比较好”的意思是说这个模型之初是没有托勒密的40环模型准确的,也由于其不准确性不能更好的说服更多人,被教会指为邪说。

确立日心说地位的是开普勒,看到描述开普勒这段就能很明确的看出来,作者是钦佩地心说的托勒密的,而比较鄙视开普勒的,也许鄙视这个词用的比较过分。

但是真正创立了天文学,并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然今天我们可能会嘲笑托勒密犯的简单的错误,但是真正了解托勒密贡献的人都会对他肃然起敬。托勒密发明了球坐标,定义了包括赤道和零度经线在内的经纬线,他提出了黄道,还发明了弧度制。  当然,他最大也是最有争议的发明是地心说。虽然我们知道地球是围绕太阳运动的,但是在当时,从人们的观测出发,很容易得到地球是宇宙中心的结论。从地球上看,行星的运动轨迹是不规则的,托勒密的伟大之处是用四十个小圆套大圆的方法,精确地计算出了所有行星运动的轨迹。(托勒密继承了毕达格拉斯的一些思想,他也认为圆是最完美的几何图形。)托勒密模型的精度之高,让以后所有的科学家惊叹不已。即使今天,我们在计算机的帮助下,也很难解出四十个套在一起的圆的方程。每每想到这里,我都由衷地佩服托勒密。一千五百年来,人们根据他的计算决定农时。但是,经过了一千五百年,托勒密对太阳运动的累积误差,还是差出了一星期。

上边是作者说托勒密,下边是说开普勒的:

完成这一使命的是开普勒。开普勒在所有一流的天文学家中,资质较差,一生中犯了无数低级的错误。但是他有两条别人没有的东西,从他的老师第谷手中继承的大量的、在当时最精确的观测数据,以及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的,这样不需要用多个小圆套大圆,而只要用一个椭圆就能将星体运动规律描述清楚了。只是开普勒的知识和水平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了这个问题。

行星的运行轨迹故事到这里还没有结束,天王星的运行轨迹和用椭圆轨迹模型计算出的结果不相符,偷懒的办法是继续修正这一模型,但是一些严肃的科学家研究这一问题,发现是吸引天王星偏离轨道的海王星。这篇文章里边也有太阳系行星的一些故事,有兴趣的可以看看。

以天文学的发展这么一个过程描述了数学模型的重要性,并且总结了几点:

  1. 一个正确的数学模型应当在形式上是简单的。(托勒密的模型显然太复杂。)
  2. 一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确, 但是,如果我们认定大方向是对的,就应该坚持下去。(日心说开始并没有地心说准确。)
  3. 大量准确的数据对研发很重要。
  4. 正确的模型也可能受噪音干扰,而显得不准确;这时我们不应该用一种凑合的修正方法来弥补它,而是要找到噪音的根源,这也许能通往重大发现。

接下来谈谈密码学原理,根据我个人的了解有四类(不知是否准确):一类是单向的散列映射的,如MD5,SHA-1,RIPEMD等。这类加密是不可逆的,即只能把明文变成密文,但是知道密文也没办法找回明文;第二类就是密钥公钥RSA这种,是双向的,非对称的,可以加密解密;第三类是对称的,即通信双方约定一种加密方法,通过统一方法进行加密解密;第四类就是分组密码,可以把明文分组或者密钥分组,在特定条件下组合起来才能从密文得到完整的明文。

先说第一类,用过md5的同学都了解,md5使用哈希函数散列明文,获得一串定长的字串,这个字串就是明文的密文。一般我们用md5来加密我们不需要知道明文的内容,比如密码验证,数据库里存的是md5密文,下次用户登录时我们只需要把用户输入的密码进行md5加密与数据库内存储的密文对比即可知道是否是正确密码;还有数字签字等应用。既然是使用散列函数,那势必会造成散列的冲突,md5也有这样的可能,但是这个概率十分的小。另外中国密码学家王小云破译了MD5、HAVAL-128、MD4和RIPEMD等四个著名密码算法。十分敬仰这位女科学家!她的一些信息

第二类的加密方法就是google黑板报里说的那篇,是通过一种加密算法产生密钥公钥来进行可逆的加密方法。基本原理如下:

  1. 先找出两个大质数P、Q,需要一百位左右,这样可以防止短时间内破解。
  2. 获得N=(P*Q) ,和M=(P-1)*(Q-1)。
  3. 找一个整数E与M互质,然后再找一个整数D使 E*D mod M =1 。

这样我们就获得了这类加密算法的基本数据,其中E是公钥,是公开的,D是私钥,乘积N是公开的。 如果我们想加密一个明文X,我们这样:X^E mod N = Y ;这样Y就是密文了。 利用费马小定理我们就得到了解密方法:Y^D mod N = X 。

费马小定理内容是:a^p mod p = a  ,其中p是大于2的质数;
扩展一下,当然也有个费马大定理:x^n + y^n = z^n (其中n大于2)不定式的整数解都是平凡解,即至少有一个未知数是0。

原理就是这样,应用的话我们请出著名的Alice and Bob 来进行说明。

比如Alice有公钥和私钥,Bob想给Alice传递信息,Bob就先把自己的信息通过一种和Alice约定好的格式转换,然后根据上边的加密公式进行加密,把加密结果传给Alice。Alice获得密文之后就可以使用自己的密钥根据解密公式进行解密,然后逆向约定的格式转换,即获得Bob传递的信息了。关于这种非对称的RSA加密详细可参见wiki

第三类对称密码,也是传统密码的加密方法,一般是通过对明文编码后的结果和一个约定字串进行一系列位运算和变换得到密文,然后对这密文进行同一方法的逆运算即可得到明文。这种方法要求加密方法和加密字串都严格保密。感觉通信双方有个加密解密密码本那种也算这种类别里吧,比如使用这种方法的鼻祖凯撒,先约定一个密码本,里边写第一条字母A翻译成C,第二条数字4翻译成Z等等条码,然后通信双方都有这样一个密码本,这时候就可以使用明文通信说:这段信息或这个单词参照第几条解密等等,《潜伏》里那个余则成不是天天晚上听电台拿本书翻译密文么。。。。

然后第四类就是分组密码,一般可以对明文编码进行一系列对称加密或者非对称加密,把密文分段,最后组合密文进行相应的解密。一般这样的加密方法可以完成特定条件下才能完成解密过程,比如所有拿分段密文的人在场才能解密等情况,同样也可以把密钥分组也是可以的;还有一种情况是有多组密钥分组,只需要在指定组数的情况下组合起来即可解密密文。

比如电影中经常出现这样的情节:有一份绝密文件需要交给5位特工,为了防止某个特工被捕或者叛变,5名特工各自只持有其中1/5的文件(更好的做法是只持有其中1/5的密钥),这5名特工需要同时在场才能获取文件全文。但这也有一个隐患:如果真的有特工被抓了,当坏人们发现只拿到其中一份文件没有任何用处的同时,特工们也会因为少一份文件无法解开全文而烦恼。此时,你或许会想,是否有什么办法能够让特工们仍然能够恢复原文,即使一部分特工被抓住了?换句话说,有没有什么密文发布方式使得,只要5个人中半数以上的人在场就可以解开绝密文件?这样的话,侵入者必须要能操纵半数以上的特工才可能对秘密文件造成实质性的影响。这种秘密共享方式被称为(3,5)门限方案,意即5个人中至少3人在场才能解开密文。 实现(m,n)门限方案的一个传统办法是,把这份文件的密钥拆成C(n,m-1)份,每个人持有C(n-1,m-1)份密钥。在(3,5)门限方案中,我们需要C(5,2)=10个密钥,不妨分别用0到9编号;5个特工各持有6个密钥,密钥的分配如下:

特工#1: 012345
特工#2: 012   678
特工#3: 0  34 67 9
特工#4:  1 3 56 89
特工#5:   2 45 789

上述分配表的构造其实很简单:为特工的每一种5选3组合分配一个密钥,例如把密钥0分给特工1、2、3,把密钥1分给特工1、2、4,把密钥9分给特工3、4、5。这样的话,任意两个人在场都无法打开文件,因为他们始终缺少一把钥匙(这把钥匙分给了其余三个人)。而任意三个人在场都足以打开文件,因为根据鸽笼原理,任何一个5选3组合中总有一个人落在这三个人当中。这样,我们便利用组合数学巧妙地解决了这一问题。

在密码学中,我们有一些更精妙的方案。最巧妙的方法是,把秘密文件编码为三维空间中的一个点,然后生成5个过该点的平面,每个特工持有其中一个平面方程。显然,两个特工在一起是无法获得原文件的,因为两个平面的公共点有无穷多个;但三个平面的交点是唯一的,因此任意三个人在一起都能解开原文件。

另一个有趣的办法利用了下面这个事实:知道m-1次多项式函数上的任意m个点就能恢复出整个多项式。因此,我们可以把文件编码为一个二次多项式f,然后把f(1)、f(2)、f(3)、f(4)和f(5)的值告诉对应的特工。任意三个特工碰头之后,只需要解一个三元线性方程即可恢复原文件。多项式的这一性质还曾用于数据备份当中。

利用数论知识我们还能得到一个简单的协议。中国剩余定理告诉我们,给出m个两两互质的整数,它们的乘积为P;假设有一个大整数M,如果我们已知M分别除以这m个数所得的余数,那么在0到P-1的范围内可以唯一地确定这个M。我们可以想办法构造这样一种情况,n个数之中任意m个的乘积都比M大,但是任意m-1个数的乘积就比M小。这样,任意m个模数就能唯一地确定M,但m-1个数就不足以求出M来。

Mignotte门限方案就用到了这样一个思路。我们选取n个两两互质的数,使得最小的m个数的乘积比最大的m-1个数的乘积还大。例如,在(3,5)门限方案中,我们可以取53、59、64、67、71这五个数,前面三个数乘起来得200128,而后面两个数相乘才4757。我们把秘密文件编码为一个4757和200128之间的整数,比如123456。分别算出123456模上面那五个数的结果,得到19、28、0、42、58。显然,知道任意三个同余方程就可以唯一地确定出123456,但仅知道两个方程只能得到成百上千个不定解。例如,假设我们知道了x模59等于28,也知道了x模67得42,那么我们只能确定在0到59*67-1内的解913,并且只能断定M是一个形如59 * 67 * k + 913的数,其中k的数量级和当初选的那五个数一样大。

这里我们看到密码学中数学模型的威力,也是十分简单的数学模型。这样的例子很多,比如:条件概率贝叶斯定理,很简单的一个公式,应用领域宽广的你无法想象。还有博弈论、纳什均衡在经济等领域的应用,等等等等。

个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

2 Comments - Leave a comment
  1. alan20062006说道:

    感觉很这篇科普型的文章很适合我这种读本科的刚开始学信息安全的人哈哈,以后会多看看你的博文的

  2. amber说道:

    你也看数学之美系列啊。写的很不错。最近也想研究下一些组合概率的东西。苦于没时间。博客也一直没怎么更新。

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 11 月 19 日