Chapter 10 비대칭 키 암호 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Chapter 10 Objectives  대칭키 암호와 비대칭 키 암호시스템의 차이점 트랩도어 일방향 함수 소개와 비대칭 키 암호시스템에서의 응용 비대칭 키 암호시스템의 초기 아이디어인 배낭암호시스템의 소개  RSA 암호시스템  Rabin 암호시스템  ElGamal 암호시스템  타원곡선 암호시스템

Topics discussed in this section: 10-1 INTRODUCTION 대칭 키 암호시스템과 비대칭 암호 시스템은 병존하게 될 것이며 보안 서비스 분야에서 각각의 역할을 하게 될 것이다. 사실은 이 두 시스템은 서로 보완적이다. 한 시스템의 장점이 다른 한 시스템의 단점을 보완하고 있다. Topics discussed in this section: 10.1.1 키(Keys) 10.1.2 일반적인 아이디어 (General Idea) 10.1.3 양쪽에 필요한 것 (Need for Both) 10.1.4 트랩도어 일방향 함수 (Trapdoor One-Way Function) 10.1.5 배낭 암호 (Knapsack Cryptosystem)

대칭 키 암호시스템은 비밀을 공유하는 것에 기반을 두고 있다. 비대칭 키 암호시스템은 개별적 비밀에 기반을 두고 있다. 10-1 개요(INTRODUCTION) 두 시스템의 개념적인 차이는 어떻게 비밀을 유지하는 가에 따라 달라진다. 대칭 키 암호시스템에서는 비밀을 두 사람이 서로 공유해야 한다. 비대칭 키 암호시스템에서는 비밀을 공유하지 않고 각자 비밀로 보존한다. Note 대칭 키 암호시스템은 비밀을 공유하는 것에 기반을 두고 있다. 비대칭 키 암호시스템은 개별적 비밀에 기반을 두고 있다.

대칭 키 암호시스템은 기호를 대체시키거나 치환하는 것이다. 비대칭 키 암호시스템은 숫자를 다른 숫자로 변경하는 것이다. 개요 대칭 키 암호시스템이 기호(문자나 비트)를 대체하거나 치환하는 데 기반을 두고 있는 반면에 비대칭 키 암호시스템은 수를 이용한 수학적 함수를 응용하는 데 기반을 두고 있다. 대칭 키 암호시스템에서는 평문과 암호문은 기호의 조합으로 간주된다. Note 대칭 키 암호시스템은 기호를 대체시키거나 치환하는 것이다. 비대칭 키 암호시스템은 숫자를 다른 숫자로 변경하는 것이다.

10.1.1 키(Keys) 비대칭 키 암호시스템에서는 두 개의 서로 다른 키를 사용한다. 한 개는 개인 키이고 다른 한 개는 공개 키이다. Figure 10.1 비대칭-키 암호시스템의 암호화와 복호화

10.1.2 일반적인 아이디어 (General Idea) Figure 10.2 비대칭-티 암호시스템의 일반적 아이디어

C = f (Kpublic , P) P = g(Kprivate , C) 10.1.2 Continued 평문/암호문 (Plaintext/Ciphertext) 대칭 키 암호시스템과는 다르게 비대칭 키 암호시스템에서는 평문이나 암호문이 정수로 다루어진다. 암호화/복호화 (Encryption/Decryption) C = f (Kpublic , P) P = g(Kprivate , C)

10.1.3 양쪽에 필요한 것 (Need for Both) 매우 중요한 사실 중의 하나로 자주 잘못 이해하고 있는 것이 있다. 비대칭 키(공개 키) 암호시스템의 등장으로 인해 대칭 키(비밀 키) 암호시스템의 역할이 없어지는 것이 아니라는 것이다.

