密码学-古典密码(2)

1、第二章、密码学 主要内容 密码学的历史发展过程 基本术语和定义 相关基础数学理论 古典密码 现代密码1、密码学的起源 隐写术(Steganography)：通过隐藏消息的存在来保护消息。常用的手段包括：隐形墨水、字符格式的变化、图形图像（水印）。1、密码学的起源 象形文字的修改(Modified Hieroglyphics)：密码学的第一个例子是对标准书写符号的修改，例如古埃及法老坟墓上的文字（3200-1100 B.C.），核心思想是代替(Substitution)1、密码学的起源 500 B.C.，斯巴达人在军事上用于加解密 发送者把一条羊皮纸螺旋形地缠在一个圆柱形木棒上，核心思想是置换（

2、Permutation）1、密码学的起源 205-123 B.C.，棋盘密码 1 2 3 4 5 1 A B C D E 2 F G H IJ K 3 L M N O P 4 Q R S T U 5 V W X Y Z HELLO 23153131341、密码学的起源 50 B.C.，恺撒密码HELLO KHOOR A B C D E F G X Y Z D E F G H I J A B C 2、密码学发展的三个阶段 1949年之前 古典密码 19491975年 传统密码 1976年以后 现代密码2、密码学发展的三个阶段 1949年之前 古典密码 密码学还不是科学，而是艺术 出现一些密码算法

3、和加密设备 密码算法的基本手段(代替 &置换)出现，针对的是字符 简单的密码分析手段出现 基于字符的密码2、密码学发展的三个阶段 代替密码（substitution cipher） 明文中的每个字符被替换成密文中的另外的字符。接收者对密文做反向替换就可以恢复出明文。 简单代替密码（单字母密码） 多字母密码 置换密码(permutation cipher)2、密码学发展的三个阶段 简单代替密码 明文的一个字符用相应的一个密文字符代替。 单表代换 一个明文字符对应固定的一个密文字符 可用频率分析的方法破解 多表代换 一个明文字符对应几个密文字符，加密时任选其中一个 可隐藏明文字母的统计信息

4、 增大了密文空间2、密码学发展的三个阶段 单表代替密码的频率分析2、密码学发展的三个阶段 多表代替密码的设计 出现频率高的字符用更多的密文来代替，以隐藏明文字母的统计信息 例如： a2,41,89 c9,38 k78 t1,8,43,66,91 明文ATTACK可加密为(2,1,8,41,9,78)或(41,43,91,38,78)2、密码学发展的三个阶段 多字母密码 明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。可以用矩阵变换方便地描述多字母代换密码，有时又称起为矩阵变换密码。 Playfair密码2、密码学发展的三个阶段 Playfair密码 将明文中的双字母组合作为一个单元

5、对待，并将这些单元转换为密文的双字母组合。采用55变换矩阵，如以CIPHER作密钥：C I P H ER A B D FG K L M NO Q S T UV W X Y Z加密规则：按成对字母加密 相同对中的字母加分隔符(如x)：balloon ba lx lo on 同行取右边: he EC, rb BF 同列取下边: dm MT, bs SP 其他取交叉: kt MQ, od TR2、密码学发展的三个阶段 Playfair密码分析： 有2626=676种字母对组合 字符出现几率一定程度上被均匀化 基于字母频率的攻击比较困难 依然保留了相当的结构信息2、密码学发展的三个阶段 代替密码（su

6、bstitution cipher） 置换密码（permutation cipher） 又称换位密码（transposition cipher) 明文的字母保持相同，但顺序被打乱了。2、密码学发展的三个阶段 换位密码（transposition cipher) 换位密码把明文按列写入，按行读出 密钥包含3方面信息: 行宽, 列高, 读出顺序密钥密钥:4 3 1 2 5 6 7明文明文:a t t a c k po s t p o n ed u n t i l tw o a m x y z密文：密文： TTNA APTM TSUO AODW COIX PETZ2、密码学发展的三个阶段 19491

