【文章】应用密码学 - 隐写术代替和换位密码

1.2 隐写术

    隐写术是将秘密消息隐藏在其它消息中，这样，真正存在的秘密被隐藏了。通常发送者写一篇无伤大雅的消息，然后在同一张纸中隐藏秘密消息。历史上的隐写方式有隐形墨水，用小针在选择的字符上刺小的针眼，在手写的字符之间留下细微差别，在打印字符上用铅笔作记号、除了几个字符外，大部分字符用格子盖起来等等。

    最近，人们在图象中隐藏秘密消息，用图象的每个字节的最不重要的比特代替消息比特。图象并没有怎么改变—大多数图象标准规定的颜色等级比人类眼睛能够觉察得到的要多得多——秘密消息却能够在接收端剥离出来。用这种方法可在1024ⅹ1024灰色刻度图片中存储64K字节的消息。能做此类把戏的公开程序已有好几种。

    Peter Wayner的模拟函数也能使消息隐匿，这类函数能修改消息，使它的统计外形与一些其它东西相似：如纽约时报的题录部分、莎士比亚的戏剧、Internet网上的新闻组[1584，1585]。这类隐写术愚弄不了普通人，但却可以愚弄那些为特定的消息而有目的地扫描Internet的大型计算机。

1.3 代替密码和换位密码

    在计算机出现前，密码学由基于字符的密码算法构成。不同的密码算法是字符之间互相代换或者是互相之间换位，好的密码算法是结合这两种方法，每次进行多次运算。

    现在事情变得复杂多了，但原理还是没变。重要的变化是算法对比特而不是对字母进行变换，实际上这只是字母表长度上的改变，从26个元素变为2个元素。大多数好的密码算法仍然是代替和换位的元素组合。

    代替密码

        代替密码就是明文中每一个字符被替换成密文中的另外一个字符。接收者对密文进行逆替换就恢复出明文来。

        在经典密码学中，有四种类型的代替密码¾¾

（1）简单代替密码，或单字母密码：就是明文的一个字符用相应的一个密文字符代替。报纸中的密报就是简单的代替密码。

（2）多名码代替密码：它与简单代替密码系统相似，唯一的不同是单个字符明文可以映射成密文的几个字符之一，例如A可能对应于5、13、25或56，“B”可能对应于7、19、31或42，等等。

（3）字母代替密码：字符块被成组加密，例如“ABA”可能对应于“RTQ”，ABB可能对应于“SLL”等。

（4）多表代替密码：由多个简单的代替密码构成，例如，可能有5个被使用的不同的简单代替密码，单独的一个字符用来改变明文的每个字符的位置。

    著名的凯撒密码就是一种简单的代替密码，它的每一个明文字符都由其右边第3个（模26）字符代替（A由D代替，B由E代替LLW由Z代替LX由A代替，Y由B代替，Z由C代替）。它实际上更简单，因为密文字符是明文字符的环移，并且不是任意置换。

    ROT13是建在UNIX系统上的简单的加密程序，它也是简单的代替密码。在这种密码中，A被N代替，B被O代替等等，每一个字母是环移13所对应的字母。

    用ROT13加密文件两遍便恢复出原始的文件：

P=ROT13（ROT13（P））

    ROT13并非为保密而设计的，它经常用在互联网Vsenet电子邮件中隐藏特定的内容，以避免泄露一个难题的解答等等。

    简单代替密码是很容易破译的，因为它没有把明文的不同字母的出现频率掩盖起来。在好的密码分析者重构明文之前，所有的密文都由25个英文字母组成[1434]，破译这类密码的算法可以在[578，587，1600，78，1475，1236，880]中找到。好的计算机破译算法见[703]。

    多名码代替密码早在1401年最早由Duchy Mantua公司使用，这些密码比简单代替密码更难破译，但仍不能掩盖明文语言的所有统计特性，用已知明文攻击，破译这种密码非常容易，唯密文攻击要难一些，但在计算机上只需几秒钟[710]。详情见[126]中的叙述。

    多字母代替密码是字母成组加密，普莱费尔在1854年发明了这种密码。在第一次世界大战中英国人就采用这种密码[794]。字母成对加密，它的密码分析在[587，1475，880]中讨论。希尔密码是多字母代替密码的另一个例子[732]。有时你会把Huffman编码用作密码，这是一种不安全的多字母代替密码。

    多表代替密码由Leon Battista在1568年发明[794]，在美国南北战争期间由联军使用。尽管他们容易破译[819，577，587，794]（特别是在计算机的帮助下），许多商用计算机保密产品都使用这种密码形式[1387，1390，1502]。（怎么破译这个加密方案的细节能够在[135，139]中找到，这个方案用在Word-Perfect中）。维吉尼亚密码（第一次在1586年发表）和博福特密码均是多表代替密码的例子。

    多表代替密码有多个单字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母等等。在所有的密钥用完后，密钥又再循环使用，若有20个单个字母密钥，那么每隔20个字母的明文都被同一密钥加密，这叫做密码的周期。在经典密码学中，密码周期越长越难破译，使用计算机就能够轻易破译具有很长周期的代替密码。

    滚动密钥密码（有时叫书本密码）是多表代替密码的另一个例子，就是用一个文本去加密另一个文本，即使这种密码的周期与文本一样长，它也是很容易被破译的[576，794]。