(Trapdoor One-Way Function) 10.1.4 트랩도어 일방향 함수 (Trapdoor One-Way Function) 비대칭 키 암호시스템의 뒤에 숨어있는 주요한 아이디어는 트랩도어 일방향 함수(trapdoor one-way function) 개념이다. 함수 (Functions) Figure 10.3 정의역과 공역 사이의 대응규칙인 함수

10.1.4 Continued 일방향 함수 (One-Way Function (OWF)) 1. f 는 계산이 쉽다. 트랩도어 일방향 함수 (Trapdoor One-Way Function (TOWF)) 3. y와 트랩도어(trapdoor)(비밀)가 주어지면 x 를 쉽게 계산할 수 있다.

10.1.4 Continued Example 10. 1 n 이 매우 큰 수라면, n = p × q 는 일방향 함수이다. 주어진 p 와 q 로부터 n 을 계산하는 것은 매우 쉽다. 하지만 주어진 n 으로부터 p 와 q 를 계산하는 것은 매우 어렵다. 이것이 바로 소인수분해 문제이다. Example 10. 2 n 이 매우 큰 수라면, 함수 y = xk mod n 은 하나의 트랩도어 일방향 함수이다. 주어진 x, k, 와 n에 대해 우리가 y 를 계산하는 것은 쉽다. 하지만 y, k, 와 n이 주어졌을 때, x 를 계산해내는 것은 매우 어렵다. 이것이 이산대수문제이다. 그러나 만약에 우리가 k × k ′ = 1 mod f(n)이 되는 트랩도어 k′ 를 알고 있다면, x = yk′ mod n 을 이용하여 x를 구할 수 있다. 이것이 바로 유명한 RSA이다.

ai ≥ a1 + a2 + … + ai−1 10.1.5 배낭 암호 (Knapsack Cryptosystem) 정의( Definition) a = [a1, a2, …, ak ] and x = [x1, x2, …, xk]. 주어진 a와 x로부터 s를 계산하는 것은 매우 쉽다. 하지만 s와 a가 주어졌다고 했을 때, x를 구하는 것은 어렵다. 초증가 순서짝 (Superincreasing Tuple) ai ≥ a1 + a2 + … + ai−1

10.1.5 Continued

10.1.5 Continued Example 10. 3 매우 간단한 예로서 a = [17, 25, 46, 94, 201,400] 이고 s = 272 라고 가정해보자. 표 10.1에 knapsackSum 하고 inv_knapsackSum 알고리즘을 이용하여 어떻게 순서짝 x를 구했는지 나타내었다. 이 경우에 x = [0, 1, 1, 0, 1, 0] 이다. 즉, 25, 46, 201 이 배낭 속에 들어있다는 것을 나타낸다.

10.1.5 Continued 배낭을 이용한 비밀 통신 (Secret Communication with Knapsacks.) Figure 10.4 배낭 암호시스템을 이용한 비밀 통신

10.1.5 Continued Example 10. 4 이것은 절차를 보여주기 위해서 만들은 아주 간단한 예이다. 1. 키 생성: a. 밥은 초증가 순서짝 을 만든다. b. 밥은 모듈로로 , 을 선택한다. 치환표로는 을 택한다. c. 밥은 순서짝 를 계산한다. d. 밥은 순서짝 e. 밥은 a 를 공개한다. 그리고 n, r, b 는 비밀로 한다.

10.1.5 Continued Example 10. 4 2. 앨리스가 단 하나의 문자 “g" 만을 밥에게 보낸다고 가정을 해보자. 앨리스는 7-비트 ASCII 코드를 이용하여 “g"를 로 부호화한다. 그 다음 순서짝 을 생성한다. 이것이 평문이다. b. 앨리스는 s=knapsackSum(a, x)=2165를 생성한다. 이것이 밥에게 보낼 암호문이다.

