암호 알고리즘과 해시 2

앞 문서에서 대칭키 암호(symmetric-key cryptography)를 다뤘다. 이 문서는 서로 다른 두 키를 쓰는 공개키 암호(public-key cryptography)의 대표 알고리즘과, 되돌릴 수 없는 해시 함수(hash function)를 정리한다. 시험은 안전성의 근거와 해시 출력 길이를 묻는다.

공개키 알고리즘

이름	안전성의 근거
RSA(Rivest-Shamir-Adleman)	큰 수의 소인수분해가 어렵다
디피-헬먼(Diffie-Hellman)	이산대수(discrete logarithm) 문제. 키 교환용
엘가말(ElGamal)	이산대수 문제
ECC(타원 곡선 암호)	타원 곡선 위의 이산대수 문제

RSA는 MIT의 리베스트(Rivest)·샤미르(Shamir)·애들먼(Adleman)이 1977년에 공개했고 이름도 세 사람의 머리글자다. 학술지 논문은 1978년에 실려서 시험 자료에는 1978년으로 적히기도 한다. 두 소수를 곱하기는 쉽지만 곱한 결과를 다시 두 소수로 나누기는 매우 어렵다는 점을 이용한다. 디피-헬먼은 1976년에 공개키 개념과 함께 나온 키 교환 방식으로, 엿들을 수 있는 통신로에서도 두 사람이 같은 비밀 키를 나눠 갖게 해 준다. 이산대수 문제는 어떤 수를 몇 번 곱해야 원하는 값이 되는지 알아내기 매우 어려운 수학 문제이고, 디피-헬먼·엘가말·ECC가 이 어려움에 기댄다. ECC(Elliptic Curve Cryptography, 타원 곡선 암호)는 RSA보다 짧은 키로 비슷한 안전성을 낸다.

해시 함수

해시 함수(hash function)는 임의 길이의 입력을 고정 길이 값으로 바꾸는 함수다. 입력이 조금만 바뀌어도 결과가 크게 달라지고, 결과에서 원래 입력을 되돌릴 수 없다. 그래서 복호화(decryption)가 목적이 아니라 파일이 바뀌지 않았는지 확인하는 무결성(integrity) 검사와 비밀번호 저장에 쓴다.

이름	출력 길이	비고
MD5(Message Digest 5)	128비트	리베스트, 1991년, MD4 대체
SHA-1(Secure Hash Algorithm 1)	160비트	해시 충돌(hash collision)이 발견되어 폐기 권고
SHA-2(Secure Hash Algorithm 2)	224·256·384·512비트	미국 NSA 설계, 2001년 미국 NIST 발표

해시 충돌은 서로 다른 두 입력이 같은 해시 값을 내는 것으로, 이런 입력을 찾아낼 수 있으면 위조 파일도 원본과 같은 값을 내 변조를 확인할 수 없다. 이 밖에 시험에 이름으로만 나오는 해시로 HAVAL, MD4, N-Hash, SNEFRU가 있고, 이름과 해시 알고리즘의 일종이라는 점만 기억하면 된다. N-Hash는 1990년 일본 NTT 연구진이 제안한 128비트 해시로, 시험 자료에는 N-NASH로 잘못 적힌 경우가 있다. MD5는 512비트 블록 단위로 입력을 처리한다.

시험 포인트

• "큰 수를 소인수분해하기 어렵다", "MIT의 세 사람" → RSA. "이산대수", "키 교환" → 디피-헬먼.
• "짧은 키로 RSA와 비슷한 안전성" → ECC.
• "임의 길이 입력을 고정 길이 값으로" → 해시. MD5 128비트, SHA-1 160비트.
• 해시 종류: SHA 계열, HAVAL, MD4, MD5, N-Hash, SNEFRU.