잉여의 생각저장소

개요

 타원곡선 암호는 줄여서 ECC는 공개키 암호화 방식 중 하나로 데이터 암호화 디지털 인증 등 현재 가장 많이 쓰이는 암호방식이다. ECC는 큰 수의 소인수 분해가 어렵다는 것에 착안해 만든 RSA 암호와 달리 이산로그문제에 착안해 만들어졌다. 때문에 256비트의 ECC키는 3072비트의 RSA키와 비슷한 암호화 레벨이며 키값이 커질수록 RSA보다 암호화 레벨이 급격하게 높아진다.

타원곡선

 먼저 타원곡선이란 아래 식을 만족하는 그래프를 뜻하며, 판별식(영어로 discriminant)이 0이 아니어야 한다.

$y^2 = x^3 + ax + b, (4a^3 + 27b^2 \neq 0)$

그래프를 그리면 위와 같이 나타나는데 이 그래프 위의 점들의 집합 G는 아래 조건들을 만족한다.

① G에 속한 임의의 점 P, Q에 대해서 P + Q 또한 G에 속한다
② (P + Q) + R = P + (Q+ R)
③ ideal point 0이 있으며 P + 0 = 0 + P = P
④ Q가 P의 역원이면 P + Q = 0
⑤ P + Q = Q + P

위 조건들 중 만약 두 점 p, q의 합을 단순히 x좌표와 y좌표의 합이라면 ① 식을 만족하지 않는다. ① 식이 만족하는 이유는 타원곡선에서 덧셈연산을 특별하게 정의하고 있기 때문인데, 아래 그림을 먼저 본다.

  위 그림처럼 타원곡선에서 두 점 P, Q의 덧셈은 두 점을 지나는 직선과 타원곡선이 만나는 또 다른 점 -R에서 수직선을 그어 타원곡선과 만나는 점 R이다. 때문에 타원곡선에서 두 점의 합은 타원곡선에서 속한 점이다. 여기서 P, Q를 지나는 직선과 만나는 또다른 점을 -R이라고 한 이유는 -R이 R의 역원이 되기 때문이다. -R과 R은 수직선으로 이 직선과 타원곡선이 만나는 또 다른 점은 없다. 즉 R + (-R) 연산은 기하학적으로 타원곡선과 만나는 점이 없으므로 0(ideal point)으로 표현한다.

 만약 같은 P를 더하면 어떻게 될까? 같은 점을 더하면 위 그림처럼 해당 점의 접선과 타원곡선이 만나는 또다른 점 -R에서 수직선을 그어 만나는 점 R이다. 이와 같이 타원곡선의 덧셈에 대한 정의로 타원곡선의 점은 스칼라 곱셈 연산도 표현 가능하다. 예를 들어 7P는 4P + 3P로 이며 4P는 2P + 2P, 3P는 2P + P 이므로 P의 덧셈연산을 거듭해서 구하다보면 P의 모든 스칼라 곱도 구할 수 있다.

 지금까지 기하학적으로 타원곡선의 덧셈연산을 살펴보았는데 대수적으로 살펴보면 어떨까?

① 타원 위의 서로 다른 두 점 P, Q의 덧셈을 구하려고 할 때

$m = \frac{y_Q  -   y_P}{x_Q   -   x_P}$

m은 두 점을 지나는 직선의 기울기이며 직선의 식은 아래와 같다.

$y = m(x - x_P) + y_P$

이를 타원곡선 식의 y값에 대입하면 아래와 같다.

$(m(x - x_P) + y_P)^2 = x^3 + ax + b$
$x^3 - m^2x^2 + ... = 0$

결국 R의 x값을 구하는 것은 위 3차 방정식의 해를 구하는 것과 같다.

여기서 우리가 이미 알고 있는 P, Q의 x값이 있고 x^3의 계수가 1이므로, 즉 x^2의 계수는 세 근의 합에 -값이 된다.

$(x - x_P)(x - x_Q)(x - x_R) = x^3 - (x_P + x_Q + x_R)x^2 + ...$

