HDU 1211 RSA 解公钥密码

题面

RSA是一种加密工具。

  • 选择两个素数$p,q$。
  • 计算$n=p \times q$,$f(n)=(p-1) \times (q-1)$。
  • 选择一个整数$e \in (1,f(n))$,使得$gcd(e,f(n))=1$,$e$是公钥。
  • 计算$d$使得$d \times e \equiv 1 \pmod {f(N)}$。

如果解密的话使用如下方法:
$$M=D(c)=c^d \% n$$
$c$是一种ASCII的值,请把密文翻译成明文。

题解

计算$n,F(n)$用扩展欧几里得求出$d$,最后根据公式求明文。

代码

#include <iostream>
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}
int mul(int x, int y, int mod)
{
    int res = 1;
    while(y)
    {
        if(y & 1)
            res = ((res % mod) * (x % mod)) % mod;
        x = ((x % mod) * (x % mod)) % mod;
        y >>= 1;
    }
    return res;
}
int main(){
    int p,q,e,t,n,fn,d;
    ios::sync_with_stdio(false);
    while(cin>>p>>q>>e>>t){
        n=p*q;
        fn=(p-1)*(q-1);
        exgcd(e,fn);
        d=(x+fn)%fn;
        while(t--){
            int a;
            cin>>a;
            cout<<char(mul(a,d,n));
        }
        cout<<endl;
    }
    return 0;
}
Last modification:June 29th, 2019 at 04:07 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment