암호에 대한 이해 정보 보안 개론 7장

1 1 2 2 3 3 4 2 암호의 필요성을 알아본다. 암호화와 복호화의 의미를 이해한다. 여러 암호화 방법의 원리와 그 용도를 살펴본다. 3 4 해시 알고리즘의 원리를 이해한다. 2

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

Section 01 암호의 발전사 대체법(Transposition) EH FDUHIXO IRU DVVDVVLQDWRU 해당 글자를 다른 글자로 대체하여 암호화하는 방법. BC 50년에 로마시대의 줄리어스 시저( Julius Caesar, BC 100)가 이 대체법을 군사적인 목적으로 사용. 시저의 암호화 방법 알파벳 26글자를 3자 또는 4자씩 오른쪽으로 이동시킨 뒤, 해당되는 글자로 변환시켜 암호화. 알파벳을 3 글자씩 오른쪽으로 이동시킨 예 EH FDUHIXO IRU DVVDVVLQDWRU → BE CAREFUL FOR ASSASSINATOR(암살자를 주의하라)

Section 01 암호의 발전사 대체법(Transposition) 모노알파베틱 (Mono alphabetic) 알파벳 26자를 각각 다른 알파벳에 대응시키는데, 규칙 없이 임의의 문자에 임의의 알파벳을 대칭시켜 암호화함. 이렇게 만들어진 암호문은 26!(26×25×24...×2×1~4×1026)가지의 경우의 수를 가짐. 간단한 키워드나 키프레이즈(Keyphrase)를 이용해 해당 알고리즘으로 대칭표를 만들기도 함. 모노알파베틱 예 : ASSASSINATOR라는 키워드의 대칭표 키워드에서 중복된 알파벳을 제거하면 ASINTOR. 이 단어를 앞에 놓고(➊), ASINTOR의 마지막 알파벳 R부터 Z까지를 뒤에 적는데 앞에 나온 알파벳은 제외한다(➋). 다시 A부터 시작해 중복된 알파벳을 제외해 끝까지 적는다(➌).

Section 01 암호의 발전사 빈도수 분석법 단일 치환 암호법은 키워드를 몰라도 복호화가 가능 9세기에 알 킨디라는 아랍의 학자가 기술한 책에 기록되어 있는데, 빈도 분석법 (Frequency Analysis) 이용 빈도 분석법은 알파벳의 26글자가 문장에서 통계적으로 비슷한 빈도수를 가진다는 점에서 착안한 것

Section 01 암호의 발전사 비즈네르 암호화 비즈네르는 프랑스의 외교관으로 일했고, 외교관의 업무가 암호와 매우 깊은 관련이 있어 업무상 관심을 가지게 됨. 비즈네르 암호화 방식은 앞서의 방식과 달리 a가 b에 대응될 수도 있고 c에 대응될 수도 있음. 무엇에 대응할 지를 결정하는 것은 키다. [그림 7-4] 비즈네르

Section 01 암호의 발전사 [표 7-1] 비즈네르 표

Section 01 암호의 발전사 비즈네르 암호화 근대 암호화 비즈네르 암호화 예: wish to be free from myself의 암호화 키가 secret is beautiful 이라 하고 비즈네르의 표를 이용해 암호화 수행. 비즈네르 암호화 같은 방식을 다중문자 치환(Polygram Substitution) 암호 기법이라고 함. 단순한 빈도 분석법으로는 깰 수 없고 17~18세기에 널리 보급되기 시작했음. 19세기에 찰스 배비지에 의해 빈도 분석법을 통한 규칙성을 찾는 방법으로 복호화 방법이 만들어짐. 근대 암호화 19세기 말 찰스 배비지가 비즈네르 암호화 방식의 복호화 방법을 알아내자 암호 제작계는 혼란에 빠짐. 마르코니가 무선 통신을 발명하자 이 문제는 더욱 심각해짐. 무선 통신은 강력한 전달 도구를 제공했지만, 통신 내용을 보호할 수 없는 상태에서는 그 용도가 제한적으로 사용됨.

Section 02 대칭 암호화 방식 암호학적 강도를 높일 때는 혼돈(Confusion)과 확산(Diffusion)을 이용. 혼돈 : 암호문의 통계적 성질과 평문의 통계적 성질의 관계를 난해하게 만드는 성질 확산 : 각각의 평문 비트와 키 비트가 암호문의 모든 비트에 영향을 주는 성질 DES(Data Encryption Standard) 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의 위치를 바꿈.

