RSA加密法 & C 程式實作 & openssl 產生key

一、簡介:
  RSA是一種非對稱加密方式，使用者利用公鑰加密，或是使用私鑰解密。使用的數字通常很大(目前為1024 bit以上)。

二、流程:
  1. 產生鑰匙:
    A. 取兩質數p和q，並另N = p * q
    B. 設定 r 為(p - 1) * (q - 1)的公倍數。如:r = (p - 1) * (q - 1)
    C. 找一個e與r互質(且小於r)
    D. 找出e在mod r下的乘法反元素d  (e * d mod r = 1)
    E. (e, N)為公鑰；(d, N)則為私鑰

  2. 加密:
    密文 = (明文)^e mod N
  3. 解密:
    明文 = (密文)^d mod N

三、實作:
  1. 產生鑰匙: 利用openssl可以產生鑰匙
   

$openssl genrsa -out <file>.pem <key bit>

   

$openssl rsa -text -in <file>.pem

(轉為可讀的形式)
產生的key:

modulus即為N
publicExponent即為e
Private-Key即為d
也就是，使用(publicExponent, modulus)加密；使用(Private-Key, modulus)解密
最下面RSA private key為decode前的樣子(pem格式)

  2. 程式碼完全參照參考網址：（除了）
http://www.codedata.com.tw/social-coding/rsa-c-implementation/
（除了power有改變）

#include <stdio.h>
#include <assert.h>
#include <stdint.h>


#define BigInt uint64_t


BigInt newBigInt(char *str) {
  return atoi(str);
}

char tempStr[1025];

char *big2str(BigInt a) {
  sprintf(tempStr, "%lld", a);
  return tempStr;
}


BigInt mul(BigInt a, BigInt b) {
  return a*b;
}


BigInt div(BigInt a, BigInt b) {
  return a/b;
}


BigInt mod(BigInt a, BigInt n) {
  return a%n;
}



BigInt inv(BigInt e, BigInt r) {
  BigInt d;
  for (d=2; d<r; d++) {
    BigInt ed = mul(e, d); // re = (e*d) % r;
    BigInt re = mod(ed,r);
    if (re == 1) {
      printf("e=%lld d=%lld r=%lld (e*d) mod r=%lld\n", e, d, r, re);
      return d;
    }
  }
  assert(0);
}




BigInt Encrypt::power(BigInt a, BigInt k, BigInt N) {
    BigInt l_out = 1;



    while (k != 0)
    {



        if (k & 0x01)
        {
            l_out *= a;

            l_out = mod(l_out, N);
        }
        a *= a;
        a = mod(a, N);
        k = k >> 1;
    }
    return l_out;
}



int main() {
  BigInt p = newBigInt("2213"), q = newBigInt("2663");
  BigInt N = mul(p, q);
  BigInt r = mul(p-1, q-1);
  printf("N=%s r=%s\n", big2str(N), big2str(r));
  BigInt e = newBigInt("4723");
  BigInt d = inv(e, r);
  BigInt m = newBigInt("3320");
  printf("m=%s\n", big2str(m));
  BigInt c = power(m, e, N);
  printf("c=%s\n", big2str(c));
  BigInt m2 = power(c, d, N);
  printf("m2=%s\n", big2str(m2));
}

ref:
http://www.codedata.com.tw/social-coding/rsa-c-implementation/