암호이론 1 (Encryption & Decryption) 오세종 1
목차 개요 암호알고리즘의비교 정리 2
개요 정보를안전하게보관, 교환할수있는기본적인방법중의하나가암호화 암호학은가장오래된학문중의하나 전쟁에서명령을안전하게전달하기위한수단으로많이쓰임 2 차세계대전당시의정보전 이번강의를통해암호화에대한기초개념을익히고암호화를통해정보를어느정도까지안전하게보호할수있는지에대해배움 3
개요 송신자 S 가수신자 R 에게전달매체 ( 유, 무선 ) T 를통해어떤메시지를보내고자할때외부침입자 O 에의해당할수있는보안위협 메시지가 R 에게전달되는것을막음 (blocking) 메시지를중간에가로채서내용을읽음 (intercept) 메시지의내용을변조함 ( 수정, 첨가 ) (modify) O 가보내는메시지를마치 S 가보내는것처럼위장함 (fabricate) O S T R 4
개요 용어정의 암호화 (encryption) : 메시지를내용을확인하기어렵도록다른형태로바꾸는것 복호화 (decryption) : 암호화된내용을원래내용으로복원하는것 평문 (plaintext): 암호화가되기이전의메시지 암호문 (ciphertext): 암호화과정을거친메시지 평문 (P) 암호화 (E) 암호문 (C) C = E(P) 복호화 (D) 평문 (P) P = D(C) 5
개요 키를이용한암호화알고리즘 어떤암호화알고리즘은키 (key) 를사용한다. C = E(K, P) 암호화와복호화를위해서로다른키를이용하기도한다. C = E(K E, P), P = D (K D,C) 대칭 (symmetric) 암호화 키평문 암호화 암호문 복호화 평문 비대칭 (asymmetric) 암호화 키1 평문 암호화 키 2 암호문 복호화 평문 6
개요 암호해독 (cryptanalysis) 암호학분야의연구자중에는암호해독을전문으로연구하는사람들이있다. 이들은암호알고리즘을깨뜨리는것을목표로하는데, 그렇게함으로서보다견고한암호알고리즘을만드는데기여한다. 암호해독연구자들의활동 암호화된메시지의해독 암호화된메시지에서어떤패턴을찾아냄으로써복호화알고리즘을유추 암호화알고리즘의약점을연구 7
개요 암호는깨어질수있다 암호화알고리즘은깨어질수있다. 즉, 충분한시간과데이터가주어지면해독알고리즘을찾아낼수있다. 실용성의문제. 해독알고리즘을찾는데얼마의시간이필요한가의문제. 암호를해독하는데두달이걸릴때, 10 12 년이걸릴때 컴퓨팅속도가해가다르게향상되고있고, 병렬, 분산처리등의기술적발전으로현재는안전하다고평가되는알고리즘들이미래에는안전하지않을수있다. 8
단순알파벳암호화 (monoalphabetic cipher) 시이저 (Julius Caesar) 암호 알파벳코드를오른쪽으로 3칸식 shift C i = P i + 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 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 예 ) 메시지 - TREATY IMPOSSIBLE WUHDWB LPSRVVLEOH 9
단순알파벳암호화 (monoalphabetic cipher) 시이저 (Julius Caesar) 암호 ( 계속 ) 장점 : 단순하다. C i = P i + 3 은외우기쉬운규칙이기때문에암호화, 복호화를쉽게할수있다. 단점 : 단순하기때문에알고리즘을유추하는것이용이 10
단순알파벳암호화 (monoalphabetic cipher) 순열 (permutation) 을이용한암호화 순열의예 : π = 1, 3, 5, 7, 9, 10, 8, 6, 4, 2 [ 예 π(3) = 5] 알파벳에 0 25 의숫자를부여 정해진순열을이용알파벳을치환 π(λ) = 25 - λ 를적용하면 a z, b y, c x, 11
단순알파벳암호화 (monoalphabetic cipher) 키 (key) 를이용한암호화 송신자와수신자만아는키를정함 ( 예 : king) 알파벳치환의첫부분에키값을배치 평문 암호문 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 K I N G 나머지부분을키값이아닌알파벳으로채움 ( 외우기쉽게 ) 평문 암호문 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 K I N G A B C D E F H J L M O P Q R S T U V W X Y Z 12
단순알파벳암호화 (monoalphabetic cipher) 암호의해독 암호문 : wklv phvvdjh lv qrw wrr kdug wr euhdn 2,3 글자로된영어단어는드물다 (am, is, to, be, and..) wrr 이런패턴의단어는더드물다 (see, too, add, odd) wrr : see wr : se (X), wrr : too wr : to (ok!) 중간결과 : t--- ------- -- -ot too ---- to ---- ot 로끝나는단어 : cot, dot, got, hot, lot, not, pot, rot 따라서 q 는 n 이다. 이와같은과정반복 공백 (blank) 이단어와단어를구분하는단서 ( 공백을없애거나일정길이로잘라서공백삽입필요 13
단순알파벳암호화 (monoalphabetic cipher) 어떤방법을이용하건단순알파벳암호화는쉽게깨어질수있다. ( 원리 : 문장내에서알파벳의출현빈도가알려짐 ) count percent count percent A B C D E F G H I J K L M 3312 573 1568 1602 6192 966 769 1869 2943 119 206 1579 1500 7.49 1.29 3.54 3.62 14.00 2.18 1.74 4.22 6.65 0.27 0.47 3.57 3.39 N O P Q R S T U V W X Y z 2982 3261 1074 116 2716 3072 4358 1329 512 748 123 727 16 6.74 7.37 2.43 0.26 6.14 6.95 9.85 3.00 1.16 1.69 0.28 1.64 0.04 14
복합알파벳암호화 (polyalphabetic cipher) 단순알파벳암호화의약점은알파벳빈도수가암호문에도그대로반영된다는점 ( 이것을해결할방법은?) 빈도수가높은 t 가어떤때는 a 로어떤때는 x 로암호화된다면이런문제를줄일수있다. 홀수위치 평문 암호문 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 A D G J N O S V Y B E H K N Q T W Z C F I L O R U X 짝수위치 평문 암호문 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 N S X C H M R W B G L Q V A F K P U Z E J O T Y D I 15
자리옮김 (Transposition) 자리옮김은원본메시지의알파벳순서를규칙에따라재배열함으로써, 공격자들에게혼란을일으키고평문메시지를유추하는것을어렵게만드는것을목표로한다. 16
자리옮김 (Transposition) 세로방향자리옮김 (columnar transposition) 메시지를가로방향으로일정자리수로끊어배열한뒤세로방향으로읽는다. C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12.. 17
자리옮김 (Transposition) 세로방향자리옮김 (columnar transposition) 가로배열평문 T H I S I S A M E S S A G E T O S H O W H O W A C O L U M N A R T R A N S P O S I T I O N W O R K S 암호문 TSSOH OANIW HAASO LRSTO IMGHW UTPIR SEEOA MROOK ISTWC NASNS 평문에서어떤열의길이가다른열보다짧으면어떻게하나 18
자리옮김 (Transposition) 세로방향자리옮김 (columnar transposition) 평문 가로배열평문 암호문 평문을모두읽고난후에야암호문작성이시작될수있다. 만일저장공간이 11 Mbyte 이고평문의길이가 5 Mbyte 라면암호화불가능 매우긴메시지를암호화하는데는부적합하다. 19
모르스부호응용 (Fractionated Morse) 모르스부호 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 --.. 사용빈도가높은문자에는 1 자리코드부여 문자와문자사이에는일정간격의시간지연 ( / 로표기 ) 20
모르스부호응용 (Fractionated Morse) 결국모르스부호는., -, / 로구성되어있다. 3 가지기호의모든조합의수는? 3 3 = 27 모든영문자 (26) 를표현하고도남는다 (1) 26 개의조합을순서대로나열한뒤알파벳을할당한다. 송수신자간에약속한키워드를먼저할당하고, 그다음에나머지문자들을할당한다. 키워드를 wovenflax 라고가정 21
모르스부호응용 (Fractionated Morse) 알파벳할당테이블 W... O..- V../ E.-. N.-- F.-/ L./. A./- X.// B -.. C -.- D -./ G --. H --- I --/ J -/. K./- M.// P /.. Q /.- R /./ S /-. T /-- U /-/ Y //. Z //- 22
모르스부호응용 (Fractionated Morse) (2) 평문을모르스부호로바꾼다. ( 모르스부호표참조 ) 평문 : FRACTIONATED MORSE 모르스부호표현..-./.-./.-/-.-./-/../---/-./.-/ -/./-..//--/---/.-./.../. (3) 모르스부호표현을 3 자리씩끊어서묶는다...-./. -./.-/ -.-./- /.. /-- -/-./. -/- /./ -.. //- -/- --/.-. /.../. 23
모르스부호응용 (Fractionated Morse) (4) 알파벳할당테이블을참조하여대응하는알파벳문자를기록한다. 암호문완성 평문..-./. -./.-/ -.-./- /.. /-- -/-./. O L D F C A P T K L -/- /./ -.. //- -/- --/.-. /.../. K R B Z K I E P L : FRACTIONATED MORSE 암호문 : OLDFCAPTKLKRBZKIEPL 24
암호알고리즘의비교 앞에서살펴본알고리즘들은두그룹으로분류될수있다 스트림암호화 (stream cipher) 예 ) 단순알파벳암호화알고리즘 ISSOPMI.. ascsdcs.. ( 평문 ) 암호화 ( 암호문 ) 블록암호화 (block cipher) 예 ) 치환, 모르스부호응용알고리즘 XN OI TP YR ( 평문 ) 암호화 ( 암호문 ) 25 po Ba Kd nw
암호알고리즘의비교 스트림암호화 장점 단점 빠른암호화속도 에러파급효과가적다 평문의특성 ( 예 : 문자출현빈도..) 이암호문에도그대로반영 악의적공격자에의해쉽게내용의첨가, 변경이가능 26
암호알고리즘의비교 블록암호화 장점 단점 평문에혼돈성을주어해독을어렵게함 한번만들어진암호문은내용추가, 변경이어렵다. 암호화속도가느림 암호화시에러의파급효과가크다. 27
정리 암호화는통신상에서정보를보호할수있는가장기본적인방법 안전한암호알고리즘을개발하려는노력이지금도진행되고있다. 암호화는통신시간 + 암호화 / 복호화시간을요구하기때문에시간적비용을요구 ( 안전한알고리즘일수록암호화, 복호화시간이길어지는경향이있다.) 28
참고문헌 C.P.Pfleeger, Security in Computing, second edition, Prentice-Hall International Inc.,1997. (chapter 2) 29