前阵子看了电视剧暗算蛮喜欢它构思和里面表演其中有个故事提到了密码学故事本身不错但是有点故弄玄虚不过有点是对就是当今密码学是以数学为基础(没有看过暗算读者可以看下介绍http://ent.sina.com.cn/v/2005-10-17/ba866985.shtml

　　我们后面要多次提到这部电视剧)

　　密码学历史大致可以推早到两千年前相传名将凯撒为了防止敌方截获情报用密码传送情报凯撒做法很简单就是对 2十几个罗马字母建立张对应表比如说



　　这样如果不知道密码本即使截获段信息也看不懂比如收到个消息是 EBKTBP那么在敌人看来是毫无意义字通过密码本解破出来就是 CAESAR 词即凯撒名字这种编码思路方法史称凯撒大帝当然学过信息论人都知道只要多截获些情报统计下字母频率就可以解破出这种密码柯蓝道尔在他“福尔摩斯探案集”中“跳舞小人”故事里已经介绍了这种小窍门技巧在很长时间里人们试图找到些好编码思路方法使得解密者无法从密码中统计出明码统计信息但是基本上靠经验有经验编码者会把常用词对应成多个密码使得破译者很难统计出任何规律比如如果将汉语中“是”词对应于唯个编码 0543那么破译者就会发现 0543 出现特别多但如果将它对应成十个密码 054337372947 等等每次随机挑个使用每个密码出现次数就不会太多而且破译者也无从知道这些密码其实对应个字这里面虽然包含着朴素概率论原理但是并不科学化另外好密码必须做到不能根据已知明文和密文对应推断出新密文内容历史上有很多在这方面设计得不周到密码例子在第 2次世界大战中日本军方密码设计就很成问题美军破获了日本很多密码在中途岛海战前美军截获日军密电经常出现 AF 这样个地名应该是太平洋某个岛屿但是美军无从知道是哪个于是美军就逐个发表自己控制每个岛屿上假新闻当美军发出“中途岛供水系统坏了” 这条假新闻后从截获日军情报中又看到 AF 供水出来问题电文美军就断定中途岛就是 AF事实证明判断正确美军在那里成功地伏击了日本主力舰队

　　事实上在第 2次世界大战中很多顶尖科学家包括提出信息论香农都在为美军情报部门工作而信息论实际上就是情报学直接产物香农提出信息论后为密码学发展带来了新气象根据信息论密码最高境界是使得敌人在截获密码后对我方所知没有任何增加用信息论专业术语讲就是信息量没有增加般来讲当密码的间分布均匀并且统计独立时提供信息最少均匀分布使得敌人无从统计而统计独立能保证敌人即使看到段密码和明码后不能破译另段密码这也是暗算里传统破译员老陈破译份密报后但无法推广原因而数学家黄依依预见到了这个结果她知道敌人新密码系统编出密文是统计独立有了信息论后密码设计就有了理论基础现在通用公开密钥思路方法包括暗算里“光复号”密码就是基于这个理论

　　公开密钥原理其实很简单我们以给上面单词 Caesar 加解密来介绍说明它原理我们先把它变成组数比如它 Ascii 代码 X=099097101115097114(每 3位代表个字母)做明码现在我们来设计个密码系统对这个明码加密

　　1找两个很大素数(质数)P 和 Q越大越好比如 100 位长, 然后计算它们乘积 N=P×QM=(P-1)×(Q-1)

　　2找个和 M 互素整数 E也就是说 M 和 E 除了 1 以外没有公约数

　　3找个整数 D使得 E×D 除以 M 余 1即 E×D mod M = 1

　　现在世界上先进、最常用密码系统就设计好了其中 E 是公钥谁都可以用来加密D 是私钥用于解密定要自己保存好乘积 N 是公开即使敌人知道了也没关系

　　现在我们用下面公式对 X 加密得到密码 Y



　　好了现在没有密钥 D神仙也无法从 Y 中恢复 X如果知道 D根据费尔马小定理则只要按下面公式就可以轻而易举地从 Y 中得到 X



　　这个过程大致可以概况如下:　



　　公开密钥好处有:

　　1.简单

　　2. 可靠公开密钥思路方法保证产生密文是统计独立而分布均匀也就是说不论给出多少份明文和对应密文也无法根据已知明文和密文对应来破译下份密文更重要是 N,E 可以公开给任何人加密用但是只有掌握密钥 D 人才可以解密, 即使加密者自己也是无法解密这样即使加密者被抓住叛变了整套密码系统仍然是安全(而凯撒大帝加密思路方法有个知道密码本人泄密整个密码系统就公开了)

　　3.灵活可以产生很多公开密钥E和私钥D组合给区别加密者

　　最后让我们看看破解这种密码难度首先要声明世界上没有永远破不了密码关键是它能有多长时间有效期要破公开密钥加密方式至今研究结果表明最好办法还是对大字 N 进行因数分解即通过 N 反过来找到 P 和 Q这样密码就被破了而找 P 和 Q 目前只有用计算机把所有数字试遍这种笨办法这实际上是在拼计算机速度这也就是为什么 P 和 Q 都需要非常大种加密思路方法只有保证 50 年计算机破不了也就可以满意了前几年破解 RSA-158 密码是这样因数分解



　　395058745832651445264197678006144819960207764603049364541393760515793556265294

　　50683609727842468219535093544305870490251995655335710209799226484977949442955603

　　= 3388495837466721394368393204672181522815830368604993048084925840555281177 ×11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

　　现在让我们回到暗算中黄依依第次找结果经过系列计算发现无法归零也就是说除不尽我猜她可能试图将个大数 N 做分解没成功第 2次计算结果是归零了介绍说明她找到 N=P×Q 分解思路方法当然这件事能不能用算盘完成我就不知道了但我觉得比较夸张另外我对该电视剧还有个搞不懂问题就是里面提到“光复号”密码误差问题个密码是不能有误差否则就是有密钥也无法解码了我想可能是指在构造密码时P 和 Q 的没找对其中个(甚至两个都)不小心找成了合数这时密码保密性就差了很多如果谁知道电视剧里面讲“误差”是指什么请告诉我另外电视剧里提到冯∙诺依曼说他是现代密码学祖宗我想是弄错了应该是香农冯∙诺依曼贡献在发明计算机和提出博弈论(game theory)

　　不管如何样我们今天用所谓最可靠加密思路方法数学原理其实就这么简单点也不神秘无非是找几个大素数做些乘除和乘方运算就可以了