I부 암호

암호 기초 2장

암호용어 정의 암호학(Cryptology) 암호생산(Cryptography) 암호분석(Cryptanalysis) “비밀코드”를 만들거나 해독하는 과학 암호생산(Cryptography) “비밀코드”를 만드는 것 암호분석(Cryptanalysis) “비밀코드”를 해독하는 것 암호(Crypto) 상기한 모든 것 또는 그 이상

암호용어 정의 암호체계는 평문을 암호화 하는데 사용 암호화 결과는 암호문 암호문을 평문으로 복원하는 것은 복호화 키는 암호체계를 만드는데 사용 대칭키 암호체계는 같은 키를 암호화와 복호화를 위해 사용 공개키 암호체계는 공개키는 암호화, 개인키는 복호화(서명)에 사용

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

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

단순 치환 평문: fourscoreandsevenyearsago Key: 암호문: 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 z C 암호문 암호문: IRXUVFRUHDAGVHYHABHDUVDIR 3번씩 이동하는 “카이사르 암호”

카이사르 암호 복호화 평문: 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 z C 암호문

단순하지만 않은 치환 경우 주어진 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 z G 암호문

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

단순치환보다 간단한 경우 키는 문자의 순열 치환될 필요가 없음 예제 가능한 키는 26! > 288 평문 a b c d e 키는 문자의 순열 치환될 필요가 없음 예제 평문 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 z O 암호문 가능한 키는 26! > 288

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

암호분석 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 Z 8

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

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

일회용 암호-암호화 h e i l t r s r l h t 암호화: 평문  키 = 암호문 평문: 키: 암호문: 001 000 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 복호화: 암호문  키 = 평문 암호문: 키: 평문: 110 101 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 k i l h t e r 암호문: “키”: 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년대 미국에서 전송된 소련 스파이 메시지 핵무기에 대한 첩자 행위 등 수 많은 메시지가 전송 스파이는 미국에 일회용 암호 키 반입 비밀 메시지를 일회용 키를 사용 암호화 일회용 암호 키의 반복 사용이 해독이 가능토록 하였음.

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

코드북 암호 말 그대로 “코드워드”로 채워진 책 짐머맨 전보는 코드북으로 암호화 현대 블록 암호들은 코드북들! Februar 13605 fest 13732 finanzielle 13850 folgender 13918 Frieden 17142 Friedenschluss 17149 : : 현대 블록 암호들은 코드북들! 나중에 다시 토의 하겠음…

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

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

역사적인 암호들 Crypto timeline Spartan Scytale  전위 암호 카이사르 암호 Poe’s The Gold Bug 1876년 선거

1876 선거 “러더퍼드 헤이즈” 대 “새뮤엘 틸덴”: 팽팽한 대결 선거 4개 주의 대위원 선거인단이 결정 4개 주의 대위원이 헤이즈로 결정 틸덴은 헤이즈가 대위원에게 뇌물을 주어 부당하게 선출되었다고 주장 이것이 사실인가?

1876 선거 나중에 틸덴 지지자들의 암호화된 메시지 발견 암호문: 부분적인 코드북과 전위 암호 중요 단어들은 코드북에서 치환 암호문 평문 Copenhagen Greenbacks Greece Hayes Rochester votes Russia Tilden Warsaw telegram : :

1876 선거 원 메시지에 코드북을 적용 암호문은 5 단어들의 배수 (총 길이, 10, 15, 20, 25 또는 30 단어) 각 길이에. 고정된 순열을 결과 메시지에 적용 순열들은 같은 길이의 많은 메시지를 비교하여 찾아짐 주어진 길이의 모든 메시지에 같은 키를 적용하였음에 유의

1876 선거 암호문: Warsaw they read all unchanged last are idiots can’t situation 코드북: Warsaw  telegram 전위: 9,3,6,1,10,5,2,7,4,8 평문: Can’t read last telegram. Situation unchanged. They are all idiots. 키의 재사용은 약한 암호문을 더욱 악화 교훈: 키를 재사용하거나 남용하지 말 것!

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

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

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

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

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