암호 이야기 - 보이지 않는 전쟁 -

차 례 1. 암호란 무엇인가: 비밀정보의 교환 수단 2. 고전암호 2-1. 제1세대 암호: 이동암호, 대치암호 등… 1. 암호란 무엇인가: 비밀정보의 교환 수단 2. 고전암호 2-1. 제1세대 암호: 이동암호, 대치암호 등… 2-2. 제2세대 암호: 기계암호 3. 현대암호 (제3세대 암호) 3-1. 비밀키 암호체계: 암호화 키(비밀) = 복호화 키 (비밀) 3-2. 공개키 암호체계: 암호화 키(공개) ≠ 복호화 키 (비밀) 3-3. RSA 암호체계: Rivest, Shamir, Adleman 3-4. 암호분석: 수학이론을 이용하여 효용성과 안전성 연구 3-5. 암호의 응용 4. 끝맺는 말: 정보속국 = 21세기형 식민지

1. 암호란 무엇인가? 비밀정보의 교환을 위해 생겨남 정보화시대 : 정보의 관리, 보호의 중요성 증대 암호(暗號, cryptography) 비밀정보의 교환을 위해 생겨남 처음에는 군사용으로 주로 사용 현재 전자상거래, 전자우편, 무선통신 등에 널리 쓰임 정보화시대 : 정보의 관리, 보호의 중요성 증대 국가, 회사, 단체, 개인 암호체계의 효용성 및 안전성 분석 고급 수학이론에 기반

암호의 개념도 정보원군 송신자양 암호문 복호화 과정 평문 암호화 과정 평문 도청자씨 암호문을 도청한 도청자씨가 송신자양과 정보원군이 주고 받은 평문의 내용을 쉽게알아낼 수 없도록 고안하는 것이 중요하며 경비도 저렴하고 사용이 편리하며 오류도 적어야 함

2. 고전암호 2-1. 제1세대 암호 - 고대 그리스 ~ 19세기 말 2-2. 제2세대 암호 - 20세기 전반부 (전신의 발명 ~ 제2차 세계대전 이전) * 현대암호 (제3세대 암호) - 제2차 세계대전 종전 이후 ~ 현재

2-1. 제1세대 암호 이동암호 (shift cipher) 아핀 암호 (affine cipher) B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 이동암호 (shift cipher) 0, 1, 2, ···, 25을 정해진 수만큼 26을 법으로 더하여 암호화 예) 3만큼 이동 (케사르 암호): cryptography → fubswrjudskb 아핀 암호 (affine cipher) 두 정수 a,b를 선택한 후, 평문 m을 c≡am+b (mod 26)로 암호화 (단 a는 26과 서로 소) a가 26과 서로 소이므로 da≡1 (mod 26)인 d가 존재 암호문 c를 d(c-b) ≡ d(am) ≡ (da)m ≡ m (mod 26)으로 복호화 예) a=1, b=3이면 케사르 암호

대치암호(substitution cipher) A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 대치암호(substitution cipher) 임의로 뒤섞은 순열을 하나 선택한 후, 이 순열을 이용하여 암호화 예) 0→25, 1→24, … , 24→1, 25→0 cryptography → xibkgltizksb 이 예는 a=-1, b=25인 아핀 암호 이동암호 ⊂ 아핀 암호 ⊂ 대치암호

셜록홈즈의 춤추는 인형 “come here at once.” 위: 셜록홈즈의 의뢰받은 암호메세지 아래: 암호를 간파한 홈즈가 다시 범인에게 보낸 암호문 가장 자주 나오는 모양: e 깃발 : 단어마다 끝 철자 “come here at once.”

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 비게네르 암호 (Vigenere cipher) 암호화 키를 선택: 키 = (5,22,3,14) 평문: (crypto) = (2,17,24,15,19,14) 암호화: (2,17,24,15,19,14) + (5,22,3,14,5,22) ≡ (7,13,1,3,24,10) = (hnbdyk) 복호화: (7,13,1,3,24,10) - (5,22,3,14,5,22) ≡ (2,17,24,15,19,14) = (crypto)

