替换式密码
此条目需要补充更多来源。 (2016年9月25日) |
替换式密码，又名取代加密法[1]，是密码学中按规律将文字加密的一种方式[2]。替换式密码中可以用不同字母数为一单元，例如每一个或两个字母为一单元，然后再作加密。密文接收者解密时需用原加密方式解码才可取得原文本。由于拼音文字中字的组成为有限的字母，以英语为例只有26个字母，组成可能的单元数较少，因此使用替换式密码相对较为容易，而且亦可使用简单机械进行加密；相反，非拼音文字如中文则因单元数非常大难以使用一般加密方式，必需建立密码本，然后逐字替换。更何况某些非拼音文字中字字皆由不同大小的字根来组字，较难转换，因此使用替换式密码的示例比较少。
当以替换式密码与置换式密码（或称转位式密码或移转式密码[3]:1-15）相比较时，可以发现转位式密码只是改变明文中单元的位置，而单元本身没有转变；相反，替换式密码只是转换单元，但密文中单元的位置没有改变[4]:13。
替换式密码亦有许多不同类型。如果每一个字母为一单元（或称元素[2]）进行加密操作，就可以称之为“简易替换密码”（英语：simple substitution cipher）或“单表加密”（英语：monoalphabetic cipher）[4]:13，另又称为单字母替换加密；以数个字母为一单元则称为“多表加密”（英语：polyalphabetic cipher）[4]:13或“表格式加密”（英语：polygraphic）。单表加密只可在一个单元中使用同一种替换加密，而多表加密则可在一个单元使用不同的加密方式，明文单元映射到密文上可以有好几种可能性，反之亦然[4]:13。
简易替换密码
简易替换加密是一种以特定方式改变字母表上字母顺序，并以此顺序书写的加密方式。这样一张改变了字母次序的字母表即为‘替换表’。替换表可以以偏移或逆转（分别为凯撒密码和阿特巴希密码（英语：Atbash））或更复杂方式构造，此时称之为‘混合表’。传统上会先把一个关键词写在字母表最前面，再删去重复字母，这样就能得到一个混合表。
例子
使用混合表系统，关键字为“zebras”：
| 明文为 | ABCDEFGHIJKLMNOPQRSTUVWXYZ |
| 密文为 | ZEBRASCDFGHIJKLMNOPQTUVWXY |
明文为：
flee at once. we are discovered!
加密结果为：
SIAA ZQ LKBA. VA ZOA RFPBLUAOAR!
传统上，密文会省略标点符号和空格，同时会有一固定长度的单位，以避免传输错误和变相显示明文中单词的边界。这些单位被称为“组”（英语：groups）[4]:13，有时叫“组数”（英语：group count）（即组的数量），并使其作为一额外检查。通常都会使用五个字母为一组[4]:17[5]，然后使用电报传送消息：
SIAAZ QLKBA VAZOA RFPBL UAOAR
如果该段明文的长度不能被五整除，将需要在最后用“NULL”补齐[3]:1-7。这些空字符可以是任何字符，因为解密后可以看出是明显的废话（如ORANG EOOOO），所以接收器可以很容易地发现并将其丢弃。如若接收发现密文的长度不能被五整除，就可以得知传输出错，并要求重新发送。
简易替换密码有时不一定要替换至另一字母，例如在猪圈密码中，密文由格子的符号组成。例子如下：[6]
这些功能增加的安全性与以前其实相差不大，因为基本上所有奇怪的符号最后都会转换成A-Z字母。
有时销售人员会在他们的名单和目录中使用非常简单的加密法：用字母来代替数字。
| 本文（数字）： | 1234567890 |
| 加密字母： | MAKEPROFIT [7] |
例子：MAT代表120。
简易替换密码的安全性
简易替换密码的缺点是字母表中的最后几个字母（其中大多是低使用频率）往往留在最后。加强的办法是在加密后再做一次纵栏式移调，但很多时也没有这样做。
尽管加密用到的密钥可能性很大（26! ≈ 288.4，若88位元），但要破解单表加密却异常容易。只要提供有合理长度的密文（见下文），密码分析就能通过频率分布的分析推断最常见的单元的意义，即频率分析。这使破解者可用剔除法，把有个单元的意思解出来，见一个破解的例子。在某些情况下，可以从它们的字母的格局来破解，例如“attract”和“osseous”是英语中仅有的“ABBCADB”模式的“根”，即如遇见有简易替换密码的密文中出现“ABBCADB”，即可猜测其为“attract”或“osseous”。康乐及报纸拼图等包含着不少这种加密法。
按照英语的单一性距离，密文平均最少需要27.6个字母才能破解混合表简易替换密码[8]。而在正常情况下，假设遇到的是新排列方式，但通常都需要约50个字母（当中有些密文可以用得比较少）。然而，当密文有极平坦的频率分布，密文长度的需求可能越来越大。同时，加密者可以添加空字元来造成平坦的频率分布。
另外，有另一种方法来“伪造”频率分布，名为漏字文。顾名思义，这些文章会有意避免使用某个或某几个特定字母。如果漏掉的是E，那么若然继续以正常的频率分析（估计最高频率者为E）就不可能找出真正的明文。
谐音替换法
早期的加密中，为增加替换式密码应付频率分析攻击的强度，有时会采用“谐音”来改变明文字母频率。在这种加密算法中，明文字母可以映射到多个密文符号。通常情况下，频率最高的明文符号（如E）会比低使用频率的字母（如X）有更多的谐音符号，使频率分布更为平坦，让分析更困难。
但亦因此，只是字母之间互相替换就会造成不够分配，从而有了好几种不同的解决方法。其中最简单的方式可以算是用1-0共10个数字作为某些字母的替换。另一种方法则是将现有的字母分开成原字母配以简单的变化、大写、小写、上下倒转的字母、镜像文字（左右倒转）等。虽然更为艺术化，却不代表一定更安全，其中一些谐音替换法全部使用新发明的奇特符号来代表字母。（参见伏尼契手稿以及爱伦·坡所著的金甲虫）
一种有趣的变化名为命名密码法[3]:1-8。此加密法有许多不同的版本，之间的区别来自其前缀。而该前缀来自宣读来访贵宾称号的公职人员名字。这种密码结合一个小型密码本组成一个大型的谐音替换表。在此密码中，常用单词会按密码本加密，余下字母则按另一本密码本加密，两者符号最后在密文中混起来，以减低简易替换密码中被破解的风险[3]:1-8。路易十四所使用的密码是罗西诺尔家族创立的伟大密码，该密码直至法国王室废止后百年才被破解。
15世纪早期至18世纪后期，命名密码是外交文件及间谍最常使用的加密，然而其中大多数仍然使用加密性能较差的命名密码。虽然由十六世纪中叶开始政府情报机构的密码分析员就破解部分命名密码法，但使用者通常的反应仅仅
是加大谐音替换表。十八世纪后期，谐音替换系统开始消亡之时，一些命名密码已有高达5万个符号。
然而，并非所有命名密码法都已被破解。直到今天，仍然不时有新的命名密码被破解的新闻。
比尔密码是另一个谐音替换法的例子。这个故事指在1819年至1821年期间由一个加密文本来隐藏美国独立宣言中所述的宝藏。在这里，每个密文字元由一个数字替换。数字代表着独立宣言中第几个字的第一个字母。独立宣言中许多字的首字母都是一样的，而密文数字能是其中任何一个，例如正文中第二和第六个字都是“I”开头，即“I”既可以是2，又可以是6。而解读仅仅就是把密文中的数字（如代数X），放到独立宣言中查找（第X个字的首字母）。
斯塔尔则描述了另一个谐音替换密码[9][10]，其密码是第一次尝试在电脑的数据库上加密。在斯塔尔的方法中，无论是明文还是密文都是以二进制字符串存储，因此谐音的数量可以非常大，使得频率分析比平常更为困难。
多表替换加密
在1467年，多表替换密码由莱昂·巴蒂斯塔·阿尔伯蒂以圆碟的形式首次描述。约翰尼斯·特里特米乌斯所著的《隐写术》（古希腊语：Steganographia）中介绍了一种表格（见下；15世纪已完成但很久以后才出版[11]）。1563年，乔瓦尼·巴蒂斯塔·德拉波尔塔在《书写中的隐蔽字符》（古希腊语：De Furtivis Literarum Notis）描述了一个更复杂的混合字母版本[12]:139。
在一个多表替换密码中，会使用多个字母作为密码。为了加快加密或解密速度，所有的字母通常写在一张表格上，密码学上称作tableau。这种表格通常是26×26，因为这样才能放下全部26个英文字母。填充表格及选择下次使用的字母的方法，就是不同多字母替换密码之间的定义。多字母替换密码比单字母更难打破，因为其替换可能性多，密文要较长才可。
其中最著名的一种为吉奥万·巴蒂斯塔·贝拉索于1585年推出的维吉尼亚密码[4]:34。它于1863年之前一直未被破解。法国人称它作“不能破译的密码”（法语：le chiffre indéchiffrable）。（此密码曾被误以为由布莱斯·德·维吉尼亚所创[12]:On the Origin of a Species，所以才叫作维吉尼亚密码。）
维吉尼亚密码中，表格的第一行只需直接填上26个字母，然后以下每一行的字母都是向左偏移一格。（这叫作表格横移，数学上每一列同余26。）要用这种密码需要使用一个关键字来作为密钥。关键字每次用完就再次重复。假设关键字是“CAT”，明文的第一个字由“C”加密，第二个字由“A”加密，第三个则由“T”加密，然后再回到C加密，一直重复。然后按照右边的密码表加密，例如BALL用CAT作关键字时会加密至DAEN，可见即使是同一个“L”亦会加密至另一个字母。现实中，维吉尼亚密码的关键字非常长。
1863年，弗里德里希·卡西斯基少校发明了一种方法（在克里米亚战争前已由查尔斯·巴贝奇秘密并独立地发明[13][14]），使得可以计算维吉尼亚密码中关键字的长度[4]:37。这种方法需要较长的密文，因为其运作依靠找出常见的字（如THE）使用相同关键字（如ABC）的数量，因此，极短的密文难以用此办法找出。
因此，即使在今天，如果在表格中使用混合表加密，或关键字是随机的，维吉尼亚密码理论上亦难以破解。但由于实际上很难用到这些方法，维吉尼亚密码的使用越来越少。
其他著名的多字母替换加密包括：
表格式替换加密
在表格式替换密码中，明文不再单独替换某个字母，而是一次过替换较大的字母单元（通常为一对字母）。第一个优点是频率分布比单个字母时更平坦（虽然实际上并不平坦，因为在日常语言中，“TH”就远远比“XQ”常见）。其次，其产生的大量的符号，相应地需要更多的密文来进行高效的字母频率分析[来源请求]。
为了替换每“对”字母，将需要共676个符号（ ）。在之前说过的《书写中的隐蔽字符》一书中，德拉波尔塔提出了这样一个系统：用一个20 x 20的表格（意大利或拉丁文字中的20个字母。），其中填上400个特别的字形。然而，该系统实为不切实际，更有可能从来没有实际使用过[来源请求]。
最早的实用表格式替换密码是查尔斯·惠斯登爵士于1854年所创的波雷费密码。在此密码中，5×5的方格中填满了混合字母（两个字母，通常I和J并排，即I等于J）。明文中每两个字母为一单元，通常这个单元会在表上组成一个四方形（单元内容占其中两个角），然后取另外两角为密文。当单元内容在同一列或同一行时（即无法组成四方形），同列者密文为明文往右偏移一格；同行者密文为明文往下偏移一格。单元中两者为同字母者于该单之前添加X（或Q）（即其后全体往后偏移一格）。波雷费密码于第二次波耳战争开始直到第二次世界大战为止一直用于军事用途[4]:26。
在1901年，费利克斯·第利斯塔推出了其他一些实际可用的表格式替换加密，包括二分密码、四方密码及三分密码[来源请求]。
莱斯特·S·希尔于1929年发明了希尔密码，它是一种表格式替换加密。希尔密码可以使用线性代数来结合拥有非常多字母的单元。每个字母被视为二十六进制的数字：A = 0，B = 1，依此类推。（在某些变种中，会添加3个额外符号，将基底变成一个质数。）一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果同余26。注意用作加密的矩阵（即密匙）在 必须是可逆的，否则就不可能解码。只有矩阵的行列式和26互质，才是可逆的[来源请求]。
因为希尔密码完全建基于线性关系上，它会很容易受到己知明文攻击，因此，有时它会结合一些非线性步骤来减少被击破的机会[来源请求]。
机械替换加密
从第一次世界大战时期开始，直到电脑被广泛使用（某些政府约在20世纪50至60年代开始使；其他组织在十年或更后，1975年前则未有个人使用的纪录），多字母替换密码一直在机械上被广泛应用。几位发明家于同一时间有着类似的想法，1919年间已有四次关于旋转盘的专利申请。其中最重要并著名的可算是德意志国防军于1930年代所用的恩尼格玛密码机[15]。同时期盟军亦有其加密系统：美国的Sigaba及英国的Typex[来源请求]。
它们的相似之处在于它们都使用机械式旋转盘来加密。由于不止一个旋转盘的组成密文，如果每个字皆配一符号，符号用量将高于天文数字。然而，这些机器的早期版本极易被破解。信号情报服务处的威廉F.弗里德曼威廉·F·弗里德曼于早期就发现了赫本旋转器的漏洞；政府密码学校的第利温·诺克斯在第二次世界大战前就破解了恩尼格玛密码机中没有接线板的版本。布莱切利园的分析员在后期才能破解恩尼格玛密码机的军用版本，其灵感来自波兰数学家马里安·雷耶夫斯基[来源请求]。
SIGABA与Typex加密的讯息民间则至今没有被破解的消息[来源请求]。
一次性密码本
一次性密码本是一种颇特别的替换密码。它由约瑟夫·马宾于第一次世界大战后期建立[16][17]。克劳德·夏农约在第二次世界大战期间，在数学上证明它的保密性牢不可破[18]，其过程于1940年末首次出版。在常见的做法中，一次性密码本可以被称为一个单次替换密码。通常情况下，明文字母将以某种方式（通常为逻辑异或[2]）与关键字组合（而不是替换掉）[19]。
一次性密码本在大多数情况下都是不切实际或难以使用，因为它需要关键字跟明文一样（或更）长、“完全”随机、只能使用一次，更要保证除了发送者和接收者之外其它所有人都不知道。当这些条件有一项没有执行，甚至只是极其轻微的违反，一次性密码本便再也不是坚不可摧，甚至一触即溃。美国曾于第二次世界大战期间用非随机的一次性密码本加密讯息，再将其送往苏联。美国的密码学家于40年代开始就能破解极少数一次性密码本。（见维诺那计划[20]）
现代密码学中的替换加密
上述的替换式密码，尤其那些是只需使用铅笔和纸张的手动加密密码，都不再经常使用。然而，即使到了今天，替换加密的概念仍在进步。从一个够新奇的角度来看，现代位元导向式的分组密码（如资料加密标准及高阶加密标准）仍可视为使用大量二进制字母的替换加密。此外，分组密码通常包含较小的替换表，名为S-box[3]:3-14，其同时包含逻辑异或算法[3]:3-14。参见替换网络。
流行文化中的替换密码
- 夏洛克·福尔摩斯中的跳舞小人，其用跳舞小人替换英语，福尔摩斯最后根据分析字母频率来破解密码[21]。
- 最终幻想X中斯毕拉世界的语言实际上是一种替换密码，其发音方法却同为拉丁系统（例如你在英语中是you，然后加密至oui，再以法语来读出oui）[22]。
- 飞出个未来中外星人的语言的符号全由英文替换加密而成。观众相当快就破译出来，过程是在“Slurm”（外星人字）和“Drink”（英语）之间找到其密钥[23]。后来，生产商建立了第二套外星人语言，其使用了数学密码的更换和组合[24]。然而，此密码再一次遭破译，方法是将英语转为1至26，转换之后再加上前一个字母的编号，再同余26（亦即代表前字母为Z时后字母不会加密）[24]。这些加密讯息可以从整个系列中每一集和其随后推出的电影中看出。
参考文献
- ^ 傳統密碼學的基本原理. 正修科技大学资讯管理系. [2011-11-28]. （原始内容存档于2009-12-21） （中文（繁体））.
- ^ 2.0 2.1 2.2 密碼學原理與技術 (PDF). 资讯安全宣导专区稻江科技暨管理学院. [2011-11-28]. （原始内容存档 (PDF)于2020-09-20） （中文（繁体））.
- ^ 3.0 3.1 3.2 3.3 3.4 3.5 ICCL-资讯密码暨建构实验室, 王旭正、柯宏叡. 密碼學與網絡安全 [理论、实务与应用]. 博硕文化. 2011年 [2004年]. ISBN 957-527-690-6 （中文（繁体））.
- ^ 4.00 4.01 4.02 4.03 4.04 4.05 4.06 4.07 4.08 4.09 Salomma, Arto. 1.2. public-key cryptography. 香港: 国防工业出版社. [1990]. ISBN 7-118-01777-9 （中文（简体））.
- ^ Ron Hipschman. 秘密語言. [2011年11月13日]. （原始内容存档于2021年3月7日） （英语）.
- ^ Wrixon, Fred B. Codes, Ciphers, and other Cryptic & Clandestine Communication. Black Dog & Leventhal Publishers, Inc. 1998: 第182-183页. ISBN 1579120407 （英语）.
- ^ David Crawford, Mike Esterl. At Siemens, witnesses cite pattern of bribery. 华尔街日报. 2007-01-31 （英语）.
在慕尼黑的总部，前西门子经理Michael Kutschenreuter向检察官指控西门子广泛使用加密代码来处理贿款。他指西门子以"Make Profit"这10个字母代替1-2-3-4-5-6-7-8-9-0，比如"file this in the APP file"意味着贿赂为销售的2.55％。而西门子的发言人则表示：没有“Make Profit”的加密系统。
- ^ Josef Pieprzyk,Thomas Hardjono,Jennifer Seberry. Fundamentals of computer security. 2011年 [2003年] [2011-11-03]. ISBN 3-540-43101-2. （原始内容存档于2020-07-27） （英语）.
- ^ Stahl, Fred Alan. On Computational Securit. 2011年 [1974年].
- ^ Fred Alan Stahl. A homophonic cipher for computational cryptography (PDF). : 565 [1973] [2011-11-30]. （原始内容 (PDF)存档于2016-04-09） （英语）.
- ^ Indice de Libros Prohibidos （1877年） [Index of Prohibited Books of Pope Pius IX （1877年）]. Vatican. [2009年8月2日]. （原始内容存档于2016年5月9日） （西班牙语）.
- ^ 12.0 12.1 12.2 Kahn, David. The Codebreakers [The Story of Secret Writing]. Simon & Schuster. 2011年 [1967年]. ISBN 0-684-83130-9 （英语）.
- ^ Singh, Simon. 第2章：維吉尼亞密碼. The Code Book. 兰登书屋. 1999年: 63–78页. ISBN 0-385-49532-3 （英语）.
- ^ Franksen, O. I. Mr. Babbage's Secret [the Tale of a Cipher]. Prentice Hall. 2011年 [1985年]. ISBN 0-684-83130-9 （英语）.
- ^ Hakim, Joy. 美國歷史 [战争，和平]. 纽约: 牛津大学出版社. 1995. ISBN 0-19-509514-6 （英语）.
- ^ Miller, Frank. Telegraphic code to insure privacy and secrecy in the transmission of telegrams. C.M. Cornwell. 1882.
- ^ Steven M. Bellovin. Frank Miller: Inventor of the One-Time Pad. Department of Computer Science. Columbia University. [2011-11-29]. （原始内容存档于2021-03-01） （英语）.
- ^ Shannon, Claude. Communication Theory of Secrecy Systems. Bell System Technical Journal. 1949年, 28 (4): 656–715页 （英语）.
- ^ Stream Ciphers (PDF). 圣荷西州立大学. [2011-11-29]. （原始内容存档 (PDF)于2020-09-24） （英语）.
- ^ The Translations and KGB Cryptographic Systems (PDF). The Venona Story (Fort Meade, Maryland: 美国国家安全局). 2004年1月15日: 26–27 (28–29th of 63 in PDF) [2009年5月3日]. （原始内容 (PDF)存档于2009年5月10日） （英语）.
...KGBs cryptographic material manufacturing center in the Soviet Union apparently reused some of the pages from one-time pads. This provided Arlington Hall with an opening.
- ^ Sir Arthur Ignatius Conan Doyle. The Adventure of the Dancing Men. The Return of Sherlock Holmes. 英国: George Newnes. [1903] [2016-05] （英语）.
- ^ Final Fantasy X: Al Bhed Language Guide. Lynn Brown. A.K.A. enigmaopoeia. [2011-11-30]. （原始内容存档于2017-03-24） （英语）.
- ^ Omniglot. [2008-06-03]. （原始内容存档于2012-09-06） （英语）.
- ^ 24.0 24.1 The Day the Earth Stood Stupid. Futurama. Audio Commentary 11 记录于 （英语）.
- 书籍
- Yardley, Herbert. The American Black Chamber. Bobbs-Merrill, 1931.
外部链接
- CrypTool （页面存档备份，存于互联网档案馆） 网上学习工具-建立并破解替换式密码。
- 破解使用了单字母替换加密的工具 （页面存档备份，存于互联网档案馆）
- SCB Cipher Solver （页面存档备份，存于互联网档案馆） 单字母替换加密破解工具
- Substitution cipher implementation with Caesar and Atbash ciphers （页面存档备份，存于互联网档案馆）（Java）
- Online simple substitution implementation（Flash）
- MAKEPROFIT加密（把明文放在URL，网页显示结果）
- 单字母替换密码 （页面存档备份，存于互联网档案馆） 使用己知明文攻击来破解单字母替换密码
- http://cryptoclub.math.uic.edu/substitutioncipher/sub2.htm （页面存档备份，存于互联网档案馆）