7、975年 传统密码 计算机使得基于复杂计算的密码成为可能 Shannon, The Comm Theory of Secret Systems, 1949 David Kahn, The Codebreakers, 1967 J.L.Smith, A Cryptographic Device for Data Comm, 1971 H.Feistel, Cryptography and Computer Privacy, 1973 数据的安全基于密钥而不是算法的保密2、密码学发展的三个阶段 加密通信模型HelloHelloHello2、密码学发展的三个阶段 加密通信模型HelloHello加密

8、机解密机#$&#$&#$&密钥源安全信道安全信道2、密码学发展的三个阶段 1976年以后 现代密码 Diffie, Hellman. New Directions in Cryptography, 1976 1977年Rivest,Shamir & Adleman提出了RSA公钥算法 90年代逐步出现椭圆曲线等其他非对称算法 非对称密码使得无密钥传输的保密通信成为可能！ 对称密钥密码算法进一步发展 1977年DES加密算法正式成为标准 90年代RC6, MARS, Twofish, Serpent等加密算法出现 2001年Rijndael算法成为DES的替代者B

9、的公开密钥的公开密钥2、密码学发展的三个阶段 非对称密码加密通信模型HelloHello加密机解密机#$&#$&#$&公开密钥库B的私人密钥的私人密钥3、基础知识和基本术语 问题的描述 发送者(Sender)把消息(Message)传递给接收者(Receiver)，他想确保除接收者以外的任何人都不能阅读发送的消息。 消息的内容被称为明文(Plaintext)，用某种方法伪装消息以隐藏其内容的过程成为加密(Encrypt)或译成密码(Encipher) 被加密的消息成为密文(Ciphertext)，而把密文还原为明文的过程称为解密(Decrypt)或解译密码(Deciph

10、er)。3、基础知识和基本术语 密码学(Cryptology) 是研究信息系统安全保密的科学。是数学的一个分支，包括密码编码学和密码分析学。 密码编码学(Cryptography) 主要研究对信息进行编码，实现对信息的隐蔽。 密码分析学(Cryptanalytics) 主要研究加密消息的破译或消息的伪造。3、基础知识和基本术语 密码算法(Cryptography Algorithm) 是用于加密和解密的数学函数。 密码员对明文进行加密操作时所采用的一组规则称作加密算法(Encryption Algorithm)。 接收者对密文解密所采用的一组规则称为解密算法(Decryption Algori

11、thm)。3、基础知识和基本术语 密码算法的数学表达 明文用M或P表示，密文用C表示，加密函数E作用于M得到C，数学公式表示为：E(M) = C 相反地，解密函数D作用于C产生MD(C) = M 如果使用了密钥K，则可表示为：EK(M) = C; DK(C) = M3、基础知识和基本术语 密码系统（密码体制）的数学描述 它是一个五元组（P, C, K, E, D）满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）（4）E是加密算法的有限集，D是解密算法的有限集（5）对任意的kK，有一个加密算法ekE和相应的

