密码的加密与解密模型

1、密码的加密与解密的数学模型Author： C. Z. NiuOffice： #1-403Email: 密码学的基本概念密码学的基本概念v 密码学基本模型密码分析（Cryptanalysis）接收方Plaintext 明文Decryption解密Key解密密钥Encryption加密Key加密密钥发送方Plaintext 明文不安全信道Ciphertext 密 文 加密：( )KCEm解密：( )KmDC先加密后再解密消息，原始的明文将恢复出来，先加密后再解密消息，原始的明文将恢复出来， D D（E E（M M）=M.=M.密文用密文用C C（CipherCipher）表示，也是二进制数据，有时

2、和）表示，也是二进制数据，有时和M M一样一样大，有时稍大大，有时稍大. .通过压缩和加密的结合，通过压缩和加密的结合，C C有可能比有可能比P P小些小些. .明文用M(Message,消息)或P(Plaintext,明文)表示，它可能是比特流、文本文件、位图、数字化的语音流或数字化的视频图像等.加密函数加密函数E作用于作用于M得到密文得到密文C，用数学公式表示为：，用数学公式表示为： E（M）=C.解密函数解密函数D作用于作用于C产生产生M，用数据公式表示为：，用数据公式表示为： D（C）=M.置换密码Caesar Caesar 密码密码 ABCDEFGHIJKLMNOPQRSTUVWXY

3、ZABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIGKLMNOPQRSTUVWXYZABCDEFGHIGKLMNOPQRSTUVWXYZABCCaesar was a great soldierCaesar was a great soldier密码本密码本密文密文Fdhvdu zdv d juhdw vroglhuFdhvdu zdv d juhdw vroglhu明文明文密文密文CAESAR CAESAR 密码密码 ： c=( m+ 3) Mod 26c=( m+ 3) Mod 26A AB BC CD DE EF FJ JH HI IJ JK K0 01 12 23 34

4、 45 56 67 78 89 91010仿射变换密码上面移位置换密码的一个简单变种就是仿射变换密码，上面移位置换密码的一个简单变种就是仿射变换密码，其数学表示为其数学表示为互素必需与模其中自然数mambapc)(mod在上面例子移位置换密码下，明文中相邻的字母对应的在上面例子移位置换密码下，明文中相邻的字母对应的密文字母也是相邻的，如密文字母也是相邻的，如A A和和B B对应的密文字母分别为对应的密文字母分别为D D和和E,E,但在仿射变换下，但在仿射变换下， 对应的密文字母分别为对应的密文字母分别为F(F(3 3* *0+5)mod26=5=F0+5)mod26=5=F) )和和I I，它

