CS70Disc 04A

1 RSA Warm-Up

在学习RSA加密算法时，需要掌握以下关键知识点：

RSA基本原理：

RSA是一种非对称加密算法，主要用于安全数据传输。

密钥由公钥（$N, e$）和私钥（$N, d$）组成，$N$是两个大质数$p$和$q$的乘积。

公钥与私钥的生成：

选择两个大于3的不同质数$p$和$q$。

计算$N = pq$。

计算$(p-1)(q-1)$，并选择一个小于$(p-1)(q-1)$且与$(p-1)(q-1)$互质的整数$e$（常用的选择是小质数如3、5、17等）。

计算私钥$d$，使得$ed \equiv 1 \mod (p-1)(q-1)$。

加密与解密过程：

加密：给定明文$x$，使用公钥进行加密，计算$E(x) = x^e \mod N$。

解密：给定密文$y$，使用私钥进行解密，计算$D(y) = y^d \mod N$。

互质与欧几里得算法：

$e$必须与$(p-1)$和$(q-1)$互质，这通常通过计算最大公约数（gcd）来验证。

扩展欧几里得算法用于求解私钥$d$。

中国剩余定理：

在解密过程中，如果模数$N$由两个互质数$p$和$q$组成，可以利用中国剩余定理（CRT）来简化解密计算。

步骤

公钥和私钥的生成：

确定质数$p$和$q$。

计算模数$N$和$(p-1)(q-1)$。

选择合适的$e$。

计算私钥$d$。

消息的加密：

使用公钥对消息进行加密。

消息的解密：

使用私钥对接收到的密文进行解密，并使用中国剩余定理进行简化计算。

Note 7: 考虑一个RSA方案，其模数为 $ N = pq $，其中 $ p $ 和 $ q $ 是大于 3 的不同质数。

(a) 使用 $ e = 2 $ 作为RSA公钥有什么问题？

若 $ e = 2 $，则我们需要满足 $ (e, (p-1)(q-1)) = 1 $ 才能找到私钥 $ d $。
由于 $ p $ 和 $ q $ 是不同的奇质数，因此 $ (p-1)(q-1) $ 必然是偶数。
因此，$ (e, (p-1)(q-1)) = 2 $，不存在私钥。
这表明 $ e $ 应该避免使用偶数，更一般地说，$ e $ 不应为偶数。

(b) 找到一个关于 $ p $ 和 $ q $ 的条件，以使 $ e = 3 $ 成为有效的指数

为了让 $ e = 3 $ 有效，必须满足 $ (e, p-1) = 1 $ 和 $ (e, q-1) = 1 $。
由于 3 是质数，因此 $ p-1 $ 和 $ q-1 $ 不能被 3 整除。
这意味着 $ p $ 和 $ q $ 必须是形式为 $ 3k + 1 $ 或 $ 3k + 2 $ 的质数。如果 $ p $ 或 $ q $ 的形式是 $ 3k $（即可被 3 整除），那么它们就不是质数。

(c) 假设 $ p = 5 $，$ q = 17 $，且 $ e = 3 $。求公钥。

公钥由 $ (N, e) $ 组成，其中： $ N = p q = 5 = 85 $
因此，公钥为 $ (85, 3) $。

(d) 求私钥。

私钥 $ d $ 需要满足 $ ed (p-1)(q-1) $。
首先计算 $ (p-1)(q-1) $：$ (p-1)(q-1) = 4 = 64 $
需要满足： $ 3d $
通过扩展的欧几里得算法，我们可以找到 $ d $。最终得出 $ d = 43 $。

(e) 爱丽丝想要将消息 $ x = 10 $ 发送给鲍勃。她使用公钥加密消息 $ E(x) $。

加密函数为： $ E(x) = x^e N $
代入数据： $ E(10) = 10^3 $
计算 $ 10^3 = 1000 $：$ 1000 = 65 $
所以，爱丽丝发送的加密消息为 $ 65 $。

(f) 假设鲍勃收到爱丽丝发送的消息 $ y = 19 $。他用什么方程解密消息？解密后的消息是什么？

