암호-2장. 암호 기초 ㅎㅎ 정보보호 기능의 가장 핵심적 기술인 암호를 다룬다. 흥미로운 암호의 역사를 소개하고, 고전적인 암호체계로부터 현대적인 디지털 암호체계에 이르는 기술의 발전을 살펴보고 현대의 고급 암호분석 기법을 소개한다. 한빛미디어(주)

학습목표 2장. 암호 기초 단순치환, 이중전위, 코드북 , 일회성 암호 등의 다양한 고전 암호체계를 살펴본다. 암호분석의 기본요소를 설명한다.

대칭키 암호체계는 같은 키를 암호화와 복호화를 위해 사용 공개키 암호체계는 공개키는 암호화, 개인키는 복호화(서명)에 사용 Section 02 암호 용어 암호학(Cryptology) “비밀코드”를 만들거나 해독하는 과학 암호생산(Cryptography) “비밀코드”를 만드는 것 암호분석(Cryptanalysis) “비밀코드”를 해독하는 것 암호(Crypto) 상기한 모든 것 또는 그 이상 암호체계는 평문을 암호화 하는데 사용 암호화 결과는 암호문 암호문을 평문으로 복원하는 것은 복호화 키는 암호체계를 만드는데 사용 대칭키 암호체계는 같은 키를 암호화와 복호화를 위해 사용 공개키 암호체계는 공개키는 암호화, 개인키는 복호화(서명)에 사용

커크호프 원칙(Kerckhoffs Principle) 암호 체계 기본 가정 암호체계는 완전히 공격자에게 알려져 있고, 단지 키만이 유일한 비밀 커크호프 원칙(Kerckhoffs Principle) 암호 알고리즘은 비밀이 아니다. 왜 이런 가정을 하는가? 비밀 알고리즘들은(공개되었을 때) 알고리즘 자체는 강력하지 않을 경우가 많다. 비밀 알고리즘은 결국 공개된다. 사전에 취약점을 발견하는 것이 유리하다.

암호체계 블랙박스 일반적인 암호체계의 사용 키 키 암호문 평문 암호화 복호화

평문: fourscoreandsevenyearsago Key: Section 03 고전 암호-단순 치환 평문: fourscoreandsevenyearsago Key: 암호문: IRXUVFRUHDAGVHYHABHDUVDIR 3번씩 이동하는 “카이사르 암호” 평문 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 D E F G H I J K L M N O P Q R S T U V W X Y Z A B 암호문

평문: spongebobsquarepants 카이사르 암호체계가 사용되는 것을 알고 있다고 가정 카이사르 암호 복호화 평문: spongebobsquarepants 카이사르 암호체계가 사용되는 것을 알고 있다고 가정 암호문: VSRQJHEREVTXDUHSDQWU 평문 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 D E F G H I J K L M N O P Q R S T U V W X Y Z A B 암호문

주어진 n  {0,1,2,…,25}에서 n 시프트 키는 n 예제: 키 = 7 단순하지만 않은 치환 경우 평문 암호문 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 H I J K L M N O P Q R S T U V W X Y Z A B C D E F 암호문

주어진 암호: CSYEVIXIVQMREXIH 키를 찾는 방법? 26가지의 가능한 키  모든 가능한 키를 시도! 전수키 조사 암호분석 1: 모두 시도 단순 치환(n 시프트) 사용 키는 알지 못한 상태 주어진 암호: CSYEVIXIVQMREXIH 키를 찾는 방법? 26가지의 가능한 키  모든 가능한 키를 시도! 전수키 조사 해답: 키 = 4

키는 문자의 순열 치환될 필요가 없음 예제 가능한 키는 26! > 288! 단순치환보다 간단한 경우 평문 암호문 a b 키는 문자의 순열 치환될 필요가 없음 예제 가능한 키는 26! > 288! 평문 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 J I C A X S E Y V D K W B Q T Z R H F M P N U L G 암호문

단순 치환이 사용되었음을 알고 있다. n 시프트일 필요가 없다. 주어진 암호문의 키를 찾는 방법: 암호분석 II: 잘 생각하자 PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFA

288 의 모든 단순 치환키를 모두 시도할 수는 없다 – 경우의 수가 너무 많음. 다른 방법은? 영어 문자의 사용 빈도수를 … 암호분석 II 288 의 모든 단순 치환키를 모두 시도할 수는 없다 – 경우의 수가 너무 많음. 다른 방법은? 영어 문자의 사용 빈도수를 …

암호문: 암호분석 II 아래 정보를 이용하여 복호화 암호문 빈도수: A B C D E F G H I J K L M N O P PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFA 아래 정보를 이용하여 복호화 암호문 빈도수: 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 21 26 6 10 12 51 25 9 3 1 15 28 42 27 4 24 22

암호체계가 만약 알려진 가장 효율적인 공격이 모든 키를 시도해야 하면 보안적으로 안전하다. 암호분석: 용어 암호체계가 만약 알려진 가장 효율적인 공격이 모든 키를 시도해야 하면 보안적으로 안전하다. 암호체계가 다른 지름길이 있으면 보안적으로 안전하지 않다. 이 정의에 의하면, 안전하지 않은 체계가 안전한 체계보다 해독하기가 더 어렵다!

 평문: attackxatxdawn 암호문: xtawxnattxadakc 이중 전위 평문: attackxatxdawn 암호문: xtawxnattxadakc 키: 행/열 크기와 순열 (3,5,1,4,2)과 (1,3,2) 행과 열을 바꾼다 

