#6392. 「THUPC2018」密码学第三次小作业 / Rsa

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

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

RSA 的基本原理如下:

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

n^{e}\equiv c\pmod N

  • 消息解密:利用密钥 d 进行解密

c^{d}\equiv n\pmod N

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

c_1=m^{e_1}\bmod N

c_2=m^{e_2}\bmod N

现在,一个攻击者截获了 c_1​ c_2​ e_1​ e_2​ N​ ,请帮助他恢复出明文 m​

输入格式

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

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

输出格式

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

  • 一个非负整数 m ,请选手务必在输出时保证 0\le m<N 。答案 m 保证与 N 互质。

样例

样例输入

1
1502992813 2511821915 653507 57809 2638352023

样例输出

19260817

数据范围与提示

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

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