Cryptography

개요
- Base64
- 오래된 암호 알고리즘
카카오 신입 공채 문제: RSA
- 풀이 예제
- 용어 정리

개요

암호학의 모든것 위키피디어를 번역했는데 내용이 아주 좋다.

RSA의 입력 길이는 n 보다 작아야 하는 제한이 있다. 2048 비트 RSA 키는 최대 245 바이트의 입력 길이 제한이 있다. 11 바이트는 패딩. “splitting”은 여러 보안 문제로 추천되지 않으며, AES와 같은 대칭 암호화 체계를 사용해 처리한 후 암호화한다.

RSA 크랙 20바이트 키를 크랙하는데 VM 리눅스 서버에서 20분 정도 걸림
SO의 잘못된 예제를 정상 동작하도록(n을 크게 하여) 수정한 매우 간단한 RSA 알고리즘 코드

z = 90
h = 107
u = 107

e = 17
d = 257
n = 377

print (z,h,u)

c_z = z ** e % n
c_h = h ** e % n
c_u = u ** e % n

print (c_z, c_h, c_u)

p_z = c_z ** d % n
p_h = c_h ** d % n
p_u = c_u ** d % n

print (p_z, p_h, p_u)

실행 결과

(90, 107, 107)
(350L, 373L, 373L)
(90L, 107L, 107L)

Base64

6비트 단위로 인코딩. 4비트가 패딩인 경우 6비트 패딩 2개 추가, 2비트가 패딩인 경우 6비트 패딩 1개만 추가. =가 패딩이다. (p91, 『스토리로 이해하는 암호화 알고리즘』, 2017)

$ echo -n 'Man' | openssl base64
TWFu
$ echo -n 'M' | openssl base64
TQ==
$ echo -n 'Ma' | openssl base64
TWE=

오래된 암호 알고리즘

시저
단어별 빈도로 해독
비즈네르
키 길이에 따라 여러개 원판 사용
아핀
곱셈, 덧셈 두 개의 암호법을 합하여 Wx+b를 모듈라 연산

카카오 신입 공채 문제: RSA

아래 문제는 카카오 신입 공채 문제 후보였으나 난이도가 너무 높아 결국 출제하지 못했다.

라이언과 어피치는 사내 커플이다.

비밀 연애를 하던 그들은 들키지 않도록 RSA 알고리즘으로 암호화한 메시지를 주고 받았는데, 오늘도 어피치는 라이언의 공개키를 이용해 아래와 같은 암호화된 숫자를 보내왔다.

공개키: (10403, 49)
암호화된 숫자: 5134

어피치의 암호화된 숫자를 받은 라이언은 복호화를 하기 위해 노트북을 열던 순간, 그만 실수로 콜라를 엎지르고 말았다. 엎지른 콜라가 노트북에 스며들면서 그 안에 저장해둔 개인키도 더 이상 알 수 없게 되었는데 …

과연 라이언은 어피치의 메시지를 해독할 수 있을까?

참고로 어피치는 사랑의 의미를 담은 네 자리 숫자를 암호화 했다고 한다. 어피치가 암호화한 네 자리 숫자는 과연 무엇일까?

RSA 알고리즘 소개

RSA는 공개키 암호시스템으로 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 둔 안전한 암호체계이다. RSA는 두 개의 키를 사용하는데, 모두에게 공개하는 공개키(public key)와 공개해선 안되는 개인키(private key)로 구성된다. 공개키는 메시지를 암호화(encrypt)할때 사용하고, 개인키는 암호화된 메시지를 복호화(decrypt)할때 사용한다.

키의 생성 과정은 아래와 같다.

p와 q라고 하는 두 개의 서로 다른(\(p \neq q\)) 소수를 고른다.
두 수를 곱하여 \(N = p\cdot{q}\)를 찾는다.
\(r = (p - 1)(q - 1)\)를 구한다.
r 보단 작고, r과 서로소인 정수 e를 찾는다.
확장된 유클리드 호제법(확장 유클리드 알고리즘)을 이용하여 \(d \times e\)를 r로 나누었을 때 나머지가 1인 정수 d를 구한다.

이제 이 값들을 이용해서 키를 만들 수 있다. 공개키는 (N, e) 이고, 개인키는 (N, d)이다.

암호화/복호화 공식은 각각 아래와 같다.

암호화: c = m^e mod N
복호화: m = c^d mod N

출처: https://hackernoon.com/how-does-rsa-work-f44918df914b

풀이 예제

공개키가 (667, 39) 라고 가정해보자. 즉, N = 667, e = 39 이다. 이제 이 키를 이용하여 숫자를 암호화해 보도록 한다. 암호화할 숫자는 99로 가정하자.

공개키: (667, 39)
입력값: 99

이제 이 값을 암호화해보자.

99^39 mod 667 = 249

암호화된 값은 249가 된다.

여기서 개인키를 알아낸다면 복호화 공식을 적용하여 쉽게 원래의 값으로 돌릴 수 있을 것이다. 즉, d 값을 알아내어 249^d mod 667 = 99를 구할 수 있을 것이다.

d 값을 찾는 방법은 N을 소인수 분해하여 소수인 두 p, q 값을 알아내면 쉽게 구할 수 있다. 물론 실제로 쓰이는 RSA 알고리즘은 N 값이 매우 크기 때문에(1024비트 RSA 알고리즘의 경우 N 값은

161521746670640296426473658228859984306663144318152681524054709078
245736590366297248377298082656939330673286493230336261991466938596
691073112968626710792148904239628873374506302653492009810626437582
587089465395941375496004739918498276676334238241465498030036586063
929902368192004233172032080188726965600617167

이다.) 수퍼 컴퓨터로도 소인수 분해를 하는게 거의 불가능하고 이것이 바로 RSA 알고리즘이 안전한 원리다. 하지만 여기서 N 값은 고작 667에 불과하므로 소인수 분해를 할 수 있는 코드를 작성하여 돌려보면 두 소수는 p = 23, q = 29 임을 금방 찾아낼 수 있다. 이 경우 r은 \((p - 1)(q - 1)\)인 \(22 \times 28 = 616\)이 된다. \(d \times e\)를 r로 나누었을때 나머지가 1인 값을 찾으면, e가 39이므로 d가 79일때 \(79 \times 39 = 3081\)이 되는데, 3081은 r의 값인 616으로 나누었을때 나머지가 1이다. 즉, d는 79 임을 알 수 있다.

이제 개인키는 아래와 같다.

개인키: (667, 79)

찾아낸 d 값을 이용해 암호화된 값 249를 복호화 해보자.

249^79 mod 667 = 99

원래의 입력값인 99가 나온다.

용어 정리

소수^{prime number}: 1과 자기 자신 외에 양의 약수가 없는, 1보다 큰 자연수
소인수 분해^{prime factorization}: 합성수를 소수의 곱으로 나타내는 방법. 소인수 분해를 일의적으로 결정하는 방법은 아직 발견되지 않았다. 현대 암호 처리에서 소인수 분해의 어려움은 중요한 기준이 된다.
확장된 유클리드 호제법^{Extended Euclidean algorithm}: 유클리드 알고리즘의 확장으로 정수 a와 b의 최대 공약수 외에도 베주 항등식^{Bézout’s identity}의 계수를 계산한다. (TODO: ‘확장된 유클리드 호제법’에 대해서는 설명을 추가하거나 이 용어를 사용하지 않고 보다 쉬운 용어로 풀이 필요. 영문 위키피디어에서는 사용하지 않음)

Last Modified: 2021/06/08 13:03:45