首页
论坛
课程
招聘
[原创]实战!关键词加密法破译
2009-6-8 16:41 7315

[原创]实战!关键词加密法破译

2009-6-8 16:41
7315
【文章标题】: 实战!关键词加密法破译
【文章作者】: DCracker
【作者声明】: 只是感兴趣,没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
  一、关键词加密法简介
      
      经典加密法主要有两种基本类型,一种是替换(substitution)加密法,每个密文字母被其他字母替换,如明文字母
  “d”可能被密文字母“c”替代。另一种是换位(transposition)加密法,明文中的每个字母没有改变,但它们在密文中
  的位置进行了重新排列,如单词“cipher”在密文中可能成了“hpirec”。将经典替换加密法再进行细分,又可分为两类:
  一种称为单码加密法,另一种称为多码加密法。而我要介绍的关键词加密法属于单码加密。
     
      关键词加密法按如下步骤进行:
  
  (1)选择一个关键词作为密钥,如果该关键词有重复的字母,去掉除第一次出现之外的所有相同字母。如,选择关键词为
  “success”,则使用“suce”。
  
  (2)将该关键词写在字母表的下方,并用字母表的其他字母按标准顺序填写余下的空间。
  
  例如,对于关键词“pacific”,则使用“pacif”并允许其从字母表的任意位置开始(比如从“k”开始),则替换表如下:
      
      a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
      
      q  r  s  t  u  v  w  x  y  z  p  a  c  i  f  b  d  e  g  h  j  k  l  m  n  o
  
  在这种情况下,加密明文Help I am lost:
  
      明文    h  e  l  p  i  a  m  l  o  s  t
  
      密文    x  u  a  b  y  q  c  a  f  g  h
  
  二、对关键词加密法的分析
  
    1.唯密文攻击
      
      下面是一个用关键词加密的一段英文信息:
  
      qihihpkgqigqukybmpqiyqukfigqubgqukktmexfimgbgobtf
      tymtbnqutqkskmkftbgpigkimfimkpqkjptuktniyrppukpkkfpqi
      hkthekqiorkppvutqvktmknibgohkyimkvkkskgdgivbquivatg
      vkkskmvbgbgqubphtqqekiyvbqphrqbvbeegiqobskrjuijkvk
      vbeecrpqutskqiqmxutmnkmqutgkskmqidkkjirmfkpptokpptyk
      tgnpirgn
  
      加密后的信息已经面目全非,初次破译可能觉得无从下手,但是稍微考虑一下我们现在已经知道的信息。
  
  (1)明文是用标准英语写成的;
  (2)所用加密法为关键词加密法;
  (3)每个明文字母已被唯一的密文字母替代。
  
      可能已经有读者闲我罗嗦了,没错,上面的第(3)条是破解该加密法的关键。语言的每个字母都有其自身的特性,每
  个字母在文章中出现的频率是相对固定的。因此,我们使用频率统计法来破译上面的密文。
  
      标准英语字母的常见频率表:    
  
  字母 A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
  
  次数 32  6   12  16  42  8   6   24  26  2   2   14  12  28  32  8   1   26  24  36  12  4   6   2   8   1
  
      由高到低的顺序为:ETAONIRSHDLUCMPFYWGBVJKQXZ
      
      现在来看一下密文的频率统计:
  
  字母 k   q   i   p   t   g   b   m   u   v   e   f   h   r   y   n   s   o   j   d   x   a   c   l   w   z
  
  次数 41  25  23  19  19  18  16  15  14  11  7   7   7   7   7   6   6   5   4   2   2   1   1   0   0   0
     
      我们现在可以进行一下尝试,将密文的字母按标准频率表来进行匹配:
  
  明文 A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
  
  密文 i   d   h   v   k   n   j   u   g   a   c   e   r   t   p   y   l   b   m   q   f   x   o   w   s   z
  
      密文变为:tacacoeitaitheprsotaptheua ……
  
      结果很令人失望,替换后的密文没有出现有意义的词组和句式。
  
      实际文本中的字母频率分布,与标准字母频率分布是有些变化的,不过这种偏差应该不大。因此,如果不考虑准确的频
  率匹配,而是考虑频率分组的话,可将标准英语字母分为4组:
  
      高   E  T  A  O  N  I  R  S  H
  
      中   D  L  U  C  M
  
      低   P  F  Y  W  G  B  V
  
      极少 J  K  Q  X  Z
  
      高频组与低频组之间可能会有分隔,不同分组的两个相邻字母的出现频率差在2%左右。最高频率的字母通常为“e”,
  但也可能是“t”或“a”。
  
      我们回头看看密文的频率分布情况, 我们注意到字母“u”和“v”的频率差较大(从14到11),因此高频字母很有可
  能由“k”、“q”、“i”、“p”、“t”、“g”、“b”、“m”和“u”表示。密文字母“k”的频率最大,据此猜测密文
  字母“k”可能表示的是明文字母“e”,“q”可能为“t”。为了使我们猜测得更加准确,还要考虑一下双联字母和三联字
  母。在标准英语文本中,“th”、“he”和“er”字母对出现的几率很高。
      
      密文中多次出现的双联字母和三联字母:
  
      双联字母:qu   qi   bg   sk   gq   kk   kp   uk   ut   vb
      出现次数: 9    7    6    6    5    5    5    5    5    5
  
      三联字母:ksk  gqu  kpp  quk  qut  skm  bee  bgo  bgq  fim
      出现次数:  4    4    3    3    3    3    2    2    2    2
  
      观察密文我们就会发现,与密文“k”、“q”有关的双联和三联字母为“qu”“qi”、“gq”、“gqu”、“uk”和
  “quk”,利用这些与“k”、“q”有关的信息和之前的假设,可得到这样一个结论:密文“qu”很可能是明文“th”,
  密文“uk”很有可能是明文“he”,而“quk”可能是“the”。
  
      密文高频组替换关系如下,括号中的对应关系还没有确定:
  
      明文 E  T(A  O  N  I  R  S)H
  
      密文 k  q(i  p  t  g  b  m)u
  
      在确定了一些可能的替换字母后,有几条途径进行下去。一是查看三联字母,另一种是用上面括号中的不同映射方式将
  密文进行替换,并在密文中确定可能的单词。括号中的不同映射方式一共有720(6!)种之多,也就是说密文高频组替换方
  式有720种,逐一尝试每种方式,最终肯定会得到一种比较合适的映射方式。
  
      借助辅助软件,多次尝试后,得到如下替换关系:
  
      明文 E  T  A  O  N  I  R  S  H
  
      密文 k  q  t  i  g  b  m  p  u
     
      对密文进行替换得到(未替换用“-”表示):
  
      密文1 qihihpkgqigqukybmpqiyqukfigqubgqukktmexfimgbgobtf
      
      明文1 to-o-sentonthe-irsto-the-onthintheear---ornin-ia-
  
      密文2 tymtbnqutqkskmkftbgpigkimfimkpqkjptuktniyrppukpkkfpqi
      
      明文2 a-rai-thate-ere-ainsoneor-oreste-sahea-o--sshesee-sto
  
      密文3 hkthekqiorkppvutqvktmknibgohkyimkvkkskgdgivbquivatg
      
      明文3 -ea--eto--ess-hat-eare-oin--e-ore-ee-en-no-itho--an
   
      密文4 vkkskmvbgbgqubphtqqekiyvbqphrqbvbeegiqobskrjuijkvk
      
      明文4 -ee-er-ininthis-att-eo--its--ti-i--not-i-e--ho-e-e
  
      密文5 vbeecrpqutskqiqmxutmnkmqutgkskmqidkkjirmfkpptokpptyk
      
      明文5 -i----stha-etotr-har-erthane-erto-ee-o-r-essa-essa-e
  
      密文6 tgnpirgn
      
      明文6 an-so-n-      
  
      可以在明文2中间部分看到“thate-ere-ains”,猜测应为“that e-e remains”,明文1中末尾处的“theear---orni
  n-ia-”,猜测应为“the early morning i am”,“oneor-oreste-sahea-o-”应为“one or more steps ahead of”。联
  系这几处可知,密文“e”为“l”,“x”为“y”,“f”为“m”,“j”为“p”,“n”为“d”及“y”应为“f”。
  
      最终经过反复查找单词,利用字母的特性,发现关键词为“thank you”,起始位置为字母“a”。
  
  明文 A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z
  
  密文 t   h   a   n   k   y   o   u   b   c   d   e   f   g   i   j   l   m   p   q   r   s   v   w   x   z  
  
      解密后的明文为:
  
      to bob sent on the first of the month in the early morning 
  
      i am afraid that eve remains one or more steps ahead of us 
  
      she seems to be able to guess what weare doing before we 
  
      even know it how can we ever win in this battle of wits 
  
      but i will not give up hope we will just have to try harder
  
      than ever to keep our messages safe and sound . 
  
  
    2.已知明文攻击
  
      上面信息是Alice发给Bob的,而Bob给Alice的回信如下:
  
      tmhjfpasaltmltdabfrstmbtdakmltdfltdahbtarlmmlemlmtoa
  
      hbrhfehbtarhjjavafsmljydukhlsdaphllmtpmltfluatmoasjapiy
  
      fhksurawawfjjbflchiaytdhtsdaphllmtorahimrhttdavary
  
      jahstwawfjjpmkaunwftdtdanarbaptpfndarsystakhlelavar
  
      dhvamrwmrryhomutdarhchflomo
   
      密文同样是用关键词加密法处理过的,但是已经更换关键词。破译这段密文同样可以用字母频率分析法来进行,但是现
  在的我们和第一次破译关键词加密法时,已经不一样了。我们已经破译了之前Alice发给Bob的信息,通信双方的信息格式应
  大体一致。据此,我们可以大胆猜测,上面的密文中,开头部分极有可能为“To Alice”。故可能的替换表关系为:
  
      明文 A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
  
      密文 h  -  p  -  a  -  -  -  f  -  -  j  -  -  m  -  -  -  -  t  -  -  -  -  -  - 
  
      根据关键词加密法替换字母表的性质可知,密文字母“a”右侧的字母序号应依次增大,并且不包含左侧字母“h”和
  “p”,“t”右侧字母与明文字母相同。故可确定替换表为:
   
      明文 A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
  
      密文 h  -  p  -  a  -  -  -  f  g  i  j  k  l  m  -  -  -  -  t  u  v  w  x  y  z 
  
      最后在用这个替换表,替换密文字母,查找单词,最终确定关键词为“hope”,起始位置为字母“a”。解密后的明文
  如下:
  
      to alice sent on the first of the month in the afternoon do not be
  
      afraid after all eveisonly human she cannot continue to be slecky
  
      i am sure we will fing a key that she cannot break or atthe very least
  
      we will come up with the perfect cipher system and never have or worry
  
      about her again 
                                                                bob
  
      
      即使只知道密文中一定包含某个词,而不知道这个词在密文中的具体位置,还是可以迅速将该密文破译。下面举最后一
  个例子。
  
      下面这段密文用关键词加密法处理过,还知道密文中一定包含“registration”这个词。
  
      rdeqeqftqrcntemgjkrurkouiejpyktrdcroubeqrocrekjskordu
  
      juxrquiuqruocrqmdkkheqmkiejbtlqkkjdcvuyktpumcpupwdemd
   
      mhcqquqyktwehhaurcgejbyuresqkhuriugjkwqkemcjqurtl
  
      iymhcqqqmdupthucjpwumcjrcgucrhucqrkjumhcqqrkburduo
  
      ptoejbrduqloejbhuriugjkwwdcreqbkejbkjcqqkkjcqlkqqeahu
  
      文字的字母和单词,都有其特殊的性质,我们来看看单词“registration”的结构组成:
  
                            r e g i s t r a t i o n
      
      忽略掉无重复的字母:  r * * i * t r * t i * * 
                            -     +   # -   # +
                            |_____|___|_|   | |
                                6 |___|_____|_| 
                                    6 |_____|
                                         3
      仔细观察密文第一行末尾处的“……oubeqrocrekj……”,这段密文的结构与单词“registration”的结构完全一致!
      
      密文 o  u  b  e  q  r  c  k  j
      
      明文 r  e  g  i  s  t  a  o  n
  
      接下来的工作就和上面一样了, 破译出的关键词为“campus”,起始字母位置为“a”,解密后的明文为:
  
      this is just a quick note to remind you that registration for 
  
      the next semester at school is coming up soon have you decaded
  
      which classes you will be taking yet if so let me know so i can
  
      setup my class schedule and we can take at least one class together
  
      during the spring let me know what is going on as soon as possible.
  
  
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                       2009年06月08日 16:35:32

