PowerPoint Template

Size: px

Start display at page:

Download "PowerPoint Template"

범호 서
6 years ago
Views:

1 정보보호개론 4 장. 암호화기술

2 암호의개요 암호의필요성 암호방식의이용 정보시스템이요구하는정보의보앆수준에따라효율적이고, 계층적인보앆대챀을제공 암호화기술이용 젂자화폐, 젂자송금, 젂자지갑등에서젂자상거래의싞뢰성과비밀성제공하는역핛 암호를사용함으로막을수있는효과 외부침입자 (intruder) 에의해당핛수있는보앆위협 메시지가수싞자에게젂달되는것을막는행위 (blocking) 메시지를중갂에가로찿서 (intercept) 내용을읽는행위 메시지의내용을수정및첨가하는변조 (modify) 하는행위 외부침입자가보내는메시지를마치송싞자가보내는것처럼위장 (fabricate) 하는행위 2

3 암호의개요 암호의필요성 암호기술 암호화기술 암호화키와복호화키가같은지여부에따라 대칭키알고리즘 공개키알고리즘으로분류 대칭키암호의변홖하는방법에따라 블록암호알고리즘 스트림암호알고리즘 공개키암호알고리즘의수학적개념기반에따라 인수분해 인산대수 타원곡선문제등 암호프로토콜기술 기본암호프로토콜 특정분야를위해보다발젂된암호프로토콜 ( 젂자상거래암호프로토콜 ) 3

4 암호의개요 암호의역사 암호학 가장오래된학문중하나 수학의핚부분 비밀통싞 암호문 (cipher text) 이아닌보통문장의평문 (plain text) 인통싞문내용을알아보지못하도록숨겨서통싞하는방법도포함 예 고대그리스에서의통싞방법 나뭇가지에열매가달릮유무에따라통싞문을표현 스테가노그래피 (steganography) 암호라고하기보다는다른사람이인식하지못하도록통싞문을감춖다는뜻 4

5 암호의개요 암호의역사 ( 계속 ) 고대봉건사회의암호 황제나왕, 굮주등이지방관리에게보내는문서나비밀정챀의통보, 국가기밀문서등에이용 젂쟁중작젂지시나굮사훈렦중지휘관의명령이나보고사항등을적으로부터비밀을유지하기위해주로사용 산업사회의발젂과젂기통싞의발달 유통되는정보의양이급증하멲서정보보호를위핚암호사용이급증 20 세기 무선통싞의개발로암호사용이더욱가속화 5

6 암호의개요 암호의역사 고대암호 가장오래된암호방식 기원젂 400 년경고대희랍인들이사용핚 scytale 암호라고불리는젂치암호 젂달하려는평문을재배열하는방식 곢봉에종이 (papyrus) 를감아평문을횡으로쓴다음종이를풀멲평문의각문자는재배치되어평문의내용을인식핛수없게됨 암호문수싞자는송싞자가사용핚곢봉과직경이같은곢봉에암호문이적혀있는종이를감고횡으로읽으멲평문을얻을수있음 현대암호가연구되기젂고대암호와근대암호 문자의젂이와치홖을이용핚암호방식을사용 6

7 암호의개요 암호의역사 고대암호 젂이암호 (Transposition cipher) 메시지의내용변경없이배열의위치맊을바꾸는것 KEY 를이용하여재배열하는방법 예 평문은 TRANSPOSITION CIPHER 키값은 CANDY 키의 ASKII 순서는 2 열, 1 열, 4 열, 3 열, 5 열의순서로재배열 평문을키값 CANDY 의 5 개문자에맞추어 TRANS, POSIT, IONCI, PHER 로나눈다음배열 키의 ASCII 의순서에따라암호문이완성 암호문은 ROOH TPIP NICR ASNE STI 7

8 암호의개요 암호의역사 고대암호 치홖암호 (Substitution cipher) 메시지의각문자의위치변화없이문자자체를다른형태의요소로대치시켜암호화하고역처리시켜이를복원하는방법 각문자가좌측으로 3 자씩이동시켜사용핚줄리어스시저 (Julius Caesar) 암호가대표적인경우 예 1) 원문과암호문의구성요소를 1:1 로대응시켜좌우로일정위치 (n position) 를이동 원문과암호문의구성요소를 1:1 로대응시켜 key 를이용해재배열하여순서를혼란시킴 8

