文档教程知识库【免费下载链接】CS-Xmind-Note计算机专业课408思维导图和笔记计算机组成原理第五版 王爱英数据结构王道计算机网络第七版 谢希仁操作系统第四版 汤小丹项目地址https://gitcode.com/gh_mirrors/cs/CS-Xmind-Note点击查看免费下载本文依据仓库笔记 信息安全/信息安全四——公私钥密码体制.md 展开系统梳理公钥密码非对称密码的思想起源、设计原理、三大代表体制Diffie-Hellman、RSA、ElGamal及支撑它们的数论基础并通过完整数值实例逐步推演加解密过程。读完本文你将理解公钥与对称密码各自的优劣与分工、陷门单向函数如何支撑双钥体系以及每个算法在加密/解密、数字签名、密钥交换三大场景中的定位。本仓库的信息安全系列笔记以《密码编码学与网络安全第六版斯托林斯》为蓝本见 README.md本章是其中承上启下的一环上游是 信息安全二——密码学.md基本概念与 信息安全三——对称密码体制.mdDES/AES 等对称算法下游是 信息安全五——消息认证、数字签名及PGP.md公钥体制在签名与 PGP 中的落地完整目录见 信息安全/README.md。一、公钥与对称密码的取舍从对称算法的优劣势说起对称密码单钥密码与公钥密码双钥密码的根本差异已在 信息安全二——密码学.md 中给出定义对称算法加密密钥与解密密钥相同或实质等同从一个易于推出另一个非对称算法则恰好相反。理解了两者各自的优缺点也就理解了为什么现代密码体系往往采用公钥做密钥管理、对称做数据加密的混合结构。1.1 对称加密的优点速度快、处理量大适用于对应用数据的直接加密是数据面加密的主力。密钥长度相对较短通常在 40 比特256 比特量级相比公钥密码动辄上千比特的密钥管理和存储成本低。可构造各种加密体制在对称密码之上可以构建伪随机数发生器、HASH 函数等多种密码原语用途灵活。1.2 对称加密的缺点密钥分发困难通信双方必须持有相同且保密的密钥密钥的传递本身就是一个安全问题。密钥管理规模爆炸大型网络中每对通信方都需要独立的密钥密钥量大、难以管理一般需要可信第三方TTP如密钥分发中心 KDC介入。密钥需要经常更换使用周期短频繁更换进一步加剧了管理负担。无法实现抗抵赖传统对称加密算法无法解决数字签名问题——因为密钥共享无法向第三方证明某条消息确实出自某一方。1.3 公钥加密的优点密钥保密面窄只有秘密钥私钥需要保密公开钥公钥完全可以公开分发。密钥生命周期相对较长密钥对可以长期使用无需频繁更换。天然支持数字签名许多公钥方案可以产生数字签名机制解决抗抵赖需求。密钥数量少在大型网络上每个用户只需一对密钥所需的密钥总量相对较少n 个用户仅需 n 对密钥而对称体制在理想情况下需要 C(n,2) 个会话密钥。1.4 公钥加密的缺点速度慢、处理量少数学运算复杂大数模幂运算只适合处理小量关键数据如密钥交换、消息摘要的签名。密钥长度相对较长同等安全强度下远长于对称密钥见 4.4 节性能对比。安全性没有得到理论证明公钥密码的安全性建立在某些数学难题计算上不可行的假设之上而非已被证明的绝对结论。维度对称加密公钥加密密钥关系加密/解密密钥相同或等同公钥公开、私钥保密处理速度快适合大量数据加密慢适合少量关键数据如密钥交换密钥长度40256 比特量级相对较长数百至上万比特密钥管理大网络中密钥量大需 TTPKDC每用户一对密钥数量少密钥更换需要经常更换生命周期相对较长数字签名无法实现抗抵赖可产生数字签名机制安全性证明—尚未得到理论证明依赖计算难题二、公钥密码体制的思想从密钥分配难题到陷门单向函数2.1 起源1976 年的划时代论文与 1978 年的 RSA公钥密码体制的诞生有两个标志性节点1976 年Stanford 大学的 Diffie 博士与导师 Hellman 在 IEEE Trans. on IT 上发表划时代文献W. Diffie and M. E. Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22, No.6, Nov 1976, PP.644-654。这一体制的出现为解决计算机信息网中的安全提供了新的理论和技术基础被公认为现代公钥密码学诞生的标志。1978 年MIT 的三位数学家 R. L. Rivest、A. Shamir 和 L. Adleman 发明了一种用数论构造双钥体制的方法称作 MIT 体制后被广泛称为RSA 体制。值得注意的是信息安全二——密码学.md 中的密码学发展脉络也印证了这一时间线1976 年之后密码学进入新方向——公钥密码学阶段公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。2.2 基本原理基于数学函数的双钥体制与古典及对称密码基于替换和置换不同公钥算法基于数学函数并且使用两个独立的密钥。公钥密码学的提出是为了解决对称密码的两个根本问题密钥的分配无需事先共享秘密即可建立安全信道数字签名提供对称密码无法实现的身份认证与抗抵赖。基本思想每个用户拥有自己的密钥对 (K~U~, K~R~)即公开密钥私有密钥。公钥 K~U~ 公开私钥 K~R~ 保密。A 向 B 发送消息时A→BY E_KUb(X) // 用 B 的公钥加密明文 X B D_KRb(Y) D_KRb(E_KUb(X)) X // 用 B 的私钥解密任何攻击者即使截获密文 Y 并掌握 B 的公钥也无法在计算上可行的时间内恢复明文 X。2.3 公钥体制的主要特点加密和解密能力分开公钥能加密只有私钥能解密反之私钥签名、公钥验签能力同样分离。多对一保密通信多个用户加密的消息只能由一个用户解读适用于公共网络中实现保密通信。一对多认证/签名只能由一个用户加密消息而使多个用户可以解读可用于认证系统中对消息进行数字签字。无需事先分配密钥打破了对称密码必须预共享密钥的限制。密钥持有量大大减少每人只需维护自己的密钥对和少量他人的公钥。提供对称密码无法或很难提供的服务如与哈希函数联合运用可生成数字签名可证明安全的伪随机数发生器的构造以及零知识证明等。2.4 公钥算法的安全条件一个可用的公钥算法涉及三类参与者发送方、接收方、攻击者和四类数据公钥、私钥、明文、密文必须满足以下条件产生一对密钥是计算可行的已知公钥和明文产生密文是计算可行的加密容易接收方利用私钥来解密密文是计算可行的解密容易对于攻击者利用公钥来推断私钥是计算不可行的已知公钥和密文恢复明文是计算不可行的可选加密和解密的顺序可交换——这一性质使得同一算法既能用于保密通信也能用于数字签名先签名后加密或先加密后签名的变体。2.5 如何设计一个公钥算法陷门单向函数设计的核心难点在于公钥和私钥必须相关但从公钥到私钥不可推断必须要找到一个难题从一个方向走是容易的从另一个方向走是困难的还要把这个难题与加解密操作结合起来。因此一个实用的公开密钥方案的发展依赖于找到一个陷阱门单向函数Trapdoor One-way Function。满足下列条件的函数 f 称为单向陷门函数给定 x计算 y fk(x) 是容易的正向单向给定 y计算 x 使 x fk-1(y) 是不可行的无陷门时逆向困难存在陷门 k已知 k 时对给定的任何 y若相应的 x 存在计算 x 使 fk-1(y) 是容易的持有陷门者可逆。直观理解函数对所有人都是单向的但设计者额外保留了一把陷门即私钥拥有陷门的人可以反向计算其他人不可以。2.6 支撑公钥体制的数学难题非对称密钥加密使用数学上的复杂计算问题作为安全基石正向计算容易反向计算困难计算机不可能在有效的时间内算出反向结果从而不可能破解密码。典型的例子与对应体制包括难题说明对应体制大数乘积 vs 大整数分解计算两个大数的乘积非常容易分解一个很大的数如 200 多位非常困难——若该大数只含有两个非常大的素数各 100 多位作为因子大整数分解问题IFPRSA 体制背包问题已知子集和求原集合难背包体制历史上曾被破译二次剩余问题判断一个数是否为模 n 的二次剩余—模 n 的平方根问题已知平方求模 n 平方根难—离散对数问题DLP有限域乘法群上的离散对数问题ElGamal 体制椭圆曲线离散对数问题ECDLP定义在有限域椭圆曲线上的离散对数问题类比的 ElGamal 体制ECC2.7 公钥密钥的应用范围公钥密码主要承担三类任务这也是本文后续三大体制各自的主战场加密/解密用公钥加密、私钥解密实现保密通信数字签名身份鉴别用私钥签名、公钥验证实现认证与抗抵赖密钥交换协商出会话密钥交给高速的对称算法使用。三、Diffie-Hellman 密钥协商协议3.1 算法思想与安全基础Diffie-HellmanDH密钥交换算法允许两个用户安全地交换一个秘密信息用于后续的通讯过程。它的巧妙之处在于通信双方不需要预先共享任何秘密就能在公开信道上协商出一个共享密钥。算法的安全性依赖于计算离散对数的难度。补充理解DH 本身解决的是密钥协商而非加密协商出的共享密钥通常交给对称算法使用。另外需要说明的是单纯的 DH 协议不包含身份认证易受中间人攻击实际系统如 TLS中会结合数字签名或证书对参与方进行认证数字签名的机制在 信息安全五——消息认证、数字签名及PGP.md 中有展开。3.2 算法步骤双方选择素数 p 以及 p 的一个原根 a注素数 p 以及原根 a 可由一方选择后发给对方用户 A 选择一个随机数 Xa p计算 Ya aXamod p用户 B 选择一个随机数 Xb p计算 Yb aXbmod p每一方保密 X 值私密数而将 Y 值公开数交换给对方用户 A 计算共享密钥 K YbXamod p用户 B 计算共享密钥 K YaXbmod p双方获得同一个共享密钥 aXaXbmod p。正确性在于A 算出的 (aXb)Xa与 B 算出的 (aXa)Xb在数学上相等均为 aXa·Xbmod p而攻击者虽然能窃听到 a、p、Ya、Yb但要由它们恢复 Xa或 Xb即计算离散对数是困难的。3.3 数值实例推演密钥交换基于素数 q 97 和 97 的一个原根 a 5。A 和 B 分别选择秘密密钥 Xa 36 和 Xb 58每人计算其公开密钥如下Y_a 5^36 mod 97 50 Y_b 5^58 mod 97 44交换公开密钥以后每人计算共享的秘密密钥如下A : K (Y_b)^X_a mod 97 44^36 75 mod 97 B : K (Y_a)^X_b mod 97 50^58 75 mod 97双方协商出共享密钥 75。从公开信息 {50, 44} 出发攻击者要计算出 75 很不容易——这正是离散对数难题在起作用。四、RSA 算法的数学原理4.1 密钥对的生成RSA 体制的建立分四步选择两个大素数 p、qp ≠ q——p、q 私有选定后保密计算 n p·qn 21024笔记中以此为示例取值——n 公开计算得出实际部署中模长通常取 2048 位及以上选择整数 e使得 gcd(e, φ(n)) 1——e 公开选定其中 φ(n) 为欧拉函数见 6.4 节计算 d ≡ e-1mod φ(n)——d 保密计算得出即 d 是 e 模 φ(n) 的乘法逆元可用扩展欧几里德算法求解其流程在 信息安全二——密码学.md 中有表格式推演。于是得到公钥KU {e, n}私钥KR {d, n}4.2 加解密与正确性加密明文 M nC M^e mod n 解密 M C^d mod n正确性验证依赖欧拉定理的推论若 n p·qp、q 为不同素数则对任意 0 ≤ m ≤ n 有 mk·φ(n)1≡ m mod n。由于 e·d ≡ 1 mod φ(n)即 e·d k·φ(n)1因此C^d (M^e)^d M^(e·d) M^(k·φ(n)1) ≡ M mod n从而解密 M Cdmod n 能恢复明文。安全性则建立在 2.6 节所述的大整数分解问题IFP上攻击者若能从公开的 n 分解出 p、q就能计算 φ(n) 并推出私钥 d而分解大整数在计算上不可行。4.3 数值实例推演选 p 7q 17则n p·q 119 φ(n) (p-1)(q-1) 6 × 16 96 取 e 5小于 96且与 96 互为素数 d 77 ∵ 5×77 385 4×96 1 ≡ 1 mod 96公钥 (5, 119)私钥 (77, 119)加密 M 19C M^e mod n 19^5 mod 119 66 mod 119解密 C 66M C^d mod n 66^77 mod 119 19 mod 119明文 19 被成功恢复验证了 RSA 加解密过程的正确性。4.4 性能定位RSA 与 DES 的取舍从教材中的DES 和 RSA 性能比较同等强度可知为达到相近的安全强度RSA 所需的密钥长度远大于 DES数十比特的对称密钥需对应成百上千比特的 RSA 模数且 RSA 的加解密处理速度远慢于 DES。因此实际系统几乎从不直接用 RSA 加密大块数据而是采用混合体制用 RSA 加密/交换体积很小的会话密钥再用 DES/AES 等对称算法加密实际数据。这种公钥管密钥、对称管数据的分工正是本章开篇对比两种算法优缺点的实践意义所在。RSA 的定位总结基础难题为IFP大整数分解问题同时支持加/解密、密钥交换、数字签名三种用途是使用最广泛的公钥密码体制。五、ElGamal基于离散对数的公钥密码5.1 参数选择与密钥生成ElGamal 加密算法由 ElGamal 于 1984、1985 年提出在密码协议中有着大量应用是除 RSA 之外最有代表性的公开密钥密码。它是一种基于有限域 GF(p) 上的离散对数问题DLP的公钥密码体制既可用于加密又可用于签名。参数选择与密钥生成选择一个素数 pp 的一个原根本原元r以及一个整数 a0 ≤ a ≤ p-2计算 s ramod p公开 {p, r, s}保密 aa 即私钥{p, r, s} 即公钥材料。5.2 加密与解密加密对明文信息 x秘密选择随机数 k0 ≤ k ≤ p-2计算二元组 (y1, y2) 作为密文y1 r^k mod p y2 x · s^k mod p解密x y2 · (y1^a)^(-1) mod p正确性验证利用 s ra(x·s^k) · ((r^k)^a)^(-1) ≡ x·r^(ak) · r^(-ak) ≡ x mod p5.3 非确定性概率加密ElGamal 加密算法是非确定性的因为每次加密都要选择一个随机数 k相同的明文随着加密前随机数 k 的不同产生不同的密文。这一特性使得同一明文反复加密也不会产生相同的密文从而抵抗某些统计分析攻击代价是密文膨胀为原来的两倍两个元素 y1、y2。5.4 安全基础与应用ElGamal 的安全性建立在DLP离散对数问题之上从公开的 {p, r, s} 恢复私钥 a等价于求解 s ramod p 中的离散对数 a而该问题在计算上是困难的。与 RSA 相同ElGamal 亦可用于加/解密、密钥交换、数字签名其签名方案及验证流程在 信息安全五——消息认证、数字签名及PGP.md 中单独展开PGP 也大量采用了 ElGamal 类体制。六、数论基础公钥密码的地基数论是密码学特别是公钥密码学的基本工具研究离散数字集合的相关问题。RSA 依赖大整数分解与欧拉定理DH 与 ElGamal 依赖原根与离散对数以下概念构成了这些体制的数学地基。6.1 素数与互素数素数称整数 pp 1是素数如果 p 的因子只有 ±1、±p。最大公因子若满足下面两个条件则称 c 是两个整数 a、b 的最大公因子记为 c gcd(a, b)c 是 a 的因子也是 b 的因子即 c 是 a、b 的公因子a 和 b 的任一公因子也是 c 的因子。互素如果 gcd(a, b) 1则称 a 和 b 互素。RSA 要求 gcd(e, φ(n)) 1 即为此概念。6.2 模运算与同余设 n 是一正整数a 是整数用 n 除 a得商为 q、余数为 r用a mod n表示余数 r。若 (a mod n) (b mod n)则称两整数 a 和 b模 n 同余记为 a ≡ b mod n。称与 a 模 n 同余的数的全体为 a 的同余类记为 [a]称 a 为该同余类的表示元素。注意如果 a ≡ 0 (mod n)则 n | a。同余的性质若 n | (a-b)则 a ≡ b mod n(a mod n) ≡ (b mod n)则 a ≡ b mod na ≡ b mod n则 b ≡ a mod na ≡ b mod nb ≡ c mod n则 a ≡ c mod n。求余数运算 a mod n 将整数 a 映射到集合 {0, 1, …, n-1}称求余运算在这个集合上的算术运算为模运算其核心性质如下即先取模再运算与先运算再取模等价[(a mod n) (b mod n)] mod n (a b) mod n [(a mod n) - (b mod n)] mod n (a - b) mod n [(a mod n) × (b mod n)] mod n (a × b) mod n6.3 费马小定理费马Fermat定理p 为素数a 是整数且不能被 p 整除则a^(p-1) ≡ 1 mod p例a 7p 19则 ap-1 718≡ 1 mod 19。费马小定理是欧拉定理在模数为素数时的特例也常用于素性检验。6.4 欧拉函数与欧拉定理欧拉Euler函数 φ(n)表示小于 n 且与 n 互素的正整数个数。例如 φ(6) 21 和 5。基本性质p 是素数φ(p) p - 1。例φ(7) 6若 n 的因子分解为 n ∏piaiai 0pi互不相同则 φ(n) n·∏(1 - 1/pi)若 gcd(m, n) 1则 φ(mn) φ(m)·φ(n)。特别地若 p、q 都是素数则 φ(pq) (p-1)(q-1)。例φ(21) 12 φ(3)×φ(7) 2×6。这正是 RSA 中 φ(n) (p-1)(q-1) 的来源。欧拉定理若 a 与 n 为互素的正整数则a^φ(n) ≡ 1 mod n例a 3n 10φ(10) 434 81 ≡ 1 mod 10。欧拉定理的等价形式a^(φ(n)1) ≡ a mod n推论若 n p·qp ≠ q 都是素数k 是任意整数则对任意 0 ≤ m ≤ n 有m^(k·φ(n)1) m^(k(p-1)(q-1)1) ≡ m mod n这条推论正是 4.2 节中 RSA 加解密正确性的数学依据。6.5 原根与离散对数原根Primitive root欧拉定理表明对两个互素的整数 a、n 有 aφ(n)≡ 1 mod n。定义存在最小正整数 m ≤ φ(n)且 m | φ(n)使得 am≡ 1 mod n若对某个 a这个最小正整数 m φ(n)则称 a 是 n 的一个原根。离散对数若 a 是素数 p 的一个原根则对任意整数 bb ≠ 0 mod p存在唯一的整数 i1 ≤ i ≤ p-1使得b ≡ a^i mod p称 i 为 b 以 amod p为底的指数离散对数记作 inda,p(b)。它满足两个类似对数的性质ind_a,p(xy) [ind_a,p(x) ind_a,p(y)] mod φ(p) ind_a,p(x^r) [r × ind_a,p(x)] mod φ(p)离散对数的计算难度对 y ≡ gxmod p已知 g、x、p计算 y 是容易的模幂运算快速幂可在多项式时间内完成已知 y、g、p计算 x 是困难的无已知多项式时间算法。这种正向容易、逆向困难的不对称性正是 Diffie-Hellman 密钥协商与 ElGamal 加密的安全性根基。七、总结三大公钥体制一览体制安全基础密钥材料典型用途特点Diffie-HellmanDLP离散对数素数 p 原根 a私密数 Xa/Xb密钥交换只协商密钥不直接加密无认证需结合签名RSAIFP大整数分解n p·q公钥 {e, n}、私钥 {d, n}加/解密、密钥交换、数字签名使用最广泛确定性加密密文与明文一一对应ElGamalDLP离散对数素数 p 原根 rs ra公开 {p, r, s}、保密 a加/解密、密钥交换、数字签名非确定性概率加密相同明文产生不同密文三者的共同逻辑链条清晰可循公钥体制要解决的问题是密钥分配与数字签名 → 解决工具是陷门单向函数 → 具体实例来自大整数分解RSA与离散对数DH、ElGamal两大数学难题 → 而这一切又建立在数论同余、欧拉函数/定理、原根、离散对数之上。掌握本文的推演路径后可继续阅读仓库配套笔记 信息安全五——消息认证、数字签名及PGP.md了解公钥密码如何与哈希函数结合最终落地为数字签名与 PGP 邮件加密等真实应用。赞分享文档教程知识库【免费下载链接】CS-Xmind-Note计算机专业课408思维导图和笔记计算机组成原理第五版 王爱英数据结构王道计算机网络第七版 谢希仁操作系统第四版 汤小丹项目地址https://gitcode.com/gh_mirrors/cs/CS-Xmind-Note点击查看免费下载相关推荐OpenSSL密钥交换协议Diffie-Hellman与ECDH实现OpenSSL密钥交换协议Diffie Hellman与ECDH实现 1. 密钥交换协议基础 密钥交换Key Exchange是加密通信的基础环节负责在密码学网络安全通信5个创新方法重构API集成策略的完整指南5个创新方法重构API集成策略的完整指南 在当今的微服务架构时代API已成为现代应用开发的基石。面对数百个API服务的选择开发者常常陷入选择困难症如文档Crypto公钥密码学RSA加密与签名实践终极指南Crypto公钥密码学RSA加密与签名实践终极指南 Crypto是一个强大的免费C加密库提供了完整的RSA公钥密码学实现。RSA加密是现代安全通密码学后端上一篇探索高效开发ch32v003fun 项目推荐下一篇zigimg核心功能解析一站式掌握图像格式检测与像素操作创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考