第2章古典密码学
第2章 古典密码学
21古典密码学体制 21.1定义和分类 个密码系统( Cryptosystem)是一个五元组 (P,cK,E,D)满足条件: (1)P是可能明文的有限集;(明文空间) (2)C是可能密文的有限集;(密文空间) (3)K是一切可能密钥构成的有限集;(密钥空间) (4)任意有一个加密算法和相应的解密 算法k哽得 和 E分别为加密 解密函数,满足e:P→Cd:C→P。 (ek(x)=x,这里,x∈P
2.1古典密码学体制 2.1.1定义和分类 – 一个密码系统（Cryptosystem）是一个五元组 （P,C,K,E,D)满足条件： （1）P是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间） （4）任意 ,有一个加密算法 和相应的解密 算法 ，使得 和 分别为加密、 解密函数，满足 。 k K ek E dk D ek : P → C dk :C → P dk (ek (x)) = x,这里, x P
窃听者 Oscar Alice 加密 解密 Bob 安全信道 密钥源
x x Alice 加密 解密 密钥源 安全信道 窃听者Oscar k y Bob
实用密码体系 每个加密函数和每个解密函数应当能有效 地被计算。 即使看到密文串y,窃听者 Oscar确定所用 的密钥k或明文串x是不可行的。 已知密文串y的情况下试图计算密钥k的 过程称为密码分析( Cryptanalysis
• 实用密码体系 – 每个加密函数和每个解密函数应当能有效 地被计算。 – 即使看到密文串y，窃听者Oscar确定所用 的密钥k或明文串x是不可行的。 • 已知密文串y的情况下试图计算密钥k的 过程称为密码分析（Cryptanalysis）
古典密码学分类 代换( Substitution)密码和置换 ( Permutation)密码
• 古典密码学分类 – 代换（Substitution）密码和置换 （Permutation）密码
·2.1.2代换密码 将明文字母表抽象地表示为一个整数集Z0=01…q-1。在加密 通常将明文消息划分成长为L的消息单元,称为明文组,以m表示, 如m=(m,m…m-)m∈q0≤≤L-1。m也称作L一报文,它可以看作是 定义在z4上的随机变量 z=2×2nx…*×z(个)=m=(m,m…m1)m,∈2n0≤1≤L 这时明文空间P=z。密文字母表三抽象表示成整数集Z。=21…q 密文单元或组为c=(c0,c1…LL个)c∈2,0ssD-1。c是定义在z上的 随机变量。密文空间C=z。一般地,明文和密文由同一字母表构成。代 换密码可以看作是从Z到z的映射。L=1时,称作单字母代换,也称作 流密码(5 tream cipher)。L1时,称作多字母代换,亦称分组密码 ( Block cipher)
• 2.1.2 代换密码 将明文字母表Θ抽象地表示为一个整数集 。在加密时 通常将明文消息划分成长为L的消息单元，称为明文组，以m表示， 如 。 m也称作L－报文，它可以看作是 定义在 上的随机变量 这时明文空间 。密文字母表Ξ抽象表示成整数集 。 密文单元或组为 。c是定义在 上的 随机变量。密文空间 。一般地，明文和密文由同一字母表构成。代 换密码可以看作是从 到 的映射。L＝1时，称作单字母代换，也称作 流密码（Stream cipher）。L>1时，称作多字母代换，亦称分组密码 （Block cipher）。 Zq = 0,1, ,q −1 m = (m0 ,m1 , ,mL−1 ),ml Zq,0 l L −1 L Zq Z = Zq Zq Zq (L ) = m = (m0 ,m1 , ,mL−1 ) ml Zq ,0 l L −1 L q 个 L P = Zq 0,1, , 1 ' Z ' = q − q ( , , , )( , ,0 1 ' ' ' 0 1 1 = ' ' ' − − c c c c L c Z l L L 个） l q ' ' L q Z ' ' L q C = Z L Zq ' ' L q Z
1.单表代换密码 单表代换密码是对明文的所有字母都用 个固定的明文字母表到密文字母表的 映射,即∫:Z→2。令明文m=mm1…,则 相应地密文为c=e(m)=c0c1…=f(m)(m)…
1. 单表代换密码 单表代换密码是对明文的所有字母都用 一个固定的明文字母表到密文字母表的 映射，即 。令明文 ,则 相应地密文为 。 Zq Zq f : → m = m0 m1 c = e(m) = c0 c1 = f (m0 ) f (m1 )
几类简单的单表代换密码 移位密码( Shift cipher) 设P=C=K=2对0sk≤25,定义 e,(x)=x+k mod 26 且 dR(y)=y-k mod 26 (x,yE Z2)
• 几类简单的单表代换密码 – 移位密码（Shift Cipher） 设 定义 且 , 0 25, P = C = K = Z26 对 k ek (x) = x + k mod 26 ( ) 26 dk (y) = y − k mod 26 x, y Z
例2.1恺撒( Caesar)密码是k=3的情况。即通过简单的向右 移动源字母表3个字母则形成如下代换字母表 b c ef 三:DEFG|H|I K L MNOP S R S T UVWX BC 若明文为: please confirm receipt 则密文为: SOHDVE FRQILUP UHFHLSW
• 例2．1 恺撒（Caesar）密码是k＝3的情况。即通过简单的向右 移动源字母表3个字母则形成如下代换字母表 若明文为： please confirm receipt 则密文为：SOHDVE FRQILUP UHFHLSW Θ: a b c d e f g h i j k l m Ξ: D E F G H I J K L M N O P n o p q r s t u v w x y z Q R S T U V W X Y Z A B C
安全性分析 移位密码是极不安全的(mod26),因为 它可被穷举密钥搜索所分析:仅有26个可 能的密钥,尝试每一个可能的加密规则,直 到一个有意义的明文串被获得。平均地说, 个明文在尝试26/2=13解密规则后将显 现出来
• 安全性分析 – 移位密码是极不安全的（mod26），因为 它可被穷举密钥搜索所分析：仅有26个可 能的密钥，尝试每一个可能的加密规则，直 到一个有意义的明文串被获得。平均地说， 一个明文在尝试26/2＝13解密规则后将显 现出来