이를 먼저 기울기 m에 대해 정리한 식에 대입하면 아래와 같이 R의 x값을 구할 수 있다.

$x_P + x_Q + x_R = m^2$
$x_R = m^2 - x_P - x_Q$

R의 x값을 직선의 방정식에 대입하여 R의 y값도 계산한다.

$y_R = m(x_R - x_P) + y_P$

② 같은 점 P 2개의 덧셈을 구할 때

점 P에서 타원곡선의 접선의 기울기 m은 타원곡선의 미분방정식에 점 P를 대입한 값이므로 아래와 같다.

$m = \frac{3x_P^2  +  a}{2y_P}$

 그리고 결과 R은 같은 점을 더했으므로 Q값 대신 P값을 넣어 아래와 같이 정리할 수 있다.

$x_R = m^2 - 2x_P$
$y_R = m(x_R - x_P) + y_P$

유한체에서 타원곡선

 위에서 그래프로 나타낸 타원곡선은 무한대 실수 범위이다. 하지만 타원곡선을 이용해서 암호화에 적용하려면 유한한 자연수 범위에서 덧셈연산도 역으로 추적하기 어려워야 한다. 타원곡선암호는 모든 점들을 큰 소수 p에 대한 나머지들, 즉 𝔽p 내에 존재한다. 만약 𝔽p에서 점 P(x, y)가 타원곡선 E에 있다면 x, y는 모두 소수 p의 나머지 들이고 타원곡선 식도 mod p에서 만족하면 된다.

${x, y \in \mathbb{F}_p,\ y^2 = x^3 + ax + b\ (mod\ p)}$

 mod p에서 덧셈 연산은 접선의 기울기에서 분모의 역원을 계산할 수 있어야 한다.

${a^{-1} \equiv \ b \ (mod\ p)}$

나머지연산에서 나눗셈은 위와 같이 해당 값의 역원을 찾아서 곱셈으로 표현할 수 있다. 이는 앞서 포스팅한 RSA 암호에서 확장된 유클리드 알고리즘이나 페르마의 소정리를 참고하면 구할 수 있다. (아래 참고로 링크한 andrea corbellin blog에서는 확장된 유클리드 알고리즘을 사용하였으나 소수에 대한 나머지 연산이므로 페르마의 소정리를 사용하는 편이 더 쉬운듯 하다. 역원을 구할 때 시간 복잡도는 O(log p)로 비슷하다.)

 𝔽p에서 덧셈연산과 스칼라 곱 계산을 통해 얻은 타원곡선 위의 점들은 이산로그문제가 된다. 이를 좀 더 간단히 설명하자면

$ 2^n = 64$
${2^n \equiv 9\ (mod\ 17)}$

위에 n값는 6으로 쉽게 구할 수 있지만 mod 17에서 2의 배수 중 9가 되는 값은 일일이 계산해 보지 않는 이상 어렵다. 타원곡선 점들도 이와 같이 몇 번의 덧셈연산으로 결과 값을 구하긴 쉽지만 기준 점으로 부터 몇 번의 연산을 했는지는 구하기 매우 어렵다. 타원곡선암호란 구하기 어려운 몇 번의 덧셈을 해야하는지 위에 이산로그문제에서 지수가 되는 부분을 비밀키로 하고 그 결과가 되는 점을 개인키로 한다.

위처럼 유한체에서 타원곡선은 모든 연산을 유한한 범위의 자연수로 표현가능하고 역방향으로 추적을 어렵게 한다. 하지만 이를 바로 암호화에 사용하기에는 몇가지 검증 작업을 더 거쳐야 한다.  andrea corbellin blog에서는 아래 식을 예로 들었다.

${y^2 \equiv x^3 + 2x + 3\ (mod\ 93),\  G = (3, 6)}$

 위 타원곡선식에서 기준점 G를 이용하여 몇 번의 연산을 통해 키를 생성한다고 가정하자.

