chap7.3密码与解密模型-

7.3密码和解密模型密码的历史密码的作用密码模型西元前404年斯巴达国(今希腊)北路军司令莱山得在征服雅典之后,信使赶到,献上了一条皮带,上面有文字,通报敌军欲断其归路的企图.4世纪希腊出现了隐蔽书信内容的初级密码.8世纪古罗马教徒为传播新教,创造了「圣经密码」.中世纪末叶，西班牙的平民百姓与贵族阶级的青年男女,为了冲破封建制度对自由恋爱的束缚,不得不采取种种秘密通信的形式,从而导致了各种原始密码的产生.密码的历史2023/2/4

1200年罗马教皇政府和意大利世俗政府开始有系统地使用密码.19世纪随着资本主义的发展和资产阶级相互斗争的需要,出现了无线电密码通信.密码的作用1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。2023/2/4密码学名词明文需要采用某种方法对其进行变换来隐蔽它所载荷的信息或字符串加密过程将明文变换成另一种不能被非授权者所理解的隐蔽信息的消息或字符串的过程明文经过加密过程的变换所得的消息或密文字符串将明文变为密文的变换加密变换解密变换将密文变为明文的变换密钥加（解）密变换所使用的参数2023/2/4置换密码是一个最容易实现而且最为人们熟悉的密码。只需要把每个字母由其它的字母来替换而形成密文。而替换的规则是随机的或者是系统的。凯撒密码是首先将讯息(明码)中的字母,用不同的字母代替。他的做法是系统地将字母向后推三个位置。a-Db-Ec-Fd-Ge-Hf-Ig-Jh-Ki-Lj-Mk-Nl-Om-Pn-Qo-Rp-Sq-Tr-Us-Vt-Wu-Xv-Yw-Zx-Ay-Bz-C置换密码2023/2/4关于模运算（mod26）模m

等价设

a,b为两个整数,若称

a模m等价于b，记作剩余集称为模m的剩余集运算律设a,b

为两个整数，则模m

倒数设，若存在使得则称a模m可逆（有模m

倒数），记作命题模26倒数表25175112371931521912523211917151197531a–1(mod26)a整数a模m

可逆a

与m

无公共质数因子2023/2/4thismessageistopsecretWKLVPHVVDJHLVWRSVHFUHWwearethechampionZHDUHWKHFKDPSLRQ如果26个字母被从1到26编号，用p表示明文中某个字母的编号，用c表示相应的密文中字母的编号，则凯撒密码就可以由如下的模型给出

c=p+3(Mod26)其中的数3就是凯撒密码的秘钥，更一般的形式由下面的公式给出c=p+k(Mod26)其中1≤k≤25.称这种密码为移位置换密码，k称为移位因子.2023/2/4仿射变换密码上面移位置换密码的一个简单变种就是仿射变换密码，其数学表示为在上面例子移位置换密码下，明文中相邻的字母对应的密文字母也是相邻的，如A和B对应的密文字母分别为D和E,但在仿射变换下，对应的密文字母分别为H和K，它们有3个字母的间隔(a=3)其中自然数a必须与模m互素2023/2/42023/2/4例假设下面是仿射变换加密的，试破译此文FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHKFSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS假设此问题由26个英文字母组成，取m=26.由于与26互素，a有12种不同的取法，b有26种不同的取法，所以仿射变换有12*26=312种。可以用频率法，即密文中出现次数最多的字母与英文中最常见的字母对应。在密文中在平常统计中F：出现12次E：出现频率13.04%R：出现12次T：出现频率13.04%S：出现9次Z：出现频率0.08%K：出现8次2023/2/42023/2/42023/2/4GTGAERCSGTKESRE……RKLGUGXDERTMMT利用上述解密公式对密文进行解密得到：这是一串没有意义的字符串，解密失败2023/2/4最后破译文为ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON即ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON破译成功(3)如令R(17)对应E(4)，K(10)对应T(19)，得同余式17=4a+b(mod26)10=19a+b(mod26),我们可以得到加密公式：c=3p+5(mod26),解密公式：p=3-1(c-5)(mod26)=9(c-5)(mod26)=9c+7(mod26)2023/2/4多重图系统Hill密码中所用的数学手段是矩阵运算。

加密过程：1）将英文的26个字母、空格和必要的标点符号与1到29之间的整数建立一一对应关系，称为字符的表值，然后根据明文字符的表值，将明文信息用数字表示。设通讯双方给出这29个字符的表值如下：ABCDEFGHIGKLMNO123456789101112131415PQRSTUVWXYZ空格？！16171819202122232425262728292023/2/42）选择一个n阶可逆整数方阵A，称为Hilln密码的加密矩阵，它是加密体制的“密钥”，是加密的关键，仅通讯双方掌握。3）将明文字母分组。Hill2

使用的是二阶矩阵，所以将明文字母每2个一组（可以推广至Hilln密码），若最后仅有一个字母，则补充一个没有实际意义的哑字母。这样使得每组都有2个字母，查出每个字母的表值，构成一个二维列向量。4）令，由的两个分量反查字符表值得到的两个字母即为密文字母。2023/2/4

解密过程：加密过程的逆过程。字符（明文）表值一组数分组向量A左乘向量反查表值密文ＨILL密码的数学模型2023/2/4例：设明文为“MEET求这段明文的Hill2密文。将明文分为：