10.1.5 Continued Example 10. 4 3. 밥은 암호문 s=2165 를 복호화 할 수 있다. a. 밥은 s’=x × r -1 mod n =2165 × 37-1 mod 900 = 527 을계산한다. b. 밥은 x’=inv_knapsackSum(s’, b) =[1, 1, 0, 1, 0, 1, 1]를 계산한다. c. 밥은 x=permute(x’) =[1, 1, 0, 0, 1, 1, 1]을 계산하여 (1100111)2를 얻는다. 이것을 ASCII 코드를 이용하여 문자로 환원하면 문자 “g"를 얻는다.

Topics discussed in this section: 10-2 RSA CRYPTOSYSTEM 가장 많이 사용되는 공개 키 알고리즘은 RSA 암호시스템인데 RSA라는 이름은 이것을 고안해낸 사람들(Rivest, Shamir, Adleman)의 이름을 따서 만들은 것이다. Topics discussed in this section: 10.2.1 소개 (Introduction) 10.2.2 절차 (Procedure) 10.2.3 간단한 예제 (Some Trivial Examples) 10.2.4 RSA에 대한 공격 (Attacks on RSA) 10.2.5 권장 사항 (Recommendations) 10.2.6 최적 비대칭 암호 패딩(OAEP) (Optimal Asymmetric Encryption Padding (OAEP)) 10.2.7 응용(Applications)

10.2.1 소개 (Introduction) Note Figure 10.5 RSA 연산의 복잡도 이것을 공격하려면 이브는 을 계산해야 한다.

10.2.2 Procedure Figure 10.6 RSA의 암호화, 복호화와 키 생성

R = <Zn , +, × > G = <Z f(n)∗, × > 10.2.2 Continued 두 개의 대수구조 (Two Algebraic Structures) 암호화/복호화 환 Encryption/Decryption Ring: R = <Zn , +, × > 키 생성 군 Key-Generation Group: G = <Z f(n)∗, × >

10.2.2 Continued

10.2.2 Continued 암호화 (Encryption)

10.2.2 Continued 복호화 (Decryption)

10.2.2 Continued RSA 증명 (Proof of RSA)

10.2.3 Some Trivial Examples Example 10. 5 밥은 p 와 q 를 7 과 11로 선택해서 n = 77을 계산한다. 그러면 f(n) = (7 − 1)(11 − 1) 또는 60이 된다. 밥은 이제 Z60∗ 안에서 두 개의 지수 e 와 d 를 선정한다. 만약 e 를 13으로 선택한다면, d 는 37이 된다. e × d mod 60 = 1 으로서 서로 역원관계임을 명심하기 바란다. 이제 앨리스가 평문 5 를 밥에게 보내려고 한다고 하자. 앨리스는 공개된 값 13을 이용해서 5를 암호화 한다. 밥은 암호문 26 을 수신하게 되며 자신의 개인키인 37을 이용하여 이 암호문을 복호화 한다.

10.2.3 Some Trivial Examples Example 10. 6 여기서는 다른 사람 존이 밥에게 메시지를 보내려고 한다고 해보자. 존은 밥이 공개한(밥의 사이트에 공개된) 공개 키인 13을 활용할 수 있다. 존의 평문이 63이라고 한다면 존은 다음과 같이 암호화를 한다. 밥은 암호문 28을 수신하게 되며 자신의 개인 키인 37을 이용하여 이 암호문을 복호화 한다.

10.2.3 Some Trivial Examples Example 10. 7 제니퍼는 자신의 키 쌍을 만들기 위해 p = 397, q = 401을 사용하여 n = 159197을 계산했다. 또한 (n) = 158400을 계산했다. 그리고 e = 343 and d = 12007을 선택했다. 만약에 테드가 e 와 n을 알면 메시지를 제니퍼에게 보낼 수 있다는 것을 보여라. 테드가 제니퍼에게 보내고자 하는 메시지가 “NO" 라고 가정해보자. 테드는 일단 각 문자를 두 자리 숫자로 된 코드(00에서 25까지)로 바꾼다. 그 다음 이 두 개의 문자코드를 이어붙여 4자리 숫자를 만든다. 이렇게 해서 만들어진 문자코드인 평문은 1314이다. 그림 10.7에 이 단계를 나타내었다.

