Chapter 08. 암호에 대한 이해 : 숨기고자 하는 이들의 싸움

암호의 발전사 대칭 암호화 방식 비대칭 암호화 방식 해시

고전 암호를 통해 암호의 원리를 이해한다. 대칭 암호화를 이해한다. 비대칭 암호화를 이해한다. 비대칭 암호화의 원리와 기능을 이해한다. 해시 알고리즘의 원리를 이해한다.

01 암호의 발전사 암호와 관련된 기본 용어 암호문(Cipher Text) : 비밀을 유지하기 위해 당사자끼리만 알 수 있도록 꾸민 약속 기호 평문(Plain Text) : 암호와 반대되는 말, 누구나 알 수 있게 쓴 일반적인 글 암호화(Encryption) :평문을 암호문으로 바꾸는 것 복호화(Decryption) : 암호문을 평문으로 바꾸는 것 암호화 알고리즘(Encryption Algorithm) : 암호화를 수행하거나, 복호화를 수행할 때 양쪽이 서로 알고 있어야 할 수단 암호화키(Encryption Key) : 약속한 규칙 [그림 8-1] 암호화와 복호화

01 암호의 발전사 최초의 암호 BC 480년 : 스파르타에서 추방되어 페르시아에 살던 데마라토스가 페르시아의 침략 계획 소식을 나무판에 조각 하여 적은 후 밀납을 발라 스파르타에 보낸 것 스테가노그래피(Steganography) : 실제로 전달하고자 하는 정보 자체를 숨기는 것 ‘덮다’는 뜻의 그리스어‘스테가노스(Steganos)’와 ‘쓰다’라는 뜻의 그라페인 (grapein)이 합쳐진 말 전치법 단순히 메시지에 있는 문자의 위치를 바꾸는 방법 BC 400년 : 스파르타 사람이 군사용으로 사용하던 암호화 방식도 전치법 일정 굵기의 봉에 종이를 두르고, 여기에 전달하고자 하는 문장을 쓴 뒤 종이를 풀어 다른 부대에 전달함. (이때 봉의 굵기를 함께 알려줌) 종이를 전달받은 부대는 이를 같은 굵기의 봉에 두른 후에 암호문을 읽음. 종이를 봉에 두르는 것이 암호화 알고리즘, 봉의 굵기가 암호화 키 [그림 8-2] 스파르타의 봉 암호화

01 암호의 발전사 대체법 대체법(Substitution)은 해당 글자를 다른 글자로 대체하여 암호화하는 방법 단일 치환 알파벳 한 글자를 다른 하나의 글자로 대체하는 방식으로 암호화를 수행 시저 암호 : BC 50년에 로마 시대의 줄리어스 시저(Julius Caesar)가 군사적인 목적으로 대체법을 사용 알파벳 26글자를 3자 또는 4자씩 오른쪽으로 이동시킨 뒤 해당되는 글자로 변환시켜 암호화 EHFDUHIXO IRU DVVDVVLQDWRU → BE CAREFUL FOR ASSASSINATOR(암살자를 주의하라) [그림 8-3] 알파벳을 3자씩 오른쪽으로 이동시킨 결과 [그림 8-4] 줄리어스 시저

01 암호의 발전사 대체법 단일치환 모노 알파베틱 암호 : 알파벳 26자를 각각 다른 알파벳에 대응시키는데, 규칙 없이 임의의 문자에 임의의 알 파벳을 대칭시켜 암호화함. 이렇게 만들어진 암호문은 26!(26×25×24...×2×1~4×1026)가지의 경우의 수를 가짐. 간단한 키워드나 키프레이즈(Keyphrase)를 이용해 해당 알고리즘으로 대칭표를 만들기도 함. 모노 알파베틱 예 : ASSASSINATOR라는 키워드의 대칭표 키워드에서 중복된 알파벳을 제거하면 ASINTOR. 이 단어를 앞에 놓고(), ASINTOR의 마지막 알파벳 R부터 Z까지를 뒤에 적는데 앞에 나온 알파벳은 제외(). 다시 A부터 시작해 중복된 알파벳을 제외해 끝까지 적음(). 단일 치환 암호법은 키워드를 몰라도 복호화가 가능 9세기 : 알 킨디라는 아랍의 학자가 기술한 책에 그 복호화 방법이 기록되어 있는데 빈도 분석법(Frequency Analysis)을 이용함. 빈도 분석법은 알파벳의 26자가 문장에 통계적으로 비슷한 빈도 수를 가진다는 점에서 착안한 것 [그림 8-5] ASSASSINATOR 알파벳 대칭표

