[05.13]古典密码学

夏理雾棋

古典密码学（一）
爱伦 坡所说：密码可破!人类的智慧不可能造成这样的密码，使得人类本身的才智即使运用得当也无法破开它!
一 、密码学的发展历程
密码学在公元前400多年就早已经产生了，正如《破译者》一书中所说“人类使用密码的历史几乎与使用文字的时间一样长”。密码学的起源的确要追溯到人类刚刚出现，并且尝试去学习如何通信的时候，为了确保他们的通信的机密，最先是有意识的使用一些简单的方法来加密信息，通过一些（密码）象形文字相互传达信息。接着由于文字的出现和使用，确保通信的机密性就成为一种艺术，古代发明了不少加密信息和传达信息的方法。例如我国古代的烽火就是一种传递军情的方法，再如古代的兵符就是用来传达信息的密令。就连闯荡江湖的侠士，都有秘密的黑道行话，更何况是那些不堪忍受压迫义士在秘密起义前进行地下联络的暗语，这都促进了密码学的发展。

事实上，密码学真正成为科学是在19世纪末和20世纪初期，由于军事、数学、通讯等相关技术的发展，特别是两次世界大战中对军事信息保密传递和破获敌方信息的需求，密码学得到了空前的发展，并广泛的用于军事情报部门的决策。例如在希特勒一上台时，德国就试验并使用了一种命名为“谜”的密码机，“谜”型机能产生220亿种不同的密钥组合，假如一个人日夜不停地工作，每分钟测试一种密钥的话，需要约4.2万年才能将所有的密钥可能组合试完，希特勒完全相信了这种密码机的安全性。然而，英国获知了“谜”型机的密码原理，完成了一部针对“谜”型机的绰号叫“炸弹”的密码破译机，每秒钟可处理2000个字符，它几乎可以破译截获德国的所有情报。后来又研制出一种每秒钟可处理5000个字符的“巨人”型密码破译机并投入使用，至此同盟国几乎掌握了德国纳粹的绝大多数军事秘密和机密，而德国军方却对此一无所知；太平洋战争中，美军成功破译了日本海军的密码机，读懂了日本舰队司令官山本五十六发给各指挥官的命令，在中途岛彻底击溃了日本海军，击毙了山本五十六，导致了太平洋战争的决定性转折。因此，我们可以说，密码学为战争的胜利立了大功。在当今密码学不仅用于国家军事安全上，人们已经将重点更多的集中在实际应用，在你的生活就有很多密码，例如为了防止别人查阅你文件，你可以将你的文件加密；为了防止窃取你钱物，你在银行账户上设置密码，等等。随着科技的发展和信息保密的需求，密码学的应用将融入了你的日常生活。
二 、密码学的基础知识
密码学(Cryptogra phy)在希腊文用Kruptos(hidden)+graphein(to write)表达，现代准确的术语为“密码编制学”，简称“编密学”， 与之相对的专门研究如何破解密码的学问称之为“密码分析学”。密码学是主要研究通信安全和保密的学科，他包括两个分支：密码编码学和密码分析学。密码编码学主要研究对信息进行变换，以保护信息在传递过程中不被敌方窃取、解读和利用的方法，而密码分析学则于密码编码学相反，它主要研究如何分析和破译密码。这两者之间既相互对立又相互促进。密码的基本思想是对机密信息进行伪装。一个密码系统完成如下伪装：加密者对需要进行伪装机密信息（明文）进行伪装进行变换（加密变换），得到另外一种看起来似乎与原有信息不相关的表示（密文），如果合法者（接收者）获得了伪装后的信息，那么他可以通过事先约定的密钥，从得到的信息中分析得到原有的机密信息（解密变换），而如果不合法的用户（密码分析者）试图从这种伪装后信息中分析得到原有的机密信息，那么，要么这种分析过程根本是不可能的，要么代价过于巨大，以至于无法进行。
在计算机出现以前，密码学的算法主要是通过字符之间代替或易位实现的，我们称这些密码体制为古典密码。其中包括：易位密码、代替密码（单表代替密码、多表代替密码等）。这些密码算法大都十分简单，现在已经很少在实际应用中使用了。由于密码学是涉及数学、通讯、计算机等相关学科的知识，就我们现有的知识水平而言，只能初步研究古典密码学的基本原理和方法。但是对古典密码学的研究，对于理解、构造和分析现代实用的密码都是很有帮助。以下介绍我们所研究的古典密码学。
三 、古典密码学的基本方法
从密码学发展历程来看，可分为古典密码（以字符为基本加密单元的密码）以及现代密码（以信息块为基本加密单元的密码）两类。而古典密码有着悠久的历史，从古代一直到计算机出现以前，古典密码学主要有两大基本方法：
①代替密码：就是将明文的字符替换为密文中的另一种的字符，接收者只要对密文做反向替换就可以恢复出明文。
②置换密码(又称易位密码)：明文的字母保持相同，但顺序被打乱了。
现在我们汇报我们研究的几种简单的古典密码学
1.滚桶密码
在古代为了确保他们的通信的机密，先是有意识的使用一些简单的方法对信息来加密。如公元六年前的古希腊人通过使用一根叫scytale的棍子，将信息进行加密。送信人先将一张羊皮条绕棍子螺旋形卷起来（如图），然后把要写的信息按某种顺序写在上面，接着打开羊皮条卷，通过其他渠道将信送给收信人。如果不知道棍子的宽度（这里作为密匙）就是不容易解密里面的内容的，但是收信人可以根据事先和写信人的约定，用同样的scytale的棍子将书信解密。
2. 掩格密码
16世纪米兰的物理学和数学家Cardano发明的掩格密码，可以事先设计好方格的开孔，将所要传递的信息和一些其他无关的符号组合成无效的信息，使截获者难以分析出有效信息。