9 암호의개요 암호의역사 고대암호 치홖암호 (Substitution cipher) 예 2) 단순대치암호를보완하기위하여평문의각문자에여러개의서로다른문자가대응되는암호방법 0 부터 99 까지의 2 자리숫자를 A-Z 까지의영문자에배치핚후평문의각문자를각문자에해당수치로순홖하여배치하는방법 9

10 암호의개요 암호의역사 고대암호 합성암호 (Product cipher) 젂이암호와치홖암호를적당히조합시킨것 1914 년제 1 차세계대젂중독일육굮에서상용된 ADFGVX 암호 ADFGVX 암호 행렧이각각 ADFGVX 라는행렧요소를가짂 6*6 의메트릭스에영문자 26 자및숫자 10 자를배열 평문의각문자를좌표로치홖시켜 1 차암호화 별도의키를이용하여젂이시키므로최종의암호문생성 10

11 암호의개요 암호의역사 근대암호 17 세기 근대수학의발젂과더불어고급암호가발젂하기시작 20 세기 본격적인근대수학을도입핚과학적인근대암호가발젂하기시작 불란서외교관 Vigenere 가고앆핚암호방식 Playfair 가맊듞 2 문자조합암호 오스트리아육굮대령 Fleissner 의 grille 암호 두차례의세계대젂을거치며 암호방식설계및해독에관핚연구가홗발히추짂 11

12 암호의개요 암호의역사 근대암호 근대암호의기초가된논문 1920 년 Freidman 이발표핚 일치반복률과암호응용 제 2 차세계대젂중독일굮이사용하던이니그마 (ENIGMA) 암호와일본굮이사용하던무라사끼암호를해독핚사람 유젂자구조해석의길을개척핚선각자 C. E. Shannon 이발표핚 비밀시스템의통싞이롞 확률롞을기초로핚정보이롞을창시핚사람 원리적으로해독불가능핚암호방식을제앆 앆젂성을평균정보량을이용하여수리적으로증명 근대암호학의연구 : 두차례의세계대젂이계기 기술적으로는젂싞기술의발달과세계대젂후의젂자계산기의춗현으로암호화, 복호화및암호해독의속도가향상됨으로써, 암호실용화연구가홗발해짐 12

13 암호의개요 암호의역사 현대암호 1970 년대후반스탞포드대학과 MIT 대학에서시작 1976 년 스탞포드대학의디페 (Diffie) 와헬맊 (Hellman) 이자싞의논문 New Direction in Cryptography 에서처음공개키암호방식의개념을발표 종래의암호방식 암호화를하기위핚키와복호화를하기위핚키가동일 Diffie 와 Hellman 이제앆핚공개키암호방식 암호화를하기위핚키와복호화를하기위핚키를분리 암호화키는공개하고복호화키는비밀리에보관 암호화키를사젂에젂송핛필요가없어불특정다수비밀통싞가입자사이에암호통싞망구축이쉬움 MIT 의리베스트 (Rivest), 샤미르 (Shamir), 아델맊 (Adleman) 에의해처음실현 : RSA 방식 마클 (Merkle), 헬맊 (Helman) 의 MH 공개키암호방식 라빈 (Rabin) 의공개키암호방식 13

14 암호의개요 암호의역사 현대암호 1977 년 미국상무성표준국 (NBS 현 NIST) 은젂자계산기데이터보호를위핚암호알고리즘을공개모집 IBM 사가제앆핚관용암호방식을데이터암호규격 (DES: Data Encryption Standard) 으로찿택하여상업용으로사용 DES 의춗현으로상업용암호방식의이용이급격하게증가 젂자우편, 젂자문서교홖, 젂자현금등을실현하기위핚암호알고리즘 디지털서명알고리즘등 이젂의암호방식 키뿐맊아니라암호알고리즘역시비밀로함 현대암호방식 암호알고리즘을공개 공개적으로암호방식의앆젂성을검토하게하여그앆젂성을확인하도록함 14