2-2. 제2세대 암호 제2세대 암호의 특징 - 전신의 등장과 1차 세계대전의 영향으로 크게 발전 독일과 일본의 암호를 해독하는데 성공: 제2차 세계대전에서 연합군이 승리한 가장 중요한 요인 중의 하나 수학적으로도 약간 진보 긴 블록을 암호화 할 수 있는 복잡한 기계들을 사용함으로써 해독에 엄청난 계산이 필요하도록 한 점이 특징 (기계암호) 컴퓨터의 출현과 함께 무용지물이 됨

기계암호 기계암호에 쓰인 대표적인 기계 Enigma - 독일의 Enigma Colossus - 영국의 Colossus Hagelin - 스위스의 Hagelin

Enigma에 얽힌 이야기 1 기본원리: 영문 알파벳 26자를 다른 26자로 바꾸도록 설계된 전기회로를 내장한 원통을 여러 개 붙여 놓은 것으로 맨 앞의 원통은 입력단자에 연결시키고 맨 끝의 원통에는 출력단자에 연결시킴 (각 원통은 회전 가능) → 계속 변형 발전됨 미국의 Hebern(1915) 네덜란드의 Koch(1919) → 독일의 Scherbius (Enigma) 스웨덴의 Damm(1919) → Hagelin (주식회사 “Crypto”) Haglin은 한국전에서도 사용됨 Enigma는 반사바퀴를 넣어 암호화와 복호화를 같은 기계로 할 수 있으며, 같은 철자는 같은 철자로 암호화되지 못하는 등의 장점이자 약점을 가지고 있었음

3. 현대암호 (제3세대 암호) 제2차 세계대전 종전 이후 고급 수학이론의 활용 민수용 암호의 등장 샤논(Shannon)의 이론 (“통신의 수학적 이론”) 컴퓨터의 발달 고급 수학이론의 활용 민수용 암호의 등장

현대암호의 특징 기밀성(secrecy) 혹은 안전성(security) 효율성(efficiency) 무결성(integrity) 인증(authentication) 부인봉쇄(non-repudiation)

현대암호의 분류 비밀키 암호 (대칭키 암호) - 블록 암호 - 스트림 암호 비밀키 암호 (대칭키 암호) - 블록 암호 - 스트림 암호 공개키 암호 (비대칭키 암호, PKC) - RSA (Rivest, Shamir, Adleman) - ECC(Elliptic Curve Cryptosystem) - NTRU, XTR 등

= 3-1. 비밀키 암호체계 개념도 f f ( 사전에 공유 ) 암호화 키 : k 복호화 키 : k 비밀키 비밀키 - 1 k 정보원군 송신자양 암호문 평문 암호 알고리즘 k f 복호 알고리즘 1 - k f 평문

블록 암호 긴 평문을 일정한 길이의 블록으로 나누어 블록단위 암호화하는 방식 긴 평문을 일정한 길이의 블록으로 나누어 블록단위 암호화하는 방식 DES (Data Encryption Standard) 1976년 미 국가 표준국(NIST) 주도하에 설계됨 64비트 단위로 암호화; 키의 길이=56비트 AES (Advanced Encryption Standard) 1997년부터 진행, 2001년 Rijndael이 채택됨 128비트 단위로 암호화; 키의 길이=128비트(이상)

DES의 기본 구조 (16라운드 Feistel 구조) f f 입 력 L1 R1 K1 L2 R2 K2 14-more rounds . 14-more rounds L16 R16 출 력

스트림 암호 평문을 1비트(bit) 단위로 암호화하는 방식 키를 키스트림 생성기라는 알고리즘에 입력하여 발생되는 1비트 키의 무한수열로 평문을 암호화 블록 단위로 사용하기도 함

