RSA算法,为什么正好B=A^e2 mod n RSA的算法涉及三个参数,n、e1、e2.其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度. e1和e2是一对相关的值,e1可以任意取,但要求
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/20 03:28:31
RSA算法,为什么正好B=A^e2 mod n RSA的算法涉及三个参数,n、e1、e2.其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度. e1和e2是一对相关的值,e1可以任意取,但要求
RSA算法,为什么正好B=A^e2 mod n
RSA的算法涉及三个参数,n、e1、e2.
其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度.
e1和e2是一对相关的值,e1可以任意取,但要求e1与(p-1)*(q-1)互质；再选择e2,要求(e2*e1)mod((p-1)*(q-1))=1.
(n及e1),(n及e2)就是密钥对.
RSA加解密的算法完全相同,设A为明文,B为密文,则：
A=B^e1 mod n；
B=A^e2 mod n；
e1和e2可以互换使用,即： A=B^e2 mod n；B=A^e1 mod n;
第一个公式好理解A=B^e1 mod n；但是第二个公式不能理解,
为什么正好B=A^e2 mod n
RSA算法,为什么正好B=A^e2 mod n RSA的算法涉及三个参数,n、e1、e2.其中,n是两个大质数p、q的积,n的二进制表示时所占用的位数,就是所谓的密钥长度. e1和e2是一对相关的值,e1可以任意取,但要求
A^e2 mod n=B^(e1*e2)mod n,------1
因为e1*e2=1mod[(p-1)(q-1)],所以e1*e2=r*[(p-1)(q-1)]+1,为了表达简洁些,把（p-1）(q-1)表示成a,1式就变为B^(a+1)mod n-----2
下面分情况讨论
当B和n互素的时候,根据欧拉定理（B^a=1mod n）,显然1式=B
当B和n不互素的时候,由于n=p*q,B必然能被p或者q整除,假设B=k*p,则B与q互素,再运用欧拉定理,B^(q-1)=1mod q,B^[(p-1)(q-1)]=1mod q,即B^a=1mod q,所以B^a=t*q+1,两边同时乘以B=k*p,得：B^(a+1)=k*t*p*q+1=k*t*n+1,显然B^(a+1)=1mod n
不是大数的蒙氏算法么。
- -
RSA 算法中(e2*e1)mod((p-1)*(q-1))=1。这*号是(e1 x e2) (mod z) 其中，-1次方只是个逆元的表示记号而已，是仿照以前的“倒数”的