5、们有，它们有3 3个字母的间隔个字母的间隔(a=3)(a=3)26(mod53 pc11111(mod),1(mod),() (mod)apcbmamaaamapacbmamama仿射变换的解密公式可通过求解同余方程得到记整数 关于模 的同余逆为即对上式两边同乘得Remark:只有 与 互素，才可能存在 关于模 的同余逆例假设下面是仿射变换加密的，试破译此文假设下面是仿射变换加密的，试破译此文FSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHKFSFPR EDLFS HRLER KFXRS KTDMM PRRKF SFUXA FSDHKFSPVM RD

6、SKA 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种不同的取法，所以放射变换有种不同的取法，所以放射变换有1212* *26=32126=321种。种。可采取穷举法来破译。可采取穷举法来破译。可以用频率法，即密文中出现次数最多的字母与英文中最常见的字母可以用频率法，即密文中出现次数最多的字母与英文

7、中最常见的字母对应。对应。在密文中在密文中 在平常统计中在平常统计中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次次 -1(5)(4),(17)(19),54(mod26)17 19(mod26)12 15 (mod26)a1512(mod26)7 12(mod26)6(mod26)FERTa ba ba （1）如令对应对应得同余式这样有：所以：a=6与26不互素，所以无

8、法对密文解密。-1(17)(5),(18)(19),174(mod 26)1819(mod 26)115 (mod 26)a151(mod 26)7 1(mod 26)7 (mod 26)17-4 7 (mod 26)11(mod 26)15(mod 26)715(mod 26)159 (mod 26)RESTabababcppc （2）如令对应对应得同余式这样有：所以：a=7我们可得到加密公式:解密公式:GTGAE RCSGT KESRE GTGAE RCSGT KESRE RKLGU GXDER TMMT RKLGU GXDER TMMT利用上述解密公式对密文进行解密得到：利用上述解密公式

9、对密文进行解密得到：这是一串没有意义的字符串，解密失败！这是一串没有意义的字符串，解密失败！(17)(5),(10)(19),174(mod 26)1019(mod 26)35(mod 26),35(mod 26),39(3*91mod 26)9(5) (mod 26)97 (mod 26)REKTababcppcpcc（3）如令对应对应得同余式我们可得到加密公式解密公式因 的同余逆所以解密公式为：最后破译文为ANAME RICAN SECRE TAGEN TWILL MEETA NAFGH ANISTANMOL EINTH ECOFF EEBAR ATTHU RSDAY AFTER NOON

10、即AN AMERICAN SECRET AGENT WILL MEET AN AFGHANISTAN MOLE IN THE COFFEE BAR AT THURSDAY AFTERNOON破译成功HILL密码密码q Hill Hill2 2密码中所用的数学手段是密码中所用的数学手段是矩阵运算矩阵运算。q 加密过程：加密过程：1 1）将英文的）将英文的2626个字母个字母与与0 0到到2525之间的整数建立一一对应之间的整数建立一一对应关系，称为字母的关系，称为字母的表值表值，然后根据明文字母的表值，将，然后根据明文字母的表值，将明文信息用数字表示。设明文信息只用明文信息用数字表示。设明文信息

11、只用2626个大写字母表个大写字母表示，通讯双方给出这示，通讯双方给出这2626个字母的表值如下：个字母的表值如下：ABCDEFGHIJKLM23456789101112NOPQRSTUVWXYZ131415161718192021222324252 2）选择一个二阶可逆整数方阵）选择一个二阶可逆整数方阵A，称为，称为HillHill2 2密码的加密码的加密矩阵，它是加密体制的密矩阵，它是加密体制的“密钥密钥”，是加密的关键，是加密的关键，仅仅通讯双方掌握通讯双方掌握。3 3）将明文字母分组。）将明文字母分组。 HillHill2 2 使用的是二阶矩阵，所以使用的是二阶矩阵，所以将明文字母每将

12、明文字母每2 2个一组（可以推广至个一组（可以推广至HillHilln n密码），若最密码），若最后仅有一个字母，则补充一个没有实际意义的哑字母。后仅有一个字母，则补充一个没有实际意义的哑字母。这样使得每组都有这样使得每组都有2 2个字母，查出每个字母的表值，构个字母，查出每个字母的表值，构成一个二维列向量成一个二维列向量 。4 4）令）令 ，由，由 的两个分量反查字母表值得到的的两个分量反查字母表值得到的两个字母即为密文字母。两个字母即为密文字母。Aq 解密过程：加密过程的逆过程。解密过程：加密过程的逆过程。字母字母（明文）（明文）表值表值一组数一组数分组分组向量向量A A左左乘乘向量向量反

13、查表值反查表值密文密文ILLILL密码的数学模型密码的数学模型例例：设明文为：设明文为“MEET”, 求这段明文的求这段明文的 HillHill2 2 密文。密文。5021A将明文分为： ME ET对应密文 UUQR对应的列向量为124,419左乘矩阵A后的向量为2042,2095关于26取模2016,2017110,1, 2,1.ABABBAI (mod m)AmBAm(mod)mmmmZmZnZnBAm定义设 为一正整数，记整数集合对于一个元素属于的 阶方阵 ，若存在一个元素属于的 阶方阵 ，使得称 为模 可逆。 为 的模 逆矩阵，记为11det( )1det1AA (mod)mmZAmm

14、AAZAmmAm命题 元素属于的方阵 模 可逆的充要条件是： 和没有公共的素数因子。推论 若方阵 的每个元素属于，而且则 是模 可逆的，且它的逆矩阵就是 的模 逆矩阵。dcbaA)(mod)(11macbdbcadA设方阵 满足命题1的条件容易验证11()(mod)adbcadbcmAmAm其中是关于模 的同余逆。于是方程组在模 意义下的解为对上面例子对上面例子,det(A,det(A)=5,)=5,它与它与2626互素，所以满足互素，所以满足命题命题1 1的条件，故的条件，故A A关于模关于模2626的逆为的逆为1152525(mod 26)21(mod 26)(521)0 10 11054

15、21 10(mod 26)(mod 26)0210 21A因为 的同余逆11 10(mod)(mod 26)0 21Am解密公式为：对密文对密文UUQRUUQR进行解密得到进行解密得到)26(mod1943571861716210101)26(mod4124202202020210101即明文MEETHillHill密码的加密与解密过程类似于在密码的加密与解密过程类似于在n n维向量空间维向量空间中进行线性变换及其逆变换。每个明文向量是一中进行线性变换及其逆变换。每个明文向量是一个个Z Zm m上的上的n n维向量，乘以加密矩阵并对维向量，乘以加密矩阵并对m m取余，仍取余，仍为为Z Zm m

16、上的一个上的一个n n维向量。由于加密矩阵维向量。由于加密矩阵A A为模为模m m的可的可逆矩阵，所以如果知道了逆矩阵，所以如果知道了n n个线性无关的个线性无关的n n维明文维明文向量及其对应的密文向量，就可以求出它的加密向量及其对应的密文向量，就可以求出它的加密矩阵矩阵A A及其模及其模m m的逆矩阵的逆矩阵A A-1-1(mod)(mod)公开密钥系统公开密钥系统Hill密码的加密和解密都只需要加密矩阵这个密钥就可以了。这种系统称为单密钥系统。如果加密和解密使用两个不同的密钥，则称为双密钥系统，也称为公开密钥系统。密钥的拥有者将其中一个密钥公开，另一个保密。双密钥系统（1）W.Diffi

17、e 和 M.Hellman最早提出 （2）R.L.Rivest, A.Shamir和 L.Adleman 提出第一个方法双密钥系统的程序是这样的收方先告诉发方如何把情报制成密码（敌人也听到）发方依法发出情报的密文（敌人也可能收到密文）收方将密码还原成原文（敌人却解不开密文）公钥密码系统的加密原理公钥密码系统的加密原理v 每个通信实体有一对密钥（公钥，私钥）。公钥公开，用于加密，私钥保密，用作解密v A向B 发送消息，用B的公钥加密v B收到密文后，用自己的私钥解密cipher加密算法B的公钥解密算法BPlainTextB的私钥PlainTextA任何人向B发送信息都可以使用同一个密钥(B的公钥

18、)加密没有其他人可以得到B 的私钥，所以只有B可以解密公钥密码系统的签名原理vA A向向B B 发送消息，用发送消息，用A A的私钥加密（签名）的私钥加密（签名）vB B收到密文后，用收到密文后，用A A的公钥解密（验证）的公钥解密（验证）PlainText加密算法解密算法cipherPlainTextABA的私钥A的公钥3.3.2 RSA算法简介vRon Rivest, Adi Shamir , Leonard AdlemanRon Rivest, Adi Shamir , Leonard Adleman（麻省理工学院）（麻省理工学院）vRSARSA的安全性基于大数分解的难度的安全性基于大数

19、分解的难度数论基础v a a与与b b的最大公因数：的最大公因数：gcdgcd (a, b) (a, b) gcd(20, 24)=4 , gcdgcd(20, 24)=4 , gcd (15, 16)=1 (15, 16)=1v 如果如果gcd(agcd(a, b)=1 , b)=1 ，称，称a a与与b b 互素互素v 模运算模运算 modmoda= q n +r 0rn ; q=a= q n +r 0rn ; q= a/na/n ; ; x x 表示小于或等于表示小于或等于x x的最大整数的最大整数a=a= a/na/n n n + + ( (a mod na mod n) ) , r

20、= a mod n , r = a mod n 如果如果 ( (a mod n a mod n ) )= = ( (b mod nb mod n) ) ，则称则称a a 与与b b 模模n n同余同余，记为记为 a a b mod n b mod n 例如，例如， 23 8 mod 5 , 8 1 mod 723 8 mod 5 , 8 1 mod 7数论基础（续）v模运算是可交换的、可结合的、可分配的模运算是可交换的、可结合的、可分配的(a+b) mod n = (a mod n ) + (b mod n) ) mod n(a-b) mod n = ( (a mod n) (b mod n)

21、 ) 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 nv幂,模运算 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 数论基础（续）v 欧拉函数欧拉函数(n) (n) n n是正整数，是正

