胡杨林社区-常大风-个人文章

科普——密码学

常大风
2007-11-11 15:18   收藏:0 回复:2 点击:6845

    如何把机密的信息写成一种别人看不懂、自己却能看懂的形式呢?密写,也就是把文本加密的方法广泛应用在战争、银行、商业、情报等领域;在日常生活中也是有用的。比如,你想在日记中记录一件很重要的事情;或者,你和你的情人互传纸条(现在的学生有手机,已经不用这种古老的传讯手段了;但是特定场合,也许还会用得到,谁知道呢?);或者,你想在一个公共信息栏给特定的人传递信息;或者,你是一个记性不太好的人,你想在某处写下你的银行密码而又不被人窃取......在这些场合下,你会发现密码学相当有用。
  给文本加密的方法有很多。日常手工加密,大多数方法在拥有强大计算机的专业人士手里不堪一击;不过也有少数能够经受考验,这些方法如果不是优秀的破译团队,就很难破解。况且你也不太可能碰到国家安全局劳师动众来破译你的日记的情况。所以这些简单的加密方法可以认为是很安全的,只要你的密码不泄露。下面介绍几种简单实用的加密方法,并分别对其安全性和方便程度作出评估。这几种方法都是对于英文文本进行加密的,不过也可以用于汉语拼音文本,只是稍为麻烦一些。
  首先介绍两项基本原则。
  1.在密码学中,通常把英文26个字母从0到25编号,并经常用这些数字代替字母:0-A,1-B,2-C,3-D,4-E,5-F,6-G,7-H,8-I,9-J,10-K,11-L,12-M,13-N,14-O,15-P,16-Q,17-R,18-S,19-T,20-U,21-V,22-W,23-X,24-Y,25-Z。这里从零开始编号是有用意的,因为这样可以进行一些模运算,见下文。
  2.加密文本的时候,单词之间的空格要挤掉,也就是说不算空格。
  
  
  1.简单移位系统(推荐星级:*)。
  设定1-25之间的任何数字作为密码。例如,用3作密码。那么,在你写的密文中,把原文(明文)的每个字母在字母序里向后移动3位,就变成密文(暗文)。这样,加密I love you: I向后移三位变为L, l-o, o-r, v-y, e-h, y-b(注意这里,y往后移两位就超出z了,于是把a放在z的后面继续),o-r, u-x。于是密文变成:loryhbrx。注意密文最好不要留空格,也不要保留大小写,因为这样会增加被破解的危险。
  解密的时候,只要记住密码3,把密文每个字母往前移3位就可以了。
  评价:这种方法安全性很低,但是使用方便。某些场合不妨用之。在我介绍的几种方法之中,这种方法安全性最低。下面几种方法就相对安全一些,如果你周围的人对密码学都一无所知,那么都可以放心使用。
  
  
  2.Caesar系统(推荐星级:***)。
  因罗马时代的发明人Julius Caesar得名。传说被恺撒大帝使用过。
  Caesar系统的密码是自己选的一个单词。例如,选mountain,写出以下的字母序列:mountaibcdefghjklpqrstvwxyz。看出来了吗?就是在正常字母序列中抽掉你的密码mountain。由于mountain中有两个n,把第二个去掉。 然后,把正常字母序列写在这个序列下面:
  Mountaibcdefghjklpqrsvwxyz.......密文字母序
  Abcdefghijklmnopqrstuvwxyz.......明文字母序
  在加密的时候,用上面那个序列里的字母代替原文中的字母写成密文。例如,m代替a,o代替b。解密时方向相反。所以,加密heishere的结果是:btcqbkpt。
  如果你的文本中有数字,那么不妨写一个36字符的序列,并把数字加在你的密码中。
  评价:这种方法比简单移位系统安全,可以在你的日记中使用。但是,如果加密的文字有(大约)400字符以上,那么攻击者手工花费1天时间即可破解,因为英文和其它语言中每个字母都有一定的使用频率,破解者根据这些频率就可以破译。
  
  
  3.仿射系统(推荐星级:*)。
  和上面的两种方法一样,都是把一个字母用另一个字母代替。这样的方法叫做单字母替换,也称单表系统。如果象下面的Playfair系统那样,两个字母两个字母地替换,就称为双字母系统。以此类推,有三字母系统,多字母系统。替换单元越长,安全性越高。
  首先,设定两个密码a,b。a是1-25之间的整数,并且要和26互素,也就是说没有大于1的公约数。A有以下12种选择:1,3,5,7,9,11,15,17,19,21,23,25。B可以是0-25之间的任何整数,一共有26种选择。这样一来,仿射系统的密码a,b的组合就一共有12*26=312种。但是,a=1的时候b不能选0。所以实际的选法一共有311种。下面大家将会看到为什么。这种方法的使用需要模运算。如果你不懂模运算,没有关系,我会解释。很简单。
  参看上面的英文字母编号。从a=0开始,把每一个字母用另一个字母代替。如果你选密码a=3,b=1,那么加密的时候,把原字母的数字代号作以下运算:数字代号*a+b。这样,你会得到另一个数字。把它对26做模运算,也就是说,把它除以26所得的余数作为计算结果。例如,你要用a=3,b=1加密字母t。由于t的数字代号是19(参见上文),所以:t*a+b=19*3+1=58。58对26求余得6。而数字代号为6的字母是g,所以,在密文中,就用g代替t。
  如果设定密码 a=3,b=1,加密序列如下:
  原文:a b c d e f....x..y z(省略的部分大家自己算吧!)
  代号:0 1 2 3 4 5....23.24 25
  密文:1 4 7 10 13 16...18.21.24
  就是:b e h k n q s v y
  现在来看一下为什么a不能和26有大于1的公约数。如果设定密码 a=2,b=1,加密序列如下:
  原文:a b c d e f g h I j k....x..y z
  代号:0 1 2 3 4 5 6 7 8 9 10...23.24 25
  密文:1 3 5 7 9 11 13 15 17 19 21...21.23.25
  就是:b d f h j l n p r t v....v..y..z
  可以看到,对于不同的原文字母k,x,却使用相同的字母v代替。这给阅读带来混淆。
  阅读:如果你知道密码,就可以写出上面的替换关系,把密文翻译成明文。还有一种线性代数解密的方法,这里请容我省略。
  评价:可以看到,仿射系统当a=1的时候其实就是简单移位系统。所以它包括了简单移位系统,并且写法(311种)比简单移位系统(26)多,所以安全性也高于后者。但是,比起可以任意选择单词作为密码的Caesar系统来,它的写法又太少了。所以,它又没有Caesar安全。不过,仿射系统不失为一种有趣、方便的密码系统,在比较短的文本加密中可以放心使用。
  
  以上的单表系统,在善于运用计算机、又知道你用的是单字母替换方法、并且掌握英文字母使用频率的统计资料的破译者面前是不太安全的。下面的双表、多表系统就安全得多。虽然也有双字母、三字母的使用频率统计,但是要破译密文,理论上文本必须达到上万个(双字母)、数十万个字符。
  
  4.Playfair系统(推荐星级:****)。
  曾经被英国军队在第一次世界大战中使用过。
  例如,你和战友在战争开始约定了用这种方法加密,并且密码是fight4。现在你们分散在两地,你要传递35 enemies are coming这条信息给战友。
  首先,把英文26个字母和0-9这10个数字写成一个6*6的正方形:
  F I G H T 4
  A B C D E J
  K L M N O P
  Q R S U V W
  X Y Z 0 1 2
  3 5 6 7 8 9
  看出来了吗?以密码fight4开头,其余的按照音序和字母序写下来就可以了。现在把要加密的信息去掉空格,每两个字符写成一组:35 EN EM IE SA RE CO MI NG。
  对于每两个字母,Playfair有其加密规则。如果两个字符在上面的正方形中不在同一行或同一列中,例如EN,那么由于EM-CO组成一个小矩形,就用C0代替EM。注意顺序,不要写成OC。同样的道理,EN用DO代替,IE-TB,SA-QC,RE-VB,CO-EM,MI-LG,NG-MH。对于两个字符在同一行或一列的情况,把它们分别往右或往下移一个位置就可以了。例如,35变成56(3往右移位成5,5往右移位成6)。再如:KN-LO,MZ-S6,89-93(注意这里,8移位成9,9往右移位就出了正方形,这时,在这一行从头开始)。这样一来,你要写给战友的信息就变成56 DO CO TB QC VB EM LG MH了。谁能看懂?相当安全。同时,你的战友只要记住这种方法和你们约定的密码fight4,就可以解读了。你写日记、传纸条的时候也一样,但是要记住密码。
  说明:1、最开始的Playfair不包含数字,把英文26个字母中很少使用的k省掉,写成5*5的正方形。我略加变通,写成6*6。2、Playfair只能加密长度为偶数的文本,因为字符都是成对加密的。不过,你可以省掉最后一个字符,或者加上一个无关紧要的字符呀!
  评价:Playfair是相当安全的。只要你不泄露密码。记得写完后,把草稿纸销毁。
  
  
  5.Hill系统(推荐星级:**)。
  这种方法需要线性代数知识,使用起来不方便,并且如果手工加密,由于计算量大,限于3*3以下的矩阵,安全性还比不上下面的Vigenere。我个人认为,这种方法的实用性比不上Playfair。不叙述了。
  
  
  6.Vigenere(推荐星级:*****)。
  由法国人Blaise de Vigenere和一位海军司令(哪个国家的我记不得了)Francis Beaufort分别独立发明。这种方法是很安全的,如果你使用得当,即使你周围有顶级的密码学家,也不容易破译。
  Vigenere的密码也是一个使用者任选的单词。例如,选择swordsman作为密码。它的长度是9个字符。于是我们写出一个26*10的方阵来:
  A S W O R D S M A N
  B T X P S E T N B O
  C U Y Q T F U O C P
  D V Z R U G V P D Q
  E W A S V H W Q E R
  F X B T W I X R F S
  G Y C U X J Y S G T
  H Z D V Y K Z T H U
  I A E W Z L A U I V
  J B F X A M B V J W
  K C G Y B N C W K X
  L D H Z C O D X L Y
  M E I A D P E Y M Z
  N F J B E Q F Z N A
  O G K C F R G A O B
  P H L D G S H B P C
  Q I M E H T I C Q D
  R J N F I U J D R E
  S K O G J V K E S F
  T L P H K W L F T G
  U M Q I L X M G U H
  V N R J M Y N H V I
  W O S K N Z O I W J
  X P T L O A P J X K
  Y Q U M P B Q K Y L
  Z R V N Q C R L Z M
  我们用密码为swordsman的这个方阵加密heisgoingtoflee...。把密码词和明文相对:
  swordsman swords...
  heisgoing toflee....
  在加密的时候,把明文按照密码词的长度(这里是9个字符)分成若干段,分别和密码词相对。然后,逐个字母加密。在上面的方阵第一行中找到密码词的第一个字母s,第一列中找到明文的相应字母h它们相交的地方是第2列第8行的字母z。这就是密文的第一个字母。接下来,w和e相交于a,o和i相交于w,...于是,密码词、明文、密文变成下面的对应关系:
  swordsman swords...
  heisgoing toflee....
  zawjjgunt...lktchw...
  解密的时候,只要在第一行中找到密码词的相应字母,在它所在的那一列中找到相应的暗文字母,那么,暗文字母横过去的最左边,就是你要的明文。请记住,不论是加密还是解密,都先在第一行中找密码词的字母。
  大家会认为上面的方法很烦琐,不论对于加密还是解读都是如此。确实,如果每次都要写方阵的话很费时间。不过,还有不用方阵、甚至连草稿都不需要打的加密、解密方法。为此你必须记住每个字母的数字代号。在上面的方阵中,s和w相交得到z,其实是s和w的数字代号相加,得到z的数字代号25。以此类推,w和e相加得到a,o+i=w,等等,见下表。当然,如果加和的结果大于25,就对26求余数。一定要记住,求余是密码学中最常用的运算之一。
  这样一来,就不用写出庞大的方阵了。加密过程轻松快捷。解密的时候也同样方便,只要用暗文字母的数字代号减去密码词相应字母的数字代号,就得到相应明文字母的数字代号。如果差是一个负数,例如下面第2列a(0)-e(4)=-4,怎么办呢?没关系,-4对26求正余数,或者-4加上26,就等于22(w)了。
  密码 s w o r d s m a n
   18 22 14 17 3 18 12 0 13
  明文 h e i s g o i n g
   7 4 8 18 6 14 8 13 6
  暗文 z a w j j g u n t
   25 26=0 22 35=9 9 32=6 20 13 19
  评价:如果你记住了每个字母的数字代号,Vigenere方法对于你来说,就是简单实用、安全系数很高的加密方法了。由于你可以选取很长的密码词,大大增加了攻击者破解的难度。况且如果你熟练,还免去了草稿,让那些专门在垃圾箱里动脑筋的间谍没有可乘之机。在安全性上,Playfair和Vigenere是不可同日而语的。如果说你可以在日记、秘密信函中放心地使用Playfair的话,那么,当你使用Vigenere的时候,请抱着“肆无忌惮“的心理吧!但记住,密码词越长越好。
  
  附注
  1.现代的密码学
  除了上面所说的这些,在计算机时代之前还有许多著名的密写系统,例如二战中德军使用的ENIGMA,美军使用的SIGABA,日军使用的RED和PURPLE,等等。其中当然是ENIGMA最出名,因为它被英国破译了!我不知道ENIGMA加密的方法,但是,它从明文到密文肯定要经过很多次复杂的运算(这些运算不是用手工,而是用密码机进行的),不光是象Playfair、Vigenere那样写方阵、加加减减就行了。因此,这些二战中使用的密码系统一定要比一战中的安全。不过,由于原理都是字母替换,破解的时候都是频率统计,可能也安全不到哪里去。呵呵,我是外行。
  计算机发明之后,更复杂的密码系统被开发出来,这些系统手工操作几乎是不可行的,不论是加密还是解密。例如,DES(美国数据加密标准,IBM在1975年发明的)、背包系统、公钥系统,等等。其中,使用公钥系统时,双方不需要事先认识,或者事先约定加密密码,而是各自有各自的密码。但是,这样怎么能读懂对方的密文呢?第三者为什么读不懂呢?其实公钥系统相当于把明文加密两次,加、解密的时候两个密码词的使用顺序可以颠倒也得到相同的结果。打个比方,A通过邮局寄一口箱子给B,上面上了他的锁。B收到箱子之后自然打不开。于是,B在箱子上又加了一道锁,然后给A寄回来。箱子上现在有两把锁。A收到箱子后把自己的那把锁打开,再次把箱子寄给B。现在,箱子上只有B的锁了。这样,B收到箱子后就可以打开。而作为有间谍嫌疑的邮局C,始终无法打开箱子!真是聪明!公钥系统的好处,除了可以不用事先约定密码词之外,作为使用的任一方,都可以随时更换密码而不影响交流。不重复使用密码是公钥系统增加安全性的秘诀。
  但是,尽管有这么多“强壮“(安全)的密写系统,我们还是可以放心地使用我们古老的手工加密。为什么呢?首先,加密方法虽然随着计算机、数学的发展大大进步,破解的手段却没有成比例地进步。我们只要在Vigenere中增加密钥词的长度,就可以增强安全性。此外,加密方法是人发明的,我们自己也可以发明出许多密写系统,仅供我们自己使用。如果我们不把这些希奇古怪的法子告诉密码学家,他们很多时候也是一筹莫展的。要知道,现在市面上流行的许多加密系统,他们的加密方法都是公布的,只有密码词,使用者各自保密。在知道加密方法的前提下(例如,我知道你用Playfair方法加密)去破解,就要相对容易一些。而我们是不必公布自己希奇古怪的方法的。如果我们想保护自己的top secret,我们可以想出很多方法。市面上的密码系统为什么公布他们的加密方法呢?我想,首先是为了专利。很多加密系统是作为商业软件出售的。另外,他们要建立一套标准流程,大家都用同一种方法,个人管好密码就行。标准流程的建立有利于进一步的开发。
  总之,在可以忽略国家安全局对你产生兴趣的前提下,放心地在日记、纸条,甚至公函中使用古老的密码系统吧!
  同时,请开动脑筋,开发自己喜欢的密写系统。
  
  2.上面6种密写系统的总结
  密写系统 便捷性 安全性 推荐程度
  简单移位 ***** * *
  Caesar **** ** ***
  仿射 ** * *
  Hill * *** **
  Playfair **** *** ****
  Vigenere **** ***** *****
  
  
原创[别推荐]  林友收藏  

  
【点击回复或查看回帖】

传统或网络媒体转载请与作者联系,并注明转自【胡杨林】及作者名,否则即为侵权。

Copyright © 2008 MY510.COM 版权所有