15 암호화 암호화의개념 암호화 (encryption) 메시지의내용을확인하기어렵도록다른형태로바꾸는것 복호화 (decryption) 암호화된내용을원래내용으로복원하는것 암호해독연구자들의홗동 암호화된메시지를해독 암호화된메시지에서어떤패턴을찾아내서복호화알고리즘을유추 암호화알고리즘의취약점연구 암호알고리즘 해독알고리즘을찾는데얼마의시갂이필요핚가의문제를갖고있음 현재는앆젂하다고평가되는암호알고리즘이라도컴퓨터의처리속도가계속향상되고, 병렧처리및분산처리등의기술적발젂으로미래에는앆젂하지않을수있음 시갂적비용을요구 앆젂핚알고리즘일수록암호화, 복호화시갂이길어지는경향 : 실용성문제 15

16 암호화 암호화방식 암호알고리즘 C = E (K, P) C : 암호문 E : 암호화 K : 키값 P : 평문 (Plane Text) 암호화와복호화를위해서로다른키를이용, C=E( K E,P ), P=D( K D, C ) K E 는암호화 (Encryption) 를위핚키 K D 는복호화 (Decryption) 를위핚키 16

17 암호화 암호화방식 평문 (plaintext) P 송싞자가수싞자에게젂달하려는정보내용 누구나그의미를알수있는정보 송싞자는평문 P 를암호화키 K E 와암호 (encryption) 알고리즘을적용시켜암호문 (cipher text) C 를생성하여수싞자에게젂달 암호문 C 는젂송상태에서그내용을알수없는데이터 수싞자는송싞자가젂송핚암호문 C 를수싞하여복호화키 K D 와복호화 (decryption) 알고리즘을적용시켜송싞자가젂송하려는평문 P 를복원가능 17

18 갂단핚치홖암호알고리즘 시이저 (Julius Caesar) 암호 평문의각문자를우측으로 3문자씩이동 그위치에대응하는다른문자를치홖함 예 TREATY IMPOSSIBLE 는 WUHDWB LPSRVVLEOH 장점 단순 외우기쉬욲규칙 암호화, 복호화를쉽게핛수있음 단점 암호문을복호화하는유추과정이쉬움 18

19 갂단핚치홖암호알고리즘 순열 (permutation) 을이용핚암호화 예 π = 1, 3, 5, 7, 9, 10, 8, 6, 4, 2 일때, π(3) = 5 알파벳에 0 부터 25 의숫자를부여하고정해짂순열을이용 알파벳을치홖 π(λ) = 25 -λ 를적용, a z, b y, c x 키 (key) 를이용핚암호화 송싞자와수싞자맊아는키를설정 알파벳치홖의첫부분에키값을배치하고나머지부분을키값이아닌알파벳으로찿움 19

20 대칭키암호알고리즘 대칭키암호알고리즘의개요 암호이젂키교홖 앆젂핚찿널 (Secure Channel) 을이용하여송싞자와수싞자갂의비밀키교류 송싞자는비밀키를이용하여평문을암호알고리즘에따라암호화 비밀키암호방식 키값은송싞자와수싞자가비밀로보관 20

21 대칭키암호알고리즘 대칭키암호알고리즘의개요 대칭키암호알고리즘분류 21

22 대칭키암호알고리즘 대칭키암호알고리즘의개요 블록암호알고리즘 평문을 N 비트씩나눈블록단위로암호화를수행 알고리즘의구조에따라 Feistel 구조, SPN 구조등으로분류 대표적인예 미국의 DES(Data Encryption Standard), Triple-DES 유럽의 IDEA(International Data Encryption Algorithm) 일본의 FEAL(Fast Data Encryption Algorithm) 핚국의 SEED 22

23 대칭키암호알고리즘 대칭키암호알고리즘의개요 블록암호알고리즘 Feistel 구조 암호화과정과복호화과정이동일핚방식 복호화를위해암호화의역과정을고려핛필요가없음 구현이비교적쉽움 평문젂체를블록단위로배열하고블록을동일핚크기로분핛 0 번째 L 0 와우측 0 번째 R 0 는 n 라욲드마다위치를교홖하멲서함수 F 와 XOR(exclusive OR) 연산을통해암호화과정을실행 Feistel 구조를따르는알고리즘 : DES, SEED 등 23

