分组密码的基本概念

分组密码概述

• 分组密码是许多系统安全的一个重要组成部分。可用于构造
  • 伪随机数生成器
  • 流密码
  • 消息认证码(MAC)和杂凑函数
  • 消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分

    应用中对于分组码的要求

• 安全性
• 运行速度
• 存储量(程序的长度、数据分组长度、高速缓存大小)
• 实现平台(硬、软件、芯片)
• 运行模式

  分组密码概述

  明文序列$x_0, x_1,...,x_i,...$，分组长度为n
  加密函数$E:V_n \times K \rightarrow V_m$
  密文分组长度为m
  这种密码实质上是字长为n的数字序列的代换密码。
  
• 通常取n=m。
• 若n<m ，则为有数据扩展的分组密码。
• 若n>m ，则为有数据压缩的分组密码

  分组密码的设计原则

  分组密码设计问题

  分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。

  安全性设计原则

• 混淆原则(Confusion)
  • 混淆原则就是将密文、明文、密钥三者之间的统计关系和代数关系变得尽可能复杂，使得敌手即使获得了密文和明文，也无法求出密钥的任何信息；即使获得了密文和明文的统计规律，也无法求出明文的新的信息。
  • 可进一步理解为：
    • 明文不能由已知的明文，密文及少许密钥比特代数地或统计地表示出来。
    • 密钥不能由已知的明文，密文及少许密钥比特代数地或统计地表示出来
• 扩散原则(Diffusion)
  • 扩散原则就是应将明文的统计规律和结构规律散射到相当长的一段统计中去(Shannon的原话)。
  • 也就是说让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。
  • 如果当明文变化一个比特时,密文有某些比特不可能发生变化,则这个明文就与那些密文无关,因而在攻击这个明文比比特时就可不利用那些密文比特。

    分组密码算法应满足的要求

• 分组长度n要足够大：
  • 防止明文穷举攻击法奏效。
• 密钥量要足够大：
  • 尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。
• 由密钥确定置换的算法要足够复杂：
  • 充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击。
• 加密和解密运算简单：
  • 易于软件和硬件高速实现。
• 数据扩展：
  • 一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。
• 差错传播尽可能地小。
  • 一个密文分组的错误尽可能少的影响其他密文分组的解密。

    分组密码的实现原则

• 软件实现的原则：
  • 使用子块和简单的运算。如将分组n化分为子段，每段长为8、16或32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐比特置换。
• 硬件实现的原则：
  • 加密解密可用同样的器件来实现。

    SP网络

    代换概述

    代换的定义

    如果明文和密文的分组长都为n比特，则明文的每一个分组都有$2^n$个可能的取值。为使加密运算可逆（使解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。
    不同可逆变换的个数有$2^n !$个。
    

    代换的弱点

• 如果分组长度太小，如$n=4$，系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破
  • 这个弱点不是代换结构固有的，只是因为分组长度太小
  • 如果分组长度n足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效
• 从实现的角度来看，分组长度很大的可逆代换结构是不实际的
  • 仍以4比特的代换表为例，该表定义了$n=4$时从明文到密文的一个可逆映射，其中第2列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。
  • 从本质上来说，第2列是从所有可能映射中决定某一特定映射的密钥
  • 密钥需要64比特
• 一般地，对n比特的代换结构，密钥的大小是$n \times 2^n$比特。如对64比特的分组，密钥大小应是$64 \times 2^{64} = 2^{70} \approx 10^{21}$比特，因此难以处理。

  SP网络

• 在Shannon 1949 的文章中，介绍了替代-置换网络的思想即SP网络
  • 这种思想形成了现代密码的基础
  • SP网络是替代-置换乘积密码的现代形式
• SP网络是基于下列两种最基本的密码运算：
  • 替代（ Substitution ）
  • 置换（ Permutation ）

    代换网络

    代换是输入集$A$到输出$A'$上的双射变换：
    $$f_k: A \rightarrow A'$$
    式中，k是控制输入变量，在密码学中则为密钥。
• 实现代换fk的网络称作代换网络
  • 双射条件保证在给定k下可从密文惟一地恢复出原明文
• 代换fk的集合：$s = \{ f_k | k \in K \}$
• 如果网络可以实现所有可能的$2^n !$个代换，则称其为全代换网络
  • 全代换网络密钥个数必须满足条件：$\# \{ k \} \ge 2^n !$
