首页 >> 其他 >> 计算机科学 >> 文章

凯撒的加密术Comments>>

发表于 2010-12-09 07:44 | Tags 标签:,


送上开场诗一首:我用相思作玉杯,真情当酒意相随,爱心已醉何时醒,你似蝴蝶梦里飞。

你可以把这首诗发给你女友,聪明的她一定能看出这是首藏头诗,从而明白你的心意。其实,藏头诗就是一种加密术,它通过坐标变换的方式隐藏了秘密,这个例子虽然很简单,但它反映出了加密术的本质--变换坐标系。

加密术最早应用于古代战争,当时是靠士兵随身携带的信件来传递情报,但总是免不了被敌方俘虏,从而使情报落入敌手,这对作战部队而言可是生死悠关的大事。传说当时的凯撒大帝有一个能加密的办法,就在写命令前做一个对应表,明码:A B C D E F....W X Y Z,密码:D E F G H I....Z A B C,如果他想写BABY,就用EDEB来表示。

当大将收到了EDEB这个密码后,向前推3个字母,就得到了明文。这个对应表的移位数是3,当然别的数也可以,作战前由凯撒定好移位数后通知大将们,战时就可以进行保密通信了。这种加密方式其实就是把坐标系横移了3格。但是,这种简单的加密方法也很容易被敌方猜到,敌人从1到25推25次,得到25组新编码,必有一种编码是真实的情报内容,把这组编码区别出来非常容易,因为其它24组都是毫无意义的字母组合,只有这一组是有意义的句子,找个识字的人就可以看得出来。

既然这种加密手段并不安全,那凯撒该怎么办呢?有个聪明人给他出了个主意,对应表不按字母顺序写,搞个乱序的。例如A对Q,B对F,随意配对,只要保证26个明密码一一对应没有重复就行了。每次出征前,凯撒就会搞个非常杂乱的明密码对应表,然后发给大将。这招很不错,敌人即使截获了密文,由于不知道明密码对应表,也很难搞明白,这其实也是坐标系统的一种变换,这种方法被后人称为“单表系统”。

这种乱序的加密术比顺序的安全多了,但它还是有一个明显的漏洞。以英文为例,一篇文档里每个字母的出现次数是不同的,例如E出现的次数最多,甚至可以搞出个频次表来,如果一份密文中R出现的次数最多,那这个R会不会就是E呢?这个猜想很合理,即使代表的不是E,那它代表的也应是明文中出现次数较多的字母。按照这种思路试试吧,卖糕的,密码解开了。

现在又轮到加密方纠结了,他们想,破解方是在拿明密文中字母出现的频次做文章,如果我们能把频次的区别消除掉,他们不就没办法了吗?道理虽然很好,但怎样才能消除这种频次的差别呢,毕竟明文中字母的频次就是不一样,这本身没法改变啊。

功夫不负有心人,有一天加密方终于找到了解决问题的关键,这个关键就是“多表”,每个明文都对应多个密文,例如图上的A分别对应着XGV,这三个密文的选择取决于明文的位置,A在第一位时选X,第二位时选G,第三位时选V。将整个一段明话按三位一段进行分组后就可以加密了。这个例子是三维的,维数还可以更多,那就更难破译了。这种多表系统非常有效,但其实还是有统计规律可循的,只是短短一段密文是不足以找到规律的。

这种对应规律相对固定的多表系统,还是给破解带来了突破口。随着技术的发展,人们开始尝试用机械改良这种多表系统,通过引入更多的变化来增大破解的难度。二战期间德军有一种加密转轮机,四个轮子负责把输入的明码置乱成密码,其对应规律是动态变化的,使破译难度大大增加。有一个负责管理加密转轮机的德军军官汉斯.施密特,为了钱与盟军情报人员勾搭上了,他提供了该机的技术资料,得到了相当于现在1千万法郎的报酬,后来他害怕了想退出,但已经由不得他了,他先后与盟军情报人员接头34次,波兰顶级数学家里杰斯基等人在这些绝密情报的帮助下终于将该转轮机完全破解。

还是回到凯撒吧,他当然知道自己的加密术并不很安全,送情报的士兵被抓后受刑不过就会把密信交出来,如果防止传令兵被俘后泄露情报呢?有人又给他出了一招:把一批士兵的头发剃光,并用火烙铁在脑顶上烙上不同的印迹,并对哪个兵烙上什么样的疤做好记录,被烙的士兵一头雾水,不明白这是为什么。大战之前,凯撒召集大将,并要求他们牢记一组对应关系,梅花疤代表“马上率部向我驰援”,三角疤代表“固守阵地”等等。

