RSA 인증

인증은 통신하려는 상대방이 신뢰할 수 있는 지를 확인하는 사용자 인증과 메시지의 내용을 누군가 바꿔치기 했는지를 확인하기 위한 메시지 인증으로 나눌 수 있다. 사용자 인증은 공개키 기반인 RSA를 이용한 디지털 서명 방식을 사용할 수 있다. 

원리는 메시지의 해쉬 값에 인증서 발급자가 개인키를 통해 암호화하고 이를 수신하는 쪽은 해쉬 값을 공개키로 암호화를 해제해 해쉬함수를 통해 메시지의 무결성을 검사하는 방식으로 이루어 진다.   암호화된 해쉬 값을 디지털 서명 값이라고 하는 데 이 값은 오직 인증서 발급자의 개인키로만 암호화되고 이를 공개키를 통해서 확인 할 수 있기 때문에 이를 통해 인증서를 발행한 쪽에서 이 메시지를 전송했음을 신뢰할 수 있다. 물론 중간에 침입자가 자신이 만든 인증서를 상대방의 인증서로 속이고 이를 전달할 수 있다. 이러한 문제를 해결하기 위해, 공인된 인증 기관에 자신의 공개키를 등록하게되는데, 이에 따라 추가적으로 공인된 인증 기관의 정보와 인증서의 변조를 막기 위해 공인된 인증기관의 개인키로 디지털 서명을 추가한다. 상대방은 공인된 인증기관에 대한 공개키를 가지고 이 인증서의 신뢰 여부를 판단하게 된다. 

 

여기서 디지털 서명을 암호화 하기 위한 개인키와 공개키가 어떻게 생성되는지에 대해 살펴본다. 

1. 두 소수 p, q를 정하고 이를 곱한 값을 K라 하자. 

2. (p - 1)(q - 1) 의 최소 공배수를  라고 한다.

3.  와 서로 소인 임의의 소수를 e 로 정한다.

4. d x e mod  = 1  이 되는 ( 이를 e의  에 대한 나머지 연산의 곱셈 역원이라고 한다.) d를 정한다. 

 

메시지를 암호화 할 때 메시지 m 에 대해 암호화된 메시지  이고 이를 반대로  을 통해 m 으로 복호화 할 수 있다.

아래는 이를 테스트하기 위한 코드로 실제로는 키의 길이가 int 값으로 부족하지만 실제 RSA가 어떤 방식으로 암호화와 복호화를 수행하는 지를 보여주기 위해 작은 수를 사용한다. 실제로는 BigNumber를 통해서 구현해야 하는데, gmp 라이브러리를 사용해서 이를 구현 할 수 있다. 이에 대한 내용은 다음에 다루기로 한다. 

#include <gtest/gtest.h>
#include <random>
#include "utility.h"
TEST(rsa_test_case, gcd_case) {
   EXPECT_EQ(3,  gcd(15, 6));
}
TEST(rsa_test_case, lcm_case) {
    EXPECT_EQ(60,  lcm(10, 12));
}

TEST(rsa_test_case, e_value_case) {
    int e = 0;
    for(e = 4098; gcd(e, 60) != 1; e = next_prime(e));
    EXPECT_EQ(4099, e);
}

TEST(rsa_test_case, random_number_case) {
    std::cout << random_prime<long long>() << std::endl;
}

TEST(rsa_test_case, rsa_case) {
   auto p = random_prime<int>();
   auto q = random_prime<int>();
    int e = 0;
    int  K = p * q;
   int   phi = lcm(p -1, q - 1);
    for(e = 4098; gcd(e, phi) != 1; e = next_prime(e));
    auto d = invert(e, phi);
    int message = 128;
    auto c = powm(message, e, K);
    auto m = powm(c, d, K);
    EXPECT_EQ(message, m);

}

int main(int argc, char **argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

#pragma once
#include <iostream>
#include <tuple>
#include <random>
#include <array>
#include <cstdio>
#include <vector>
/*
 *  gcd (a , b)
 *  if b == 0
 *  return a;
 *  else
 *  gcd(b, a mod b)
 */
template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
T gcd(T a, T b) {
    if (b == 0) return a;
    return gcd( b, a % b);
}
/*
 * lcm(a, b)
 *  a * b / gcd(a, b);
 */

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
T lcm (T a, T b) {
    if (b > a ) std::swap(a, b);
    return (a * b)  / gcd(a, b);
}

/*
 *  x^e
 *  if e == 0  return 1
 *  else e % 2 == 0  return x^(2/n) * x^(2/n)
 *  else  return x^(n-1) * x
 */
template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
T powm (T base, T exp, T mod) {
    if(exp == 0) return 1;
    T u = powm(base, exp  / 2, mod);
    u = (u * u) % mod;
    if( exp % 2 == 1) {
        u = (base * u) % mod;
    }
    return u;
}

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
bool is_primitive(T base, T mod) {
    T exp = 2;
   T r = base * base;
    for(; r != base; exp++) {
        r *= base;
        r %= mod;
    }
    return exp == mod;
}

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
std::vector<T> primitive_root( T mod) {
    std::vector<T> v;
    for(T base = 2; base < mod; base++) {
        if(is_primitive(base, mod)) v.push_back(base);
    }
    return v;
}

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
std::tuple<T , T , T> extended_gcd(T a,T b) {
    if(b == 0) {
        return {1, 0, a};
    } else {
        T x, y, g;
        // ax + by = gcd(a,b) => bx'  + (a mod b)y' = gcd(a,b) => ay' + b(x' - [a/b]*y') = gcd(a,b)
        std::tie(x, y, g) = extended_gcd(b, a%b);
        return { y, x - (a/b) *y, g};
    }
}

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
bool is_prime(T n) {
    if (n < 2) return false;
    // prime range  is 2 <= sqrt(n)
    for(T i = 2; i * i <= n; i++) {
        if(n % i == 0) return false;
    }
    return true;
}

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
T next_prime(T n) {
    bool found = false;
    while(!found) {
        n++;
        if(is_prime(n))
            found = true;
    }
    return n;
}

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
T random_prime() {
    std::array<u_char , 1> arr;
    std::for_each(arr.begin(), arr.end(), [] (u_char& c) {
        std::uniform_int_distribution<> di(0, 0xff);
        std::random_device rd;
        c = di(rd);
    });
    T n = 0;
   for(int i = 0 ; i < arr.size(); i++) {
       n  |=  arr[i]  << i*8;
   }
    return next_prime(n);
}

template <typename T, typename std::enable_if<std::is_integral_v<T>>::type * =  nullptr>
T invert(T a , T mod) {
    long long  x, y , g;
    //Fermat's little theorem : x^n mod m = x^ mod(m-1)  mod m
    if(is_prime(mod)) {
        return powm(a, mod -2, mod);
    }
    std::tie(x, y, g)  = extended_gcd(a, mod);
     return (x % mod + mod) %mod;
}

RSA는 인증보다는 암호화를 위한 공유키를 교환하기 위해 사용되었다. 클라이언트는 서버의 공개키를 이용해 공유키를 암호화해 서버에 전달하면 클라이언트와 서버가 이 키를 이용해 암호화를 수행하였으나, 보안상의 취약점으로 TLS 1.3에서는 더 이상 키 교환 프로토콜로 사용되지 않고 인증을 위해서만 사용된다.