[2023春季班]《安卓高级研修班(网课)》月薪两万班招生中~

收藏
点赞0
打赏
分享
最新回复 (4)
雪    币: 143
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
schlieffen 活跃值 1 2009-6-8 19:04
2
0
啊^_^,楼主参考了Richard Spillman的<<经典密码学与现代密码学>>,这本书在经典密码学方面讲得很详细.如果Alice和Bob不更换密钥的话,密文越多,频率分析越有效果.关键词加密法由于是一对一的字母对应,用程序的话可以考虑穷举,当然这没有任何破密的味道了.
雪    币: 1225
活跃值: 活跃值 (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
jackozoo 活跃值 14 2009-6-8 21:33
3
0
两种极端:
1. 关键词长度为0时, 则退化为Caesar Cipher. 穷举26-1次即可解密)
2. 关键词长度为26时, 则变为普通单表替换(substitution). (存在多达A26^26次可能, 不过增加了秘匙长度)

使用关键词(key word)加上位置(position)配合作为秘匙, 可以减小秘匙长度 , 不过有这样一个固定的缺点:
关键词后面的字母递增, 前面的字母递减 .  

当然了, LZ的这种方法还是属于单表替换的一种,这样始终逃不掉字频破译,  不过算是一种新思路~ 学习了 ~
雪    币: 143
活跃值: 活跃值 (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
schlieffen 活跃值 1 2009-6-8 23:45
4
0
第二种极端存在的可能应该是26!种。
雪    币: 1225
活跃值: 活跃值 (35)
能力值: (RANK:680 )
在线值:
发帖
回帖
粉丝
jackozoo 活跃值 14 2009-6-10 12:10
5
0
A26^26 就等于 26!     这个A是英文单词"排列"的首字母.
游客
登录 | 注册 方可回帖
返回