Microsoft PowerPoint - chap05.ppt

Transcription

1 학기현대암호학 제 5 장공개키암호 박종혁 Tel: jhpark1@snut.ac.kr

2 5.0 주요내용 키배송문제 공개키암호 시계연산 RSA 다른공개키암호

3 5.1 키배송문제 대칭암호에서는양측이안전하게통신을하기위해서비밀키를공유하는것이핵심이다.

4 5.1.1 키배송 대칭암호를사용하려고하면바로키배송문제 (key distribution problem) 에부딪치게된다. 앨리스가자신의메시지를암호화할때사용했던대칭키를보내지않으면밥은복호화할수없다.

5 키배송문제를해결하기위한방법 키의사전공유에의한해결 키배포센터에의한해결 Diffie-Hellman 키교환 공개키암호에의한해결

6 5.1.2 키사전공유 키배송문제를해결하기위한가장간단한방법은 안전한방법으로키를사전에건네주는 것이다. 이것을키의사전공유라부른다.

7 사전공유의한계 안전한방법으로통신상대에게키를건네주지않으면안된다 인원이많아지면통신을위한키의수가방대해지는것도문제이다

8 키를보내버리면도청자이브도복호화 할수있다 ( 키배송문제 )

9 5.1.3 키배포센터 평문블록 블록암호알고리즘에서암호화의대상이되는평문을말한다. 평문블록의길이는블록암호알고리즘의블록길이와같다. 암호문블록 블록암호알고리즘을써서평문블록을암호화한암호문을말한다.

10 평문블록과암호문블록

11 앨리스가밥에게암호메일보내기 1. 앨리스는키배포센터에 밥과통신하고싶다 고신청한다. 2. 키배포센터는의사난수생성기를써서세션키를만든다. 이것은앨리스와밥이이번통신에만사용하기위한일시적인키이다. 3. 키배포센터는데이터베이스로부터앨리스의키와밥의키를꺼낸다. 4. 키배포센터는앨리스의키를써서세션키를암호화해서앨리스에게보낸다. 5. 키배포센터는밥의키를써서세션키를암호화해서밥에게보낸다.

12 앨리스가밥에게암호메일보내기 6. 앨리스는키배포센터로부터온세션키 ( 앨리스의키로암호화되어있음 ) 를복호화해서세션키를얻는다. 7. 앨리스는세션키를써서밥에게보낼메일을암호화해서밥에게보낸다. 8. 밥은키배포센터에서온세션키 ( 밥의키로암호화되어있음 ) 를복호화해서세션키를얻는다. 9. 밥은세션키를써서앨리스에게온암호문을복호화한다. 10. 앨리스와밥은세션키를삭제한다.

13 키배포센터에의한키배송 키배포센터 DB 2 세션키 (K) 생성 3KA, KB 를 DB 에서추출 밥의키 : KB 앨리스의키 : KA, 전사원의키 1 밥과통신하기를원한다고키배포센터에의사전달 앨리스 ( 송신자 ) 6 세션키복구 : D KA [E KA (K)]=K 를수행 7 메시지암호화 E K (M) 수행 4E KA (K) 를생성하여앨리스에게전달 5E KB (K) 를생성하여밥에게전달 전송 밥 ( 수신자 ) 8 세션키복구 : D KA [E KA (K)]=K 를수행 9 메시지복호화 D K [E K (M)]=M 수행

14 5.1.4 Diffie-Hellman 키교환 송수신자가어떤특정정보를서로교환한다. 이정보는도청자이브가읽어도괜찮다. 교환한정보를가지고동일한키를각각만들어낼수있다. 도청자이브는같은키를만들수없다 두통신자사이에인증을제공하지못한다는결점이있다.

15 공개키인증서를이용해세션키를 교환하는방법 1. 메시지를준비한다. 2. 일회용세션키를이용하는대칭암호기법으로메시지를암호화한다. 3. 앨리스의공개키를이용해서그세션키를암호화한다. 4. 암호화된세션키를메시지에첨부해서앨리스에게보낸다.

16 5.1.5 공개키암호를이용한키배송 수신자는미리 암호화키 를송신자에게알려준다. 이 암호화키 는도청자에게알려져도괜찮다. 송신자는그 암호화키 를써서보내고자하는메시지를암호화해서수신자에게보낸다. 복호화할수있는것은 복호화키 를가지고있는사람 ( 수신자 ) 뿐이다.

17 공개키암호를이용한키배송 공개된영역 가져오기 B 공개키 밥의공개키 키 밥의공개키로암호화된키 밥 ( 수신자 ) B 공개키 밥의공개키 앨리스 ( 송신자 ) 암호화 밥의공개키로암호화된키 전송 복호화키 B 개인키 밥의개인키

18 5.2 공개키암호 공개키암호를사용하면앞절에서말한키배송문제를해결할수있다. 내용 공개키암호의역사와구조, 공개키암호를사용한통신의흐름, 공개키암호만으로는해결할수없는문제

