古典算法复习课概要课件

数据加密与PKI技术

第11周

数据加密涉及算法复习课

2023/7/281

数据加密与PKI技术

第11周数据学习目标理解凯撒密码与Playfair等古典替换密码掌握DES加密中的IP置换与S盒变换掌握欧几里德最大公因子算法灵活运用费马定理与欧拉定理理解RSA加解密算法理解背包密码体制掌握Diffie—Hellman密钥交换计算理解Elgamal算法与DSA算法2023/7/282学习目标理解凯撒密码与Playfair等古典替换密码2023古典密码学作业1、恺撒与安东尼要举行一个秘密会议，他写了一个密信“ULEHU”,请问地点在什么地方？并写出推导出它的数学求解式。（写一个就可以了）答：M=C-K（mod26），M=20-3（mod26）=17=R，同理其他字母可解。明文：RIBER2、截获了一封密信，已知是恺撒变形密信，并知道了两对明文和相应的密文字母，求解K？并写出数学求解式。明文是:vy，密文是AD.答：k=c-m（mod26），k=0-21（mod26）=5。3、用playfair密码加密：Iseeaplane！这句话，密钥就是playfair。答：先将明文两个字母分一组，isexeaplanex，

C=cnkuhplapqku4、用Vigenère密码加密hereishowitw.这些字母，密钥是（V-21，E-4，C-2，T-19，O-14，R-17）。（注意全部忽略空格和标点符号）答：根据规则将密钥重复，每个字母相当于凯撒加密，C=citxwjcsybtn2023/7/283古典密码学作业1、恺撒与安东尼要举行一个秘密会议，他写了一个Caesar密码表例2．1

恺撒（Caesar）密码是k＝3的情况。即通过简单的向右移动源字母表3个字母则形成如下代换字母表若明文为：pleaseconfirmreceipt则密文为：SOHDVEFRQILUPUHFHLSWM:a0b1c2d3e4f5g6h7i8j9k10l11m12C:DEFGHIJKLMNOPn13o14p15q16r17s18t19u20v21w22x23y24z25QRSTUVWXYZABC2023/7/284Caesar密码表例2．1恺撒（Caesar）密码是k＝3Playfair密码体制Playfair密码表

playfirbcdeghkmnoqstuvwxz1234512345该密码体制的密钥是一个单词，比如playfair，将单词中后面重复的字母去掉，只保留不相同的字母，得到playfir，将剩下的字母排列成5×5矩阵的起始部分，矩阵的剩余部分则用26个字母表中未出现的字母填充，并将i与j作为一个字母对待（原因？）2023/7/285Playfair密码体制Playfair密码表playfir各种各样的移位密码是在16世纪发明的，它们大多数来自于Vigenère方法，它是法国密码学家维吉尼亚于1586年提出一种多表替换密码,但是就加密性而言，Vigenère密码体制更复杂和高级，直到20世纪初，这种加密体制在很多地方仍然被认为是安全的，虽然早在19世纪，Babbage和Kasiski就展示了如何攻击它们。在1920年，由Fridman开发了另外一种加密方法，打破了Vigenère及其相关的密码方法。第一步：这个加密的密钥是一个向量，按如下方式选择。首先，确定一个密钥长度，如6，然后从0～25个整数中选择元素项满足这个长度的向量，如k＝（21，4，2，19，14，17），将其称为向量。这样，系统的安全性所依赖的就是既不能知道密钥内容也不能得知其长度。

Vigenère密码2023/7/286各种各样的移位密码是在16世纪发明的，它们大多数来自Vigenère密码第二步：下面所举的例子就是利用k来加密信息，首先，取明文的第1个字母并将之移21位，然后将第2个字母移4位，第3个字母移2位等等，一旦得到了密钥的结尾，又从头开始，这样第7个字母又移位21位，第8个字母移4位等等，加密过程的密码流程表如下：（明文）hereishowitworks(密钥)21421914172142191417214219（密文）CITXWJCSYBHNJVML

这样对于这么一段明文就可以用Vigenère完全进行加密了，注意这里没有一个字母的频率比其他大很多，这是因为e在加密的过程中扩散成了几个字母的缘故。