01 암호의 발전사 대체법 단일치환 모노 알파베틱 암호 1995년에 출간된 옥스퍼드 영어 사전에서 각 알파벳의 빈도수를 통계낸 것을 살펴보자. 암호문에서 가장 많이 쓰인 알파벳이 T이고, 그 다음이 S, K, G라면 다음과 같은 대칭표가 만들어짐. [그림 8-6] 옥스퍼드 영어 사전(9판)의 알파벳별 빈도 수 [그림 8-7] 알파벳 빈도수별 대칭표

01 암호의 발전사 대체법 다중치환 한 글자가 암호화키와의 맵핑에 따라 여러 가지 다른 문자로 대체되어 암호화되는 방식 비즈네르 암호화 : 26×26의 알파벳 대칭표를 이용해서 암호화하고자 하는 평문과 암호화키의 맵핑을 이용하 여 암호화와 복호화를 수행하는 방식 [그림 8-9] 비즈네르 표

01 암호의 발전사 대체법 비즈네르 암호화 비즈네르 암호화의 예 : 평문은 wish to be free from myself이고, 암호화키는 secret is beautiful 비즈네르 복호화 과정 : 암호화키의 첫 번째 문자 s를 비즈네르 표의 가로 축으로 하여 O를 찾은 뒤, 세로 축 w를 찾는 방식 비즈네르 암호화 방식은 17~18세기에 널리 보급되어 사용되었음. 19세기에 찰스 배비지가 빈도 분석법을 이용해 규칙성을 찾는 방법으로 복호화 방법을 만듦. [그림 8-10] 비즈네르 암호화 예 [그림 8-10] 비즈네르 암호화 예

01 암호의 발전사 대체법 다중치환 플레이페어 암호 1854년 찰스 휘트스톤(Charles Wheatstone)이 개발 라이언 플레이페어(Lyon Playfair)를 통해 널리 알려지게 됨. 그의 이름을 따서 플레이페어 암호(Playfair cipher)라고 불림. 1차 세계대전 당시 영국 육군에서 야전 표준 시스템으로 사용 2차 세계대전에는 미 육군 및 기타 연합군에 의해 사용 플레이페어 암호화는 2개로 이뤄진 문자 쌍을 다른 문자 쌍으로 대체하는 암호화 방법 보통 정사각형 암호판 안에 영어 알파벳을 배열한 것으로 대체하여 만듦. 암호화키(ASSASSINATOR)에서 중복 문자를 제거한 문자(ASINTOR)를 5×5 정사각형에 순서대로 배열하고, 나머지 알파벳을 차례대로 배열하면 암호판이 완성 이때 5×5 암호판의 칸이 알파벳 개수(26)보다 한칸 모자라므로 I와 J 혹은 Q와 Z를 같은 칸에 넣음. [그림 8-12] 찰스 휘트스톤(좌)과 라이언 플레이페어(우) [그림 8-13] 플레이페어 암호화 테이블

01 암호의 발전사 대체법 플레이페어 암호 플레이페어 방식으로 암호화하려면 먼저 주어진 평문을 2개씩 묶은 문자 쌍으로 만들어야 함. 띄어쓰기는 무시하고 2개의 문자 쌍을 한 칸씩 차례대로 나열 이때 SS와 같이 한 쌍의 문자가 같거나 마지막에 하나 남은 문자에는 X를 추가하여 문자 쌍으로 만듦. 평문을 대체함으로써 암호문으로 만들어보자. 암호화하려는 두 문자가 서로 다른 행과 다른 열에 존재할 경우(BE), 암호 문자는 B와 E의 행과 열이 만나 는 곳에 위치한 G(B의 같은 열)와 O(E의 같은 열)이다. [그림 8-14] 플레이페어 방식으로 암호문 만들기

