Microsoft PowerPoint - crypto [호환 모드]

Size: px

Start display at page:

Download "Microsoft PowerPoint - crypto [호환 모드]"

준현 사공
5 years ago
Views:

1 U-571 과 Enigma

2 암호와수학

3 차례 재미있는암호이야기 필요한수학 ; 잉여산, 합동식 Fermat 와 Euler RSA 공개키암호 Trapdoor Problem ( 쥐덫문제 ) 이산로그문제 (DLP)

4 U-571 그들은왜침몰하는배 ( 잠수함 ) 에올라갔을까?? 목숨을걸고 ( 실제영국해군여러명사망 ) 안전한암호의제조와상대암호의해독이전쟁의승패를가름 오늘날에는??

5 암호와음어 음어 : 어제와같은시간같은장소에서만나자 암호 : 최초의암호다운암호는로마의 Julius Caesar 시대 Substitution ; 문자들의역할바꾸기 Transposition ; 문자열의순서바꾸기

6 Subsitution 암호의보기 평문 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 암호문 y v w p n r z t q g u m c f x i j a k e b h l o d s 가능한 substitution 방법 ; 26!- 가지 26! = 약 4 * = 403,291,461,126,605,635,584,000,000

7 영문자의사용빈도 a 8.04 % n 7.09 % b 1.54 % o 7.60 % c 3.06 % p 2.00 % d 3.99 % q 0.11 % e % r 6.12 % f 2.30 % s 6.54 % g 1.96 % t 9.25 % h 5.49 % u 2.71 % i 7.26 % v 0.99 % j 0.16 % w 1.92 % k 0.67 % x 0.19 % l 4.14 % y 1.73 % m 2.53 % z 0.09 %

8 Subsitution 암호의보기 암호문 : etnan xfwn lyk y ryetna qf ebwkxf ltx kyqp etqk yphqwn qk rxa dxb kxf dxb pxfe lykt dxbaknmr lnmm kx dxba rnne kcnmm mqun tnmm qr qf vnp lqet y zqam unni dxba ktxnk xf 빈도 : n ; 12.1 % x ; 10.6 % k ; 9.1 % q ; 7.6 %

9 영문자의사용빈도 a 8.04 % n 7.09 % b 1.54 % o 7.60 % c 3.06 % p 2.00 % d 3.99 % q 0.11 % e % r 6.12 % f 2.30 % s 6.54 % g 1.96 % t 9.25 % h 5.49 % u 2.71 % i 7.26 % v 0.99 % j 0.16 % w 1.92 % k 0.67 % x 0.19 % l 4.14 % y 1.73 % m 2.53 % z 0.09 % n e? 12.1 % x t? 10.6 % k 9.1 % q 7.6 % m l? 6.8 % t 6.1 % y a?, i? 5.3 % e 5.3 % f 4.6 %

10 ??? etnan xfwn lyk y ryetna qf ebwkxf ltx kyqp etqk e e t e a a a e t t a yphqwn qk rxa dxb kxf dxb pxfe lykt dxbaknmr a e t t t t t a t e lnmm kx dxba rnne kcnmm mqun tnmm qr qf vnp e t t ee e e e e lqet y zqam unni dxba ktxnk xf a ee t te t

11 영문자의사용빈도 가장빈번하게짝지워지는철자 ; th > he > an > in > er, is, in, on, ou, 가장빈번하게사용되는단어 ; the > of > and > to > a > in > 암호문에서는 ; xf > xb > et > tn > na, qk, qf, etn 3번 따라서, etn = the 로가정 etnan = there 로가정 ryetna = father 로가정 (gather 로가정실패후 ) q, x = o, i 로가정

12 q=o, x=i??! etnan xfwn lyk y ryetna qf ebwkxf ltx kyqp etqk there i e a a father o t i h ao tho yphqwn qk rxa dxb kxf dxb pxfe lykt dxbaknmr a o e o fir i i i i t a h i r e f lnmm kx dxba rnne kcnmm mqun tnmm qr qf vnp e i i r feet e o e he of o e lqet y zqam unni dxba ktxnk xf oth a or ee i r hie i

