[Cryptography] 비대칭 키 암호화 (Asymmetric-Key Encipherment)

Computer Science/Security

[Cryptography] 비대칭 키 암호화 (Asymmetric-Key Encipherment)

나죽못고나강뿐 2024. 8. 20. 02:13

📕 목차

1. 비대칭 키 암호화
2. RSA
3. ECC: Elliptic Curve Cryptosystem

1. 비대칭 키 암호화

📌 비대칭 키 암호화란

개인 키와 공개 키 두 키를 한 쌍으로 암호키를 구성하는 방법
- 개인 키(private key): 개인이 보관
- 공개 키(public key): 타인에게 공개 (여러 사람이 볼 수 있음)
응용 분야
- 비밀 메시지: A의 공개 키로 암호화한 메시지는 A의 개인 키로만 풀 수 있음. (ex. HTTPS 통신)
- 전자 서명: A의 공개 키로 복호화가 되면, A의 개인 키로 암호화한 것이라는 증거 (ex. JWT signature)

📌 대칭 키 vs 비대칭 키

	대칭 키 암호화	비대칭 키 암호화
개념적 차이	비밀을 두 사람이 서로 공유	비밀을 공유하지 않고, 각자 비밀로 보존
키 구성 차이	비밀 키를 두 사람이 공유	개인 키 + 공유 키
구성원 수가 N	비밀 키의 수 = N(N-1)/2	개인 키 N개 + 공유 키 N개
암호 방식 차이	기호(문자나 비트)를 대체하거나 치환하는 데 기반	숫자를 다른 숫자로 변경
평문과 암호문 형식	기호의 조합으로 간주	정수로 표현
암호화/복호화 방식	\(C = E_{K}(P)\), \(P = D_{K}(C)\)	\(C = f(K_{public}, P)\), \(P = g(K_{private}, C)\)
활용 분야	(길이가 긴) 메시지 암호화	짧은 데이터(ex. 비밀 키) 암호화, 전자 서명, 인증
알고리즘 실행시간	빠름	느림

📌 Trapdoor One-Way Function