01 암호의 발전사 대체법 플레이페어 암호 LF와 같이 두 문자가 같은 열에 있다면 대체되는 암호문은 각각 아래쪽에 있는 문자이다. 문자 L은 V, 문자 F는 L에 대체되며 맨 아래쪽 문자일 경우에는 같은 열 맨 위의 문자로 대체됨. OR과 같이 두 문자가 같은 행에 있다면 대체되는 암호문은 각각 오른쪽에 있는 문자이다. 문자 O는 R, 문자 R은 B에 대체되고 맨 오른쪽 문자일 경우에는 같은 행 맨 왼쪽 문자로 대체됨.

01 암호의 발전사 대체법 플레이페어 방식 , , 의 규칙에 따라 각 문자열을 암호화한 결과 암호화한 플레이페어 암호화를 복호하하는 방법 암호화할 때 사용한 암호판을 이용하여 , ,  규칙의 반대(위쪽, 왼쪽)의 문자로 대체하면 됨. [그림 8-15] 플레이페어 방식의 암호화 결과

02 대칭 암호화 방식 암호학적 강도를 높일 때는 혼돈(Confusion)과 확산(Diffusion)을 이용 DES 알고리즘 혼돈 : 암호문의 통계적 성질과 평문의 통계적 성질의 관계를 난해하게 만드는 성질 확산 : 각각의 평문 비트와 키 비트가 암호문의 모든 비트에 영향을 주는 성질 DES 알고리즘 1972년 미 상무부의 NBS(National Bureau of Standards, 후에 NIST가 된다)에서 보안 문제가 대두됨에 따라 정 보보호를 목적으로 공모한 암호 알고리즘. IBM의 바터 투흐만(Water Tuchman)과 칼 마이어(Carl Meyer)가 개발 1977년 1월 NIST에 의해 암호화 표준으로 결정 64비트의 블록 암호화 알고리즘이며, 56비트 크기의 암호화 키로 암호화됨. 생성 가능한 암호화 키는 최대 256(약 7200조)가지 암호화는 다음 두 가지 기본 변환을 통해 이루어짐. 하나의 블록인 64비트를 L1(32비트)과 R1(32비트)으로 나눔. R1을 암호화 키로 생성한 S-Box로 f 함수를 만들어 치환 작업을 한 후 이 값을 L1과 XOR한 다음 L2와 R2의 위치를 바꿈.

02 대칭 암호화 방식 DES 알고리즘 암호화 과정 한 단계를 라운드(Round)라 표현 혼돈이 이 과정에서 이루어짐. 복호화는 암호화의 반대로 수행 [그림 8-16] DES 암호화 과정 [그림 8-17] DES 복호화 과정

02 대칭 암호화 방식 DES 알고리즘 S-Box에 넣기 전에 일종의 확장 과정을 거침. 1100은 3(0011)으로 암호화됨. DES는 DC(Differential Cryptoanalysis), LC(Linear Cryptoanalysis), DES challenge 등의 공격으로 1999년에 4개 월 동안 분산 환경에서 병렬 처리로 복호화하는 데 성공 1998년에는 전용 칩을 이용하여 56시간 만에, 1999년에는 전용 칩과 10만 대의 PC를 이용하여 22시간 만에 복 호화하는 데 성공 1998년 11월 이후부터는 미 정부에서 사용을 중단 [그림 8-18] DES 암호화 알고리즘의 확장 과정 [그림 8-19] DES의 S-BOXㅋ

02 대칭 암호화 방식 트리플 DES 알고리즘 DES의 복호화가 가능해짐에 따라 AES가 나오기 전까지 임시로 사용한 암호화 알고리즘 암호화 및 복호화 과정에서 2개의 암호화키를 이용 [그림 8-20] 트리플 DES 암호화 및 복호화 과정

