2. 在 RSA 公开密钥系统中,若截获了发给一个公开密钥 e=3,n=33 的密文 c=2,请计算明文是什么? （10 分）

在RSA加密中，密文c和明文m的关系为：c = m^e mod n，其中e是公钥中的指数，n是公钥中的模数。

根据题目给出的公钥 e=3, n=33 和密文c=2，我们可以得到：

m = c^d mod n

其中d为私钥，需要通过对公钥进行分解得到。在本题中，n=33=3*11，由于3和11都是质数，因此可以直接使用欧拉函数求出d，即：d = (p-1)(q-1) = 2*10 = 20。

现在我们需要求出2的20次方对33取模的结果。为了避免计算量过大，我们可以使用快速幂算法进行计算，具体步骤如下：

1. 将20转换为二进制数，得到10100。

2. 从右往左遍历二进制数，若当前位为1，则将结果乘以当前底数的幂，否则不做操作。每乘一次后，将底数自乘一次取模，即可得到最终结果。

按照上述步骤，我们可以得到：

2^20 mod 33 = (2^4)^5 mod 33 = 16^5 mod 33 = 16*16*16*16*16 mod 33 = 16

因此，明文m = c^d mod n = 2^20 mod 33 = 16。

所以，明文为16。

相关问题

2. 在 RSA 公开密钥系统中,若截获了发给一个公开密钥 e=3,n=33 的密文 c=2,请计算明文是什么?

在 RSA 公开密钥系统中，密文 c 和明文 m 的关系是：

c = m^e mod n

其中，e 和 n 是接收方的公开密钥，m 是发送方发送的明文，c 是发送方加密后得到的密文。

根据题意，我们已知公钥 e = 3 和 n = 33，密文 c = 2。因此，我们可以列出如下方程：

2 = m^3 mod 33

为了求解明文 m，我们可以尝试枚举 m 的值，直到找到一个满足方程的 m。由于 n = 33，我们可以考虑从 0 到 32 枚举 m 的值，然后依次计算 m^3 mod 33 的结果，直到找到一个等于 2 的结果。这个过程可以用程序来实现，也可以手动计算。

经过计算，我们可以得到明文 m = 5，因此，原始的明文就是 5。

rsa算法中n=11413,e=7467,密文是5859,利用分解11413=101*113,求明文。

RSA算法中，n是两个大素数p和q的乘积，即n=p*q。同时，e是与(p-1)(q-1)互质的数。

由题可知，n=11413，其质因数分解为101和113。

我们需要求解d，使得d ≡ e^(-1) (mod (p-1)(q-1))。

首先计算(p-1)(q-1)=(101-1)(113-1)=100*112=11200。

然后计算e的模逆：
7467 ≡ d (mod 11200)
即找到整数d，使得7467d ≡ 1 (mod 11200)。

通过扩展欧几里得算法可以得到：
7467*581 = 1 + 11200*(-49)

所以，d ≡ 581 (mod 11200)。

经过计算可以得到d=581。

最后，利用公式：明文 ≡ 密文^d (mod n)。
即明文 ≡ 5859^581 (mod 11413)。

通过计算得到明文为5523。

所以，明文为5523。