一、簡介:
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/
