關于ElGamal加密算法實作的總結（附最小本原元代碼）

重點：ElGamal既能夠加密，也能夠用來簽名。兩者雖然過程很像，但并不是同一件事。例如：

https://blog.csdn.net/boksic/article/details/7014386

這個展示了很多原理，也介紹了加密與解密過程的實作，算是比較直接的。

而  http://blog.sina.com.cn/s/blog_5b5ed0720100atsy.htm 和  https://www.cnblogs.com/math/p/discrete-log.html 則是對ElGamal算法的依靠：離散對數問題進行了深入的探究。可以選看。

在我們實作該算法的時候會遇到大量的幂運算，模運算的混合運算公式，例如：

  如果 b太大，則會出現Int 類型裝不下的情況。是以可以結合 https://www.cnblogs.com/juruohx/p/7787415.html 這裡介紹的模運算公式 (a + b) % p = (a % p + b % p) % p  來寫出如下代碼來進行計算：

private int calc_BigNum(int c1,int c2,int p)
        {
            //遞歸方法
            //if (c2 == 1)
            //{
            //    return Convert.ToInt32(c1 % p);
            //}
            //else
            //{
            //    return Convert.ToInt32(((c1 % p) * calc_BigNum(c1, c2 - 1, p)) % p);
            //}

            //非遞歸方法
            if (c2 == 0)
            {
                return 1;
            }

            List<int> result = new List<int>();
            while (c2>0)
            {
                result.Add(Convert.ToInt32(c1 % p));
                c2 -= 1;
            }
            int value = Convert.ToInt32(result[0] % p);
            for (int i = 1; i < result.Count; i++)
            {
                value *= Convert.ToInt32(result[i] % p);
                value = Convert.ToInt32(value % p);

            }
            return Convert.ToInt32(value % p);

        }
           

這樣就能夠解決了（不推薦遞歸的算法，容易溢出）

最後，關于講的最好的和最全面的應該是：https://www.jiamisoft.com/blog/20564-elgamal.html 

但是這一句：

再用擴充 Euclidean 算法對下面方程求解b：

M = xa + kb ( mod p - 1 ) ，簽名就是( a, b )。随機數k須丢棄。

則是沒有解釋怎麼在已知m,x,a,k,p的情況下求b。我自己寫了下面的方法來求：

private int calc_c2(int m,int x , int c1 , int k, int p)
        {
            while (true)
            {
                if(m-c1*x > 0 && Convert.ToInt32((m - c1 * x) % k) == 0)
                {
                    int c2 = (m - c1*x) / k;
                    return c2;
                }
                else
                {
                    m += p - 1;
                }
            }

            
        }
           

因為我和該文章的一些變量名沒有相同，是以看起來很亂，在我這個代碼中，該方程是這樣寫的：m = x*c1 + k*c2  mod (p-1)

就辛苦你們這些讀者了(●ˇ∀ˇ●)

附：如果有人需要有求本原元的代碼，下面的代碼希望對你有用

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int P;
const int NUM = 32170;
int prime[NUM/4];
bool f[NUM];
int pNum = 0;
void getPrime()//線性篩選素數
{
	for (int i = 2; i < NUM; ++ i)
	{
		if (!f[i])
		{
			f[i] = 1;
			prime[pNum++] = i;
		}
		for (int j = 0; j < pNum && i*prime[j] < NUM; ++ j)
		{
			f[i*prime[j]] = 1;
			if (i%prime[j] == 0)
			{
				break;
			}
		}
	}
}
__int64 getProduct(int a,int b,int P)//快速求次幂mod
{
	__int64 ans = 1;
	__int64 tmp = a;
	while (b)
	{
		if (b&1)
		{
			ans = ans*tmp%P;
		}
		tmp = tmp*tmp%P;
		b>>=1;
	}
	return ans;
}
 
bool judge(int num)//求num的所有的質因子
{
	int elem[1000];
	int elemNum = 0;
	int k = P - 1;
	for (int i = 0; i < pNum; ++ i)
	{
		bool flag = false;
		while (!(k%prime[i]))
		{
			flag = true;
			k /= prime[i];
		}
		if (flag)
		{
			elem[elemNum ++] = prime[i];
		}
		if (k==1)
		{
			break;
		}
		if (k/prime[i]<prime[i])
		{
			elem[elemNum ++] = prime[i];
			break;
		}
	}
	bool flag = true;
	for (int i = 0; i < elemNum; ++ i)
	{
		if (getProduct(num,(P-1)/elem[i],P) == 1)
		{
			flag = false;
			break;
		}
	}
	return flag;
}
int main()
{
	
	getPrime();
	while (cin >> P)
	{
		for (int i = 2;;++i)
		{
			if (judge(i) && i<P)
			{
				 
				cout << i<< endl;
				
			}
		}
	}
	return 0;
}