02 대칭 암호화 방식 AES 알고리즘 SEED 알고리즘 ARIA 알고리즘 NIST는 1997년 암호화 알고리즘을 다시 공모. 공모 조건은 앞으로 30년 정도 사용할 수 있는 안정성, 128비트 암호화 블록, 다양한 키의 길이. 1997년 9월부터 1998년 4월까지 알고리즘 공모를 받았으며 12개국에서 총 15개의 알고리즘이 제안됨. 1998년 8월까지 1차 예선 평가가 이루어져 구현상의 문제점을 검증 1999년 3월까지 효율성 평가를 거쳐 미국의 MARS, RC6, Twofish, 벨기에의 Rijndael, 영국/이스라엘/덴마크 의 합작인 Serpent가 결선 알고리즘으로 선정. 결선에서는 공개적으로 암호학적 안전성 분석을 하였는데 리즈멘(Rijmen)과 대먼(Daemen)의 Rijndael 알고리 즘이 2000년 10월 최종 AES(Advanced Encryption Standard)로 선정. SEED 알고리즘 전자상거래, 금융, 무선통신 등에서 전송되는 개인정보와 같은 중요한 정보를 보호하기 위해, 1999년 2월 한국 인터넷진흥원과 국내 암호전문가들이 순수 국내기술로 개발한 128비트 블록의 암호 알고리즘 ARIA 알고리즘 전자정부 구현 등으로 다양한 환경에 적합한 암호화 알고리즘이 필요함에 따라 국가보안기술 연구소(NSRI) 주 도로 학계, 국가정보원 등의 암호전문가들이 힘을 모아 개발한 국가 암호화 알고리즘 ARIA 알고리즘은 경량 환경 및 하드웨어에서의 효율성 향상을 위해 개발된 128비트 블록 암호 알고리즘 2004년에 국가표준기본법에 의거하고 지식경제부에 의해 국가표준(KS)으로 지정

02 대칭 암호화 방식 기타 대칭형 알고리즘 IDEA 1990년 : ETH(Eidgenossische Technische Hochschule)의 라이(Lai)와 매시(Massey)가 제안한 PES(Proposed Encryption Standard)가 발표됨. 1991년 : 이를 개선해 IPES(Improved PES)라는 이름으로 다시 발표됨. 1992년 : IDEA(International Data Encryption Standard)로 이름이 바뀜. IDEA는 128비트의 키를 사용해 64비트의 평문을 8라운드를 거쳐 64비트의 암호문을 생성 모든 연산이 16비트 단위로 이루어지도록 하여 16비트 프로세서에서 구현이 용이 주로 키 교환에 쓰임. RC5 1994년 미국 RSA 연구소의 리베스트(Rivest)가 개발한 입출력, 키, 라운드 수가 가변인 블록 알고리즘 RC5(Ron’s Code 5)는 32/64/128비트의 키를 가짐. 속도는 DES의 10배 Skipjack 미 국가안보국(NSA)에서 개발한 Clipper 칩에 내장되는 블록 알고리즘 알고리즘의 형태와 구조를 비밀로 유지하다가 1998년에 공개됨 소프트웨어로 구현되는 것을 막고자 Fortezza Card에 칩 형태로 구현됨. 전화기와 같이 음성을 암호화하는 데 주로 사용 64비트의 입출력, 80비트의 키, 총 32라운드를 가짐.

03 비대칭 암호화 방식 등장 배경 비대칭 암호화 방식의 발견 대칭 암호화 방식으로는 암호화 키 교환의 문제를 해결할 수 없었음. 이를 위해 비대칭 암호화 방식이 연구됨. 비대칭 암호화 방식의 발견 1974년부터 암호 전달 문제를 연구하기 시작 1975년 디피는 비대칭키라 부르는 개념을 집에서 콜라를 가지러 아래층으로 내려가던 중에 떠올림. [그림 8-21] 위트필드 디피(좌)와 마틴 헬만(우)

03 비대칭 암호화 방식 비대칭 암호화 방식의 발견 공개된 정보가 3이라 가정 같은 키를 공유하기 위해 철수는 자신이 정한 숫자 5를 사용해 3인 243이라는 수를 영희에게 보냄. 영희도 자신의 숫자를 7로 정하고, 3인 2,178을 철수에게 보냄. 철수와 영희는 상대에게 받은 수에 자신의 수를 제곱승. 둘은 자신이 정한 5와 7 숫자를 상대방에게 전달하지 않고서도 50,031,545,098,999,707 이라는 같은 키를 공유 하게 됨. [그림 8-22] 키 공유에 관한 기본 아이디어

