암호 이야기 수학과 채 갑병

통신수단의 발전(전쟁, spy, etc) 비밀보장의 요구 암호를 만드는 사람들과 해독가와의 전쟁 2007 채갑병 RC

암호의 진화 현대사회에서의 의미의 증대 프라이버시, 법집행과 테러 범죄집단 1차세계대전 : 독가스와 염소 사용 : 화학전쟁 박테리아와 항생제의 관계 현대사회에서의 의미의 증대 프라이버시, 법집행과 테러 범죄집단 1차세계대전 : 독가스와 염소 사용 : 화학전쟁 2차세계대전 : 원자폭탄 : 물리학 전쟁 3차세계대전 : 정보 제어 : 수학전쟁 2007 채갑병 RC

원문 = plaintext : 보통 소문자로 나타냄 암호문 = ciphertext : 대문자로 표시 Code : 문장, 단어의 대체 codename : 암호명 새벽에 공격하라 : Jupiter 원문 = plaintext : 보통 소문자로 나타냄 암호문 = ciphertext : 대문자로 표시 2007 채갑병 RC

Communications Headquaters ) 영국정보통신본부 (GCHQ = Government Communications Headquaters ) 미국 국가안보국 ( NSA : National Security Agency) 2007 채갑병 RC

에피소드 1 스코틀랜드 여왕 메리의 암호 메리와 엘리자베스(영국여왕)는 사촌간 메리의 엘리자베스 암살음모 : 암호로 편지 교환 국무장관 월싱엄경이 암호 추적 : 해독가 토머스 펠립스의 도움 2007 채갑병 RC

에피소드 2 그리스와 페르시아의 전쟁(역사-헤로도토스 지음) 페르시아의 크세르크세스Xerxesd 왕 아테네와 스파르타의 반항 페르시아의 대 그리스 전쟁준비(BC480) 그리스인 데마라토스 : 종이대신 당시에는 밀납을 입힌 나무판이 사용되었음 – 밀납을 밀어내고 메시지를쓴다음 다시 밀납을 입혀 감춤 – 고르고가 신의 계시로 밀납을 벗겨 읽음 그리스의 전쟁승리 2007 채갑병 RC

에피소드 3 히스타아이오스가 밀레토스의 아리스나고라스에게 페르시아 왕에게 반기를 들도록 종용한 편지(역사-헤로도토스 지음) 머리를 삭발후 메시지 씀 – 다시 머리카락이 자랄때까지 기다린후 전령으로 감 – 머리를 다시 자르고 메시지를 봄 (1년은 머리를 못감겠군 !) 2007 채갑병 RC

비밀 통신의 방법 스테가노그라피(steganography) 크립토그래피(cryptography) 2007 채갑병 RC

스테가노그라피(steganography) : 메시지의 존재자체를 감추는 비밀통신의 방법 위의 2, 3번 에피소드에 해당 고대중국에서 얇은 비단에 메시지를 쓴 뒤 작은공처럼 만들어 이를 밀랍으로 싼다음 전령이 삼킴 15세기 이탈리아 과학자 조반니 포르타Giovanni Porta(1535-1615)는 삶은 달걀에 메시지를 숨기는 방법을 기록 : 명반에 식초를 섞어 만든 잉크로 삶은 달걀위에 글씨를 쓰면, 달걀 껍질의 미세한 구멍으로 잉크가 스며들어감 껍질을 벗겨서 읽음 2007 채갑병 RC

기원후 1세기에 플리니Pliny(AD 23-79) 는 티티말러스라는 식물즙(탄소를 많이 함유)을 잉크로 사용해 보이지 않는 메시지를 쓰는 방법을 설명 : 열을 가해서 봄 2007 채갑병 RC

크립토그래피(cryptography) 메시지의 의미를 감추는 비밀통신 방법 메시지의 의미를 감추는 과정을 암호화(encryption)라고 부른다 특정 프로토콜을 따라 암호화 하고 받은 사람은 다시 복호화(decryption-암호화의 반대) 한다. 2007 채갑병 RC

