终于到了第二部分《密码技术》了,这一章讲了《密钥长度》,还涉及到了NP问题、生物计算机和量子计算机等前沿知识,还有网络蠕虫分布式破译密码等,看完后感觉我宿舍的电脑放着是浪费计算资源呀。

概念

  • 对称密钥长度
  • 穷举攻击所需时间和金钱估计
  • 软件破译机
  • 神经网络
    对密码分析来说并不是特别有用,主要是由其解空间的模式导致,神经网络善于处理那些连续解的问题,这些解比另一些好,神经网络就可以“学习”。而破译密码算法并没有可以“学习”的“标准”,要么找到要么找不到。神经网络适用于那些结构化环境,那里一些东西必须要学习,而在信息熵很高、随机性很强的密码学领域就不适用了。
  • 病毒--网络蠕虫占用大众的计算机来进行分布式破译密码

  • 中国式抽彩法--有奖励的网络蠕虫
  • 生物工程技术:计算机是0和1,生物是四种核苷酸(文中用海藻做例子,具体如何设计未知)
  • 纳诺技术?
  • 热力学的局限性
    热力学第二定律的结论是:信息的表达需要一定的能量。通过改变系统的状态,记录单独的1位所需要的能量不少于kT,其中T表示系统的绝对温度,k是波尔兹曼常数。假定k=1.38 x 10^(-16) erg/K,宇宙的环境温度为3.2K,那么在此温度下运行的计算机每设置或清除1位将消耗4.4 x 10^(-16) erg/K的能量。在比宇宙辐射温度低的环境中运行一台计算机将需要附加的能量来运行热泵。
    目前,太阳每年辐射出的能力约为1.21 x 10^41 erg,该能量足以使理想的计算机上的 2.7 x 10^56 个单独位发生改变,也足以使一个187位计算机中的所有状态值发生改变。如果绕太阳建造一个Dyson球,并且让它一点也不少地吸收32年的能力,那我们就能使一台计算机的能量增加到2^192。当然,它不会让能力剩余,以便计算机完成任何有用的计算。
    但是这仅仅是一颗星体,所有星体中很渺小的一颗。一颗典型的超新星释放的能量可达10^51erg(约是能量以微中子形式释放的100倍,还得现在就开始)。如果所有这些能力被用于运算,那么一个219位的计算器会循环其所有状态值。这些数字与设备的技术性能无关,它只是热力学允许的最大值。所以我们可以断言:对256位的密钥进行穷举攻击是绝对行不通的,除非在超空间里用超物质制造计算机。

  • 公开密钥长度
    实际上,单向陷门函数是一个谎言,因子分解被推测是一个难题。众所周知它似乎是这样。如果它的确是,也没有人能证明难题就真的很难。大多数人都假定因子分解是困难的,但它从来没有被从数学上证明过
    不难想象50年后的情形,人们围坐在一起,兴致勃勃地谈论着过去的美好时光:那时候,人们习惯于认为因子分解是难的,密码术正基于这种难度,而公司实际上依靠这种素材大赚其钱。也可以很容易地设想到,未来在数论方面的发展使因子分解更加容易或者复杂度定理的发展使因子分解变得毫无意义。(这是作者的推测)
    1977年,Ron Rivest说过分解一个125位(十进制)的数据需要40 x 10^15年。可是,一个129位的数据在1994年被成功分解。(RSA-129??)
    如果有什么教训的话,那就是做出预言将是很愚蠢的。

  • 二次筛选法

  • 一般数域筛选法
  • 特殊数域筛选法
  • DNA计算法
  • 单向汉密尔顿圈
  • NP完全问题(NP-complete problem)
    根据定义,任何NP完全问题的一个实例都可以在多项式时间里变换成其他NP完全问题的一个实例,当然也可以转换成单向汉密尔顿问题的一个实例。从20世纪70年代开始,密码学家才尝试将NP完全问题用于公开密钥密码系统中。
    “假定破译者有100万个处理器,每个处理器每秒能测试100万次”,或许很快就被改成“假定破译者有1000个发酵桶,每个发酵桶有20000升的容量”。

  • 量子计算法
    量子计算法的基本原理是爱因斯坦波粒二象性:光子可以同时存在于多种状态。一个典型的例子就是,当光照射到银白色的镜面时,它会有波一样的特性,既可以反射也可以传播,就像波浪撞击一堵带有缺口的防波堤,有时会返回去,有时却可以穿过去。然而对光子进行测量时它又表现出粒子的特性,有一个唯一的可被测量的状态。
    Peter Shor阐述了一个基于量子力学的因子分解机器的设计模型。与一般的计算机在某一特定时刻可以认为有一个固定的状态不同,量子计算机有一个内部波动函数,这个函数是所有可能基的联合重叠。计算机在单步运算中通过改变整套的状态值来改变波动函数。在这种意义上,量子计算机是基于经典的有限状态机改进而成的:它利用量子特性允许在多项式时间里进行因子分解。理论上可以用来破译基于大数分解离散对数问题的密码系统。
    ......
    ......由于没有内部时钟,所以数以千万计甚至数以亿计的独立门用于分解密码上非常大的数,如果n个量子门又很小的错误概率p,则每成功运行一次所需实验的次数就是(1/(1-p))^n。
    实践起来前景渺茫,在作者成书那个时候

  • 对称密钥和公开密钥长度的比较
    一个系统往往是在其最弱处被攻击
    一般而言应该选择比对称密钥算法更安全的公开密钥长度,因为公开密钥算法通常持续时间长,且保护更多的信息。

  • 对单向散列函数的生日攻击

    1. 给定散列函数H(M),破译者逐步创建其他文件M',使得H(M)==H(M');
    2. 攻击者随机找出M、M',使得H(M)==H(M');
      房子里有253个人才有可能使至少一个人与你生日相同,而只需要23个人就可以有两个人生日相同(这两个人可能一个是你,也可能都不是)。2^m --> 2^(m/2)
  • 生日攻击(birthday attack)

  • 密钥应该多长
  • 设置密码长度比你认为安全的还要长一些(当然得根据保护的信息的价值、和破译者的损耗来定)

问题

  • 信息“熵”是什么?
  • 生物技术中的纳诺技术是什么?
  • 热力学的局限性中的一些物理概念,以及对256位密钥进行穷举行不通?那后面为什么可以破解2047位(公开密钥长度的建议值)?是因为用了好的数学分解方法吗?
  • 没细看DNA计算法中的例子:1994年,Leonard M. Adleman用DNA链演示NP完全问题的解决方法
  • 量子计算机实验成功的次数怎么求????
  • 生日攻击的概率如何求?
  • 二次筛选法
  • 一般数域筛选法
  • 特殊数域筛选法
  • DNA计算法
  • 单向汉密尔顿圈
  • NP完全问题(NP-complete problem)