19 Diffie 와 Hellman 공개키암호의영향 수학적함수를근거로해서만들었다 공개키알고리즘은비트패턴의단순한조작이아니다 비대칭방식 공개키암호는오직한개의키만사용하는대칭암호방식과대조적으로서로다른두개의키를이용한다 공개키는두개의키를사용한다 기밀성, 키분배, 인증분야에서매우성능이뛰어나다

20 5.2.1 공개키암호에대한잘못된상식 공개키암호가대칭암호보다암호해독에있어서더안전하다고생각하는것이다. 공개키암호기술을일반적으로사용하기때문에대칭암호를더이상사용하지않게된다는생각이다. 대칭암호의경우키분배센터를이용해야하는성가신교환절차가있기때문에공개키를사용하면키분배가매우쉽다고생각한다는것이다.

21 사실은 공개키암호에서도모종의프로토콜형태가필요하다 종종중앙에이전트가필요할때도있다 사용하는절차들도대칭암호와비교해볼때더단순하다거나더효과적이라고말하기어렵다.

22 5.2.2 공개키암호란 공개키암호 (public-key cryptography) 에서는 암호화키 와 복호화키 를나눈다. 송신자는 암호화키 를써서메시지를암호화하고, 수신자는 복호화키 를써서암호문을복호화한다. 암호화키 는암호화를위해송신자가사용하는것이고, 복호화키 는복호화를위해수신자가사용하는것이다.

23 암호화키와복호화키의구별 송신자가필요한것은암호화키뿐이다. 수신자가필요한것은복호화키뿐이다. 도청자에게알려지면곤란한것은복호화키이다. 암호화키는도청자에게알려져도괜찮다.

24 공개키 (public key) 공개키암호에서암호화키는일반에게공개할수있다. 공개해도상관이없으므로이키를공개키 (public key) 라부른다. 공개키전달방법 메일, 신문의광고란, 간판으로해서길가에세워도, Web 페이지로전세계에서읽을수있도록해도괜찮다. 도청자이브에게공개키가도청되는것을신경쓸필요가없다.

25 개인키 (private key) 복호화키는절대로공개해서는안된다. 이키는당신만이사용하는것이다. 그러므로이키를개인키 (private key) 라부른다. 개인키는다른사람에게보이거나, 건네주거나해서는안된다. 개인키는자신의통신상대에게도보여서는안되는것이다.

26 대칭암호의비밀키와개인키 대칭암호에서사용하는키는비밀키 (secret key) 라고일컬어진다. 공개키암호에서사용되는두개의키는공개키 (public key) 와개인키 (private key) 라고한다 항상개인키는비밀로해야하지만비밀키라고부르지않고개인키라고부르기로한다. 그이유는대칭암호에서사용하는비밀키와혼동하지않도록하기위한것이다.

27 키쌍 (key pair) 공개키와개인키는둘이한쌍이된다. 이키쌍을가리켜키쌍 (key pair) 이라고부른다. 공개키로암호화한암호문은그공개키와쌍이되는개인키가아니면복호화할수없다. 키쌍을이루고있는 2개의키는서로밀접한관계 수학적인관계 가있다. 이때문에공개키와개인키를각각별개로만들수는없다.

28 5.2.3 공개키암호의역사 1976 년휘트필드디피 (Whitfield Diffie) 와마틴헬만 (Martin Hellman) 이공개키암호의아이디어를발표 공개키가어떠한특성을가져야하는지를제시 1977 년, 공개키암호의구체적인알고리즘으로서랠프메르클레 (Ralph Merkle) 와마틴헬만 (Martin Hellman) 에의한배낭 (napsack) 암호가만들어졌다.

29 공개키암호의역사 1978 년, 공개키암호알고리즘 RSA 발표 론라이베스트 (Ron Rivest), 아디샤미르 (Adi Shamir), 레너드애들먼 (Leonard Adleman)

30 5.2.4 공개키암호구조 다섯가지핵심요소 평문 (Plaintext): 암호알고리즘 (Encryption algorithm): 공개키와개인키 (Public and private key): 암호문 (Ciphertext): 복호알고리즘 (Decryption algorithm):

31 5.2.5 공개키를사용한통신의흐름 1. 밥은공개키 / 개인키로이루어진한쌍의키를 만든다. 2. 밥은자신의공개키를앨리스에게보낸다. 3. 앨리스는밥의공개키를써서메시지를암호화 한다. 4. 앨리스는암호문을밥에게보낸다. 5. 밥은자신의개인키를써서암호문을복호화한 다.

