一、简要介绍

ElGamal加密算法是一种基于Diffie-Hellman密钥交换协议的公钥加密算法。它以其发明者Taher ElGamal的名字命名，被广泛应用在电子邮件系统等领域。本文将深入探讨ElGamal加密算法的基本原理、流程以及如何实际应用。

ElGamal加密算法基于计算离散对数的难度，其安全性相较于RSA等其他公钥加密算法而言，更为可靠。然而，ElGamal加密算法也存在一些局限性，如加密及解密计算量大，密文长度是明文的两倍等。

二、算法流程：

1. 密钥生成：
   * 选择一个大的素数p和一个p的本原元g。
   * 随机选择一个整数a（1<a<p-1），计算A=g^a mod p。
   * 公钥为(p,g,A)，私钥为a。

2. 加密过程：
   * 接收者公开公钥(p,g,A)，发送者选择明文M（1<M<p）。
   * 发送者随机选择整数k（1<k<p-1），计算出两个密文C1和C2。
   * C1=g^k mod p，C2=M*(A^k) mod p。
   * 发送者将(C1,C2)发送给接收者。

3. 解密过程：
   * 接收者接收到(C1,C2)，使用私钥a进行解密。
   * M=C2/(C1^a) mod p。

三、算法优势

ElGamal加密算法的主要优点是其安全性高，难以破解；可以用于加密和数字签名；以及其具有公钥和私钥分离的特性。然而，其计算量大，加密和解密速度较慢，且加密后的密文长度较长，这在一定程度上限制了其应用范围。尽管ElGamal加密算法有其局限性，但得益于其较高的安全性，它仍然是公钥加密算法中的重要成员，被广泛应用于诸多领域。

四、代码实现

#include<iostream>

using namespace std;

#include <stdlib.h>

#include <time.h>

#include<math.h>

long long int c1,c2;

long long int m;

unsigned int p, g,x,z;

unsigned int d;

unsigned int y, k = 0;

unsigned int isprime(unsigned int x)

{

    unsigned int ret = 1;

    unsigned int i;

    unsigned int size = (int)sqrt(x);

    if (x == 1 || (x != 2 && x % 2 == 0)) ret = 0;

    for (i = 3; i <= size; i++) {

        if (x % i == 0) {

            ret = 0;

            break;

        }

    }

    return ret;

}

unsigned int gcd(unsigned int a, unsigned int b) {

    if (b == 0) {

        return a;

    }

    else {

        return gcd(b, a % b);

    }

}

unsigned int qni(unsigned int a, unsigned int b, unsigned int mod) {

    unsigned int res = 1;

    while (b) {

        if (b & 1) res = res * a % mod;

        b >>= 1;

        a = a * a % mod;

    }

    return res;

}

unsigned int jiami(unsigned int m, unsigned int e, unsigned int n)

{

    int c = 1;

    while (e >= 1) {

        if (e % 2) c = (m * c) % n;

        m = (m * m) % n;

        e /= 2;

    }

    return c;

}

unsigned int jiemi(unsigned int c, unsigned int d, unsigned int n)

{

    int m = 1;

    while (d >= 1) {

        if (d % 2) m = (c * m) % n;

        c = (c * c) % n;

        d /= 2;

    }

    return m;

}

int main()

{

    srand((unsigned)time(NULL));

    printf("如果手动输入素数请按输入：1,自动生成素数请输入：2\n");

    scanf("%d", &z);

    if (z == 1)

    {

        printf("请输入一个素数p：\n");

        scanf("%d", &p);

        if (isprime(p)) {

            printf("%d是素数\n", p);

        }

        else {

            printf("%d不是素数\n", p);

            return 0;

        }

    }

    else

    {

        p = 0;

        while (isprime(p) == 0 || p<4)

        {

            p = rand() % (100 - 1 + 1) + 1;

        }

    }

    printf("生成的素数为：%d", p);

    printf("请输入两个小于p的随机数g，x：\n");

    scanf("%d %d", &g, &x);

    y = jiami(g, x, p);

    while (gcd(k, p-1) != 1)

    {

        k = rand() % (p-1) + 2;

    }

    printf("公钥y,g,p和私钥x分别是：%d %d %d %d\n", y, g, p, x);

    printf("请输入明文：\n");

    scanf("%lld", &m);

    c1 = jiami(g, k, p);

    c2 = m*jiami(y, k, p)%p;

    printf("加密后密文是：%lld,%lld\n", c1,c2);

    printf("请输入密文:\n");

    scanf("%lld %lld", &c1,&c2);

    d = jiami(c1, x, p);

    m = c2*qni(d,p-2,p)%p;

    printf("解密后明文是：%lld\n", m);

    return 0;

}