0G=0
1G=(3,6)
2G=(80,10)
3G=(80,87)
4G=(3,91)
5G=0
6G=(3,6)
7G=(80,10)
8G=(80,87)
9G=(3,91)

그리고 기준점에 대해 스칼라 곱을 순차적으로 구해보면 위와 같이 점 5개가 반복해서 나타난다. 위 타원곡선을 암호화에 사용한다면 5번의 연산만으로 사용자의 비밀키를 추적할 수 있다. 물론 암호화에서는 큰 소수를 나머지연산에 사용하겠지만 위에서 봤듯이 mod 93인데 기준점과 타원곡선에 따라 표현할 수 있는 점이 5개 밖에 나오지 않는 경우도 있다. 

이처럼 유한체에서 어떤 타원곡선이 표현할 수 있는 총 점의 수는 암호화 레벨을 결정하는 중요한 요소이다. 그리고 현재 이를 구할 수 있는 알고리즘으로 Schoof's algorithm이 있다. (이 알고리즘은 Hasse's theorem on elliptic curves과 중국인의 나머지정리를 기반으로 만들어졌는데, 아직 이해하지 못해 추후 따로 포스팅할 까 합니다. 그리고 타원곡선 표준에서는 이 알고리즘을 통해 미리 정해진 타원곡선과 기준점, 유한체의 범위를 사용하므로 새로운 타원곡선을 만들지 않는 이상 직접적으로 Schoof's algorithm을 사용할 일은 없습니다.)

키 생성

타원곡선 암호에서 키 생성을 위해 domain parameters를 정해야 한다. domain parameters는 a, b, N, n, h, G로 총 6개이다. 먼저 a, b는 타원곡선 식의 요소이고 p는 유한체 범위를 결정하는 소수이다.

그리고 a, b, p값으로 타원곡선의 총 점의 수 N값은 Schoof's algorithm을 통해 구한다. 그 뒤 기준점이 되는 G와 n, h는 아래 순서를 반복해서 구한다.

① 전체 집합 원소의 수 N에서 부분집합의 수인 n을 결정한다. (n은 소수이면서 N의 약수)
② 보조 인자(cofactor)인 h = N/n 를 구한다.
③ 타원곡선 위 임의의 점 P를 골라서 기준점 G = hP를 구한다.
④ G가 0이면 다른 P를 골라서 반복한다.