단 방향(one-way) 함수
- x가 주어질 때, f(x)는 계산이 쉽다.
- y가 주어질 때, \(f^{-1}(y)\)로 x를 계산하는 것은 어렵다.
- 예를 들어, n이 매우 큰 수이고, x와 k를 알 경우, \(y = x^{k} \, mod \, n\)은 계산이 쉽다. 하지만 y, k, n을 이용하여 x를 파악하는 건 매우 어렵다. (\( \sqrt[k]{y} % n \)는 실수, 하지만 암호학에선 정수로 표현해야 하므로 경우의 수가 매우 많아진다.)
Trapdoor 단 방향 함수
- Trapdoor(비밀)가 주어지면 \(f^{-1}(y)\)로 x를 쉽게 구할 수 있게 한다.
- 예를 들어, \(k \times k' = 1 \, mod \, \varphi(n)\)이 되는 트랩도어 k'를 알고 있다면, \(x = y^{k'} \, mod \, n\)을 이용하여 x를 구할 수 있다. (k: 공개키, k': 개인키)

그새 이전 내용을 까먹어서 복기했는데, k와 k'이 위와 같은 관계를 갖는다는 것은 두 값이 모듈러 곱셈의 역원 관계임을 의미한다.

따라서 이전에는 계산이 사실상 불가능했던 x값을 비밀키(k')로 빠르게 역연산을 수행하여 구할 수 있다.

📌 φ(n) : Euler의 φ 함수

💡 RSA 알고리즘의 베이스가 되는 개념 (피어라고 읽더라..)

def: n보다 작으면서 n과 서로소인 정수의 개수 (\(Z_{n}^{*}\)에 속하는 원소의 개수; %n을 했을 때, 역수가 존재하는 정수 집합)
φ(n)을 구하는 방법
- φ(1) = 0
  - 1보다 작으면서, 1과 서로소인 정수이므로 0으로 잡는다.
- p가 소수일 경우: φ(p) = p - 1
  - φ(5) = {1,2,3,4} = 4
  - φ(13) = 12
- m과 n이 서로소 관계일 경우: φ(m*m) = φ(m) * φ(n)
  - φ(10) = φ(2*5) = φ(2) * φ(5) = 1 * 4 = 4
- p가 소수일 경우: φ(\(p^{e}\)) = \(p^{e} - p^{e-1}\)
  - φ(240) = φ(\(2^{4}\) * 3 * 5) = (\(2^{4}\) - \(2^{3}\))*2*4 = 64 (\(\because Z_{8}^{*} = \varphi (2^{3}) = 2^{3} - 2^{2} = 4\))
  - 소인수분해가 가장 오래 걸리기 때문에 지배 시간 복잡도가 된다.
φ(n)에 관한 오일러 정리
- a와 n이 서로소일 경우, \(a^{\varphi (n)} \, \equiv \, 1\) (mod n)
  - a = 3, n = 10이라 가정하면, φ(10) = 4가 된다.
  - \( a^{\varphi (n)} \, mod \, n\) = \(3^{4} % 10\) = 1 (언제나 참)
- 또 다른 형태의 정리: a < n, k가 정수이면, \(a^{k \, \times \, \varphi (n)+1} \, \equiv \, a\) (mod n)
  - a, n이 서로소: \( a(a^{ \varphi (n)} \, mod \, n)^{k} \, mod \, n \, = a \cdot 1^{k} \, mod \, n \, = \, a \)
  - a, n이 서로소가 아니면:
    n = p * q (p, q는 소수)
    a = p * i (a와 q는 서로소)

✒️ 증명: a < n, k가 정수이면, \(a^{k \, \times \, \varphi (n)+1} \, \equiv \, a\) (mod n)

a와 n이 서로소면, \(a^{\varphi (n)} \equiv 1 \, (mod \, n)\)이므로, \(a^{k \times \varphi (n) + 1} \equiv 1^{k} * a\) (mod n)

이건 위에서 증명했으므로, 패스

a와 n이 서로소가 아니고, n = p * q이며, a = i * p라고 가정 (a와 q는 서로소)

\begin{align} a^{\varphi (n)} \, mod \, q &= a^{\varphi (p) * \varphi (q)} \, mod \, q\\ &= (a^{\varphi (q)} \, mod \, q)^{\varphi (p)} \, mod \, q = 1\\ a^{k \cdot \varphi (n)} \, mod \, q &= 1^{k} \, mod \, q = 1\\ a^{k \times \varphi (n)} &= 1 + j * q \, (단, j는 \, 임의의 \, 정수)\\ a^{k \times \varphi (n) + 1} &= a * (1+j*q)\\ &= a + a * j * q \\ &= a + i*j*p*q \, (\because 정의에 \, 의해 \, a = i*p) \\ &= a+ i*j*n \, (\because 정의에 \, 의해 \, p \cdot q = n)\\ a^{k \times \varphi (n) + 1} \, mod \, n &= (a+ i*j*n) \, mod \, n\\ &= a\end{align}

도중에 \( a^{k \times \varphi (n)} = 1 + j * q \)가 되는 이유가 헷갈렸는데, 모듈러 연산을 이해하면 별로 어렵지 않다.

\( a^{k \times \varphi (n)} \, mod q = 1\)이라는 것은 \( a^{k \times \varphi (n)} \)을 q로 나눈 나머지가 1이라는 의미다.

모듈러 연산에서, 어떤 수를 q로 나눈 나머지가 1이라면, 그 수를 (1 + q의 배수)로 표현할 수 있다.

즉, \( a^{k \times \varphi (n)} \)은 1에 q의 어떤 배수를 더한 형태해야 하므로, j는 임의의 정수를 의미한다.

2. RSA 암호 시스템

📌 RSA 암호 시스템이란

Revest, Shamir, Adleman의 이름을 딴 공개 키 알고리즘으로 가장 널리 사용된다.
기본 개념
- 공개 키 = (e, n) → \(C = P^{e} \, mod \, n\) (n은 2,048 bit)
- 개인 키 = d → \(P = C^{d} \, mod \, n\)

공격자는 \(\sqrt[e]{C} \, mod \, n\)을 계산해야 하는데, 현재까지 알려진 polynomial time 알고리즘이 존재하지 않는다.

쉽게 말해서, 계산이 너무 오래 걸려서 사실상 해독 불가능하다.

📌 키 생성 알고리즘

RSA Key Generation 함수는 다음과 같이 동작해야 한다.

p ≠ q인 두 개의 큰 소수 p와 q를 선택한다. (p와 q는 각각 512bit 이상이어야 하며, 보통 1,024 bit)
n = p * q (n은 1,024 bit - 309 자리 - 이상)
φ(n) = (p - 1) * (q - 1)
1 < e < φ(n)이면서, φ(n)과 서로소인 e를 선택한다.
d = \(e^{-1}\) mod φ(n) (d는 modulo φ(n)으로 e의 역원 → e*d mod φ(n) == 1)
public_key = (e, n) (비밀키 d를 만들 때 사용한 e, n을 공개키로 사용)
private_key = d
return public_key and private_key

원리 자체는 단순하기 그지 없는데, 아주 큰 수(p, q 두 수의 곱)를 알아내기 힘들게 만드는 것이다.

공격자가 n으로 d를 구하려면, n을 소인수 분해해야 하는데 경우의 수가 너무 많아서 불가능하다.

반면에 비밀키 d만 알고 있다면, 아주 빠르게 복호화할 수 있다.

🤔 n, e를 다 줬는데, 왜 d를 못 구해?

d = \(e^{-1}\) mod n 이었다면 당연히 구했겠지만, d = \(e^{-1}\) mod φ(n)이기 때문에 얘기가 달라진다.
φ(n)은 (p-1)(q-1)로 계산되는데, 문제는 p와 q의 조합을 무슨 수로 찾아낼 것이냐는 거다.

단순히 많다고만 하면 당연히 감이 안 올테니, 직접 경우의 수를 계산해보자.

RSA에서 권장되는 키 크기가 최소 2,048 bit 이상이어야 하므로, n은 2,048 bit 이상이어야 한다.
n = p*q이므로, p와 q는 각각 대략 1,024 bit의 소수여야 한다.
소수 정리에 따르면, x보다 작은 소수의 개수는 대략 x / ln(x)이므로, 2^1024 근처 소수 개수는 약 2^1014개.
대략 (2^1014)^2 = 2^2028 ≈ 10^611개 조합이 가능하다.

현재 관측 가능한 우주의 원자 수가 대략 10^81개라고 하는데, 이는 우주의 원자 수보다도 압도적으로 많은 말도 안 되는 경우의 수를 보인다.

📌 RSA 정확성 증명

💡 평문 P의 길이는 n보다 작아야 한다!

오일러 정리의 두 번째 규칙에 의해 (if n = p * q, a < n, k가 정수라면)
- \(a^{k \times \varphi (n) + 1} \equiv a \) (mod n)
수신자가 받은 평문이 \(P_{1}\)이고, 송신자가 보낸 평문 P와 동일함을 증명
- \(P_{1} = C^{d} \, mod \, n = (P^{e} \, mod \, n)^{d} \, mod \, n = P^{ed} \, mod \, n\)
- ed = k * φ(n) + 1 (d와 e는 modulo φ(n)으로 역원)
- \(P_{1} = P^{ed} \, mod \, n\) → \(P_{1} = P^{k \varphi (n) + 1}\) mod n = P mod n

P가 n보다 작아야 하는 이유는 n으로 모듈로 연산해야 하는데, P가 n보다 크면 정보 손실이 발생할 수 있기 때문이다.

P < n일 때만 암호화 함수가 일대일 대응을 보장하는데, 이는 즉 각 평문에 대해 유일한 암호문이 생성되고, 각 암호문이 유일한 평문으로 복호화 될 수 있는 조건이다.

📌 RSA 예시(1)

1️⃣ A가 p, q를 7, 11로 선택해서 n = 77을 계산

φ(n) = (7 - 1)(11 - 1) = 60
\(Z_{60}^{*}\) 안에서 두 개의 지수 e와 d를 선정: e = 13 → d = 37
- 13 * 37 mod 60 = 1
공개키 = (77, 13), 개인키 = 37

2️⃣ B가 평문 5를 A에게 송신

P = 5 → C = \(P^{e}\) mod n = \(5^{13}\) mod 77 = 26

3️⃣ B는 암호문 26을 수신한 후, 개인키 37로 복호화

C = 26 → P = \(C^{d}\) mod n = \(26^{37}\) mod 77 = 5

4️⃣ C가 63을 A에게 보낼 경우

P = 63 → C = \(63^{13}\) mod 77 = 28 → P = \(28^{37}\) mod 77 = 63

5️⃣ D가 p = 397, q = 401을 사용하여 n = 159,197을 계산

φ(n) = 396 * 400 = 158,400 → e = 343, d = 12,007 선택

6️⃣ E가 D에게 "NO"라는 메시지를 보낼 경우

각 문자를 두 자리 숫자로 된 코드로 변경 (N=13, O=15)
두 개 코드를 이어 붙여 4자리 숫자 1314(평문) 생성
암호화와 복호화 진행

📌 e의 역원 d를 구하기 위해 Extended Euclidian 알고리즘 사용

Euclid 알고리즘은 익히 들어봐서 알겠지만, gcd 구하는 알고리즘이다.

gcd(a, 0) = 1
gcd(a, b) = gcd(b, a%b)
ex. gcd(10, 6) = gcd(6, 4) = gcd(4, 2) = gcd(2, 0) = 2

🔐 암호화

RSA_Encryption(P, e, n) { // P는 Z_n에서 평문이고 P < n, e는 아주 큰 수
    C = FastExponentiation(P, e, n) // P^e mod n 계산
    return C
}

🔓 복호화

RSA_Decryption(C, d, n) { // C는 Z_n에서 암호문
    P = FastExponentiation(C, d, n) // C^d mod n 계산
    return P
}

📌 Fast Exponentiation

💡 \(P^{e}\)와 \(C^{d}\) 지수 연산을 빠르게 계산

y = \(a^{x}\) mod n을 단순 계산하면, x가 아주 큰 수(ex. 512 bit)일 때 아주 오랜 시간 소요
Square-and-Multiply: y = \(a^{9}\) = \(a^{1001_{2}}\) = \(a^{8}\) * 1 * 1 * a

📌 RSA 공격: 소인수 분해 공격

매우 큰 n으로부터 p와 q를 찾는 것은 infeasible
- n = p*q → φ(n) = (p-1) * (q-1) → e * d mod φ(n) = 1
RSA가 안전해지기 위한 권장 사항
- n은 1,024 bit 이상 (4,096 bit 까지도 권고)
- 두 개의 소수 p와 q는 적어도 512 bit 이상
- p와 q는 너무 가까이 있는 수가 되지 않도록 설정
- p-1과 q-1은 적어도 하나의 큰 소인수를 가져야 한다.
- n값을 공동으로 사용해서는 안 된다.
- e 값은 \(2^{16}\)+1 (=65,537)이거나, 이 값에 가까운 정수를 사용해야 한다. (e를 먼저 정하고, e와 φ(n)이 서로소가 되도록 p, q를 선택하면 편하다.)

이래서 jwt secret key의 최소 길이를 지정해뒀었구나..

이거 처음 배우고 그 이유를 알게 돼서 즐거웠었던 기억이 난다 ㅎㅎ

3. ECC: Elliptic Curve Cryptosystem

📌 As-is

RSA의 문제점이라 한다면, 보안을 위해 key가 매우 커져야 한다는 단점이 있다. (기본적으로 n이 2,048 bit)

key가 커지면 그만큼 소요되는 연산 속도도 길어지는데, 블록 체인을 RSA 알고리즘으로 암호화한다고 생각해보자.

블록체인은 Singled Linked List 구조로 공개키를 코인에 저장하고, 내 코인임을 증명하려면 비밀키로 증명한다.

이를 작업 증명(Proof of Work)라고 하는데, 이 계산 속도가 비트 코인 트랜잭션 속도에 영향을 준다.

지금 안 그래도 트랜잭션 속도가 2회/10분 밖에 안 되는 느려터진 속도를 갖는데, 암호화/복호화까지 느려터지면 어떻게 사용이 가능하겠나.

빠른 서명 생성과 검증은 노드들이 새로운 트랜잭션과 블록을 더 빨리 처리하고 전파할 수 있도록 해주므로, key size를 줄이는 것이 관건이다.

📌 타원 곡선 암호 시스템

보다 짧은 키의 길이(256bit ~)로 RSA과 비슷하거나 깨기 힘든 보안 수준을 갖는다.
일반적인 타원 곡선 방정식: 2개의 변수를 갖는 3차 방정식
- \(y^{2} + b_{1}xy + b_{2}y = x^{3} + a_{1}x^{2} + a_{2}x + a_{3}\)
실수 상의 타원 곡선 (위 식에서 허수 제거)
- \(y^{2} = x^{3} + ax + b\)
- 모든 근이 실근인 경우, 좌표와 수평선과 곡선이 3지점에서 교차 (이걸로 n, e, d를 결정한다.)
- 하지만 실수 체계를 사용할 수 없으므로, 모듈로 연산해서 정수 체계로 변환이 필요하다. (mod 연산)

📌 타원 곡선 상의 덧셈 연산

이건 뒤에서 타원 곡선 상 덧셈 연산이 필요해서 나오는 개념.

타원 곡성 상의 두 점 P = (\(x_{1}, y_{1}\), Q = \(x_{2}, y_{2}\))에 대해 R = P + Q를 정의

P와 Q를 연결하여 직선 그리기
직선과 교차하는 곡선 상의 점(-R)에 대해 x 축으로 대칭점 탐색
- P와 Q가 동일할 경우에는 P를 지나는 접선을 이용
a의 경우, P와 Q를 지나는 직선 방정식: 기울기 = λ, R = (\(x_{3}\), \(y_{3}\))
- 기울기 λ = \(\frac{y_{2}-y_{1}}{x_{2}-x_{1}}\)
- R의 좌표 \(x_{3} = \lambda^{2} - x_{1} - x_{2}\), \(y_{3} = \lambda(x_{1} - x_{3}) - y_{1}\)
b의 경우, \(\lambda = \frac{(3x_{1}^{2} + a)}{2y_{1}}\), \(x_{3}\)와 \(y_{3}\)는 위의 식과 동일

📌 GF(p) 상의 타원 곡선

GF(p): Modulo p를 이용한 타원 곡선 (p는 소수)
- x의 값: 0부터 p-1 범위에 존재 (역수가 존재하는 범위)
- 덧셈 연산: 덧셈 결과를 mod p
역원 구하기
- (x, y)의 역원 → (x, -y) (단, -y는 y의 덧셈에 대한 역원)
- ex. p=13이면, (4, 2)의 역원 → (4, -2) → (4, 11)
타원 곡선 식 \(y^{2} = (x^{3} + ax + b) \, mod \, p\) 곡선(\(E_{p}(a,b)\)) 상의 점 찾기

ellipticCurvePoints (p, a, b) { // \(E_{p}\)(a,b) 곡선의 점 찾기
x = 0
while (x < p) {
w = (x^3 + ax + b) mod p // w is y^2
if (w is a perfect square in Z_p)
output (x, \(\sqrt{w}\)) (x, -\(\sqrt{w}\))
x = x + 1
}
}

🟡 타원 곡선 \(E_{13}\)(1,1)의 예

\(y^{2} = (x^{3} + x + 1) \, mod \, 13\) 위에 정의된 점들

위 수식으로 계산을 쭉~ 해보면 P, -P 리스트를 구할 수 있다.

🟡 타원 곡선 \(E_{13}\)(1,1)의 덧셈 예

P = (4, 2), Q = (10, 6)일 때, R = P + Q를 구하는 방법은 다음과 같다.

λ = \(\frac{y_{2}-y_{1}}{x_{2}-x_{1}}\) = (6 - 2) * \((10 - 4)^{-1}\) mod 13 = 4 * 11 mod 13 = 5 mod 13
- Extended Euclidian 알고리즘을 이용해 \(6^{-1}\) mod 13을 계산
x = \(\lambda^{2} - x_{1} - x_{2}\) = (\(5^{2}\) - 4 - 10) mod 13 = 11 mod 13
y = \(\lambda(x_{1} - x_{3}) - y_{1}\) = (5(4-11) - 2) mod 13 = 2 mod 13
R = (11, 2)
- R이 바로 \(E_{13}\)(1,1)의 곡선 상의 점에 해당한다.

📌 타원 곡선을 이용한 ElGamal 암호 시스템

타원 곡선 암호 시스템도 RSA와 비슷한 보안 방식인데, 경우의 수가 너무 많아서 구할 수 없게 만든다.

아니, 근데 대체 이런 건 어떻게 생각해내는 거지? 진짜 천재다.

이게 왜 어렵냐면, 우선 곡선 상의 \(e_{1} = (x_{1}, y_{1})\) 좌표는 generator로써, 모두가 알고 있는 공개값으로 걸어 둔다.

그리고 \(e_{2} = (x_{2}, y_{2})\)는 d * \(e_{1}\) 연산으로 생성한 공개키로써, 타원 곡선상의 스칼라 곱셈을 의미한다.

여기서 사용한 d를 개인키로써 가지게 된다.

이제 평문 P를 좌표로써 환산한 후에 좌표 \(C_{1}\), \(C_{2}\)를 구한다. (암호문으로 취급, r은 임의의 매우 큰 수)

\(C_{1} = r \, \times \, e_{1}\)
\(C_{2} = P + r \, \times \, e_{2}\)

공개키 \(e_{1}\), \(e_{2}\), \(E_{p}\)는 서버측으로부터 전달받은 것을 사용한다.

서버는 이를 다시 복호화하기 위해서, 다음과 같이 풀이해야 한다.

\begin{align} C_{2} &= P + r * e_{2}\\ P &= C_{2} - r * e_{2}\\ &= C_{2} - r(d*e_{1})\\ &= C_{2} - d \cdot C_{1} \end{align}

아니, 그런데 뭔가 좀 이상하지 않나? e1과 e2를 아는데, 고작 정수값인 d를 구하는 게 뭐가 그렇게 힘들단 거지?

라고 생각한다면 과거의 나처럼 위 수식을 제대로 음미하지 못 한 상태일 확률이 크다..

타원 곡선 상에서 \(e_{2} = d \times e_{1}\)은 단순 곱셈이 아니라, e1을 d번 자기 자신과 더하는 연산을 의미한다.

즉, 2*e1은 e1을 두배로 늘리는 게 아니고, 복잡한 기하학적 연산을 통해서 수행해야 하는데, 가장 빠른 알고리즘을 사용해도 O(\(\sqrt{n}\)) 시간이 걸린다. (문제는 n이 타원 곡선의 점의 개수인데, 2^256이라서 경우의 수가 너무 많음.)

그러나 ElGamel 암호 시스템이 어려운 점은 다름아닌 평문을 타원 곡선의 한 점 P로 어떻게 1:1 매핑할 건지...진짜 어케함.

📌 Bitcoin에서 사용하는 타원 곡선: Secp256k1

Bitcoin에서는 전자 서명을 위해서 타원 곡선을 이용한다.
Secp256k1 타원 곡선 식은 \(y^{2} = (x^{3} + 7)\) mod p
- p = a very large prime number = \(2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1\)
  = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
K = k * G
- k: 개인 키 (256 bit)
- G: 타원 곡선 상의 고정된 점 (공개키)
  (79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798, 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8) → ,를 기준으로 앞이 X축, 뒤가 Y축
- 공개키로부터 개인키를 유추하려면 적어도 k번의 덧셈이 필요한데 불가능함.
- 반대로 공개키를 만들기 위해서도 G를 k번 더해야 하지 않을까??? 가장 큰 수가 \(2^{255} - 1\)인데 언제 더하냐. → Double-and-Add 알고리즘을 사용하면 된다!

📌 Double-and-Add 알고리즘

k * G를 계산하는 방법은 2가지가 있다.

첫 번째는 G를 k번 더하는 미친 짓이고, 다른 하나는 G를 256번의 더하기 연산으로 구하는 방법이다.

이게 뭔소리여.

그러나 실제 알고리즘은 단순하기 그지 없는데, 우선 left-to-right로 k의 bit를 조사한다.

1: Double(2배 연산)을 적용한 후 Add(G를 더함)
0: Double만 적용

이제 1, 0의 규칙대로 계산만 해주면 된다....😀

예시라도 하나 보고 가세유..

만약, 26 * G = K을 구하고 싶다고 가정하자.

\(26_{10} = 11010_{2}\)를 left-to-right로 bit를 스캔하면서 다음과 같이 처리하면 된다.

bit1(1): G 초기화
bit2(1): G + G = 2G(Double) → 2G + G = 3G(Add)
bit3(0): 3G + 3G = 6G(Double)
bit4(1): 6G + 6G = 12G(Double) → 12G + G = 13G(Add)
bit5(0): 13G + 13G = 26G(Double)

저작자표시 비영리