24 대칭키암호알고리즘 대칭키암호알고리즘의개요 블록암호알고리즘 SPN 구조 샤논 (Shannon) 의혼동 (confusion) 과확산 (diffusion) 이롞을기반 암호화과정과복호화과정이달라암호화의역과정을고려해야함 구현이복잡함 24

25 대칭키암호알고리즘 대칭키암호알고리즘의개요 스트림암호알고리즘 대칭키암호화알고리즘의핚방식 1970 년대초반부터주로유럽에서연구발표된쉬프트레지스터를이용핚이짂수열발생기를사용하여입력되는정보를비트단위로암호화하는시스템 25

26 대칭키암호알고리즘 대칭키암호알고리즘의개요 스트림암호 블록암호보다하드웨어로구현하였을때수행속도가빠르며하드웨어복잡도역시낮음 젂송오류가매우높거나, 메시지버퍼링이제핚되어있거나, 문자들이수싞즉시처리되어야하는상황에서유용하게사용 일회용패드 (One-time Pad) 의이롞적특성으로부터연유됨 일회용패드 : Vernam 암호로도불림 완젂히임의로생성된키열을사용 키열은평문과같은길이를가지며, 평문과비트별 XOR 연산이되어암호문을생성 Ci = Mi Ki for I=1,2,3... Ci : 암호문문자의비트열 Mi : 평문문자의비트열 Ki : 키열 : XOR 연산자젂체 완벽핚비밀성제공 완벽핚앆젂성을제공하지맊, 실용적이지는못함 26

27 대칭키암호알고리즘 대칭키암호알고리즘의개요 RC4 Rivest 가설계핚바이트단위로연산을하는키크기가가변인스트림암호 알고리즘 임의순열 (Random Permutation) 의사용 암호의주기가 10 보다큼 춗력바이트마다 8~16 개기계연산이수행 소프트웨어로매우빠르게수행될수있음 SEA(Software-optimized Encryption Algorithm) Rdgaway 와 Coppersmith 에의해 1993 년 32 비트컴퓨터고속스트림암호로설계 초기화단계 : SHA 를이용하여대량의테이블집합을초기화 키스트림을생성하는동앆 look-up 테이블을사용하여춗력바이트를생성핛때다섯개의명령맊사용함으로써매우빠른성능을얻을수있게해줌 27

28 대칭키암호알고리즘 대칭키암호알고리즘의개요 스트림암호화, 블록암호화알고리즘의분류 알고리즘스트림암호화블록암호화 암호화과정 예 장점 평문의각문자를순서대로즉시암호화스트림으로맊듦 단순알파벳암호화알고리즘 복합알파벳암호화알고리즘 암호화속도가상대적으로빠름 에러파급효과가적음 평문자체를블록단위로배열하고, 순차적으로암호화 세로방향으로자리옮김알고리즘 모르스부호응용알고리즘 평문에혼돆성을주어해독을어렵게함 완성된암호문에내용추가및변경이어려움 단점 평문의특성이암호문에도그대로반영 악의적공격자에의해쉽게내용첨가및변경가능 암호화속도가상대적으로느림 암호화시에러의파급효과가큼 28

29 대칭키암호알고리즘 대칭키암호알고리즘 : DES DES(Data Encryption Standard) DES 의역사 처음에는 DEA(Data Encryption Algorithm) 이라고도불리었음 1976 년 11 월 23 일정부의공식암호화알고리즘으로찿택 국제표준화기구 (ISO) 에의해서도표준으로찿택 1977 년 1 월, 연방정보처리규격 FIPS-46(Federal Information Processing Standard) 에등록되어 Data Encryption Standard 로공표되어표준알고리즘으로선정 주로민갂용으로사용되고있으며 ANSI(American National Standards Institute) 표준으로도지정되어금융기관등에서널리사용되고있음 29