MEET对应密文WYPM2023/2/42023/2/4设方阵满足命题2的条件,容易验证2023/2/4对上面例子,det(A)=5,它与29互素，所以满足2的条件，故A关于模29的逆为2023/2/4对密文WYPM进行解密得到即明文MEET2023/2/4一个简单实例明文：Ourmarshalwasshot分组：ourmarshalwasshott补充哑元对应向量加密：左乘加密矩阵直接结果2023/2/4密文向量密文ekrmkbixyjyceelshh解密求得解密矩阵左乘密文向量再取模即可求得明文向量，

从而得出明文结论使用Hill密码时的加解密矩阵应该模26

可逆2023/2/4HILLn密码的破译

关键在于求出解密矩阵（解密密钥）

只要破译出n组线性无关的密文向量

若有2023/2/4一个破译例子甲方截获了一段密文：OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH经分析这段密文是用HILL2密码编译的，且这段密文的字母UCRS依次代表了字母TACO，若明文字母的表值如前，试破译这密文的内容？关系根据解密原理2023/2/4计算解密密钥A－12023/2/4破译密文向量明文向量明文：ClintonisgoingtovisitacountryinMiddleEast2023/2/4

Hill密码的加密与解密过程类似于在n维向量空间中进行线性变换及其逆变换。每个明文向量是一个Zm上的n维向量，乘以加密矩阵并对m取余，仍为Zm上的一个n维向量。由于加密矩阵A为模m的可逆矩阵，所以如果知道了n个线性无关的n维明文向量及其对应的密文向量，就可以求出它的加密矩阵A及其模m的逆矩阵A-1(modm)2023/2/4公开密钥系统Hill密码的加密和解密都只需要加密矩阵这个密钥就可以了。这种系统称为单密钥系统。如果加密和解密使用两个不同的密钥，则称为双密钥系统，也称为公开密钥系统。密钥的拥有者将其中一个密钥公开，另一个保密。双密钥系统（1）W.Diffie和M.Hellman最早提出（2）R.L.Rivest,A.Shamir和L.Adleman

提出第一个方法双密钥系统的程序是这样的收方先告诉发方如何把情报制成密码（敌人也听到）发方依法发出情报的密文（敌人也可能收到密文）收方将密码还原成原文（敌人却解不开密文）2023/2/4公钥密码系统的加密原理每个通信实体有一对密钥（公钥，私钥）。公钥公开，用于加密，私钥保密，用作解密A向B发送消息，用B的公钥加密B收到密文后，用自己的私钥解密PlainText加密算法解密算法ABcipherPlainTextB的私钥C的公钥B的公钥任何人向B发送信息都可以使用同一个密钥(B的公钥)加密没有其他人可以得到B的私钥，所以只有B可以解密2023/2/4公钥密码系统的签名原理A向B发送消息，用A的私钥加密（签名）B收到密文后，用A的公钥解密（验证）PlainText加密算法解密算法cipherPlainTextABA的私钥A的公钥2023/2/4RSA算法简介RonRivest,AdiShamir,LeonardAdlemanRSA的安全性基于大数分解的难度RSA在美国申请了专利（已经过期），在其他国家没有RSA已经成了事实上的工业标准，在美国除外2023/2/4数论基础a与b的最大公因数：gcd(a,b)gcd(20,24)=4,gcd(15,16)=1如果gcd(a,b)=1，称a与b互素模运算moda=qn+r0≤r<n;q=[a/n];

[x]表示小于或等于x的最大整数a=[a/n]n+(amodn),r=mmodn如果(amodn)=(bmodn)，则称a与b模n同余，记为

a≡bmodn

例如，23≡8mod5,8≡1mod72023/2/4数论基础（续）欧拉函数ф(n)n是正整数，ф(n)是比n小且与n

互素的正整数的个数ф(3)=|{1,2}|=2

ф(4)=|{1,3}|=2

ф(5)=|{1,2,3,4}|=4

ф(6)=|{1,5}|=2

ф(7)=|{1,2,3,4,5,6}|=6ф(10)=|{1,3,7,9}|=4

ф(11)=|{1,2,3,4,5,6,7,8,9,10}|=10

如果p是素数，则ф(p)=p-1,比如ф(2),ф(5)，ф(11)如果p,q是素数，则ф(pq)=ф(p)ф(q)＝(p-1)(q-1)。比如，ф(10)=ф（2*5）=ф（2）ф（5）=1*4=42023/2/4数论基础（续）例如：

m=3,n=10;ф(10)=4mф(n)=34=81;81mod10=1

即

81≡1mod1034+1=243≡3mod10欧拉定理若整数m

和n

互素，则等价形式2023/2/4数论基础（续）推论：给定两个素数p,q,两个正整数n,m

，使得n=pq,0<m<n

；则对于任意正整数k

，下列关系成立：

mkф(n)+1≡mmodn2023/2/4RSA算法操作过程密钥产生1.取两个大素数p,q,保密;2.计算n=pq，公开n;3.计算欧拉函数ф(n)=（p-1）(q-1)；4.任意取一个与ф(n)互素的小整数e,即

gcd(e,ф(n))=1;1<e<ф(n)

e作为公钥公开;5.寻找d,使得

de≡1modф(n),ed=k

ф(n)+1

d作为私钥保密。p=7,q=17n=119Ф(n)=96选择e=55d=k×96＋1令k=4,得到求得d=772023/2/4RSA算法加密/解密过程密钥对（KU,KR