10.2.3 Continued Figure 10.7 예 10.7의 암호화와 복호화

10.2.4 Attacks on RSA Figure 10.8 RSA에 대한 가능한 공격들

10.2.6 OAEP Figure 10.9 최적 비대칭 암호 패딩(OAEP)

10.2.6 Continued Example 10. 8 여기에 실제적인 예를 들어보기로 하자. 우리는 512-비트 p 와 q 를 선택하고 n 과 f(n)을 계산하자. 그 다음 e 를 선택하고 f(n)과 서로 소가 되는지를 점검해보자. 그리고 나서 d를 계산한다. 마지막으로 암호화와 복호화가 되는 결과를 보여주기로 한다. 정수 p 는 159 자리 십진수이다.

10.2.6 Continued 모듈로 값 n = p × q 이고 이것은 309자리 십진수이다. Example 10. 8 Continued 모듈로 값 n = p × q 이고 이것은 309자리 십진수이다. f(n) = (p − 1)(q − 1) 은 309자리 십진수이다.

10.2.6 Continued Example 10. 8 Continued 밥은 e = 35535 (65537이 이상적임)를 선택하고 이것이 f(n)과 서로 소인지 확인하기 위해 검증한다. 밥은 모듈로 f(n)에 대한 e의 역원을 구하고 그것을 d라고 한다.

10.2.6 Continued Example 10. 8 Continued 앨리스는 "THIS IS A TEST" 라는 메시지를 보내고자 한다. 이것을 00-26 인코딩 시스템을 이용해서 숫자로 변경을 할 수 있다.(여기서 26은 스페이스를 나타낸다) 앨리스가 계산한 암호문 C = Pe 는 다음과 같다.

10.2.6 Continued 밥은 암호문으로부터 P = Cd 를 이용하여 평문을 복호화할 수 있다. Example 10. 8 Continued 밥은 암호문으로부터 P = Cd 를 이용하여 평문을 복호화할 수 있다. 이것으로부터 코드를 복구한 평문은 "THIS IS A TEST" 이다.

Topics discussed in this section: 10-3 Rabin 암호시스템 (RABIN CRYPTOSYSTEM) Rabin 암호시스템은 e 와 d가 고정된 값을 갖는 RSA 암호시스템으로 간주된다. 달리 말하면 암호화는 C ≡ P2 (mod n) 이고 복호화는 P ≡ C1/2 (mod n).이다. Topics discussed in this section: 10.3.1 절차(Procedure) 10.3.2 Rabin 시스템의 보안 (Security of the Rabin System)

10-3 Continued Figure 10.10 Rabin 암호시스템에서 암호화, 복호화와 키 생성

10.3.1 Procedure 키 생성 (Key Generation)

10.3.1 Continued 암호화 (Encryption)

Rabin 암호시스템은 결정적 알고리즘이 아니다. 복호화를 하면 동등한 확률로 4 개의 평문 후보가 나타난다. 10.3.1 Continued 복호화 (Decryption) Note Rabin 암호시스템은 결정적 알고리즘이 아니다. 복호화를 하면 동등한 확률로 4 개의 평문 후보가 나타난다.

10.3.1 Continued Example 10. 9 Rabin 알고리즘을 설명하기 위해서 아주 간단한 예를 들어보기로 하자. 밥은 p = 23 과 q = 7 1. 을 선택한다. 이 두 수는 모두 모듈로 4로 3과 합동이란 점에 유의하기 바란다. 밥은 n = p × q = 161을 계산한다. 밥은 n을 공개한다. 반면에 p와 q는 비밀로 유지한다. 앨리스가 평문 P = 24 를 밥에게 보내고자 한다. 161하고 24는 서로 소이다. 24는 Z161* 의 원소이다. 앨리스는 C = 242 = 93 mod 161을 계산해서 이 결과인 93을 밥에게 보낸다.

