Turing机 用机器来模拟人们用纸笔进行运算的过程： >在纸上写上或擦除某个符号； >把注意力从纸的一个位置移动到另一个位置； 在每个阶段，人要决定下一步的动作，依赖于 ()此人当前所关注的纸上某个位置的符号 (b)此人当前思维的状态。 图灵构造出一台假想的机器，由以下几个部分： 一条无限长的纸带 一个读写头 一个状态寄存器 套控制规则 26
26 Turing机 用机器来模拟人们用纸笔进行运算的过程： ➢在纸上写上或擦除某个符号； ➢把注意力从纸的一个位置移动到另一个位置； 在每个阶段，人要决定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号 (b) 此人当前思维的状态。 图灵构造出一台假想的机器，由以下几个部分： 一条无限长的纸带 一个读写头 一个状态寄存器 一套控制规则
可计算问题 若某问题，若存在一个Turing机，对于 相应的初始状态，Turing机经过有限步 最终停机。称该问题是(Turing)可 计算的。 对于可计算的问题，计算复杂性的定义： ■计算所需的步数或指令条数（这叫时间复 杂度)。 ■计算所需的存储单元数量（这叫空间复杂 度)。 27
27 可计算问题 若某问题，若存在一个Turing机，对于 相应的初始状态，Turing机经过有限步 最终停机。称该问题是（ Turing ）可 计算的。 对于可计算的问题，计算复杂性的定义： ◼计算所需的步数或指令条数(这叫时间复 杂度)。 ◼计算所需的存储单元数量(这叫空间复杂 度)
(4)密码学 密码的强度依赖于构造密码算法问题的计算 复杂度。但计算上困难的问题不一定就意味 着密码算法的强度是足够安全的（复杂度和 安全的不平衡) 密码算法需要的是在不知道密钥的情况下解 密是困难的问题，但是在知道密钥的情况下 解密应该是容易的。（依赖陷门信息的困难 28
28 密码的强度依赖于构造密码算法问题的计算 复杂度。但计算上困难的问题不一定就意味 着密码算法的强度是足够安全的（复杂度和 安全的不平衡） 密码算法需要的是在不知道密钥的情况下解 密是困难的问题，但是在知道密钥的情况下， 解密应该是容易的。（依赖陷门信息的困难） (4) 密码学
密码学发展：大体分三个阶段 ■历史时期的古典密码学加密手段 -恺撒密码 ■二战尤其是计算机出现以来的现代阶段 Shannon ■公钥体系阶段 Diffie/Hellman、RSA 29
29 密码学发展: 大体分三个阶段 ◼历史时期的古典密码学加密手段 –恺撒密码 ◼二战尤其是计算机出现以来的现代阶段 - Shannon ◼公钥体系阶段 Diffie/Hellman、RSA
20世纪早期密码机 TYPEX TUNNY C Deuuche-Muu 山培满-到
20世纪早期密码机