首页 >> 数学 >> 计算机科学 >> 文章

漫谈信息安全(一)Comments>>

发表于 2012-05-27 07:57 | 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,那它代表的也应是明文中出现次数较多的字母。按照这种思路试试吧,My God,密码解开了。

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

功夫不负有心人,有一天加密方终于找到了解决问题的关键,这个关键就是“二维”,这个方法被后人称为“多表系统”,就是把明文字母两个一组的重新排列,按组去设置乱码表。明码表有:AA AB...AZ BA BB...BZ CA CB....ZZ,每组再指定一个两个字母的密码对。例如明文BABY,密文就是分别对应BA和BY的两组密码对。这个方法其实就是把一维坐标系扩展成了二维。

这个多表系统非常有效,一直到二战期间还在使用。当时德军有一种根据多表系统原理设计的加密转轮机,有三个轮子负责把输入的明码置乱成密码,英国一直破译不出来。后来德国为了进一步增加保密性,多加了个轮子,可保密性不仅没有增加反而下降了,终于被英国解了密。这就好比是洗扑克牌,并不是洗的次数越多就越乱乎,你已经洗得足够乱乎了,又洗了一次,这次反而不够乱乎了。

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

隐写术也是由来已久了,传说凯撒为了防止传令兵被俘后泄露情报,想出了一招:把一批士兵的头发剃光,并用火烙铁在脑顶上烙上不同的印迹,并对哪个兵烙上什么样的疤做好记录,被烙的士兵一头雾水,不明白这是为什么。大战之前,凯撒召集大将,并要求他们牢记一组对应关系,梅花疤代表“马上率部向我驰援”,三角疤代表“固守阵地”等等。

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

如果敌人看到了这个蹊跷,但不认为这是个蹊跷,那当然更好了,二战中的一位音乐家就做到了这一点。他当时是盟军的一位情报员,跟其他情报员隐藏情报的方式不一样,他自创了一套英文字母和五线谱之间的对应表,并把情报写成了曲谱带在身上大摇大摆地过关卡。他最危险的一次就是遇到了一位深通乐理的德军军官,德军军官拿着五线谱拷问他,他竟然真的把情报乐谱完整地唱出出来,虽然不好听,但终归还算是个谱子。音乐家靠这招送情报无数,从来没有失过手。

加密的方法越来越巧妙,但随着计算机的诞生,这些被称为古典密码术的方法全部失效,因为它们根本抵挡不住计算机的穷举分析。现代密码学的思路跟古典密码术非常不同,它是先找出一个数学难题,然后把加密方法归结到这个难题上,若解不出这个数学难题就破解不了这个密码。现代密码学更加引人入胜,这是下一个话题。

0
为您推荐