32 공개키를사용해서앨리스가밥에 게메시지보내기 앨리스 ( 송신자 ) 3 앨리스는밥의공개키로메시지를암호화한다 메시지 2 밥은자신의공개키 B 공개키를앨리스에게보낸다 1 밥은자신이사용할공개키와개인키로이루어진한쌍의키를만든다 B 공개키 5 밥은암호문을신의개인키로복호화한다 B 개인키 밥 ( 수신자 ) B 공개키 암호화 메시지 암호문 4 앨리스는암호문을밥에게보낸다 복호화 암호문 B 개인키

33 5.2.5 여러가지용어 공개키암호와같은의미로비대칭암호 (asymmetric cryptography) 라는용어를사용한다. 이것은대칭암호와의대비를잘나타내는용어이다. 대칭암호에서는암호화와복호화에서같은키를사용 대칭암호에서는암호화와복호화가마치거울에비친것처럼대칭을이루고있다. 그에비해비대칭암호에서는암호화와복호화에서다른키를사용한다. 대칭이아니고, 비대칭인암호라고부를수있다.

34 5.2.6 공개키암호로도해결할수 없는문제 공개키에대한검정 입수한공개키에대한판단이필요 공개키의인증에관한문제이다. 중간자공격 (man-in-the-middle attack) 공격이유효하다 처리속도문제 대칭암호에비해처리속도가몇백배나늦다는

35 5.3 시계연산 RSA 알고리즘을이해하기위해필요한가장기본적이며최소한의연산인시간연산

36 5.3.1 덧셈 바늘이하나만달린시계를떠올리기바란다 의자리에는 0 이라고쓰여있다 즉 0 부터 11 까지의숫자가표시된시계이다

37 예 바늘이 7 을가리키고있다고하고오른쪽으로 6 눈금보내면바늘은어디를가리키는가?

38 예 13 일까? 아니다, 이시계에는13은없다. 바늘은1을가리킨다

39 예 7 을가리키고있다고하고오른쪽으로 20 눈금을보내면바늘은어디를가리키는가?

40 예 음, 바늘은 27 을가리키는게아니고 12 마다 0 으로돌아가니까 을가리키게된다

41 수행한내용을수식으로보면 (7 + 20) 12 = = 2 나머지 3

42 mod 계산 나눗셈을해서나머지를구하는계산을위한기호 ( 연산자 ) 의표현 mod

43 mod 연산의예 mod 를사용하면 27 을 12 로나누었을때의나머지를다음과같이표기할수있다. 27 mod 12 란 27 을 12 로나눈나머지 27 을 12 로나눈나머지는 3 이므로 27 mod 12 = 3

44 수학적표현 27과3은12를제수로해서합동이다 라고표현한다. 이야기를정리해보면 시계를오른쪽으로돌린다는것은덧셈에해당한다. 단, 단순한덧셈이아니라 나눗셈의나머지 (mod) 를생각할것.

45 mod 12 덧셈연산표

46 5.3.2 뺄셈 뺄셈이라는것은덧셈의역의연산이므로시계의바늘을왼쪽으로돌리면되는것 그런데여기서시계를왼쪽으로돌리는것을금지한다. 바늘이7을가리키고있을때, 어떻게하면바늘이0을가리키게되는가?

47 예 7 에뭔가를더해서 12 로나눈나머지는 0 이되는수는무엇인가를알면된다 (7 + ) mod 12 = 0 여기에서 에들어갈숫자는무엇일까? 단 는 0, 1, 2,, 10, 11 중하나이어야한다. 음수 -7 은여기서생각하지않는다.

48 예 를더해서 12 로나눈나머지는 0 이된다 (7 + 5) mod 12 = 0

49 ( X + Y) mod 12 = 0 이되는 X 와 Y 의짝

50 mod 12 뺄셈연산표

51 5.3.3 곱셈 보통산수에서는곱셈은 덧셈을반복한것 이다. 예를들면 7 4라는것은 7을 4회더한것이다. 7 4 =

52 시계연산의곱셈도덧셈의반복 (7 4 는 28 이므로 ) 7 4 mod 12 = 28 mod 12 (28 12 는몫이 2 이고나머지가 4 이므로 ) 28 mod 12 = 4

53 mod 12 곱셈연산표

54 5.3.4 나눗셈 뺄셈을생각할때덧셈의역연산을생각한것처럼곱셈의역연산을생각한다. 예를들면다음식에대해생각해본다. 7에 를곱해서 12의 mod를취했더니 1이되었다. 이때의 는무엇일까? 7 mod 12 = 1

55 바늘의조작으로생각하면 7 눈금오른쪽으로돌리는 조작을몇회반복하면 1 이되는가? 하는문제이다. 이것은금방은알수없다. 에 0, 1, 2, 을순서대로넣어서 7 mod 12 를계산해본다.

56 7 mod 12 계산표

57 mod 12 의세계에서는 이표에서 는 7 이라는것을알수있다. 7 7 mod 12 = 1 지금생각한것은 mod 12 의세계에서는 7 에무엇을곱하면 1 이되는가? 라는문제였다. 바꿔말하면 mod 12 의세계에서는 1 7 의답은무엇인가? 라는문제가된다. 즉, 12 로나누어남는수를취하는세계에서나눗셈을생각한것이되는것이다.

58 mod 세상의역수 mod 12 = 1 라는관계식을보면서손으로잠깐 mod 12의부분을가려본다. 와 는역수의관계에있다는것이다. 역수란, 곱하면 1이되는수를말한다.

59 보통의산수라면 은의곱셈에대한역원

60 mod 세상에서는 0부터 11까지중에서어떤수에도역수는있는것일까? 시계연산에서 어떤수의역수가존재하는지어떤지 하는문제는, 공개키알고리즘 RSA에서 공개키와쌍을이루는개인키가존재하는지어떤지 하는문제와직결되어있다.

61 0 의역수는있는가? 0 눈금의회전 ( 즉돌리지않는것 ) 을아무리반복해도 1 까지바늘을나아가게할수는없으므로, 0 mod 12 = 1 을충족시키는 는존재하지않는다.

62 1 의역수는어떤가? 1 mod 12 = 1 을충족시키는 는분명히 1 이다.

63 2 의역수는어떤가? 2 mod 12 = 1 을충족시키는 는존재하지않는다. 왜냐하면 2눈금의회전을반복해도 0, 2, 4, 6, 8, 10, 0, 2, 4, 6, 8, 처럼짝수인곳만을가리키기때문이다. 절대로 1은가리키지않는다.

64 다른수들은? 마찬가지로 3 mod 12 = 1 나 4 mod 12 = 1 를충족시키는 도없다.

65 여기서일람표로만들어본다 0은특별하므로제외하도록한다. 1 mod 12 = 1 = 1 2 mod 12 = 1 는존재하지않는다 3 mod 12 = 1 는존재하지않는다 4 mod 12 = 1 는존재하지않는다 5 mod 12 = 1 = 5 6 mod 12 = 1 는존재하지않는다 7 mod 12 = 1 = 7 8 mod 12 = 1 는존재하지않는다 9 mod 12 = 1 는존재하지않는다 10 mod 12 = 1 는존재하지않는다 11 mod 12 = 1 = 11

66 모두다역수를갖지는않는다 역수를가지고있는수는 1, 5, 7, 11 밖에없다 소수인가라고생각할수도있지만꼭그렇지도않다 (2와 3은소수이지만역수를안가진다 ). 그수와 12의최대공약수가 1인지아닌지로판단할수가있는것이다.

67 최대공약수를살펴보면 1 mod 12 = 1 = 1 1 과 12 의최대공약수는 1 5 mod 12 = 1 = 5 5 와 12 의최대공약수는 1 7 mod 12 = 1 = 7 7 과 12 의최대공약수는 1 11 mod 12 = 1 =11 11 과 12 의최대공약수는 1

68 최대공약수를살펴보면 2 mod 12 = 1 는존재하지않는다 2와 12의최대공약수는 1이아니다 3 mod 12 = 1 는존재하지않는다 3와 12의최대공약수는 1이아니다 4 mod 12 = 1 는존재하지않는다 4와 12의최대공약수는 1이아니다 6 mod 12 = 1 는존재하지않는다 6와 12의최대공약수는 1이아니다 8 mod 12 = 1 는존재하지않는다 8와 12의최대공약수는 1이아니다 9 mod 12 = 1 는존재하지않는다 9와 12의최대공약수는 1이아니다 10 mod 12 = 1 는존재하지않는다 10와 12의최대공약수는 1이아니다

69 서로소 ( 素 ) 12 와의최대공약수가 1 인수 (5, 7, 11) 는수학에서는 12 와서로소 ( 素 ) 인수라고부른다.

70 5.3.5 거듭제곱 7 4 =

71 시계에서의거듭제곱이란? 7 눈금오른쪽으로돌린다 를 7 회반복한다 를 7 회반복한다 를 7 회반복한다 바늘은어디를가리키게되는가? 실제계산은간단하다. 여하튼거듭제곱계산을하고나서나눗셈의나머지를취하면된다 (mod 를취하면되는 ).

72 실제계산 74 mod 12 = mod 12 = 2401 mod 12 ( Q 은 2401) = 1 ( Q 는몫이 200이고나머지가 1)

73 좀쉬운계산 74 mod 12 = mod 12 = ((7 7 mod 12) (7 7 mod 12)) mod 12 = ((49 mod 12) (49 mod 12)) mod 12 = (1 1) mod 12 = 1 mod 12 = 1

74 5.3.6 대수 거듭제곱의역연산을대수라고한다. 보통의수학에서대수를구하는계산은그다지어렵지않다. 예를들면 7 X = 49 에서 X 는 2 라는것은금방알수있다. 비록숫자가커져도대수를구하는계산은그다지어렵지않다.

75 시계계산에있어서의대수는이산대수라고한다. 예를들면, 7 X mod 13 = 8 이되는 X 는무엇일까?

