读书笔记
第11章 - 密码学工程设计原理与实际应用
11.1 Diffie-Hellman 协议
Diffie-Hellman协议是公钥密码学的里程碑，提出了一种有效的密钥管理方法。该协议允许双方在不安全的通信渠道上协商出相同的密钥，而不会被监听者获取。
- Diffie-Hellman协议的核心思想是使用一个加密密钥和解密密钥不同的加密算法，从而实现密钥的安全分发和管理。
- 该协议解决了传统密钥分发方式中密钥数量快速增长的问题，通过让通信双方使用一个公开的加密密钥来避免频繁的密钥交换。
11.2 群
Diffie-Hellman协议使用了模p乘法群Zp*，其中p为素数。群中的元素由生成元g产生，g的阶确定了群中元素的个数和性质。
- 在协议中，p为大素数，g为p的本原元，其阶为p-1。
- 群的阶决定了协议的安全性，生成元g的选择需要注意确保其具有足够高的阶，避免产生小的子群。
- DH问题即为计算离散对数问题，是解决协议安全性的关键。
11.3 中间人攻击
DH协议容易受到中间人攻击，导致通信双方无法辨别对方身份。中间人可伪装成通信双方，窃取密钥并窃听通信内容。
- 协议参与方需要采取措施确保通信双方身份的真实性，避免受到中间人攻击。
11.4 一些可能的问题
DH协议的实现需注意以下问题：
- 攻击者可能篡改通信中的参数，导致通信双方生成相同的弱密钥。
- 生成元g的选择需要注意，避免产生小的子群以确保协议的安全性。
- 使用安全素数可增强协议的安全性，通过选择合适的(p, q)参数集合，确保生成的密钥不易受到攻击。
11.5 安全的素数
安全素数选择对协议的安全性至关重要：
- 安全素数为形如2q+1的素数p，其中q也为素数，保证了生成的密钥具有较高的安全性。
- 使用Legendre符号函数可验证参数是否为平方数，避免了可能的安全漏洞。
以上是Diffie-Hellman协议的基本原理、安全性问题以及解决方案的总结。
11.6 使用较小的子群
使用安全素数方法的效率问题在于素数p的位数越大，计算量就越大。为了解决这个问题，可以采用较小的子群方法：
- 选择一个256位的素数q，并找到一个更大的素数p满足p = Nq + 1，其中N为任意值。
- 找到阶为q的元素g，验证其条件，使得(g ≠ 1) 且 (g^q mod p = 1)。
- 在通信中，所有数值都应该在g生成的子群中，接收方应该检查接收到的值是否在正确的子群中。
使用这种方法可以显著提高效率，因为计算的工作量会减少很多。
11.7 p的长度
选择正确长度的素数p对于DH系统的安全至关重要。为了满足安全需求，p的长度至少应该为6800位。然而，从性能的角度来看，这可能并不可行。对称密钥长度和公钥长度之间有很大差异，因此不能直接将其进行比较。通常对称密钥长度是固定的，而公钥长度可以根据需要变化。建议使用2048位作为最小值，并根据需求增加密钥长度。
11.8 实践准则
建立DH协议使用的子群时，应遵循以下准则：
- 选择256位的素数q和一个大素数p，使得p = Nq + 1，其中N是整数。
- 验证群参数，确保p和q都是素数，g是(p-1)的因子，且满足(g ≠ 1) 且 (g^q mod p = 1)。
- 参与方收到的每个数值都应验证是否在正确的子群中。
11.9 可能出错的地方
在DH协议中，检查接收到的数是否属于正确的子群至关重要，以避免小子群攻击。如果不检查这些数值，可能会导致安全漏洞，使攻击者能够获取关键信息。因此，验证接收到的值是否在正确的子群中是最简单、最健壮的解决方案。
12. 密码学工程设计和实际应用
12.1 引言
- RSA是最著名且广泛使用的公钥密码系统之一，同时提供数字签名和公钥加密功能。
- 基于解决大整数分解问题的困难性设计，这个问题吸引了广泛研究。
12.2 中国剩余定理
- CRT用于解决模合数n运算问题。
- 给出了Garner公式，用于高效计算x的原始值。
- CRT的应用可以提高模n计算效率，节省时间。
12.2.1 Garner公式
- Garner公式用于计算x的原始值，提高了计算效率。
12.2.2 推广
- CRT适用于多个不同素数乘积的情形，但更复杂。
- 在本书中不涉及更复杂的情况。
12.2.3 应用
- CRT在模n计算中的应用可节省大量时间。
- 加法和乘法运算中的CRT表示可大幅减少计算量。
- 对于指数运算，CRT也能带来时间节省。
12.2.4 结论
- 当n=pq时，CRT表示可用于加速模n的计算。
- CRT带来的额外软件复杂性和转换开销通常值得。
12.3 模n乘法
- 在RSA中，需要找到一个指数t使得x=1(mod n)对几乎所有的x都成立。
- 使用Euler函数φ(n)来计算t，通常为(p-1)(q-1)。
- 对于特殊情况x=0(mod p)，RSA的基本性质仍然成立。
12.4 RSA
RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，以下是其详细说明：
-
选择素数p和q：
- 随机选择两个不同的大素数p和q。
- 计算n = p * q。
-
选择公钥和私钥：
- 计算欧拉函数值t = lcm(p-1, q-1)。
- 选择两个不同的指数e和d，满足ed ≡ 1 (mod t)。
- 公开指数e，通常选取小奇数值。
- 使用扩展欧几里得算法计算e模t的逆元d，确保ed ≡ 1 (mod t)。
-
加密和解密：
- 加密消息m：计算密文c ≡ m^e (mod n)。
- 解密密文c：计算明文m ≡ c^d (mod n)。
-
密钥对：
- 公钥：(n, e)，分发给多个参与方。
- 私钥：(p, q, t, d)，由生成RSA密钥的人秘密保存。
-
简化表示：
- 通常将emodn写为c"mod n，简化操作。
- 指数都要取模t，d可记为1/e。
12.4.1 RSA数字签名
- RSA不仅可用于加密消息，还可用于对消息进行签名。
- 签名计算方式与加密相同，使用私钥计算消息的签名。
- 任何知道公钥的人都可以验证签名的有效性。
12.4.2 公开指数
- 若公开指数e与t = lcm(p-1, q-1)有公因子，则d没有解，因此需要小心选择p、q和e。
- 选择小的公开指数能提高RSA效率，常用e=3和e=5。
- 对加密和签名使用不同的公开指数可以消除相互影响。
12.4.3 私钥
- 知道公钥(n, e)，计算私钥(p, q, t, d)中的任何一个值都极其困难，基于因子分解的复杂性。
- 知道任何一个私钥值，都可以计算出其他值，合理假定私钥的拥有者掌握这些值。
12.4.4 n的长度
- 模n应与DH中的模p具有相同长度。
- 保护数据20年的最小n长度是2048位，建议取4096位。
- 两个素数p和q应具有相同长度。
12.4.5 生成RSA密钥
- 提供生成RSA密钥的例程，包括生成素数和计算密钥参数。
12.5 使用RSA的缺陷
- RSA存在结构性问题，可能导致多种攻击。
- 使用编码函数可消除结构，但标准化算法如PKCS#1 v2.1需谨慎使用，避免复杂性和实现规范的混淆。
12.6 加密
加密是RSA的典型应用，但实际中很少使用。RSA的消息长度受限于n的长度，且RSA操作耗时。解决方案是选择随机密钥K，RSA加密K，再用K加密实际消息m。这样可避免长度限制且减少RSA操作次数。一种更简单的方法是选择随机数r，并定义K为hash(r)模n的结果。这种方法简单而安全。
encryptRandomKeyWithRSA 函数
- 输入：RSA公钥(n, e)，其中e=5
- 输出：加密的对称密钥K和RSA密文e
- 计算k和选择随机数r，满足0≤r<2^k-1
- 计算K=SHA-256(r)
- 计算e = r^e mod n
- 返回(K, e)
decryptRandomKeyWithRSA 函数
- 输入：RSA私钥(n, d)，对应e=5，密文c
- 输出：加密的对称密钥K
- 确保0≤c<n
- 计算K=SHA-256(c^d mod n)
- 返回K
RSA安全性分析表明，即使K泄露给Eve，也不会暴露Alice的私钥。使用散列函数和不对r进行范围检查增强了安全性。
解释了即使发生K泄露给Eve的情况下，也不会暴露Alice的私钥信息。
12.7 签名
在签名方案中，对消息进行散列运算，将其转换为固定长度的值。然后使用RSA私钥对该值进行签名。签名验证时，将消息再次转换为相同的固定长度值，验证签名是否匹配。
MsgToRSANumber 函数
- 输入：RSA公钥n和消息m
- 输出：模n的值s
- 使用PRNG生成器生成随机数
- 计算k和x
- 将x mod n作为s的值返回
SignWithRSA 函数
- 输入：RSA私钥(n, d)，对应e=3，消息m
- 输出：消息m的签名a
- 将消息m转换为模n的值s
- 计算签名σ=s^d mod n
- 返回σ
VerifyRSASignature 函数
- 输入：RSA公钥(n, e)，其中e=3，消息m和签名σ
- 输出：验证签名是否有效
- 将消息m转换为模n的值s
- 断言s与σ mod n相等，否则抛出异常
RSA签名的安全性分析类似于RSA加密。只有知道私钥的人才能计算签名，验证签名的人可确认消息是由Alice签名的。
苏格拉底挑战
