PowerPoint Template

Size: px

Start display at page:

Download "PowerPoint Template"

익태 시
5 years ago
Views:

1 SeoulTech UCS Lab st 현대암호학 제 3 장암호의역사 박종혁교수 Tel: jhpark1@seoultech.ac.kr

2 1절시저암호 2절단읷치환암호 3절다중치환암호 4절에니그마 5절전치암호와치환암호 6절암호알고리즘과키 2

3 제 1 절시저암호 1.1 시저암호란? 1.2 시저암호의암호화 1.3 시저암호의복호화 1.4 전사공격에의한해독 3

4 1.1 시저암호란? 시저암호 (Caesar cipher) 줄리어스시저 ( 유리우스케사르 ) 가사용하였다는암호 평문으로사용되는알파벳을일정한문자수만큼 평행이동 시킴으로써암호화 4

5 알파벳 3 문자평행이동 5

6 1.2 시저암호의암호화 평문 : kabsoonyee 암호문 : NDeVRRQBHH 6

7 시저암호에의한암호화 7

8 1.3 시저암호의복호화 암호화때와동일한크기의역방향평행이동 8

9 시저암호에의한복호화 9

10 1.4 전사공격에의한해독 암호문 NDeVRRQBHH 을보고다른정보없이도 kabsoonyee 라는메시지를맞출수는없을까? 영어알파벳은 26 문자이므로암호화키는 0 에서 25 까지 26 가지 전사공격 (brute-force attack) 키가될수있는모든가능한후보들을시도해보는방법 10

11 시저암호문에대한전사공격 11

12 제 2 절단읷치환암호 2.1 단읷치환암호란무엇읶가? 2.2 단읷치환암호의암호화 2.3 단읷치환암호의복호화 2.4 단읷치환암호의키공간 2.5 빈도붂석에의한해독 12

13 2.1 단읷치환암호란무엇읶가? 단일치환암호 (simple substitution cipher) 평문을구성하는알파벳을다른알파벳으로변환하는암호 시저암호는단일치환암호 13

14 단읷치환암호의치환표 ( 예 ) 14

15 2.2 단읷치환암호의암호화 평문 : kabsoonyee 를암호화해보자 암호문 : SWYLBBNKXX 약점 평문에등장하는문자의빈도가암호문으로바뀐뒤에도암호문내에서동일한빈도로나타난다 15

16 2.3 단읷치환암호의복호화 치환표가단일치환암호의 키 암호화때에사용한치환표가필요 송신자와수신자는치환표를공유 16

17 2.4 단읷치환암호의키공간 시저암호는전사공격으로해독가능 단일치환암호는전사공격으로해독이어렵다 단일치환암호가시저암호에비해훨씬많은키후보를가질수가있기때문 17

18 키공간 키공간 (key space) 해당암호에서사용할수있는 모든키의집합 이키공간에속하는가능한키의총수를키공간의크기 키공간이크면클수록전사공격은어렵다 단일치환암호의키의총수 ㆍㆍㆍ 1 =

19 전사공격시간 ㆍㆍㆍ 1 = 키수가이렇게많다면 1 초에 10 억개의키를적용하는속도로조사한다고해도, 모든키를조사하는데 120 억년이상의시간이필요 19

20 2.5 빈도붂석에의한해독 전사공격에서단일치환암호를해독하는것은어렵다 빈도분석암호해석법을사용하면단일치환암호도해독할수있다 빈도분석에서는평문에등장하는문자의빈도와암호문에나오는문자의빈도가일치하는것을이용하는것이다. 20

21 2.5 빈도붂석을이용한암호해독 A good glass in the bishop's hostel in the devil's seat forty-one degrees and thirteen minutes northeast and by north main branch seventh limb east side shoot from the left eye of the death's-head a bee line from the tree through the shot fifty feet out. - 애드가앨런포우 황금벌레 21

22 소설에등장한빈도붂석 빈도분석방법은소설에등장 에드가앨런포우의 황금벌레 아서코난도일의 셜록홈즈이야기, 춤추는남자의모험 22

23 소설속의암호 23

24 최초의빈도붂석에대한자료 최초의기록으로남아있는빈도분석에대한내용은 9 세기 암호문해독에관한논고 에등장하는아랍의현학자알킨디 (al- Kindi) 에의해제안 24

25 빈도붂석을이용한암호해독 암호문 MeYLGVIWAMeYOPINYZGWYeGMZRUUYPZAIXILGVSIZZMPGKKD WOMePGROeIWGPCeIPAMDKKeYCIUYMGIFRWCeGLOPINYZHRZM PDNYWDWOGWITDWYSeDCeeIAFYYWMPIDWYAGTYPIKGLMXFPI WCeHRZMMeYMeDWOMGQRYWCeUXMeDPZMQRGMeeYAPISDWO FICJILYSNICYZeYMGGJIPRWIWAIHRUNIWAHRZMUDZZYAMeYFRW CeMRPWDWOPGRWAIOIDWSDMeIGWYMSGMePYYeYHRUNYARNF RMSDMeWGOPYIMYPZRCCYZZIOIDWIWAIOIDWeYMPDYAILMYPM eymwunmdwougpzykfrmimkizmeiamgodtydmrniwasikjyai SIXSDMeeDZWGZYDWMeYIDPZIXDWODIUZRPYMeYXIPYZGRPDM DZYIZXMGAYZNDZYSeIMXGRCIWWGMOYM 25

26 암호문속의영어알파벳출현빈도표 문자개수문자개수문자개수문자개수문자개수 I 47 개 G 27 개 C 12 개 F 7 개 V 2 개 Y 47 개 Z 27 개 S 11 개 L 6 개 B 0 개 M 45 개 P 26 개 N 10 개 H 5 개 W 35 개 R 22 개 U 10 개 J 3 개 e 33 개 A 17 개 K 8 개 T 3 개 D 30 개 O 16 개 X 8 개 Q 2 개 26

27 영어알파벳출현빈도 27

28 최빈도를갖는문자를 e 로변환 MEeLGVIWAMEeOPINeZGWeEGMZRUUePZAIXILGVSIZZMPGKKDWO MEPGROEIWGPCEIPAMDKKEeCIUeMGIFRWCEGLOPINeZHRZMPDN ewdwogwitdwesedceeiafeewmpidweagtepikglmxfpiwcehr ZMMEeMEDWOMGQReWCEUXMEDPZMQRGMEEeAPISDWOFICJILeS NICeZEeMGGJIPRWIWAIHRUNIWAHRZMUDZZeAMEeFRWCEMRPWD WOPGRWAIOIDWSDMEIGWeMSGMEPeeEeHRUNeARNFRMSDMEWG OPeIMePZRCCeZZIOIDWIWAIOIDWEeMPDeAILMePMEeMWUNMDWO UGPZeKFRMIMKIZMEIAMGODTeDMRNIWASIKJeAISIXSDMEEDZWGZ edwmeeidpzixdwodiuzrpemeexipezgrpdmdzeizxmgaezndze SEIMXGRCIWWGMOeM 28

29 영어의 the 점검 thelgviwatheopinezgwehgtzruuepzaixilgvsizztpgkkdwothpg ROhIWGPChIPAtDKKheCIUetGIFRWChGLOPINeZHRZtPDNeWDWOG WITDWeShDChhIAFeeWtPIDWeAGTePIKGLtXFPIWChHRZtthethDWOt GQReWChUXthDPZtQRGthheAPISDWOFICJILeSNICeZhetGGJIPRWI WAIHRUNIWAHRZtUDZZeAtheFRWChtRPWDWOPGRWAIOIDWSDthIG WetSGthPeeheHRUNeARNFRtSDthWGOPeItePZRCCeZZIOIDWIWAIOI DWhetPDeAILtePthetWUNtDWOUGPZeKFRtItKIZthIAtGODTeDtRNIWA SIKJeAISIXSDthhDZWGZeDWtheIDPZIXDWODIUZRPetheXIPeZGRPDt DZeIZXtGAeZNDZeShItXGRCIWWGtOet 29

30 익숙한단어추측 thelgviwatheorinezgwehgtzruuerzaixilgvsizztrgkkdwothrgr OhIWGrChIrAtDKKheCIUetGIFRWChGLOrINeZHRZtrDNeWDWOGWIT DWeShDChhIAFeeWtrIDWeAGTerIKGLtXFrIWChHRZtthethDWOtGQRe WChUXthDrZtQRGthheArISDWOFICJILeSNICeZhetGGJIrRWIWAIHRU NIWAHRZtUDZZeAtheFRWChtRrWDWOrGRWAIOIDWSDthIGWetSGthr eehehrunearnfrtsdthwgoreiterzrccezzioidwiwaioidwhetrdea ILterthetWUNtDWOUGrZeKFRtItKIZthIAtGODTeDtRNIWASIKJeAISIXSD thhdzwgzedwtheidrzixdwodiuzrrethexirezgrrdtdzeizxtgaeznd ZeShItXGRCIWWGtOet 30

31 단어패턴 thethdwg 라는패턴이보인다. 이것은 the thing 일지도모른다 (D i, W n) grine 라는패턴이보인다. 사전을찾아보았더니, grace, grade, grape, grate, grave, gripe, grofe, 처럼많은후보가있다. 이것으로는결정을할수없다. I a 를가정해보면 greater 라는패턴이나오므로 I a 는맞는것같다. 하지만, N c 를가정하면 tricening 라는패턴이나왔다. 이런단어는영어단어에없는것같다. 따라서 N c 는잘못일지도모른다. 31

32 빈도추측 빈도가높은문자중아직가정에등장하지않은문자는 o 이다 한편암호문중에등장하는빈도가높은문자로서아직모르는것은 G 와 Z G o 를가정 thelovanathegranezonehotzruuerzaaxalovsazztrokkingthrorgha norcharatikkhecauetoafrncholgranezhrztrineningonatineshichh aafeentraineaoterakoltxfranchhrztthethingtoqrenchuxthirztqro thhearasingfacjalesnacezhetoojarrnanaahrunanahrztuizzeat hefrnchtrrningrornaagainsithaonetsothreehehrunearnfrtsithno greaterzrccezzagainanaagainhetrieaalterthetnuntinguorzekfrtat KaZthaAtogiTeitRNanASaKJeAaSaXSithhiZnoZeintheairZaXingiaUZRr ethexarezorritizeazxtoaeznizeshatxorcannotget 32

33 패턴 끝에 Cannotget 이라는패턴이등장했다. C c 가틀림없다. C c 라는것을통해조금전에생각한 N c 는역시잘못이라는것을알수있다 thelovanathegranezonehotzruuerzaaxalovsazztrokki ngthrorghanorcharatikkhecauetoafrncholgranezhrztr ineningonatineshichhaafeentraineaoterakoltxfranchh RZtthethingtoQRenchUXthirZtQRothheAraSingFacJaLeSN acezhetoojarrnanaahrunanahrztuizzeathefrnchtrrn ingrornaagainsithaonetsothreehehrunearnfrtsithnogr eaterzrccezzagainanaagainhetrieaalterthetnuntinguorz ekfrtatkazthaatogiteitrnanasakjeaasaxsithhiznozeint heairzaxingiauzrrethexarezorritizeazxtoaeznizeshatx orcannotget 33

34 패턴 Shich 라는패턴이보인다. 이것은 which 일것이다 (S w). 34

35 빈도가낮은문자추측 thethingtoqrench 라는패턴이찾아졌다. 이것은분명히 the thing to QRench 이다. 사전을찾아보니 quench 라는단어가있었다 (Q q, R u). quench 라는것은 갈증을해소하다 라는의미이다. 마시는것에관한이야기가아닐까? hotzuuuer 라는패턴이찾아졌다. 이것은 hot summer 일것이다 (Z s, U m). U 가두개연속해있다는것이큰실마리였다. 갈증을해소하다 라는문맥과도일치한다. 35

36 빈도가낮은문자추측 thelovanathegranesonehotsummersaaxalovwasstrokkingthroug hanorcharatikkhecametoafuncholgraneshustrineningonatinewhi chhaafeentraineaoterakoltxfranchhustthethingtoquenchmxthirst quothhearawingfacjalewnaceshetoojarunanaahumnanahustmis seathefunchturningrounaagainwithaonetwothreehehumneaunfut withnogreatersuccessagainanaagainhetrieaalterthetnmntingmorse KFutatKasthaAtogiTeituNanAwaKJeAawaXwithhisnoseintheairsaXin giamsurethexaresouritiseasxtoaesnisewhatxoucannotget 36

37 단어와내용추측 sucessagainanaagain 라는패턴이있다. 이것은 success again and again 일것이다 (A d). triedalter 라는패턴이보인다. 이것은틀림없이 tried after 이다 (L f). whatxoucannotget 라는패턴이보인다. 이것은 what you cannot get 일것이다 (X y). thefovandthegranesonehotsummersdayafovwasstrokk ingthroughanorchardtikkhecametoafunchofgraneshus trineningonatinewhichhadfeentrainedoterakoftyfranc hhustthethingtoquenchmythirstquothhedrawingfacjafe wnaceshetoojarunandahumnandhustmissedthefunch turningroundagainwithaonetwothreehehumnedunfutwi thnogreatersuccessagainandagainhetriedafterthetnmnt ingmorsekfutatkasthadtogiteitunandwakjedawaywith hisnoseintheairsayingiamsuretheyaresouritiseasytodes Nisewhatyoucannotget 37

38 정리 thefoxandthegrapesonehotsummersdayafoxwasstrokkingthroughano rchardtikkhecametoafunchofgrapeshustripeningonatinewhichhadfe entrainedoterakoftyfranchhustthethingtoquenchmythirstquothhedra wingfacjafewpaceshetoojarunandahumpandhustmissedthefunchtu rningroundagainwithaonetwothreehehumpedupfutwithnogreatersucc essagainandagainhetriedafterthetnmptingmorsekfutatkasthadtogitei tupandwakjedawaywithhisnoseintheairsayingiamsuretheyaresouritise asytodespisewhatyoucannotget 38

39 정리 foxwasstrokking fox was strolling (K l) hetoojarunandahumpandhustmissed he took a run and a jump and just missed (H j) (J k) hejumpedupfutwithnogreatersuccess he jumped up but with no greater success (F b) butatlasthadtogiteitup but at last had to give it up (T v) 이암호문에나오지않은마지막 1 문자 (B z) 39

40 단어와내용추측 thefovandthegranesonehotsummersday 라는패턴이있다. 이것은틀림없이 the fox and the grapes one hot summers day(v x, N p) 일것이다. 40

41 치환표 41

42 해독된평문 thefoxandthegrapesonehotsummersdayafoxwasstrollingthroughanorc hardtilhecametoabunchofgrapesjustripeningonavinewhichhadbeentra inedoveraloftybranchjustthetoquenchmythirstquothhedrawingbackafe wpaceshetookarunandajumpandjustmissedthebunchturningroundaga inwithonetwothreehejumpedupbutwithnogreatersuccessagainandagai nhetriedafterthetemptingmorselbutatlasthadtogiveitupandwalkedaway withhisnoseintheairsayingiamsuretheyaresouritiseasytodespisewhaty oucannotget 42

43 띄어쓰기 이솝우화 에나오는 여우와포도 이야기 "The Fox and the Grapes" One hot summer's day, a Fox was strolling through an orchard till he came to a bunch f grapes just ripening on a vine which had been trained over a lofty branch. "Just the to quench my thirst, "quoth he. Drawing back a few paces, he took a run and a jump, and just missed the bunch. Turning round again with one, two, three, he jumped up, but with no greater success. Again and again he tried after the tempting morsel, but at last had to give it up, and walked away with his nose in the air, saying: "I am sure they are sour." It is easy to despise what you cannot get. 43

44 해독작업 빈도가높은문자뿐만아니라빈도가낮은문자도단서가된다. 처음과끝을아는것은단서가된다. 단어의단락을알면그것도단서가될수있다. 암호문이길면해독이쉬워진다. 같은문자가연속해서나타나면그것은단서가된다 ( 단일치환암호에서는어떤문자어느문자로암호화되는지는정해져있기때문에 ). 해독의속도가점점빨라진다. 44

45 3. 다중치환암호 단일치환암호의약점 평문과암호문간의단순대응을사용하기때문에평문의단일문자에대한빈도가그대로암호문에반영된다. 따라서암호해독자로하여금빈도분석을어렵게하기위해서는암호문에나타나는문자들의빈도를거의균등하게만드는암호를이용하는것이바람직하다. 45

46 3. 다중치환암호 다중치환을이용하여문자의발생빈도를균일화한다. 다중치환암호방법의대표적인예 비제네르 (Vigenere) 암호 힐 (Hill) 암호. 46

47 치환기법 Hill 암호기법 각문자에정수값을부여하고 m 개의문자를치환 M=3 개는 3 개의문자를치환하는방법 C1 = (k11 p1 + k12 p2 + k13 p3 ) mod 26 C2 = (k21 p1 + k22 p2 + k23 p3 ) mod 26 C3 = (k31 p1 + k32 p2 + k33 p3 ) mod 26 C: 암호문 P: 평문 k: 키 47

48 치환기법 암호문형식을열벡터와행렬로표현 C1 K11 K22 K13 P1 C2 = K21 K22 K23 P2 C3 K31 K32 K33 P3 암호화사례 평문 : PAYMOREMONEY 암호키 48

49 치환기법 암호문계산 C1 C2 C3 = K11 K22 K13 K21 K22 K23 K31 = K32 K33 P1 P2 P3 평문을숫자변환 PAYMOREMONEY : P 15, A 0, Y 24, 숫자대입암호문치환 K( ) + ( ) mod 26 = ( ) = LNS C1 = 17 x x x 24 = 375 mod 26 = C2 = 21 x x x 24 = 819 mod 26 = C3 = 2 x x x 24 = 486 mod 26 =

50 치환기법 50

51 치환기법 다중단일문자치환암호기법 관련된단일문자치환규칙들의집합을사용함 주어진변환에사용될특정규칙은키에의해결정됨 대표적인 Vigenere 암호방식 행렬표를구성 키문자 x 와평문자 y 가주어지면암호문자는 x 행 y 열의암호문 V 키 : deceptive 평문 : we are discovered save yourself 51

52 현대 VIGENRE 표 52

53 제 3 절다중치환암호 3.1 빈도분석이가능한가? 53

54 3.1 빈도붂석이가능한가? 빈도분석이가능했던이유는평문에등장하는문자의빈도와암호문에등장하는문자의빈도가일치하기때문 다중치환암호 (polyalphabetic substitution cipher) 평문에등장하는문자의빈도와암호문에등장하는문자의빈도를다르게만드는암호알고리즘 비장느르암호 (Vigenere Cipher) 에니그마기계 (Enigma machine) 빈도분석을이용한공격방법이무용지물 54

55 제 4 절에니그마 4.1 에니그마란무엇읶가? 4.2 에니그마에의한암호통신 4.3 에니그마의구조 4.4 에니그마의암호화 4.5 날자별키와통신키 4.6 통신오류의회피 4.7 에니그마의복호화 4.8 에니그마의약점 4.9 에니그마의해독 55

56 4.1 에니그마란무엇읶가? 에니그마 (enigma) 독일의세르비우스 (Arthur Scherbius) 가 20 세기초에발명한암호화 / 복호화를수행하는기계 에니그마는독일어로 수수께끼 를의미 회전하는원반과전기회로를써서강력한암호를만들고자시도 발명당시에는에니그마를상용으로사용 나치독일시대에는군용으로사용하려고개량 56

57 에니그마와로터 57

58 4.2 에니그마에의한암호통신 타이프라이터와톱니바퀴와전지와전구를조합한기계 암호화와복호화를 1 대의기계로수행 송신자와수신자는각각에니그마를 1 대씩소유 58

59 코드북과코드북의내부 코드북에는송 / 수신자가사용하는날짜별키가기록되어있고, 송신자 / 수신자는이책자의지시에따라에니그마를설정 59

60 4.3 에니그마의구조 에니그마는알파벳 26 문자를암호화 / 복호화할수있지만, 그림이복잡하기때문에여기서는알파벳의수를 4 문자로가정 60

