是我在上大學的侄子問的題目，參考了書籍、博客，花了一些時間完成的，丟掉可惜了，記錄下來吧。這個程序還有些缺陷，數值太大時計算結果會溢出

緣起

是我侄子問的題目，參考了書籍、博客，花了一些時間完成的，丟掉可惜了，記錄下來吧。這個程序還有些缺陷，數值太大時計算結果會溢出

代碼

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define longint long long

// 得到一個隨機數
int random(int minValue, int maxValue)
{
	return rand() % (maxValue - minValue + 1) + minValue;
}

// 交換兩個變量的值 
void swap(longint a, longint b)
{
	longint temp = a;
	a = b;
	b = temp;
}

// 歐幾里得算法求最大公約數
longint gcd(longint a, longint b)
{
    if (a < b)
    {
        swap(a, b);
    }

    while (true)
    {
        longint mod = a % b;
        if (mod == 0)
        {
            return b;
        }
        return gcd(b, mod);
    }
}

// 求與baseNum的power次方同余的一個數
longint powAndMod(longint baseNum, longint power, longint p)
{
    if (power == 0)
    {
        return 1;
    }
    if (power % 2 == 1)
    {
        return (powAndMod(baseNum, power - 1, p) * baseNum) % p;
    }
    else
    {
        longint temp = (powAndMod(baseNum, power / 2, p) % p);
        return temp * temp;
    }
}

// 費馬小定理判斷是否為質數
bool probablyPrime(longint p)
{
    if (p == 1)
    {
        return false;
    }
    if (p == 2)
    {
        return true;
    }
    if (p % 2 == 0)
    {
        return false;
    }
    return powAndMod(2, p - 1, p) % p == 1;
}

// 隨機得到一個質數
int getPrimeNumber(int minValue, int maxValue)
{
    while (true)
    {
        int num = random(minValue, maxValue);
        if (probablyPrime(num))
        {
            return num;
        }
    }
}

// 求 群Z_p^*的本原元，p為素數
longint findGenerator(longint p)
{
    for (longint i = 2; i < p; i++)
    {
        if (gcd(i, p) == 1)
        {
            if (powAndMod(i, p - 1, p) % p == 1)
            {
                return i;
            }
        }
    }
    return -1;
}

int main()
{
	srand(time(NULL));

	int p = getPrimeNumber(1000000, 2000000);
    printf("選擇一個素數 p = %d\n", p);

    longint alpha = findGenerator(p);
	printf("選擇本原元 α = %d\n", alpha);

	longint privateKey = random(2, p - 2);
	printf("選擇 privateKey = %d\n", privateKey);

	longint publicKey = powAndMod(alpha, privateKey, p) % p;
	printf("計算 publicKey = α^privateKey mod p = %d\n", publicKey);

	printf("\n\n---加密---\n\n");

	longint x = random(1, p - 1);
	printf("選擇明文 x屬于Z_p^* = %d\n", x);

	longint i = random(2, p - 2);
	printf("選擇 i = %d\n", i);

	longint ke = powAndMod(alpha, i, p) % p;
	printf("計算臨時密鑰 ke = α^i mod p = %d\n", ke);

	longint km = powAndMod(publicKey, i, p) % p;
	printf("計算掩碼密鑰 km = publicKey^i mod p = %d\n", km);

	longint y = (x % p) * (km % p);
	printf("加密消息，得到密文 y = x * km mod p = %d\n", y);

	printf("\n\n---解密---\n\n");

	longint km2 = powAndMod(ke, privateKey, p) % p;
	printf("計算掩碼密鑰 km = ke^privateKey mod p = %d\n", km);

	longint x2 = (y / km2) % p;
	printf("解密 x = y * km^{-1} mod p = %d\n", x2);
}

參考

-《深入淺出密碼學》