RSA算法

一、算法概述

RSA属于"非对称加密"算法，与传统的对称加密不同，它使用一对密钥：公钥和私钥。公钥可以公开分享，用于加密数据；而私钥必须严格保密，用于解密数据。这种特性使得RSA成为安全通信的理想选择。

二、密钥生成流程

1. 选择两个大素数

首先随机选择两个大素数p和q。在实际应用中，这些素数通常有数百位长，以保障安全性。

p = 61  // 示例用的素数，实际应用中要大得多
q = 53

2. 计算模数n

计算n = p × q。这个n将作为公钥和私钥的一部分。

n = p × q = 61 × 53 = 3233

3. 计算欧拉函数φ(n)

欧拉函数φ(n)表示小于n且与n互质的正整数的个数。对于n = p×q，φ(n) = (p-1)(q-1)

φ(n) = (p-1)(q-1) = 60 × 52 = 3120

4. 选择公钥指数e

选择一个整数e，满足：

• 1 < e < φ(n)

• e与φ(n)互质（即gcd(e, φ(n)) = 1）

通常选择65537(0x10001)，因为它计算效率高且安全性好。

e = 17  // 示例值

5. 计算私钥指数d

d是e关于φ(n)的模反元素，即满足：
d × e ≡ 1 mod φ(n)

这可以通过扩展欧几里得算法计算得出。

d = 2753  // 因为17 × 2753 = 46801 ≡ 1 mod 3120

6. 最终密钥对

• 公钥：(n, e) = (3233, 17)

• 私钥：(n, d) = (3233, 2753)

三、加密过程

假设Bob想发送加密消息给Alice：

1. Alice将自己的公钥(n, e)发送给Bob

2. Bob将消息转换为整数m（0 ≤ m < n）

3. Bob计算密文c = mᵉ mod n

4. Bob发送c给Alice

示例：
假设m = 65（ASCII字符'A'）
c = 65¹⁷ mod 3233 = 2790

四、解密过程

Alice收到密文后：

1. 使用私钥(n, d)计算m = cᵈ mod n

2. 将整数m转换回原始消息

示例：
m = 2790²⁷⁵³ mod 3233 = 65