「密码学」-Elgamal密码体制

Elgamal：

加密

1. 随机选择一个质数,并且求出模情况下的本原根,并将公开
2. 随机选择一个整数,作为私钥，并对保密。
3. 计算出公钥
4. 对于一段明文,随机选择一个整数,分别计算出

解密

1. 对于密文进行解密，首先应当计算模情况下的逆元。然后明文

本原根：最小的原根被称为本原根

习题

• 选择一个质数,在模情况下的最小原根是,选择一个数,写出对明文加密密文和解密过程。

• 加密
  依题意：其中的
  公钥
  
  
  密文为

• 解密
  依题意：其中
  求出在模的逆元
  

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
ll factor[maxn], k;
bool prim(ll x)
{
    if(x==1)
    {
        return false;
    }
    if(x==2)
    {
        return true;
    }
    if(x%2==0)
    {
        return false;
    }
    for(ll i=3; i*i<=x; i++)
    {
        if(x%i==0)
        {
            return false;
        }
    }
    return true;
}
ll qpow(ll a,ll n,ll mod)
{
    ll ans=1;
    ll base=a;
    while(n)
    {
        if(n&1)
        {
            ans=ans*base%mod;
        }
        base=base*base%mod;
        n>>=1;
    }
    return ans%mod;
}
void decompose(ll x)  //分解质因子
{
    ll ans = 0;
    for (ll i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            factor[k++] = i;
            while (x % i == 0)  x /= i;
        }
    }
    if (x > 1)  factor[k++] = x;
}
ll cal(ll n)  //求素数最小原根
{
    k=0;
    decompose(n - 1);
    for (ll g = 2; g < n; g++)
    {
        int flag = 1;
        for (int i = 0; i < k; i++)
        {
            ll t = (n - 1) / factor[i];
            if (qpow(g, t, n) == 1)
            {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
            return g;
    }
}
void exgcd(ll a,ll b,ll &gcd,ll &x,ll &y)
{
    if(b==0)
    {
        gcd=a;
        x=1;
        y=0;
    }
    else
    {
        exgcd(b,a%b,gcd,y,x);
        y-=x*(a/b);
    }
}
ll inv(ll a,ll b)
{
    ll gcd,x,y;
    exgcd(a,b,gcd,x,y);
    return gcd==1?(x%b+b)%b:-1;
}
int main()
{
    printf("encry 1,decry2\n");
    int flag;
    scanf("%d",&flag);
    ll p,a,b,x;
    ll A,B,C,byg;
    if(flag==1)
    {
        //printf("随机生成一个大的质数p");
        printf("Prime p,a,b,x\n");
        scanf("%lld%lld%lld%lld",&p,&a,&b,&x);
        byg = cal(p);
        printf("%lld\n", byg);
        A=qpow(byg,a,p);
        cout<<A<<endl;
        B=qpow(byg,b,p);
        C=(x*qpow(A,b,p))%p;
        printf("C(%lld,%lld)\n",B,C);
    }
    else if(flag==2)
    {
        printf("Prime p,a,B,C");
        scanf("%lld%lld%lld%lld", &p,&a,&B,&C);
        ll K=inv(qpow(B,a,p),p);
        cout<<C *K%p<<endl;
    }
    // printf("输入质数p,随机数a,随机数b,明文x");
    // scanf("%lld%lld%lld%lld", &p,&a,&b,&x);
    // ll byg = cal(p);
    // printf("%lld\n", byg);
    // ll A=qpow(byg,a,p);
    // cout<<A<<" A "<<endl;
    // ll B=qpow(byg,b,p);

    // ll C=(x*qpow(A,b,p)%p)%p;
    // printf("%lld %lld\n",B,C);
    // ll K=inv(qpow(B,a,p),p);
    // cout<<C *K%p<<endl;
    return 0;
}