Amy Guan

  • 236 主题
  • 251 帖子
  • 134 积分
  • 身份:LV1 技术小白
  • E币:132

反复推敲后,深入浅出给你科普加密术

2016-6-28 02:00:00 显示全部楼层
自从有了战争就有了加密术,加密术越来越复杂,解密术也越来越先进,加密术与解密术魔高一尺道高一丈,此消彼长各领风骚。
  1、古典加密术

    凯撒密码就是一款典型的古典加密术,其加密规则非常简单,把字母表整体移位,形成明密文的对应表,接收者按提前规定好的位数反向移位就解密了。
   9b68c55f9a36b8477f601001f945b18722d1bfc2.jpg902x471 68.9 KB


  这种加密术很简陋,明密文的对应关系也就25种,即使不知道移了几位,只要移位不超过25次,就能把有意义的原文找出来。
  这确实不够安全,那该如何改进呢?您一定想到了乱序的法子,字母表不整体移位,而是乱序对应,这样明密文的对应关系就远远超过25种。
   fa697a5fd302fb23ec30affd186f99684515565a.jpg908x222 34.3 KB


  乱序的思路很好,但也不够安全,因为它抗不住概率分析。我们都知道英文中26个字母出现的频次是不一样的,E出现的最多,如果一份密文中N的个数最多,我就有理由相信其对应的明文就是E。
   81613a4aa18f3de5b4c6a0f3e58c1319e7f2751f.jpg918x439 56.1 KB


  再比如,如果一份密文中某个字母出现的概率约为10%,我就会更倾向于认为它是T而不是Q,因为T的概率约为9%,而Q的概率则低得多啊。这种猜测未必十分准确,但却在很大程度上接近了真相,可以有效地减少了解密尝试的次数。
  好了,现在轮到加密方想招了,既然解密方靠的是自然语言的非均匀性,那我就尽量把密文搞均匀了。于是加密方设置了3套密文表,明文中的147位使用密文1,258位使用密文2,369位使用密文3。例如明文中的E,会有B、K、H三种密文来表达,其概率就会被摊平了。
   396e1c8ee34c4759b05d60f30e68aed5f768714c.jpg974x539 120 KB


  现在又轮到解密方想招了,既然你把单个字母的概率规律给隐藏了,那只能从字母组合去下手了。大家都知道某些字母组合出现的频次是很多的,例如THE和ING,那在密文中遇到固定的三字母组合时,就要首先怀疑是不是它们。
   4e933cfc5b5cf6cabe1ae947e43aa836c63b2918.jpg949x551 58 KB


  再次轮到加密方想招了,归根结底,解密方利用的就是自然语言的非均匀性在密文中的映射,如果想办法把密文中的规律性完全去掉,那解密方岂不是就没招了?
  这个思路是对的,但把明密文之间的映射规律完全去除,需要很复杂的置乱算法,于是复杂机械和电动机械就走上了加密术的舞台,并在此基础上形成了近代加密术。
  2、近代加密术

    美军的滚筒机就是个典型的复杂机械加密设备,25个铝盘外沿分别按不同次序刻着26个英文字母,然后套在一根轴上,每个铝盘都可以独立地转动。加密时逐个转动滚轮,使情报内容出现在一行,然后把往下数第5行的字母抄下来作为密文。接收方收到密文后,逐个转动滚轮,使密文出现在一行,然后往上数第5行的字母就是明文。
  第5行只是举例,可以是任意行,这要靠双方提前约定。而且,每次作战前都会把25个铝盘拆下来,按照新的次序进行安装,即使上次作战时被敌人捕获了一部滚筒机,因为铝盘的次序变了,敌人还是解不了密。
  比滚筒机更复杂的是齿轮机,它可以把密文中字母规律彻底搞乱,使得解密工作变得更加困难。
   286cf326863a1e9a9db4f386d4e7d1c54e974469.jpg938x581 112 KB


   5d6b7410d0d8655b6524637bd554f0285a7bf49b.jpg950x532 106 KB


  德国的ENIGMA齿轮机最典型,当年盟军曾调动了一帮顶级数学家去破密,研究了很长时间还是毫无头绪。盟军只好从别外下手,他们瞄准了一位仓库保管员,这位保管员是个没有信仰好逸恶劳的人,他的哥哥是个纳粹高官,他哥哥也知道这个弟弟没啥出息不堪大用,就给他找了个仓库保管员的闲差,而这个仓库里就有ENIGMA齿轮机。
  这位保管员羡慕上流社会生活,可钱总是不够花,被盟军情报员一忽悠就动心了,他把ENIGMA齿轮机的一部分资料偷拿出来卖了。盟军发现资料是真的后欣喜若狂,盯着他不放,要求他接着偷。
  这个保管员一共卖了30多次,后来他害怕不敢卖了,跟他接头的盟军情报员威胁他“你出卖情报的证据都在我们手上,你继续卖就可以活,还接着有钱拿,你不卖就是个死,你哥也得受牵连”。这个故事告诉我们一个道理“当内奸卖情报是条不归路,如何开始你能做主,但如何结束你就说了不算了。”
  3、公钥密码术

    有点跑题了,言归正转。加密术与解密术的斗争此消彼长,ENIGMA齿轮机代表了复杂机械加密的最高阶段,很长时间内解密非常困难,加密术胜出。但出现计算机后,局面就发生了变化,在计算机强大的解算能力面前,齿轮机简直不堪一击,破解它就是分分钟的事,解密术胜出。
  现在又轮到加密方想招了,以往加密术的安全性依赖的是加密算法的复杂性,齿轮机算法比凯撒密码算法复杂,所以就更安全,但现在再复杂的算法都抗不住计算机了,所以安全性不能再依赖算法了。
  那该依赖什么呢?现在改成了依赖密钥,因为密钥可以有几乎无穷多个,而你不知道哪个才是对的,现代加密体制的安全性就依赖于此。
  在以往的加密术中,你只要知道是如何加密的,就会知道如何解密,因为解密就是加密的逆过程嘛。现在加密算法抗不住计算机了,那索性就公开好了,那现在的问题就变为了:加密算法分开后,咋还能不让外人从中倒推出解密算法?
  很明显,加密算法应该是没有反函数的单向函数。例如“取余算法”,7和11两个明文,除以3后的余数分别为1和2,这种算法就没有反函数,因为除以3余数为1和2的数值有无穷多个,并不能定位到7和11。
  那具体是如何实现的呢?例如我想传送【1  1  0  1】这组明文序列,设置了一个加密用的序列【3  6  9  17】作为基底,两个序列逐位相乘再相加,即1*3 1*6 0*9 1*17=26,于是就把26作为了密文。
  您一定觉得有问题,因为接收者根据这个基底在分解26时,不止有【1  1  0  1】这一个解,【0  0  1  1】也是一个解,有两组明文可以加密成一个密文,在解密时就会造成混淆,这当然是不可以的。
  那该怎么办呢?当~当~当~,现在隆重推出超递增序列。例如【1  3  5  11  21  44】就是一组超递增序列,您能看出它有什么特点吗?
  这组序列中的任何一个数值,都比它前面的所有数值之和还要大,例如11大于1 3 5的和。这有什么用呢?这可以保证解密的唯一性。例如明文是【1  0  0  1  0  1】,与超递增序列逐位相乘累加的结果是56,接收者按超递增序列从后至前的次序进行比较,因为56比44大,所以对应位肯定是1而不是0,这又是为什么呢?
  假如44这位对应的是0,那前面所有位即使都是1,其总和也会小于44,这是超递增序列的性质嘛,然后比44更大的56就不可能被正确分解。
  44这一位对应的是1,此位确定后继续向前推进,因为56-44=12,用12继续向前比较。因为12比21小,因此倒数第二位的值就应该是0而不是1,如果是1的话就爆了嘛。接着再向前比较,12比11大,所以倒数第三位的值就是1。就是这样从后向前观察比较,只用一遍就可以把唯一的明文分析出来。
  如果把这个A序列【1  3  5  11  21  44】公开行不行?当然是不行的,因为坏人知道了这个序列就能轻松的解密。A序列只能让合法的接收者知道,不能让其它人知道。但是这个序列必须要公开啊,说好的加密算法公开,若不公开岂不是又落回了老套?
  那该怎么办呢?当~当~当~,现在推出第二个关窍,那就是对超递增序列进行变形。还以A序列为例,将序列中的每个数值等乘以43,乘积超过1590时,就取小于1590的余数,并形成新的B序列。请注意,我利用的是43*37=1590 1这个关系式,43这个数字是我随意找的素数,正是它的随意性,形成了公钥加密的保密性,因为你不知道会是哪个数啊。
  因为43*44=1892=1590 302,所以B序列就是【43  129  215  473  903  302】,这就是公开的加密算法,重要的事情说三遍:公开的是B序列而不是A序列!公开的是B序列而不是A序列!公开的是B序列而不是A序列!
  把明文【1  0  0  1  0  1】用B序列加密,当然还是逐位相乘再累加啦,得出密文818,你根据B序列和818这两条信息啥也推不出来,因为B序列并不是超递增序列,你不可能从后至前一遍就找到答案,只能从000000到111111进行64次尝试。这个例子过于简单,实际的序列会长得多,尝试的次数是天文数字,这是一项基本不可完成的任务。
  最后再说合法接受者,除了B序列和818,他还知道37和1590,这就是绝对不能让他人知道的私钥。他把818乘以37得出30266,而30266=19*1590 56,这就取出了56这个数值,而他根据37和1590,可以从B序列中找到A序列,再通过A序列和56就可以从后至前一遍就解算出明文【1  0  0  1  0  1】。
  后面这三段写得有点粗略,为什么43、37和1590这三个数会这么神奇?这其中有数论中的最小正剩余问题,实在是不能再展开分析了。否则就会越说越多,出现我常常遇到的学生课后反馈“老师您讲得真好,前半段我都有点明白了,可后半段又把我讲迷糊了,现在我是彻底不明白了”。
  您通过阅读这篇科普文章,获得哪些知识上的收益呢?我帮您总结一下吧,至少有5个认知:
  