13 q=i, x=o?!! etnan xfwn lyk y ryetna qf ebwkxf ltx kyqp etqk there o e a a father i t o ho ai thi yphqwn qk rxa dxb kxf dxb pxfe lykt dxbaknmr a i e i for o o o o t a h o r e f lnmm kx dxba rnne kcnmm mqun tnmm qr qf vnp e o o r feet e i e he if i e lqet y zqam unni dxba ktxnk xf ith a ir ee o r hoe o 따라서, k=s, l=w, p=d

14 OK!!! etnan xfwn lyk y ryetna qf ebwkxf ltx kyqp etqk there o e was a father i t so who sai this yphqwn qk rxa dxb kxf dxb pxfe lykt dxbaknmr a i e is for o so o o t wash o rse f lnmm kx dxba rnne kcnmm mqun tnmm qr qf vnp we so o r feet s e o e he if i e lqet y zqam unni dxba ktxnk xf with a ir ee o r shoes o 따라서, f=n, d=y, b=u, m=l

15 성공!!! etnan xfwn lyk y ryetna qf ebwkxf ltx kyqp etqk there on_e was a father in t son who sai_ this yphqwn qk rxa dxb kxf dxb pxfe lykt dxbaknmr a i_e is for you son you _ont wash yourself lnmm kx dxba rnne kcnmm mqun tnmm qr qf vnp well so your feet s_ell li_e hell if in _e_ lqet y zqam unni dxba ktxnk xf with a _irl _ee_ your shoes on

16 Subsitution + Transposition Subsitution 암호문 2 : etnanxfwnlykyryetnaqfebwkxfltxkyqpetqk yphqwnqkrxadxbkxfdxbpxfelyktdxbaknmr Subsitution 암호문 3 : etna nxfw nlyk yrye tnaq febw kxfl txky qpet qkyp hqwn qkrx adxb kxfd xbpx fely ktdx bakn Subsitution + Transposition 암호문 : aten wxnf klny eryy qnta wefb lxkf yxtk tpqe pkqy nqhw xkqr bdax dxkf xbxp yefl xtkd nabk

17 독일의 Enigma 제 2 차세계대전중사용 4개의 substitution wheel 문자의사용빈도를은폐하기위해 한문자를입력할때마다 4개의바퀴가돌아가면서 substitution 규칙을바꿈 매 8 시간마다 8개의바퀴중 4개를선택하는방법과 끼우는순서와바퀴들의초기위치변경 반사바퀴

18 Bletchley Team 제 2 차세계대전때영국의암호해독반 런던교외 Bletchley Park 에본부 많을때는 10,000 명의직원 년대많은 (?) 비밀문서공개

19 Alan Turing Bletchley Team 의연구원 A. Turing 결국은시간과의싸움 (8 시간마다새 subsitution 규칙 ) Bombe, Collosus 등의장비로 Enigma 해독반자동화 최초의컴퓨터? 컴퓨터의원리발명 ; Turing Machine 컴퓨터의등장과발전 : 암호의개념자체를바꿈

20 암호의개념 평문 암호화과정 복호화과정 평문 암호문 영희 철수 盜士님

21 암호의개념 메시지는결국숫자 (10 진법, 2 진법, ) Block 으로나눌수있음 단어를숫자로 substitute 할수도 ( 코드북 ) 주로제 1 차세계대전 Enigma 의비밀키는 substitution 규칙

22 현대암호 아예암호화 / 복호화방법 ( 알고리즘 ) 공개 컴퓨터의발달로엄청난 computing power 알고리즘자체의비밀에의존할수없기때문 비밀키 (secret key) 를모르면해독할수없도록설계 암호화의필요성 무선통신, 인터넷등은마음만먹으면 공격 가능 혹 나는아무도해독못할암호를만들수있다??

23 현대암호의응용 군사, 외교 : 비밀문서, 비밀통신 은행업무 : 인터넷뱅킹, 은행간거래 전자화폐 : 인증, 위조 ( 변조 ) 방지, 부인방지 전자투표 : 투표자인증, 이중투표방지, 비밀유지등 문서보안 : 비밀유지, 위조 ( 변조 ) 방지 이동통신 : 비밀유지, 회원자격확인

24 현대암호의분류 대칭키암호체계 Symmetric-Key Cryptosystem 블록암호 (Block Cipher) 스트림암호 (Stream Cipher) DES, AES, SEED RC4, SEAL, 공개키암호체계 Public-Key Cryptosystem RSA ( 소인수분해의어려움 ) ECC ( 타원곡선위에서의이산로그문제 ) XTR, NTRU, NICE, BGC, MOR,