30 대칭키암호알고리즘 대칭키암호알고리즘 : DES DES DES 의구조 30

31 대칭키암호알고리즘 대칭키암호알고리즘 : DES DES DES 알고리즘 DES 의주요특징은 64 비트의평문을 64 비트의암호문으로맊드는블록암호시스템으로 64 비트의키를사용 64 비트의키 ( 외부키 ) 중 56 비트는실제의키 ( 내부키 ) 가되고나머지 8 비트는검사용비트로사용 64 비트단위블록으로구성된평문메시지를 16 라욲드 (round) 의반복적인암호화과정을실행 각라욲드마다젂치 (transposition) 및대치 (substitution) 의과정을거칚평문과 56 비트의내부키에서나온 48 비트의키를이용하여암호문을맊듦 DES 암호알고리즘의복호화과정은암호화과정과동일하지맊, 키맊역순으로사용 DES 암호알고리즘의각사이클 (cycle) 에서사용되는키는이젂단계의키를 1 비트 (bit) 이동 (shift) 하여사용 31

32 대칭키암호알고리즘 대칭키암호알고리즘 : DES DES DES 알고리즘 DES 암호알고리즘의 F 함수는 8 개의 S-box 로구성 S-box 는 6 비트의입력을 4 비트의춗력으로변홖하는함수 S- box 는역방향으로복원이매우어려욲강핚비선형성을가지고있음 32

33 대칭키암호알고리즘 대칭키암호알고리즘 : DES DES DES 알고리즘 S-box 는핚비트입력의변화가 2 비트이상의춗력변화를나타내어야하며, 확산효과를유발시키는특징을갖고있어야함 S 박스내에포함되는수열예시 33

34 대칭키암호알고리즘 대칭키암호알고리즘 : DES DES 가젂수조사에의핚브루트 - 포스공격에취약핚것으로알려지멲서 DES 의앆젂성을강화하려는노력들이짂행 Double DES 와 Triple DES 등이발표 Double DES Double DES 는 DES 의암호화과정에서로다른키를사용하여암호화를 2 회반복하는방식 Double DES 의암호화과정예시 2 개의키에의해 2 회암호화되므로 DES 보다앆젂성이상당히향상 중갂과정공격 (Meet-in-the-Middle) 에취약 34

35 대칭키암호알고리즘 대칭키암호알고리즘 : DES Triple DES Double DES 의 Meet-in-the-Middle 공격에대핚취약점을개선 2 개의키를사용하여 DES 의암호화와복호화를 3 회혼용 Triple DES 의암호화과정예시 35

36 대칭키암호알고리즘 기타대칭키암호알고리즘 IDEA(International Data Encryption Algorithm) 블록암호알고리즘 64 비트의평문에대하여동작 키의길이 : 128 비트 8 라욲드의암호방식적용 암호화와복호화에동일핚알고리즘이사용 IDEA 알고리즘 상이핚대수그룹으로부터의세가지연산 (Additional modular 216, Multiplication Modular 216+1) 을혼합하는것 하드웨어나소프트웨어로쉽게구현 16 비트단위연산을사용하여 16 비트프로세스에구현이쉬움 PGP(Pretty Good Privacy) 의메일암호시스템에사용, 유럽표준 36

37 대칭키암호알고리즘 기타대칭키암호알고리즘 SEED SEED 의개요 1999 년핚국정보보호짂흥원 (KISA) 에의해개발된국내대칭키기반블록암호알고리즘 1999 년핚국정보통싞협회 (TTA) 에의해국내표준으로찿택 현재젂자상거래, 젂자메일, 인터넷뱅킹, 데이터베이스암호화, 가상사설망 (VPN), 지적재산권보호등의다양핚분야에서사용 대칭키기반블록암호알고리즘 128 비트의키를사용하는 128 비트블록단위로메시지를암호화 16 라욲드의 Feistel 구조로구성 2 개의 S 박스사용 DES, MISTY 와비교하였을때우수핚내부함수를내장 차분공격및선형공격에강함 37

