Question

根据RSA算法，选择两个素数p=11,q=7,设公钥n=77,e=7，私钥是多少？

Answer 1

N=pq=7*11=77
(p-1)(q-1)=6*10=60
根据公式d×
e
≡
1
(mod
(p-1)(q-1))
又e=7,所以
7*d≡
1
(mod
60)。。即
7d
mod
60
=
1。
7x43=301。。301除以6刚好余1.
所以d=43
______________________________________________
下面是公式依据：
假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥：
1.随意选择两个大的质数p和q，p不等于q，计算N=pq。
2.根据欧拉函数，不大于N且与N互质的整数个数为(p-1)(q-1)
3.选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1)
4.用以下这个公式计算d：d×
e
≡
1
(mod
(p-1)(q-1))
5.将p和q的记录销毁。
e是公钥，d是私钥。d是秘密的，而N是公众都知道的。Alice将她的公钥e传给Bob，而将她的私钥d藏起来。