### RSA算法实现报告
#### 实验环境
- **硬件配置**：处理器：Intel(R) Core(TM) i5-2430M CPU @ 2.40GHz (4CPUs), ~2.4GHz；内存：2048MB RAM
- **软件工具**：
- 操作系统：Windows 7 旗舰版
- 开发工具：Microsoft Visual C++ 6.0
#### 实验涉及的相关概念与基本原理
**RSA算法**是一种非对称加密算法，由Ron Rivest, Adi Shamir 和 Leonard Adleman在1977年提出。它具有以下特点：
- **应用广泛**：既能用于数据加密也能用于数字签名。
- **安全性**：基于大数分解难题，即从公钥和密文推断出明文的难度等同于分解两个大素数的积。
- **密钥生成**：
- 选择两个大素数\( p \)和\( q \)。
- 计算\( n = pq \)。
- 随机选择加密密钥\( e \)，要求\( e \)和\( (p-1)(q-1) \)互质。
- 使用扩展欧几里得算法计算解密密钥\( d \)，满足\( ed \equiv 1 \mod{(p-1)(q-1)} \)。
**加密过程**：
- 将明文\( m \)（通常为二进制形式）分为长度为\( s \)的数据块\( m_1, m_2, \ldots, m_i \)。
- 对每个数据块\( m_i \)，计算密文\( c_i = m_i^e \mod{n} \)。
**解密过程**：
- 对每个密文\( c_i \)，计算明文\( m_i = c_i^d \mod{n} \)。
**RSA的应用场景**：
- **数据加密**：用于保护传输过程中的敏感数据。
- **数字签名**：确保数据的完整性和来源的真实性。
#### 安全性考虑
**大数分解**：RSA的安全性依赖于大数分解的难度。虽然尚未有确凿证据表明破解RSA必须通过大数分解，但分解\( n \)仍然是最明显的攻击方式。
- 随着技术的进步，能够分解的素数越来越大，因此\( n \)必须足够大才能保证安全。
**速度**：RSA算法执行的是大数运算，因此其运行速度远低于对称加密算法如DES。一般用于少量数据的加密或用于生成会话密钥。
**选择密文攻击**：RSA容易受到选择密文攻击，即攻击者可以构造特定的密文，通过合法的解密方获取敏感信息。为防止此类攻击，需要采取额外的措施，例如：
- 使用好的公钥协议。
- 在签名前对数据进行哈希处理。
- 不对陌生人提供的随机文档签名。
**公共模数攻击**：如果多个用户共享相同的模数\( n \)，即使各自的\( e \)和\( d \)不同，也可能会导致安全漏洞。攻击者可以通过已知的\( e_1, e_2, C_1, C_2 \)计算出明文\( P \)。避免这种情况的方法是确保每个用户都有独立的\( n \)。
**小指数攻击**：选择过小的公钥指数\( e \)可能导致安全问题。通常推荐使用较大的\( e \)值来增强安全性。
#### 实验内容
**产生大数的方法**：
- 方法名称：`GetPrime()`
- 实现思路：利用Java语言中的`java.math.BigInteger`类生成随机大数。
**判断素数的方法**：
- 方法名称：`MillerRobin(BigInteger num)`
- 实现思路：采用Miller-Rabin素性测试算法，这是一种概率性算法，用于确定一个给定的数是否为素数。
以上实验内容展示了如何在C++环境下实现RSA算法的基本功能，并提供了相关的数学基础和安全注意事项。通过这些内容的学习与实践，可以更好地理解RSA算法的工作原理及其在实际应用中的优势和局限性。