战斗中凯撒被围困了,情况很危机,他拿来了记录本,把烙梅花疤的几个人都点了出来,命令他们沿不同的路线到大将处报到,“不用我们传个口信或带个情报吗?”这些人很不解,“不用,你们到大将处报个到就算完成了任务”凯撒说到。这些人出发了,有的人成功地找到了大将报到,大将二话不说,立即给他剃头查疤。也有的人被俘,严刑拷打也问不出情报,因为他的确不知道情报。距离剃头烙疤的时间已经很久了,士兵新长出的头发已经遮盖了烙疤,敌人也轻易察觉不到这个蹊跷。

加密后的密文即使摆在敌人面前,他们也搞不清楚其真实内容,但让他们知道了这是件隐藏着重要情报的密文,就会拼命破解,这总归不是好事。如果密文摆在他们面前,他们竟然毫无察觉,那当然更好了,这就是隐写术。凯撒给传令兵头上烙疤就是隐写术的鼻祖。谍报小说里经常会介绍到这样的场景,潜伏者用淀粉水写情报,晾干后再在上面写一封信作为掩护,收信者并不关注信的内容,而是在信纸上涂上一层碘,淀粉水情报就会变成蓝色显示出来了。这样的一封信,即使让特务机关拆开审查,只要不知道这个门道,那什么也查不出来。

很多加密术看起来非常巧妙,但随着计算机的诞生,这些被称为古典密码术的方法全部失效,因为它们根本抵挡不住计算机的穷举分析。现代密码学的思路跟古典密码术非常不同,它是先找出一个数学难题,然后把加密方法归结到这个难题,若解不出这个数学难题就破解不了他的密码。隐写术也逐渐脱离了物理和化学反应,而是与加密术结合了起来,把秘密隐藏在数据中,现代密码学更加引人入胜,且等以后慢慢道来。

0
为您推荐