스트림 암호 전송 : Key (Seed) 평문 : 0 1 0 0 1 0 1 1 0 0 0 1… 키스트림 생성기 키스트림 : 1 1 0 1 0 1 1 0 0 1 0 1… 암호문 : 1 0 0 1 1 1 0 1 0 1 0 0… 전송 암호문 : 1 0 0 1 1 1 0 1 0 1 0 0… : Key (Seed) 키스트림 생성기 키스트림 : 1 1 0 1 0 1 1 0 0 1 0 1… 평문 : 0 1 0 0 1 0 1 1 0 0 0 1…

3-2. 공개키 암호체계 개념도 f 암호화 키 : e 복호화 키 : d 수신자의 공개키 수신자의 비밀키 정보원군 송신자양 암호문 평문 암호 알고리즘 e f 복호 알고리즘 평문

3-3. RSA 암호체계 1978년 Rivest, Shamir, Adleman에 의해 고안된 암호체계로서 가장 널리 쓰이는 공개키 암호체계 소인수분해의 어려움에 기반 (n=pq, p,q는 소수) 공개키 암호체계에서는 다수의 사용자가 허용됨 easy d를 알면 쉽고 d를 모르면 어렵다 함정(trapdoor)함수

p,q를 모르면 j(n)을 모르고, j(n)을 모르면 d를 계산할 수 없다. RSA의 키 생성 n=pq 계산 (p, q : 소수) p=19, q=23, n=437 j(n)=(p-1)(q-1) 계산 (n과 서로소인 정수의 개수) j(n)=18ⅹ22=396 j(n)과 서로 소인 e 선택 e=13 ed=1(mod j(n)) 을 만족하는 d 계산 d=61 공개키 : (n,e) 비밀키 : d 공개키:(437,13) 비밀키:61 p,q를 모르면 j(n)을 모르고, j(n)을 모르면 d를 계산할 수 없다.

RSA의 암호화 및 복호화 m = 123 = 긴급탈출 공개키 : (437,13) 비밀키 : 61 386 암호화 복호화 송신자양 정보원군 386 암호화 복호화 123 = 긴급탈출

RSA의 암호화 및 복호화 386 자기야 ! 긴급탈출-OK ? 긴급탈출-OK ! 고마워 ! 공개키 : (437,13) 도청자씨 송신자양 정보원군 386 도청자씨

RSA의 서명기능 공개키 : (437,13) 비밀키 : 61 123 서명 (sign) 서명 확인 386 = 송신자 송신자양 정보원군 123 서명 확인 서명 (sign) 386 = 송신자

소수판정 ㆍ소수의 판정은 RSA 암호체계를 만들기 위해 필요 2, 3, 5, 7, 11, 13, 19, 23, 29, …, , , … ㆍ많은 수학자들의 노력으로 효과적인 소수판정법들이 실용화되어서 100자리 수를 판정하는데 약 45초 200자리 수는 약 6분 정도 소요 (확률적인 방법)

소인수분해 ㆍ소인수분해 주어진 수의 제곱근 보다 작은 모든 양의 정수로 차례로 나누어 보는 방법으로는 1초에 백만 번의 계산을 할 수 있는 컴퓨터로 30 자리 수 -1일; 40 자리 수 -100만년; 50 자리 수 -우주의 역사보다도 긴 시간이 필요! 현재까지 알려 진 가장 빠른 방법: 75자리 수는 한 달; 100자리 수는 백년 정도가 소요 RSA 암호체계: 소수판정은 빨리 할 수 있지만 소인수분해는 많은 시간이 걸린다는 사실을 이용

3-4. 암호분석 암호해독이란?

암호해독

암호해독

암호해독 암호해독이란 주어진 암호문에 대하여 여러 가지 단편적인 정보들을 토대로 평문을 복원하는 작업 암호해독이란 주어진 암호문에 대하여 여러 가지 단편적인 정보들을 토대로 평문을 복원하는 작업 암호분석(Cryptanalysis) 암호의 해독 뿐만 아니라, 암호체계의 안전성을 검증함으로써 새로운 암호체계 개발에 핵심적인 역할을 함 암호의 안전성 컴퓨터의 능력, 시간, 비용 등을 감안할 때 현실적으로 주어진 시간 내에 그 해독 방법을 알아내기가 불가능할 때 암호체계가 안전하다고 판단함

