密码学的数学原理

学之数系列二美十二 由视电剧暗算》所《到想的? 谈谈密 码学数的原理学

-

-------------------------------------------------------------------------------

20802年16月 日0104 : 阅 次读: 1数88 2 默字认体 p9 t10t 1p1p 1tp2t1 p3 t41tp 51pt 61tp1 p7 t8p1t 02pt25p t

20

0年9月173日下 午0 :90:000

发表者：G

oolge（歌谷）究员研吴 军

前一子阵了看电剧《视暗算》蛮，喜它欢的构和思面的表里。演中其一有故个提事了密到学，码事故本身错不，但是有点弄故玄。不虚有过一是对点的，是就当今的码密学以是学为基础数。的没（有过暗看算的者读以看一可介绍下，thtp://en.tsina.oc.mcn/v/020-15017/ba86-968.5hsmtl

因为们后我要多次提面到这电视部。）剧

密

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

这样

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

在那里功成伏地击了本主日舰力。

队

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

公

密开钥原的理其实很单简，们我给以上的单面词 Cesar 加a密解来说明的它理。我原先把们变成一它组，数如它的 比Asic 代码i =0X[**************]41每三位（表代个字母一做明）码现在我们来设计一个。密系码，对统这明码个密。加

1，两个找大很的素数质数）P（和 Q， 越大越好，比如10 位0的, 长后计算它然的乘们 积=NP×QM，=P-1）（（Q×-1。）

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

3，找一

个数整D ，得使E × 除D以 M余 ，即1E D ×modM 1。=

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

。现在，我

用下们面的式公 对X加密， 到密得码 Y。

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

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

开公密钥好的处有：

1

简单。.

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

）

.3灵活可，产生很多的公开以钥E和密私D钥组的合不同给加密的

者。

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

数[***********][***********][***********][***********]62592

[***********][***********][***********][***********]449556230

= [***********][***********][***********][***********] 7×[***********][***********][***********][***********][1**********]394

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

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