密码的加密与解密的密码的加密与解密的数学模型数学模型密码的加密与解密密码学的基本概念密码学基本模型发送方接收方Encryption加密Decryption解密加密：c= EK (m)解密：m= DK (c)不安全信道密码分析（Cryptanalysis）Plaintext 明文Key解密密匙Key加密密匙Plaintext 明文Ciphertext 密 文 密码的加密与解密明文用明文用M M（MessageMessage，消息）或，消息）或P P（PlaintextPlaintext，明文），明文）表示，它可能是比特流、文本文件、位图、数字化的表示，它可能是比特流、文本文件、位图、数字化的语音流或者数字化的视频图像等。语音流或者数字化的视频图像等。密文用密文用C C（CipherCipher）表示，也是二进制数据，有时和）表示，也是二进制数据，有时和M M一样大，有时稍大。通过压缩和加密的结合，一样大，有时稍大。通过压缩和加密的结合，C C有可能有可能比比P P小些。小些。加密函数加密函数E E作用于作用于M M得到密文得到密文C C，用数学公式表示为：，用数学公式表示为：E E（M M）=C=C。解密函数。解密函数D D作用于作用于C C产生产生M M，用数据公式表示，用数据公式表示为：为：D D（C C）=M=M。先加密后再解密消息，原始的明文将。先加密后再解密消息，原始的明文将恢复出来，恢复出来，D D（E E（M M）=M=M必须成立。必须成立。密码的加密与解密置换密码置换密码Caesar Caesar 密码密码 ABCDEFGHIGKLMNOPQRSTUVWXYZABCDEFGHIGKLMNOPQRSTUVWXYZDEFGHIGKLMNOPQRSTUVWXYZABCDEFGHIGKLMNOPQRSTUVWXYZABCCaesar was a great soldierCaesar was a great soldier密码本密码本密文密文Fdhvdu zdv d juhdw vroglhuFdhvdu zdv d juhdw vroglhu明文明文密文密文CAESAR CAESAR 密码密码 ： c=( m+ 3) Mod 26 c=( m+ 3) Mod 26A A B B C C D D E E F F J J H H I I J J K K0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010密码的加密与解密仿射变换密码仿射变换密码上面移位置换密码的一个简单变种就是仿射变换密码，上面移位置换密码的一个简单变种就是仿射变换密码，其数学表示为其数学表示为在上面例子移位置换密码下，明文中相邻的字母对应的在上面例子移位置换密码下，明文中相邻的字母对应的密文字母也是相邻的，如密文字母也是相邻的，如A A和和B B对应的密文字母分别为对应的密文字母分别为D D和和E,E,但在仿射变换下，但在仿射变换下， 对应的密文字母分别为对应的密文字母分别为F(F(3*0+5)mod26=5=F3*0+5)mod26=5=F) )和和I I，它们有，它们有3 3个字母的间隔个字母的间隔(a=3)(a=3)密码的加密与解密密码的加密与解密例例8.38.3假设下面是仿射变换加密的，试破译此文假设下面是仿射变换加密的，试破译此文FSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHKFSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHKFSPVM RDSKA RLVUU RRIFE FKKAN EHOFZ FUKRE SVVSFSPVM RDSKA RLVUU RRIFE FKKAN EHOFZ FUKRE SVVS假设此问题由假设此问题由2626个英文字母组成，取个英文字母组成，取m=26.m=26.由于与由于与2626互素，互素，a a有有1212种种不同的取法，不同的取法，b b有有2626种不同的取法，所以放射变换有种不同的取法，所以放射变换有12*26=32112*26=321种。种。可采取穷举法来破译。可采取穷举法来破译。可以用频率法，即密文中出现次数最多的字母与英文中最常见的字母可以用频率法，即密文中出现次数最多的字母与英文中最常见的字母对应。对应。在密文中在密文中 在平常统计中在平常统计中F F：出现：出现1212次次 E E：出现频率：出现频率 13.04% 13.04%R R：出现：出现1212次次 T T：出现频率：出现频率 13.04% 13.04%S S：出现：出现9 9次次 Z Z：出现频率：出现频率 0.08% 0.08%K K：出现：出现8 8次次 密码的加密与解密密码的加密与解密密码的加密与解密GTGAE RCSGT KESRE RKLGU GXDER TMMTGTGAE RCSGT KESRE RKLGU GXDER TMMT利用上述解密公式对密文进行解密得到：利用上述解密公式对密文进行解密得到：这是一串没有意义的字符串，解密失败这是一串没有意义的字符串，解密失败密码的加密与解密最后破译文为ANAME RICAN SECRE TAGEN TWILL MEETA NAFGH ANISTANMOL EINTH ECOFF EEBAR ATTHU RSDAY AFTER NOON即AN AMERICAN SECRET AGENT WILL MEET AN AFGHANISTAN MOLE IN THE COFFEE BAR AT THURSDAY AFTERNOON破译成功密码的加密与解密HILL密码q HillHill2 2密码中所用的数学手段是密码中所用的数学手段是矩阵运算矩阵运算。q 加密过程：加密过程：1 1）将英文的）将英文的2626个字母个字母与与0 0到到2525之间的整数建立一一对应之间的整数建立一一对应关系，称为字母的关系，称为字母的表值表值，然后根据明文字母的表值，将，然后根据明文字母的表值，将明文信息用数字表示。设明文信息只用明文信息用数字表示。设明文信息只用2626个大写字母表个大写字母表示，通讯双方给出这示，通讯双方给出这2626个字母的表值如下：个字母的表值如下：ABCDEFGHIJKLM 2345678910 11 12NOPQRSTUVW XYZ13 14 15 16 17 18 19 20 21 22 23 24 25密码的加密与解密2 2）选择一个二阶可逆整数方阵）选择一个二阶可逆整数方阵A，称为，称为HillHill2 2密码的加密码的加密矩阵，它是加密体制的密矩阵，它是加密体制的“密钥密钥”，是加密的关键，是加密的关键，仅仅通讯双方掌握通讯双方掌握。3 3）将明文字母分组。）将明文字母分组。 Hill Hill2 2 使用的是二阶矩阵，所以使用的是二阶矩阵，所以将明文字母每将明文字母每2 2个一组（可以推广至个一组（可以推广至HillHilln n密码），若最密码），若最后仅有一个字母，则补充一个没有实际意义的哑字母。后仅有一个字母，则补充一个没有实际意义的哑字母。这样使得每组都有这样使得每组都有2 2个字母，查出每个字母的表值，构个字母，查出每个字母的表值，构成一个二维列向量成一个二维列向量 。4 4）令）令 ，由，由 的两个分量反查字母表值得到的的两个分量反查字母表值得到的两个字母即为密文字母。两个字母即为密文字母。密码的加密与解密q 解密过程：加密过程的逆过程。解密过程：加密过程的逆过程。字母字母（明文）（明文）表值表值一组数一组数分组分组向量向量A A左左乘乘向量向量反查表值反查表值密文密文ILLILL密码的数学模型密码的数学模型密码的加密与解密例：设明文为“MEET求这段明文的 Hill2 密文。将明文分为： ME ET对应密文UUQR密码的加密与解密密码的加密与解密设方阵 满足命题8.1的条件容易验证密码的加密与解密对上面例子对上面例子,det(A)=5,det(A)=5,它与它与2626互素，所以满足互素，所以满足8.18.1的条件，故的条件，故A A关于模关于模2626的逆为的逆为密码的加密与解密对密文对密文UUQRUUQR进行解密得到进行解密得到即明文MEET密码的加密与解密HillHill密码的加密与解密过程类似于在密码的加密与解密过程类似于在n n维向量维向量空间中进行线性变换及其逆变换。每个明空间中进行线性变换及其逆变换。每个明文向量是一个文向量是一个Z Zm m上的上的n n维向量，乘以加密矩维向量，乘以加密矩阵并对阵并对m m取余，仍为取余，仍为Z Zm m上的一个上的一个n n维向量。由维向量。由于加密矩阵于加密矩阵A A为模为模m m的可逆矩阵，所以如果的可逆矩阵，所以如果知道了知道了n n个线性无关的个线性无关的n n维明文向量及其对维明文向量及其对应的密文向量，就可以求出它的加密矩阵应的密文向量，就可以求出它的加密矩阵A A及其模及其模m m的逆矩阵的逆矩阵A A-1-1(mod)(mod)例子详见例子详见P88,P88,例例8.58.5密码的加密与解密公开密钥系统Hill密码的加密和解密都只需要加密矩阵这个密钥就可以了。这种系统称为单密钥系统。如果加密和解密使用两个不同的密钥，则称为双密钥系统，也称为公开密钥系统。密钥的拥有者将其中一个密钥公开，另一个保密。双密钥系统（1）W.Diffie 和 M.Hellman最早提出 （2）R.L.Rivest, A.Shamir和 L.Adleman 提出第一个方法双密钥系统的程序是这样的收方先告诉发方如何把情报制成密码（敌人也听到）发方依法发出情报的密文（敌人也可能收到密文）收方将密码还原成原文（敌人却解不开密文）密码的加密与解密公钥密码系统的加密原理每个通信实体有一对密钥（公钥，私钥）。公钥公开，用于加密，私钥保密，用作解密A向B 发送消息，用B的公钥加密B收到密文后，用自己的私钥解密PlainText加密算法解密算法ABcipherPlainTextB的私钥C的公钥B的公钥任何人向B发送信息都可以使用同一个密钥(B的公钥)加密没有其他人可以得到B 的私钥，所以只有B可以解密密码的加密与解密公钥密码系统的签名原理公钥密码系统的签名原理A A向向B B 发送消息，用发送消息，用A A的私钥加密（签名）的私钥加密（签名）B B收到密文后，用收到密文后，用A A的公钥解密（验证）的公钥解密（验证）PlainText加密算法解密算法cipherPlainTextABA的私钥A的公钥密码的加密与解密3.3.2 RSA3.3.2 RSA算法简介算法简介Ron Rivest, Adi Shamir , Leonard Ron Rivest, Adi Shamir , Leonard AdlemanAdlemanRSARSA的安全性基于大数分解的难度的安全性基于大数分解的难度RSARSA在美国申请了专利（已经过期），在其在美国申请了专利（已经过期），在其他国家没有他国家没有RSARSA已经成了事实上的工业标准，在美国除已经成了事实上的工业标准，在美国除外外密码的加密与解密数论基础数论基础a a与与b b的最大公因数：的最大公因数：gcd (a, b)gcd (a, b)gcd(20, 24)=4 , gcd (15, 16)=1gcd(20, 24)=4 , gcd (15, 16)=1如果如果gcd(a, b)=1 gcd(a, b)=1 ，称，称a a与与b b 互素互素模运算模运算 mod moda= q n +r 0rn ; q=a/n ;a= q n +r 0rn ; q=a/n ; x x 表示小于或等于表示小于或等于x x的最的最大整数大整数a=a/nn + (a mod n) , r = m mod n a=a/nn + (a mod n) , r = m mod n 如果如果 (a mod n )= (b mod n) (a mod n )= (b mod n) ，则称则称a a 与与b b 模模n n同余同余，记为记为 a a b mod n b mod n 例如，例如， 23 8 mod 5 , 8 1 mod 7 23 8 mod 5 , 8 1 mod 7密码的加密与解密数论基础（续）数论基础（续）模运算是可交换的、可结合的、可分配的模运算是可交换的、可结合的、可分配的(a+b) mod n = (a mod n ) + (b mod n) ) mod n(a-b) mod n = ( (a mod n) (b mod n) ) mod n(ab) mod n = ( (a mod n ) （b mod n) ) mod n (a (b+c) ) mod n = （( a b) mod n + (a c) mod n）mod n幂,模运算 ma mod n m2 mod n = (mm) mod n = (m mod n ) 2 mod n m4 mod n = (m2 mod n ) 2 mod n m8 mod n = ( (m2 mod n )2 mod n )2 mod n m25 mod n = (m m8 m16) mod n 密码的加密与解密数论基础（续）数论基础（续）欧拉函数欧拉函数(n) (n) n n是正整数，是正整数， (n) (n) 是比是比n n小且与小且与n n 互素的正整数的个互素的正整数的个数数(3)=|(3)=|1, 2| =21, 2| =2 (4)=|(4)=|1, 3| =21, 3| =2 (5)=|(5)=|1, 2, 3, 4 | =41, 2, 3, 4 | =4 (6)=|(6)=|1, 5| =41, 5| =4 (7)=|(7)=|1, 2, 3, 4, 5, 6| =61, 2, 3, 4, 5, 6| =6(10)=|(10)=|1, 3, 7, 9| =41, 3, 7, 9| =4 (11)=|(11)=|1, 2,3,4,5,6, 7,8, 9,10| =101, 2,3,4,5,6, 7,8, 9,10| =10 如果如果p p是素数，则是素数，则(p)=p-1, (p)=p-1, 比如比如(2), (5)(2), (5)， (11)(11)如果如果p,q p,q 是素数，则是素数，则(pq)=(p) (q)(pq)=(p) (q) (p-1)(q- (p-1)(q-1) 1) 。比如，。比如，(10)= (10)= （2*52*5）= = （2 2） （5 5）=1*4=4=1*4=4密码的加密与解密数论基础（续）数论基础（续）例如：例如： m=3, n=10; m=3, n=10; (10)=4(10)=4 m m(n)(n)=3=34 4=81 ; 81 mod 10 = 1=81 ; 81 mod 10 = 1 即即 81 1 mod 10 81 1 mod 10 3 34+14+1 = 243 3 mod 10 = 243 3 mod 10 欧拉定理欧拉定理 若整数若整数m 和和n 互素，则互素，则等价形式等价形式密码的加密与解密数论基础（续）数论基础（续）推论：给定两个素数推论：给定两个素数p, qp, q , , 两个正整数两个正整数 n n, , m m ，使得，使得n=pq, 0mnn=pq, 0mn ； 则对于任则对于任意正整数意正整数k k ，下列关系成立：，下列关系成立： m m k k(n)+1(n)+1 m mod n m mod n密码的加密与解密RSARSA算法操作过程算法操作过程密钥产生密钥产生1. 1. 取两个大素数取两个大素数 p, q , p, q , 保密保密; ; 2. 2. 计算计算n=pqn=pq，公开公开n; n; 3. 3. 计算欧拉函数计算欧拉函数(n) =(n) =（p-1p-1）(q-1)(q-1)；4. 4. 任意取一个与任意取一个与(n) (n) 互素的小整数互素的小整数e, e, 即即 gcd (e, (n) )=1; 1e (n)gcd (e, (n) )=1; 1e (n) e e作为公钥公开作为公钥公开; ;5. 5. 寻找寻找d, d, 使得使得 de de 1 mod (n) 1 mod (n) , , ed ed = =k k (n) +(n) +1 1 d d 作为私钥保密。作为私钥保密。p=7,q=17n=119(n)=96选择e=55d=k961令 k=4, 得到求得d=77密码的加密与解密RSA RSA 算法加密算法加密/ /解密过程解密过程密钥对（密钥对（KU, KRKU, KR）: :KU=e, n , KR=KU=e, n , KR=d d, n, n加密过程加密过程把待加密的内容分成把待加密的内容分成k k比特的分组，比特的分组，k logk log2 2n n，并写成数字，设为，并写成数字，设为M,M,则：则：C= MC= Me e mod n mod n解密过程解密过程M = CM = Cd d mod n mod n 5,11977,119c=m5 mod 119m=c77 mod 119密码的加密与解密RSARSA加密过程举例加密过程举例1.1.p=7,q=17, n=7*17=119p=7,q=17, n=7*17=1192.2.(n(n)=(7-1)=(7-1)(17-1)=96(17-1)=963.3.选选 e=5, e=5, gcdgcd (e, (e, (n(n) = ) = gcdgcd (5, 96)=1;(5, 96)=1;4.4.寻找寻找 d d，使得使得 ed 1 mod 96 , ed 1 mod 96 , 即即 ed= k*96+1, ed= k*96+1, 取取 d= 77 d= 77 5.5.公开公开( (e,ne,n)=(5, 119)=(5, 119)6.6.将将d d 保密，丢弃保密，丢弃p, qp, q；7.7.加密：加密：m=19 m=19 19 19 5 5 66 mod 119 , c= 66 66 mod 119 , c= 66解密解密 66667777 modmod 119 =? 119 =? 密码的加密与解密