解密函数为： $ D(y) = y^d N $
代入数据： $ D(19) = 19^{43} $
使用中国剩余定理（CRT）进行解密：

根据 CRT，对于互质的数 $ p $ 和 $ q $，如果：$ x a p $ $ x b q $ 则有： $ x = aqq_1 + bpp_1 pq $ 其中 $ p_1 = p^{-1} q $ 和 $ q_1 = q^{-1} p $。

在本例中，$ p = 5 $ 和 $ q = 17 $，所以：$ x ^{43} x ^{43} $

计算 $ 19^{43} $：
- $ 19 = 4 $
- 因此 $ 19^{43} ^{43} $
计算 $ 19^{43} $：
- 使用费马小定理，得 $ 19^{16} $，因此：$ 19^{43} = 19^{16 + 11} ^2 ^{11} ^{11} $
- 计算 $ 19^{11} $，由于 $ 19 $，所以：$ 2^{11} $
- 计算出 $ 2^4 $, $ 2^8 $, 所以：$ 2^{11} = 2^{8} ^{3} $

根据中国剩余定理，我们知道：

$ x $
$ x $

我们计算 $ p_1 $ 和 $ q_1 $：

$ p_1 = 5^{-1} = 7 $
$ q_1 = 17^{-1} = 3 $

代入中国剩余定理： $ x + 8 $ 计算得到： $ x + 280 $ 进一步计算： $ x + 280 $ 最后得出： $ x $ 因此，解密后的消息 $ D(y) = 59 $。

RSA 多密钥加密

背景知识： RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，广泛用于安全数据传输。RSA 加密依赖于两个大素数的乘积 $N = pq$，其中 $p$ 和 $q$ 是大于 3 的不同质数。公钥由 $ (N, e) $ 组成，其中 $e$ 是加密指数。私钥通过 $d$ 来计算，满足 $ed \equiv 1 \mod (p-1)(q-1)$。

题目描述：

一个秘密社团的成员使用相同的公钥指数 $e$ 加密和传输秘密词 $x$。假设一个窃听者 Eve 观察到了多个公钥和它们对应的加密传输。我们需要分析 Eve 如何利用这些信息来破解加密。

(a) Eve 如何破解加密

公钥信息： Eve 观察到的公钥有 $ (p_1q_1, 7) $ 和 $ (p_1q_2, 7) $，可以得知：
- $N_1 = p_1q_1$
- $N_2 = p_1q_2$
破解步骤：
1. 计算 $ (N_1, N_2) $:$ (p_1q_1, p_1q_2) = p_1 $ 由于 $q_1$ 和 $q_2$ 是不同的素数，且 $p_1$ 是公因数，因此可以通过欧几里得算法高效计算最大公约数。
2. 通过求出 $p_1$，可以分别计算出 $q_1$ 和 $q_2$：
  - 由 $N_1 = p_1q_1$ 和 $N_2 = p_1q_2$ 可得： $ q_1 = , q_2 = $
结论： 因此，Eve 能够破解加密，因为她可以通过求最大公约数获得 $p_1$，进而找出 $q_1$ 和 $q_2$。

(b) Eve 为什么不能破解新选择的 N

新公钥信息： 现在的公钥是 $ (p_1q_1, 3) $、$ (p_2q_2, 3) $ 和 $ (p_3q_3, 3) $，其中：
- $N_1 = p_1q_1$
- $N_2 = p_2q_2$
- $N_3 = p_3q_3$
破解分析：
1. 没有公共因数： 由于所有的 $p_1$、$p_2$、$p_3$、$q_1$、$q_2$、$q_3$ 都是不同的素数，任何两个 $N_i$ 都没有公共因数。
2. 无法使用 GCD 方法： Eve 不能像之前那样计算最大公约数来找出任何公共因数，因此也无法利用公钥的信息来破解加密。
结论： 在这种情况下，Eve 无法通过 GCD 方法找到任何信息，无法破坏加密。

(c) Eve 如何找到未改变的秘密 x

