Question

使用RSA加密体制，接收方的公开密钥是（e,n）=（5,35）,接收到的密文是C =10,求明文M.

2011-2012学年《 现代密码学》考试题

Answer 1

M=C^e mod 35
mod为除法取余
10^5mod35＝5
100000÷35＝2857.5

Answer 2

RSA加密算法：
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.(e,n)是公钥，(d,n)是私钥
由n=35得到p,q分别为5,7。由(d * e) ≡ 1 (mod ((p-1)(q-1)) )得d=29.
明文M=C^dmodn=10^29mod35=5