This article was originally an open source implementation of Computer System Principle Experiment 2 of Shandong University
Since the score for the Principles of Computer Systems experiment is based on the difficulty of the encryption algorithm, and encryption algorithms are obviously not the focus of Principles of Computer Systems, my implementation is open sourced for other students’ reference.
The implementation is divided into two source files, keygen and cry. Keygen is responsible for generating keys, and cry is responsible for encryption and decryption. The complete code is attached at the end of the article.
keygen.c main part
The principle of rsa algorithm will not be explained anymore. Its key generation requires two large prime numbers p and q, and an e that is relatively prime with m. The larger p and q, the higher the security. Here comes a set of p, q, e, You can change it to the input form and find the large prime number input yourself.
It is difficult to use the C language to achieve high precision (without referencing third-party libraries), so some security is sacrificed here in exchange for much higher coding convenience. The range of __int128 reaches 1.7e38, and the 38-bit precision can barely be used as half high precision. Note that some compilers or machines do not support __int128. You can change it to long long, and then reduce p and q.
In the output, (e, n) is the public key and (d, n) is the private key, which is a pair. Public key encryption can and can only be decrypted with the private key, and vice versa. (The general usage is to publish the public key, others use the public key to encrypt the file and send it, and then you use the private key to decrypt it after receiving it)
int main()
{<!-- -->
__int128 p = 179424673, q = 3262476787;
//__int128 p = read(), q = read();
__int128 n = p * q;
__int128 m = (p - 1) * (q - 1);
__int128 e = 1628441;
//__int128 e = read();
if (gcd(e, m) != 1)
{<!-- -->
printf("e is not coprime with m\
");
return 0;
}
__int128d;
__int128 y;
exgcd(e, m, d, y);
d = (d % m + m) % m;
printf("n= ");
print(n);
printf("\
");
printf("e= ");
print(e);
printf("\
");
printf("d= ");
print(d);
return 0;
}
cry.c main part
Same as keygen, use __int128 instead of high precision.
First enter the operands, 1 for encryption and 2 for decryption, then the file to be encrypted (decrypted) (note the suffix), and the key (e,n) or (d,n)
Note that the file to be decrypted must be suffixed with .rsa, otherwise the following four characters will be deleted (modify by yourself)
The encryption implementation principle is to read the file to be encrypted byte by byte (char is exactly one byte), then encrypt it byte by byte, encrypt each byte into a digital ciphertext, and output it to the encrypted file, two bytes There are spaces in between to facilitate reading the ciphertext one by one during decryption.
Decryption is to decrypt each ciphertext into one byte and output it to a file.
int main()
{<!-- -->
printf("input as following:\
1(encry) filename e n\
2(decry) filename d n\
");
int ope;
scanf("%d", &ope);
char s[1000];
scanf("%s", s);
if (ope == 1)
{<!-- -->
__int128 e = read(), n = read();
FILE *fp1 = freopen(s, "r", stdin);
strcat(s, ".rsa");
FILE *fp2 = freopen(s, "w", stdout);
char c = getchar();
while (c != EOF)
{<!-- -->
__int128 x = c;
print(qpow(x, e, n));
putchar(' ');
c = getchar();
}
fclose(fp1);
fclose(fp2);
}
else
{<!-- -->
__int128 d = read(), n = read();
FILE *fp1 = freopen(s, "r", stdin);
s[strlen(s) - 4] = '\0';
FILE *fp2 = freopen(s, "w", stdout);
__int128 x;
while (x = read())
printf("%c", (char)qpow(x, d, n));
fclose(fp1);
fclose(fp2);
}
return 0;
}
Full file
cry.c
#include <stdio.h>
#include <string.h>
inline __int128 read()
{<!-- -->
__int128 x = 0, f = 1;
char ch;
if ((ch = getchar()) == EOF)
return 0;
while (ch < '0' || ch > '9')
{<!-- -->
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' & amp; & amp; ch <= '9')
{<!-- -->
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(__int128 x)
{<!-- -->
if (x < 0)
{<!-- -->
putchar('-');
x = -x;
}
if(x>9)
print(x / 10);
putchar(x % 10 + '0');
}
__int128 qpow(__int128 a, __int128 b, __int128 mod)
{<!-- -->
__int128 ans = 1;
while (b)
{<!-- -->
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main()
{<!-- -->
printf("input as following:\
1(encry) filename e n\
2(decry) filename d n\
");
int ope;
scanf("%d", &ope);
char s[1000];
scanf("%s", s);
if (ope == 1)
{<!-- -->
__int128 e = read(), n = read();
FILE *fp1 = freopen(s, "r", stdin);
strcat(s, ".rsa");
FILE *fp2 = freopen(s, "w", stdout);
char c = getchar();
while (c != EOF)
{<!-- -->
__int128 x = c;
print(qpow(x, e, n));
putchar(' ');
c = getchar();
}
fclose(fp1);
fclose(fp2);
}
else
{<!-- -->
__int128 d = read(), n = read();
FILE *fp1 = freopen(s, "r", stdin);
s[strlen(s) - 4] = '\0';
FILE *fp2 = freopen(s, "w", stdout);
__int128x;
while (x = read())
printf("%c", (char)qpow(x, d, n));
fclose(fp1);
fclose(fp2);
}
return 0;
}
keygen.c
#include#include inline __int128 read() { __int128 x = 0, f = 1; char ch; if ((ch = getchar()) == EOF) return 0; while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' & amp; & amp; ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void print(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if(x>9) print(x / 10); putchar(x % 10 + '0'); } __int128 qpow(__int128 a, __int128 b, __int128 mod) { __int128 ans = 1; while (b) { if (b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans; } __int128 exgcd(__int128 a, __int128 b, __int128 & amp;x, __int128 & amp;y) { if (!b) { x = 1; y = 0; return a; } __int128 d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } __int128 gcd(__int128 a, __int128 b) { return b ? gcd(b, a % b) : a; } int main() {<!-- --> __int128 p = 179424673, q = 3262476787; //__int128 p = read(), q = read(); __int128 n = p * q; __int128 m = (p - 1) * (q - 1); __int128 e = 1628441; //__int128 e = read(); if (gcd(e, m) != 1) {<!-- --> printf("e is not coprime with m\ "); return 0; } __int128d; __int128 y; exgcd(e, m, d, y); d = (d % m + m) % m; printf("n= "); print(n); printf("\ "); printf("e= "); print(e); printf("\ "); printf("d= "); print(d); return 0; }