假设条件： 假设秘密 $x$ 没有改变，仍然使用 $e = 3$ 的相同公钥，传输的消息为： $ x^3 N_1, x^3 N_2, x^3 N_3 $
破解步骤：
1. 利用中国剩余定理（CRT）： Eve 观察到的加密消息是 $x^3$ 对 $N_1$、$N_2$、$N_3$ 的取模结果，由于 $N_1$、$N_2$、$N_3$ 是互质的，Eve 可以使用 CRT 将这些方程结合起来： $ x^3 a_1 N_1 $ $ x^3 a_2 N_2 $ $ x^3 a_3 N_3 $
2. 求解 $x^3 \mod (N_1N_2N_3)$: 通过 CRT，Eve 可以得到 $x^3$ 在 $N_1N_2N_3$ 模下的值。
3. 求解 x： 由于 $x < N_1$、$x < N_2$、$x < N_3$，因此可以直接得到： $ x^3 < N_1N_2N_3 $ 因此，Eve 可以从 $x^3$ 中计算出 $x$： $ x = $
结论： Eve 最终可以通过 CRT 计算出 $x^3$，然后直接求立方根得到 $x$，从而成功破解信息。

RSA 用于演唱会门票号码

背景知识： RSA（Rivest-Shamir-Adleman）是一种常用的非对称加密算法，用于在不安全的通道上安全地传输信息。RSA 的安全性依赖于大素数的乘积，常用的公钥格式为 $ (N = pq, e) $，其中 $N$ 是大于 512 位的数，$p$ 和 $q$ 是两个大素数。

题目描述：

Alice 想告诉 Bob 她的演唱会门票号码 $m$（整数范围为 0 到 100），但不想让窃听者 Eve 知道这个号码。

(a) Eve 如何得知 Alice 的票号

情况分析： Bob 公布了他的公钥 $ (N, e) $。Alice 使用 RSA 加密她的消息，并将加密后的结果发送给 Bob。由于 $m$ 的可能值仅为 101 个（0 到 100），Eve 可以进行穷举。
破解步骤：
1. Eve 知道 Alice 的票号只能是 0 到 100 之间的整数。
2. Eve 逐一尝试所有可能的票号 $m$： $ c = m^e N $ 其中 $c$ 是 Alice 发送的加密消息。
3. 对于每一个可能的 $m$，Eve 计算 $m^e \mod N$，并与收到的密文 $c$ 进行比较，找到匹配的值。
结论： 因此，Eve 能通过穷举所有 101 个可能的票号 $m$ 来确定 Alice 的演唱会票号。

(b) Alice 如何使用随机数 r 保护票号

新方案： Alice 选择一个随机数 $r$，其长度为 256 位（足够难以猜测），然后她将 $r$ 和 $r^m$ 加密并发送给 Bob。Alice 发送：
- $x = r^e \mod N$
- $y = (r^m)^e = r^{em} \mod N$
破解步骤：
1. Eve 得到 $x$ 和 $y$：
  - $x$ 是 $r$ 的加密结果，Eve 也知道 $y$ 是 $r^{em}$ 的加密结果。
2. 计算 $r^{-1} \mod N$：
  - Eve 可以使用扩展欧几里得算法找到 $x$ 的逆元 $x^{-1} \mod N$。
3. 求得 $m^e \mod N$：
  - 使用 $x^{-1}$ 乘以 $y$ 得到： $ m^e y x^{-1} N $
4. 破解 $m$：
  - 由于 $m$ 的可能值仍然在 0 到 100 之间，Eve 可以通过穷举方法计算所有可能的 $m$ 的 $m^e$，并与之前得到的结果进行比较： $ m^e z N $ 找到匹配的 $m$。
另一种方法：
- 对于所有 101 个可能的 $m$，Eve 计算 $y = r^{em} \mod N$ 并与接收到的 $y$ 进行比较，确定匹配的票号。
结论： 尽管 Alice 引入了随机数 $r$ 以增加安全性，Eve 仍然可以通过计算和比较的方式确定票号 $m$。