rsa.md

   1 # RSA
   2
   3 TODO
   4
   5 generating keys:
   6
   7 1. *p := large random prime*
   8 2. *q := large random prime*
   9 3. *n := p * q*
  10 4. *f := (p - 1) * (q - 1)* (this step may differ in other versions)
  11 5. *e := 65537* (most common, other constants exist)
  12 6. *d := solve for x: 1 = (x * e) mod f*
  13 7. *public key := (n,e)*
  14 8. *private key := d*
  15
  16 message encryption:
  17
  18 1. *m := message encoded as a number < n*
  19 2. *encrypted := m^e mod n*
  20
  21 message decryption:
  22
  23 1. *m := encrypted^d mod n*
  24 2. *decrypted := decode message from number m*
  25
  26 ## Code Example
  27
  28 Here is a stupidly simple [C](c.md) code demonstrating the algorithm, for simplicity we use laughably small primes, we only consider 4 character string as a message and make other simplifications.
  29
  30 ```
  31 #include <stdio.h>
  32 #define e 65537       // often used constant
  33
  34 typedef unsigned long long u64;
  35
  36 void generateKeys(u64 prime1, u64 prime2, u64 *privateKey, u64 *publicKey)
  37 {
  38   u64 f = (prime1 - 1) * (prime2 - 1);
  39
  40   *publicKey = prime1 * prime2;
  41   *privateKey = 1;
  42
  43   while (*privateKey) // brute force solve the equation
  44   {
  45     if (((*privateKey) * e) % f == 1)
  46       break;
  47
  48     (*privateKey)++;
  49   }
  50 }
  51
  52 u64 powerMod(u64 n, u64 power, u64 mod) // helper func, returns n^power % mod
  53 {
  54   u64 result = 1;
  55
  56   for (int i = 0; i < power; ++i)
  57     result = (result * n) % mod;
  58
  59   return result;
  60 }
  61
  62 u64 encryptNum(u64 n, u64 publicKey)
  63 {
  64   return powerMod(n,e,publicKey);
  65 }
  66
  67 u64 decryptNum(u64 n, u64 publicKey, u64 privateKey)
  68 {
  69   return powerMod(n,privateKey,publicKey);
  70 }
  71
  72 int main(void)
  73 {
  74   u64 priv, pub,
  75     prime1 = 33461,
  76     prime2 = 17977;
  77
  78   const char *str = "bich"; // we'll only consider 4 char string
  79
  80   puts("generating keys, wait...");
  81
  82   generateKeys(prime1,prime2,&priv,&pub);
  83
  84   printf("prime1 = %llu\nprime2 = %llu\nprivate key = %llu\npublic key = %llu\n",
  85     prime1,prime2,priv,pub);
  86
  87   u64 data = str[0] | (str[1] << 7) | (str[2] << 14) | (str[3] << 21);
  88
  89   printf("string to encode: \"%s\"\n",str);
  90   printf("string as numeric data: %lld\n",data);
  91
  92   if (data >= pub)
  93   {
  94     puts("Data is too big, choose bigger primes or smaller data.");
  95     return 1;
  96   }
  97
  98   puts("encrypting...");
  99
 100   u64 encrypted = encryptNum(data,pub);
 101   printf("encrypted: %lld\n",encrypted);
 102
 103   puts("decrypting...");
 104
 105   data = decryptNum(encrypted,pub,priv);
 106   printf("decrypted: %lld\n",data);
 107
 108   printf("retrieved string: \"%c%c%c%c\"\n",data & 0x7f,(data >> 7) & 0x7f,
 109     (data >> 14) & 0x7f,(data >> 21) & 0x7f);
 110
 111   return 0;
 112 }
 113 ```
 114
 115 The program prints out:
 116
 117 ```
 118 generating keys, wait...
 119 prime1 = 33461
 120 prime2 = 17977
 121 private key = 323099873
 122 public key = 601528397
 123 string to encode: "bich"
 124 string as numeric data: 219739362
 125 encrypting...
 126 encrypted: 233361060
 127 decrypting...
 128 decrypted: 219739362
 129 retrieved string: "bich"
 130 ```