Section 02 대칭 암호화 방식 DES의 암호화와 복호화 과정 암호화 과정 한 단계를 라운드(Round)라 표현하고, 혼돈이 이 과정에서 이루어짐. DES는 이러한 과정을 하나의 블록에 대해 알고리즘을 16번 수행하므로16라운드 알고리즘. 복호화는 암호화의 반대로 수행

Section 02 대칭 암호화 방식 DES는 암호화 방식의 차이에 따라 ECB(Electronic CodeBook), CBC(Cipher Block Chaining), CFB(Cipher FeedBack), OFB(Output FeedBack)로 나뉨 S-Box에 대한 이해 입력문의 확장 S-Box 에서 매칭 111000은 맨 앞 비트 1과 마지막 비트 0을 합쳐 10(2)이 되고, 가운데 블록은 1100(12) 이 됨. 따라서 111000은 위의 S-Box에서 가로 12, 세로 2가 만나는 3(0011)이 됨. 결국 1011 1100 0111의 가운데 있는 1100은 3(0011)으로 암호화됨. [표 7-3] DES의 S-Box

Section 02 대칭 암호화 방식 트리플 DES DES는 DC(Differential Cryptoanalysis), LC(Linear Cryptoanalysis), DES challenge 등의 공격으로 1999년에 4개월 동안 분산 환경에서 병렬 처리로 복호화하는 데 성공. 1998년에는 전용 칩을 이용하여 56시간 만에, 1999년에는 전용 칩과 10만 대의 PC를 이용하여 22시간 만에 복호화하는 데 성공. 1998년 11월 이후부터는 미 정부에서 사용을 중단. 트리플 DES DES의 복호화가 가능해짐에 따라 AES가 나오기 전까지 임시로 사용한 암호화 알고리즘. 2개의 암호화 키를 이용한 DES.

Section 02 대칭 암호화 방식 AES 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)로 선정.

Section 02 대칭 암호화 방식 기타 대칭형 암호화 알고리즘 IDEA RC5 Skipjack 1990년 ETH(Eidgenossische Technische Hochschule)의 라이(Lai)와 매시(Massey)가 제안한 PES(Proposed Encryption Standard)가 발표됨. 991년에 이를 개선해 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)는 64비트의 키를 가짐. 속도는 DES의 10배. Skipjack 미 국가안보국(NSA)에서 개발한 Clipper 칩에 내장되는 블록 알고리즘으로, 알고리즘의 형태와 구조를 비밀로 유지하다가 1998년에 공개됨. 소프트웨어로 구현되는 것을 막고자 Fortezza Card에 칩 형태로 구현됨. 전화기와 같이 음성을 암호화하는 데 주로 사용된다. 64비트의 입출력, 80비트의 키, 총 32라운드를 가짐.

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

Section 03 비대칭 암호화 방식 비대칭 키에 대한 이해 공개된 정보는 3 같은 키를 공유하기 위해 철수는 자신이 정한 숫자 5를 사용해 3^5인 243이라는 수를 영희에게 보낸다. 영희도 자신의 숫자를 7로 정하고, 3^7인 2,178을 철수에게 보낸다. 철수와 영희는 상대에게 받은 수에 자신의 수를 제곱승. 둘은 자신이 정한 5와 7 숫자를 상대방에게 전달하지 않고서도 50,031,545,098,999,707 이라는 같은 키를 공유하게 됨.

Section 03 비대칭 암호화 방식 RSA(Rivest, Sharmir, Adleman) 알고리즘 1977 년 MIT의 로널드 리베스트(Ronald Rivest), 아디 샤미르(Adi Shamir), 레오나르도 애들먼(Leonard Adleman)이 고안. RSA 암호는 소수(素數)를 이용. 중요 정보를 두 개의 소수로 표현한 후 그것의 곱을 힌트와 함께 전송해 암호로 사용할 수 있다는 아이디어 [그림 7-12] 리베스트, 샤미르, 앤들먼

