作业帮有关于RSA算法的问题.
来源：学生作业帮 编辑：作业帮 分类：数学作业 时间：2024/05/11 02:53:52
有关于RSA算法的问题.
我看到RSA加密算法,
“
1 任意选取两个不同的大质数p和q,计算乘积r=p*q.
2 任意选取一个大整数e,e与（p-1）*（q-1）互质,整数e用做加密密钥.注意：e的选取是很容易的,所有大于p和q的质数都可用.
3 确定解密密钥d：d * e = 1 mod（p - 1）*（q - 1）根据e、p和q可以容易地计算出d.
4 公开整数r和e,但是不公开d.
5 将明文P（P是一个小于r的整数）加密为密文C,计算方法为C = P^e mod r .
6 将密文C解密为明文P,计算方法为：P = C^d modulo r .
”
我很不理解其中几个含义,一个是步骤3,“d * e = 1 mod（p - 1）*（q - 1”这个式子是怎么计算d的?
另外一个是“C = P^e mod r”和“ P = C^d modulo r”,就是说我不懂这2个式子的含义.是“C=P的e次方的结果,再除以r的余数”嘛?第二个就更不懂了.
我看到RSA加密算法,
“
1 任意选取两个不同的大质数p和q,计算乘积r=p*q.
2 任意选取一个大整数e,e与（p-1）*（q-1）互质,整数e用做加密密钥.注意：e的选取是很容易的,所有大于p和q的质数都可用.
3 确定解密密钥d：d * e = 1 mod（p - 1）*（q - 1）根据e、p和q可以容易地计算出d.
4 公开整数r和e,但是不公开d.
5 将明文P（P是一个小于r的整数）加密为密文C,计算方法为C = P^e mod r .
6 将密文C解密为明文P,计算方法为：P = C^d modulo r .
”
我很不理解其中几个含义,一个是步骤3,“d * e = 1 mod（p - 1）*（q - 1”这个式子是怎么计算d的?
另外一个是“C = P^e mod r”和“ P = C^d modulo r”,就是说我不懂这2个式子的含义.是“C=P的e次方的结果,再除以r的余数”嘛?第二个就更不懂了.
第一次看公钥的时候也没明白,现在懂了.先解释一下 X = Y mod Z 的含义吧：X = Y+kZ,k是整数.mod Z操作是对等号两边都作用的,不只是对Y作用的.
步骤3算d的方法：
d = (1 + k(p-1)(q-1)) / e , k是整数,使得d也是整数即可.
C=P^e mod r的解释：加密过程.P的e次方除以r的余数为C.
P=C^d mod r的解释：解密过程.把 C=P^e mod r带入此式,用一点数论的知识就能证明其正确性了.建议百度百科RSA,或 http://en.wikipedia.org/wiki/RSA_(algorithm)
再问： 谢谢您。您已经回答我的问题了。 继续请教您下，“d = (1 + k(p-1)(q-1)) / e"这个式子是如何计算出来d的呢？就比如假设p=101,q=107,e=109。所以d=（1+k*100*106）/109，d是如何推断出来的？ 非常感谢。为您加分哈~
再答： 没事儿。就是把k=1~N带进去试。计算稍微麻烦点，给你两行matlab代码吧，一下就计算出来k=4,d=389了。 k = 1:100; i = find(mod(1+k.*10600,109)==0); d=(1+k(i)*10600)/109;
步骤3算d的方法：
d = (1 + k(p-1)(q-1)) / e , k是整数,使得d也是整数即可.
C=P^e mod r的解释：加密过程.P的e次方除以r的余数为C.
P=C^d mod r的解释：解密过程.把 C=P^e mod r带入此式,用一点数论的知识就能证明其正确性了.建议百度百科RSA,或 http://en.wikipedia.org/wiki/RSA_(algorithm)
再问： 谢谢您。您已经回答我的问题了。 继续请教您下，“d = (1 + k(p-1)(q-1)) / e"这个式子是如何计算出来d的呢？就比如假设p=101,q=107,e=109。所以d=（1+k*100*106）/109，d是如何推断出来的？ 非常感谢。为您加分哈~
再答： 没事儿。就是把k=1~N带进去试。计算稍微麻烦点，给你两行matlab代码吧，一下就计算出来k=4,d=389了。 k = 1:100; i = find(mod(1+k.*10600,109)==0); d=(1+k(i)*10600)/109;