1、古典和近代加密术的核心方式就是“代换”,即构建越来越复杂的明密文对应代换的关系,靠代换关系的复杂度来保证安全性。
2、自然语言的非均匀性是破译的抓手和关键,当破解的结果是一堆乱码时,那肯定就是没搞对,如果是一段意义清晰的信息,那一般就是搞对了。
3、“构建加密函数,通过反函数解密”这种传统的对称式加密方式已抗不住计算机的暴力破解。
4、现代加密方式的安全性依赖的是密钥,而不是加解密的算法。
5、公钥密码的关键就是“单向函数”,解密不是加密的逆过程,其安全性依赖于几乎有无穷可能的私钥。
  这5个结论是很重要的信息安全理论知识,我将它们浓缩在了这篇不长的科普文章中。
  最后一个感悟:信息安全是个高门槛的理论,相关的专业基础书籍虽然很多,但打开就是一堆公式,您不会有丝毫兴趣去读。但您为什么能完全看懂这篇科普文章,甚至学习领悟到5个信息安全重要知识呢?其奥秘在于我总结出来的“两种逻辑”。
  一是理论的内在逻辑。专业书籍中的内容组织,遵循的是理论本身的内在逻辑,并用数学语言进行描述,这只适合有专业基础的内行人士学习,外行很难看懂的。
  二是听众的认知逻辑。讲课或写科普文章,绝不是把自己领悟到的理论内在逻辑讲出来,由于基础的不同,听众是很难跟上你的思维的。而应遵循听众的认知逻辑,简单地说,就是把理论的内在逻辑进行改造,形成符合外行听众的认知逻辑。否则的话,你讲的再对也没用,因为听众听不懂。
  在内容的组织必须换位思考,每一个环节都考虑到听众会有什么疑惑,我该用什么样的说法去消除他的疑惑。最关键的不是把正确的说法推送给听众,而是设计听众会自然产生的疑惑,并用通俗的说法解决这些疑惑,这才能帮助他们真正的理解。
  您是否发现这篇文章有很多思维上的引导?而且你会想“说的对啊,那该怎么办呢?”,然后文章给出了答案。这就由生硬的告诉你知识,变成了你产生了疑问,作者通过解决你的疑问,帮助你掌握了知识。这种思维上的引导,使您不太费力地就领悟到了信息安全理论的5个重要结论。
    文/奥卡姆剃刀
来源:新浪博客

最新评论

楼层直达:

骄傲的海盗

  • 192 主题
  • 210 帖子
  • 110 积分
  • 身份:LV1 技术小白
  • E币:110
骄傲的海盗 2016-6-29 02:18:28 显示全部楼层
通俗易懂,收藏了。刀刀不愧是老师。

xyta092

  • 0 主题
  • 8 帖子
  • 100 积分
  • 身份:LV1 技术小白
  • E币:100
我要评论
2
2
广告
关闭 热点推荐上一条 /3 下一条
快速回复 返回列表