(domain parameters를 구할 때 andrea corbellin blog에서는 Lagrange's theorem을 언급하며 부분집합에 관한 부가설명이 있습니다. 이 부분도 완벽하게 이해하지 못하여 추후 설명 추가하겠습니다.)

 domain parameters를 모두 정하면 이제 공개키와 비밀키를 만들 수 있다. RSA 암호와 달리 타원곡선 암호에서는 비밀키를 먼저 정한다.

비밀키 d는 [1 ... n-1] 에서 자연수 값으로 키 생성자가 지정할 수 있다. 그리고 공개키는 타원곡선 위의 좌표 H = dG이다.

 위에서 domain parameters를 결정하는 과정은 d(비밀키)와 domain parameters로 부터 공개키를 구하는 것은 쉽지만 H(공개키)와 domain parameters로부터 비밀키를 구하는 것은 어렵게 설계되있다. 이렇게 역추적하려면 어려운 이산로그문제를 풀게 하는 것이 타원곡선암호의 핵심이다.

ECDH

 ECDH는 Diffie–Hellman key exchange을 Elliptic Curve에 적용한 방법이다. Diffie–Hellman key exchange의 핵심은 서로 통신할 두 사람이 같은 키를 공유하는 것인데 중간에 전송하는 정보를 가로채도 사용자의 비밀키를 알 수 없게 하는 데 있다.

ECDSA

작업중

참고

andrea corbellin blog (가장 ECC에 대해 자세하게 설명한 블로그)

Standards for Efficient Cryptography Group

 이 글은 SHA1의 원리와 소스코드 그리고 충돌, 취약점을 다룬다.

 (충돌 및 취약점은 정리 중 입니다. 완료되는 대로 업데이트 하겠습니다.)

개요

 암호학적 해시 함수로 데이터를 160bit의 해시 값으로 나타낸다. 해시 함수를 간단히 설명하면 서로 다른 데이터로 만든 해시 값 2개가 달라야 한다. 해시 값의 bit 수가 정해져있기 때문에 서로 다를 확률이 0일 수는 없지만, 0에 가깝도록 그리고 공격자가 같은 해시 값이 나오는 서로 다른 문서들을 만들 수 없도록 하는 것이 목적이다. NSA에서 창안하여 만들어진 함수이며 TLS, SSL, SSH, HTTP 인증서, GIT 커밋 등 많은 애플리케이션 및 프로토콜에서 사용 중이다. SHA-1은 1993년 SHA-0가 발표된 후 2년 뒤인 1995년에 취약점을 보완하여 만들었다.(아래 해시 값 생성에서 이 둘의 차이 설명) 하지만 현재 이 둘 모두 취약점 및 충돌이 발표되어 대부분 기업, 단체 등에서 SHA-2, SHA-3를 사용한다.

해시값 생성

 해시값 생성과정 및 코드는 wikipedia SHA-1_pseudocode를 c++로 구현함.

 (전체 소스코드: https://github.com/JangTaeHwan/AlgorithmTraining/blob/master/Mathematical/sha/sha1.cpp)

  ① 초기화

var = 32bit, var64 = 64bit 의미

Data m = 암호화 할 데이터,

var64 ml = m.size()*8; // m의 원래 크기, bit size로 나타냄

// SHA1의 해시 값이 되는 5개의 digest (computer science에서 digest는 output이 되는 해시 값을 의미)

// 초기 값은 아래와 같이 상수로 정해져 있으며 데이터를 읽어가면서 해시 값을 바꾸는 작업을 한다.

var h[DIGEST_NUMS] = {

    0x67452301,

    0xEFCDAB89,

    0x98BADCFE,

    0x10325476,

    0xC3D2E1F0,

};

  ② padding

// m에 '1' 비트 1개 추가 (실제론 0b10000000 추가)

m += (char)0x80;

       // m.size() + ml이 64bytes(512bit)로 나누어 떨어질 때까지 '0'비트를 계속 추가

       // input데이터가 byte단위로 나누어 떨어짐을 가정하고 모든 과정에서 byte단위로 추가 함

m += (char)0x00;

// ml을 big endian 순서로 m에 추가 (실행환경을 little endian로 가정, big endian 환경에서 실행시 0번 index부터 추가)

for (int i=7; i>=0; i--) {

   char byte = (ml >> 8*i) & 0xff;

   m += byte;

}

// 이제 m은 64bytes(512bit)로 나누어 떨어진다.

   ④ chunk를 16개의 words로 나눈다. 각각의 word는 32bit이다.

// big endian 순서로 data를 읽어온다.

for (unsigned int i = 0; i < WORDS_NUMS; i++) {

    words[i] = (chunk[4*i+3] & 0xff)

               | (chunk[4*i+2] & 0xff)<<8

               | (chunk[4*i+1] & 0xff)<<16

               | (chunk[4*i+0] & 0xff)<<24;

}

   ⑤ 16...79 index words는 아래 식에 따라 순차적으로 채운다.

var word = w[i-3] xor w[i-8] xor w[i-14] xor w[i-16];

word = BYTE_ROTATE_LEFT32(word, 1);

* 여기서 word의 bit들을 한 칸씩 왼쪽으로 옮기는데 이 부분이 SHA0과 SHA1의 차이이다.

   ⑥ main loop

// k값은 h의 초기값과 마찬가지로 정해진 상수 값이다.

var a = h[0];

var b = h[1];

var c = h[2];

var d = h[3];

var e = h[4];

var f, k;

for (unsigned int i = 0; i <= 79; i++) {

    if (0 <= i && i <= 19) {

        f = (b bitand c) bitor (~b bitand d);

        k = 0x5A827999;

    }

    else if (20 <= i && i <= 39) {

        f = b xor c xor d;

        k = 0x6ED9EBA1;

    }

    else if (40 <= i && i <= 59) {

        f = (b bitand c) bitor (b bitand d) bitor (c bitand d);

        k = 0x8F1BBCDC;

    }

    else if (60 <= i && i <= 79) {

        f = b xor c xor d;

        k = 0xCA62C1D6;

    }

    var temp = BYTE_ROTATE_LEFT32(a, 5) + f + e + k + w[i];

    e = d;

    d = c;

    c = BYTE_ROTATE_LEFT32(b, 30);

    b = a;

    a = temp;

}

   ⑦ digest 값에 ⑥에서 구한 값 더하기

h[0] = h[0] + a;

h[1] = h[1] + b;

h[2] = h[2] + c;

h[3] = h[3] + d;

h[4] = h[4] + e;

   ⑧ 최종 해시 값 hh(20bytes, 160bit)는 h[0]부터 h[4]를 나열한 값이다.

충돌

 작업 중...

RSA 암호[RSA cryptosystem]

 이 글은 RSA 암호 과정 및 증명 그리고 필요한 모든 정리를 다룬다. (유클리드 알고리즘 정리 및 증명, 페르마의 소정리, 오일러 정리)

그리고 암호 과정 전반에 필요한 소스코드(c++)를 포함한다.

개요

 공개 키 암호 방식 중 하나이며 널리 쓰이는 함호 방식이다. 대칭키 암호방식과 다르게 암호화 할 때와 복호화 할 때 사용하는 키가 다른 비대칭 암호 방식이다.

그리고 RSA 암호시스템은 일반적인 공개키 암호시스템과 다르게 공개키(public key)뿐만 아니라 개인키(private key)로 암호화하여 공개키(public key)로 복호화 할 수 있다. 

키 생성

① 서로 다르며 큰 두 소수 p, q를 고른다. 그리고 p, q에 대해 아래 값을 구한다. ( φ(n)은  오일러 피 함수이다.)

② 아래 식을 만족하는 e를 구한다. (여러 e 값들 중에서 하나 임의로 선택)

③ 아래 식을 만족하는 d를 구한다. (확장된 유클리드 알고리즘 이용)

④ 공개키는 <n, e>이며 개인키는 <n, d>이다. (p, q, φ(n) 값은 보안상 파기)

확장된 유클리드 알고리즘

 먼저 유클리드 알고리즘은 두 개의 자연수의 최대공약수를 구하는 알고리즘 중 하나다. 정의는 "두 수 a, b (b > a)의 최대공약수는 a와 r(b를 a로 나눈 나머지)의 최대공약수와 같다" 이다.

- 유클리드 알고리즘 증명

① 정의를 식으로 나타내면 아래와 같다. (gcd는 최대공약수 의미)

② gcd(a, b) = G 그리고 a = G*α, b = G*β를 만족하는 자연수 α, β에 대해 아래식으로 정리. (α와  β는 서로소)

③ 위 식을 통해 G는 r의 약수임을 확인. β-α*q가 α와 서로소임을 증명하면 gcd(a, r) = G이므로 증명 끝.

 여기서 β-α*q와 α의 최대공약수 M이 α와 β의 약수임을 알 수 있다. 그리고 α와 β는 서로소이므로 M = 1이다.

따라서  β-α*q와 α도 서로소이다.

 유클리드 알고리즘을 반복해서 이용하면 두 자연수의 최대공약수를 간단하게 구할 수 있다. 코드로 나타내면 아래와 같다.

uint32_t gcd(uint32_t a, uint32_t b) {
    if (b > a) swap(a, b);
    if (a % b == 0) return b;
    return gcd(b, a % b);
}

 위 코드는 φ(n)와 서로소인 e값 들을 구하는데 쓰이며 e*d ≡ 1 (mod φ(n))을 만족하는 d를 구하기 위해선 확장된 유클리드 알고리즘이 필요하다. 확장된 유클리드 알고리즘이란 a, b의 최대공약수를 유클리드 알고리즘을 이용하여 구할 때 반복되는 식을 정리해서 a*x + b*y = gcd(a, b)를 만족하는 정수 x, y를 구하는 것이다.

 a, b의 최대공약수를 구하는 과정은 위와 같이 표현할 수 있으며 rn이 gcd(a, b)이다. 여기서 q값 들은 각 스탭별 구할 수 있는 상수이므로 r값들은 a, b로 풀어서 표현할 수 있다.

 이렇게 보면 계산과정이 복잡해 보이지만 a, b의 계수들을 상수 s, t들로 표현해보면

 이와 같으며 이를 코드로 표현하면 다음과 같다.

// 유클리드 호제법 확장
// a*x + b*y = gcd(a, b), a < b 일 때 정수 x, y를 반환
std::pair<int64_t, int64_t> xgcd(int64_t a, int64_t b) {
    int64_t x[3] = {0, 1, 1}, y[3] = {1, 0, 0};

    while (b % a) {
        int64_t q = b / a;

        x[2] = x[0] - q*x[1];
        y[2] = y[0] - q*y[1];

        x[0] = x[1]; x[1] = x[2];
        y[0] = y[1]; y[1] = y[2];

        int64_t rest = b % a;
        b = a;
        a = rest;
    }

    return std::make_pair(x[2], y[2]);
}

// 재귀적으로 구하는 함수
std::pair<int64_t, int64_t> xgcd2(int64_t a, int64_t b) {
    if (a == 0)
        return std::make_pair(0, 1);

    auto next = xgcd2(b % a, a);

    int64_t x = next.first;
    int64_t y = next.second;

    return std::make_pair(y - (b/a)*x, x);
}

 이 코드는 키 생성과정의 e*d ≡ 1 (mod φ(n))에서 d를 구하는데 쓰인다. a*x + b*y = gcd(a, b) 에서 a는 e, b는 φ(n)이면 gcd(a, b) = gcd(e,  φ(n)) = 1 이다.

따라서 d값은 위 xgcd 함수에서 반환한 x값에서 mod φ(n)으로 나머지 연산한 값이다.

 필자는 나머지 연산에서 역원을 구하는 것이므로 오일러 정리를 이용하면 편하게 구할 수 있지 않을까 생각했었다. 하지만 오일러 정리를 이용하면 d ≡ e^(φ(φ(n))) 이 되는데 이는 φ(n)에 대한  오일러 피 함수를 구해야 함을 뜻한다. φ(n)은 (p-1)*(q-1)이고 p, q는 아주 큰 소수이므로 φ(n)은 아주 큰 두 짝수의 곱이 된다. 따라서 φ(φ(n))를 구하는 비용은 매우 커서 확장된 유클리드 알고리즘을 이용해서 d값을 구하는 편이 더 쉽다.

암호화 및 복호화 과정

 전송하려는 메시지를 특정 길이로 잘라서 정수로 표현했을 때 n보다 작은 값이 되도록 한다.

정수로 표현한 특정 메시지를 m이라 할 때 공개키 <n, e>로 암호화한 메시지 c값은 아래 식으로 구한다.

 전달받은 메시지 c는 개인키 <n, d>로 아래와 같이 복호화 한다.

 공개키 및 개인키에 포함된 n은 나머지 연산에 쓰이며 e, d는 지수로 쓰인다. 위 과정은 아래 식이 참임을 전제로 한다. (아래 RSA 증명 참고)

그리고 d를 먼저 사용하여 암호화한 메시지를 만들 수 있기 때문에 개인키로 암호화하여 공개키로 복호화가 가능하다.

// base^exp를 거듭제곱을 통해 빠르게 구하는 코드
uint64_t fastPow(uint64_t base, uint64_t exp, uint32_t mod) {
    uint64_t result = 1;

    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result*base) % mod;
        }
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return result;
}

