less_retarded_wiki/rsa.md

RSA

TODO

generating keys:

1. p := large random prime
2. q := large random prime
3. n := p * q
4. f := (p - 1) * (q - 1) (this step may differ in other versions)
5. e := 65537 (most common, other constants exist)
6. d := solve for x: 1 = (x * e) mod f
7. public key := (n,e)
8. private key := d

message encryption:

1. m := message encoded as a number < n
2. encrypted := m^e mod n

message decryption:

1. m := encrypted^d mod n
2. decrypted := decode message from number m

Code Example

Here is a stupidly simple C code demonstrating the algorithm, for simplicity we use laughably small primes, we only consider 4 character string as a message and make other simplifications.

#include <stdio.h>
#define e 65537       // often used constant

typedef unsigned long long u64;

void generateKeys(u64 prime1, u64 prime2, u64 *privateKey, u64 *publicKey)
{
  u64 f = (prime1 - 1) * (prime2 - 1);

  *publicKey = prime1 * prime2;
  *privateKey = 1;

  while (*privateKey) // brute force solve the equation
  {
    if (((*privateKey) * e) % f == 1)
      break;

    (*privateKey)++;
  }
}

u64 powerMod(u64 n, u64 power, u64 mod) // helper func, returns n^power % mod
{
  u64 result = 1;

  for (int i = 0; i < power; ++i)
    result = (result * n) % mod;

  return result;
}

u64 encryptNum(u64 n, u64 publicKey)
{
  return powerMod(n,e,publicKey);
}

u64 decryptNum(u64 n, u64 publicKey, u64 privateKey)
{
  return powerMod(n,privateKey,publicKey);
}

int main(void)
{
  u64 priv, pub,
    prime1 = 33461,
    prime2 = 17977;

  const char *str = "bich"; // we'll only consider 4 char string

  puts("generating keys, wait...");

  generateKeys(prime1,prime2,&priv,&pub);

  printf("prime1 = %llu\nprime2 = %llu\nprivate key = %llu\npublic key = %llu\n",
    prime1,prime2,priv,pub);

  u64 data = str[0] | (str[1] << 7) | (str[2] << 14) | (str[3] << 21);

  printf("string to encode: \"%s\"\n",str);
  printf("string as numeric data: %lld\n",data);

  if (data >= pub)
  {
    puts("Data is too big, choose bigger primes or smaller data.");
    return 1;
  }

  puts("encrypting...");

  u64 encrypted = encryptNum(data,pub);
  printf("encrypted: %lld\n",encrypted);

  puts("decrypting...");

  data = decryptNum(encrypted,pub,priv);
  printf("decrypted: %lld\n",data);

  printf("retrieved string: \"%c%c%c%c\"\n",data & 0x7f,(data >> 7) & 0x7f,
    (data >> 14) & 0x7f,(data >> 21) & 0x7f);

  return 0;
}

The program prints out:

generating keys, wait...
prime1 = 33461
prime2 = 17977
private key = 323099873
public key = 601528397
string to encode: "bich"
string as numeric data: 219739362
encrypting...
encrypted: 233361060
decrypting...
decrypted: 219739362
retrieved string: "bich"