암호화: 평문  키 = 암호문 h e i l t r s r l h t 일회용 암호-암호화 평문: 키: 암호문: e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111 암호화: 평문  키 = 암호문 h e i l t r 001 000 010 100 111 101 평문: 111 101 110 100 000 001 s r l h t 키: 암호문:

복호화: 암호문  키 = 평문 일회용 암호-복호화 s r l h t 암호문: 키: h e i l t r 평문: e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111 복호화: 암호문  키 = 평문 s r l h t 110 101 100 001 111 암호문: 키: 111 101 110 100 000 001 010 h e i l t r 평문:

이중 첩자는 송신자가 다음의 “키”를 사용했다고 주장 일회용 암호 이중 첩자는 송신자가 다음의 “키”를 사용했다고 주장 s r l h t 110 101 100 001 111 암호문: “키”: 101 111 000 100 110 011 010 001 k i l h t e r “평문”: e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

체포된 송신자는 “키”가 아래와 같다고 주장 일회성 암호 s r l h t 암호문: “키”: h e l i k s “평문”: 110 101 100 001 111 암호문: “키”: 111 101 000 011 110 001 100 010 h e l i k s “평문”: e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111

왜 암호를 분배하는 방법과 동일하게 메시지를 분배하지 않는가? 일회용 암호 요약 증명된 안전성 암호문이 평문에 대한 어떤 정보도 제공하지 않음. 모든 평문은 같은 확률 키는 임의수이며 단 한번만 사용 키는 송수신자만 알고 있음. 키 크기는 메시지 크기와 동일 메시지 무결성을 제공하지 않음. 왜 암호를 분배하는 방법과 동일하게 메시지를 분배하지 않는가?

일회용 암호 키의 반복 사용이 해독이 가능토록 하였음. 실세계의 일회용 암호 VENOVA 프로젝트 1940년대 미국에서 전송된 소련 스파이 메시지 핵무기에 대한 첩자 행위 등 수 많은 메시지가 전송 스파이는 미국에 일회용 암호 키 반입 비밀 메시지를 일회용 키를 사용 암호화 일회용 암호 키의 반복 사용이 해독이 가능토록 하였음.

“Ruth” == Ruth Greenglass “Liberal” == Julius Rosenberg VENONA 해독 (1944) “Ruth” == Ruth Greenglass “Liberal” == Julius Rosenberg “Enormous” == the atomic bomb

말 그대로 “코드워드”로 채워진 책 짐머맨 전보는 코드북으로 암호화 코드북 암호 말 그대로 “코드워드”로 채워진 책 짐머맨 전보는 코드북으로 암호화 Februar 13605 fest 13732 finanzielle 13850 folgender 13918 Frieden 17142 Friedenschluss 17149 : : 독일 외상 짐머만이 멕시코 정부에 전달한 이 비밀 문서에서 독일은 미국이 참전할 경우 멕시코가 독일편에 가담해 준다면 그 대가로 미국령 텍사스, 뉴멕시코, 애리조나를 넘겨주겠다고 제의했다. 현대 블록 암호들은 코드북들!

짐머맨 전보 현재까지 가장 알려진 코드북 중에 하나 미국이 일차 세계대전에 참여하게 된 계기 암호문은 우측…

짐머맨 전보 해독 영국은 부분적인 코드북 확보 빠진 부분을 보충하여 해독

“신사는 타인의 우편물을 읽지 않는다”  국방장관 헨리 스팀슨, 1929 Section 04 현대 암호 역사- 20세기 초 1차 세계대전  짐머맨 전보 “신사는 타인의 우편물을 읽지 않는다”  국방장관 헨리 스팀슨, 1929 2차 세계대전  암호분석의 황금시대 일본 펄프암호 (암호명 MAGIC) 독일 이니그마암호 (코드명 ULTRA)

Claude Shannon  정보이론의 아버지 컴퓨터 혁명  대량 자료 2차 세계대전 이후 Claude Shannon  정보이론의 아버지 컴퓨터 혁명  대량 자료 Data Encryption Standard (DES), 70’s 공개키 암호, 70’s CRYPTO conferences, 80’s Advanced Encryption Standard (AES), 90’s 암호체계는 숨겨져 있다가 바깥 세상으로 빠져 나오게 되었음.

Information Theory의 창시자 1949 논문: Comm. Thy. of Secrecy Systems Claude Shannon Information Theory의 창시자 1949 논문: Comm. Thy. of Secrecy Systems 혼돈(confusion)과 확산(diffusion) 혼돈  암호문과 평문의 관계를 상관관계를 숨김 확산  평문의 통계적 성질을 암호문 전반에 퍼뜨려 숨김 일회성 암호가 안전함을 증명 일회성 암호는 혼돈만을 사용하고, 이중 전위 암호는 확산만을 사용

대칭키 공개키 해시 알고리즘 Section 05 암호학의 분류 암호화와 복호화에 같은 키 사용 스트림 암호 블록 암호 암호화(공개키)와 복호화(개인키)를 위해 2개의 키 사용 디지털 서명 해시 알고리즘

암호문 공격(Ciphertext only) 알려진 평문 공격(Known plaintext) Section 06 암호분석의 분류 암호문 공격(Ciphertext only) 알려진 평문 공격(Known plaintext) 선택된 평문 공격(Chosen plaintext) “점심시간 공격” 프로토콜은 선택된 문장을 암호화 할 수 있음 적응적 선택 평문 공격 관련키 공격 순방향 탐색 공격(공개키 암호에서만 가능) 기타 등등 ….