RSA 암호화 구현
필자는 수학을 못하기때문에 왜 이게 이렇게 되는지 아직두 잘 모르겠다.
그래서 이글은 stap by step으로 구현에 대해 이야기를 할것이다.
RSA는 아래의 flow을 따라간다.
- 두개의 소수를 찾는다.
- 공개키를 만든다.
- 공개키 기반으로 개인키를 만든다.
- 데이터를 암호화 복호화을 해본다.
1. 두개의 소수를 찾는다.
공개키를 만들기위해서는 총 두가지의 다른 소수가 필요하다.
필자는 이키를 p와 q라고 부를거고 p를 11로 q를 13로 한다.
p와 q의 곱한 값을 n이라고 한다. n을 module 이라고 한다.
n = 11 * 13 = 143 이다. 이때 n의 bit Size을 구해주자.

계산기의 bin은 총 13바이트이다. 보통 RSA의 암호화하게되면 1024bit , 2048bit란 이야기가 나오는데 이 사이즈의 크기를 가르키는 것이다.
bit 두배가 될수록 암호화 성능은 6-7배 떨어진다.

2. 공개키를 만든다.
공개키를 만들기위해 e라는 값이 필요한데 다음과 같은 특성이 있다.
- 1보다 크고 Φ(n)보다 작아야한다.
- Φ(n) = (P-1)(Q-1) 이다.
- e는 Φ(n) 서로수여야한다.
Φ(n)은 (p-1)( Q-1) = 120
즉 1 < e < 120이고 서로수를 만족하는 수는 7이다.
공개키는 143 과 7이다.
3. 개인키를 만든다.
개인키에서는 d라는 값이 필요한다.
ed를 (p – 1)(q – 1)(p−1)(q−1)으로 나눈 나머지가 1이 되도록 하는 d를 찾는다.
이는 mod러의 역수를 취하는 방법과 매우 동일하기 때문에 확장 유클리드 호제법으로 구할수 있다.
자세한 내용은 https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-inverses 이를 참조하자.
역수를 구하게되면 47이 나온다.
비밀키는 143과 47이다.
3. 암호화 복보화 하기.
암호화호와 복호화의 공식은 다음과 같다.
- 암호화 = ce mod n.
- 복보화 = cd mod n
#include<stdio.h>
#include<math.h>
// Returns gcd of a and b
int gcd(int a, int h)
{
int temp;
while (1)
{
temp = a % h;
if (temp == 0)
return h;
a = h;
h = temp;
}
}
void extended_euclid(long a, long b, long* x,
long* y, long* d)
/* calculates a * *x + b * *y = gcd(a, b) = *d */
/* Author: Pate Williams (c) 1997 */
{
long q, r, x1, x2, y1, y2;
if (b == 0) {
*d = a, * x = 1, * y = 0;
return;
}
x2 = 1, x1 = 0, y2 = 0, y1 = 1;
while (b > 0) {
q = a / b, r = a - q * b;
*x = x2 - q * x1, * y = y2 - q * y1;
a = b, b = r;
x2 = x1, x1 = *x, y2 = y1, y1 = *y;
}
*d = a, * x = x2, * y = y2;
}
int main()
{
double p = 3;
double q = 7;
double n = p * q;
double e = 2;
double phi = (p - 1) * (q - 1);
while (e < phi)
{
if (gcd(e, phi) == 1)
break;
else
e++;
}
long d, x, y;
extended_euclid(phi, e, &x, &y, &d);
d = y;
double msg = 12;
printf("Message data = %lf", msg);
double c = pow(msg, e);
c = fmod(c, n);
printf("\nEncrypted data = %lf", c);
double m = pow(c, d);
m = fmod(m, n);
printf("\nOriginal Message Sent = %lf", m);
return 0;
}

추가적으로 rsa암호화를 하게되면 아래와 같은 형태를 자주 볼수있는데 으로 rsa암호화를 하게되면 아래와 같은 형태를 자주 볼수있는데 이를 PKCS 라고 하며 이값에 모듈값과 N값이 담겨져있다.
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAm87/x6XSM/qUj4wsdBYf
o3L3gXRantoFxkm6byVvyyMr2yJJ0UKR8NIncutYkk5WxrscRnyazzOKgW1KnNwH
hzjgJO9GkGK8c0U5sjaRBAyOXvVBptzgX+d0j09EkuByXam44ZlleVo+lSLH1uOo
JvNWzYrEL3iwY0s4x4r04vGGiBdb9lx1UKNlLExREHXiD3DELBjwTR6xiw1WMY2w
kf5DAKcQmRnmQDRI/G4rrVEhWLkP6LPbluq5PqreRZNsCj2sIF2tc6j7p+cSlF4C
JrhdMc9eSmUYCNKcXEZOMoPIZ7BdJkMqHdSeoTwSTV3/P0/2y5EnQ7fwxjZSaRUA
gRZQvd8lTtxx/Flq+TH6gHd6bOBmi7oOCpWwpQFKgogOklz3mnBo+znajSTd4bdV
g/6VmNB5oZYEG64i2l1B0WGbzvOe5lfUgsC4nXDxCcubahoXRc+Hmvy65gqPus02
PJFBJVULYHgVN6hljNy65/pL8IYvkx4laJuK6aFNngSg5mDIO6l2iv9n1X1VusPa
GKDfKbMrEWmt+SdZY1b2yTy+h9uQyhvYvTu0muwePKLfMXo0hebSJWojWlVEClgO
pTYgLvbumZ4Tx/KAomjybvS9NxsR4Iu7xM3cwWgj6zNvj7Eq0pFIGh3vqvL7Wvn0
dLKeWdV1hOZBtK+o4xGFJNMCAwEAAQ==
-----END PUBLIC KEY-----
참조 :
https://www.geeksforgeeks.org/rsa-algorithm-cryptography/
https://ko.wikipedia.org/wiki/%EA%B3%B5%EA%B0%9C_%ED%82%A4_%EC%95%94%ED%98%B8_%ED%91%9C%EC%A4%80