스테가노그라피와 크립토그래피를 동시에 사용 하기도 했다. 즉 메시지의 존재와 의미 두 가지를 모두 감춘다. 마이크로도트microdot – 독일 스파이가 중남미에서 2차대전때 사용 : 미국에 의해 발견, 해석됨 2007 채갑병 RC

크립토그래피 전치법transposition 대체법substitution 2007 채갑병 RC

크립토그래피 전치법transposition 단순히 메시지 안에 있는 문자의 위치를 바꾸어 사용한다.(아나그램anagram이라고 부르기도 한다) cow를 cwo, ocw, owc, wco, woc등으로 바꿈 For example, consider this sentence 의 경우 35!/4!= 430547831932756038736110472396800000000 의 배열방법이 존재 송신인과 수신인 사이에 미리 정해놓은 규칙(protocol)을 사용해야 한다. 2007 채갑병 RC

전치법transposition 의 예 가로장 울타리 THY SECRET IS THY PRISONER; IF THOU LET IT GO, THOU ART A PRISONER TO IT T Y E R T S H P I O E I T O L T T O H U R A R S N R O T H S C E I T Y R S N R F H U E I G T O A T P I O E T I TYERTSHPIOEITOLTTOHURARSNROTHSCEITYRSNRFHUEI GTOATPIOETI 2007 채갑병 RC

기원전 5세기에 스파르타인이 사용했던 사이테일scytale : 세줄 가로장 울타리 전치법 글자를 짝지어 그 두개의 순서를 뒤바꾸는 방법 기원전 5세기에 스파르타인이 사용했던 사이테일scytale : 나무 막대기에 길고가는끈이나 양피지 끈을 입히고 가로질러 글을 쓴다음 풀러서 전달한다. 받은사람은 같은 지름의 막대기에 다시묶어서 메시지를 본다. 2007 채갑병 RC

크립토그래피 대체법 substitution 카마수트라(인도 학자 바차야나지음AD4)에서 최초로 언급 율리우스 카이사르 애용 2007 채갑병 RC

meet at midnight 이라는 메시지는 예 A D H I K M O R S U W Y Z V X B G J C Q L N E F P T meet at midnight 이라는 메시지는 CUUZ VZ CGXSGIBZ 라는 암호문으로 변환 2007 채갑병 RC

카이사르의 이동 사이퍼 원문 알파벳 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 원문 veni, vidi, vici (왔노라, 보았노라, 이겼노라) 암호문 YHQL, YLGL, YLFL 2007 채갑병 RC

알고리듬은 원문 알파벳의 한 글자는 그에 상응하는 사이퍼 알파벳의 글자하나로 대체 사이퍼 알파벳은 알파벳 순서에 상관없이 재배열 된것 열쇠는 특정 암호문에 사용된 정확한 사이퍼 알바벳을 의미 2007 채갑병 RC

알고리듬과 열쇠사이의 관계 2007 채갑병 RC

“암호의 보안성은 그 암호에 사용된 알고리듬이 아니라, 열쇠에 관한 비밀보장에 달려있다.” 아우후스트 케르코프스 폰 니우엔호프 Auguste Kerckhoffs von Nieuwenhof << 군사 암호학 >>에서 “암호의 보안성은 그 암호에 사용된 알고리듬이 아니라, 열쇠에 관한 비밀보장에 달려있다.” 2007 채갑병 RC

카이사르의 이동 사이퍼는 총 25가지의 열쇠가 있다. –너무 적다. 임의의 사이퍼알파벳을 사용한다면 (26!-1)가지의 열쇠중 하나를 선택할수 있다. 25! =15511210043330985984000000 = 1.55 X 10^25 가지 2007 채갑병 RC