换位密码

    在换位密码中，明文的字母保持相同，但顺序被打乱了。在简单的纵行换位密码中，明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出（见图1.4），解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。

    对这些密码的分析在[587，1475]中讨论。由于密文字符与明文字符相同，对密文的频数分析将揭示出 每个字母和英语有相似的或然值。这给了密码分析者很好的线索，他就能够用各种技术去决定字母的准确顺序，以得到明文。密文通过二次换位密码极大地增强了安全性。甚至有更强的换位密码，但计算机几乎都能破译。

    在第一次世界大战中，德国人所用的ADFGVX密码就是一种换位密码与简单的代替密码的组合。在那个时代它是一个非常复杂的算法，但被法国密码分析家George Painvin所破 [794]。

    虽然许多现代密码也使用换位，但由于它对存储要求很大，有时还要求消息为某个特定的长度，因而比较麻烦。代替密码要常用得多。

转轮机

    在20年代，人们发明各种机械加密设备用来自动处理加密。大多数是基于转轮的概念，机械转轮用线连起来完成通常的密码代替。

    转轮机有一个键盘和一系列转轮，它是Vigenere 密码的一种实现。每个转轮是字母的任意组合，有26个位置，并且完成一种简单代替。例如：一个转轮可能被用线连起来以完成用“F”代替“A”，用“U”代替“B”，用“L”代替“C”等等，而且转轮的输出栓连接到相邻的输入栓。

    例如，在4个转轮的密码机中，第一个转轮可能用“F”代替“A”， 第二个转轮可能用“Y”代替“F”， 第三个转轮可能用“E”代替“Y”， 第四个转轮可能用“C”代替“E”，“C”应该是输出密文。那么当转轮移动后，下一次代替将不同了。

    为使机器更安全，可把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，n个转轮的机器的周期是26ⁿ。，为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。

    最著名的转轮装置是恩尼格马(Enigma)。恩尼格马在第二次世界大战期间由德国人使用。其基本原理由欧洲的Arthur Scherbius和Arvid Gerhard Damn发明，它由Arthur Scherbius在美国申请了专利[1383]，德国人为了战时使用，大大地加强了基本设计。

    恩尼格马有三个转轮，从五个转轮中选择。转轮机中有一块稍微改变明文序列的插板，有一个反射轮导致每个转轮对每一个明文字母操作两次。像恩尼格马那样复杂的密码，在第二次世界大战期间都被破译了。波兰密码小组最早破译了德国的恩尼格马，并告诉了英国人。德国人在战争进行过程中修改了他们的密码。英国人继续对新的方案进行分析，他们是如何破译的，请见[794，86，448，498，446，880，1315，1587，690]。有关怎么破译恩尼格马的两个传奇报道在[735，796]中叙述。

进一步的读物

    这不是一本经典密码学的书，因此不多讨论这些问题。计算机出现前有两本优秀的密码学著作是[587，1475]；[448]提出了一些密码机的现代密码分析方法。Dorothy Denning在[456]中讨论了许多密码，而[880]对这些密码作了很多复杂的数学分析。另一本更早的讨论模拟密码的著作见[99]，文献 [579]对这个学科做了很好的回顾。David Kahn的历史性密码学论著也是非常优秀的[794，795，796]。

1.4 简单异或

    异或在C语言中是“^”操作，或者用数学表达式⊕表示。它是对比特的标准操作：

                            0⊕0 = 0

                            0⊕1 = 1

                            1⊕0 = 1

                            1⊕1 = 0

    也要注意：

                            a⊕a = 0

                            a⊕b⊕b = a

    简单异或算法实际上并不复杂，因为它并不比维吉尼亚密码多什么东西。它之所以被包括在这本书中，是因为它在商业软件包中很流行，至少在MS-DOS和Macintosh世界中是这样[1502，1387]。不幸的是，如果一个软件保密程序宣称它有一个“专有”加密算法（该算法比DES更快），其优势在于是下述算法的一个变种。

/ * usage crypto Key input-file output-fife * /

void main (（int argc, char argvl ）)

* FILE * fi，* fo；

  int * cp；

  int  c；

  if（（cp = argv[1]）&& *cp != ‘\0’）{

  if（（fi=fopen（argv[2]，“rb”））！ =NULL）{

     if（（fo=fopen（argv[3]，“wb”））！=NULL）{

       While（（c=getc（fi）!=EOF）{

         if（! * cp）  cp=argv[1]；

         C ^=*（cp + +）；

             Putc（c，fo）；

       }

       fclose（fo）；

    }

    fclose（fi）；

    }

  }

}

    这是一个对称算法。明文用一个关键字作异或运算以产生密文。因为用同一值去异或两次就恢复出原来的值，所以加密和解密都严格采用同一程序。

P  ⊕  K = C

C  ⊕  K = P

    这种方法没有实际的保密性，这类加密易于破译，甚至没有计算机也能破译[587,1475]，用计算机只需花费几秒钟就可破译。

    假设明文是英文，而且假设密钥长度是一个任意小的字节数，下面是它的破译方法¾¾

    （1）用重合码计数法找出密钥长度[577]。用密文异或相对其本身的各种字节的位移，统计那些相等的字节数。如果移位是密钥长度的倍数，那么超过6%的字节将是相等的。如果不是，则只有0.4%以下的字节将是相等的（假设一随机密钥加密标准的ASCII文本；其他的明文将有不同的数值）。这叫做重合指数。指出密钥长度倍数的最小位移就是密钥的长度。

    （2）按那个长度移动密文，并且和自己异或：这样就消除了密钥，留下明文和移动了密钥长度的明文的异或。由于英语每字节有1.3比特的实际信息（见11.1节），有足够的多余度去测定唯一的解密。

    尽管如此，一些软件销售商在兜售这种游戏式算法时，还声称“几乎和DES一样保密”，这使人感到震惊。NSA最终允许美国的数字蜂窝电话产业界使用这个算法（有160比特的重复“密钥”）对话音保密。异或或许能防止你的小妹妹读你的文件，但却不能防止密码分析家在几分钟内破译它。