• 密码设计中需要先定义代换集$S$，而后还需定义解密变换集，即逆代换网络$S^{-1}$，它以密文$y$作为输入矢量，其输出为恢复的明文矢量$x$。
• 要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。
• 实用密码体制的集合$S$中的元素个数都远小于$2^n !$。

  代换盒(S盒）

  在密码设计中，可选$n = r \cdot n_0$，其中$r$和$n_0$都为正整数，将设计$n$个变量的代换网络化为设计$r$个较小的子代换网络，而每个子代换网络只有$n_0$个输入变量。称每个子代换网络为代换盒(Substitution Box)。
  

  S盒的设计准则

  迄今为止，有关方面未曾完全公开有关DES的S盒的设计准则。Branstead等曾披露过下述准则：
• S盒的输出都不是其输入的线性或仿射函数。
• 改变S盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。
• 当S盒的任一输入位保持不变，其它5位输入变化时(共有$2^5 = 32$种情况)，输出数字中的0和1的总数近于相等。
  这三点使DES的S盒能够实现较好的混淆。

  Feistel密码结构

  Feistel密码设计思想

• 乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果。
• Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。

  Feistel密码实现的参数

  Feistel网络的实现与以下参数和特性有关：
• 分组大小: 分组越大则安全性越高，但加密速度就越慢。
• 密钥大小：密钥越长则安全性越高，但加密速度就越慢。
• 轮数：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。
• 子密钥产生算法：该算法的复杂性越大，则密码分析的困难性就越大。
• 轮函数：轮函数的复杂性越大，密码分析的困难性也越大

  设计Feistel密码的两个要求

  在设计Feistel网络时，还有以下两个方面需要考虑：
• 快速的软件实现：在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。
• 算法容易分析：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法

  Feistel密码加解密结构

  Feistel加密结构

  输入是分组长为$2w$的明文和一个密钥$K$。将每组明文分成左右两半$L_0$和$R_0$，在进行完$n$轮迭代后，左右两半再合并到一起以产生密文分组。第i轮迭代的输入为前一轮输出的函数：
  $$ L_i = R_{i - 1} \\ R_i = L_{i - 1} \oplus F(R_{i - 1}, K_i) $$
  其中$K_i$是第$i$轮用的子密钥，由加密密钥$K$得到。一般地，各轮子密钥彼此不同而且与$K$也不同。

  Feistel解密结构

• Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入
• 但使用子密钥$K_i$的次序与加密过程相反，即第1轮使用$K_n$，第2轮使用$K_{n-1}$，……，最后一轮使用$K_1$。这一特性保证了解密和加密可采用同一算法

  Feistel密码解密的正确性

  在加密过程中：
  $$ LE_{16} = RE_{15} \\ RE_{16} = LE_{15} \oplus F(RE_{15}, K_{16}) $$
  在解密过程中:
  $$ LD_1 = RD_0 = LE_{16} = RE_{15} \\ \begin{aligned} RD_1 & = LD_0 \oplus F(RD_0, K_{16}) = RE_{16} \oplus F(RE_{15}, K_{16}) \\ & = [LE_{15} \oplus F(RE_{15}, K_{16})] \oplus (RE_{15}, K_{16}) \\ & = LE_{15} \end{aligned} $$
  所以解密过程第1轮的输出为$LE_{15}||RE_{15}$，等于加密过程第16轮输入左右两半交换后的结果。
  容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第$i$轮有：
  $$ LE_i = RE_{i - 1} \\ RE_i = LE_{i - 1} \oplus F(RE_{i - 1}, K_i) $$
  因此：
  $$ RE_{i - 1} = LE_i \\ LE_{i - 1} = RE_i \oplus F(RE_{i - 1}, K_i) = RE_i \oplus F(LE_i, K_i) $$

  DES算法

  DES算法简介

  美国制定数据加密标准简况

• 目的：
  • 通信与计算机相结合是人类步入信息社会的一个阶梯，它始于六十年代末，完成于90年代初。计算机通信网的形成与发展，要求信息作业标准化，安全保密亦不例外。只有标准化，才能真正实现网的安全，才能推广使用加密手段，以便于训练、生产和降低成本。
• 美国NBS在1973年5月15公布了征求建议。1974年8月27日NBS再次出公告征求建议，对建议方案提出如下要求：
  • 算法必须提供高度的安全性
  • 算法必须有详细的说明,并易于理解
  • 算法的安全性取决于密钥,不依赖于算法
  • 算法适用于所有用户
  • 算法适用于不同应用场合
  • 算法必须高效、经济
  • 算法必须能被证实有效
  • 算法必须是可出口的
• IBM公司在1971年完成的LUCIFER密码 (64 bit分组，代换-置换，128 bit密钥)的基础上，改进成为建议的DES体制
• 1975年3月17日NBS公布了这个算法，并说明要以它作为联邦信息处理标准，征求各方意见。
• 1977年1月15日建议被批准为联邦标准[FIPS PUB 46]，并设计推出DES芯片。
• 1981年美国ANSI 将其作为标准，称之为DEA[ANSI X3.92]
• 1983年国际标准化组织(ISO)采用它作为标准，称作DEA-1
• NSA宣布每隔5年重新审议DES是否继续作为联邦标准，1988年（FIPS46-1）、1993年（FIPS46-2），1998年不再重新批准DES为联邦标准。
• 虽然DES已有替代的数据加密标准算法，但它仍是迄今为止得到最广泛应用的一种算法，也是一种最有代表性的分组加密体制。
• 1993年4月，Clinton政府公布了一项建议的加密技术标准，称作密钥托管加密技术标准EES(Escrowed Encryption Standard)。算法属美国政府SECRET密级
• DES发展史确定了发展公用标准算法模式，而EES的制定路线与DES的背道而驰。人们怀疑有陷门和政府部门肆意侵犯公民权利。此举遭到广为反对。
• 1995年5月AT&T Bell Lab的M. Blaze博士在PC机上用45分钟时间使SKIPJACK的 LEAF协议失败，伪造ID码获得成功。1995年7月美国政府宣布放弃用EES来加密数据，只将它用于语音通信。
• 1997年1月美国NIST着手进行AES（Advanced Encryption Standard）的研究，成立了标准工作室。2001年Rijndael被批准为AES标准
• DES（Data Encryption Standard）算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。这是IBM的研究成果。
• DES是第一代公开的、完全说明细节的商业级现代算法，并被世界公认。

  DES的框架和主要参数

• 分组长度为64 bits (8 bytes)
• 密文分组长度也是64 bits。
• 密钥长度为64 bits，有8 bits奇偶校验，有效密钥长度为56 bits。
• 算法主要包括：初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。

  初始置换IP与逆初始置换

• 初始置换是将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组。
• 逆初始置换$IP^{-1}$。将16轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。
• $IP$和$IP^{-1}$在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系。