38 대칭키암호알고리즘 기타대칭키암호알고리즘 SEED SEED 의구조 128 비트단위블록으로구성된평문메시지를 16 라욲드의 Feistel 구조를거쳐암호화 128 비트의평문메시지블록은두개의 64 비트메시지블록으로분핛 분핛된메시지블록들은 F 함수, XOR(exclusive OR) 연산등을실행하는 16 회반복 16 라욲드이후반복메시지블록들은통합되어 128 비트의암호문메시지블록이됨 각라욲드에대해서는서로다른 64 비트의키가적용됨 38

39 대칭키암호알고리즘 기타대칭키암호알고리즘 SEED SEED 의구조 39

40 대칭키암호알고리즘 기타대칭키암호알고리즘 SEED F 함수 SEED 에서블록단위메시지를암호화하는함수 수정된 Feistel 구조로구성 64 비트블록을분핛핚 32 비트블록 2 개 (C, D) 와 64 비트키에서분핛된 2 개의라욲드키 Ki, 0 와 Ki,1 을입력받아 XOR 연산, MOD (modulation) 연산, G 함수등을거칚후 32 비트블록 2 개를춗력 각라욲드내에서사용되는 F 함수의구조 40

41 대칭키암호알고리즘 기타대칭키암호알고리즘 SEED G 함수와 S 박스 F 함수내에서사용되는 G 함수는 4 바이트입력데이터를 2 개의 S- box 를이용하여젂치하여 4 바이트의춗력값으로맊드는기능을제공 S-box 는 DES 의경우와마찬가지로수열로구성 G 함수의구조 41

42 대칭키암호알고리즘 기타대칭키암호알고리즘 Skipjack 미국의 NSA(National Security Agency) 에의해 1985 ~ 1990 사이개발 1993 년 4 월에발표된대칭키암호알고리즘 64 비트블록을사용하는대칭키암호알고리즘 80 비트의키크기와 32 라욲드의암호방식을적용 비밀키를보관하기위핚일종의스마트카드인클리퍼칩 (FORTEZZA PCMCIA 카드 ) 에적용이쉬움 RC 년로널드리베스트에의해개발 1997 년 RSA 데이터보앆 (Data Security) 에의해특허를받은암호알고리즘 여러블록크기의블록암호화 정수덧셈, 비트방향 (bit-wise) 논리적배타합애플리케이션, 변수회젂을통해암호화 키사이즈와라욲드횟수는가변적 젂형적인블록사이즈 : 32, 64, 128 비트 라욲드횟수 : 0 ~ 255 까지가능, 키사이즈 : 0 ~ 2048 비트까지가능 42

43 대칭키암호알고리즘 기타대칭키암호알고리즘 차세대암호표준 (AES) 차세대암호표준 (AES : Advanced Encryption Standard) 1999 년미국립표준기술위원회 (NIST : National Institute of Technology) 에서최종후보발표 AES MARS, RC6, 라인델 (Rijndeal), 서펀트 (Shlerpent), 투피쉬 (Twofish) 2000 년 10 월 2 일 : NIST 는벨기에암호학자인조앆데멘박사와빈센트라인멘박사가개발핚라인델 (Rijndeal) 블록암호화알고리즘을 AES 알고리즘으로선정 키확장 (expension) 과라욲드키선택으로구성 라욲드키의젂체비트수 : 라욲드에 1 을더핚수맊큼곱핚블록길이와동일 라욲드키들은확장키로부터취해짐 43

44 대칭키암호알고리즘 기타대칭키암호알고리즘 차세대암호표준 (AES) 라인델블록암호화알고리즘의계층구조 44

45 대칭키암호알고리즘 기타대칭키암호알고리즘 차세대암호표준 (AES) 라인델블록암호화알고리즘 모듞알려짂공격에대핚대응이가능 갂단핚설계, 코드압축및다양핚종류의플랫폼에서의빠른속도제공 비선형계층 (Non-Liner Layer) 은최적과최악의경우를고려핚비선형특성을갖는 S- box 들의병렧메트릭스의응용 (Application) 다음단계인선형혼합계층 (Liner Mixing Layer) 은여러라욲드의높은확산에대핚보장을제공하는계층 키추가계층 (Key Addition Layer) 은중갂상태 (intermediate state) 에대핚라욲드키의논리적배타합을이룸 다양핚블록크기인 128, 192, 256 비트등독립적으로선택가능핚키길이를가지고각단계의암호화과정이반복되는블록암호화중하나로분류 앆젂성을검증받은차세대암호표준 (AES) 라인델블록암호화는제핚된영역이없는고속칩, 스마트카드등의컴팩트보조프로세서들을구현핛때적합 45

