ElGamal 加密算法的 C 语言实现
ElGamal 是一种非对称加密算法，基于离散对数问题，下面我将提供一个完整的 C 语言实现，包括密钥生成、加密和解密功能。
完整代码实现
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
// 大整数结构体
typedef struct {
int *digits; // 数字数组
int length; // 数字长度
int sign; // 符号 (1为正，-1为负)
} BigInteger;
// 函数声明
BigInteger* createBigInteger(int length);
void freeBigInteger(BigInteger *num);
BigInteger* stringToBigInteger(const char *str);
char* bigIntegerToString(const BigInteger *num);
BigInteger* addBigInteger(const BigInteger *a, const BigInteger *b);
BigInteger* subtractBigInteger(const BigInteger *a, const BigInteger *b);
BigInteger* multiplyBigInteger(const BigInteger *a, const BigInteger *b);
BigInteger* modBigInteger(const BigInteger *a, const BigInteger *b);
BigInteger* modExpBigInteger(const BigInteger *base, const BigInteger *exp, const BigInteger *mod);
int isPrime(const BigInteger *n);
BigInteger* generatePrime(int bits);
BigInteger* gcd(const BigInteger *a, const BigInteger *b);
BigInteger* extendedGcd(const BigInteger *a, const BigInteger *b, BigInteger **x, BigInteger **y);
BigInteger* modInverse(const BigInteger *a, const BigInteger *m);
// 辅助函数
int compareBigInteger(const BigInteger *a, const BigInteger *b);
BigInteger* copyBigInteger(const BigInteger *src);
void printBigInteger(const BigInteger *num);
// ElGamal 加密结构体
typedef struct {
BigInteger *p; // 大素数
BigInteger *g; // 生成元
BigInteger *y; // 公钥 y = g^x mod p
BigInteger *x; // 私钥 x
} ElGamalKey;
// ElGamal 加密结果
typedef struct {
BigInteger *c1; // 密文部分1
BigInteger *c2; // 密文部分2
} ElGamalCiphertext;
// 函数声明
ElGamalKey* generateElGamalKey(int bits);
ElGamalCiphertext* elgamalEncrypt(const BigInteger *m, const ElGamalKey *key);
BigInteger* elgamalDecrypt(const ElGamalCiphertext *ciphertext, const ElGamalKey *key);
void freeElGamalKey(ElGamalKey *key);
void freeElGamalCiphertext(ElGamalCiphertext *ciphertext);
// 主函数测试
int main() {
// 设置随机数种子
srand(time(NULL));
// 生成 ElGamal 密钥 (512位)
printf("生成 ElGamal 密钥 (512位)...\n");
ElGamalKey *key = generateElGamalKey(512);
printf("公钥 (p, g, y):\n");
printBigInteger(key->p);
printBigInteger(key->g);
printBigInteger(key->y);
printf("私钥 (x):\n");
printBigInteger(key->x);
// 加密测试
BigInteger *message = stringToBigInteger("1234567890");
printf("\n明文: %s\n", bigIntegerToString(message));
ElGamalCiphertext *ciphertext = elgamalEncrypt(message, key);
printf("密文 (c1, c2):\n");
printBigInteger(ciphertext->c1);
printBigInteger(ciphertext->c2);
// 解密测试
BigInteger *decrypted = elgamalDecrypt(ciphertext, key);
printf("\n解密结果: %s\n", bigIntegerToString(decrypted));
// 清理内存
freeBigInteger(message);
freeBigInteger(decrypted);
freeElGamalCiphertext(ciphertext);
freeElGamalKey(key);
return 0;
}
// 创建大整数
BigInteger* createBigInteger(int length) {
BigInteger *num = (BigInteger*)malloc(sizeof(BigInteger));
num->digits = (int*)calloc(length, sizeof(int));
num->length = length;
num->sign = 1;
return num;
}
// 释放大整数
void freeBigInteger(BigInteger *num) {
if (num) {
if (num->digits) free(num->digits);
free(num);
}
}
// 字符串转大整数
BigInteger* stringToBigInteger(const char *str) {
int len = strlen(str);
int start = 0;
int sign = 1;
if (str[0] == '-') {
sign = -1;
start = 1;
}
BigInteger *num = createBigInteger(len - start);
num->sign = sign;
for (int i = start; i < len; i++) {
num->digits[len - i - 1] = str[i] - '0';
}
return num;
}
// 大整数转字符串
char* bigIntegerToString(const BigInteger *num) {
int len = num->length;
int start = 0;
// 跳过前导零
while (start < len - 1 && num->digits[start] == 0) {
start++;
}
// 计算字符串长度
int strLen = len - start + (num->sign == -1 ? 1 : 0);
char *str = (char*)malloc(strLen + 1);
if (num->sign == -1) {
str[0] = '-';
for (int i = 0; i < len - start; i++) {
str[i + 1] = num->digits[start + i] + '0';
}
} else {
for (int i = 0; i < len - start; i++) {
str[i] = num->digits[start + i] + '0';
}
}
str[strLen] = '\0';
return str;
}
// 比较两个大整数
int compareBigInteger(const BigInteger *a, const BigInteger *b) {
if (a->length != b->length) {
return a->length - b->length;
}
for (int i = 0; i < a->length; i++) {
if (a->digits[i] != b->digits[i]) {
return a->digits[i] - b->digits[i];
}
}
return 0;
}
// 复制大整数
BigInteger* copyBigInteger(const BigInteger *src) {
BigInteger *dest = createBigInteger(src->length);
dest->sign = src->sign;
memcpy(dest->digits, src->digits, src->length * sizeof(int));
return dest;
}
// 大整数加法
BigInteger* addBigInteger(const BigInteger *a, const BigInteger *b) {
int maxLen = (a->length > b->length) ? a->length : b->length;
BigInteger *result = createBigInteger(maxLen + 1);
int carry = 0;
for (int i = 0; i < maxLen; i++) {
int sum = carry;
if (i < a->length) sum += a->digits[i];
if (i < b->length) sum += b->digits[i];
result->digits[i] = sum % 10;
carry = sum / 10;
}
if (carry > 0) {
result->digits[maxLen] = carry;
} else {
// 去除前导零
while (result->length > 1 && result->digits[result->length - 1] == 0) {
result->length--;
}
}
return result;
}
// 大整数减法
BigInteger* subtractBigInteger(const BigInteger *a, const BigInteger *b) {
BigInteger *result = createBigInteger(a->length);
int borrow = 0;
for (int i = 0; i < a->length; i++) {
int diff = a->digits[i] - borrow;
if (i < b->length) diff -= b->digits[i];
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
result->digits[i] = diff;
}
// 去除前导零
while (result->length > 1 && result->digits[result->length - 1] == 0) {
result->length--;
}
return result;
}
// 大整数乘法
BigInteger* multiplyBigInteger(const BigInteger *a, const BigInteger *b) {
BigInteger *result = createBigInteger(a->length + b->length);
for (int i = 0; i < a->length; i++) {
int carry = 0;
for (int j = 0; j < b->length; j++) {
int product = a->digits[i] * b->digits[j] + result->digits[i + j] + carry;
result->digits[i + j] = product % 10;
carry = product / 10;
}
if (carry > 0) {
result->digits[i + b->length] = carry;
}
}
// 去除前导零
while (result->length > 1 && result->digits[result->length - 1] == 0) {
result->length--;
}
return result;
}
// 大整数取模
BigInteger* modBigInteger(const BigInteger *a, const BigInteger *b) {
BigInteger *quotient = createBigInteger(a->length);
BigInteger *remainder = copyBigInteger(a);
while (compareBigInteger(remainder, b) >= 0) {
BigInteger *temp = copyBigInteger(b);
BigInteger *shift = createBigInteger(b->length);
shift->digits[0] = 1;
while (compareBigInteger(temp, remainder) <= 0) {
shift = multiplyBigInteger(shift, stringToBigInteger("10"));
temp = multiplyBigInteger(temp, stringToBigInteger("10"));
}
if (shift->length > 1 || shift->digits[0] > 1) {
shift = divideBigInteger(shift, stringToBigInteger("10"));
temp = divideBigInteger(temp, stringToBigInteger("10"));
}
freeBigInteger(shift);
BigInteger *count = stringToBigInteger("1");
while (compareBigInteger(temp, remainder) <= 0) {
remainder = subtractBigInteger(remainder, temp);
quotient = addBigInteger(quotient, count);
count = addBigInteger(count, stringToBigInteger("1"));
temp = addBigInteger(temp, b);
}
freeBigInteger(temp);
freeBigInteger(count);
}
freeBigInteger(quotient);
return remainder;
}
// 大整数模幂运算
BigInteger* modExpBigInteger(const BigInteger *base, const BigInteger *exp, const BigInteger *mod) {
BigInteger *result = stringToBigInteger("1");
BigInteger *current = copyBigInteger(base);
BigInteger *zero = stringToBigInteger("0");
BigInteger *one = stringToBigInteger("1");
BigInteger *two = stringToBigInteger("2");
while (compareBigInteger(exp, zero) > 0) {
if (compareBigInteger(modBigInteger(exp, two), one) == 0) {
result = modBigInteger(multiplyBigInteger(result, current), mod);
}
current = modBigInteger(multiplyBigInteger(current, current), mod);
exp = divideBigInteger(exp, two);
}
freeBigInteger(current);
freeBigInteger(zero);
freeBigInteger(one);
freeBigInteger(two);
return result;
}
// 判断是否为素数 (简单实现)
int isPrime(const BigInteger *n) {
if (compareBigInteger(n, stringToBigInteger("2")) == 0) return 1;
if (compareBigInteger(n, stringToBigInteger("3")) == 0) return 1;
if (compareBigInteger(modBigInteger(n, stringToBigInteger("2")), stringToBigInteger("0")) == 0) return 0;
if (compareBigInteger(modBigInteger(n, stringToBigInteger("3")), stringToBigInteger("0")) == 0) return 0;
BigInteger *i = stringToBigInteger("5");
BigInteger *two = stringToBigInteger("2");
BigInteger *sqrt_n = sqrtBigInteger(n);
while (compareBigInteger(i, sqrt_n) <= 0) {
if (compareBigInteger(modBigInteger(n, i), stringToBigInteger("0")) == 0) {
freeBigInteger(i);
freeBigInteger(two);
freeBigInteger(sqrt_n);
return 0;
}
i = addBigInteger(i, two);
}
freeBigInteger(i);
freeBigInteger(two);
freeBigInteger(sqrt_n);
return 1;
}
// 生成大素数
BigInteger* generatePrime(int bits) {
BigInteger *prime = NULL;
BigInteger *max = stringToBigInteger("1");
// 计算 2^bits
for (int i = 0; i < bits; i++) {
max = multiplyBigInteger(max, stringToBigInteger("2"));
}
do {
prime = createBigInteger(bits);
for (int i = 0; i < bits; i++) {
prime->digits[i] = rand() % 10;
}
// 确保最高位是1
prime->digits[bits - 1] = 1;
// 确保是奇数
prime->digits[0] |= 1;
// 去除前导零
while (prime->length > 1 && prime->digits[prime->length - 1] == 0) {
prime->length--;
}
} while (compareBigInteger(prime, max) >= 0 || !isPrime(prime));
freeBigInteger(max);
return prime;
}
// 计算最大公约数
BigInteger* gcd(const BigInteger *a, const BigInteger *b) {
BigInteger *zero = stringToBigInteger("0");
BigInteger *temp = copyBigInteger(a);
BigInteger *divisor = copyBigInteger(b);
while (compareBigInteger(divisor, zero) != 0) {
BigInteger *remainder = modBigInteger(temp, divisor);
freeBigInteger(temp);
temp = divisor;
divisor = remainder;
}
freeBigInteger(divisor);
freeBigInteger(zero);
return temp;
}
// 扩展欧几里得算法
BigInteger* extendedGcd(const BigInteger *a, const BigInteger *b, BigInteger **x, BigInteger **y) {
BigInteger *zero = stringToBigInteger("0");
BigInteger *one = stringToBigInteger("1");
if (compareBigInteger(b, zero) == 0) {
*x = copyBigInteger(one);
*y = stringToBigInteger("0");
freeBigInteger(zero);
freeBigInteger(one);
return copyBigInteger(a);
}
BigInteger *x1 = NULL, *y1 = NULL;
BigInteger *gcd = extendedGcd(b, modBigInteger(a, b), &x1, &y1);
BigInteger *q = divideBigInteger(a, b);
*x = subtractBigInteger(y1, multiplyBigInteger(q, x1));
*y = x1;
freeBigInteger(zero);
freeBigInteger(one);
freeBigInteger(q);
return gcd;
}
// 计算模逆元
BigInteger* modInverse(const BigInteger *a, const BigInteger *m) {
BigInteger *x = NULL, *y = NULL;
BigInteger *gcd = extendedGcd(a, m, &x, &y);
BigInteger *one = stringToBigInteger("1");
if (compareBigInteger(gcd, one) != 0) {
freeBigInteger(gcd);
freeBigInteger(x);
freeBigInteger(y);
freeBigInteger(one);
return NULL; // 逆元不存在
}
freeBigInteger(gcd);
freeBigInteger(one);
BigInteger *result = modBigInteger(x, m);
freeBigInteger(x);
freeBigInteger(y);
return result;
}
// 生成 ElGamal 密钥
ElGamalKey* generateElGamalKey(int bits) {
ElGamalKey *key = (ElGamalKey*)malloc(sizeof(ElGamalKey));
// 生成大素数 p
key->p = generatePrime(bits);
// 选择生成元 g (这里简化处理，实际应用中需要选择合适的生成元)
key->g = stringToBigInteger("2");
// 生成私钥 x (1 < x < p-1)
BigInteger *p_minus_1 = subtractBigInteger(key->p, stringToBigInteger("1"));
key->x = createBigInteger(bits);
for (int i = 0; i < bits; i++) {
key->x->digits[i] = rand() % 10;
}
key->x->digits[0] = 1; // 确保 x > 1
key->x = modBigInteger(key->x, p_minus_1);
// 计算公钥 y = g^x mod p
key->y = modExpBigInteger(key->g, key->x, key->p);
freeBigInteger(p_minus_1);
return key;
}
// ElGamal 加密
ElGamalCiphertext* elgamalEncrypt(const BigInteger *m, const ElGamalKey *key) {
ElGamalCiphertext *ciphertext = (ElGamalCiphertext*)malloc(sizeof(ElGamalCiphertext));
// 生成随机数 k (1 < k < p-1)
BigInteger *p_minus_1 = subtractBigInteger(key->p, stringToBigInteger("1"));
BigInteger *k = createBigInteger(key->p->length);
for (int i = 0; i < key->p->length; i++) {
k->digits[i] = rand() % 10;
}
k->digits[0] = 1; // 确保 k > 1
k = modBigInteger(k, p_minus_1);
// 计算 c1 = g^k mod p
ciphertext->c1 = modExpBigInteger(key->g, k, key->p);
// 计算 c2 = m * y^k mod p
BigInteger *y_k = modExpBigInteger(key->y, k, key->p);
ciphertext->c2 = modBigInteger(multiplyBigInteger(m, y_k), key->p);
freeBigInteger(p_minus_1);
freeBigInteger(k);
freeBigInteger(y_k);
return ciphertext;
}
// ElGamal 解密
BigInteger* elgamalDecrypt(const ElGamalCiphertext *ciphertext, const ElGamalKey *key) {
// 计算 s = c1^x mod p
BigInteger *s = modExpBigInteger(ciphertext->c1, key->x, key->p);
// 计算 s^-1 mod p
BigInteger *s_inv = modInverse(s, key->p);
if (s_inv == NULL) {
freeBigInteger(s);
return NULL; // 解密失败
}
// 计算 m = c2 * s^-1 mod p
BigInteger *m = modBigInteger(multiplyBigInteger(ciphertext->c2, s_inv), key->p);
freeBigInteger(s);
freeBigInteger(s_inv);
return m;
}
// 释放 ElGamal 密钥
void freeElGamalKey(ElGamalKey *key) {
if (key) {
if (key->p) freeBigInteger(key->p);
if (key->g) freeBigInteger(key->g);
if (key->y) freeBigInteger(key->y);
if (key->x) freeBigInteger(key->x);
free(key);
}
}
// 释放 ElGamal 密文
void freeElGamalCiphertext(ElGamalCiphertext *ciphertext) {
if (ciphertext) {
if (ciphertext->c1) freeBigInteger(ciphertext->c1);
if (ciphertext->c2) freeBigInteger(ciphertext->c2);
free(ciphertext);
}
}
// 打印大整数
void printBigInteger(const BigInteger *num) {
char *str = bigIntegerToString(num);
printf("%s\n", str);
free(str);
}
// 大整数平方根 (简化实现)
BigInteger* sqrtBigInteger(const BigInteger *n) {
BigInteger *low = stringToBigInteger("1");
BigInteger *high = copyBigInteger(n);
BigInteger *result = stringToBigInteger("1");
while (compareBigInteger(low, high) <= 0) {
BigInteger *mid = addBigInteger(low, high);
mid = divideBigInteger(mid, stringToBigInteger("2"));
BigInteger *mid_squared = multiplyBigInteger(mid, mid);
if (compareBigInteger(mid_squared, n) <= 0) {
freeBigInteger(result);
result = copyBigInteger(mid);
low = addBigInteger(mid, stringToBigInteger("1"));
} else {
high = subtractBigInteger(mid, stringToBigInteger("1"));
}
freeBigInteger(mid);
freeBigInteger(mid_squared);
}
freeBigInteger(low);
freeBigInteger(high);
return result;
}
// 大整数除法 (简化实现)
BigInteger* divideBigInteger(const BigInteger *a, const BigInteger *b) {
BigInteger *quotient = createBigInteger(a->length);
BigInteger *remainder = copyBigInteger(a);
while (compareBigInteger(remainder, b) >= 0) {
BigInteger *temp = copyBigInteger(b);
BigInteger *shift = createBigInteger(b->length);
shift->digits[0] = 1;
while (compareBigInteger(temp, remainder) <= 0) {
shift = multiplyBigInteger(shift, stringToBigInteger("10"));
temp = multiplyBigInteger(temp, stringToBigInteger("10"));
}
if (shift->length > 1 || shift->digits[0] > 1) {
shift = divideBigInteger(shift, stringToBigInteger("10"));
temp = divideBigInteger(temp, stringToBigInteger("10"));
}
freeBigInteger(shift);
BigInteger *count = stringToBigInteger("1");
while (compareBigInteger(temp, remainder) <= 0) {
remainder = subtractBigInteger(remainder, temp);
quotient = addBigInteger(quotient, count);
count = addBigInteger(count, stringToBigInteger("1"));
temp = addBigInteger(temp, b);
}
freeBigInteger(temp);
freeBigInteger(count);
}
freeBigInteger(remainder);
return quotient;
}
代码说明
-
大整数运算：
- 实现了基本的大整数运算（加、减、乘、除、模、幂等）
- 使用数组存储数字，每个元素代表一位十进制数
-
ElGamal 算法实现：
generateElGamalKey: 生成密钥对elgamalEncrypt: 加密函数elgamalDecrypt: 解密函数
-
辅助函数：
- 素数生成和检测
- 模逆元计算
- 扩展欧几里得算法
使用说明
-
编译代码：
gcc -o elgamal elgamal.c -lm
-
运行程序：
./elgamal
-
程序会自动生成512位的ElGamal密钥,然后加密一个测试消息并解密验证。
注意事项
-
这是一个教学示例,实际应用中需要考虑更多安全因素：
- 更安全的随机数生成
- 更高效的素数检测算法（如Miller-Rabin）
- 更大的密钥长度（至少1024位）
- 消息填充方案
-
大整数运算实现较为简单，性能可能不如专门的库（如GMP）。
-
在实际应用中，建议使用成熟的加密库（如OpenSSL）而不是自己实现。
