若通信双方使用RSA单向陷门函数加解密信息， 已知接收方公钥 (en)=(5,35)，截获密文为C=10，求明文M.

在RSA加密中，加密过程为 $C\equiv M^e \pmod n$，其中 $n=pq$ 为两个大质数的乘积，$e$ 为加密密钥，$C$ 为密文，$M$ 为明文。

在本题中，接收方公钥为 $(e,n)=(5,35)$，即 $n=35$, $e=5$。已知密文 $C=10$，我们需要求解明文 $M$。

由于加密过程中使用了单向陷门函数，我们需要使用接收方的私钥才能解密。接收方的私钥 $d$ 可以通过求解如下同余方程得到：

$$
ed \equiv 1 \pmod {\varphi(n)}
$$

其中 $\varphi(n)$ 表示欧拉函数，对于任意正整数 $n$，有 $\varphi(n)$ 表示小于等于 $n$ 的正整数中与 $n$ 互质的数的个数。对于素数 $p$，$\varphi(p)=p-1$。对于两个不同的素数 $p$ 和 $q$，$\varphi(pq)=(p-1)(q-1)$。

在本题中，$n=35=5\times7$，$\varphi(n)=(5-1)(7-1)=24$。因此，我们需要求解以下同余方程：

$$
5d \equiv 1 \pmod {24}
$$

通过计算可得，$d=5$ 是方程的一个解。因此，接收方的私钥为 $d=5$。

接下来，我们可以使用接收方的私钥将密文 $C=10$ 解密为明文 $M$：

$$
M \equiv C^d \pmod n
$$

代入参数，得

$$
M \equiv 10^5 \pmod {35} \equiv 25 \pmod {35}
$$

因此，原始明文为 $M=25$。

相关问题

设通信双方使用RSA公钥密码体制，接收方的公钥是（e，n）=（3，253），接收的密文是c=110，求明文m。

根据RSA公钥密码体制的加密过程，密文c是明文m经过加密得到的，即：

c = m^e mod n

代入已知的参数，即可得到：

110 = m^3 mod 253

为了求解明文m，需要将上式转化为求解m的形式。这里可以尝试暴力枚举m的取值，从1到252依次代入上式计算，找到使得等式成立的m值即可。但是这种方法显然不太可行，因为需要计算252次。

更好的方法是使用RSA算法中的解密过程，根据公钥和私钥的关系，可以得到：

d = e^-1 mod φ(n)

其中，φ(n)表示欧拉函数，对于素数p和q，有φ(n) = (p-1)(q-1)。在本题中，n = 253 = 11 × 23，因此φ(n) = 10 × 22 = 220。将e = 3代入上式，可以得到d = 147。

解密过程如下：

m = c^d mod n = 110^147 mod 253 = 191

因此，明文m为191。

设通信双方使用RSA公钥密码体制，接收方的公钥是（e，n）=（3，253），接收的密文是c=110，求明文m

根据RSA公钥密码体制的加密过程，密文c = m^e mod n，其中m为明文。

将给定的参数代入公式，得到：

110 = m^3 mod 253

将253分解质因数，得到253 = 11 * 23。

根据模运算的性质，m^3 mod 253 = (m^3 mod 11) * (m^3 mod 23) mod 253。

因为3是比较小的指数，可以通过枚举的方式找到满足条件的m。

首先，计算m^3 mod 11，因为11是质数，根据费马小定理，m^(11-1) mod 11 = 1，即m^10 mod 11 = 1。因此，m^3 mod 11 的取值只有0、1、-1三种情况。

接下来，计算m^3 mod 23。由于23比较大，不能直接用费马小定理。可以采用快速幂算法，将3表示为二进制形式：3 = 2^1 + 2^0，然后进行幂运算：

m^3 mod 23 = m^(2^1) * m^(2^0) mod 23 = (m^2 mod 23) * (m^1 mod 23) mod 23

接着，使用快速幂算法计算m^2 mod 23 和 m^1 mod 23：

m^1 mod 23 = m mod 23

m^2 mod 23 = (m^1)^2 mod 23 = (m mod 23)^2 mod 23

最后，将m^3 mod 253表示为m^3 mod 11和m^3 mod 23的乘积：

m^3 mod 253 = (m^3 mod 11) * (m^3 mod 23) mod 253

根据前面的计算结果，m^3 mod 11的取值只有0、1、-1三种情况，而m^3 mod 23的取值可以通过快速幂算法得到。可以将这两个取值的组合列出来，计算它们的乘积，看看哪个乘积等于110 mod 253。

m^3 mod 11 | m^3 mod 23 | m^3 mod 253
-----------|-------------|-------------
0 | 0 | 0
1 | 1 | 1
-1 | 22 | 157

可以看到，只有m^3 mod 23 = 22时，才有可能满足条件。因此，可以将m^3 mod 23 = 22带入前面的快速幂算法中，计算出m的取值：

m^1 mod 23 = m mod 23

m^2 mod 23 = (m^1)^2 mod 23 = (m mod 23)^2 mod 23

m^4 mod 23 = (m^2)^2 mod 23 = ((m mod 23)^2)^2 mod 23

m^8 mod 23 = (m^4)^2 mod 23 = (((m mod 23)^2)^2)^2 mod 23

m^16 mod 23 = (m^8)^2 mod 23 = ((((m mod 23)^2)^2)^2)^2 mod 23

m^22 mod 23 = (m^16) * (m^4) * (m^2) * (m^0) mod 23 = ((((((m mod 23)^2)^2)^2)^2) * ((m mod 23)^2) * m) mod 23

因此，m^3 mod 23 = 22时，m的取值为：

m = ((((((m mod 23)^2)^2)^2)^2) * ((m mod 23)^2) * m) mod 253

代入m^3 mod 253 = (m^3 mod 11) * (m^3 mod 23) mod 253，可以得到：

110 = (-1) * 22 mod 253

即110 + 253k = -22，解得k = 1，因此：

m = ((((((m mod 23)^2)^2)^2)^2) * ((m mod 23)^2) * m) mod 253 = 153

因此，明文m为153。