잉여의 생각저장소

 이 글은 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에 대해 포스팅할까 합니다!

정의

페르마의 소정리를 일반화 한 것이다.

임의의 자연수 a, n이 서로소일 때 아래 식을 만족한다.

여기서 φ(n)은 오일러의 피 함수라 하며 1 부터 n까지의 자연수 중에 n과 서로소인 것의 개수를 나타내는 함수이다.

증명

오일러 정리 증명 과정은 이전에 포스팅 한 페르마의 소정리의 증명과 유사하다.

① 아래 집합 S는 n이하 자연수에서 n과 서로소인 수들의 집합이다.

심화

오일러 정리 증명과정이 페르마의 소정리의 증명과 유사하여 왜 굳이 φ(n) 오일러의 피 함수가 필요한지 의문이 들 수 있다.

실제로 φ(n)은 n이 소수가 아니면 계산량이 많아 나머지 연산에서 n이 소수일 때가 많다.

그럼 모든 자연수 a, n이 서로소일 때 페르마의 소정리의 식을 증명하도록 유도해보자.

① 아래 집합 S는 n보다 작은 자연수들의 집합이다.

③ 페르마의 소정리의 증명 ①을 통해 S = AS 이다.

④ 두 집합의 곱이 합동이다. (여기까지는 오일러 정리와 같으며 참이다.)

⑤ 1 ~ n-1 중 n과 서로소가 아닌 수는 나눌 수 없다.

모든 정수 a, b에 대해 a*c ≡ b*c (mod n) 일 때 a ≡ b (mod n)을 만족하려면 n과 c가 서로소여야 한다.

a*c ≡ b*c, (a-b)*c ≡ 0 (mod n) 이다. 이 때 c가 n과 서로소가 아닌 n의 약수라면 a-b가 n의 다른 약수일 때

(a-b)*c ≡ 0 (mod n) 이 식은 만족한다.

예를 들어 4*2 ≡ 1*2 (mod 6)은 만족하지만 4 ≡ 1 (mod 6)은 아니다.

위 과정을 통해 mod n에서 n이 소수가 아닐 때 페르마의 소정리 식이 만족하지 않으며 φ(n)을 계산해야하는 이유를 알 수 있다.

그리고 n이 소수일 때 n보다 작은 모든 자연수는 n과 서로소이므로 φ(n) = n-1이다.

rsa 암호에서 쓰이는 소수들의 곱으로 나머지 연산을 하는 경우, 서로 다른 소수 p, q에 대해 φ(p*q) = (p-1)*(q-1) 로 응용해서 쓸 수도 있다.

응용

큰 지수 제곱을 나머지 연산에서 구하는 문제를 쉽게 풀 수 있다.

마치며

 이번시간에는 페르마의 소정리와 오일러 정리가 어떻게 다른지 오일러 피 함수가 왜 필요한지를 말씀드렸습니다.

다음시간에는 조합론에서 이용되는 뤼카의 정리를 포스팅할 까 합니다~