题目（原题的拼写错误）

在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
求解出d作为flga提交

分析

回顾一下 RSA 算法描述：

RSA 算法的具体描述如下：
（1）任意选取两个不同的大素数 p 和 q 计算乘积 \(n=pq,\varphi(n)=(p-1)(q-1)\)；
（2）任意选取一个大整数 e，满足 \(gcd(e,\varphi(n))=1\)，整数 e 用做加密钥（注意：e 的选取是很容易的，例如，所有大于 p 和 q 的素数都可用）；
（3）确定的解密钥 d，满足 \((de)\mod\varphi(n)=1\)，即 \(de=k\varphi(n)+1,k\ge1\) 是一个任意的整数；所以，若知道 e 和 \(\varphi(n)\)，则很容易计算出 d；
（4）公开整数 n 和 e，秘密保存 d；
（5）将明文 m（m<n 是一个整数）加密成密文 c，加密算法为

\[c=E(m)=m^{e}\mod n \]

（6）将密文 c 解密为明文 m，解密算法为

\[m=D(c)=c^{d}\mod n \]

然而只根据 n 和 e（注意：不是 p 和 q）要计算出 d 是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道 d）才可对密文解密。

根据描述编写解密代码：

long long p = 473398607161;
long long q = 4511491;
int e = 17;
long long d = -1;
long long varphi = (p - 1) * (q - 1);

// de = kφ(n) + 1
int k = 1;
while (1) {
	if ((k * varphi + 1) % e == 0) {
		printf("%lld", (k * varphi + 1) / e);
		break;
	}
}

return 0;

得到 flag 内容，套壳提交。

Flag

flag{125631357777427553}

参考

RSA算法