RSA算法

Public Key Cryptography

RSA 方法概述

现在Alice想要和Bob发送消息，设\(p\)和\(q\)是两个大素数（在密码学中，指几百位数甚至上千位数的素数，人们常用512、1024甚至2048位的素数），并定义\(N=pq\)，我们将发送给Bob的消息视为在模\(N\)下的数字(除0,1)；另外，设\(e\)是相对素数为\((p-1)(q-1)\)的任何数（通常选择较小的值以提高加密速度），那么Bob的公匙为一对数字\((N,e)\)，而Bob的私匙是\(d\)，它需要满足条件\(ed \pmod{(p-1)(q-1)} ≡ 1\)。
[Encryption加密] 假设Alice想要向Bob发送消息\(x\)，\(x\)为整数且\(\pmod{N}\)，那么她计算\(E(x) ≡ x^e \pmod{N}\)并发送；
[Decryption解密] Bob收到后，计算\(D(y)≡y^d \pmod{N}\)，还原出原始消息\(x\)。

Theorem 7.1: Under the above definitions of the encryption and decryption functions \(E\) and \(D\), we have \(D(E(x)) ≡ x \pmod{N}\) for every possible message \(x ∈ \{0, 1, . . . , N − 1\} \).

---

Theorem 7.2: [Fermat’s Little Theorem] For any prime \(p\) and any \(a ∈ \{1, 2, . . . , p−1\}\), we have \(a^{p−1} ≡ 1 \pmod{p}\).

---

Theorem 7.3: [Prime Number Theorem] Let \( \pi(n) \) denote the number of primes that are less than or equal to \( n \). Then for all \( n \geq 17 \), we have \[ \pi(n) \geq \frac{n}{\ln n}. \]