密码的加密与解密模型

密码的加密与解密的数学模型Author：C.Z.NiuOffice：#1-403Email:[e-mail]密码学的基本概念密码学基本模型密码分析（Cryptanalysis）接收方Plaintext明文Decryption解密Key解密密钥Encryption加密Key加密密钥发送方Plaintext明文不安全信道Ciphertext密文加密：()KCEm解密：()KmDC先加密后再解密消息，原始的明文将恢复出来，D（E（M））=M.密文用C（Cipher）表示，也是二进制数据，有时和M一样大，有时稍大.通过压缩和加密的结合，C有可能比P小些.明文用M(Message,消息)或P(Plaintext,明文)表示，它可能是比特流、文本文件、位图、数字化的语音流或数字化的视频图像等.加密函数E作用于M得到密文C，用数学公式表示为：E（M）=C.解密函数D作用于C产生M，用数据公式表示为：D（C）=M.置换密码Caesar密码ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIGKLMNOPQRSTUVWXYZABCCaesarwasagreatsoldier密码本密文Fdhvduzdvdjuhdwvroglhu明文密文CAESAR密码：c=(m+3)Mod26ABCDEFJHIJK012345678910仿射变换密码上面移位置换密码的一个简单变种就是仿射变换密码，其数学表示为互素必需与模其中自然数mambapc)(mod在上面例子移位置换密码下，明文中相邻的字母对应的密文字母也是相邻的，如A和B对应的密文字母分别为D和E,但在仿射变换下，对应的密文字母分别为F((3*0+5)mod26=5=F)和I，它们有3个字母的间隔(a=3))26(mod53pc11111(mod),1(mod),,()(mod)apcbmamaaamapacbmamama仿射变换的解密公式可通过求解同余方程得到记整数关于模的同余逆为即对上式两边同乘得Remark:只有与互素，才可能存在关于模的同余逆例假设下面是仿射变换加密的，试破译此文FSFPREDLFSHRLERKFXRSKTDMMPRRKFSFUXAFSDHKFSPVMRDSKARLVUURRIFEFKKANEHOFZFUKRESVVS假设此问题由26个英文字母组成，取m=26.由于与26互素，a有12种不同的取法，b有26种不同的取法，所以放射变换有12*26=321种。可采取穷举法来破译。可以用频率法，即密文中出现次数最多的字母与英文中最常见的字母对应。在密文中在平常统计中F：出现12次E：出现频率13.04%R：出现12次T：出现频率13.04%S：出现9次Z：出现频率0.08%K：出现8次-1(5)(4),(17)(19),54(mod26)1719(mod26)1215(mod26)a1512(mod26)712(mod26)6(mod26)FERTababa（1）如令对应对应得同余式这样有：所以：a=6与26不互素，所以无法对密文解密。-1(17)(5),(18)(19),174(mod26)1819(mod26)115(mod26)a151(mod26)71(mod26)7(mod26)17-47(mod26)11(mod26)15(mod26)715(mod26)159(mod26)RESTabababcppc（2）如令对应对应得同余式这样有：所以：a=7我们可得到加密公式:解密公式:GTGAERCSGTKESRE……RKLGUGXDERTMMT利用上述解密公式对密文进行解密得到：这是一串没有意义的字符串，解密失败！(17)(5),(10)(19),174(mod26)1019(mod26)35(mod26),35(mod26),39(3*91mod26)9(5)(mod26)97(mod26)REKTababcppcpcc（3）如令对应对应得同余式我们可得到加密公式解密公式因的同余逆所以解密公式为：最后破译文为ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON即ANAMERICANSECRETAGENTWILLMEETANAFGHANISTANMOLEINTHECOFFEEBARATTHURSDAYAFTERNOON破译成功HILL密码Hill2密码中所用的数学手段是矩阵运算。加密过程：1）将英文的26个字母与0到25之间的整数建立一一对应关系，称为字母的表值，然后根据明文字母的表值，将明文信息用数字表示。设明文信息只用26个大写字母表示，通讯双方给出这26个字母的表值如下：ABCDEFGHIJKLM０１23456789101112NOPQRSTUVWXYZ131415161718192021222324252）选择一个二阶可逆整数方阵A，称为Hill2密码的加密矩阵，它是加密体制的“密钥”，是加密的关键，仅通讯双方掌握。3）将明文字母分组。Hill2使用的是二阶矩阵，所以将明文字母每2个一组（可以推广至Hilln密码），若最后仅有一个字母，则补充一个没有实际意义的哑字母。这样使得每组都有2个字母，查出每个字母的表值，构成一个二维列向量。4）令，由的两个分量反查字母表值得到的两个字母即为密文字母。A解密过程：加密过程的逆过程。字母（明文）表值一组数分组向量A左乘向量反查表值密文ＨILL密码的数学模型例：设明文为“MEET”,求这段明文的Hill2密文。5021A将明文分为：MEET对应密文UUQR对应的列向量为124,419左乘矩阵A后的向量为2042,2095关于26取模2016,,201711{0,1,2,,1}.ABABBAI(modm)AmBAm(mod)mmmmZmZnZnBAm定义设为一正整数，记整数集合对于一个元素属于的阶方阵，若存在一个元素属于的阶方阵，使得称为模可逆。为的模逆矩阵，记为11det()1det1AA(mod)mmZAmmAAZAmmAm命题元素属于的方阵模可逆的充要条件是：和没有公共的素数因子。推论若方阵的每个元素属于，而且则是模可逆的，且它的逆矩阵就是的模逆矩阵。dcbaA)(mod)(11macbdbcadA设方阵满足命题1的条件容易验证11()(mod)adbcadbcmAmAm其中是关于模的同余逆。于是方程组在模意义下的解为对上面例子,det(A)=5,它与26互素，所以满足命题1的条件，故A关于模26的逆为1152525(mod26)21(mod26)(521)010110542110(mod26)(mod26)021021A因为的同余逆1110(mod)(mod26)021Am解密公式为：对密文UUQR进行解密得到)26(mod1943571861716210101)26(mod4124202202020210101即明文MEETHill密码的加密与解密过程类似于在n维向量空间中进行线性变换及其逆变换。每个明文向量是一个Zm上的n维向量，乘以加密矩阵并对m取余，仍为Zm上的一个n维向量。由于加密矩阵A为模m的可逆矩阵，所以如果知道了n个线性无关的n维明文向量及其对应的密文向量，就可以求出它的加密矩阵A及其模m的逆矩阵A-1(mod)公开密钥系统Hill密码的加密和解密都只需要加密矩阵这个密钥就可以了。这种系统称为单密钥系统。如果加密和解密使用两个不同的密钥，则称为双密钥系统，也称为公开密钥系统。密钥的拥有者将其中一个密钥公开，另一个保密。双密钥系统（1）W.Diffie和M.Hellman最早提出（2）R.L.Rivest,A.Shamir和L.Adleman提出第一个方法双密钥系统的程序是这样的收方先告诉发方如何把情报制成密码（敌人也听到）发方依法发出情报的密文（敌人也可能收到密文）收方将密码还原成原文（敌人却解不开密文）公钥密码系统的加密原理每个通信实体有一对密钥（公钥，私钥）。公钥公开，用于加密，私钥保密，用作解密A向B发送消息，用B的公钥加密B收到密文后，用自己的私钥解密cipher加密算法解密算法BPlainTextB的私钥PlainTextA任何人向B发送信息都可以使用同一个密钥(B的公钥)加密没有其他人可以得到B的私钥，所以只有B可以解密公钥密码系统的签名原理A向B发送消息，用A的私钥加密（签名）B收到密文后，用A的公钥解密（验证）PlainText加密算法解密算法cipherPlainTextABA的私钥3.3.2RSA算法简介RonRivest,AdiShamir,LeonardAdleman（麻省理工学院）RSA的安全性基于大数分解的难度数论基础a与b的最大公因数：gcd(a,b)gcd(20,24)=4,gcd(15,16)=1如果gcd(a,b)=1，称a与b互素模运算moda=qn+r0≤rn;q=[a/n];[x]表示小于或等于x的最大整数a=[a/n]n+(amodn),r=amodn如果(amodn)=(bmodn)，则称a与b模n同余，记为a≡bmodn例如，23≡8mod5,8≡1mod7数论基础（续）模运算是可交换的、可结合的、可分配的(a+b)modn=((amodn)+(bmodn))modn(a-b)modn=((amodn)–(bmodn))modn(a×b)modn=((amodn)×（bmodn))modn(a×(b+c))modn=（(a×b)modn+(a×c)modn)modn幂,模运算mamodnm2modn=(m×m)modn=(mmodn)2modnm4modn=(m2modn)2modnm8modn=((m2modn)2modn)2modnm25modn=(m×m8×m16)modn数论基础（续）欧拉函数ф(n)n是正整数，ф(n)是比n小且与n互素的正整数的个数ф(3)=|{1,2}|=2ф(4)=|{1,3}|=2ф(5)=|{1,2,3,4}|=4ф(6)=|{1,5}|=4ф(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=4数论基础（续）例如：m=3,n=10;ф(10)=4mф(n)=34=81;81mod10=1即81≡1mod1034+1=243≡3mod10nmnmod1)(nmmnmod1)(欧拉定理若整数m和n互素，则等价形式数论基础（续）推论：给定两个素数p,q,两个正整数n,m，使得n=pq,0mn；则对于任意正整数k，下列关系成立：mkф(n)+1≡mmodnRSA算法密钥产生1.取两个大素数p,q,保密;2.计算n=pq，公开n;3.计算欧拉函数ф(n)=（p-1）(q-1)；4.任意取一个与ф(n)互素的小整数e,即gcd(e,ф(n))=1;1eф(n)e作为公钥公开;5.寻找d,使得de≡1modф(n),ed=kф(n)+1d作为私钥保密。p=7,q=17n=119Ф(n)=96选择e=55d=k×96＋1令k=4,得到求得d=77RSA算法加密/