안전성 공격 패턴에 따른 분류 - 선택 암호문 공격(Chosen Ciphertext Attack-CCA1)에 대한 안전성 - 선택 평문 공격(Chosen Plaintext Attack-CPA)에 대한 안전성 - 선택 암호문 공격(Chosen Ciphertext Attack-CCA1)에 대한 안전성 - 적응선택 암호문 공격(Adaptively Chosen Ciphertext Attack-CCA2)에 대한 안전성 공격 목적에 따른 분류 - 구별불능(indistinguishability-IND) 안전성 - 변조불능(nonmalleability-NM) 안전성

3-5. 암호의 응용 은행 비밀번호 전자화폐, 전자투표 전자경매, 입찰(Electronic Auction, Bid) 영지식증명(Zero-Knowledge Proof) 다자간계산(Multi-Party Computation) …

은행 비밀번호 고객이 계좌를 개설할 때 비밀번호를 지정하면 고객의 비밀번호를 RSA암호체계로 암호화한 값만 계좌번호와 함께 보관하고 비밀번호는 삭제 고객이 예금인출을 원할 때, 비밀번호를 제시하면 같은 방법으로 암호화하여 기존에 계좌번호와 함께 기록되어 있는 값과 일치하면 인출 이 과정이 없으면 인출 불가. 즉, 비밀번호의 암호화 과정을 생략한 채 은행에 보관된 암호화된 값만 제시해서는 인출이 불가하므로 안전 암호화된 값만으로 비밀번호를 아는 것은 매우 어려움...

전자화폐 전자화폐의 구성 은행 구매자 상점 전자화폐의 요구조건 발행단계 결제단계 지불단계 전자화폐의 요구조건 안전성, 비밀성(privacy), 이중사용 금지, 양도성, 분할성 off-line 사용, …

스마트 카드 신용카드와 같은 크기, 두께의 플라스틱 카드 마이크로프로세서, 주변회로, 기억장치(ROM), 보안 알고리즘 기능을 갖춘 마이크로 컴퓨터를 Chip On Board의 형태로 내장 보안성, 다목적성, 휴대성, 사용의 편리성 스마트 카드 = 현금

전자투표 집계 결과

전자투표 전자투표 시스템의 요구조건? 투표자인증, 이중투표방지, 비밀유지, 투표결과 변조방지 집계 결과 전자투표 시스템의 요구조건? 투표자인증, 이중투표방지, 비밀유지, 투표결과 변조방지 정확하고 신뢰할 수 있는 집계, 선거방해 저지

전자 입찰과 경매, ZKP와 MPC, … 전자경매 또는 전자입찰(Electronic Auction or Bid) 구매자가 구매가를 암호화하여 접수하고 모든 접수가 완료된 후 경매자가 구매자들의 협조를 얻어 복호화. 구매자가 구매가를 조작할 수 없도록 함 영지식증명(Zero-Knowledge Proof) 내가 알고 있는 어떤 중요한 정보에 대하여 그 내용에 관한 것은 일체 알려 주지 않으면서 내가 그 정보를 알고 있음을 상대방에게 증명해 보이는 방법 다자간계산(Multi Party Computation) 다수의 사용자가 각각 자신만이 아는 정보를 소유한 상태에서 각자의 정보는 노출시키지 않고 모두에게 필요한 새로운 정보를 계산하여 공유하는 방법

4. 끝맺는 말 다양해진 암호의 기능과 용도 고급 수학이론의 활용으로 암호이론은 수학의 한 분야로 분류되고 있음 정보화 시대: 정보 대국, 정보 속국? 네 정보는 내 정보, 내 정보도 내 정보 … 21세기형 식민지