2023/7/287Vigenère密码第二步：下面所举的例子就是利用k来加密信其中Mi是二元数字，为：

M58M50M42M34M26M18M10M2 M60M52M44M36M28M20M12M4 M62M54M46M38M30M22M14M6 M64M56M48M40M32M24M16M8 M57M49M41M33M25M17M9M1 M59M51M43M35M27M19M11M3 M61M53M45M37M29M21M13M5 M63M55M47M39M31M23M15M7如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始顺序将被恢复。2023/7/288其中Mi是二元数字，为：2023/7/288求IP逆置换例如求矩阵-1的逆。即为：4279186355281973642023/7/289求IP逆置换例如求矩阵-图1函数F(R,K)的计算过程S盒变换2023/7/2810图1函数F(R,K)的计算过程S盒变换2023/7/281F中的代换由8个S盒组成，每个S盒的输入长为6比特、输出长为4比特，其变换关系由表2.7定义，每个S盒给出了4个代换（由一个表的4行给出）。对每个盒Si，其6比特输入中，第1个和第6个比特形成一个2位二进制数，用来选择Si的4个代换中的一个。6比特输入中，中间4位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为4位二进制数即得这一S盒的输出。例如，S1

的输入为011001，行选为01（即第1行），列选为1100（即第12列），行列交叉位置的数为9，其4位二进制表示为1001，所以S1的输出为1001。2023/7/2811F中的代换由8个S盒组成，每个S盒的输入长为6比特、输出长为费尔玛定理和欧拉定理费尔玛(Fermat)定理和欧拉(Euler)定理在公钥密码体制中起着重要作用。1.费尔玛定理定理4.2(Fermat)若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。Fermat定理也可写成如下形式：设p是素数，a是任一正整数，则ap≡amodp。2023/7/2812费尔玛定理和欧拉定理费尔玛(Fermat)定理和欧拉(2.欧拉函数设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)。例如：φ(6)=2，φ(7)=6，φ(8)=4。若n是素数，则显然有φ(n)=n-1。例如：由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12。2023/7/28132.欧拉函数2023/7/2813定理4.3若n是两个素数p和q的乘积，则φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。3.欧拉定理定理4.4（Euler）若a和n互素，则aφ(n)≡1modn。2023/7/2814定理4.3若n是两个素数p和q的乘积，则φ(n)=φ欧几里得算法欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。2023/7/2815欧几里得算法欧几里得（Euclid）算法是数论中的一个基本技1.求最大公因子Euclid算法是基于下面一个基本结论：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)。例如：gcd(55,22)=gcd(22,55mod22)=gcd(22,11)=gcd(11,0)=11。在求两个数的最大公因子时，可重复使用以上结论。例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=12023/7/28161.求最大公因子2023/7/2816例1求gcd(1970,1066)。1970=1×1066+904, gcd(1066,904)1066=1×904+162, gcd(904,162)904=5×162+94, gcd(162,94)162=1×94+68, gcd(94,68)94=1×68+26, gcd(68,26)68=2×26+16, gcd(26,16)26=1×16+10, gcd(16,10)16=1×10+6, gcd(10,6)10=1×6+4, gcd(6,4)6=1×4+2, gcd(4,2)4=2×2+0, gcd(2,0)因此gcd(1970,1066)=2。2023/7/2817例1求gcd(1970,1066)。2023/7/2811.密钥的产生①选两个保密的大素数p和q(各100～200位十进制数字)。②计算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的欧拉函数值。③选一整数e，满足1<e<φ(n)，且gcd(φ(n),e)=1。④计算d，满足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e与φ(n)互素，由模运算可知，它的乘法逆元一定存在。⑤以{e,n}为公开钥,{d,n}为秘密钥。算法描述2023/7/28181.密钥的产生算法描述2023/7/28182.加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算：

c≡memodn3.解密对密文分组的解密运算为：

m≡cdmodn2023/7/28192.加密2023/7/2819例2：选p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，满足1<e<φ(n)，且gcd(φ(n),e)=1。确定满足d·e=1mod96且小于96的d，因为77×5=385=4×96+1，所以d为77，因此公开钥为{5，119}，秘密钥为{77，119}。设明文m=19，则由加密过程得密文为