61 에니그마암호통신흐름 61

62 로터 로터 (rotor) 로터는앞과뒤의단자가전선으로연결되어있는원반모양의부품 로터하나하나의연결선은바꿀수는없지만, 문자를입력할때마다자동으로회전 하나의문자를입력하면로터 1 이 1/4 회전한다 ( 알파벳의수를 4 문자로했을경우 ). 로터 1 이 1 회전하면로터 2 가 1/4 회전하고, 로터 2 가 1 회전하면로터 3 이 1/4 회전 62

63 로터 63

64 에니그마의구조 (4 문자 ) 64

65 secretletter 를암호화하기 65

66 4.4 에니그마암호화 평문 : secretletter 를암호화하여송신하기 에니그마설정 통신키의암호화 암호화된통신키메모 에니그마의재설정 메시지의암호화 결합 66

67 4.5 날짜별키와통신키 날짜별키는메시지의암호화가아니라통신키의암호화에사용 날짜별키는 키를암호화하기위한키 이와같은키를키암호키 (key encrypting key; KEK) 라한다 메시지를통신키로암호화하고, 통신키를날짜별키로암호화하는 2 단구조 67

68 4.6 통신오류의회피 통신키 uat 를 2 회연속해서 uatuat 라고입력 당시무선기술수준이낮아서통신이제대로되지않는경우가많이있었기때문 68

69 4.7 에니그마의복호화 69

70 4.8 에니그마의약점 통신키를 2 회반복한것을암호화한다 통신키를선택한것이사람이다 코드북을배송하지않으면안된다 70

71 4.9 에니그마의해독 에니그마의설계는 숨기는것에의한보안 (security by obscurity) 에의존하지않음 폴란드의암호해독자르예프스키 날짜별키에의한암호문으로부터날짜별키를간파하는방법을고안 영국의암호해독팀은블레츨리파크에모여에니그마의해독 71

72 제 5 절전치암호와치환암호 5.1 전치암호 5.2 치환암호 72

73 5.1 전치암호 전치암호 (transpositon cipher) 전치란평문에서사용하는문자의집합과암호문에서사용하는문자의집합이동일 문자집합내부에서 자리를바꾸는규칙 평문에사용된문자와암호문에사용된문자가일대일대응규칙 시저암호 73

74 5.2 치환암호 치환암호 (substititution cipher) 치환암호의엄밀한의미는평문에서사용하는문자의집합과암호문에서사용하는집합이다를수있다 평문문자를다른문자로 교환하는규칙 교환규칙이일대일대응이아니어도무방 비장느르암호 모든전치암호는치환암호 74

75 제 6 절암호알고리즘과키 6.1 암호알고리즘과키를붂리하는이유 75

76 암호알고리즘과키 암호명암호알고리즘키 시저암호 평문의각문자를 지정한문자수 만큼평행이동한 다. 평행이동하는문자수 단일치환암호치환표에따라알파벳을변환한다. 치환표 에니그마 ( 통신키의암호화 ) 에니그마의기계를써서 플러그보드의연결선, 3 장의로터의순서, 각로터의설치각도 에따라알 파벳을변환한다. 플러그보드의연결선 3 장의로터순서 각로터의설치각도 에니그마 ( 통신문의암호화 ) 플러그보드의연결선과 3 장의로터의순서를고정한 에니그마기계를사용하여 각로터의설치각도 에따라알파벳을변환한다. 각로터의설치각도 76

77 암호알고리즘 과 키 를붂리 77

78 6.1 암호알고리즘과키를붂리하는이유 암호알고리즘안에는변경가능한부분 이반드시포함 변경가능한부분 이 키 에해당 78

79 Q & A 79

80 Thank You! 80

Microsoft PowerPoint - chap02.ppt

Microsoft PowerPoint - chap02.ppt 2010-1 학기현대암호학 2 장암호의역사 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 2.0 주요내용 암호 시저암호 단일치환암호 애니그마 암호해독법 전사공격 (brute force attack) 빈도분석 알고리즘과키의관계 2 2.1 시저암호 단순한암호인시저암호를소개 3 2.1.1 시저암호란 시저암호 (Caesar cipher)