RSA 암호화 구현

필자는 수학을 못하기때문에 왜 이게 이렇게 되는지 아직두 잘 모르겠다.

그래서 이글은 stap by step으로 구현에 대해 이야기를 할것이다.

RSA는 아래의 flow을 따라간다.

1. 두개의 소수를 찾는다.
2. 공개키를 만든다.
3. 공개키 기반으로 개인키를 만든다.
4. 데이터를 암호화 복호화을 해본다.

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. 암호화 복보화 하기.

암호화호와 복호화의 공식은 다음과 같다.

• 암호화 = c^e mod n.
• 복보화 = c^d 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