10.3.1 Continued Example 10. 9 밥은 93을 수신하고 다음 4 개의 값을 계산한다. a1 = +(93 (23+1)/4) mod 23 = 1 mod 23 a2 = −(93 (23+1)/4) mod 23 = 22 mod 23 b1 = +(93 (7+1)/4) mod 7 = 4 mod 7 b2 = −(93 (7+1)/4) mod 7 = 3 mod 7 밥은 4 개의 가능한 답 (a1, b1), (a1, b2), (a2, b1), (a2, b2) 을 선택하고 중국 인 나머지 정리를 사용해서 4 개의 가능한 평문인 116, 24, 137, and 45 를 구한다. 이 4 개는 모두 161과 서로 소이다. 오직 2 번째 평문만이 앨리스가 보낸 평문과 동일한 것이다.

Topics discussed in this section: 10-4 ElGamal 암호시스템 (ELGAMAL CRYPTOSYSTEM) RSA 와 Rabin 이외에 또 다른 공개 키 암호시스템으로 ElGamal 이 있는데 이것은 발명자의 이름 Taher ElGamal을 따서 지은 이름이다. ElGamal은 제 9장에서 토론한 이산대수 문제에 근거해서 만든 시스템이다. Topics discussed in this section: 10.4.1 ElGamal 암호시스템 (ElGamal Cryptosystem) 10.4.2 절차(Procedure) 10.4.3 증명(Proof) 10.4.4 분석(Analysis) 10.4.5 ElGamal의 안전성(Security of ElGamal) 10.4.6 응용(Application)

10.4.2 Procedure Figure 10.11 ElGamal에서 키 생성, 암호화와 복호화

10.4.2 Continued 키 생성(Key Generation)

10.4.2 Continued

ElGamal 암호시스템의 암호화와 복호화의 비트-연산 복잡도는 다항식 수준이다. 10.4.2 Continued Note ElGamal 암호시스템의 암호화와 복호화의 비트-연산 복잡도는 다항식 수준이다.

10.4.3 Continued 밥은 암호문 (5와 6)을 수신하고 평문을 계산한다. Example 10. 10 간단한 예를 하나 들어보기로 하자. 밥이 p = 11 과 e1 = 2 를 선택했다. 여기서 2는 Z11* 의 한 우너시근이라는 점에 유의하기 바란다. 밥은 d = 3 을 선택하고 e2 = e1d = 8 을 계산한다. 그래서 공개키는 (2, 8, 11) 이고 개인키는 3이 된다. 앨리스는 r = 4 를 선택하고 평문 7에 대한 C1 과 C2 를 계산한다. 밥은 암호문 (5와 6)을 수신하고 평문을 계산한다.

10.4.3 Continued Note Example 10. 11 복호화에서 P = [C2 × (C1d) −1] mod p 를 사용하는 대신에 곱셈에 대한 역원의 계산을 생략하고 P = [C2 × C1 p−1−d] mod p 를 사용할 수 있다(제 9장 페르마의 리틀 정리 참조). 예 10.10에서 우리는 P = [6 × 5 11−1−3] mod 11 = 7 mod 11 을 계산할 수 있다. Note ElGamal 암호시스템이 안전하기 위해서 p는 적어도 300자리 이상의 십진수이어야 하고 r은 암호화 할 적마다 매번 다르게 사용해야 한다.

10.4.3 Continued Example 10. 12 보다 현실적인 예를 하다 들어보자. 밥은 512 비트(이상적인 비트 수는 1024 이지만)짜리 정수를 사용한다고 해보자. 이 정수 p 는 155 자리 십진수이다(이상적인 수는 300자리를 가져야 한다). 밥은 e1, d 를 선택하고 아래와 같이 e2 를 계산한다.