Section 03 비대칭 암호화 방식 RSA 알고리즘에서는 모든 사람이 고유한N값을 갖게 되는데, N은 두 소수의 곱. 만약 영희가 자신의 N을 p=17,159와 q=10,247의 곱인 N=17,159*10,247=175,828,273으로 정했다면, 영희는 자신의 N값을 모든 사람들에게 공개. 이 때의N 값은 영희의 공개키가 된다. 영희에게 메시지를 보내고 싶은 사람은N 값을 찾아 어떤 알고리즘을 통해 암호화를 한 후 영희에게 보냄. p와 q는 영희의 사설키다. RSA가 처음으로 공개된 것은 1977년 8월. 공개 당시에 독자들에게 p와 q를 찾아보라고 제시한 N 값 잡지에 실린지 17년만인 1994년 4월 26일에 600명의 지원자로 이루어진 팀이 p와 q가 다음 두 수임을 발견했다고 발표. 현재 사용되는 250 자리 RSA 암호는 복호화하는데 우주의 나이만큼 걸림. N = 14,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,362,562, 561,842, 935,706,935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541 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

Section 03 비대칭 암호화 방식 비대칭 키를 이용한 기밀성 확보 철수는 전화번호부에서 전화번호를 찾듯이 영희의 공개키(Public Key)를 얻어, 이 공개키를 이용해 편지를 암호화해서 보내면 영희는 자신이 가진 사설키(Private Key)를 이용해 철수의 편지를 복호화하여 읽을 수 있음.

Section 03 비대칭 암호화 방식 비대칭 키를 이용한 기밀성 확보 예 철수와 영희가 어느 날 철물점에 가서 자물쇠를 하나 샀다고 하자. 둘은 나중에 중요한 물건을 주고받을 때 이 자물쇠를 쓰기로 하고, 자물쇠 부분은 철수가 갖고 열쇠는 영희가 갖는다. 어느 날 철수가 중요한 물건을 영희에게 보낼 일이 생겼다. 그 물건은 꼭 영희만 받아야 하기 때문에 철수는 둘이 같이 산 자물쇠를 쓰기로 했다. 튼튼한 상자를 사서 함께 산 자물쇠로 잠근 후 영희에게 소포로 보낸다. 그러면 소포로 보내진 상자는 열쇠를 가진 영희만 열어볼 수 있을 것이다. 여기서 자물쇠는 영희의 공개키가 되고 열쇠는 영희의 사설키가 된다.

Section 03 비대칭 암호화 방식 비대칭 키를 이용한 부인방지 확보 철수는 영희에게 편지를 보낼 때 자신의 사설키로 편지를 암호화하여 전송. 철수의 사설키로 암호화된 편지는 철수의 공개키로만 열 수 있으므로 영희는 그 편지가 철수가 쓴 것임을 확신할 수 있음.

Section 03 비대칭 암호화 방식 비대칭 키를 이용한 부인방지 확보 예 철수와 영희가 달리기 대회에서 우승해 받은 메달을 반으로 잘라 나눠가졌다고 하자. 세월이 흘러 철수는 자식에게 메달의 반을 물려주었다. 그리고 영희가 어떤 아이가 목에 반쪽짜리 메달을 메고 다니는 것을 보고, “너 철수의 딸 맞지?”라고 했을 때 메달의 반을 가지고 있던 그 아이가“난 철수의 딸이 아냐”라고 할 수 없을 것이다. 철수가 가지고 있던 메달의 반이 철수의 사설키가 되고, 영희가 가지고 있던 메달의 반이 철수의 공개키가 된다.

Section 04 해시 해시(Hash) 하나의 문자열을 이를 상징하는 더 짧은 길이의 값이나 키로 변환하는 것. 세 평문은 길이가 다르지만 해시 결과는 32개의 문자로 길이가 모두 같음. 또한 둘째와 세째 평문은 단어 하나만 다를 뿐인데 해시 결과가 완전히 다름. 이와 같은 결과는 해시값을 통해 해시되기 전의 값을 추측하는 것이 불가능하게 하는 해시의 특성 때문임.

