3.3密码攻防—— 认识图灵机（教学课件）-信息科技清华版（贵州）四年级上册（新教材）

密码攻防 —— 认识图灵机 密码攻防 —— 认识图灵机 目 录 密码攻防——机器对决 01 图灵机——对计算的思考 02 密码学已成为与数学、通信、电子、计算机、物理等领域相互联系、相互渗透的交叉学科。密码学的发展经历了从简单到复杂，从不完善到较为完善，从具有单一功能到具有多种功能的发展过程。这节课我们就探索一下，密码攻防是如何促进了计算机的发展的，思考通用计算何以能实现，领悟“算力”这一信息时代要素的重要作用，并通过讨论“图灵机可以解决什么问题”，体验“图灵机”的魅力。 知识大讲堂 自从无线电和莫尔斯电码问世后，人类通信进入了一个崭新的时代——无线电时代。但是无线电通信完全是一个开放的广播系统，在己方接收电文的同时，对方也可“一览无遗”。因此密码学也就立即与无线电结合，出现了无线电加密解密技术。 密码攻防⸺ 机器对决 在长期的密码攻防中，加密一方曾经通过提高加密算法的复杂度，长期占据主动地位；但字母概率统计的奥秘被发现之后，解密一方最终找到了破译“一对一”替换加密的通用法则，传统加密方法也随之走到了历史的尽头。 传统加密术所遇到的瓶颈，也事关无线通信的应用前景。无线通信若真正走向实际应用，急需一种安全可靠，而又简便有效的加密、解密方法。 为此，亚瑟·谢尔比乌斯（Arthur Scherbius）设计发明了恩尼格玛密码机（德语：Enigma，又译哑谜机，或“谜”式密码机），实现了高效、复杂加密的无线通信。 恩尼格玛密码机原理 恩尼格玛密码机由键盘、编码器、显示板构成。恩尼格玛密码机的编码转轮结构相当复杂和精密；键盘一共有 26 个键，排列方式和广为使用的计算机键盘基本一样；显示板是在键盘上方标示了 26 个字母的小灯泡，当键盘上的某个键被按下时，和这个字母被加密后的密文字母所对应的小灯泡就会亮起来。 无线电发报员在键盘上敲下一个明文字母，就会自动发送对应的密文并点亮相应的密码字母，大大节省了人工编码的时间。恩尼格玛密码机复杂的替换过程完全由机械自动完成，加密人员只需要设定好转子的初始位置，连接好接线板，然后像打字员一样正常输入字母就可以，密文随之自动生成。 恩尼格玛密码机难以破译的关键在于，它不是运行简单的“一对一”代换式密码，而是同一个字母可以被不同的字母替换。因此，字母概率统计的破译方法就对恩尼格玛密码机完全失效了。 恩尼格玛密码机的解密难度 恩尼格玛密码机本质上仍然使用代换法加密，只不过不再采用简单的“一对一”代换，而是经过了多套代换，对应的明文与密文之间存在着6×17576×100391791500=10586916764424000 种可能，也就是一亿亿多种可能。 图灵的“计算机器” 1939 年秋，艾伦·麦席森·图灵（Alan Mathison Turing）临危受命，负责破译恩尼格玛密码机。图灵一接触恩尼格玛密码机，就知道破译这种密码机依靠人的计算能力是无法完成的，解决之道只能是——用机器来对抗机器。为寻求破解之道，图灵想到并借助自己 1936 年为解决希尔伯特判定问题而设计的“图灵机”—— 一种可以辅助数学研究的通用计算机器。 在通用计算思想的指导下，图灵和同事们开始开发一种叫作Bombe 的机器，能够在进入穷举法前先排除一些自相矛盾的组合方式，然后将多台这样的机器环形相连，就能更快速地测试可能的密码设置，从而找到正确的答案。 虽然 Bombe 并不是严格意义上的“图灵机”，但当人们追述计算机科学与计算机技术发展史的时候，依然把图灵和他的 Bombe机器奉为现代计算机的先驱，并开创了计算机科学和密码学的新时代，同时 Bombe 和恩尼格玛密码机也完成了算力攻防史上的第一次碰撞，完成了“不可能”的挑战。 思 考 假如你接到跟图灵类似的任务，你有什么样的好主意？ 图灵机⸺ 对计算的思考 1936 年 5 月，24 岁的图灵向伦敦权威的数学杂志投了一篇论文，题为《可计算数及其在判定问题上的应用》（On Computable Numbers, with an Application to theEntscheidungsproblem），在论文的附录里，图灵描述了一种可以辅助数学研究的通用计算机器模型，后来被人称为“图灵机”，我们所熟知的计算机的发明以及人工智能的实现都基于这个构想。 图灵机构成 图灵机（Turing machine）是一种抽象计算模型，通过一组有限的规则来模拟计算过程，被认为是现代计算机的理论基础。 图灵机由四个部分组成。 （1）一个无限长的存储带，带子由一个个连续的存储格子组成，每个格子可以存储一个数字或符号。 （2）一个读写头，读写头可以在存储带上左右移动，并可以读、修改存储格上的数字或符号。 （3）内部状态存储器，该存储器可以记录图灵机的当前状态，并且有一种特殊状态为停机状态。 （4）控制程序指令，指令可以根据当前状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作（左移还是右移），并改变状态存储器的值，令机器进入一个新的状态或保持状态不变。 图灵机可以解决什么问题 图灵证明了，假设上述图灵机计算模型里所说的功能都能以某种物理形式实现，那么任意可计算问题都可以被解决。那么哪些是可计算问题，哪些又是不可计算问题呢？ 可计算问题举例如下。 （1）计算 1+2+3+…+100。 （2）根据自己的身高和体重，判断是否肥胖。 不可计算问题举例如下。 （1）今晚吃什么？ （2）哪种颜色最受欢迎？ 分组提出一些问题，划分出哪些是计算问题，哪些不是计算问题，又有哪些是可计算的。 课堂活动 拓展阅读 感谢观看 $