古典加密

密码学演变历史

  • William Frederick Friedman (September 24, 1891 – November 12, 1969) 美国陆军密码专家。1930年代,他领导了陆军的一个研究部门Signals Intelligence Service (SIS),其中一部分服务一直延续到五十年代。三十年代晚期,在他的指导下,Frank Rowlett 破解了日本人的PURPLE加密机,这样就截获了日本的大量外交和军事的秘密。
  • 1948, Claude Shannon’s “The Communication Theory of Secrecy System”成为现代密码学理论基础
  • 1971, IBM发明Luciffer Cipher, 128位密钥作分组加密。这项发明是由Horst Feistel(Jan.30, 1915–Nov.14,1990)领导的,他是密码学家,当时在IBM负责设计加密器,他的工作最终激发了70年代Data Encryption Standard (DES)的研发高潮
  • 1976-1977,美国国家标准局正式公布实施DES
  • 1975, Whitfield Diffie and Matin Hellman, A New Direction in Cryptography, 首次提出适应网络保密通信的公开密钥思想,揭开现代密码学研究的序幕,具有划时代的意义
  • 1977-1978,Ronald Rivest, Adi Shamir, Len Adleman第一次提出公开密钥密码系统的实现方法RSA
  • 1981,成立International Association for Cryptology Research
  • 1985,Abbas El Gamal提出概率密码系统ElGamal方法
  • 1990-1992,Lai Xuejia and James: IDEA, The International Data Encryption Algorithm
  • 2000, AES, Advanced Encryption Standard

理论安全

无条件安全Theoretical Secure (or Perfect Secure)

攻击者无论截获多少密文,都无法得到足够的信息来唯一地决定明文。Shannon用理论证明:欲达理论安全,加密密钥长度必须大于等于明文长度,密钥只用一次,用完即丢,即一次一密,One-time Pad,不实用。

实际安全

计算上安全Practical Secure (or Computationally Secure)

如果攻击者拥有无限资源,任何密码系统都是可以被破译的;但是,在有限的资源范围内,攻击者都不能通过系统的分析方法来破解系统,则称这个系统是计算上安全的或破译这个系统是计算上不可行(Computationally Infeasible)。

密码体制

加密系统采用的基本工作方式称为密码体制。密码体制的基本要素是密码算法和密钥。密码算法是一些公式、法则或程序;密钥是密码算法中的控制参数。

对称密码体制和非对称密码体制

对称密码体制(Symmetric System, One-key System, Secret-key System)

加密密钥和解密密钥相同,或者一个密钥可以从另一个导出,能加密就能解密,加密能力和解密能力是结合在一起的,开放性差。

非对称密码体制(Asymmetric System, Two-key System, Public-key System)

加密密钥和解密密钥不相同,从一个密钥导出另一个密钥是计算上不可行的,加密能力和解密能力是分开的,开放性好。

序列密码体制和分组密码体制

序列密码

如果密文不仅与最初给定的算法和密钥有关,同时也与明文位置有关(是所处位置的函数),则称为序列密码体制。加密以明文比特为单位,以伪随机序列与明文序列模2加后,作为密文序列。

分组密码

如果经过加密所得到的密文仅与给定的密码算法和密钥有关,与被处理的明文数据在整个明文中的位置无关,则称为分组密码体制。通常以大于等于64位的数据块为单位,加密得相同长度的密文。

确定型密码体制和概率密码体制

确定型:当明文和密钥确定后,密文也就唯一地确定了。

概率型:当明文和密钥确定后,密文通过客观随机因素从一个密文集合中产生,密文形式不确定,称为概率型密码体制。

单向函数型密码体制和双向变换型密码体制

单向函数型密码体制适用于不需要解密的场合,容易将明文加密成密文,如哈希函数;

双向变换型密码体制可以进行可逆的加密、解密变换。

现代密码学的基本原则

设计加密系统时,总是假定密码算法是可以公开的,需要保密的是密钥。一个密码系统的安全性不在算法的保密,而在于密钥,即Kerckhoff原则。

对加密系统的要求

  • 系统应该是实际上安全的(practical secure),截获密文或已知明文-密文对时,要决定密钥或任意明文在计算上是不可行的。
  • 加密解密算法适用于密钥空间中的所有元素。
  • 系统易于实现,使用方便。
  • 系统的安全性不依赖于对加密体制或加密算法的保密,而依赖于密钥。
  • 系统的使用不应使通信网络的效率过分降低。