열쇠의 단순성 송신자와 수신자사이의 오해의 여지를 줄이기 위해 열쇠의 단순화가 요구된다. 무작위로 사이퍼 알파벳을 구성하는 대신, 송신자는 열쇠를 보조하는 키워드keyword, 혹은 키프레이즈keyphrase를 선택할 수 있다. 2007 채갑병 RC

JULIUS CAESAR 를 키워드로 사용하면, 즉 이를 사이퍼 알파벳의 시작으로 사용할 수 있다. 원문 알파벳 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 U L I S C A E R T V W X Y Z B D F G H K M N O P Q 2007 채갑병 RC

키워드나 키프레이즈를 외우기 쉽다. 따라서 사이퍼 알파벳을 외우기 쉽다. 사이퍼 알파벳을 외우기가 간단하지 않다면 송신자가 이를 종이에 기록해 놓을 가능성이 높아지는데, 이종이가 적의 수중에 들어간다면 이 열쇠를 사용한 모든 암호문의 보안은 깨지는 것이다. 이 방법은 선택할 수 있는 사이퍼 알파벳의 개수가 줄어드는 단점이 있다. 2007 채갑병 RC

아랍의 암호 전문가들 10세기경 칼리프 왕국에서 제작된 행정 지침서 <아다브 알 쿠타브Adab al-kuttab> 에서 크립토그래피를 상세히 다룸 알파벳이외의 특수문자도 사용 글자나 기호, 혹은 두가지를 같이 사용한 사이퍼를 단일 알파벳 대체 사이퍼 monoalphabetic substitution라고 부른다. 암호해독술cryptanalysis 발달 이슬람 문화의 수학 통계학 언어학등 여러 학문분야의 발달이 배경. 2007 채갑병 RC

신학자들이 선지자 모하메트의 코란을 연구하면서 독해술이 발전 단어의 출현 빈도를 비교 9세기 알킨디가지은 <암호문 해독에 관하여> 라는 책에 자세히 나와 있다. 빈도분석 frequency analysis 2007 채갑병 RC

영어 알파벳의 일반적인 출현 빈도 글자 퍼센트 글자 퍼센트 글자 퍼센트 a 8.2 j 0.2 s 6.3 글자 퍼센트 글자 퍼센트 글자 퍼센트 a 8.2 j 0.2 s 6.3 b 1.5 k 0.8 t 9.1 c 2.8 l 4.0 u 2.8 d 4.3 m 2.4 v 1.0 e 12.7 n 6.7 w 2.4 f 2.2 o 7.5 x 0.2 g 2.0 p 1.9 y 2.0 h 6.1 q 0.1 z 0.1 i 7.0 r 6.0 2007 채갑병 RC

출현빈도로 짧은 문장은 해독하기 어려움 더 필요한 힌트들 : 예 : ‘From Zanxibar to Zambia and Zaire, ozone zones make zebras run zany zigzags’ 더 필요한 힌트들 : 서로 같이 나란히 나오는 문자. 자음과 모음 2007 채갑병 RC

숙제 : 다음 문장을 해독하시오. 2007 채갑병 RC

서구의 르네상스 유럽은 암흑시대 800 – 1200년 사이 수도원 : 성서연구 아트바시atbash 히브리어에서 전통적으로 사용하던 암호 – 구약에 사용 각글자가 알파벳 처음으로 부터 몇번째인지를 세어서, 이 글자를 뒤에서 세어 같은 차례에 있는 글자로 대체하는 기술 예) a를 Z로 b를 Y 2007 채갑병 RC

<비밀보장을 위한 기술과 마술의 무효화에 대한 서한> 로저 베이컨 지음 유럽 최초의 암호학에 관한 책 13세기 영국 프란체스코 수도회의 수도사 14세기에는 연금술사와 과학자들이 자신의 발견을 비밀리에 기록하기 위해 암호 발달 15세기 암호는 산업화되어 급성장함 –정치음모들이 유행하면서 비밀통신에 대한 수요 급증 이탈리아 에서 특히 발달 – 도시국가 사이의 경쟁 암호국cipher office 설치 2007 채갑병 RC