25 대칭키와공개키암호체계 대칭키암호체계 U-571 : 그들은왜목숨을걸고암호화규칙을빼앗았을까? 암호화할수있으면복호화도할수있다. 공개키암호체계 암호화할수있어도복호화는할수없다.

26 대칭키암호체계 암호화키 : k 비밀키 사전에공유 복호화키 : k 비밀키 평문 암호화과정 복호화과정 평문 영희 f k 암호문 1 f k 철수

27 Block Cipher 와 Stream Cipher Block Cipher : Subsitution + Transposition 의결정판 DES (Data Encryption Standard) AES (Advanced Encryption Standard) Stream Cipher : 예를들어, 평문을 2 진법수로생각할때, 비밀키는평문전체길이와같은 2 진법난수 (random number) 보기 : 평문 = 비밀키 = 암호문 = 영화에보면

28 공개키암호체계 암호화키 : e 수신자의공개키 복호화키 : d 수신자의비밀키 평문 암호화과정 복호화과정 평문 영희 f e 암호문 g d 철수

29 17 세기파리사교계의두 Pierre de Fermat ( ) B. Pascal ( ) 취미 ; 수학 ( 정수론 ) 직업 ; 정치가 ( 외교관 ) a p a (mod p) x n + y n = z n (n>2) 기하학확률론유체역학철학신학 인간은생각하는갈대!

30 Fermat s Little Theorem p 는소수이고, gcd(a,p)=1 이면, a p-1 1 (mod p) p 가소수이면, a p a (mod p) 증명 : Fermat 나 Euler 는응용수학에는무관심했지만

31 Euler - 함수 정의 (n) = (n 보다작은자연수중 n 과서로소인것의개수 ) 예 ; (6) = 2 ( { 1, 2, 3, 4, 5, 6 }) 성질 p 가소수일때, (p) = p-1 a, b 가서로소일때, (ab) = (a) (b) p q 가소수이면, (pq) = (p) (q) = (p-1)(q-1)

32 Euler 의일반화 a 와 N 이서로소일때, 즉 gcd (a,n)=1 이면, a (N) 1 (mod N) 증명 : 보기 : (mod 6) Fermat s Little Theorem 은 N 이소수인경우

33 오일러정리의결과 p q 는소수, N=pq, 1 < e,d < N, ed 1 (mod (n)), gcd(x,n) = 1 이면, x ed x (mod n) 증명 : gcd(x,n) = 1 이므로, 오일러의정리에의하여 x ed = x k (N)+1 = (x (N) ) k x 1 k x = x (mod N)

34 RSA 암호체계 1978 년 Rivest, Shamir, Adleman 에의해고안된암호체계가장널리쓰이는공개키암호체계 공개키 e 로암호화하고, 비밀키 d 로복호화한다. x f e e x x (mod N ) 암호화 y f e x g d y x g d d e d y y ( x ) x(mod N ) 복호화 y p,q 소수, N=pq, ed 1 (mod (N))

35 RSA 키설정 단, ed 1 (mod (N)), gcd(e,n)=1 사람 공개키비밀키 N e N = pq d A ( 영희 ) N A e A N A = p A q A d A B ( 철수 ) N B e B N B = p B q B d B 누구나안다 소유자만안다

36 RSA 의안전성 인수분해의어려움에의존 소수 p, q 2 500, N = pq 일때, p, q 알고 N 구하기 ; 1초 N 의인수분해 ; ( 현재기술로 ) 우주역사보다긴시간필요 (100억년이나 1조년이나오십보백보 ) p, q 알면, (N) = (p-1)(q-1) 알수있고, 이때 d e ((n))-1 (mod (n)) 이므로, 비밀키노출 ( ed e ((n)) 1 (mod (n)) )

37 RSA 암호화 상황 A 가 B 에게메시지 x 를암호화하여보내고싶을때, 단, 1 < x < N 필요한것 : 누구나아는 B 의공개키 (N B,e B ) (x,n B ) 1 일확률은 (p B +q B )/N B = 0 (!) 따라서, (x,n B ) = 1 B 에게보내주는것 : x e B (mod N B ) x f e B eb x x (mod N ) 암호화 B y f e B x

