试题出自试卷《密码学基本理论（学习包章节练习题）》

问题1选项
A.11
B.13
C.15
D.17

B

RSA算法：已知e，n；n=p*q（p、q为素数)；n的欧拉函数p(n)=(p-1)*(q-1)；d*e=1modp(n)，其中d为密钥。

题干中已知n=35，则可推断ρ（n）=（5-1）*（7-1）=24，则d*e≡1 mod 24，算出d=13。答案选择B选项。计算过程如下：

13d≡1 mod 24

辗转相除法：

24 = 13*1 + 11        【x(n-2) = 1】

13 = 11*1 + 2          【x(n-1) = 1】

11 = 2*5 + 1            【x(n) = 5】

2 = 1*2 + 0

Z数组：     5    1    1

Y数组：1   5    6    11

注：（1）Z数组组成：            x(n)    x(n-1) ....    x(1)

        （2）Y数组组成：y(1)    y(2)    y(3)      .....y(n)；其中，y(1)=1，y(2) = x(n)，y(3) = y(1) + y(2)*x(n-1)，其他以此类推。

        （3）如果Z数组个数为偶数个，则y(n)为逆元；如果Z数组为奇数个，则p(n) - y(n)为逆元。

上述Z数组个数为奇数，所以 d的值为24 - 11 = 13。