76 다음과같이하면 X는 9라는것을알수있다. 7 0 mod 13 = mod 13 = mod 13 = mod 13 = mod 13 = mod 13 = mod 13 = mod 13 = mod 13 = mod 13 = 8

77 우리가주의해야할점 이산대수구하기는어렵다 위의예에서는쉽게 X의값이 9라는것을알수있다 하지만 7과같은작은수가아니고매우큰수라면해당이산대수를구하기는매우어렵다 특히숫자가백자리이상으로커지면이산대수를구하는것은고속연산을수행할수있는컴퓨터를이용하더라도상당히어렵고시간이엄청나게많이걸린다.

78 좋은방법이아직알려지지않았다 현재까지이산대수를구하는고속알고리즘은아직발견되지않았다. 이산대수는키교환프로토콜의하나인 Diffie- Hellman 키교환이나, 공개키알고리즘의하나인 ElGamal 방식에서사용되고있다.

79 5.3.7 시계의바늘에서 RSA 로 여기서알아야할중요한것은단하나이다. 그것은, 7 4 mod 12 와같은식이나와도당황하지말라는것이다. 침착하게 7을 4제곱해서 12로나눈나머지라고읽을수있다면여러분은 RSA를이해할준비가된것이다.

80 5.4 RSA 공개키암호에서는 암호화키 와 복호화키 두개의키를사용한다. 그러나어떻게하면그렇게할수있는것일까? 이절에서는현재가장많이사용되고있는공개키암호알고리즘인 RSA에대해서설명을한다

81 5.4.1 RSA 란 RSA 는공개키암호알고리즘의하나이다. RSA는공개키암호와디지털서명에사용할수있다. 1983년 RSA사는미국에서 RSA 알고리즘에대한특허를취득하였다. 그러나현재는이미특허기한이종료되었다.

82 5.4.2 RSA 에의한암호화 RSA 에서는평문도키도암호문도숫자이다 RSA 암호화 암호문 = 평문 E mod N RSA 의암호문은평문을나타내는수를 E 제곱해 서 mod N 을취한것이다.

83 E 와 N 은무엇일까? RSA의암호화는, 평문을 E제곱해서 mod N을취하는것이므로, E와N이라는한쌍의수를알면누구라도암호화를행할수있다. 따라서 E와 N이 RSA에서사용하는암호화키가된다. 즉, (E, N) 이공개키인것이다. 단 E 와 N 은어떤수라도되는것은아니다. 이들은면밀한계산에의해만들어진수다.

84 5.4.3 RSA 에의한복호화 RSA 에의한복호화는암호화와마찬가지로간단하다. RSA 의복호화 평문 = 암호문 D mod N 암호문을나타내는수를 D제곱해서 mod N을취하면평문을얻을수있다. 바꿔말하면암호문을 D회곱해서그결과를 N으로나눈 나머지를구하면그것이평문이다.

85 D 와 N 은무엇일까? 여기서사용되고있는수N은암호화때에사용한수N과같은수이다. 수D와수N을합친것이RSA의복호화키가된다. D와 N의쌍인 (D, N) 이개인키에해당된다. 궁극적으로 D와 N 모두를알고있는사람만이이암호문을복호화할수있다 D는어떤수라도괜찮은것은아니다. 복호화의키인수 D는수 E와깊은수학적연관이있다.

86 RSA 의암호화 복호화

87 RSA 의암호화와복호화 공개키 E N 개인키 D N 암호문 평문 평문 암호문 RSA 암호화암호문 = 평문 E mod N RSA 복호화평 = 암호문 D mod N

88 5.4.4 키쌍의생성 E, D, N이라는 3개의수는어떻게준비를하는것일까? E와 N이공개키, D와 N이개인키이므로 E, D, N 3개의수를구하는것은키쌍을생성하는것과다름없다.

89 RSA 의키쌍생성순서 (1) N을구한다 (2) L을구한다 (L 은키쌍을생성할때만등장하는수이다 ) (3) E를구한다 (4) D를구한다

90 N 구하기 우선처음에큰소수 p와 q 2개준비한다. 2개의수를서로곱한다. 그결과로나온수가우리가구하는 N이다 N = p q (p, q 는소수 )

91 L 을구한다 L이라는수는 RSA의암호화나복호화에는등장하지않는수로서키쌍을만드는동안에만보조적으로사용하는수이다 L은 p-1과 q-1의최소공배수 (least common multiple; lcm) 이다. 즉, L = lcm(p-1, q-1)

92 E 를구한다 E 는 1 보다크고, L 보다도작은수이다. E 와 L 과의최대공약수 (greatest common divisor; gcd) 는 1 이다. 즉, 1 < E < L gcd(e, L) = 1 E와 L의최대공약수가 1이라는조건은암호화에서사용하는 D의존재를보증하기위해필요한조건이다.

