《现代密码学第2章节经典密码学课件》由会员分享，可在线阅读，更多相关《现代密码学第2章节经典密码学课件（90页珍藏版）》请在金锄头文库上搜索。
1、1,经典密码学,现代密码学第2章,2,本章主要内容,1、密码体制的定义与分类 2、代替密码与移位密码 3、变换密码 4、乘积密码 5、密码机的发展历史,3,1. 密码体制的定义,一个密码体制是一个六元组： （M, C, K1, K2, E, D ) 其中， M -明文空间 C -密文空间 K1 -加密密钥空间 K2 -解密密钥空间 E -加密变换空间 D -解密变换空间,4,密码体制的理解,明文（plaintext)乃信息的原始形式， 一般是信息的基本单元（字母、数字或符号 等）的有限排列； 密文（cipher)乃明文经过加密以后的 结果形式，一般没有明确意义； 密钥（key)乃用于加解密变换
2、的关键信 息，视其用于加解密而分别称为加密密钥与 解密密钥；,5,密码体制的理解,一个加密变换乃一个下列形式的一一映 射：E: MK1 C 一般对于给定的kK1,把E(-,k)记为Ek; 一个解密变换乃对应一个加密变换E而 言，其实是一个以下形式的映射： D: CK2 M 并且适合（对于给定的kK2,也把 D(-,k)记为Dk）：,6,密码体制的理解,重要原则： 对任一kK1,都能找到k”K2,使得 Dk”(Ek(m)=m，mM。,7,一般性说明,我们常将26个英文字母(不区分大小写) 与整数025依次一一对应。 记 Zq=0,1,2, ,q-1 称之为模q剩余类环；当q为素数时，该环进 一步
3、形成为域，可改写为Fq 。,8,一般性说明,一般说来，一个密码体制的任一密钥 控制下的加密变换都要求把明文按n（最少必 要的固定数）个信息单元进行分组。照理， 一个密码体制的明文空间M应该是所有可能 明文的集合，但人们却习惯于把它写成前述 所有n个信息单元组的集合；如此，密文空间 C以及加解密变换的定义也有相应的变通。,9,简单密码举例,密码学的历史已有4000多年 古埃及人曾把象形文字写在石碑上,10,简单密码举例,例1. 凯撒（Caesar)密码 凯撒密码是古罗马人Julius Caesar发明 的一种密码体制，它是使用最早的密码体制 之一。 凯撒密码用于对英文信息进行加密，它 依据下列代
4、替表（由英文字母表左环移3位 得到）对信息中26个英文字母进行替换：,11,简单密码举例,若明文为： Substitution cryptosystem 则相应的密文是：,VXEVWLWXWLRQ FUBSWRVBVWHP,在上述凯撒密码体制中，英文字母代 替表即相当于密钥； 若将英文字母表左环移k(0k26)位 得到替换表，则得一推广的凯撒密码体制。,12,简单密码举例,练习 解密 “RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV“,13,简单密码举例,可写出推广凯撒密码体制的精确形式如 下： M=C =Z26 K1=K2= Z26 E=Ek|kK1 其中， E
5、k(m)= m+k (mod 26) ， mM ； D=Dk|kK2 其中， Dk(c)= c-k (mod 26)， cC 。,14,恺撒密码的一般形式,一般形式，可以把Caesar cipher 中字母移动的位数由3变为1-25中的任何一个。 可以指定一个密钥字母作为字母A的密文。 例如：密钥字母F表示： A F, B G, . Y D, Z E 即每个字母移动5位 共有26种可能的密码算法（25种可用）,15,Caesar密码分析（Cryptanalysis of Caesar ciphers）,只有 26 种可能（only have 26 possible ciphers ） A ma
6、ps to A,B,Z 可以简单的实验每个密钥（穷密钥搜索） 给定一些密文，实验每个密钥。 Original ciphertext LIZHZLVKWRUHSODFHOHWWHUV try shift of 1 KHYGYKUJVQTGRNCEGNGVVGTU try shift of 2 JGXFXJTIUPSFQMBDFMFUUFST try shift of 3 IFWEWISHTOREPLACELETTERS * plaintext HEVDVHRGSNQDOKZBDKDSSDQR try shift of 4 GDUCUGQFRMPCNJYACJCRRCPQ try shift of
7、 5 . MJAIAMWLXSVITPEGIPIXXIVW try shift of 25 eg. break ciphertext “GCUA VQ DTGCM“,16,语言冗余度与密码分析,人类语言是有冗余度的 字母使用的频率是不相同的 在英语中，e 的使用率是最高的 其次，T,R,N,I,O,A,S 其它字母使用的较低,17,英语字母使用频率,18,字母频率在密码分析中的应用,计算密文中字母出现的频率 与已知字母分布比较 单码替换不改变相对字母出现的频率 阿拉伯科学家提出此方法,19,英语字母中常见的组合,20,简单密码举例,例2. 简单移位密码 明文：transp ositio ncr
8、ypt osyste mxxxxx 密钥：=(352614) 密文： 上述将明文加密成密文的过程是： 将明文每个字母分成一组（最后不 够一组时用字母x补足）； 作为密钥的置换的定义如下： 31, 52, 23, 64, 15, 46 依据置换重新排列每组明文。,ASRPTN IISOOT RPCTNY YTSEOS XXXXMX,21,简单密码举例,上述简单移位密码体制的精确形式是： M=C =m1m2m6 | miZ26, i=1,2, ,6 K1=K2= S6（6次对称群） E=E|K1 其中，E(m1m2m6)=m(1)m(2) m(6)； D=D|K2 其中，D(c1c2c6)=c(1
9、)c(2) c(6)（为 的逆置换）。,22,密码体制的分类,依据信息元素的形态分类 对一个密码体制，考察其任一密钥控制 下的加密变换：若任意密文c=c1c2cn的各信息 元素ci均是相应明文m=m1m2mn的各信息元 素mi的某种排列，则称该种密码为移位密 码； 否则，即存在密文c=c1c2cn的各信息元素 ci不是相应明文m=m1m2mn的各信息元素 mi的某种排列，称该种密码为代替密码。,代替密码(如例1） 移位密码(如例2）,23,密码体制的分类,移位密码的特点：移位密码的加密变换 使得信息元素只有位置变化而形态不变，如此 可以打破消息中的某些固定模式（结构）。 代替密码的特点：代替密
10、码的加密变换 使得信息元素的形态有所变化，如此可以使明 文与密钥的信息混乱在一起，使局外人很难确 定明文和密钥是如何变换成密文的。,24,密码体制的分类,依据对信息元素的处理方式分类,序列(流)密码 分组(块)密码,一个密码体制的明文必要分组长度n 若为1，则称该密码为序列（流）密码，否 则（即n1）称该密码为分组（块）密码。,25,密码体制的分类,序列（流）密码的特点：加解密速度 快，无错误扩散；一般用于实际的安全产 品。 分组（块）密码的特点：适合数据库 加密，组内有错误扩散；一般用于公开的 理论研究。,26,密码体制的分类,依据密钥分类,单钥密码(传统密码，对称钥密码） 双钥密码(公钥密
11、码,非对称钥密码),基于计算复杂性，人们可以设计出这样的密码 体制：加密变换与相应的解密变换分别使用不同的 密钥k与k”，并且 kk” 在计算上不可行（尽管理论上应该能够）。如此， 用户选择该体制的一对加解密密钥(k,k”)后，可 以将前者公开而后者私存。区别于传统上加解密密 钥一致或相近而必须都保密的观念,称之为非对称( 公开)钥密码体制。,27,密码体制的分类,一般说来，单钥密码体制（包括分组、序列密 码）都是基于计算安全性的，而双钥密码体制是基于可证明安全性的。这两种安全性都是从计算量来考虑，但不尽相同。计算安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译它的计算量
12、不低于解已知数学难题的计算量。,28,密码体制的分类,单钥密码优点：运行速度快，具有可靠的保 密强度； 不足：不便密钥交换和管理。 双钥密码优点：便于密钥交换和管理，还可 用于消息认证（数字签名）； 不足：运行速度缓慢，其安全性所 依赖的数学难题的复杂性一般都未能证明。,29,早期密码体制大都比较简单，其中许 多经不起计算机的破译攻击。这些体制一般 都是直接针对原始的信息单元（字母或符号 等）设计，而并不象现代密码体制那样非常 重视和体现信息的数字化与数学处理。 但对早期密码体制的讨论可以说明构造和破译的基本原理和方法，对于理解、构造和分析现代复杂的实用密码体制有着起码的利益。,2. 代替密码
13、,30,早期密码体制基本上可以按照下述分 类笼统起来： 代替密码 移位密码 以下我们便按照这样的分类来依次学习早 期的密码体制及其破译。,2. 代替密码,31,2. 代替密码,一个代替密码，若其任何密文可以看成 是对相应明文的各组信息单元使用同一个代 替表进行替换而得到，则称其为单表代替密 码； 否则，即有密文是依次对相应明文的各 组信息单元使用有限个周期性重复的或无限 多的固定代替表进行替换而得到，称其为多 表代替密码。,32,单表代替密码,每个字母可以用其它任何一个字母替换（不能重复） 每个字母可以随机的映射到其它一个 因此密钥长度是26个字母 单字母替换密码（ Monoalphabeti
14、c Substitution Cipher ） 例如： 明文: ABCDEFGHIJKLMNOPQRSTUVWXYZ 密文: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: IFWEWISHTOREPLACELETTERS Ciphertext: WIRFRWAJUHYFTSDVFSFUUFYA,33,单表代替密码举例,给定密钥字 “STARWARS”，去掉重复字母得到 “STARW”，填写剩余字母： STARW BCDEF GHIJK LMNOP QUVXY Z 按列读取字母得到密文： Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Ciphe
15、r: SBGLQZTCHMUADINVREJOXWFKPY 可以用这个密钥加密、解密 例如 Plaintext: I KNOW ONLY THAT I KNOW NOTHING Ciphertext: H UINF NIAP OCSO H UINF INOCHIT,34,单表代替密码,需要一种简单方法指定密钥。 有多种方法，一种简单方法是写没有重复字母的“密钥字”，其它字母按顺序写在密钥字最后字母后面。 例如， 给定密钥字 “JULIUSCAESAR“ Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher: JULISCASRTVWXYZBDFGHKMNOPQ,35
16、,单表代替密码的密码分析,根据频率统计进行分析，确定每个字母被映射到什么字母，单个字母出现的可能是A或I（since know single words are A or I ） 一般来说个字母出现的可能是THE或AND，还可以用其他通常出现的双字母或三字母组合。 还可以应用其它很少应用的字母,36,单表代替密码构造方法,举例 例1. 一个英文单表代替密码 例2. 方格密码 例3. 普莱费尔(Playfair)密码 构造方法 构造单表代替密码的关键是构造一张明 密代替表(可能以对应Z26的观点写成一个数 学公式)。 以后不加声明，总假定M=C =a,b, c,z(记为A ), Z26, 或它们的n-直积。,37,单表代替密码构造方法,密钥字法 该法形成