03 비대칭 암호화 방식 RSA 알고리즘 MIT의 로널드 리베스트(Ronald Rivest), 아디 샤미르(Adi Shamir), 레오나르도 애들먼(Leonard Adleman)이 고안 RSA 암호는 소수(素數)를 이용 RSA 암호의 아이디어는 중요 정보를 두 개의 소수로 표현한 후, 두 소수의 곱을 힌트와 함께 전송해 암호로 사용하는 것 RSA 알고리즘에서는 모든 사람이 고유한N값을 갖게 됨. (N은 두 소수의 곱) 만약 영희가 자신의 N을 p=17,159와 q=10,247의 곱인 N=17,159*10,247=175,828,273으로 정함. 영희가 자신의 N값을 모든 사람들에게 공개하면 이 때의 N 값은 영희의 공개키가 됨. 영희에게 메시지를 보내고 싶은 사람은 N 값을 찾아 어떤 알고리즘을 통해 암호화를 한 후 영희에게 보냄. 여기에서 p와 q는 영희의 사설키 [그림 8-23] 리베스토, 샤미르, 애들먼(과거 모습(좌) 현재 모습(우))

03 비대칭 암호화 방식 RSA 알고리즘 리베스트, 샤미르, 애들먼은 1977년 8월에 미국의 과학잡지인 사이언티픽 아메리칸(Scientific American)에 129 자리인 N의 소인수 p와 q를 찾아보라는 퀴즈를 냄. N=114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,362,562,561,842,935,706,935,245,73 3,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541 잡지에 실린 지 17년 만인 1994년 4월 26일에 600명의 지원자로 이루어진 팀이 p와 q 값을 발견 p=3,490,529,510,847,650,949,147,849,619,903,898,133,417,764,638,493,387,843,990,820,577 q=32,769,132,993,266,709,549,961,988,190,834,461,413,177,642,967,992,942,539,798,288,533 현재 사용되는 250자리 RSA 암호는 복호화하는 데 우주의 나이만큼 소요됨.

03 비대칭 암호화 방식 비대칭 암호화의 구조 각 개인이 공개키(Public Key)와 개인키(Private Key)를 소유하는 구조 비대칭 암호화 알고리즘에서는 언제나 한 쌍의 개인키와 공개키에 의해 암호화와 복호화가 이루어짐. 철수의 개인키로 암호화된 메시지는 철수의 개인키로 복호화되지 않고, 오직 철수의 공개키로 복호화됨. 반대로 철수의 공개키로 암호화를 먼저 수행할 수도 있으며, 이런 경우 복호화는 철수의 개인키로만 가능 [그림 8-24] 각자 소유하고 있는 공개키와 개인키 [그림 8-25] 개인키와 공개키의 관계 1 [그림 8-26] 개인키와 공개키의 관계 2

03 비대칭 암호화 방식 비대칭 암호화의 기능 기밀성 비대칭 암호화 알고리즘의 가장 기본적인 기능은 기밀성(Confidentiality) 철수는 전화번호부에서 전화번호를 찾듯이 영희의 공개키(Public Key)를 구함 이 공개키를 이용해 편지를 암호화해서 보내면 영희는 자신이 가진 사설키(Private Key)를 이용해 철수의 편지를 복 호화하여 읽을 수 있음. [그림 8-27] 기밀성 확보를 위해 공개키를 이용해 암호화하기

03 비대칭 암호화 방식 비대칭 암호화의 기능 부인 방지 철수는 영희에게 편지를 보낼 때 자신의 개인키로 편지를 암호화하여 전송. 철수의 개인키로 암호화된 편지는 철수의 공개키로만 열 수 있으므로 영희는 그 편지가 철수가 쓴 것임을 확 신할 수 있음. [그림 8-28] 부인 방지 기능 확보를 위해 개인키를 이용해 암호화하기