12、解密算法dkD，使得ek: P-C 和dk: C-P分别为加密解密函数，满足dk(ek(x)=x，这里xP。4、密码算法的分类 按照明文的处理方法可分为分组密码(block cipher)和流密码(stream cipher) 分组密码将明文分成固定长度的组块，用同一密钥和算法对每一块加密，每块输出也是固定长度的密文。 流密码又称序列密码。序列密码每次加密一位或一字节的明文，是手工和机械密码时代的主流。4、密码算法的分类 按照保密的条件可分为受限制的（Restricted）算法和基于密钥（key-based）的算法 如果加脱密的保密性是基于保持算法的秘密，这种算法称为受限制的算法。 缺陷：无法

13、用于大的或经常变换的用户组织。 如果加脱密的保密性是基于保持密钥的秘密，而算法本身可以完全公开，则称为基于密钥的算法。基于密钥的算法通常有两类：对称算法和公开密钥算法。4、密码算法的分类 对称算法(Symmetric Algorithm)就是加密密钥和解密密钥相同或能相互推导的密码算法。 秘密密钥算法或单密钥算法，要求发送者和接收者在安全通信之前，商定一个密钥。 对称算法的安全性完全依赖于密钥，加密和解密表示为：EK(M) = CDK(C) = M4、密码算法的分类 公开密钥算法(Public Key Algorithm)就是加密密钥和解密密钥无法相互推导（至少在假定的长时间内）的密码算法。

14、加密密钥可以公开，任何人能用加密密钥加密信息，但只有相应的解密密钥才能解密信息。这里，加密密钥叫做公开密钥(Public Key)，用PuK表示EPuK(M) = C 解密密钥不可公开，只为解密者(接收方)个人所持有，因此叫做私人密钥(Private Key)或秘密密钥，用PrK表示DPrK(C) = M4、密码算法的分类 有些算法用私人密钥加密而用公开密钥解密，这种算法通常叫数字签名算法，可以表示为：EPrK(M) = CDPuK(C) = M5、密码分析方法 密码分析学是在不知道密钥的情况下，恢复出明文的科学。 分析者是在已知密码体制（密码算法及其实现的全部详细资料）的前提下来破译使用的密

15、钥。 常用的密码分析攻击有四类5、密码分析方法 四类常用的密码分析攻击方式 唯密文攻击(Ciphertext-only Attack) 分析者有一些消息的密文，这些密文都用同一加密算法加密，任务是尽可能恢复这些密文，或推算出加密的密钥。 已知明文攻击(Known-plaintext Attack) 分析者不但有一些消息的密文，还知道这些密文对应的明文，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法5、密码分析方法 四类常用的密码分析攻击方式 选择明文攻击(Chosen-plaintext Attack) 分析者可获得对加密机的暂时访问，因此他能自由选择明文串并构造出相应的密文串，任

16、务是推算出加密的密钥，或推导出可以对新密文进行解密的算法 选择密文攻击(Chosen-ciphertext Attack) 分析者可获得对解密机的暂时访问，因此他能自由选择密文串并构造出相应的明文串，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法6、密码算法的安全性 无条件安全（Unconditionally secure）： 无论破译者有多少密文，他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性。 唯一的算法是一次一密乱码本（One-time pad）6、密码算法的安全性 一次一密乱码本是一个大的、不重复的真随机密钥字母集，每个密钥字母加密一个明文字母，每个密钥仅对

17、消息使用一次。使用过的密钥销毁。 (PiKi) mod 26 = Ci 接收者有一个同样的密钥字母集，每个密钥字母脱密一个密文字母，使用过的密钥销毁。 (CiKi) mod 26 = Pi6、密码算法的安全性 一次一密乱码本使用过程发送者接收者+-乱码本乱码本乱码本乱码本6、密码算法的安全性 一次一密乱码本存在的问题 密钥必须随机，不能重复使用。 无法在高带宽的信道上使用。 1M带宽上通信24小时就需要90G的乱码本 必须保证发送者和接收者完全同步 不提供鉴别6、密码算法的安全性 计算上安全（Computationally secure）： 破译的代价超出信息本身的价值 破译的时间超出了信息的

18、有效期 用穷举法破解129位DES算法，平均需要2128次攻击尝试，以每秒100万次攻击尝试，用100万台PC并行处理，需要花费1019年（宇宙年龄的10亿倍）7、密码学相关基础数学 模运算 生活中的求模运算： 现在是3点钟，25小时以后是几点钟？52小时以后呢？ (52+3)24余7，52小时后应该是7点钟 今天是星期二，9天以后是星期几？90天以后呢？ (90+2)7余5，90天以后应该是星期五7、密码学相关基础数学 模运算和同余 给定任意整数a和q，以q除a，余数是r，则可以表示为a=sq+r, 0rq。 称q为模数，r为a模q的剩余，记为 ra mod q 若整数a和b有(a mod

19、q)=(b mod q)，则称a与b在模q下同余。(即a和b的差是q的倍数) 例如11和19在模4下同余(3)。7、密码学相关基础数学 模的逆元 求a对于模b的逆元，即求x满足ax mod b 1 ，可记做 x a-1 mod b 或 a x-1 mod b 如： 39 1 26 1 ，则称9和3对于模26互逆，记做9-1 mod 26 = 3或3-1 mod 26 = 9 将模数的倍数加1后分解为两个数的乘法，即可得到两个关于模数互逆的数。7、密码学相关基础数学 模运算举例 14342, 2是14模4的余，214 mod 4 （2也是14模3的余） 通常对rq的条件并不严格要求，如 1934

20、7，7 19 mod 4 负数亦可参与求模（保证余数大于零即可) (-13)(-4)43，3 (-13) mod 4 7(-3)419，19 7 mod 4 1(-1)1112， 12 1 mod 117、密码学相关基础数学 模运算的基本性质： 若q|(a-b)，则ba mod q。如113能被4整除，则3是11模4的余； (a mod q)=(b mod q)意味着ab mod q。如3 mod 4 = 11 mod 4，则3是11模4的余； ab mod q等价于ba mod q。如3是11模4的余，同时4是11模3的余； 若ab mod q且bc mod q，则ac mod q。如37