40 Responses to “漫谈信息安全(一)”

  1. single说道:

    赶紧谈下一话题吧

  2. 伯拉布说道:

    最喜欢看这种。

  3. slinerd说道:

    通俗易懂啊,情节又有趣,果然是“奥卡姆剃刀”

  4. 说道:

    这么就下个问题了...还没有看过瘾..

  5. sar说道:

    平均來說,反對這些訊息加密,6大數據中心都有這些危害地區安全的反制機制,4秒便能破解

  6. 姚森说道:

    不错,通俗易懂,引人入胜

  7. woodstocker说道:

    剃刀真牛。。。

  8. 山远水济说道:

    推荐 《走向数学系列丛书》(90年代版本)——现在新版没出全——第5本《密码学》

    ed2k下载地址如下:http://www.verycd.com/topics/2778821/

    “这些被称为古典密码术的方法全部失效,因为它们根本抵挡不住计算机的穷举分析”
    计算机分析要求有足够多的样本进行分析。如果只在关键时候通信一次,就难以破解。比如信号枪,每次开战前约定信号枪表示内容。战场上每一个人都看得到,但是数据量不够却难以破解。比如“撤退”,只用一次,谁也不知道。如果是“炮击”,来个2、3次,普通小兵也知道躲到掩体里了。

    对于复杂的字母重新映射关系,计算机也需要非常非常巨大的时间才能计算完成,后者往往根据语言习惯进行统计,快速算出结果。所以,如果使用计算机也不知道统计规律的语言——著名电影《风语者》——那破解难度相当大了。

    理论上,没有破解不了的东西,只有时间的差异。1分钟?1年?1000年?10e10年?

  9. Nibble说道:

    坐等下一个话题。

  10. 这学期选了这门课,古典是挺有意思的,,但是现代看了蛋疼啊!!!

  11. pomo酱说道:

    长知识了,这连载追了

  12. 大爱,坐等下一话题

  13. samuelhg说道:

    and?,,,,期待续集

  14. 818手机说道:

    反對這些訊息加密

  15. 渺孤鸿说道:

    感觉生命的基因密码最有吸引力!

  16. 草木灰说道:

    通俗易懂

  17. 云天明说道:

    下一话题就开始基于数学难题了……
    总感觉越到后面密码学就越想放在一个篮子里的鸡蛋……
    想象一下,某一天大整数因式分解被证明为P问题,并且有一个时间复杂度很低的算法,在所有的RSA和AES被替换之前,会产生多大的损失和恐慌……

  18. Clones说道:

    DES 和 AES 都不是基于数学难题的吧,但实际上却是应用于计算机的。而且公钥体系计算都比较慢,事实上直接也只用于数字签名、密钥分发等场合,具体的数据加密仍然得用沿袭古典密码学的对称密码体系啊。

  19. Hans海晏河清说道:

    一直迷惑:不管“单表系统”还是“多表系统”,为什么总是采用静态映射关系(即明文符号与密文符号存在固定的对应关系)呢?如果中间随机穿插无意义符号,或者不断变换映射关系(当然变换是有约定规则的,比如中间穿插随机符号,后面的新映射关系与穿插的随机符号相关),那么因为何时加入随机符号、加入的随机符号数量等信息不表现在密文中,应该就可以极大的提高破译难度,即使计算机穷举也难以处理了啊?
    百思不得其解,请楼主介绍一下?

    • hunke说道:

      是不是要考虑接受的人容易读啊?加密加到自己也搞不清了怎么办……

      • Hans海晏河清说道:

        其实也是一个算法,由加密方提供的。解密时按算法套用就可以了。
        我提的这个问题,大家觉得不合理处在哪儿?请讨论。

        • Clones说道:

          使用随机数的有比如RC4流密码。密码体系还要考虑软硬件实现的难易度,静态的映射表可以直接写在ROM里,而动态的运行时需要额外的RAM内存。要提高安全性,当然可以多种密码合用,但有性能的问题在。

  20. christopher说道:

    mark,期待下一话题。

  21. tfls说道:

    只在离散数学里头学过RSA,个人觉得,一个好的加密算法一定是在数学上优雅的
    至于AES啊,咱又不学密码学,就让那些人搞去吧

  22. tfls说道:

    最感兴趣的是,如果量子计算机发明了,那加密算法又应该如何设计?
    没见过这方面的文章,有人研究不?

  23. monkey说道:

    恩啊,蛮有意思

  24. 捌层思维广说道:

    我是学信息安全的,求大神指导

  25. jack说道:

    二呢?

  26. 张瀚楠说道:

    楼主能不能在详细解释一下那个二维的问题,我不是太明白。一维的是一对一的映射,二维是二对二。同样一片文章用一维和二维的办法分别加密,比如就e这个字母出现的频率在原文中是不会改变的,在我看来而在加密后的也没有改变也。就是说我不管你是一维e——z的加密还是二维be——xz的加密方式,只要我从一维的角度看,e的频率是没有变的,还是能破解呀。
    楼主解释再解释一下吧,最好给个例子,谢谢了

    • impost说道:

      二维是二对二,不是一对二哦。。比如,remember这个词,拆分后是re、me、mb、er四个词,这四个词分别对应密码表中的ab、cd、ef、gh(打个比方),那么remember加密后就是abcdefgh,自然就看不出频度了。。

      • 张瀚楠说道:

        按照你举得例子 re, me 分别对应ab,cd,分别是二对二的对应,看是放在一起看不就是r,e,m对a,b,c,d, 成了三对四了? 这样的看来,原信息是由26个字母组成的(虽然是两个字母一组),按照前面说的3对4的例子,要加密原信息,我所加密需要的元素至少要大于26。我的理解对吗?

    • 魂断香销说道:

      我也被这个细节所困扰 -- 感觉这里的例子作者用的不正确,或者描述的不正确
      这个“二维”的例子仿佛说的是polyalphabetic cipher,即多字母替代密码。作者提到把明文BABY字母两个一组这样替换,再想想看playhair cipher,这不就是典型的双字母替代加密么?然而后方却说起多表替代。要知道多表替代可是monoalphabetic cipher (单字母替代密码)的一种。

      经典密码:
      一 substitution cipher 代替密码
        1. monoalphabetic cipher 单字母密码
             a) 单表替代
      b) 多表替代 e.g. 维吉尼亚
        2. ployalphabetic cipher 多字母密码
            e.g. playhair cipher
      二 transposition cipher 置换密码

      多表和多字母都在一定程度上可以均化频率,感觉作者弄混了二者。当然,也有可能国内教的系统不一样吧。

  27. budblack说道:

    自从有了多说,科学会的读者们都有头像了。。。好东西啊
    密码什么的,记得以前初中上课传小纸条还得建立密码本,替换式密码嘛~哈哈~

  28. lin说道:

    基本概念貌似有点问题,藏头诗不属于加密术,而是隐写术

  29. L说道:

    信安学生路过、、、

  30. 吴钩-贾培申说道:

    信息安全还这么有意思!!

  31. 久霖说道:

    这不是您之前写过的 凯撒的加密术 吗?
    一直关注您的贴子 期待——

  32. Ray说道:

    AES和DES的原理从上层来讲和数论没有必然联系,RSA倒是基于一个数论的难题。但是,AES和DES的permutation table和s-box和数学倒是有一些的关系,那就是:什么样的permutation table和s-box设计能最大程度的打乱输入?或者是这样的permutation table和s-box能不能最大程度打乱输入?如何证明这些是需要用数论的知识的,就如同证明conflicts。

Leave a Reply for 云天明