C 中的 RSA 实现
RSA implementation in C
我正在尝试用 C 语言为一个项目实现 RSA 算法。
我可以生成所需的 encryption/decryption 密钥，但我似乎无法正确执行 encryption/decryption。
错误似乎在于我如何计算加密消息。它的数学公式是 m^e mod n，其中 m 是消息，e 是加密指数，n 是 public 密钥和私钥的 modulus。我使用 pow() 函数计算 m^e，并使用 fmod() 函数和 %n 计算 mod n。两者似乎都不起作用（给出正确的输出）。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int p1,p2,mod,tot, encExp, decExp, conRelVal;
// Function to check if numbers given are primes
// @param pr: the number being tested
int prime(long int pr){
int i;
int j;
j = sqrt(pr);
for(i = 2; i <= j; i++){
if(pr % i == 0)
return 0;
}
return 1;
}
int gcd(int a, int h)
{
int temp;
while (1)
{
temp = a%h;
if (temp == 0)
return h;
a = h;
h = temp;
}
}
//function to generate encryption key
void encryption_key(){
p1 = 61;
p2 = 53;
conRelVal = 15;
mod = p1*p2;
tot = (p1-1)*(p2-1);
encExp = 12;
while (encExp < tot){
// e must be co-prime to the totient and
// smaller than the totient.
if (gcd(encExp,tot)==1)
break;
else
encExp++;
}
decExp = ((1+(conRelVal*tot))/encExp);
printf("p1=%d\np2=%d\nmod=%d\ntot=%d\ne=%d\nd=%d\nconst=%d\n",p1,p2,mod,tot, encExp, decExp, conRelVal);
printf("Public Key:\t(%d,%d)", mod,encExp);
printf("\nPrivate Key:\t(%d,%d)", mod,decExp);
}
double encrypt(int msg){
// Encryption c = (msg ^ e) % n
double l;
l = pow(msg, encExp);
int j;
j = ((int)l%mod);
l = fmod(l, mod);
printf("\nMessage:\t%d\nEncrypted:\t%lf",msg,l);
printf("\nMessage:\t%d\nEncrypted:\t%d",msg,j);
return l;
}
void decrypt(double cyp){
// Decryption m = (c ^ d) % n
double m ;
m = pow(cyp, decExp);
int z = ((int)m%mod);
m = fmod(m, mod);
printf("\nEncrypted:\t%lf\nDecrypted:\t%lf",cyp,m);
printf("\nEncrypted:\t%lf\nDecrypted:\t%d",cyp,z);
}
int main() {
encryption_key();
int msg = 123;
double cyp = encrypt(msg);
decrypt(cyp);
return 0;
}
Results:
$ ./test
p1=61
p2=53
mod=3233
tot=3120
e=17
d=2753
const=15
Public Key: (3233,17)
Private Key: (3233,2753)
Message: 123
Encrypted: 992.000000
Message: 123
Encrypted: -2194
Encrypted: 992.000000
Decrypted: nan
Encrypted: 992.000000
Decrypted: -2194
我希望加密为 855
解密为 123
通常，编程语言对可以存储在变量中的数量有限制。每当您尝试分配一个大于它可以存储的值时，它都会 wrap/round 回到最小值并重新开始计数。
我在这里解释起来有点困难。简而言之，我想说的是，你的计算可能会出乎意料地出错，因为变量有能力决定你可以在其中存储多大的价值。因此请确保没有溢出并且计算正确。如果计算出错，那么您的输出显然不正确。
如上所述，您不能在 C 数据类型中存储大数。解决方法是使用 gmp。这是适用于您的练习的代码。丢弃代码的第一部分，它只是假设已完成模因式分解来破解私有指数。转到 /* 加密函数 */ 估计丑了...
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <gmp.h>
int main(void)
{
/* data */
int p = 61;
int q = 53;
size_t e = 17; /* public exponent */
size_t d; /* private exponent not given */
int msg = 123; /* message to be encrypted */
printf("==============\n");
printf("DATA\n");
printf("==============\n");
printf("int p = %d\n", p);
printf("int q = %d\n", q);
printf("int e = %ld\n", e);
printf("int msg = %d\n\n", msg);
/* compute modulo n */
int n = p*q;
printf("=========================\n");
printf("1 - Compute n = p * q\n");
printf("=========================\n");
printf("n = %d\n\n", n);
/* compute totient Euler function */
printf("==========================================================\n");
printf("2 - Compute totient Euler function phi(n) = (p-1)(q-1)\n");
printf("==========================================================\n");
int phi = (p-1) * (q-1);
printf("totient = %d\n\n", phi);
/* compute d private exponent */
printf("==========================================================\n");
printf("3 - Compute d private exponent d*e mod(phi(n)) = 1\n");
printf("==========================================================\n");
for (d = 1; d < ULONG_MAX; d++) {
int tmp = (d * e)%phi;
if (tmp == 1) {
printf("d is FOUND: %ld\n\n", d);
break;
}
}
/* encryption function */
printf("==========================================================\n");
printf("4 - ENCRYPTION of message 123 --> enc_msg = m^e mod(n)\n");
printf("==========================================================\n");
printf("modulo n = %d\n", n);
/* we are using gmp to be able to compute very large numbers */
mpz_t me; /* message^pub_exp */
mpz_t enc_msg; /* encrypted message */
mpz_t modn; /* modulo n previously computed "3233" */
mpz_inits(me, enc_msg, modn);
mpz_set_str(modn, "3233", 10); /* 10 means decimal number */
mpz_ui_pow_ui(me, msg, e); /* compute m^e */
mpz_mod(enc_msg, me, modn); /* compute m^e mod(n) */
printf("message^e mod(n) = ");
mpz_out_str(NULL, 10, enc_msg);
printf("\n\n");
/* decryption function */
printf("=============================================================\n");
printf("5 - DECRYPTION of enc_msg 855 --> dec_msg = enc_msg^d mod(n)\n");
printf("=============================================================\n");
printf("modulo n = %d\n", n);
int enc_message = 855; /* previously computed */
mpz_t md; /* enc_message^priv_exp */
mpz_t dec_msg; /* decrypted message */
mpz_inits(md, dec_msg, modn);
mpz_set_str(modn, "3233", 10);
mpz_ui_pow_ui(md, enc_message, d); /* compute enc_message^d */
mpz_mod(dec_msg, md, modn); /* compute enc_msg^d mod(n) */
printf("dec_msg^d mod(n) = ");
mpz_out_str(NULL, 10, dec_msg);
printf("\n\n");
/* free */
mpz_clear(me);
mpz_clear(md);
mpz_clear(modn);
mpz_clear(enc_msg);
mpz_clear(dec_msg);
return 0;
}
我正在尝试用 C 语言为一个项目实现 RSA 算法。
我可以生成所需的 encryption/decryption 密钥，但我似乎无法正确执行 encryption/decryption。 错误似乎在于我如何计算加密消息。它的数学公式是 m^e mod n，其中 m 是消息，e 是加密指数，n 是 public 密钥和私钥的 modulus。我使用 pow() 函数计算 m^e，并使用 fmod() 函数和 %n 计算 mod n。两者似乎都不起作用（给出正确的输出）。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int p1,p2,mod,tot, encExp, decExp, conRelVal;
// Function to check if numbers given are primes
// @param pr: the number being tested
int prime(long int pr){
int i;
int j;
j = sqrt(pr);
for(i = 2; i <= j; i++){
if(pr % i == 0)
return 0;
}
return 1;
}
int gcd(int a, int h)
{
int temp;
while (1)
{
temp = a%h;
if (temp == 0)
return h;
a = h;
h = temp;
}
}
//function to generate encryption key
void encryption_key(){
p1 = 61;
p2 = 53;
conRelVal = 15;
mod = p1*p2;
tot = (p1-1)*(p2-1);
encExp = 12;
while (encExp < tot){
// e must be co-prime to the totient and
// smaller than the totient.
if (gcd(encExp,tot)==1)
break;
else
encExp++;
}
decExp = ((1+(conRelVal*tot))/encExp);
printf("p1=%d\np2=%d\nmod=%d\ntot=%d\ne=%d\nd=%d\nconst=%d\n",p1,p2,mod,tot, encExp, decExp, conRelVal);
printf("Public Key:\t(%d,%d)", mod,encExp);
printf("\nPrivate Key:\t(%d,%d)", mod,decExp);
}
double encrypt(int msg){
// Encryption c = (msg ^ e) % n
double l;
l = pow(msg, encExp);
int j;
j = ((int)l%mod);
l = fmod(l, mod);
printf("\nMessage:\t%d\nEncrypted:\t%lf",msg,l);
printf("\nMessage:\t%d\nEncrypted:\t%d",msg,j);
return l;
}
void decrypt(double cyp){
// Decryption m = (c ^ d) % n
double m ;
m = pow(cyp, decExp);
int z = ((int)m%mod);
m = fmod(m, mod);
printf("\nEncrypted:\t%lf\nDecrypted:\t%lf",cyp,m);
printf("\nEncrypted:\t%lf\nDecrypted:\t%d",cyp,z);
}
int main() {
encryption_key();
int msg = 123;
double cyp = encrypt(msg);
decrypt(cyp);
return 0;
}
Results:
$ ./test
p1=61
p2=53
mod=3233
tot=3120
e=17
d=2753
const=15
Public Key: (3233,17)
Private Key: (3233,2753)
Message: 123
Encrypted: 992.000000
Message: 123
Encrypted: -2194
Encrypted: 992.000000
Decrypted: nan
Encrypted: 992.000000
Decrypted: -2194
我希望加密为 855 解密为 123
通常，编程语言对可以存储在变量中的数量有限制。每当您尝试分配一个大于它可以存储的值时，它都会 wrap/round 回到最小值并重新开始计数。
我在这里解释起来有点困难。简而言之，我想说的是，你的计算可能会出乎意料地出错，因为变量有能力决定你可以在其中存储多大的价值。因此请确保没有溢出并且计算正确。如果计算出错，那么您的输出显然不正确。
如上所述，您不能在 C 数据类型中存储大数。解决方法是使用 gmp。这是适用于您的练习的代码。丢弃代码的第一部分，它只是假设已完成模因式分解来破解私有指数。转到 /* 加密函数 */ 估计丑了...
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <gmp.h>
int main(void)
{
/* data */
int p = 61;
int q = 53;
size_t e = 17; /* public exponent */
size_t d; /* private exponent not given */
int msg = 123; /* message to be encrypted */
printf("==============\n");
printf("DATA\n");
printf("==============\n");
printf("int p = %d\n", p);
printf("int q = %d\n", q);
printf("int e = %ld\n", e);
printf("int msg = %d\n\n", msg);
/* compute modulo n */
int n = p*q;
printf("=========================\n");
printf("1 - Compute n = p * q\n");
printf("=========================\n");
printf("n = %d\n\n", n);
/* compute totient Euler function */
printf("==========================================================\n");
printf("2 - Compute totient Euler function phi(n) = (p-1)(q-1)\n");
printf("==========================================================\n");
int phi = (p-1) * (q-1);
printf("totient = %d\n\n", phi);
/* compute d private exponent */
printf("==========================================================\n");
printf("3 - Compute d private exponent d*e mod(phi(n)) = 1\n");
printf("==========================================================\n");
for (d = 1; d < ULONG_MAX; d++) {
int tmp = (d * e)%phi;
if (tmp == 1) {
printf("d is FOUND: %ld\n\n", d);
break;
}
}
/* encryption function */
printf("==========================================================\n");
printf("4 - ENCRYPTION of message 123 --> enc_msg = m^e mod(n)\n");
printf("==========================================================\n");
printf("modulo n = %d\n", n);
/* we are using gmp to be able to compute very large numbers */
mpz_t me; /* message^pub_exp */
mpz_t enc_msg; /* encrypted message */
mpz_t modn; /* modulo n previously computed "3233" */
mpz_inits(me, enc_msg, modn);
mpz_set_str(modn, "3233", 10); /* 10 means decimal number */
mpz_ui_pow_ui(me, msg, e); /* compute m^e */
mpz_mod(enc_msg, me, modn); /* compute m^e mod(n) */
printf("message^e mod(n) = ");
mpz_out_str(NULL, 10, enc_msg);
printf("\n\n");
/* decryption function */
printf("=============================================================\n");
printf("5 - DECRYPTION of enc_msg 855 --> dec_msg = enc_msg^d mod(n)\n");
printf("=============================================================\n");
printf("modulo n = %d\n", n);
int enc_message = 855; /* previously computed */
mpz_t md; /* enc_message^priv_exp */
mpz_t dec_msg; /* decrypted message */
mpz_inits(md, dec_msg, modn);
mpz_set_str(modn, "3233", 10);
mpz_ui_pow_ui(md, enc_message, d); /* compute enc_message^d */
mpz_mod(dec_msg, md, modn); /* compute enc_msg^d mod(n) */
printf("dec_msg^d mod(n) = ");
mpz_out_str(NULL, 10, dec_msg);
printf("\n\n");
/* free */
mpz_clear(me);
mpz_clear(md);
mpz_clear(modn);
mpz_clear(enc_msg);
mpz_clear(dec_msg);
return 0;
}