灰灰的密码 / 【模板】RSA共模攻击

灰灰的密码 / 【模板】RSA共模攻击

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

题目背景

1977年,Ron Rivest、Adi Shamir和Leonard Adleman一起发明了RSA加密算法。一个简易版的算法流程如下。

  • 首先随机选取两个大质数\(p,q\),令\(N=pq\)。
  • 令\(\Phi(x)\)表示比\(x\)小的和\(x\)互质的整数个数,可以证明\(\Phi(N)=(p-1)(q-1)\)。
  • 随机选取一个与小于\(\Phi(N)\)且与\(\Phi(N)\)互质的整数\(e\),计算其逆元\(d\),也就是满足\(ed\equiv 1\mod \Phi(N)\)的唯一的\(d\)。
  • 对外界公布\(e,N\)但不公布\(p,q,d\)。
  • 当有人想要加密一个消息\(m\)的时候,首先需要保证\(gcd(m,N)=1\),然后他会计算\(c\equiv m^e\mod N\)。
  • 如果你需要解密,则根据费马小定理我们有\(c^d\mod N\equiv c^{ed}\mod N\equiv m\)。
  • 费马小定理是对于任意\(N\)和与\(N\)互质的\(a\): \[a^{\Phi(N)}\equiv 1\mod N.\]

题目内容

灰灰在监听名飞与大猪比的通信,名飞和大猪比使用RSA算法进行加密。
灰灰截获了五个整数\(N,e_1,e_2,c_1,c_2\),你可以看作是两个对于同一个消息\(m\)的加密。具体来说他们满足
\[
\left\{
\begin{aligned}
&gcd(e_1,e_2)=1\\
&m^{e_1}\equiv c_1\mod N\\
&m^{e_2}\equiv c_2\mod N
\end{aligned}
\right.
\]

现在,数学不好的灰灰想让你帮他解出\(m\)。
总共有\(q\)组询问,每次都会给出一组\(N,e_1,e_2,c_1,c_2\),你需要回答所有的询问。
虽然可以,但尽量不要尝试对\(N\)做质因数分解

输入输出格式

输入格式

第一行一个整数\(q\),表示询问组数。
之后\(q\)行,每行五个整数\(N,e_1,e_2,c_1,c_2\),表示一组询问。

输出格式

一共\(q\)行,每行一个整数\(m\),输出的\(m\)需要在\([0,N-1]\)中。

样例

样例输入1

3
15 5 7 8 2
15 3 5 4 4
15 5 7 2 8

样例输出1

8
4
2

样例解释1:

对于第一组询问:
\[\left\{
\begin{aligned}
8^5=8\mod 15\\
8^7=2\mod 15
\end{aligned}
\right.\]

数据范围

对于所有数据:\(1\leq q\leq 10^4\), \(1\leq N\leq 10^{18}\), 保证所有的数都是使用RSA生成的。

AKIOI Round #1

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-08-08 08:30
结束于
2024-08-08 12:30
持续时间
4.0 小时
主持人
参赛人数
2