对称密码系统

对称密码系统的要求

使用对称密码系统有两个基本要求

  • 一个强加密算法
  • 一个只有发送方和接收方知道的秘密密钥
    • $Y = E_K(X)$
    • $X = D_K(Y)$
      必须假定加密算法是公开的
      因此必须有个安全的途径或信道分发密钥

密码学

密码编码学(Cryptography)

密码编码系统根据以下三个独立方面进行分类

  • 用于将明文转换为密文的操作类型:代换和置换
  • 所使用的密钥的数量和方式:
    • 对称密码体制(单钥系统、秘密密钥系统)
    • 非对称密码体制(双钥系统、公开密钥系统)
  • 明文的处理方式:分组加密和流加密

密码分析学(Cryptanalysis)

  • 密码分析:试图破译密文得到明文或试图获得密钥的过程为密码分析,密码破译的策略取决于加密方法及可供破译者使用的信息。
  • 穷举攻击:对密文尝试所有可能的密钥,直到把它转化为可读的有意义的明文,至少要尝试1/2可能的密钥。

对加密信息的攻击类型

  • 唯密文攻击
    • only know algorithm and ciphertext, is statistical, know or can identify plaintext
  • 已知明文攻击
    • know/suspect plaintext and ciphertext
  • 选择明文攻击
    • select plaintext and obtain ciphertext
  • 选择密文攻击
    • select ciphertext and obtain plaintext
  • 选择文本攻击
    • select plaintext or ciphertext to en/decrypt

穷举攻击

总是可以简单地尝试每一个可能的密钥
穷举攻击是最基本的攻击,难度与密钥长度成正比
平均来说要获得成功必须尝试所有可能密钥的一半

代换技术

代换法是将明文字母替换成其他字母、数字或符号的加密方法
如果把明文看成是二进制序列的话,代换就是用密文位串来代换明文位串
代换法改变明文内容的表示形式,保持内容元素之间相对位置不变

Caesar密码的三个重要特征使我们可以采用穷举攻击分析方法

  • 已知加密和解密算法
  • 所需测试的密钥只有25个
  • 明文所用的语言是已知的,且其意义易于识别

单表代换

单表代换密码不只是25种可能的密钥,而是允许任意代换,增加密钥空间
每个明文字母可以随机映射到任意一个密文字母,密文行是26个字母的任意置换,那么有26!或大于4x1026种可能的密钥,每条消息用一个字母表加密

单表代换不能改变相关字母出现的频率

  • 峰值在:A-E-H-I, N-O, R-S-T
  • 低谷在:J-K, Q, X-Z

一次一密

Joseph Mauborgne提出使用与消息一样长且无重复的随机密钥来加密消息,密钥只对一个消息加解密,之后弃之不用;每条新消息都需要与其等长的新密钥,这就是一次一密,它是不可攻破的。

加密:ci = pi ⊕ ki, pi是明文第i个二进制位, ki是密钥第i个二进制位,ci是密文第i个二进制位, ⊕是异或运算

密文是通过对明文和密钥的逐位异或而成的,根据异或运算的性质,解密过程为pi = ci ⊕ ki

运算基于二进制数据而非字母

给出任何长度与密文一样的明文,都存在着一个密钥产生这个明文。如果用穷举法搜索所有可能的密钥,会得到大量可读、清楚的明文,但是无法确定哪个才是真正所需的,因而这种密码不可破。

一次一密的两个限制

* 产生大规模随机密钥有实际困难
* 密钥的分配和保护无法保证

置换技术

改变明文内容元素的相对位置,保持内容的表现形式不变
通常称为transposition或者permutation密码
通过重新安排消息字母的位置来隐藏明文信息,而不是用其他字母来代换明文字母
这种方法是很容易破译的,因为密文拥有与明文一样的字母频率统计特性

一维变换-矩阵转置

二维变换-图形转置

栅栏技术

隐写术

隐写术不是加密技术
隐写术可以隐藏信息的存在,密码学则通过对文本信息的不同转换而实现信息的不可读

  • 字符标记
  • 不可见墨水
  • 针刺
  • 打字机的色带校正
    隐写术需要许多额外的开销来隐藏相对较少的信息