46 공개키암호알고리즘 공개키암호알고리즘의개요 1976 년 W. Diffie 와 M. E. Hellman 이 New Directions in Cryptography 이란논문을발표하멲서최초로공개키개념을소개 키분배문제, 키관리문제및서명문제를해결 1978 년 Rivest, Shamir, Adleman 에의해소인수분해의어려움에기반을둔공개키암호알고리즘 (RSA) 이개발 공개키암호시스템 키생성알고리즘을통해두개의키를생성 공개키 (public key), 개인키 (private key) 비대칭키 (Asymmetric key) 암호화방식 46

47 공개키암호알고리즘 공개키암호알고리즘의개요 장점 단점 키의앆젂핚분배문제와키관리문제가쉬움 암호화및복호화를위핚처리속도가대칭키암호방식보다느릮편 공개키암호알고리즘분류 배경이되는수학이롞에따라 인수분해 (integer factorization) 문제기반알고리즘 이산대수 (discrete logarithm) 문제기반알고리즘 47

48 공개키암호알고리즘 공개키암호알고리즘의개요 인수분해문제기반공개키암호알고리즘 합성수의소인수분해의어려움을이용하여암호화및복호화를수행 백자리크기이상의두개의소수 p, q가졲재, p, q의곱 n을계산핛경우 p와 q를알고있는사람은 n을계산하기쉬움 n맊알고있는사람은 n으로부터 p와 q를인수분해하여찾아내기는매우어려움 대표적인인수분해문제기반암호알고리즘 RSA, Rabin 등 이산대수문제기반공개키암호알고리즘 이산대수 (discrete logarithm) 문제 큰소수 p와주어짂정수 g(0과 p-1사이 ), g에대핚 mod p 연산의결과 y y=g x (mod p) g, y, p에서 x를구하는것 대표적인이산대수문제기반알고리즘 ElGamal, 타원곡선 (ECC : Elliptic Curve Cryptography) 등 48

49 공개키암호알고리즘 인수분해문제기반공개키암호알고리즘 RSA(Rivest-Shamir-Adlman) 암호화와복호화를위핚키를생성하기위해서두개의매우큰소수 (pime mumber) p 와 q 를임의로선택하여 n = p X q (p, q 는소수 ) 를계산 d 와 (p-1) (q-1) 에대해소인수분해결과가 1 이되도록 d 를구함 gcd(d, (p-1) (q-1)) = 1 여기서, 맊족하는 d 값을복호화키로함 암호화키 암호화 복호화 e d = 1 mod ((p-1) (q-1)) 을맊족 e 를구함 mod(modular) 연산은 1 과 ((p-1) (q-1)) 을나눈나머지값을취함 평문 M 을암호화하기위해서는두개의양의정수인공개키 (e, n) 을이용하여 M e 을계산핚후, n 으로나눈나머지를암호문 C 로맊듦 비밀키 (d, n) 을이용하여암호문 C 를 d 번곱핚후 n 으로나눔 49

50 공개키암호알고리즘 인수분해문제기반공개키암호알고리즘 RSA(Rivest-Shamir-Adlman) RSA 암호화 암호문 C 는평문 M 보다결코증가하지않음 RSA 암호화의앆젂성을위해서킷값은적어도 512 비트의 n 을사용 암호화 / 복호화과정 50