RSA 증명

① RSA 증명은 다음 식이 참임을 증명하는 데 있다.

② d값은 아래 식으로 부터 나왔으며 따라서 e*d를  φ(n)으로 표현할 수 있다.

③ 오일러 정리에 의해 m과 n이 서로소일 때 ①번 식을 증명한다.

 사실 오일러 정리만을 이용하면 m이 p또는 q의 배수일 때 증명 못한다. 이 경우 대부분 위키에서 m이 p또는 q의 배수일 확률이 1/p + 1/q 이고 페르마의 소정리로 증명했기 때문에 넘어간다. RSA 논문에서도 페르마의 소정리를 이용하여 증명하였다.

④ 페르마의 소정리를 이용하려면 mod n을 mod p일 때 mod q일 때 나눠서 증명해야하며 이를 위해 아래 식이 성립함을 먼저 증명한다.

(이 증명의 일반화 및 자세한 내용은 중국인의 나머지 정리 참고)

if 조건에 따라 a - b는 p의 배수면서 q의 배수다. 그리고 p, q가 서로소라고 했으므로 a - b는 p*q의 배수이기도 하다.

따라서 위 조건에 따른 결과 식은 참이다. 이를 ①식에 적용하면 다음과 같다.

⑤ mod p, mod q에 대해 ①식이 참임을 증명하면 mod p*q에 대해 ①식이 참이다.