10.4.3 Continued Example 10. 10 앨리스는 평문 P = 3200 을 밥에게 보내려고 한다. 앨리스는 r = 545131 을 선택한 다음 C1과 C2를 계산한 다음 이를 밥에게 보낸다. 밥은 평문 P = C2 × ((C1)d)−1 mod p = 3200 mod p 를 계산한다.

Topics discussed in this section: 10-5 타원 곡선 암호시스템 (ELLIPTIC CURVE CRYPTOSYSTEMS) 비록 RSA와 ElGamal이 안전한 비대칭 키 암호시스템이기는 하지만 보안을 위해서는 키의 길이가 매우 커야 한다는 대가를 치러야 한다. 연구자들은 이들과 동일한 수준의 보안성을 제공하면서 키의 길이는 짧아도 되는 암호시스템에 대해서 연구하였다. 이러한 결과로 들을 수 있는 것이 바로 타원 곡선 암호시스템(elliptic curve cryptosystem: ECC)이다. Topics discussed in this section: 10.5.1 실수상의 타원 곡선 (Elliptic Curves over Real Numbers) 10.5.2 GF( p)상의 타원 곡선 (Elliptic Curves over GF( p)) 10.5.3 GF(2n) 상의 타원 곡선 (Elliptic Curves over GF(2n)) 10.5.4 ElGamal을 시뮬레이션 한 타원 곡선 암호시스템 (Elliptic Curve Cryptography Simulating ElGamal)

10.5.1 Elliptic Curves over Real Numbers 일반적으로 타원 곡선 방정식은 다음과 같다. 실수상의 타원 곡선은 다음과 같은 특별한 범주에 속하는 타원 곡선을 사용한다.

Example 10. 13 그림 10.12는 타원 곡선인 y2 = x3 − 4x 와 y2 = x3 − 1 의 두 예의 그래프를 나타내고 있다. 두 개 다 정칙 타원 곡선이다. 그러나 첫 번째 곡선은 3 개의 실근을 갖는다 (x = −2, x = 0, and x = 2). 그러나 두 번째 곡선은 오직 1 개의 실근(x = 1) 을 갖고 2 개의 허근을 갖는다. Figure 10.12 실수 체 위의 두 개의 타원곡선

10.5.1 Continued Figure 10.13 타원곡선상의 3 가지 덧셈

10.5.1 Continued 1. 2. 3. 수학적으로 이런 경우에 교점이 무한대에 있다고 말한다. 그리고 그 점을 0 이라고 정의하고 무한원점(point at infinity) 혹은 영점(zero point)라고 부른다. 이것이 바로 이 군의 덧셈에 대한 항등원이다.

10.5.2 Elliptic Curves over GF( p) 역원 구하기 (Finding an Inverse) 점 (x, y) 의 역원은 (x, −y) 이다. 여기서 −y 는 y 의 덧셈에 대한 역원이다. 예를 들면, p = 13 이라면, (4, 2)의 역원은 (4, 11)이다. 곡선 상의 점 찾기 (Finding Points on the Curve) 알고리즘 10.12는 곡선 Ep(a, b) 상의 점들을 찾는데 사용하는 의사코드를 나타내고 있다.

10.5.2 Continued

Example 10. 14 타원 곡선 E13(1,1) 을 정의하라. 방정식은 y2 = x3 + x + 1 이고 계산은 모듈로 13으로 한다. Figure 10.14 GF(p) 위에 정의된 타원곡선상의 점들

10.5.2 Continued Example 10. 15 예 10.14의 두 점을 더해보자. P = (4, 2), Q = (10, 6)일 때 R = P + Q를 구해보자. a. λ = (6 − 2) × (10 − 4)−1 mod 13 = 4 × 6−1 mod 13 = 5 mod 13. b. x = (52 − 4 −10) mod 13 = 11 mod 13. c. y = [5 (4 −11) − 2] mod 13 = 2 mod 13. d. R = (11, 2), 이것이 예 10.14의 곡선 상의 점이다.