93 D 를구한다 D 는 E 로부터계산해서구한다. D 와 E 와 L 은다음과같은관계를갖는다. 1 < D < L E D mod L = 1 E D mod L = 1은암호문을복호화하면원래의평문으로돌아가는것을보증하기위해사용한다.

94 RSA 의키쌍생성 ( 정리해보자 )

95 RSA 의키쌍 공개키 개인키 PRNG E E x D mod L = 1 D PRNG 소수 p PRNG 소수 q E N = p x q E PRNG = 의사난수생성기 L= lcm(p-1,q-1), gcd(e,l) = 1, 1 < E < L, 1 < D < L

96 5.4.5 구체적계산 구체적인수를써서 RSA의키쌍생성 암호화 복호화를실제로해보자. 그렇지만너무큰수를사용하면계산이복잡하고힘들기때문에작은수를이용하여계산을해보자.

97 키쌍의생성예 N 을구한다 2 개의소수 p=17, q=19 를고른다. N = p q = = 323 L 을구한다 L = lcm(p-1, q-1) = lcm(16. 18) (p-1은 16, q-1은 18) = 144 (16과 18의최소공배수 )

98 키쌍의생성예 E 를구한다 gcd(e, L) = gcd(e, 144) = 1 이되는 E 를구한다 이과같은 E 는많이있다. 예를들면, 다음과같은수이다. 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 여기서는 E 로서 5 를골라보겠다. 여기까지해서공개키는 (E,N)=(5, 323) 이되었다.

99 키쌍의생성예 D 를구한다 D 는식 E D mod L = 1 을충족시켜야만된다. E에뭔가를곱해서 mod L을취하면 1이되는수를찾아보자. D = 29는, 이관계식을충족시킨다. 왜냐하면, E D mod L = 5 29 mod 144 = 145 mod 144 = 1 여기까지해서개인키는 (D,N)=(29, 323) 이되었다.

100 5.4.6 암호화 평문은 N 미만의수, 즉 323 미만의수가아니면안된다. 평문으로서 123을암호화해보자. 평문 E mod N = mod 323 = 225 따라서암호문은 225 가된다.

101 5.4.7 복호화 암호문 225 를복호화하겠다. 복호화에서는개인키 D = 29, N = 323 을사용한다. 암호문 D mod N = mod 323 = 123

102 mod 323 의계산 = = = = mod 323 = mod 323 = mod 323 = mod 323 = 191

103 mod 323 의계산 mod 323 = mod 323 = ( mod 323) ( mod 323) (225 9 mod 323) mod 323 = mod 323 = mod 323 = 123

104 5.5 RSA 에대한공격 기밀성은어떻게되어있는것일까? 즉, 암호해독자는왜평문을복원할수는없는것일까? 여기서암호해독자가알고있는것과모르는것을정리해본다.

105 암호해독자가아는것과모르는것 암호해독자가알고있는것 암호문 : 도청해서얻은것이라고하면알기쉽겠군. 수 E 와 N : 공개키로서공개되어있으므로암호해독자는 E 와 N 을알고있다. 암호해독자가모르는것 평문 : 지금부터해독하려고하는내용이다. 수D: 개인키중적어도D는모르고있다. 기타 : 암호해독자는키쌍을만들었을때의 p, q, L을모르고있다.

106 5.5.1 암호문으로부터평문구하기 RSA 의암호문은다음과같은형태이다 암호문 = 평문 E mod N 만약 mod N 이없고, 암호문 = 평문 E 이었다면암호문으로부터평문을구하는것은그다지어렵지않다.

107 이산대수구하기는매우어렵다 하지만 mod N이붙어있으면평문을구하는것은이산대수를구한다는매우곤란한문제가된다. 인류는아직이산대수를구하는빠른방법을알지못하기때문이다.

108 5.5.2 전사 (brute force) 공격 수 D 를알면암호문을복호화할수있다. 그렇기때문에 RSA에대한공격방법으로서, D 의후보가되는수를순서대로시도해서복호화한다는전사공격을생각할수있다. 전사공격은 D의비트수가크면클수록시도해보아야할수도많아지고계산도복잡해지므로점점더시간이걸리며어려워진다. 따라서비트수가충분히크면전사공격으로수 D를찾아내는것은현실적으로는불가능해진다.

109 전사공격을어렵게하기 통상 RSA에서는 p와 q의비트수로서 512 비트이상을 N은 1024 비트이상을이용한다. E나 D는 N과같은정도의크기로할수있으므로 D를찾아내기위해서는 1024 비트이상의전사공격이필요해진다. 이비트길이의전사공격에의해 D를찾아내는것은지극히곤란하다.

110 5.5.3 E 와 N 으로부터 D 구하기 암호해독자는 D 를알지못한다. 그러나공개키인 E 와 N 은알고있다. 키쌍을만들때D는원래E로부터계산해서얻은것이었다. 그렇다면암호해독자도 E로부터 D를구할수있는것은아닐까?