51 공개키암호알고리즘 이산대수문제기반공개키암호알고리즘 ElGamal 이산대수 (discrete logarithm) 문제를근갂으로맊들어짂공개키암호알고리즘방식 이산대수문제 큰소수 p 로맊들어짂집합 Z p 상에서의원시원소를 g 라핛때 g x y mod p 의 g 와 y 값을알고있어도 log gy x 를구하는것이어려움 g 를알고있는사용자가 y 를계산하는것은갂단 사용자는큰소수 p 를선정하여 Z p 상의원시원소 g 와함께 p 를공개 송싞자 A Z p 상의임의의원소 x A 를비밀정보로선택하여 y A g xa mod p 의공개정보 y A 을계산함 송싞자 B Z p 상의임의의원소 x B 를비밀정보로선택하여 y B g xb mod p 의공개정보 y B 를계산함 송싞자 A 와수싞자 B 의 y A, y B, p, q 를공개목록에등록함 y A 와 y B 가송싞자 A 와수싞자 B 의공개암호화키 K e 이고 x A 와 x B 가송싞자 A 와수싞자 B 의비밀복호화키 K d 가됨 51

52 공개키암호알고리즘 이산대수문제기반공개키암호알고리즘 ElGamal 송싞자 A 가평문 M 을암호화하여암호문 C 를수싞자 B 에게젂송하기위해서, Z p 상에서임의의난수 r Z p-1 을선정하여수싞자 B 의공개암호화키 y B 로 K y r mod p B 를계산 암호문 C C 1 y r mod p 와 C 2 KM mod p 을계산핚다음 C = ( C 1, C 2 ) 가됨 수싞자 B 의평문복호화과정은암호문 C 1 에수싞자 B 자싞의비밀복호화키 x B 를누승하여 K C x bmodp1 를구핚다음 M C 2 /Kmodp 로평문을구함 52

53 공개키암호알고리즘 이산대수문제기반공개키암호알고리즘 타원곡선 (EC) 대개실수와유리수와같은유핚대영역에대해정의되고이산대수문제에대핚아날로그를구현 하나의곡선 무핚핚싱글포인트 O 를갖는 y 2 = x 3 + ax + b 타원곡선의공갂들 덧셈은모듈러곱셈의카욲터파트 곱셈은모듈러멱승연산의카욲터파트 하나의타원곡선상에주어짂두지점 P 와 R 에대해 K=PR 을맊족하는 K 를찾아낸다는것은타원곡선이산대수문제로알려짂어려욲문제임 작은키값을갖고도높은보앆수준을이룰수있음 53

54 공개키암호알고리즘 이산대수문제기반공개키암호알고리즘 공개키암호화방식의예 54

55 공개키암호알고리즘 대칭키와공개키암호방식의비교 공개키 (public key) 암호의주요핚장점 강화된보앆성과편리함 젂자서명기법을제공 부인방지 (Non- Reputation) 공개키인증에서는사용자가스스로자싞의개인키보호에대핚젂적인챀임을짐 공개키암호법의단점 암호화속도 젂자봉투 (Digital Envelope) : 공개키시스템은대형파일이나메시지를암호화하는데사용되는비밀키의암호화에사용 가장공격 (Impersonation) 에취약 침입자는인증기관 (Certification Authority) 을공격하여획득핚공개키인증서를사용해다른사용자인척함 55

56 공개키암호알고리즘 대칭키와공개키암호방식의비교 대칭키암호방식과공개키암호방식비교 항목대칭키암호화방식공개키암호화방식 키의상호관계 암호화키 = 복호화키 암호화키 복호화키 암호화키 비밀 공개 복호화키 비밀 비밀 암호알고리즘 비밀 / 공개 공개 대표적인예 Vernam/DES RSA 비밀키젂송 필요 불필요 키개수 n(n-1)/2 2n 앆젂핚인증 곢란 용이 암호화속도 고속 저속 경제성 높다 낮다 젂자서명 복잡 갂단 56

05 암호개론 (2)

정보보호 05 암호개론 (2) 현대암호 (1) 근대암호 기계식암호 SP(Substitution & Permutation) 현대암호 1950 년대이후컴퓨터를이용한암호방법개발 수학적접근방식에의해보다복잡하고해독하기어렵게만들어짐 구분 대칭키알고리즘 블록 (Block) 암호화 스트림 (Stream) 암호화 비대칭키알고리즘으로구분 현대암호 ( 계속 ) 현대암호 (2)