Section 04 해시 MD5 32개의 16진수로 이루어졌으므로 16^32 = 340,282,366,920,938,463,463,374,607,431,768,211,456 개의 결과값이 존재. 이 수는 충분히 커 보이지만 무한은 아님. 우리가 만들어내는 데이터는 이를 훨씬 능가하여 사실상 무한에 가까움. 따라서 다른 데이터를 입력해도 해시 결과값이 같을 수 있는데, 이를 충돌(Collision)이라 함. 충돌이 자주 일어나는 해시는 좋은 해시가 아님.

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

Section 04 해시 MD5 사용 예 md5.txt 생성 md5.txt 파일에 대한 해시 생성

Section 04 해시 해시 알고리즘의 종류 MD5 알고리즘 SHA MD(Message Digest function 95) 알고리즘에는 MD2, MD4, MD5 이렇게 세 가지가 있음. 미국 MIT의 로널드 리베스트 교수가 RSA와 함께 공개키 기반 구조(Public Key Infrastucture)를 만들기 위해 개발. 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에 속함)

Section 04 해시 SHA-1과 SHA-2의 성능 비교(SHA-256, 384, 512는SHA-2에 속함) 알고리즘 메시지 문자 크기 블록 크기 해시 결과값 길이 해시 강도 SHA-1 < 264 512비트 160비트 0.625 SHA-256 256비트 1 SHA-384 < 2128 1024비트 384비트 1.5 SHA-512 2

요약 기본 암호화 방식 전치법(Transposition): 단순히 메시지 안에 들어있는 문자의 위치를 바꾸는 방법 대체법(Substitution): 메시지의 글자를 다른 글자로 대체하여 암호문을 작성하는 방법 단일 치환 암호법(Monoalphabetic Substitution Cipher) 다중 문자 치환 암호 기법: 비즈네르 암호법 대칭 암호화 방식 DES: 1977년 1월 NIST에 의해 암호화 표준으로 지정됐으며, 64비트의 블록 암호화 알고리즘이다. 56비트 크기의 키로 암호화한다. 암호화 방식의 차이에 따라 ECB(Electronic Codebook), CBC(Cipher Block Chaining), CFB(Cipher Feedback), OFB(Output Feedback)으로 나뉜다. 트리플 DES: 두 개의 DES 키를 이용해 두 번의 암호화와 한 번의 복호화 또는 두 번의 복호화와 한 번의 암호화를 수행해 암호화를 한다. AES : 미국의 MARS, RC6, Twofish, 벨기에의 Rijndael, 영국/이스라엘/덴마크의 합작인 Serpent가 결선에 들어가는 알고리즘으로 선정되었다. IDEA: 128비트의 키로 64비트 평문을 8라운드를 거쳐 64비트의 암호문을 생성한다. 모두 16 비트 단위로 연산되도록 하여 16비트 프로세서에서 구현이 용이하다. 주로 키 교환에 쓰인다. RC5: 키, 라운드 수가 가변인 블록 알고리즘 RC5(Ron’s Code 5)로, 64비트의 키를 가진다. 속도는 DES의 10배다. Skipjack: 미국의 NSA에서 개발한 Clipper 칩에 내장되는 블록 알고리즘이다. 전화기와 같은 음성을 암호화하는 데 주로 사용된다. 64비트 입출력에 80비트의 키, 총 32라운드다.

요약 비대칭 암호화 방식 해시 키 교환: 디피와 헬만이 비대칭 암호화 방식을 통한 키 교환 아이디어 고안 RSA: 충분히 큰 두 소수의 곱을 보고 두 소수를 찾기 어려운 점을 이용한다. 1977년 8월에 공개. RSA에서 쓰이는 소수는 250자리 기밀성 확보를 위한 암호화: 수신자의 공개키로 암호화하여 송신한다. 부인방지 확보를 위한 암호화: 발신자의 사설키로 암호화하여 송신한다. 해시 해시의 특성 입력되는 평문의 길이가 달라도 결과값의 길이는 같다. 입력되는 평문의 내용이 조금만 바뀌어도 해시값이 완전히 달라진다. 보안에서 해시를 사용하는 목적: 무결성 확보 MD5(Message Digest function 95): RSA와 함께 공개키 기반 구조(Public Key Infrastucture)를 만들기 위해 개발되었다. 32비트 컴퓨터에 최적화되어 있다. SHA(Secure Hash Algorithm): 160비트 값을 생성하는 해시 함수다. 데이터를 512비트의 블록으로 입력한다.

정보 보안 개론 7장 끝