21、mod 4且711 mod 4，则311 mod 4 模运算满足交换律、分配律、结合律7、密码学相关基础数学 模算术（不要求rq） 加法：(a mod q)(b mod q) = (ab) mod q例：(3 mod 4)(7 mod 4) = 6 = 10 mod 4 乘法：(a mod q)(b mod q) = (ab) mod q例：(3 mod 4)(7 mod 4) = 9 = 21 mod 4 指数：an mod q = an-1 mod q a mod qamn mod q = (am mod q)n7、密码学相关基础数学 为什么引入模运算 模运算可将很大的数变成较小的数，同时

22、保持数的某些周期性的性质不变 比如1和32085在26下同余，都可以表示字母B 密码运算涉及指数、对数等大数的运算，模运算将运算的数值始终限定在一定范围内，利于计算机快速处理7、密码学相关基础数学 位的异或运算 0 0=0, 0 1=1, 1 01, 1 1=0 特性：两次异或运算以后还原，可设计加密和脱密完全相同的函数。 1918年，弗纳姆(Vernam)密码采用二进制数据： 加密：Ci = Pi Ki 解密：Pi = Ci Ki7、密码学相关基础数学 素数（质数）及其特性 大于1、只能被1和自己整除的数：如2、3、5、2521、2365347734339、27568391 公开密钥密码学常

23、用大的素数（512位或1024位） 512位的数以内，有超过10151个素数 费尔马小定理 如果m是一个素数，且a不是m的倍数，那么有： am-1 1 mod m 推论: m是素数，a是任意整数,则: am mod m a8、模运算用于数据加密 字母编码表，将字母AZ对应于数字0258、模运算用于数据加密 移位密码 定义加密函数为E(x)=(x + a) mod 26 = y 解密函数则为D(y)=(ya) mod 26 = x 当a=3时，即为恺撒密码 对移位密码的攻击最多尝试25次8、模运算用于数据加密 移位密码举例 已知移位密码加密函数为E(x)=(x + 5) mod 26，试加密明文TODAY 解答：TODAY可编码为19 14 3 0 24，经过加密函数运算可得24 19 8 5 3，即对应于密文字符YTIFD8、模运算用于数据加密 维吉尼亚（Vigenere）密码 是一种多表移位代替密码。密钥由序列K(k1, k2, , kd)给定，第i+td个明文字母由密钥ki决定： Ek(xi+td) = (xi+td+ki) mod 26 = yi+td Dk(yi+td) = (yi+td-ki) mod 26 = xi+td 当K的长度和X一样时，就成为滚动密钥密码 当K永远不重复时，就是一次一密乱码本8、模运算用于数据加密