adworld easy_RSA | RSA算法

题目描述：

解答出来了上一个题目的你现在可是春风得意，你们走向了下一个题目所处的地方 你一看这个题目傻眼了，这明明是一个数学题啊！！！可是你的数学并不好。扭头看向小鱼，小鱼哈哈一笑 ，让你在学校里面不好好听讲现在傻眼了吧~来我来！三下五除二，小鱼便把这个题目轻轻松松的搞定了。flag格式为cyberpeace{小写的你解出的答案}

附件内容：

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

前置知识：

非对称加密算法--RSA加密原理

————————————————————————

公钥密码算法（非堆成密钥算法）：产生一对可以互逆变换的密钥Kd与Ke，但是即使知道Kd，还是无法得知Ke，这样就可将Kd公开，但只有接收方知道Ke。在此情况下，任何人均可利用Kd加密，而只有知道Ke的接收方才能解密；或是只有接收方一人才能加密（加密与解密其实都是一种动作），任何人均能解密。

简单地概述一下\(RSA\)算法加密/解密的过程：

import：

\(N\)：公钥\(1\)   \(d\)：公钥\(2\)   \(e\)：私钥
\(A\)：密文   \(B\)：明文   \(φ()\)：欧拉函数

• 公钥在同一加密规则下对于所有人来说都是已知的，加密只需公钥

• 首先约定私钥 \(e\,\)需满足：\(1 < e < φ(N)\) 且 \(gcd(e,N) = 1\) （互质，否则无解）

• 公钥 \(d\) 由 \(d*e≡1\,(mod\,φ(N))\) ① 计算出，此时称 \(d\) 是 \(e\) 的模反元素

• 为了增加破解（分解因数）的难度，\(N\) 一般为两个大质数的乘积（即 \(p\) 和 \(q\)）

加密公式： \(A^d ≡ B\;(\;mod\;N\;)\,\,\)   解密公式： \(B^e ≡ A\;(\;mod\;N\;)\,\,\)

数字签名： \(A^e ≡ B\;(\;mod\;N\;)\,\,\)   验证签名： \(B^d ≡ A\;(\;mod\;N\;)\,\,\)

我们知道当 \(p\) 和 \(q\) 都为质数时，\(φ(N) = φ (p*q) = (p-1) * (q-1)\)

故 ① 式变为：\(d * e\,\%\,(p-1)*(q-1)\,= 1\)

即 \(d*e*x-(p-1)*(q-1)*y=1\) 其中： \(x,y∈N\)

easy_RSA 这道题就是模拟了计算公钥的过程，我们可以使用扩展欧几里得算法解决。

C++ 代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void exgcd (ll a,ll b,ll &d,ll &y,ll &gcd) {
    if (!b) { d=1,y=0,gcd=a; return; }
    else { exgcd(b,a%b,y,d,gcd),y-=d*(a/b); }
}
int main()
{
    const ll p=473398607161,q=4511491,e=17;
    const ll eu=(p-1)*(q-1);
    ll d,y,gcd,mo;
    exgcd(e,eu,d,y,gcd);
    mo=eu/gcd,d=(d%mo+mo)%mo;
    cout<<d;
    return 0;
}