RSA is a very famous public key cryptosystem and I think it’s one of the greatest inventions of software engineering/information technology. It shouldn’t hurt you if you learn the detail of it.
I won’t go into detail but the following expression is everything.
c = me mod n
where m is the message and the pair of e and n is the public key. The m and n are so big that built-in 64-bit integer is not enough. That’s why I need GMP in the first place.
The catch is, the message to encrypt (m) must be smaller than n because c is always smaller than n. Also, the expression requires exponentiation and division, so it can’t be super fast. For these reasons, RSA is mainly used with other encryption algorithms such as AES, and its primary usage is to exchange the private key of those algorithms.
To decrypt the message, exact the same expression is used. This is another beauty of the algorithm.
m = cd mod n
where d is the private key.
When implementing this, encrypting and decrypting each is really a one-liner using GMP’s mpz_powm function but extra care must be taken for padding the message so that the message and n have the same length.
There are several padding methods but I chose PKCS #1 for simplicity. I had to browse RFC 8017 to figure out the exact method for the padding. As always with RFCs, it’s a huge document but all I need was this section.
To test my code, I first generated a private/public key pair using openssl commands then pasted the output on my code. The test message “hello” is also hard-coded. I then output the encrypted binary to a file, run openssl’s decrypt command to confirm the decrypted message is “hello”.
Below is a code snippet of my test.
#include <assert.h>
#include <string.h>
#include <gmp.h>
// helper function to convert C string to mpz.
int load_int_from_str(mpz_t n, const char *key_str_raw)
{
char key_str[2048*2] = {0};
int j = 0;
for(int i = 0; i < strlen(key_str_raw); i++)
{
char c = key_str_raw[i];
if ( c != ':' && c != ' ')
key_str[j++] = c;
}
return mpz_set_str(n, key_str, 16);
}
// helper function to convert mpz to binary representation.
int mpz_to_bin(mpz_t n, char *outbuf)
{
char buf[2048 * 2];
char hex[3] = {0};
mpz_get_str(buf, 16, n);
int len = strlen(buf);
int ofs = len % 2;
printf("len=%d\n", len);
int j = 0;
if (ofs == 1) // the first byte could be one-digit.
{
hex[0] = buf[0];
outbuf[j++] = (int)strtol(hex, NULL, 16);
}
for(int i = 0; i < len / 2; i++)
{
hex[0] = buf[i * 2 + ofs];
hex[1] = buf[i * 2 + ofs + 1];
outbuf[j++] = (int)strtol(hex, NULL, 16);
}
return j;
}
int test_rsa(int argc, char const **argv)
{
// The private key - it is created with OpenSSL by running the commands:
// > openssl genrsa 512 > privkey.txt
// > openssl rsa -text -noout < privkey.txt
// Then copy the "privateExponent" of the output.
const char priv_key_str_raw[] =
"57:05:07:a2:1b:2a:af:af:f4:bf:50:b1:dc:24:fb: \
16:9c:c1:33:07:6c:be:28:d7:18:02:c0:b4:08:6e: \
79:4f:f7:56:8e:6b:6b:73:cc:1d:da:66:8c:2a:a4: \
8f:8c:91:7c:1e:b4:e2:4d:56:43:aa:0b:21:25:6a: \
93:05:e6:f1";
// The public key - it is created by first creating the private key as above and then run:
// > openssl rsa -pubout < privkey.txt > pubkey.txt
// > openssl rsa -text -pubin -noout < pubkey.txt
// Then copy the "Modulus" part of the output.
const char pub_key_str_raw[] =
"00:c1:95:b1:fe:49:50:48:87:bc:d6:db:9e:17:59: \
14:a4:af:cf:32:4d:3b:85:6b:35:27:65:e2:83:89: \
b3:c1:02:8c:78:bb:08:a8:cb:c3:2e:a4:2d:ed:05: \
e6:6c:c4:06:11:5c:68:69:91:fd:a0:da:b9:e2:62: \
16:6e:20:32:a5";
mpz_t n, d, m, m_enc, m_dec;
mpz_init(n);
mpz_init(d);
mpz_init(m);
mpz_init(m_enc);
mpz_init(m_dec);
int flag = load_int_from_str(n, pub_key_str_raw);
assert(flag == 0);
flag = load_int_from_str(d, priv_key_str_raw);
assert(flag == 0);
int k = 64; // TODO: for 512-bit key only!!!
int e = 65537; // This is the "Exponent" output in the public key.
char message[] = "hello\n"; // must be smaller than the key length.
int mlen = strlen(message);
int msg = 0;
//
// Padding with PKCS#1 method
//
mpz_set_ui(m, msg);
int bt = 2; //1; // 1: private, 2: public
mpz_add_ui(m, m, bt);
for(int i = 0; i < k - mlen - 3; i++)
{
mpz_mul_ui(m, m, 256);
int ps = 0xff; // for bt = 1;
if (bt == 2){
ps = rand() & 0xff;
if (ps == 0) ps = 0x01; // has to be non-zero.
}
mpz_add_ui(m, m, ps);
}
mpz_mul_ui(m, m, 256);
//
// Convert the message to a number.
//
for(int i = 0; i < mlen; i++)
{
mpz_mul_ui(m, m, 256);
mpz_add_ui(m, m, message[i]);
}
printf("message=");
mpz_out_str(stdout, 16, m);
printf("\n");
//
// encrypting with just one line!
//
mpz_powm_ui(m_enc, m, e, n);
printf("enc=");
mpz_out_str(stdout, 16, m_enc);
printf("\n");
//
// Output the file - it can be decrypted with other RSA tools like openssl.
// For example,
// > openssl pkeyutl -decrypt -pkeyopt rsa_padding_mode:pkcs1 -inkey privkey.txt -in enc_out.bin -out dec_test.txt
//
FILE *fp = fopen("enc_out.bin", "wb");
if (fp != NULL)
{
char bin[1024];
mpz_to_bin(m_enc, bin);
fwrite(bin, k, 1, fp);
fclose(fp);
printf("file written to enc_out.bin.\n");
}
//
// decoding for verification
//
mpz_powm(m_dec, m_enc, d, n);
printf("dec=");
mpz_out_str(stdout, 16, m_dec);
printf("\n");
char dmesg[1024] = {0};
int len = mpz_to_bin(m_dec, dmesg);
// Find zero which could be the last padding byte.
int i = 0;
for(i = 3; i < len; i++)
if (dmesg[i] == 0) break;
printf("decrypted message: %s\n", dmesg + i + 1);
mpz_clear(n);
mpz_clear(d);
mpz_clear(m);
mpz_clear(m_enc);
mpz_clear(m_dec);
}