111 어렵다 아니다. 키쌍을만들었을때의방법을생각해보라. D 와 E 의관계식, E D mod L = 1 에서사용된것은 L이다. L은 lcm(p-1, q-1) 이므로 E로부터 D를계산할때는 p와 q를사용하게된다. 하지만, 암호해독자는 p와 q를전혀모른다. 따라서키쌍을만들었을때와똑같은계산을해서 D를구할수는없다.

112 RSA 의중요한포인트 소수 p와 q를암호해독자가알게해서는안된다는것이다. p와 q가암호해독자의손에넘어간다는것은개인키가암호해독자의손에들어가는것과같다.

113 N 을소인수분해하는공격 p 와 q 를암호해독자가알게해서는안된다. 하지만 N = p q라는관계식이있고, 게다가 N 은공개되어있다. N으로부터p와q를구할수는없는것일까? p와 q는소수이기때문에 N으로부터 p와 q를구하는것은자연수 N을소인수분해하는것과같다. 큰수의소인수분해를고속으로할수있는방법이발견되면RSA는해독할수있다

114 하지만 그러나현재큰수의소인수분해를고속으로행하는방법은아직발견되지않았다. 소인수분해가정말로어려운문제인가하는것은증명된것이아니며, 소인수분해를간단히행하는방법이존재하는지의여부도아직모른다.

115 p 와 q 를추측하는공격 소인수분해를하지않아도 p와 q가암호해독자에게알려질가능성은있다. p와 q는의사난수생성기로생성하는것이기때문에의사난수생성기의품질이나쁘면p와q 를암호해독자가추측해버릴우려가있다. 생성하는난수를암호해독자가추측할수있어서는안된다.

116 기타공격 N 을소인수분해해서 p 와 q 를구할수있으면 D 를구할수있다. 그러나 D 를구하는것 이 N 을소인수분해하는것 과같은것인지어떤지는수학적으로증명되어있는것은아니다. 어쩌면 N 을소인수분해하지않아도 (p 와 q 를몰라도 ) E 와 N 으로부터 D 를구하는방법이발견될지도모른다. 이와같은방법은아직발견되지않았고애초부터존재하는것이지어떤지도모른다.

117 5.5.4 중간자 (man-in-the-middle) 공격 RSA를해독하는것은아니지만, 기밀성에대한매우유효한공격방법이다. man-in-the-middle 공격이란적극적공격자맬로리가송신자와수신자사이에들어가서, 송신자에대해서는수신자처럼, 수신자에대해서는송신자처럼행세하는공격이다.

118 중간자공격절차 (1) 앨리스는밥에게메일을보내서공개키를받으려고한다. 밥에게 : 당신의공개키를주십시오. 앨리스로부터 (2) 맬로리는, 앨리스가밥에게공개키를요청한것을도청으로감지한다. (3) 밥은앨리스로부터온메일을읽고자신의공개키를앨리스에게보낸다. 앨리스에게 : 이것이내공개키야. 밥으로부터 (4) 맬로리는밥의이메일을빼앗아서앨리스에게도달하지못하도록한다. 그리고밥의공개키를살짝보존한다. 이밥의공개키는나중에맬로리가사용한다.

119 중간자공격절차 (5) 맬로리는밥행세를하며맬로리자신의공개키를앨리스에게보낸다. 앨리스에게 : 이것이내공개키야. 밥으로부터 ( 실은맬로리가자신의공개키를앨리스에게보내면서밥의행세를하는것이다.) (6) 앨리스는자신의메시지를밥의공개키 ( 실은맬로리의공개키 ) 로암호화한다. 밥에게 : 사랑해. 앨리스로부터 그렇지만앨리스가가지고있는것은밥의공개키가아니고맬로리의공개키이다. 그러므로앨리스는자신의메시지를맬로리의공개키로암호화한것이된다. (7) 앨리스는암호화한메시지를밥에게보낸다.

120 중간자공격절차 (8) 맬리로는앨리스의암호메일을빼앗는다. 이암호메일은맬로리의공개키로암호화되어있기때문에맬로리는복호화할수있다. 맬로리는앨리스의러브레터를읽는다. (9) 맬로리는앨리스행세를하며위조메일을만든다. 밥에게 : 당신따위정말싫어. 앨리스로부터 ( 실은맬로리 ) 그리고아까 (4) 에서보존해둔밥의공개키를써서이위조메일을암호화하여밥에게보낸다. (10) 밥은받은암호메일을자신의개인키로복호화한다. 그리고, 밥에게 : 당신따위정말싫어. 앨리스로부터 ( 실은맬로리 ) 라는메일을읽고쇼크를받는다.

