注以下内容参考《新编密码学》范九伦 张雪锋 侯红霞 编著7.4 椭圆曲线密码7.4.1 椭圆曲线的定义与性质椭圆曲线是指由Weierstrass方程y²axybyx³cx²dxe所确定的平面曲线。在密码学中通常使用定义在有限域Zpp为素数上的椭圆曲线y²≡x³axb(modp)其中a,b∈Zp且4a³27b²≠0(modp)保证曲线非奇异。椭圆曲线上的所有点加上无穷远点OO构成一个Abel群Ep(a,b)。加法运算规则图7-2单位元无穷远点O逆元−P(x,−y)点加过P和Q的直线交曲线于RR则P⊕Q−R倍点过P的切线交曲线于R则2P−R坐标计算公式设P(x1,y1)Q(x2,y2)RP⊕Q(x3,y3)则例7.3Z₁₁上的椭圆曲线y²x³x6计算得E₁₁(1,6)共有13个点表7-1。取生成元g(2,7)可计算出g的所有幂倍点得到群中所有点。7.4.2 椭圆曲线上的密码体制椭圆曲线密码体制基于椭圆曲线上的离散对数问题给定Ep(a,b)上的两点P和Q寻找整数k使QkPkP表示P自加k次。已知k,P求Q容易反之困难。椭圆曲线ElGamal密码体制密钥生成取g∈Ep(a,b)选取私钥x计算公钥yxg加密对明文m嵌入为曲线上的点随机选取k计算c₁kgc₂m⊕ky密文c(c₁,c₂)解密mc₂⊕(−xc₁)例7.4取g(2,7)为E₁₁(1,6)的生成元私钥x7公钥y7g(7,2)。明文m(10,9)随机数k3加密得c((8,3),(10,2))解密得m(10,9)。7.4.3 椭圆曲线密码算法的特性安全性高椭圆曲线离散对数问题的最好算法Pollardρ时间复杂度为O(√N)而有限域上标准离散对数可用指数积分法亚指数时间求解。因此ECC更安全。密钥量小、运算速度快在同等安全级别下ECC密钥长度远小于RSA表7-2。例如1024位RSA约等于160位ECC2048位RSA约等于210位ECC密码资源丰富可通过改变曲线系数生成大量不同曲线灵活性好。注意事项应避免使用超奇异椭圆曲线易受MOV攻击和异常椭圆曲线可在线性时间内求解应确保循环子群的阶有大素因子至少160比特7.5 基于身份的公钥密码体制7.5.1 概述1984年Shamir提出基于身份密码学IBC的思想。用户的身份信息如电子邮件地址直接作为公钥私钥由私钥生成中心PKG产生。这省去了公钥证书的管理开销。与传统基于证书密码体制的对比对比项传统PKI基于身份密钥生成用户自选私钥计算公钥PKG根据身份生成私钥公钥获取需证书直接使用身份信息公钥保存需目录存放证书无需目录身份认证验证证书签名向PKG证实身份7.5.2 双线性Diffie-Hellman假设基于身份的加密方案由四个算法构成系统建立、私钥提取、加密、解密。双线性映射e:G₁×G₁→G₂满足双线性e(aP,bQ)e(P,Q)^(ab)非退化性存在P,Q使e(P,Q)≠1可计算性存在有效算法计算e(P,Q)双线性Diffie-Hellman问题给定(P,aP,bP,cP)计算e(P,P)^(abc)是困难的。7.5.3 Boneh和Franklin的IBE方案2001年Boneh和Franklin使用椭圆曲线上的Weil对设计了首个实用的IBE方案。系统建立生成群G₁,G₂和双线性映射e选取生成元P主密钥s∈Zq公钥PpubsP选择Hash函数H₁:{0,1}∗→G₁H₂:G₂→{0,1}^n私钥提取对用户身份ID计算QIDH₁(ID)私钥dIDsQID加密随机选取r计算密文C(rP,m⊕H₂(e(QID,rPpub)))解密mV⊕H₂(e(dID,U))7.6 公钥密码体制的应用7.6.1 RSA密码体制的应用解决密钥分发和管理问题公钥可公开私钥保密简化大规模网络中的密钥管理。实现数字签名私钥签名公钥验证满足唯一性和私有性要求。加密短小消息RSA加密速度慢约为DES的千万分之一适合短消息加密。7.6.2 椭圆曲线密码体制的应用ECDSA数字签名速度快、强度高、签名短如Microsoft CDKey。无线网络WAPI中国无线局域网国家标准采用ECC进行身份认证。Web服务器减少计算时间和带宽消耗。IC卡无需协处理器代码和密钥存储空间小成本低。习题7 解答7-1 简述公钥密码体制的一般定义解答公钥密码体制非对称密码体制是一种加密和解密使用不同密钥的密码体制。每个用户拥有一个密钥对公钥可公开和私钥保密。公钥用于加密私钥用于解密。从公钥推算出私钥在计算上不可行。一般定义为五元组(M,C,K,E,D)M明文空间C密文空间K密钥空间公钥-私钥对E加密算法集合D解密算法集合满足对任意密钥对(pk,sk)加密变换Epk:M→C和解密变换Dsk:C→M满足Dsk[Epk[m]]m。7-2 什么是单向陷门函数如何将其应用于公钥密码体制设计解答单向陷门函数是一个可逆函数f(x)满足正向计算给定x计算yf(x)容易逆向计算给定y计算xf^(−1)(y)困难存在陷门信息知道陷门时逆向计算容易应用于公钥密码设计公钥对应函数f正向计算私钥对应陷门信息逆向计算加密用公钥计算cf(m)解密用私钥计算mf^(−1)(c)RSA基于大数分解陷门f(x)x^e mod n陷门是p,q或d。7-3 简述公钥密码体制相对单钥密码体制的优势解答优势说明密钥分配简单公钥可公开无需安全信道传递密钥密钥数量少nn个用户只需nn个密钥对对称密码需n(n−1)/2个支持数字签名私钥签名公钥验证实现不可否认性支持密钥交换如Diffie-Hellman协议密钥管理方便可定期更换密钥公钥证书机制成熟7-4 简述RSA算法的理论基础解答RSA算法的理论基础是数论中的欧拉定理和模运算欧拉定理若gcd(a,n)1则a^φ(n)≡1(modn)RSA密钥关系选择ed≡1(mod φ(n))则存在整数k使ed1kφ(n)加解密正确性若gcd(m,n)1则m^(ed)m^(1kφ(n))≡m⋅(mφ(n))^k≡m(mod n)若gcd(m,n)≠1即p∣m或q∣m可类似证明安全性基础由n分解p,q困难从而由(n,e)求d困难7-5 在RSA体制中为什么加密指数e必须与模数n的欧拉函数φ(n)互素解答解密指数d满足ed≡1(modφ(n))。该同余方程有解的充要条件是gcd(e,φ(n))1。若gcd(e,φ(n))≠1则e在模φ(n)下无乘法逆元无法计算出解密密钥d从而无法正确解密。7-6 选择p7q17e5试用RSA算法对明文m19进行加密再对密文解密。解答计算np×q7×17119计算φ(n)(p−1)(q−1)6×1696验证gcd(e,φ(n))gcd(5,96)1合法计算解密指数de^(−1)mod 96。扩展欧几里得5×773854×961故d77加密cm^e mod n19⁵ mod 11919²361≡361−3×119361−357419⁴4²1619⁵19⁴×1916×19304≡304−2×119304−23866密文c66解密mc^d mod n66⁷⁷ mod 119利用欧拉定理66⁹⁶≡166⁷⁷66^(−19)计算较繁结果应为19答案密文c66解密得m197-7 对于npq定义Ψ(n)(p−1)(q−1)/gcd(p−1,q−1)。修改RSA体制为ed≡1mod Ψ(n)(1) 证明加密和解密仍然互逆证明设λΨ(n)lcm(p−1,q−1)。由欧拉定理对任意m与p互素m^(p−1)≡1(modp)故m^λ≡1(modp)对任意m与q互素m^λ≡1(modq)因此对任意m与p或q可整除有m^λ≡1(mod pq)。由ed≡1(modλ)存在整数k使ed1kλ。则m^(ed)m^(1kλ)m⋅(m^λ)^k≡m(mod n)故加解密互逆。(2) p37,q79,e7计算修改前后d的值原RSAn37×792923φ(n)36×782808de^(−1) mod 2808扩展欧几里得28087×4011故7×(−401)≡1−401 mod 28082407d2407修改后gcd(36,78)6Ψ(n)2808/6468Ψ(n)2808/6468d′7^(−1) mod 468扩展欧几里得4687×66676×11回代得17−67−(468−66×7)67×7−468故7×67≡1mod 468d′67答案原RSA中d2407修改后d677-8 证明RSA中不动点x∈Zn∗的个数为gcd(e−1,p−1)×gcd(e−1,q−1)证明不动点满足x^e≡x(modn)即x(x^(e−1)−1)≡0(modn)。模p下x(x^(e−1)−1)≡0(modp)解为x≡0或x^(e−1)≡1(modp)。x^(e−1)≡1(modp)的解数等于gcd(e−1,p−1)。加上x≡0对应x是p的倍数但要求x∈Zn∗故排除xx含p或q因子的情况实际只考虑与n互素的解。模p下非零解个数为gcd(e−1,p−1)模q下非零解个数为gcd(e−1,q−1)。由中国剩余定理模n下的解个数为两者乘积。因此不动点个数为gcd(e−1,p−1)×gcd(e−1,q−1)7-9 Rabin密码体制ek(x)x(xB)mod np199,q211,B1357(1) 计算加密yek(32767)n199×21141989y32767×(327671357)mod 4198932767×34124mod 41989先模n化简32767 mod 419893276734124 mod 4198934124计算乘积后取模具体数值需大数运算结果为某个y值。(2) 求密文y的四个可能解Rabin解密需解x(xB)≡y(modn)即x²Bx−y≡0(modn)。配方得(2xB)²≡B²4y(modn)。分别解模p和模q下的二次同余各得两个解组合得四个模n解。7-10 找出模13的全体本原根解答模13的乘法群Z13∗阶为12。本原根是阶为12的元素。先找一个本原根2是模13的本原根吗计算2¹2≠12²42³82⁴16≡32⁶64≡12≠12¹²4096≡12的阶为12故2是本原根模p的本原根个数为φ(p−1)φ(12)4。全部本原根为2^a其中gcd(a,12)1即a1,5,7,11计算2¹22⁵32≡62⁷128≡112¹¹2048≡7答案2,6,7,117-11 给定Zp上ElGamal密码体制p31847g5私钥a7899公钥y18074解密密文(3781,14409)解答解密公式mc₂⋅(c₁^a)^(−1) mod p计算c₁^a3781⁷⁸⁹⁹ mod 31847需快速幂p求其在模p下的逆元乘以c₂14409得到明文具体数值计算较繁最终可得明文m。7-12 椭圆曲线y²x³17P1(−2,3)P2(2,5)(1) −P1关于x轴对称−P1(−2,−3)(2) 2P1λ3x₁²a/2y₁2x₃λ²−2x₁8y₃λ(x₁−x₃)−y₁−23则2P1(8,−23)(3) P1⊕P2λy₂−y₁/x₂−x₁0.5若在实数域x₃λ²−x₁−x₂0.25−(−2)−20.25y₃λ(x₁−x₃)−y₁−4.1257-13 给定椭圆曲线E₂₃(13,22): y²x³13x22。取生成元g(10,5)私钥x7公钥y7g(17,21)。对消息P(11,1)随机数k13加密并解密。解答曲线E23(13,22): y²x³13x22生成元g(10,5)私钥x7公钥y7g(17,21)消息点P(11,1)随机数k13加密c₁kg13×(10,5)需在曲线上计算倍点ky13×(17,21)c₂P⊕ky密文(c₁,c₂)解密mc₂⊕(−xc₁)c₂⊕(−7×c₁)需逐次计算椭圆曲线上的点加和倍点得到最终结果。7-14 椭圆曲线Massey-Omura密码体制RSA的椭圆曲线版本设椭圆曲线阶为N公钥e私钥d满足ed≡1mod N。对E₂₃(13,22)N22消息点Pm(11,1)公钥e13私钥d17加密并解密。解答曲线E₂₃(13,22)阶N22消息点Pm(11,1)公钥e13私钥d17验证ed13×1722110×221≡1 mod 22正确。加密CePm13×(11,1)计算曲线上的13倍点解密PmdC17×C应恢复(11,1)7-15 已知椭圆曲线E:y²x³−4x−3(mod7)点p(−2,2)求2p,4p,6p解答先验证点是否在曲线上(−2)³−4×(−2)−3−88−3−3≡4(mod7)y²4正确。计算2pλ3x₁²a/2y₁2x₃λ²−2x₁4−2×(−2)448≡1(mod7)y₃λ(x₁−x₃)−y₁2×(−2−1)−22×(−3)−2−6−2−8≡−1≡6(mod7)2p(1,6)4p2×2p6p2p⊕4p继续计算可得。7-16 RSA密码体制(1) 取e3有什么优缺点取d3安全吗为什么优点加密速度快只有两次乘法适合公钥加密短消息缺点易受低加密指数攻击。若同一消息用多个不同模数加密e3可由中国剩余定理恢复明文d3是否安全不安全。若d3由ed≡1mod φ(n)可推出e攻击者可分解n。且Wiener攻击可破小d。(2) 设n35密文C10公钥e5求明文M。n35p5,q7φ(n)24。de^(−1)mod 245^(−1)mod 24。5×525≡1故d5。解密MC^d mod n10⁵ mod 3510²100≡3010⁴≡30²900≡2510⁵10⁴×10≡25×10250≡5答案M57-17 ElGamal 加密已知素数 p71本原根 g7接收方 B 的公钥 yB3发送方 A 选择的随机数 k2明文 M30求密文 (c1,c2)解答1. ElGamal 加密公式c1g^k mod pc2M⋅yB^k mod p2. 计算 c1c172mod 7149 mod 71493. 计算 yB^kyBk329yBk3294. 计算 c2c230×9270 mod 71270÷713 余 270−3×71270−21357c2575. 密文(c1,c2)(49,57)7-18 椭圆曲线 E:y²x³x1mod 7求所有点步骤1枚举 x∈{0,1,2,3,4,5,6}计算 x³x1mod 7xx3x³x1模 7 值000 0 1 11111 1 1 33288 2 1 11432727 3 1 31346464 4 1 6969 - 9×7 69 - 63 65125125 5 1 131131 - 18×7 131 - 126 56216216 6 1 223223 - 31×7 223 - 217 6结果x0: 1x1: 3x2: 4x3: 3x4: 6x5: 5x6: 6步骤2判断每个值是否为模 7 的平方剩余模 7 的平方剩余1²12²43²24²25²46²1。所以平方剩余是1, 2, 4。aa是否为平方剩余yy平方根1是y±1≡1,63否—4是y±2≡2,53否—6否—5否—6否—步骤3列出所有点含无穷远点 Ox0: y1,6 → (0,1), (0,6)x2: y2,5 → (2,2), (2,5)其他 x 无解。加上无穷远点 O。最终答案O, (0,1), (0,6), (2,2), (2,5)共5个点。7-19 经典公钥密码体制主要建立在哪些数学难题基础之上请描述这些困难问题并对每一困难问题列举算法实例。数学难题描述算法实例大数分解给定npq求p,qRSA离散对数给定g,p,ygx求xElGamal、DSA椭圆曲线离散对数椭圆曲线上给定P,QkP求kECC、ECDSA背包问题给定向量A和和S求子集Merkle-Hellman已破Rabin函数模平方根问题Rabin加密7-20 公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的这两个问题是什么解答密钥分配问题对称密码中通信双方需共享密钥安全分配密钥困难。公钥密码中公钥可公开无需安全信道分配。数字签名问题对称密码无法实现不可否认的数字签名。公钥密码中私钥签名、公钥验证可实现数字签名。注以上内容的理解和计算如果有任何错误希望各位读者和大佬指出改正非常感谢
考研复习 Day 47 | 密码学--第七章 公钥密码（下）
发布时间：2026/6/8 3:08:12
注以下内容参考《新编密码学》范九伦 张雪锋 侯红霞 编著7.4 椭圆曲线密码7.4.1 椭圆曲线的定义与性质椭圆曲线是指由Weierstrass方程y²axybyx³cx²dxe所确定的平面曲线。在密码学中通常使用定义在有限域Zpp为素数上的椭圆曲线y²≡x³axb(modp)其中a,b∈Zp且4a³27b²≠0(modp)保证曲线非奇异。椭圆曲线上的所有点加上无穷远点OO构成一个Abel群Ep(a,b)。加法运算规则图7-2单位元无穷远点O逆元−P(x,−y)点加过P和Q的直线交曲线于RR则P⊕Q−R倍点过P的切线交曲线于R则2P−R坐标计算公式设P(x1,y1)Q(x2,y2)RP⊕Q(x3,y3)则例7.3Z₁₁上的椭圆曲线y²x³x6计算得E₁₁(1,6)共有13个点表7-1。取生成元g(2,7)可计算出g的所有幂倍点得到群中所有点。7.4.2 椭圆曲线上的密码体制椭圆曲线密码体制基于椭圆曲线上的离散对数问题给定Ep(a,b)上的两点P和Q寻找整数k使QkPkP表示P自加k次。已知k,P求Q容易反之困难。椭圆曲线ElGamal密码体制密钥生成取g∈Ep(a,b)选取私钥x计算公钥yxg加密对明文m嵌入为曲线上的点随机选取k计算c₁kgc₂m⊕ky密文c(c₁,c₂)解密mc₂⊕(−xc₁)例7.4取g(2,7)为E₁₁(1,6)的生成元私钥x7公钥y7g(7,2)。明文m(10,9)随机数k3加密得c((8,3),(10,2))解密得m(10,9)。7.4.3 椭圆曲线密码算法的特性安全性高椭圆曲线离散对数问题的最好算法Pollardρ时间复杂度为O(√N)而有限域上标准离散对数可用指数积分法亚指数时间求解。因此ECC更安全。密钥量小、运算速度快在同等安全级别下ECC密钥长度远小于RSA表7-2。例如1024位RSA约等于160位ECC2048位RSA约等于210位ECC密码资源丰富可通过改变曲线系数生成大量不同曲线灵活性好。注意事项应避免使用超奇异椭圆曲线易受MOV攻击和异常椭圆曲线可在线性时间内求解应确保循环子群的阶有大素因子至少160比特7.5 基于身份的公钥密码体制7.5.1 概述1984年Shamir提出基于身份密码学IBC的思想。用户的身份信息如电子邮件地址直接作为公钥私钥由私钥生成中心PKG产生。这省去了公钥证书的管理开销。与传统基于证书密码体制的对比对比项传统PKI基于身份密钥生成用户自选私钥计算公钥PKG根据身份生成私钥公钥获取需证书直接使用身份信息公钥保存需目录存放证书无需目录身份认证验证证书签名向PKG证实身份7.5.2 双线性Diffie-Hellman假设基于身份的加密方案由四个算法构成系统建立、私钥提取、加密、解密。双线性映射e:G₁×G₁→G₂满足双线性e(aP,bQ)e(P,Q)^(ab)非退化性存在P,Q使e(P,Q)≠1可计算性存在有效算法计算e(P,Q)双线性Diffie-Hellman问题给定(P,aP,bP,cP)计算e(P,P)^(abc)是困难的。7.5.3 Boneh和Franklin的IBE方案2001年Boneh和Franklin使用椭圆曲线上的Weil对设计了首个实用的IBE方案。系统建立生成群G₁,G₂和双线性映射e选取生成元P主密钥s∈Zq公钥PpubsP选择Hash函数H₁:{0,1}∗→G₁H₂:G₂→{0,1}^n私钥提取对用户身份ID计算QIDH₁(ID)私钥dIDsQID加密随机选取r计算密文C(rP,m⊕H₂(e(QID,rPpub)))解密mV⊕H₂(e(dID,U))7.6 公钥密码体制的应用7.6.1 RSA密码体制的应用解决密钥分发和管理问题公钥可公开私钥保密简化大规模网络中的密钥管理。实现数字签名私钥签名公钥验证满足唯一性和私有性要求。加密短小消息RSA加密速度慢约为DES的千万分之一适合短消息加密。7.6.2 椭圆曲线密码体制的应用ECDSA数字签名速度快、强度高、签名短如Microsoft CDKey。无线网络WAPI中国无线局域网国家标准采用ECC进行身份认证。Web服务器减少计算时间和带宽消耗。IC卡无需协处理器代码和密钥存储空间小成本低。习题7 解答7-1 简述公钥密码体制的一般定义解答公钥密码体制非对称密码体制是一种加密和解密使用不同密钥的密码体制。每个用户拥有一个密钥对公钥可公开和私钥保密。公钥用于加密私钥用于解密。从公钥推算出私钥在计算上不可行。一般定义为五元组(M,C,K,E,D)M明文空间C密文空间K密钥空间公钥-私钥对E加密算法集合D解密算法集合满足对任意密钥对(pk,sk)加密变换Epk:M→C和解密变换Dsk:C→M满足Dsk[Epk[m]]m。7-2 什么是单向陷门函数如何将其应用于公钥密码体制设计解答单向陷门函数是一个可逆函数f(x)满足正向计算给定x计算yf(x)容易逆向计算给定y计算xf^(−1)(y)困难存在陷门信息知道陷门时逆向计算容易应用于公钥密码设计公钥对应函数f正向计算私钥对应陷门信息逆向计算加密用公钥计算cf(m)解密用私钥计算mf^(−1)(c)RSA基于大数分解陷门f(x)x^e mod n陷门是p,q或d。7-3 简述公钥密码体制相对单钥密码体制的优势解答优势说明密钥分配简单公钥可公开无需安全信道传递密钥密钥数量少nn个用户只需nn个密钥对对称密码需n(n−1)/2个支持数字签名私钥签名公钥验证实现不可否认性支持密钥交换如Diffie-Hellman协议密钥管理方便可定期更换密钥公钥证书机制成熟7-4 简述RSA算法的理论基础解答RSA算法的理论基础是数论中的欧拉定理和模运算欧拉定理若gcd(a,n)1则a^φ(n)≡1(modn)RSA密钥关系选择ed≡1(mod φ(n))则存在整数k使ed1kφ(n)加解密正确性若gcd(m,n)1则m^(ed)m^(1kφ(n))≡m⋅(mφ(n))^k≡m(mod n)若gcd(m,n)≠1即p∣m或q∣m可类似证明安全性基础由n分解p,q困难从而由(n,e)求d困难7-5 在RSA体制中为什么加密指数e必须与模数n的欧拉函数φ(n)互素解答解密指数d满足ed≡1(modφ(n))。该同余方程有解的充要条件是gcd(e,φ(n))1。若gcd(e,φ(n))≠1则e在模φ(n)下无乘法逆元无法计算出解密密钥d从而无法正确解密。7-6 选择p7q17e5试用RSA算法对明文m19进行加密再对密文解密。解答计算np×q7×17119计算φ(n)(p−1)(q−1)6×1696验证gcd(e,φ(n))gcd(5,96)1合法计算解密指数de^(−1)mod 96。扩展欧几里得5×773854×961故d77加密cm^e mod n19⁵ mod 11919²361≡361−3×119361−357419⁴4²1619⁵19⁴×1916×19304≡304−2×119304−23866密文c66解密mc^d mod n66⁷⁷ mod 119利用欧拉定理66⁹⁶≡166⁷⁷66^(−19)计算较繁结果应为19答案密文c66解密得m197-7 对于npq定义Ψ(n)(p−1)(q−1)/gcd(p−1,q−1)。修改RSA体制为ed≡1mod Ψ(n)(1) 证明加密和解密仍然互逆证明设λΨ(n)lcm(p−1,q−1)。由欧拉定理对任意m与p互素m^(p−1)≡1(modp)故m^λ≡1(modp)对任意m与q互素m^λ≡1(modq)因此对任意m与p或q可整除有m^λ≡1(mod pq)。由ed≡1(modλ)存在整数k使ed1kλ。则m^(ed)m^(1kλ)m⋅(m^λ)^k≡m(mod n)故加解密互逆。(2) p37,q79,e7计算修改前后d的值原RSAn37×792923φ(n)36×782808de^(−1) mod 2808扩展欧几里得28087×4011故7×(−401)≡1−401 mod 28082407d2407修改后gcd(36,78)6Ψ(n)2808/6468Ψ(n)2808/6468d′7^(−1) mod 468扩展欧几里得4687×66676×11回代得17−67−(468−66×7)67×7−468故7×67≡1mod 468d′67答案原RSA中d2407修改后d677-8 证明RSA中不动点x∈Zn∗的个数为gcd(e−1,p−1)×gcd(e−1,q−1)证明不动点满足x^e≡x(modn)即x(x^(e−1)−1)≡0(modn)。模p下x(x^(e−1)−1)≡0(modp)解为x≡0或x^(e−1)≡1(modp)。x^(e−1)≡1(modp)的解数等于gcd(e−1,p−1)。加上x≡0对应x是p的倍数但要求x∈Zn∗故排除xx含p或q因子的情况实际只考虑与n互素的解。模p下非零解个数为gcd(e−1,p−1)模q下非零解个数为gcd(e−1,q−1)。由中国剩余定理模n下的解个数为两者乘积。因此不动点个数为gcd(e−1,p−1)×gcd(e−1,q−1)7-9 Rabin密码体制ek(x)x(xB)mod np199,q211,B1357(1) 计算加密yek(32767)n199×21141989y32767×(327671357)mod 4198932767×34124mod 41989先模n化简32767 mod 419893276734124 mod 4198934124计算乘积后取模具体数值需大数运算结果为某个y值。(2) 求密文y的四个可能解Rabin解密需解x(xB)≡y(modn)即x²Bx−y≡0(modn)。配方得(2xB)²≡B²4y(modn)。分别解模p和模q下的二次同余各得两个解组合得四个模n解。7-10 找出模13的全体本原根解答模13的乘法群Z13∗阶为12。本原根是阶为12的元素。先找一个本原根2是模13的本原根吗计算2¹2≠12²42³82⁴16≡32⁶64≡12≠12¹²4096≡12的阶为12故2是本原根模p的本原根个数为φ(p−1)φ(12)4。全部本原根为2^a其中gcd(a,12)1即a1,5,7,11计算2¹22⁵32≡62⁷128≡112¹¹2048≡7答案2,6,7,117-11 给定Zp上ElGamal密码体制p31847g5私钥a7899公钥y18074解密密文(3781,14409)解答解密公式mc₂⋅(c₁^a)^(−1) mod p计算c₁^a3781⁷⁸⁹⁹ mod 31847需快速幂p求其在模p下的逆元乘以c₂14409得到明文具体数值计算较繁最终可得明文m。7-12 椭圆曲线y²x³17P1(−2,3)P2(2,5)(1) −P1关于x轴对称−P1(−2,−3)(2) 2P1λ3x₁²a/2y₁2x₃λ²−2x₁8y₃λ(x₁−x₃)−y₁−23则2P1(8,−23)(3) P1⊕P2λy₂−y₁/x₂−x₁0.5若在实数域x₃λ²−x₁−x₂0.25−(−2)−20.25y₃λ(x₁−x₃)−y₁−4.1257-13 给定椭圆曲线E₂₃(13,22): y²x³13x22。取生成元g(10,5)私钥x7公钥y7g(17,21)。对消息P(11,1)随机数k13加密并解密。解答曲线E23(13,22): y²x³13x22生成元g(10,5)私钥x7公钥y7g(17,21)消息点P(11,1)随机数k13加密c₁kg13×(10,5)需在曲线上计算倍点ky13×(17,21)c₂P⊕ky密文(c₁,c₂)解密mc₂⊕(−xc₁)c₂⊕(−7×c₁)需逐次计算椭圆曲线上的点加和倍点得到最终结果。7-14 椭圆曲线Massey-Omura密码体制RSA的椭圆曲线版本设椭圆曲线阶为N公钥e私钥d满足ed≡1mod N。对E₂₃(13,22)N22消息点Pm(11,1)公钥e13私钥d17加密并解密。解答曲线E₂₃(13,22)阶N22消息点Pm(11,1)公钥e13私钥d17验证ed13×1722110×221≡1 mod 22正确。加密CePm13×(11,1)计算曲线上的13倍点解密PmdC17×C应恢复(11,1)7-15 已知椭圆曲线E:y²x³−4x−3(mod7)点p(−2,2)求2p,4p,6p解答先验证点是否在曲线上(−2)³−4×(−2)−3−88−3−3≡4(mod7)y²4正确。计算2pλ3x₁²a/2y₁2x₃λ²−2x₁4−2×(−2)448≡1(mod7)y₃λ(x₁−x₃)−y₁2×(−2−1)−22×(−3)−2−6−2−8≡−1≡6(mod7)2p(1,6)4p2×2p6p2p⊕4p继续计算可得。7-16 RSA密码体制(1) 取e3有什么优缺点取d3安全吗为什么优点加密速度快只有两次乘法适合公钥加密短消息缺点易受低加密指数攻击。若同一消息用多个不同模数加密e3可由中国剩余定理恢复明文d3是否安全不安全。若d3由ed≡1mod φ(n)可推出e攻击者可分解n。且Wiener攻击可破小d。(2) 设n35密文C10公钥e5求明文M。n35p5,q7φ(n)24。de^(−1)mod 245^(−1)mod 24。5×525≡1故d5。解密MC^d mod n10⁵ mod 3510²100≡3010⁴≡30²900≡2510⁵10⁴×10≡25×10250≡5答案M57-17 ElGamal 加密已知素数 p71本原根 g7接收方 B 的公钥 yB3发送方 A 选择的随机数 k2明文 M30求密文 (c1,c2)解答1. ElGamal 加密公式c1g^k mod pc2M⋅yB^k mod p2. 计算 c1c172mod 7149 mod 71493. 计算 yB^kyBk329yBk3294. 计算 c2c230×9270 mod 71270÷713 余 270−3×71270−21357c2575. 密文(c1,c2)(49,57)7-18 椭圆曲线 E:y²x³x1mod 7求所有点步骤1枚举 x∈{0,1,2,3,4,5,6}计算 x³x1mod 7xx3x³x1模 7 值000 0 1 11111 1 1 33288 2 1 11432727 3 1 31346464 4 1 6969 - 9×7 69 - 63 65125125 5 1 131131 - 18×7 131 - 126 56216216 6 1 223223 - 31×7 223 - 217 6结果x0: 1x1: 3x2: 4x3: 3x4: 6x5: 5x6: 6步骤2判断每个值是否为模 7 的平方剩余模 7 的平方剩余1²12²43²24²25²46²1。所以平方剩余是1, 2, 4。aa是否为平方剩余yy平方根1是y±1≡1,63否—4是y±2≡2,53否—6否—5否—6否—步骤3列出所有点含无穷远点 Ox0: y1,6 → (0,1), (0,6)x2: y2,5 → (2,2), (2,5)其他 x 无解。加上无穷远点 O。最终答案O, (0,1), (0,6), (2,2), (2,5)共5个点。7-19 经典公钥密码体制主要建立在哪些数学难题基础之上请描述这些困难问题并对每一困难问题列举算法实例。数学难题描述算法实例大数分解给定npq求p,qRSA离散对数给定g,p,ygx求xElGamal、DSA椭圆曲线离散对数椭圆曲线上给定P,QkP求kECC、ECDSA背包问题给定向量A和和S求子集Merkle-Hellman已破Rabin函数模平方根问题Rabin加密7-20 公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的这两个问题是什么解答密钥分配问题对称密码中通信双方需共享密钥安全分配密钥困难。公钥密码中公钥可公开无需安全信道分配。数字签名问题对称密码无法实现不可否认的数字签名。公钥密码中私钥签名、公钥验证可实现数字签名。注以上内容的理解和计算如果有任何错误希望各位读者和大佬指出改正非常感谢
时我踩过的雷)
)
