#P5451. [THUPC2018] 密码学第三次小作业

[THUPC2018] 密码学第三次小作业

题目背景

1977年,罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)提出了RSA 加密算法。RSA 加密算法是一种非对称加密算法,其可靠性由极大整数因数分解的难度决定。换言之,对一极大整数做因数分解愈困难,RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话,那么用 RSA 加密的信息的可靠性就肯定会极度下降。

RSA 的基本原理如下:

  • 公钥与私钥的产生
    1. 随机选择两个不同大质数 ppqq,计算 N=p×qN=p\times q
    2. 根据欧拉函数性质,求得 r=φ(N)=φ(p)φ(q)=(p1)(q1)r=\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)
    3. 选择一个小于 rr 的正整数 ee,使 eerr 互质。并求得 ee 关于 rr 的乘法逆元 dd,有 ed1(modr)ed\equiv 1 \pmod r
    4. ppqq 的记录销毁。此时,(N,e)(N,e) 是公钥,(N,d)(N,d) 是私钥。
  • 消息加密:首先需要将消息 mm 以一个双方约定好的格式转化为一个小于 NN,且与 NN 互质的整数 nn。如果消息太长,可以将消息分为几段,这也就是我们所说的块加密,后对于每一部分利用如下公式加密:
nec(modN)n^{e}\equiv c\pmod N
  • 消息解密:利用密钥 dd 进行解密
cdn(modN)c^{d}\equiv n\pmod N

题目描述

现在有两个用户由于巧合,拥有了相同的模数 NN,但是私钥不同。设两个用户的公钥分别为 e1e_1e2e_2且两者互质。明文消息为 mm,密文分别为:

$$\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix} $$

现在,一个攻击者截获了 c1c_1c2c_2e1e_1e2e_2NN,请帮助他恢复出明文 mm

输入格式

输入包含多组数据,第一行一个整数 TT 表示数据组数,保证 1T1041\le T\le 10^4 。接下来依次描述每组数据,对于每组数据:

  • 一行包含五个正整数 c1c_1c2c_2e1e_1e2e_2NN,保证 28<N<2632^{8}< N < 2^{63}NN 有且仅有两个素因子,其余数据严格按照上述RSA算法生成。

输出格式

对于每组数据,输出 11 行:

  • 一个非负整数 mm,请选手务必在输出时保证 0m<N0\le m<N。答案 mm 保证与 NN 互质。
1
1502992813 2511821915 653507 57809 2638352023
19260817

提示

版权信息

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。