(Elliptic Curves over GF(2n)) 역원 구하기 (Finding Inverses) If P = (x, y)라면 −P = (x, x + y) 이다. 곡선 상의 점 찾기 (Finding Points on the Curve) 제 7장에서 공부했던 다항식 생성원을 사용해서 곡선 상의 점을 찾을 수 있는 알고리즘을 작성할 수 있다.

10.5.3 Continued Example 10. 16 기약 다항식 f(x) = x3 + x + 1 을 사용해서 원소가 {0, 1, g, g2, g3, g4, g5, g6} 인 GF(23) 을 생각해보자. 여기서 기약 다항식이란 g3 + g + 1 = 0 혹은 g3 = g + 1 인 경우이다.

10.5.3 Continued Example 10. 16 Continued 타원 곡선 y2 + xy = x3 + g3x2 + 1, a = g3 b = 1 을 이용하면, 그림 10.15에 나타낸 것 처럼 이 곡선 상의 점들을 구해낼 수 있다. Figure 10.15 GF(2n) 위에 정의된 타원곡선상의 점들

10.5.3 Continued 두 점 더하기 (Adding Two Points) 만약 P = (x1, y1), Q = (x2, y2), Q ≠ −P 이고 , Q ≠ P 라면 R = (x3, y3) = P + Q 1. 는 다음과 같이 구할 수 있다. 2. 만약 Q = P 라면 R = P + P (혹은 R = 2P) 1. 은 다음과 같이 구할 수 있다.

10.5.3 Continued Example 10. 17 R = P + Q 를 구해보자. 단 P = (0, 1) 이고 Q = (g2, 1)이다. 그러면 λ = 0 이고 R = (g5, g4)이다. Example 10. 18 R = 2P 를 구해보자. 단 P = (g2, 1) 이다. 그러면 λ = g2 + 1/g2 = g2 + g5 = g + 1 이고 R = (g6, g5)이다.

10.5.4 ECC Simulating ElGamal Figure 10.16 타원곡선을 이용한 ElGamal 암호시스템

ECC의 안전성은 타원 곡선 대수문제를 해결하는 어려움에 의존하고 있다. 10.5.4 Continued 공개 키와 개인 키 생성 (Generating Public and Private Keys) E(a, b) e1(x1, y1) d e2(x2, y2) = d × e1(x1, y1) 암호화 Encryption 복호화 (Decryption) Note ECC의 안전성은 타원 곡선 대수문제를 해결하는 어려움에 의존하고 있다.

10.5.4 Continued Example 10. 19 여기에 제시한 예는 GF(p) 상의 타원 곡선을 사용한 암호에 대한 간단한 예이다. 밥은 GF(p)상의 타원 곡선으로 E67(2, 3) 을 선택한다. 밥은 e1 = (2, 22) 와 d = 4를 선택한다. 밥은 e2 = (13, 45) 를 선택한다. 여기서 e2 = d × e1이다. 밥은 순서짝인 (E, e1, e2)를 공개한다. 앨리스는 평문 P = (24, 26) 을 밥에게 보내려고 한다. 앨리스는 r = 2를 선택한다.

10.5.4 Continued Example 10. 19 6. 앨리스는 C1=(35, 1)을 구한다. 여기서 C1=r ×e1이다. 7. 앨리스는 C2=(21, 44)를 구한다. 여기서 C2=P + r × e2이다. 8. 밥은 C1과 C2를 구한다. 밥은 2 × C1(31, 1)을 사용해서 (23, 25)를 구한다. 9. 밥은 (23, 25)의 역원인 (23, 42)를 구한다. 10. 밥은 원래의 평문인 P=(24, 26)을 구하기 위해 (23, 42)에 C2=(21, 44) 를 더한다.