페르마의 소정리에 의해 아래 식은 참이다.

이를 적용하기 위해 ①식을 p, q에 대해 각각 정리하면

m이 mod p일 때 p의 배수이거나 mod q일 때 q의 배수일 때는 아래 식은 0이다. 따라서 모든 m에 대해 ①식은 참이다.

테스트 코드

 데이터를 특정길이로 나누고 n보다 작은 자연수로 변환하여 암호화, 복호화 과정을 진행해야 하지만 편의상 자연수를 받아서 처리하는 테스트 코드이다. (c++11 이상)

 https://github.com/JangTaeHwan/AlgorithmTraining/blob/master/Mathematical/rsa.cpp

심화

 RSA의 안정성 및 공격에 대한 글은 RSA - 리브레 위키에서 자세히 설명한다.

 이외에 필자는 공개키 하나에 개인키가 꼭 하나만 있는지 의문이 들었다. 즉 공개키를 먼저 하나 만들고 다음 만들 수 있는 개인키가 여러 개 있을 수 있다고 생각했다.

 이 가정이 맞으려면 위 식에서 특정 e에 대해 만족하는 d값이 여러 개 있어야 한다. (e와 φ(n)은 서로소)

하지만 페르마의 소정리나 오일러 정리의 증명 과정을 반복하다 보면 직관적으로 그럴 수 없다는 것을 안다.