51 Responses to “凯撒的加密术”

  1. QQending说道:

    不错不错~~写得很好!

  2. diesirae说道:

    之前有传说恐怖分子把信息写到jpeg里放在网上,应该也算隐写术吧……

    • SSL说道:

      JPEG?不好
      如果是在图形上加上信息,可以被PS出来
      如果是在编码上加上信息,一次压缩、转载、加水印等就挂了
      恐怖分子之间还是用公钥+私钥+一个内部CA比较好

    • SSL说道:

      JPEG?不好
      如果是在图形上加上信息,可以被PS出来
      如果是在编码上加上信息,一次压缩、转载、加水印等就挂了
      恐怖分子之间还是用公钥加密+对称加密+一个内部CA比较好

  3. Alonesky说道:

    即使是现代的加密算法,也逃不过穷举法,只是解密的成本已经高于了本身信息的价值,是这样的吗??

    • 破布说道:

      是的.

      比如说现在广为应用的RSA算法,密钥如果有足够的长度,即便是使用最强的超级计算机昼夜不停运算来破解,也不一定能够在太阳寿命耗尽之前搞定.这个成本太高太高了,基本不会有人傻到这个程度的.

      这个世界上还没有能保证绝对安全的方法.因为加密的本质其实是更换了坐标系,就算是用凑的,也有极低极低的概率刚好凑对对应的编码,这个防不住啊.量子加密我不清楚是不是也在此列.

      • 拉玛西亚梦说道:

        破解密码最好的手段还是使用特工。

  4. 兔子说道:

    加密与破密的对决巅峰是二战,当时,英国的13号房(好像是这个名字)里面全是图灵这种godlike级别的人,破掉了德国的恩格玛机。对密码学有兴趣推荐看《密码故事——人类智力的另类较量》。

    • zhangzhang说道:

      是呀,那个转轮加密机故事远远比博文精彩多了,你从中可以领略到人类的智慧之美,无论做机器的一方还是解密的一方都是天才与天才之间的对决,可惜博文略过那一段故事了。计算机专业的路过:-)。

      • MarsV说道:

        与其路过,不如写出来与众鼠友分享 :)

        • 多多说道:

          那本书在学校图书馆专门借来看过,很有意思,整个经过很精彩,真比大片还精彩

  5. Mine说道:

    呀,期待后续~

  6. biohu说道:

    大赞!!
    身为极客,怎能不知道加密解密。。。

  7. yutouguai说道:

    有趣有趣~学习学习~以后写信都用密码~

  8. dindog说道:

    有本书叫:
    经典密码学与现代密码学
    比这篇文章有趣且更深入。后面会介绍AES这类现代加密原理,还有谜题

  9. 埃痕说道:

    有趣…特别是隐写术…

  10. 喵酱说道:

    好玩,对图灵感兴趣~~~~

  11. firstrose说道:

    最近看了《密码传奇》,LZ的文就是缩略版……

  12. 说道:

    下次要讲RSA了吧~_~

  13. Yu说道:

    对科学不了解,喜欢看小品《山西家信》

  14. 栖枫渡说道:

    主帖超精彩,跟帖提供了很好的书!

  15. Metaverse说道:

    计算机穷举……暴力破解V5。。。

    • Y说道:

      其实也是有穷举不了的加密方式的,只要密钥比明文还长(即一次一密)

      • 拉玛西亚梦说道:

        加密成本无法接受那加密就不是们应用科学了

  16. c2blog说道:

    强文留名

  17. [...]  ’出自:http://songshuhui.net/archives/46557 [...]

  18. starryguo说道:

    用火烙铁在脑顶上烙上不同的印迹,太狠了!

  19. 高级诈骗师说道:

    据说现在有很高端的量子加密。不晓得研究到什么地步了。
    是从上面有人提到的《密码故事》中看来的。我当年还做了后面的题目呢,妄图拿到那个奖金。也不知道那奖金有没有人得到。

  20. 陈泽华说道:

    早就仰慕松鼠很久了…………初来炸到

    赶紧留心足迹

  21. 白左说道:

    啧啧,密码学呀
    作者ID注目……
    不过目前除了利用数学难题加密的信息,只要是拥有足够信息,理论上没有不能破译的密码了

    倒是觉得非密码的密码才是最大的难题:比奴鸟手稿什么的……信息太少了……

    • Y说道:

      一次一密就是理论上破解不了的加密方式
      另外所有的密码问题在密码学里面都可以被抽象成C=f(M,key)的形式

  22. 空间端点说道:

    《福尔摩斯探案集》的《跳舞人形》中,福尔摩斯用频次法破解了用人形一一代替字母的密码,密文的数量不大,用的时间并不长,可见这种方法确实太低级了。

  23. javajz说道:

    为什么一说加密就说外国的加密技术呢?难道中国古代的战争就没有加密的需要吗?建议发据一下这方面的内容.

  24. jetyoung说道:

    期待后面的作品

  25. 秒针说道:

    路过……表示对这很感兴趣

  26. 糖果米菲说道:

    刚刚考完密码学基础的课的路过...

  27. 风中的石头说道:

    看了丹布朗的《数字城堡》么?正好虚拟了一个万能解密机,一招破万招

  28. leaphyme说道:

    这些加密方式都没什么用处了……现代加密已经越来越倾向于不可破,不是说真的无法穷举,只是穷举它需要的时间已经不是人类寿命可以承受。

  29. 浅蓝色说道:

    其实最不安全的因素不是密码的加密程度,而是人。与其耗时费力的破解密码,不如想想怎么搞定设定密码的人。

  30. leilei说道:

    有种攻击方法就叫“收买攻击”,针对密码的使用者........

  31. TooWhite说道:

    老师写的很好!通俗易懂。

  32. 三生淘宝宝说道:

    我看出三点:

    1、今天的保密方式趋于统一,因为越来越多的信息被储存在电子载体中,不外乎硬件软件。古代是五花八门,就像淀粉和碘,古人所掌握的元素和方式方法或许比我们想象中的还要多。同样在欧洲,拜占庭的喷火船不是失传了吗。

    2、凡是“古代的故事”都是有“误差”的。

    3、大家关注密码本身,其实破解密码的条件也很重要,好比停电、好比找不到碘。

  33. momo-gnu说道:

    凯撒加密后来被维吉尼亚密码表取代了

  34. 有意思,不过如果现实生活中到处用加密,那社会就乱了,哈哈

  35. 成礼说道:

    确实有意思,是《暗算》

  36. Transfomers Games说道:

    历史晚上可以告别处理
    外展古希腊时帕潘德里欧的语言会使他特别到美国再见目标,承诺,并保持在欧洲,希腊。

  37. Data Recovery Guides说道:

    Hi, i believe that i saw you visited my site so i got here to return the favor?.I am trying to find issues to enhance my website!I guess its ok to make use of some of your ideas!!

  38. acid reflux advice说道:

    I cherished as much as you will receive carried out proper here. The cartoon is tasteful, your authored material stylish. nevertheless, you command get got an impatience over that you want be turning in the following. sick definitely come further before once more as exactly the same just about very frequently within case you shield this increase.

  39. Gurgaon Escorts Agency说道:

    Pretty nice post. I just stumbled upon your weblog and wanted to say that I have truly loved browsing your blog posts. In any case I will be subscribing on your feed and I hope you write again soon!

  40. sotpd说道:

    特工又不是神,还不是用那些方法。。。。方法就在那,其实只是有些你不知道而已。

  41. Marisa Hoving说道:

    Hi, Installed SiyahKernel S3-v1.7rc1 on Samsung Galaxy S3 stock rom rooted but after reboot the screen is stuck with the flashing Siyah logo... any help would be really appriciated.