3. 棋盘密码
我们可以建立一张表，使每一个字符对应一数 ， 是该字符所在行标号， 是列标号。这样将明文变成形式为一串数字密文。
例如：明文 battle on Sunday                  
密文 121144443115034330434533141154
（其中0表示空格）
例如：如图Polybius的棋盘密(B.C.200)也是一种在古希腊时已经发展的比较完备加密的方法。希腊文字“ ” 被加密为数字25 42 45 41 44 35 43
4.凯撒（Caesar）密码
据记载在罗马帝国时期，凯撒大帝曾经设计过一种简单的移位密码，用于战时通信。这种加密方法就是将明文的字母按照字母顺序，往后依次递推相同的字母，就可以得到加密的密文，而解密的过程正好和加密的过程相反。
例如：明文  battle &

夏理雾棋

nbspon  Sunday    密文   wvoogz gi Npiyvt (将字母依次后移5位)
如果我们令 个字母分别对应于整数 ～ ， ，则凯撒加密方法实际上是进行了一次数学取模为26的同余运算，即   
其中m是明文对应的数据，c是与明文对应的密文数据，k是加密用的参数，也叫密钥。比如：battle on Sunday对应数据序列为020120201205  1514  192114040125   若取密钥k为5时，得密文序列 070625251710  2019  240019090604 。这样我们也可以用数字来代替字母进行传递信息，也方便用数学变换和计算机编程进行加密与解密。
5.圆盘密码
由于凯撒密码加密的方法很容易被截获者通过对密钥赋值（1～25）的方法破解，人们有进一步将其改善，只要将字母按照不同的顺序进行移动就可以提高破解的难度，增加信息的保密程度。如15世纪佛罗伦萨人Alberti发明圆盘密码就是这种典型的利用单表置换的方法加密的方法。如图在两个同心圆盘上，内盘按不同（杂乱）的顺序填好字母或数字，而外盘按照一定顺序填好字母或数字，转动圆盘就可以找到字母的置换方法，很方便的进行信息的加密与解密。凯撒密码与圆盘密码本质都是一样的，都属于单表置换，即一个明文字母对应的密文字母是确定的，截获者可以分析对字母出现的频率，对密码体制进行有效的攻击。
6.维吉尼亚（Vigenere）密码为了提高密码的破译的难度，人们有发明一种多表置换的密码，即一个明文字母可以表示为多个密文字母，多表密码加密算法结果将使得对单表置换用的简单频率分析方法失效，其中维吉尼亚密码就是一种典型的加密方法。维吉尼亚密码是使用一个词组（语句）作为密钥，词组中每一个字母都作为移位替换密码密钥确定一个替换表，维吉尼亚密码循环的使用每一个替换表完成明文字母到密文字母的变换，最后所得到的密文字母序列即为加密得到的密文，具体过程如下：
设密钥 ，明文 ，  加密变换   其中         
例如，M＝data security，k＝best。可以先将M分解为长为4的序列data  secu rity
每一节利用密钥k＝best加密得密文c=Ek(M)=EELT TIUN SMLR。
当密钥k取的词组很长时，截获者就很难将密文破解。（我们还在计算机上就维吉尼亚密码设计的方法，编写了一个小的程序，可以运用其进行加密和相应的解密。见附录）
由于我们知识和条件所限，本学期对以上6种古典加密方法进行了学习和研究，从中我们收获颇多，我们了解古典密码学的基本原理和方法，并能够对信息进行简单的加密和解密，大大提高我们的学习文化知识的兴趣和热情，如果有条件我们在今后将进一步研究密码学。
组长：金 宇
组员：徐汪洋  牟杰  
杨得志 金益

