암호 - 고전. 현대

1. 암호란 무엇인가:  비밀정보의 교환 수단

       1. 암호란 무엇인가?

• 비밀정보의 교환을 위해 생겨남

– 처음에는 군사용으로 주로 사용

– 현재  전자상거래, 전자우편, 무선통신 등에 널리 쓰임 

• 정보화시대 : 정보의 관리, 보호의 중요성 증대

– 국가, 회사, 단체, 개인

• 암호체계의 효용성 및 안전성 분석

– 고급  수학이론에 기반

암호의 개념도

2. 고전암호

2-1. 제1세대 암호

• 이동암호 (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)

– 임의로 뒤섞은 순열을 하나 선택한 후, 이 순열을 이용하여  암호화                                    

– 예) 0→25, 1→24, … , 24→1, 25→0                           

– cryptography → xibkgltizksb                              

– 이 예는 a=-1, b=25인 아핀 암호                    

셜록홈즈의 춤추는 인형

• 위: 셜록홈즈의 의뢰받은 암호메세지

• 아래: 암호를 간파한 홈즈가   다시 범인에게 보낸 암호문

• 가장 자주 나오는 모양: e

• 깃발 : 단어마다 끝 철자

2-2. 제2세대 암호

• 제2세대 암호의 특징

기계암호

• 기계암호에 쓰인 대표적인 기계

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. 비밀키 암호체계

블록 암호

• 긴 평문을 일정한 길이의 블록으로 나누어 블록단위    암호화하는 방식

• DES (Data Encryption Standard)                        1976년 미 국가 표준국(NIST) 주도하에 설계됨      64비트 단위로 암호화; 키의 길이=56비트

• AES (Advanced Encryption Standard)                1997년부터 진행, 2001년 Rijndael이 채택됨        128비트 단위로 암호화; 키의 길이=128비트(이상)

스트림 암호

• 평문을 1비트(bit) 단위로 암호화하는 방식

• 키를 키스트림 생성기라는 알고리즘에 입력하여 발생되는 1비트 키의 무한수열로 평문을 암호화

• 블록 단위로 사용하기도 함 

스트림 암호

3-2. 공개키 암호체계

3-3. RSA 암호체계

RSA의 키 생성

RSA의 암호화 및 복호화

RSA의 암호화 및 복호화

RSA의 서명기능

소수판정

ㆍ소수의 판정은 RSA 암호체계를 만들기 위해 필요

소인수분해

– 주어진 수의 제곱근 보다 작은 모든 양의 정수로 차례로 나누어  보는 방법으로는 1초에 백만 번의 계산을 할 수 있는 컴퓨터로   30 자리 수 -1일; 40 자리 수 -100만년;                                50 자리 수 -우주의 역사보다도 긴 시간이 필요! 

– 현재까지 알려 진 가장 빠른 방법: 75자리 수는 한 달;             100자리 수는 백년 정도가 소요

– RSA 암호체계: 소수판정은 빨리 할 수 있지만 소인수분해는 많은 시간이 걸린다는 사실을 이용

3-4. 암호분석

암호해독

암호해독

암호해독

• 암호해독이란                                                         주어진 암호문에 대하여 여러 가지 단편적인 정보들을 토대로 평문을 복원하는 작업

• 암호분석(Cryptanalysis)                                           암호의 해독 뿐만 아니라, 암호체계의 안전성을 검증함으로써 새로운 암호체계 개발에 핵심적인 역할을 함  

• 암호의 안전성                                                         컴퓨터의 능력, 시간, 비용 등을 감안할 때 현실적으로 주어진 시간  내에 그 해독 방법을 알아내기가 불가능할 때 암호체계가 안전하다고 판단함

안전성

     - 선택 평문 공격(Chosen Plaintext Attack-CPA)에 대한 안전성

    - 선택 암호문 공격(Chosen Ciphertext Attack-CCA1)에 대한 안전성

    - 적응선택 암호문 공격(Adaptively Chosen Ciphertext Attack-CCA2)에    대한 안전성 

3-5. 암호의 응용

• 은행 비밀번호 

• 전자화폐, 전자투표 

• 전자경매, 입찰(Electronic Auction, Bid)                                                 영지식증명(Zero-Knowledge Proof)                          다자간계산(Multi-Party Computation) …

은행 비밀번호

• 고객이 계좌를 개설할 때 비밀번호를 지정하면 고객의      비밀번호를 RSA암호체계로 암호화한 값만 계좌번호와    함께 보관하고 비밀번호는 삭제

• 고객이 예금인출을 원할 때, 비밀번호를 제시하면 같은           방법으로 암호화하여 기존에 계좌번호와 함께 기록되어   있는 값과 일치하면 인출

• 이 과정이 없으면 인출 불가. 즉, 비밀번호의 암호화        과정을 생략한 채 은행에 보관된 암호화된 값만              제시해서는 인출이 불가하므로 안전

• 암호화된 값만으로 비밀번호를 아는 것은 매우 어려움...  

전자화폐

스마트 카드

• 신용카드와 같은 크기, 두께의 플라스틱 카드

• 마이크로프로세서, 주변회로, 기억장치(ROM), 보안 알고리즘 기능을 갖춘 마이크로 컴퓨터를 Chip On Board의 형태로 내장

• 보안성, 다목적성, 휴대성, 사용의 편리성

• 스마트 카드 = 현금

전자 입찰과 경매, ZKP와 MPC, …

• 전자경매 또는 전자입찰(Electronic Auction or Bid)

– 구매자가 구매가를 암호화하여 접수하고 모든 접수가 완료된 후 경매자가   구매자들의 협조를 얻어 복호화. 구매자가 구매가를 조작할 수 없도록 함    

• 영지식증명(Zero-Knowledge Proof)

– 내가 알고 있는 어떤 중요한 정보에 대하여 그 내용에 관한 것은 일체 알려 주지 않으면서 내가 그 정보를 알고 있음을 상대방에게 증명해 보이는 방법

• 다자간계산(Multi Party Computation)

– 다수의 사용자가 각각 자신만이 아는 정보를 소유한 상태에서 각자의 정보는 노출시키지 않고 모두에게 필요한 새로운 정보를 계산하여 공유하는 방법

4. 끝맺는 말

• 다양해진 암호의 기능과 용도 

• 고급 수학이론의 활용으로 암호이론은 수학의 한 분야로 분류되고 있음