프랑스의 필리베르 바부Philibert Babou도 유명 1506년 베네치아의 암호국장 조반니 소로Giovanni Soro는 최초의 암호 해독가로 유명 - 베네치아의 우방국과 바티칸도 가로챈 암호문을 소로에게 해독을 부탁함 프랑스의 필리베르 바부Philibert Babou도 유명 16세기말 프랑수아 비에트Francois Viete:모든 에스파냐의 암호문을 해독함 단일 알파벳 대체 사이퍼와 빈도 분석법의 대결 2007 채갑병 RC

단일 알파벳 대체 사이퍼의 진화 모조 문자 혹은 공백기호Nulls 사용 고의적인 일부 단어의 처자를 잘못쓰는 방법 예) 원문 알파벳을 1부터 99까지의 숫자로 대체 나머지 73개는 아무 의미도 없는 숫자에 불과 고의적인 일부 단어의 처자를 잘못쓰는 방법 예) Thys haz thi ifekkt off dixtaughting thi ballans off frikwenseas == This has the effect of distorting the balance of frequencies 2007 채갑병 RC

단일 알파벳 대체 사이퍼의 진화 코드워드 도입 “코드”란 광범위한 의미에서 의사소통을 비밀로 하는 방법들을 모두 코드라고 부른다. 2007 채갑병 RC

코드code 는 단어나 구를 대체 사이퍼cipher 는 글자를 대체 인사이퍼encipher 인코드encode : 암호화 디사이퍼decipher 디코드decode : 해독 엄밀하게는 구분되어 사용되나 통상적으로 공용 인크립트encrypt 디크립트decrypt : 코드, 사이퍼에 모두 적용 2007 채갑병 RC

코드와 사이퍼 어느것이 보안성이 좋은가 ? 언뜻보기에는 코드가 좋아 보임 그러나, 첫째 둘째 사이퍼 : 송신자와 수신자는 알파벳(열쇠)의 26개 알파벳에 관한 합의가 이루어지면 된다. 코드 : 수천개의 원문 텍스트의 단어들을 대체할 수 있는 코드를 개별적으로 정해야 한다. 코드북 : 수백쪽의 사전과 같을 것이다. 둘째 코드북이 적에게 넘어 갔을 경우 코드북을 다시 만드는 수고를 다시 해야 한다. 사이퍼는 26개의 사이퍼 알파벳만 다시 정하면 된다. 2007 채갑병 RC

16세기 암호제작자들은 코드가 가지고 있는 약점을 인식하고 사이퍼 혹은 노멘클라토르nomenclators를 사용 사이퍼 알파벳을 기본적으로 사용해서 메시지의 대부분을 암호화하면서 몇 개의 코드워드를 첨가하는 방법 그러나 다 허사였다. 2007 채갑병 RC

배빙턴 음모 앤터니 배빙턴Anthony Babington의 메리여왕 구출 작전 영국과 스코트랜드의 캐톨릭과 개신교사이의 투쟁 – 캐톨릭인 프랑스도 한몫 기퍼드라는 이중간첩이 월싱엄경을 도움 감옥안의 메리와의 연락 : 암호 사용 맥주통 마개에 편지를 숨김 :스테가노그라피사용 노멘클라토르 사용 J,v,w를 제외한 알파벳 각 글자들을 대체하는 23개의 기호 , 단어나 구를 대체하는 36개의 기호, 네개의 모조기호, 기호가 같은 글자가 두번 겹치는 중복글자라는 것을 표시하기 위한 기호(시그마 사용) 2007 채갑병 RC

2007 채갑병 RC

결과는 ? 토마스 펠립스에 의해 해독 배빙턴과 그 일당을 체포 메리의 처형 빈도분석법 모조 문자 제거 코드워드를 문맥을 통해 추측 펠립스의 글씨 위조술 배빙턴과 그 일당을 체포 메리의 처형 2007 채갑병 RC