c≡195mod119≡2476099mod119≡66解密为

6677mod119≡192023/7/2820例2：选p=7，q=17。求n=p×q=119，φ(n)=(例题3：已知明文m=14，pk=（3，55），求密文c和私钥sk分别为多少？解：因为n=55=5*11，所以p=5（或11），q=11（或者5），（p-1）*（q-1）=40，

e*dmod40≡1，d=e-1=27C=memodn=143mod55=492023/7/2821例题3：已知明文m=14，pk=（3，55），求密文c

RSA算法中的计算问题1.RSA的加密与解密过程RSA的加密、解密过程都为求一个整数的整数次幂，再取模。如果按其含义直接计算，则中间结果非常大，有可能超出计算机所允许的整数取值范围。如上例中解密运算6677mod119，先求6677再取模，则中间结果就已远远超出了计算机允许的整数取值范围。而用模运算的性质：(a×b)modn=[(amodn)×(bmodn)]modn就可减小中间结果。2023/7/2822RSA算法中的计算问题1.RSA的加密与解密过程2023再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x16，直接计算的话需做15次乘法。然而如果重复对每个部分结果做平方运算即求x，x2，x4，x8，x16则只需4次乘法。求am可如下进行，其中a，m是正整数：将m表示为二进制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此2023/7/2823再者，考虑如何提高加、解密运算中指数运算的有效性。例如求x1例4求7560mod561。将560表示为1000110000，算法的中间结果如表所示。所以7560mod561=1。2023/7/2824例4求7560mod561。2023/7/2824背包密码体制例5：A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量，取k=1590，t=43，gcd(43,1590)=1，得B=(43,129,215,473,903,302,561,1165,697,1523)。在得到B后，对明文分组x=(x1x2…xn)的加密运算为c=f(x)=B·Bx≡t·A·Bxmodk对单向函数f(x)，t、t-1和k可作为其秘密的陷门信息，即解密密钥。解密时首先由s≡t-1cmodk，求出s作为超递增背包向量A的容积，再解背包问题即得x=(x1x2…xn)。这是因为t-1cmodk≡t-1tABxmodk≡ABxmodk，而由k>∑ai，知ABx<k，所以t-1cmodk=ABx，是惟一的。2023/7/2825背包密码体制例5：A=(1,3,5,11,21,4例6接例5，A=(1,3,5,11,21,44,87,175,349,701)是一超递增背包向量，k=1590，t=43，得t-1≡37mod1590，设用户收到的密文是(2942,3584,903,3326,215,2817,2629,819)，由37×2942≡734mod1590,37×3584≡638mod1590,37×903≡21mod1590,37×3326≡632mod1590,37×215≡5mod1590,37×2817≡879mod1590,37×2629≡283mod1590,37×819≡93mod1590,得(734,638,21,632,5,879,283,93)。2023/7/2826例6接例5，A=(1,3,5,11,21,44,取s=734，由734>701，得x10=1；令s=734-701=33，由33<349，得x9=0；重复该过程得第一个明文分组是1001100001，它对应的英文文本是SA；类似地得其他明文分组，解密结果为SAUNAANDHEALTH。2023/7/2827取s=734，由734>701，得x10=1；令s=734-Diffie-Hellman密钥交换是W.Diffie和M.Hellman于1976年提出的第一个公钥密码算法，已在很多商业产品中得以应用。算法的惟一目的是使得两个用户能够安全地交换密钥，得到一个共享的会话密钥，算法本身不能用于加、解密。算法的安全性基于求离散对数的困难性。Diffie-Hellman密钥交换2023/7/2828Diffie-Hellman密钥交换是W.Diffie和M图2表示Diffie-Hellman密钥交换过程，其中p是大素数，a是p的本原根，p和a作为公开的全程元素。用户A选择一保密的随机整数XA，并将YA=aXAmodp发送给用户B。类似地，用户B选择一保密的随机整数XB，并将YB=aXBmodp发送给用户A。然后A和B分别由K=(YB)XAmodp和K=(YA)XBmodp计算出的就是共享密钥，这是因为(YB)XAmodp=(aXBmodp)XAmodp=(aXB)XAmodp=aXB

XAmodp=(aXA)XBmodp=(aXAmodp)XBmodp =(YA)XBmodp2023/7/2829图2表示Diffie-Hellman密钥交换过程，其中p是大图2Diffie-Hellman密钥交换2023/7/2830图2Diffie-Hellman密钥交换2023/7/28因XA，XB是保密的，敌手只能得到p，a，YA

，YB，要想得到K，则必须得到XA，XB中的一个，这意味着需要求离散对数。因此敌手求K是不可行的。例如：p=97，a=5，A和B分别秘密选XA=36，XB=58，并分别计算YA=536mod97=50，YB=558mod97=44。在交换YA，YB后，分别计算K=(YB)XAmod97=4436mod97=75,K=(YA)XBmod97=5058mod97=752023/7/2831因XA，XB是保密的，敌手只能得到p，a，YA，YB，要想Elgamal算法密钥对产生办法。首先选择一个素数p，两个随机数，g和x，g与x<p，计算y=gx(modp)，则其公钥为y,g和p。私钥是x。其中g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M，首先选择一个随机数k,k与p-1互质，计算

a=gk(modp)

再用扩展Euclidean算法对下面方程求解b：

M=xa+kb(modp-1)

实际用

b=yk*Mmodp

签名就是(a,b)。随机数k须丢弃。

验证时要验证下式：

ya*ab(modp)=gM(modp)

同时一定要检验是否满足1<=a<p。否则签名容易伪造。2023/7/2832Elgamal算法密钥对产生办法。首先选择一个素数p，两个ElGamal用于加密被加密信息为M，首先选择一个随机数k，k与p-1互质，计算

a=gk(modp)

b=ykM(modp)

(a,b)为密文，是明文的两倍长。解密时计算

M=b/ax(modp)=b*（ax）-1modp

2023/7/2833ElGamal用于加密被加密信息为M，首先选择一个随机数k，例题：鲍勃把11选择为p。然后他选择g=e1=2。他再选择x=d=3并且计算出y=e2=e1d=8。所以公钥就是（g，y，p）=(2,8,11)，私钥是x=3。爱丽丝选择k=r=4并且计算出明文7的C1和C2。鲍勃收到密文c(a=5和b=6)并且计算出明文。

2023/7/2834例题：鲍勃把11选择为p。然后他选择g=e1=2。他再选我们不用P=[C2*(C1d)-1]modp解密，就可以避免乘法逆元的计算并且还可以运用P=[C2*C1（p-1-d）]modp。在例10.10中，我们可以算出P=[6*5（11-1-3）]mod11=7mod11。

2023/7/2835我们不用P=[C2*(C1d)-1]modp解DSA算法DigitalSignatureAlgorithm(DSA)是Schnorr和ElGamal签名算法的变种，被美国NIST作为DSS(DigitalSignatureStandard)数字签名标准，DSS是由美国国家标准化研究院和国家安全局共同开发的。由于它是由美国政府颁布实施的，主要用于与美国政府做生意的公司，其他公司则较少使用，而且美国政府不提倡使用任何削弱政府窃听能力的加密软件。算法中应用了下述参数：

*p：Lbits长的素数。L是64的倍数，范围是512到1024；

*q：是p-1的160bits的素因子；

*g：g=h^((p-1)/q)modp，h满足h<p-1,h^((p-1)/q)modp>1；

*x：为秘密密钥，正整数，x<q；

*y：y=g^xmodp，(p,q,g,y)为公钥；

*k为随机数，0〈k〈q；

*H(x)：One-WayHash函数。注："^"为幂运算符2023/7/2836DSA算法DigitalSignatureAlgorit签名过程DSA中选用SHA(SecureHashAlgorithm)。p,q,g可由一组用户共享，y是公开钥，x是私钥，签名过程如下：

1.产生随机数k，k<q；

2.计算r=(g^kmodp)modq

s=(k-1(H(m)+xr))modq

r，s即签名结果。2023/7/2837签名过程DSA中选用SHA(SecureHashAlg验证过程验证过程：签名结果是(m,r,s)。

3.验证时计算w=s-1mod