Chapter 2 암호 기초

Crypto 암호학(Cryptology) Cryptography 암호 분석(Cryptanalysis) Crypto “비밀 코드”를 만들거나 해독하는 기술과 과학 Cryptography “비밀 코드”를 만드는 법 암호 분석(Cryptanalysis) “비밀 코드”를 해독하는 법 Crypto 위의 모든 것(과 그 이상)을 지칭한다. 암호학(Cryptology) “비밀코드”를 만들거나 해독하는 과학 암호생산(Cryptography) “비밀코드”를 만드는 것 암호분석(Cryptanalysis) “비밀코드”를 해독하는 것 암호(Crypto) 상기한 모든 것 또는 그 이상 Chapter 2 Crypto Basics

암호 체계: 블랙 박스 Crypto의 일반적 사용 key key plaintext plaintext encrypt decrypt ciphertext Crypto의 일반적 사용 Chapter 2 Crypto Basics

Crypto에서의 용어들 암호 체계(cipher or cryptosystem) 암호문(ciphertext) 평문 (plaintext)을 암호화(encrypt)하는데 사용 암호문(ciphertext) 암호화된 결과 복호화(decrypt) 암호문을 평문으로 복원 키(key) 암호체계를 만드는데 사용 대칭키(symmetric key) 같은 키를 암호화와 복호화를 위해 사용 공개키(public key) 공개키(public key) 는 암호화, 개인키( private key) 는 복화화에 사용 암호체계는 평문을 암호화 하는데 사용 암호화 결과는 암호문 암호문을 평문으로 복원하는 것은 복호화 키는 암호체계를 만드는데 사용 대칭키 암호체계는 같은 키를 암호화와 복호화를 위해 사용 공개키 암호체계는 공개키는 암호화, 개인키는 복호화(서명)에 사용 Chapter 2 Crypto Basics

Crypto 기본 가정 커크호프의 원칙( Kerckhoffs Principle) 왜 이런 가정을 하는가? 암호체계는 완전히 공격자에게 알려져 있고, 오직 키(Key)만이 유일한 비밀이다. 커크호프의 원칙( Kerckhoffs Principle) 암호 알고리즘은 비밀이 아니다. 왜 이런 가정을 하는가? 경험적으로 볼 때, 비밀 알고리즘들은(공개되었을 때) 알고리즘 자체는 강력하지 않을 경우가 많다. 비밀 알고리즘은 결국 공개된다. 사전에 취약점을 발견하는 것이 유리하다. http://en.wikipedia.org/wiki/Kerckhoffs'_principle In cryptography, Kerckhoffs' principle (also called Kerckhoffs' assumption, axiom or law) was stated by Auguste Kerckhoffs in the 19th century: a cryptosystem should be secure even if everything about the system, except the key, is public knowledge. It was reformulated (perhaps independently) by Claude Shannon as "the enemy knows the system". In that form it is called Shannon's maxim. In contrast to security through obscurity, it is widely embraced by cryptographers. In accordance with Kerckhoffs' principle, the majority of civilian cryptography makes use of publicly-known algorithms. By contrast, ciphers used to protect classified government or military information are often kept secret (see Type 1 encryption). The law was one of six design principles laid down by Kerckhoffs for military ciphers. Translated from French, they are: The system must be practically, if not mathematically, indecipherable; It must not be required to be secret, and it must be able to fall into the hands of the enemy without inconvenience; Its key must be communicable and retainable without the help of written notes, and changeable or modifiable at the will of the correspondents; It must be applicable to telegraphic correspondence; It must be portable, and its usage and function must not require the concourse of several people; Finally, it is necessary, given the circumstances that command its application, that the system be easy to use, requiring neither mental strain nor the knowledge of a long series of rules to observe. Bruce Schneier ties it in with a belief that all security systems must be designed to fail as gracefully as possible: "Kerckhoffs' principle applies beyond codes and ciphers to security systems in general: every secret creates a potential failure point. Secrecy, in other words, is a prime cause of brittleness—and therefore something likely to make a system prone to catastrophic collapse. Conversely, openness provides ductility."[1] It is worth expanding on what Schneier means by brittleness: after all, any security system depends crucially on keeping some things secret. What Schneier means is that the things which are kept secret ought to be those which are least costly to change should they be inadvertently disclosed. A cryptographic algorithm may be implemented by hardware and software which is widely distributed among its users; if security depended on keeping that secret, then disclosure would lead to major logistic headaches in developing, testing and distributing implementations of a new algorithm. Whereas if the secrecy of the algorithm were not important, but only that of the keys used with the algorithm, then disclosure of the keys would require the much less arduous process of generating and distributing new keys. Or in other words, the fewer and simpler the things one needs to keep secret in order to ensure the security of the system, the easier it is to maintain that security. Eric Raymond extends this principle in support of open source software, saying "Any security software design that doesn't assume the enemy possesses the source code is already untrustworthy; therefore, *never trust closed source*. [2] The controversial idea that open-source software is inherently more secure than closed-source is promoted by the concept of security through transparency. It's possible to have a secret cryptosystem while still reaping the benefits of public cryptography research: make a non-weakening change to a public algorithm, like changing the Nothing up my sleeve numbers, or, in the case of Symmetric-key algorithms, chaining the public cipher with an unrelated secret cipher. An example of technology which relies upon a secret cryptosystem is WAPI, the wireless LAN security standard the Chinese government has proposed to encompass civilian uses on a global scale. Chapter 2 Crypto Basics

