已知RSA的公钥(e,n)计算对应的私钥d

今天分享一个软考中经常出现的关于RSA私钥计算的题目。我们试着理解背后的算法逻辑，然后再看看如何解题。

设在RSA的公钥密码体制中，公钥为（e, n）= (13, 35), 则私钥d= （）。

A. 17

B. 15

C. 13

D. 11

RSA 算法

Rivest Shamir Adleman（RSA）加密算法是一种非对称加密算法，广泛应用于许多产品和服务中。非对称加密使用一对密钥（私钥和公钥），公钥是任何人都可以访问的，而私钥是密钥创建者才知道的秘密。可以使用私钥或公钥进行数据加密，然后用另一个密钥进行数据解密。

比如用户A生成一对密钥并将公钥公开。当用户B需要向用户A发送机密信息的时候，用户B使用A的公钥对机密信息进行加密再发送给A，用户A使用自己的私钥对加密信息进行解密。另一方面，用户A可以使用自己的私钥对机密信息进行签名然后发给用户B，用户B再使用A的公钥来验证签名。

算法描述

公钥

1. 任意选取两个不同的大素数p和q，计算乘积 n = p*q;

   质数是指在大于1的自然数中，除了1和它本身以外不再有其他因素的自然数。

2. 任意选取一个大整数e，满足gcd (e, (p-1) (q-1)) = 1;

** **gcd：最大公约数, e的选取比较容易，比如所有大于p和q的素数都可用

1. 公钥为（e, n）

私钥

1. 使用公式 {d*e} mod {(p-1) (q-1)} = 1 来计算；

mod，是一个数学运算符号。指取模运算符，算法和取余运算(REM)相似例如a mod b=c，表明a除以b余数为c

1. 密钥为（d, n）

解题思路

1. 已知 公钥为（e, n）= (13, 35)，即e = 13，n = 35；

2. n = p*q，得到p=5, q=7 (或者 p=7, q = 5)；

3. 计算得出 (p-1) (q-1) = 24；

4. 将以上参数代入公式 {de} mod {(p-1) (q-1)} = 1，即 {d13} mod 24 = 1

5. 分别计算4个选项，看看哪一个满足条件

   {17*13} mod 24 = 5

   {15*13} mod 24 = 3

   {13*13} mod 24 = 1

   {11*13} mod 24 = 23

   所以第三个答案满足条件，即d = 13，所以答案选C