缘起

是我侄子问的题目，参考了书籍、博客，花了一些时间完成的，丢掉可惜了，记录下来吧。这个程序还有些缺陷，数值太大时计算结果会溢出

代码

#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);
}

参考

-《深入浅出密码学》