elgamal算法加解密C语言,详解ElGamal加密算法
时间: 2024-01-04 15:02:12 浏览: 50
ElGamal算法是一种非对称加密算法,与RSA算法类似,它也是基于数论的,但是与RSA算法不同的是它的加密和解密使用的是同一个密钥对,而且加密和解密过程都需要进行一些随机化处理。
下面是ElGamal算法的加解密C语言实现:
加密过程:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
// 求模幂运算 a^b mod m
long long mod_pow(long long a, long long b, long long m)
{
long long ans = 1;
while (b > 0) {
if (b & 1) {
ans = (ans * a) % m;
}
a = (a * a) % m;
b >>= 1;
}
return ans;
}
// 生成一个大素数
long long get_prime(long long min, long long max)
{
long long i, j;
for (i = min; i <= max; i++) {
for (j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
break;
}
}
if (j > sqrt(i)) {
return i;
}
}
return -1;
}
// 生成一个随机数
long long get_random(long long min, long long max)
{
return rand() % (max - min + 1) + min;
}
int main()
{
long long p, g, x, y, k, m, c1, c2;
srand(time(0));
// 生成大素数 p
p = get_prime(10000, 20000);
// 选择一个原根 g
for (g = 2; g < p; g++) {
int flag = 1;
for (int i = 1; i < p - 1; i++) {
if (mod_pow(g, i, p) == 1) {
flag = 0;
break;
}
}
if (flag) {
break;
}
}
// 生成私钥 x
x = get_random(2, p - 2);
// 计算公钥 y
y = mod_pow(g, x, p);
// 加密
printf("请输入要加密的明文:");
scanf("%lld", &m);
k = get_random(2, p - 2);
c1 = mod_pow(g, k, p);
c2 = m * mod_pow(y, k, p) % p;
printf("密文为:(%lld, %lld)\n", c1, c2);
return 0;
}
```
解密过程:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
// 求模幂运算 a^b mod m
long long mod_pow(long long a, long long b, long long m)
{
long long ans = 1;
while (b > 0) {
if (b & 1) {
ans = (ans * a) % m;
}
a = (a * a) % m;
b >>= 1;
}
return ans;
}
int main()
{
long long p, x, c1, c2, m;
scanf("%lld%lld%lld%lld", &p, &x, &c1, &c2);
// 解密
m = c2 * mod_pow(c1, p - 1 - x, p) % p;
printf("明文为:%lld\n", m);
return 0;
}
```
其中,加密过程中,首先生成一个大素数p,然后选择一个原根g,然后生成私钥x和公钥y。加密时,选择一个随机数k,计算密文c1和c2。解密时,根据公式,将密文c1、c2、私钥x和大素数p带入即可计算出明文m。
需要注意的是,由于ElGamal算法加密过程中需要进行随机化处理,因此同样的明文在不同的加密过程中得到的密文是不同的,这也是ElGamal算法的特点之一。