指导教师：赵国藩
2003-12-23
附录：
一、密码学在侦探中的例子
在福尔摩斯侦探小说中有一则《The dancing men》的故事，其中有关于破译密码的情节。




二、自定义的密码符号
我们可以定义一种符号系统，如下图，将字母和其所在的边框对应




则图形 表示的是英文单词：beauty
三、设计的维吉尼亚密码（密匙为decipher）
密文
献给密码破解者（decipher）
Gicz svgkrv:
  K ib h qzghnm hjlfrp ubjkiew sh axexvhr. K ppci r svqjalq rqh K ib dvzwmpo iv ejn cqc uvv jrqg iscmth.
  Xjm eyssoio qh tc nhmipi. P ed myub 1.57 blxihw jqvo flw qa etpkyw mu 71 sxssj. Pepg hayuhrva dmxvq qcst mye rj om. Hvqv esaa llvv xrhzxlruoc vw bl. Xydx oizlw dh jgma brydtrg. X hq era ywgymvg edwja qp zikowa.  Ecwlqcvo M rp e dqi asf iev. Q ulic uevpty avop. K mcqsp pc ompsw.Z osxm thxzqk ompa zvuc ocro. Eeg M nqzl wnhiv ndvh krs. K wuaie kexm hbkru akbw air pmns puh vyip pda arwit. Vdd M rp kgbiprx ievbty eeg jcbilv. Zq xjm ehwk waq uduxyv M jikl tlw sp 5 sxssj. Vs K ib iitrqkvv tsih epl bvvv zstzxlh reswb iomj svqjalq sxx K ld usk nsyv wva kr pqa

夏理雾棋

t dizjlv yjpgboc. Ewjsh pry vmas qv d acg iv pfvi ymxnlk? Spgihl lvot om slei gsebdy!
  M yrtg bd oiru jtwb fsl dw uwdu ej ssuaxipv.
  Zmvp qlwk zmuptz!
                                                Qruc
                                                10.11.2003
明文
Dear doctor:
I am a middle school student of sixteen. I have a problem and I am writing to ask you for some advice.
The problem is my weight. I am just 1.57 metres high but my weight is 71 kilos. Many students often make fun of me. Some boys were unfriendly to me. That makes me feel unhappy. I am now worried about my weight. Although I am a bit too fat. I feel rather well. I enjoy my meals.I love eating meat very much. And I like sweet food too. I often have sugar with tea milk and even hot water. Now I am getting fatter and fatter. In the past two months I have put on 5 kilos. So I am becoming more and more worried about this problem but I do not kown how to lose weight quickly. Could you tell me a way to lose weight? Please help me dear doctor!
I hope to hear from you as soon as possible.
With best wishes!
                                             Mary
                                             10.11.2003
四、公开密钥密码体制
1976年，Diffie和Hellman在《密码学的新方向》一文中提出了公开密钥密码体制的思想，开创了现代密码学的新领域，其基本原理如下：
假定有两个用户A和B，每个用户都有两个算法：公开的PA、 PB和保密的SA   SB；由P无法求得S。当A要给B发信息 时，他用公开的加密PB，得到 ，发送给B。因为SB是保密的除了B之外，其他人(甚至包括A)无法通过C反过来求出 ，从而满足了保

夏理雾棋

密性要求。可见这时B的算法应满足：   
但这时真实性无法保证，因为PB是公开的，任何人都可以自称是用户A，向B发仿造的密文 为了实现真实性要求，A可以用自己的保密算法SA对 加密得到 ，发送给B，B收到以C之后用A的公开算法PA脱密：
其他人(包括B)都不知道SA，无法求得c’使得PA(c’)有意义，因此都无法冒充A，这就保证了 确实为A发出的，满足了真实性要求。

爱伦 坡所说：密码可破!人类的智慧不可能造成这样的密码，使得人类本身的才智即使运用得当也无法破开它!

五、密码学的前景
随着科学技术的迅猛发展，人们对信息安全和保密的重要性认识不断提高，在信息安全中起着举足轻重作用的密码学也就成为信息安全中不可或缺的重要部分。密码学的研究前景十分广阔，这个总是秘而不宣的重要角色，在未来发展中将起到不可估量的作用。1985年Koblitz和Miller提出将椭圆曲线用于公钥密码体制，他们第一次用椭圆曲线成功地实现了已有的一些公钥密码算法包括Differ-Hellman算法。现在椭圆曲线密码体制不仅是一个重要的理论研究领域，而且已经作为民用信息安全技术走向产业化。在信息技术领域的保密通信、数字签名、秘密共享、消息认证、密钥管理，人工智能密码学，量子密码学，安全电子商务系统，电子现金系统，电子选举系统，电子招投标系统，电子彩票系统等，密码学都在发挥着不为人知的作用。

快斗

学习