04 해시 해시의 정의 해시의 특징 하나의 문자열을, 이를 상징하는 더 짧은 길이의 값이나 키로 변환하는 것 세 평문은 길이가 다르지만 해시 결과는 32개의 문자로 길이가 모두 같음. 또한 둘째와 세째 평문은 단어 하나만 다를 뿐인데 해시 결과가 완전히 다름. 이와 같은 결과는 해시값을 통해 해시되기 전의 값을 추측하는 것이 불가능하게 하는 해시의 특성 때문임. [그림 8-29] 각 평문에 대한 MD5 해시값

04 해시 해시의 특징 MD5 32개의 16진수로 이루어졌음. 16³² = 340,282,366,920,938,463,463,374,607,431,768,211,456 개의 결과값이 존재 이 수는 충분히 커 보이지만 무한은 아님. 따라서 다른 데이터를 입력해도 해시 결과값이 같을 수 있음. 이를 충돌(Collision)이라 함. 충돌이 자주 일어나는 해시는 좋은 해시가 아님.

04 해시 해시의 역할 해시를 통해 0010이라는 라벨 값을 부여받아 해당 철수의 데이터로 직접 접근이 가능. 이렇게 구현된 데이터베이스 탐색 로직은 모든 참조값에 대해 데이터 반환 시간이 균일하고 순차 탐색보다 속도가 훨씬 빠름. 보안에서는 해시를 무결성 확인을 위한 알고리즘으로 사용 무결성 :오직 허가된 사람들에게만 정보가 개방되고, 그들에 의해서만 수정될 수 있음을 보장한다는 의미 [그림 8-30] 데이터베이스에서의 해시값을 통한 값의 참조

04 해시 해시의 역할 윈도우용 해시값 생성 툴인 md5.exe를 사용해 직접 MD5 해시를 생성하고 확인해보자. 먼저 다음과 같이 간단한 텍스트 파일(md5.txt)을 만든다. md5.exe를 이용해 이 값에 대한 해시값을 다음과 같이 3번 구해보니 모두 같음. md5.txt의 내용에서 조금만 바꿔도 다음과 같이 완전히 다른 해시값이 나옴. [그림 8-31] 해시값 테스트를 위한 임시 텍스트 파일 생성 [그림 8-32] 해시값 생성 실험 [그림 8-33] f 문자 추가 후 해시값 생성 실험

04 해시 해시의 종류 MD 알고리즘 MD(Message Digest function 95) 알고리즘에는 MD2, MD4, MD5 이렇게 세 가지가 있음. RSA를 개발한 미국 MIT의 로널드 리베스트 교수가 공개키 기반 구조를 만들기 위해 RSA와 함께 개발 1989년에 만들어진 MD2는 8비트 컴퓨터에 최적화되어 있고, MD4(1990년 개발)와 MD5(1991년 개발)는 32 비트 컴퓨터에 최적화되어 있음. MD5 알고리즘은 MD4의 확장판으로, MD4보다 속도가 빠르지는 않지만 데이터 보안성에 있어 더 많은 확신 을 제공 SHA 알고리즘 SHA(Secure Hash Algorithm) 알고리즘은 미국 NSA에 의해 만들어짐. 160비트의 값을 생성하는 해시 함수로, MD4가 발전한 형태 MD5보다 조금 느리지만 좀더 안전한 것으로 알려져 있음. SHA에 입력하는 데이터는 512비트 크기의 블록 SHA 알고리즘은 크게 SHA-1과 SHA-2로 나눌 수 있음(SHA-256, 384, 512는 SHA-2에 속한다). [표 8-1] SHA 알고리즘의 종류와 특징 알고리즘 메시지 문자 크기 블록 크기 해시 결과값 길이 해시 강도 SHA-1 ＜ 2⁴ 512비트 160비트 0.625 SHA-256 256비트 1 SHA-384 ＜ 2¹² 1024비트 384비트 1.5 SHA-512 2

04 해시 해시의 종류 알고리즘의 동작 원리 [그림 8-34] SHA 알고리즘의 동작