고전적인 암호 알고리즘 치환 이중 전위(double transposition) 일회성 암호(one-time pad) 코드북(codebook)

단순 치환(Simple Substitution) Plaintext: fourscoreandsevenyearsago Key: Plaintext Ciphertext 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 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 C Ciphertext: IRXUVFRUHDAGVHYHABHDUVDIR 시저 암호(Caesar’s cipher): 세자리 만큼 이동 Chapter 2 Crypto Basics

시저 암호의 복호화(Decryption) Ciphertext: VSRQJHEREVTXDUHSDQWU Plaintext Ciphertext 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 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 C Plaintext: spongebobsquarepants Chapter 2 Crypto Basics

단순하지 않은 치환 n 만큼 이동, n  {0,1,2,…,25} 키(key)는 n 예: key = 7 Plaintext Ciphertext 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 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 G Chapter 2 Crypto Basics

암호 분석(Cryptanalysis) I: 모든 경우를 시도한다 주어진 조건 단순 치환 사용 (n만큼 이동) 그러나 키는 알려져 있지 않다. 주어진 암호문: meqefscerhcsyeviekmvp 어떻게 키를 찾을 것인가? Exhaustive key search 가능한 키는 오직 26가지  모두 시도해 본다! 해답: key = 4 IAMABOYANDYOUAREAGIRL Chapter 2 Crypto Basics

문자열의 순열에 의한 치환 Key는 문자의 어떤 순열이다. 문자를 이동( shift)할 필요가 없다. 예 Plaintext Ciphertext 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 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 O 그러면 26! > 288 개의 가능한 키가 존재한다! 이 방법은 처음 1000년간 비밀 코드를 만드는 기술을 지배하였다. Chapter 2 Crypto Basics

암호분석 II: 잘 생각하자! 단순 치환이 사용되었다는 것을 알고 있다. 그러나 n 자리수의 이동일 필요는 없다. 다음의 암호문의 키를 찾아낼 수 있는가: PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNTOZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQGVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQHFOQPWTBDHHIXQVAPBFZQHCFWPFHPBFIPBQWKFABVYYDZBOTHPBQPQJTQOTOGHFQAPBFEQJHDXXQVAVXEBQPEFZBVFOJIWFFACFCCFHQWAUVWFLQHGFXVAFXQHFUFHILTTAVWAFFAWTEVOITDHFHFQAITIXPFHXAFQHEFZQWGFLVWPTOFFA Chapter 2 Crypto Basics

암호분석 II 모든 288 가지의 치환될 수 있는 키를 고려할 필요는 없다. 좀 더 현명할 수는 없을까? 영어 알파벳의 빈도수… Chapter 2 Crypto Basics

암호분석 II Ciphertext: 다음의 정보를 기반으로 복호화를 한다. 암호문에서의 알파벳 빈도수: 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 Z 21 26 6 10 12 51 25 9 3 1 15 28 42 27 4 24 22 8 Chapter 2 Crypto Basics

빈도수 분석(Frequency analysis)의 역사 아랍인에 의해서 발견 빈도수 분석에 대한 최조의 기록은 9세기 과학자 Al Kindi의 책에서 찾아볼 수 있다. (Abū Yūsuf Yaqūb ibn Isḥāq al-Kindī, Arabic: أبو يوسف يعقوب إبن إسحاق الكندي‎) (c. 801–873 CE), (Alkindus) 르네상스 때 아랍인에 의해서 유럽에 소개 빈도수 분석으로 치환 방법은 더 이상 안전한 암호화 알고리즘이 되지 않았다. Chapter 2 Crypto Basics