증명과정에서 자주 등장했던 0 < i < j < φ(n) 일 때 i*e와 j*e이 mod φ(n)에서 같다고 가정하면 (j - i)*e 가 φ(n)의 배수여야 한다.

그런데 e가 φ(n)와 서로소이므로 j - i가 φ(n)의 배수여야 하지만 j-i < φ(n) 이기 때문에 j = i가 아니면 φ(n)의 배수가 아니다.

따라서 mod φ(n)에서 e*d는 모두 다른 값이 나오며 e*d ≡ 1 를 만족하는 d값은 유일하다.

 위에 따라 공개키<n, e>와 개인키<n, d>는 서로 유일하다.

마치며

 이번 포스팅은 증명해야할 것도 테스트 코드 작성 및 검증도 그리고 궁금한 점도 많아 꽤나 오래 작업했습니다. 큰 수의 소인수 분해가 어렵다는 것을 기반으로 둔 만큼 쇼어 알고리즘 등 공격 및 취약점에 관심이 있고 더 공부해보고 싶기도 합니다~ 하지만 지금은 기본적인 암호화 방식 및 수학적 알고리즘을 더 공부하고 포스팅 하겠습니다. 다음시간에는 안전한 해시 알고리즘으로 알려진 SHA에 대해 포스팅할까 합니다!