ECC 알고리즘

ECC(Elliptic Curve Cryptography) 알고리즘은 공개키 암호화 알고리즘 중 하나로, 타원 곡선을 이용하여 암호화 및 서명을 수행합니다. ECC 알고리즘은 RSA 알고리즘과 비교하여 더 작은 키 크기를 사용하면서도 같은 보안 수준을 유지할 수 있어, 네트워크 환경에서 전송할 데이터의 크기를 줄일 수 있습니다. 또한, ECC 알고리즘은 안정적인 속도와 안전한 보안성을 제공하여 다양한 응용 분야에서 사용됩니다. ECC 알고리즘은 모바일 기기, 스마트카드, 블록체인 등에서 보안성을 확보하기 위해 널리 사용되고 있습니다.

 

(아래는 이해를 돕기 위한 간단한 예시로 작은 숫자를 활용해보았습니다)

 

공개키/개인키 생성과정

1. 타원 곡선 생성

ECC 알고리즘은 타원 곡선 상에서 연산을 수행합니다. 따라서 먼저 타원 곡선을 생성해야 합니다. 일반적으로 사용되는 ECC 알고리즘의 타원 곡선은 다음과 같은 수식으로 정의됩니다.

y^2 = x^3 + ax + b (mod p)

여기서 a, b는 곡선의 계수로, x, y는 곡선 위의 좌표이며, 이 수식을 만족하는 x, y 값들의 집합이 타원 곡선을 이룹니다.

곡선 : y^2 = x^3 + 2x + 2 (mod 17)

2. 기준점 생성

ECC 알고리즘에서는 타원 곡선 상의 한 점을 기준점으로 지정합니다. 이 점을 기준점(generator point) 또는 원점(generator)이라고 부릅니다. 기준점은 타원 곡선 상의 임의의 점을 선택하여 계속해서 더하는 연산을 수행하여 찾을 수 있습니다.

기준점 : G = (5,1)

3. 개인키, 공개키 생성

ECC 알고리즘에서는 개인키(private key)와 공개키(public key)를 생성합니다. 개인키는 암호화와 복호화에 사용되는 비밀 키이며, 공개키는 암호화된 메시지를 복호화하기 위해 사용되는 공개 키입니다.

개인키는 무작위로 선택된 한 점 P와 기준점 G 사이의 거리 k로 정의됩니다. 즉, 개인키 d는 다음과 같이 표현됩니다.

d = k * G

공개키는 개인키를 이용하여 생성됩니다. 공개키 Q는 개인키 d와 기준점 G 사이의 거리 k를 이용하여 다음과 같이 계산됩니다.

Q = d * G

Alice : d_A = a = 7, Bob : d_B = b = 11,
Alice : Q_A = d_A * G = 7G = (9, 16),Bob : Q_B = d_B * G = 11G = (7, 2)

암호화 과정

1. 무작위 점 선택

암호화를 위해 ECC 알고리즘에서는 먼저 메시지를 타원 곡선 상의 무작위한 한 점 R로 변환합니다. 이때 R은 타원 곡선 상의 임의의 점으로 선택됩니다.

Alice는 무작위 점 R을 선택합니다. R = (10, 15)

2. 공개키 이용하여 점 P 계산

다음으로 공개키 Q를 이용하여 타원 곡선 상의 점 P를 계산합니다. P는 다음과 같이 정의됩니다.

P = r * Q

여기서 r는 메시지를 암호화할 때 사용되는 임의의 숫자입니다.

Alice는 Bob의 공개키를 이용하여 점 P를 계산합니다. P = d_A * Q_B = 7Q_B = 7(7, 2) = (9, 16)

3. R과 P를 이용하여 암호문 생성

마지막으로 암호문 C를 생성합니다. C는 R과 P를 합한 값입니다.

C = R + P

이렇게 생성된 C가 암호문이 됩니다.

암호문 C는 R과 P를 합한 값입니다. C = R + P = (10, 15) + (9, 16) = (3, 16)
따라서 LGU+의 암호문은 (3, 16)이 됩니다.

복호화 과정

1. 개인키 이용하여 P 계산

먼저 개인키 d를 이용하여 P를 계산합니다. P는 다음과 같이 정의됩니다.

P = d * R

여기서 R은 암호문 C에서 추출한 무작위 점입니다.

다음으로 P와 공개키 Q를 이용하여 R을 계산합니다. R은 다음과 같이 정의됩니다.

R = P - r * Q

여기서 r는 암호문 C에서 추출한 임의의 숫자입니다.

마지막으로 R을 메시지로 변환합니다. R은 타원 곡선 상의 한 점이므로, 이를 메시지로 변환하기 위해서는 R의 x 좌표를 이용합니다. 이렇게 변환된 메시지가 복호화된 메시지가 됩니다.

Bob은 R과 P를 이용하여 평문을 복원합니다. M = C - d_B * R = (3, 16) - 11(10, 15) = (7, 3)
따라서 다시 LGU+으로 복호화 됩니다.