암호체계가 안전하다는 말의 뜻은? 암호를 해석하기 위해서 알려진 최선의 공격 방법은 모든 키를 다 시도해 보는 것일 때 이 암호 체계는 안전하다고 한다.(Cryptosystem is secure) 암호를 해석하는데 어떤 지름길이 있다면 그 암호체계는 불안전하다고 한다. (Cryptosystem is insecure) 이 정의에 의하면 불안전한 암호체계가 안전한 암호체계 보다도 해석하기 더 어려울 수도 있다! Chapter 2 Crypto Basics

이중 전위(Double Transposition) Plaintext: attackxatxdawn Permute rows and columns  Ciphertext: xtawxnattxadakc Key: 행렬의 크기와 순열 (3,5,1,4,2) and (1,3,2) Chapter 2 Crypto Basics

일회성 암호(One-time Pad)의 암호화 e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111 Encryption: Plaintext  Key = Ciphertext P h e i l t r 001 000 010 100 111 101 K 110 C s Chapter 2 Crypto Basics

일회성 암호의 복호화 C P Decryption: Ciphertext  Key = Plaintext s r l h t K e e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111 Decryption: Ciphertext  Key = Plaintext C s r l h t 110 101 100 001 111 K 000 P 010 e i Chapter 2 Crypto Basics

일회성 암호(One-time Pad) 이중 첩자는 송신자가 다음의 “키”를 사용했다고 주장한다. C P s r l h t K 110 101 100 001 111 K 000 P 011 010 k i e e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111 Chapter 2 Crypto Basics

일회성 암호(One-time Pad) 체포된 송신자는 “키”는 다음과 같다고 주장한다. C P s r l h t K e i k 110 101 100 001 111 K 000 011 P 010 e i k e=000 h=001 i=010 k=011 l=100 r=101 s=110 t=111 Chapter 2 Crypto Basics

일회성 암호 정리 증명된 안전성(Provably secure), when used correctly 암호문은 평문에 대한 어떤 정보도 제공하지 않는다. 모든 평문이 만들어질 가능성은 동일하다. 키(Pad)는 임의의 값이며 단지 한번만 사용된다. 키(Pad)는 오직 송신자와 수신자만 알고 있다. 키(Pad)는 메시지와 동일한 크기이다. 메시지의 무결성을 제공하지 않는다. 의문: 키(pad)를 안전하게 전달할 수 있다면 메시지 자체를 전달하면 되지 않겠는가? Chapter 2 Crypto Basics

실제 세계에서의 일회성 암호 예 프로젝트 VENONA 스파이는 미국에 일회성 암호 반입 1940년대 미국으로부터 전송된 소련 스파이의 메시지 핵무기에 대한 첩자 행위 등 수천의 메시지 전송 스파이는 미국에 일회성 암호 반입 스파이는 키를 비밀 메시지를 암호화하는데 사용 일회성 키의 반복 사용이 암호 해석이 가능하도록 했다. espionage [éspienà:¥|èspien:¥] n. (타인R타국에 대한) 스파이 행위, 첩보 활동, 정찰. a novel of intrigue and ∼ 음모 및 스파이 소설. political[military] ∼ 정치[군사] 정보 활동 Chapter 2 Crypto Basics

VENONA 암호 해석 (1944) “Ruth” == Ruth Greenglass “Liberal” == Julius Rosenberg “Enormous” == the atomic bomb Chapter 2 Crypto Basics

코드북(Codebook) 말 그대로 “코드 워드”로 채워진 책이다. Zimmerman Telegram 는 코드북으로 암호화되었다. Februar 13605 fest 13732 finanzielle 13850 folgender 13918 Frieden 17142 Friedenschluss 17149 : : 현대의 블록 암호들은 코드북이다. Chapter 2 Crypto Basics

Zimmerman Telegram 현재까지 알려진 가장 유명한 코드북의 하나 미국이 1차세계대전에 참여하도고 함 우측에 있는 것이 암호문이다. Chapter 2 Crypto Basics

해석된 Zimmerman Telegram 영국은 코드북을 부분적으로 복원하였다. 빠진 부분을 보충하여 해독 Chapter 2 Crypto Basics