22、整数，(n) (n) 是比是比n n小且与小且与n n 互素的正整数的个数互素的正整数的个数(3)=(3)=|1, 2| =2|1, 2| =2 (4)=(4)=|1, 3| =2|1, 3| =2 (5)=(5)=|1, 2, 3, 4 | =4|1, 2, 3, 4 | =4 (6)=(6)=|1, 5| =4|1, 5| =4 (7)=(7)=|1, 2, 3, 4, 5, 6| =6|1, 2, 3, 4, 5, 6| =6(10)=(10)=|1, 3, 7, 9| =4|1, 3, 7, 9| =4 (11)=(11)=|1, 2,3,4,5,6, 7,8, 9,10| =10|1

23、, 2,3,4,5,6, 7,8, 9,10| =10 如果如果p p是素数，则是素数，则(p)=p-1, (p)=p-1, 比如比如(2), (2), (5)(5)， (11)(11) 如果如果p,qp,q 是素数，则是素数，则(pq(pq)=)=(p)(p)* *(q)(q)(p-1)(p-1)* *(q-1) (q-1) 。比如，比如，(10)= (10)= （2 2* *5 5）= =（2)2)（5 5）=1=1* *4=44=4数论基础（续）例如：例如： m=3, n=10; m=3, n=10; (10)=4(10)=4 m m(n)(n)=3=34 4=81 ; 81 mod 1

24、0 = 1=81 ; 81 mod 10 = 1 即即 81 1 mod 1081 1 mod 10 3 34+14+1 = 243 3 mod 10 = 243 3 mod 10 nmn mod 1)(nmmn mod 1)(欧拉定理欧拉定理 若整数若整数m 和和n 互素，则互素，则等价形式等价形式数论基础（续）v推论：给定两个素数推论：给定两个素数p, qp, q , , 两个正整数两个正整数 n n, , m m ，使得使得n=pqn=pq, 0mn, 0mn ； 则对于任意正整数则对于任意正整数k k ，下，下列关系成立：列关系成立： m m k k(n)+1(n)+1 m mod n m mod nRSA算法v 密钥产生密钥产生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 (ngcd (e, (n) )=1; 1e (n) ) e e作为公钥公开作为公钥公开; ;5. 5. 寻找寻找d, d, 使得使得 de de 1 mod