38 2-499 = 0 만약믿을수없다면, 로또 1 등확률을 (1 조분의 1) = 이라고하면, = (10 3 ) 4 (2 10 ) 4 = = = 2 10 두주연속 1 등당첨확률은 (2-40 ) 2 = 주연속 1 등당첨확률은 (2-40 ) 12 = 2-480

39 큰수의지수계산 N = pq 이고, 1 < x,e < N 일때, x e (mod N) 계산? 보기 : x 35409?? 무식한방법 : x 를 번곱한다 ^^ ㅋㅋ = = (x 2 ) 2 = x 4 = x 22, (x 4 ) 2 = x 8 =x 23, (x 8 ) 2 = x 16 =x 24, x = x = x 215 x 211 x 29 x 26 x 24 x

40 RSA 복호화 상황 B 가 A 에게서받은암호문 y = x eb 를복호화할때, 필요한것 : B 만아는비밀키 d B 단, e B d B 1 (mod (N B )) 얻는것 : (x eb ) d B x (mod N B ) g d B y x g d B d B eb d B y y x ) x(mod N ) ( B 복호화 y

41 RSA 서명 상황 A 가 B 에게메시지를보내면서자신임을증명 메시지보낸사실부인방지 필요한것 : 서명 message z, A 만알고있는 A 의비밀키 d A 보내주는것 : (z da, x e B ) B 의확인과정 : A 의공개키 e A 이용

42 RSA 서명확인 상황 B 가 A 에게서받은서명 w = z d A 를확인하고싶을때, 필요한것 : 누구나아는 A 의공개키 (N A,e A ) 확인 : (z d A ) e A z (mod N A )? g e A y? x g e A e A d A e A w w z ) z(mod N ) ( A 확인? y

43 Trapdoor ( 쥐덫 ) Problem 실마리 (clue) 를알면역함수를쉽게구할수있지만, Clue 를모르면역함수를구하기어려운함수 Trapdoor Problem 의예 소인수분해문제 : RSA가기반한문제 이산로그문제 (Discrete Logarithm Problem, DLP) Diffie-Hellman 문제등등

44 이산로그문제 (DLP) 정의 : primitive element P 가소수일때, 모든 y를 ( 단, 1 y p-1) 어떤유일한 x에 ( 단, 1 x p-1) 대하여 y = g x (mod p) 로나타낼수있는 g가 ( 단, 1 g p-1) 존재한다. 이런 g 를 primitive element (mod p) 라고한다. 이산로그 (discrete log) 문제의정의 y 와 primitive element g 가주어졌을때, y g x (mod p) 를만족하는 x 를구하라. x log g y (mod p) 라고쓰기도한다.

45 Diffie-Hellman 문제 DH 문제의정의 g 가 primitive element (mod p) 이고 (a,b 둘중하나만알고 ) g, g a, g b 를알때, g ab 를구하라 DH 문제를이용한 DH 키공유 Alice : a 만안다. g a (mod p) 를계산하여 Bob 에게보낸다 Bob : b 만안다. g b (mod p) 를계산하여 Alice 에게보낸다 Alice : g b 에 a 제곱을하여 g ba 를얻는다 Bob : g a 에 b 제곱을하여 g ab = g ab 를얻는다 Alice 와 Bob 은같은키 (g ab (mod p)) 를공유하게된다

46 타원곡선 (Elliptic Curve) 이란? y 2 =x 3 +ax+b 꼴의곡선 타원곡선 mod p 타원곡선이란? y 2 x 3 +ax+b (mod p) 를만족하는점 (x, y) 의집합 타원곡선암호 타원곡선위에서기하학적으로덧셈을새롭게정의할수있다 새로운연산에관한이산로그문제를이용하여암호시스템을만든다 타원곡선의덧셈 P+Q

47 NSA National Security Agency (USA) 예산과조직비밀 CIA 의수십배예산?? 매년수학 new Ph. D. 수십명채용?? 수많은영화의소재 알카에다??

48 암호의대한독립만세

본 강의에 들어가기 전

본 강의에 들어가기 전 1 2.1 대칭암호원리 제 2 장. 대칭암호와메시지기밀성 2 3 기본용어 평문 (Plaintext) - original message 암호문 (Ciphertext) - coded message 암호화 (Cipher) - algorithm for transforming plaintext to ciphertext 키 (Key) - info used in cipher