121 메시지의송신자앨리스 적극적인공격자맬로리 메시지의수신자밥 (1) 당신의공개키를주시오 (2) 맬로리는통신을도청한다 (6) 앨리스는밥의공개키라고생각하고, 맬로리의공개키로메시지를암호화한다 (5) 이것이내공개키야 맬로리의공개키 (7) 앨리스는밥에게암호문을보낸다맬로리의공개키에의한암호문 (3) 이것이내공개키야 밥의공개키 (4) 맬로리는메일을빼앗아밥의공개키를보존한다 (8) 맬로리는메일을빼앗아자신의개인키로복호화한다 (9) 맬로리는위조메일을만들어밥의공개키로암호화해서밥에게보낸다 밥의공개키 10) 밥은개인키로복호화한다. 맬로리에의한 man-in-the-middle 공격

122 5.6 다른공개키암호 RSA는현재가장많이보급되어있는공개키암호알고리즘이다 RSA 이외에도공개키암호는많이있다. ElGamal 방식 Rabin 방식 타원곡선암호 이들암호는모두암호와디지털서명에이용할수있다.

123 5.6.1 ElGamal 방식 ElGamal 방식은 Taher ElGamal에의한공개키알고리즘이다. RSA는소인수분해가곤란하다는것을이용했지만, ElGamal 방식에서는 mod N으로이산대수를구하는것이곤란하다는것을이용한다. ElGamal 방식에의한암호화에서는암호문의길이가평문의 2배가되어버린다는결점이있다. 암호소프트웨어 GnuPG에구현되어있다.

124 5.6.2 Rabin 방식 Rabin 방식은 M. O. Rabin에의한공개키알고리즘이다. Rabin 방식은 mod N으로평방근을구하는것이곤란하다는것을이용하고있다. RSA는큰수N의소인수분해를하지않아도해독할수있는가능성이있지만, Rabin 방식에의한공개키암호의해독은소인수분해를행하는것과같은정도로어렵다는것이수학적으로증명되어있다.

125 5.6.3 타원곡선암호 타원곡선암호 (elliptic curve cryptosystems; ECC) 는최근주목받고있는공개키암호알고리즘이다. RSA 에비해키의비트수를적게할수있는것이특징이다. 타원곡선이라불리는곡선을정하고, 그곡선상에있는점에대하여특수한 연산 을정의한다. 타원곡선암호에서는이연산의역연산이어렵다는것을이용한다.

126 5.7 공개키암호에관한 Q&A Q&A의형식으로공개키암호에관한의문에답하겠다. 주로오해하기쉬운내용을선택했다.

127 5.7.1 공개키암호의기밀성 의문 : 답 : 공개키암호는대칭암호보다도기밀성이높은가? 이것만으로는답할수없다. 왜냐하면키의비트길이에따라기밀성의정도는변화하기때문이다.

128 5.7.2 공개키암호와대칭암호의 키길이 의문 : 답 : 1024 비트길이의키를갖는공개키암호와, 128 비트길이의키를갖는대칭암호에서는비트길이가긴공개키암호쪽이안전한가? 아니다. 공개키암호의키길이와, 대칭암호의키길이는직접비교할수없다. 1024비트길이의공개키암호와 128비트길이의대칭암호에서는, 128비트길이의대칭암호쪽이전사공격에강하다는것을알수있다.

129 전사공격에대해서같은강도를갖 는키길이비교

130 5.7.3 대칭암호의미래 의문 : 공개키암호가생겼기때문에앞으로대칭암호는사용되지않게되는것인가? 답 : 아니다. 일반적으로같은정도의기밀성을갖는키길이를선택했을경우, 공개키암호는대칭암호보다도몇백배나느려진다. 공개키암호는긴메시지를암호화하기에는적합하지않다. 목적에따라대칭암호와공개키암호두가지모두사용되게될것이다.

131 5.7.4 RSA 와소수 의문 : 답 : RSA 의키쌍을모두가자꾸만들어가면그사이소수가없어져버리는것은아닐까? 그럴염려는없다. 512 비트로표현할수있는소수의수는대략 10 의 150 거듭제곱으로전우주에존재하는원자의개수보다도많은수이다.

132 5.7.5 RSA 와소인수분해 의문 : 답 : RSA 로암호화할때큰수의소인수분해를할필요가있는것일까? 아니다. RSA 의암호화에서도, 복호화에서도, 그리고키쌍의생성에서도큰수의소인수분해를할필요는없다.

133 의문 : 답 : RSA 를해독하는것은큰수를소인수분해하는것과같은것인가? 같은것인지아닌지아직모른다. 분명히소인수분해를고속으로할수있다면 RSA는해독된다. 그러나 RSA를해독하려면소인수분해를꼭해야한다는것이증명된것은아니다. 어쩌면소인수분해를하지않아도해독할수있는방법이발견될지도모른다.

134 5.7.6 RSA 의비트길이 의문 : 답 : 소인수분해되지않기위해서는 N 은몇비트의길이가필요한가? 몇비트가되어도언젠가는소인수분해된다.