V2X-Crypto

Posted Oct 20, 2026 Updated Nov 4, 2026

By junsu

56 min read

V2X-Crypto

ECC(Elliptic Curve Cryptography)

타원 곡선의 수학적 성질을 이용한 공개키 암호화 방식
RSA 같은 다른 공개키 방식보다 짧은 키 길이로 같은 수준의 보안을 제공
짧은 키로 빠른 연산과 적은 대역폭으로 무선 통신에 적합
- V2X 메시지(BSM 등)는 초당 10회 수준으로 브로드캐스트되므로 서명·인증서 크기가 작을수록 유리

보안 강도(bit)	ECC 키 길이	RSA 키 길이
80	160	1024
112	224	2048
128	256	3072
192	384	7680
256	521	15360

활용

디지털 서명 → ECDSA
대칭키의 안전한 공유 → ECDH
암호화된 통신 → ECIES

Finite Field(유한체) : 유한한 개수의 원소들로 구성된 체

체(Field) : 덧셈, 뺄셈, 곱셈, 0이 아닌 수로의 나눗셈이 모두 정의되고 그 결과가 다시 집합 안에 있는 대수 구조
Fp
- p: 홀수 소수
  - 홀수 소수여야 하는 이유
    - 소수여야 하는 이유 : p가 소수일 때만 0이 아닌 모든 원소가 곱셈의 역원을 가짐 → 나눗셈(역원 곱)이 항상 가능해야 체가 됨
      - 곱셈의 역원 : 곱해서 1이 되는 수 (예: 3의 역원은 1/3)
        유한체에는 분수가 없으므로 곱해서 1 (mod p)이 되는 정수를 역원으로 사용
        예) mod 7 에서 3 × 5 = 15 ≡ 1 → 3의 역원은 5 → “÷ 3” 대신 “× 5”로 계산
      - 예) mod 6 에서는 2 × 3 = 0 처럼 0이 아닌 수끼리 곱해서 0이 되는 경우가 생김
        3에 2를 곱하면 0이 되어버려, 다시 원래 값 3으로 되돌릴 방법이 없음
        실제로 2 × x ≡ 1 (mod 6)을 만족하는 x가 없음 → 2의 역원이 존재하지 않음
      - 되돌릴 수 있어야(역원이 있어야) 하는 이유
        나눗셈은 곱셈을 되돌리는 연산이고, 유한체에서는 나눗셈을 역원 곱으로만 할 수 있음
        점 덧셈 공식의 / (x2 - x1), ECDSA의 k^(-1), s^(-1) 처럼 ECC 공식 곳곳에 나눗셈이 들어 있음
        나눌 수 없는 값이 하나라도 있으면 특정 점끼리 더할 수 없거나 서명을 검증할 수 없는 경우가 생김
        따라서 0이 아닌 어떤 값이 나와도 항상 나눌 수 있도록 p를 소수로 정함
    - 홀수여야 하는 이유 : p = 2(표수 2)인 경우 y^2 = x^3 + ax + b 형태(단순 바이어슈트라스 형태)로 곡선을 정의할 수 없음
      - 표수 2인 체는 2로 나눌 수 없기 때문에 별도의 곡선 식이 필요하며, 이는 이진체 F(2^m) 곡선(B-163, K-163 등)으로 따로 정의됨
- 범위 : {0, 1, … , p - 1}
- 표준 허용 p의 크기 : 192, 224, 256, 384, 521*
  - * 512가 아닌 521인 이유 : 2^521 - 1 이 메르센 소수로, mod 연산을 빠르게 수행할 수 있기 때문
  - NIST P-192, P-224, P-256, P-384, P-521 곡선에 대응
- NIST P-256의 타원 곡선이 Fp 위에서 정의
연산 : mod p(나머지 연산)
- 모든 사칙연산 결과가 유한체 안의 원소로 떨어지도록 mod p를 통해 정의
  - 유한체 안의 원소로 떨어져야 하는 이유
    - 닫힘성 : 점 덧셈의 결과가 다시 같은 곡선 위의 점이 되어야 군(Group) 구조가 성립함
    - 고정 크기 : 모든 값이 p보다 작으므로 고정된 비트 길이(예: 256bit)로 표현·전송 가능
    - 정확성 : 실수 연산과 달리 소수점·반올림 오차가 없음
    - 안전성 : 실수 곡선은 연속적이라 근사로 역산을 추적할 수 있지만, 유한체 위의 점들은 불규칙하게 흩어져 있어 역산이 어려움
- 나눗셈 : a / b = a × b^(-1) mod p (b^(-1)은 확장 유클리드 알고리즘 또는 페르마 소정리 b^(p-2) mod p 로 계산)

타원 곡선 함수 정의

조건 : 유한체 𝔽p 에서 4a^3 + 27b^2 ≢ 0 (mod p) (단, a, b ∈ 𝔽p)
- 판별식이 0이 아니어야 곡선에 뾰족점(cusp)이나 교차점(node)이 없는 매끄러운 곡선이 되어 모든 점에서 접선이 하나로 정의됨
수식 : y^2 = x^3 + ax + b (mod p)
곡선 위의 점들의 집합 E(Fp) = {(x, y) y^2 = x^3 + ax + b (mod p)} ∪ {O}
- O : 무한원점(Point at Infinity), 덧셈의 항등원 (P + O = P)
- 점 P = (x, y)의 역원 : -P = (x, -y mod p)

아래 그림은 이해를 돕기 위해 실수 위의 곡선 y² = x³ − x + 1 로 그린 것
실제 ECC는 mod p 위에서 계산하므로 점들이 흩어진 형태가 되지만, 계산 공식은 똑같이 사용됨

타원 곡선의 점 덧셈

X 좌표가 서로 다른 두 점의 덧셈
기하학적 의미 : 두 점 P, Q를 지나는 직선이 곡선과 만나는 세 번째 점을 x축에 대해 대칭시킨 점이 P + Q

그림으로 보는 순서
1. 두 점 P, Q를 잇는 직선(주황색)을 그림
2. 3차 곡선과 직선은 항상 세 점에서 만나므로, 직선이 곡선과 만나는 세 번째 점 −(P+Q)를 찾음
3. 그 점을 x축에 대해 뒤집으면(y 부호 반전) P + Q
왜 뒤집는가?
- 한 직선 위의 세 점을 더하면 O(항등원)이 되도록 정의함 : P + Q + R = O
- 따라서 P + Q = −R 이고, −R 은 R을 x축에 대해 뒤집은 점
공식과 그림의 대응
- λ : 직선의 기울기
- x3 : 직선과 곡선의 세 번째 교점의 x 좌표
- y3 : 교점의 y 좌표에 마이너스를 붙인 값 (x축 대칭)
조건 : P = (x1, y1), Q = (x2, y2), x1 ≠ x2
수식 :

λ  = (y2 - y1) / (x2 - x1)  mod p
x3 = λ^2 - x1 - x2          mod p
y3 = λ(x1 - x3) - y1        mod p

P + Q = (x3, y3)

예외 : x1 = x2 이고 y1 = -y2 이면 (P와 -P) 직선이 수직이므로 P + Q = O

타원 곡선 점 두배

한 점을 자기 자신과 더하는 연산
기하학적 의미 : 점 P에서의 접선이 곡선과 만나는 다른 한 점을 x축에 대해 대칭시킨 점이 2P

그림으로 보는 순서
1. P와 P를 이을 수는 없으므로, 대신 P에서 곡선에 닿는 접선(주황색)을 그림
2. 접선이 곡선과 다시 만나는 점 −2P를 찾음
3. 그 점을 x축에 대해 뒤집으면 2P
왜 접선인가?
- 점 Q를 P에 점점 가까이 가져가면, P와 Q를 잇는 직선은 결국 P에서의 접선이 됨
- 그래서 점 덧셈 공식의 기울기 (y2 − y1)/(x2 − x1) 대신 접선의 기울기(미분값)를 사용
  - y² = x³ + ax + b 를 미분하면 2y·y’ = 3x² + a → y’ = (3x² + a) / (2y)
예) 그림의 P = (1, 1) (a = −1)
- λ = (3·1² − 1) / (2·1) = 1
- x3 = 1² − 2·1 = −1
- y3 = 1·(1 − (−1)) − 1 = 1
- 2P = (−1, 1)
조건 : P = (x1, y1), y1 ≠ 0
수식 :

λ  = (3x1^2 + a) / (2y1)  mod p
x3 = λ^2 - 2x1            mod p
y3 = λ(x1 - x3) - y1      mod p

2P = (x3, y3)

예외 : y1 = 0 이면 접선이 수직이므로 2P = O

mod p 에서 직접 계산해보기

곡선 : y² = x³ + 2x + 2 (mod 17), 점 P = (5, 1)
2P 계산
- λ = (3·5² + 2) / (2·1) = 77 / 2 (mod 17)
  - 77 mod 17 = 9
  - 2의 역원 : 2 × 9 = 18 ≡ 1 (mod 17) → 2^(-1) = 9
  - λ = 9 × 9 = 81 ≡ 13 (mod 17)
- x3 = 13² − 2·5 = 159 ≡ 6 (mod 17)
- y3 = 13·(5 − 6) − 1 = −14 ≡ 3 (mod 17)
- 2P = (6, 3)
확인 : 3² = 9, 6³ + 2·6 + 2 = 230 ≡ 9 (mod 17) → 곡선 위의 점이 맞음
이처럼 공식 속 나눗셈은 역원 곱으로 계산되며, 결과는 항상 0 ~ 16 사이의 정수 좌표로 떨어짐

스칼라 곱

kP = P + P + … + P (k번)
실제로는 점 덧셈과 점 두배를 조합한 Double-and-Add 방식으로 계산
- k의 비트를 위에서부터 읽으며 매 비트마다 두배, 비트가 1이면 덧셈
- k가 256bit여도 약 256번의 두배 + 최대 256번의 덧셈으로 계산 가능 → O(log k)

NIST P-256 곡선 파라미터

별칭 : secp256r1, prime256v1
IEEE 1609.2에서 서명(ECDSA) 및 암호화(ECIES)에 사용되는 기본 곡선 (brainpoolP256r1, P-384 등도 지원)
이름의 의미 : P = Prime(소수체 Fp 위의 곡선), 256 = p의 비트 수

곡선 수식

앞에서 본 일반식 y² = x³ + ax + b (mod p) 에 a = −3 을 넣은 형태

y² = x³ − 3x + b   (mod p)

p = 2^256 − 2^224 + 2^192 + 2^96 − 1
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B

즉, 일반식의 a, b, p 자리에 정해진 상수를 넣은 것 뿐이고, 점 덧셈·점 두배 공식도 그대로 사용
여기에 기준점 G와 차수 n까지 정해두면 누구나 같은 곡선·같은 기준점으로 키를 만들고 검증할 수 있음

그림으로 보는 P-256

실제 P-256은 점이 약 2^256개라 그대로 그릴 수 없으므로, 같은 식 y² = x³ − 3x + b 를 두 가지 방법으로 작게 그려봄

1) 실수 위에서 본 모양

a = −3 으로 고정해도 b 값에 따라 모양이 달라짐
- 판별식 4a³ + 27b² = 27(b² − 4)
- |b| < 2 : 곡선이 두 조각 (b = 1)
- |b| > 2 : 곡선이 한 조각 (b = 3)
- |b| = 2 : 판별식이 0 → 뾰족점이 생겨 타원곡선이 아님
P-256의 b는 매우 큰 수이므로 실수로 그린다면 한 조각 형태에 해당
하지만 이 매끄러운 모양은 직관을 위한 것일 뿐, 실제 계산은 아래처럼 mod p 위에서 이루어짐

2) 작은 소수 p 위에서 본 모양

P-256과 같은 꼴의 식을 p = 97, b = 1 로 줄여서 계산한 결과 (P-256은 p 자리에 256bit 소수가 들어감)
매끄러운 곡선이 아니라 0 ~ 96 사이 정수 좌표의 점 110개 (+ 무한원점 O) 로 이루어짐
특징
- 점들이 규칙 없이 흩어져 보임
- y = p/2 를 기준으로 위아래 대칭 : (x, y)가 곡선 위의 점이면 (x, p − y) 도 곡선 위의 점 (실수 곡선의 x축 대칭에 해당)
주황색 화살표 : G → 2G → 3G → 4G → 5G 순서로 G를 계속 더한 결과
- 점이 한 방향으로 이동하지 않고 이리저리 뛰어다님
- 그래서 kG 를 보고 몇 번 더했는지(k) 역추적하기 어려움 → ECDLP가 어려운 이유를 눈으로 확인할 수 있음
참고 : 이 작은 곡선의 점 개수는 111 = 3 × 37 로 소수가 아님 → Pohlig-Hellman 공격에 취약한 구조
- P-256은 점 개수 자체가 소수 n (h = 1) 이 되도록 p, b를 골랐다는 점이 다름

파라미터	의미	값 (16진수)
p	유한체 크기(소수)	FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF
a	곡선 계수	FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC (= -3 mod p)
b	곡선 계수	5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B
Gx	기준점 x 좌표	6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296
Gy	기준점 y 좌표	4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5
n	기준점 G의 차수	FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551
h	보조인자(cofactor)	1

파라미터를 이렇게 정한 이유

p = 2^256 − 2^224 + 2^192 + 2^96 − 1
- 2의 거듭제곱의 합·차로만 이루어진 특수한 형태(Solinas 소수, 일반화된 메르센 소수)
- 2^256 ≡ 2^224 − 2^192 − 2^96 + 1 (mod p) 이므로, 곱셈 결과(최대 512bit)의 윗부분을 나눗셈 없이 덧셈·뺄셈만으로 줄일 수 있음
- 각 항이 32bit 단위(224, 192, 96)로 끊어져 있어 32/64bit CPU에서 처리하기 쉬움
a = −3
- 점 두배 공식의 3x² + a 부분이 3(x² − 1) 꼴이 되어, 실제 구현(사영 좌표)에서 곱셈 횟수를 줄일 수 있음
- 모든 곡선이 a = −3 으로 바꿀 수 있는 것은 아니지만, 보안에 영향 없이 선택 가능한 값이라 속도를 위해 고정
b
- 정해진 시드(seed) 값을 SHA-1에 넣어 나온 결과를 바탕으로 생성 (Verifiably Random, ANSI X9.62 방식)
  - SEED = c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
  - 시드로부터 SHA-1로 값 c를 만들고, b² · c ≡ −27 (mod p) 를 만족하도록 b를 정함
- 설계자가 일부러 약한 곡선을 골라 넣지 않았음을 보여주기 위한 방법
- 다만 시드 자체를 어떻게 골랐는지는 공개되지 않아 의심하는 시각도 있음 → 대안으로 brainpool 곡선(유럽), Curve25519 등이 등장
n (기준점 G의 차수)
- 약 2^256 크기의 소수 → Pohlig-Hellman 공격으로 쪼갤 수 없음
- n과 p가 거의 같은 크기인 이유 : 곡선 위 점의 개수는 항상 p + 1 근처에 있음 (Hasse 정리 : |점의 개수 − (p + 1)| ≤ 2√p)
h = 1 (cofactor, 보조인자)
- h = 곡선 위 전체 점의 개수 / n
- h = 1 이면 곡선 위 전체 점의 개수가 n과 같음 → 곡선 전체가 소수 차수의 군
- O를 제외한 곡선 위 모든 점이 기준점이 될 수 있고, 작은 부분군 공격(Small Subgroup Attack)을 걱정할 필요가 없음

키와 서명의 크기

항목	크기	설명
개인키 k	32 byte	1 ~ n−1 사이의 256bit 정수
공개키 K (비압축)	65 byte	0x04 ‖ x(32) ‖ y(32)
공개키 K (압축)	33 byte	0x02 또는 0x03 ‖ x(32)
ECDSA 서명 (r, s)	64 byte	r(32) ‖ s(32)

점 압축(Point Compression)
- x를 알면 y² = x³ − 3x + b 로 y²를 계산할 수 있으므로 y는 두 값(y, p − y) 중 하나
- 두 값은 홀짝이 다르므로 y가 짝수인지(0x02) 홀수인지(0x03) 1byte만 붙이면 y를 복원 가능
  - P-256은 p mod 4 = 3 이라 제곱근을 y = (y²)^((p+1)/4) mod p 로 바로 계산할 수 있음
- IEEE 1609.2는 대역폭을 줄이기 위해 압축 형태(compressed-y-0, compressed-y-1)를 주로 사용

타원곡선함수를 활용한 공개키 생성 방식

K = kG

공개키(K) : 암호화 연산이나 서명 검증에 사용되는 공개된 점
개인키(k) : 복호화 연산이나 서명 생성에 사용되는 비밀 값
기준점(G) : 타원곡선 위 고정된 점

유의점

기준점 G의 차수는 소수인 것이 바람직함
- 소수여야 하는 이유
  - 차수가 작은 인수로 나뉘면 ECDLP를 작은 문제로 쪼개 쉽게 풀 수 있음(Pohlig-Hellman 공격)
    - 예) n = n1 × n2 이면 크기 n1, n2인 부분군에서 각각 문제를 풀고 중국인의 나머지 정리(CRT)로 합침
    - 따라서 공격 난이도는 n의 가장 큰 소인수에 의해 결정됨
  - n이 소수이면 O가 아닌 모든 점이 같은 군을 생성하므로 작은 부분군으로 빠지는 점이 없음
G의 차수 n : G를 계속 더했을 때 처음으로 무한원점 O(항등원)이 되는 가장 작은 양의 정수
- 따라서 nG = O
- kG = (k mod n)G 이므로 개인키는 n 미만의 값만 의미가 있음
개인키 k : 1 ~ n-1 사이에서 무작위로 고르는 비밀 값
- 예측 가능한 난수를 사용하면 개인키가 노출되므로 안전한 난수 생성기(CSPRNG)를 사용해야 함

ECDLP(Elliptic Curve Discrete Logarithm Problem)

K와 G를 주어질 때 k를 구하는 문제

k가 t bit 인 경우

모든 경우의 수를 대입하면 최대 2^t회의 시도
- 이유: t비트로 표현할 수 있는 정수는 2^t개이고, 타원곡선 위의 점은 규칙성 없이 흩어져 있어 G, 2G, 3G, … 를 하나씩 계산해 K와 비교하는 방법 외에 지름길이 없기 때문
- 실제 가장 효율적인 범용 공격(Pollard’s rho)도 약 √n ≈ 2^(t/2)회의 연산이 필요
  - P-256 기준 약 2^128회 → 128bit 보안 강도

따라서 타원곡선 알고리즘은 개인키와 기준점으로는 공개키 연산은 쉽지만 공개키로 개인키를 알아내기 위한 역산은 매우 어려움

정방향(kG) : Double-and-Add로 약 수백 번의 연산
역방향(K → k) : 약 2^128번의 연산

-> ECC는 단방향성 기반의 강력한 보안 구조를 가짐

Diffie-Hellman(DH) 키 교환

지수 연산의 역산이 어려운 이산대수 문제를 기반으로 한 키 교환 방법
동작과정 예시
1. 공개 파라미터 : 큰 소수 p, 생성원 g
2. Alice : 비밀값 a 선택, A = g^a mod p 를 Bob에게 전송
3. Bob : 비밀값 b 선택, B = g^b mod p 를 Alice에게 전송
4. Alice : s = B^a mod p = g^(ab) mod p
5. Bob : s = A^b mod p = g^(ab) mod p
- 도청자는 g^a, g^b 만 알 수 있고 g^(ab)를 계산하려면 a 또는 b가 필요 → 이산대수 문제
Alice와 Bob은 비밀키를 노출하지 않고 동일한 비밀키 계산 가능

ECDH(Elliptic Curve Diffie-Hellman)

DH Key Exchange의 지수 연산을 타원곡선의 스칼라 곱 연산으로 대체
- 동작 과정
  1. 공개 파라미터 : 곡선, 기준점 G
  2. Alice : 개인키 dA, 공개키 QA = dA·G 전송
  3. Bob : 개인키 dB, 공개키 QB = dB·G 전송
  4. Alice : S = dA·QB = dA·dB·G
  5. Bob : S = dB·QA = dA·dB·G
    - 공유된 점 S의 x 좌표를 KDF에 넣어 실제 대칭키로 사용
- 이점
  - 같은 보안 강도에서 키 길이가 훨씬 짧음 (DH 3072bit ↔ ECDH 256bit)
  - 연산량과 전송량이 적어 차량 OBU 같은 임베디드 환경, 무선 통신에 적합
  - 매 세션마다 임시(ephemeral) 키를 사용하면 장기 개인키가 유출되어도 과거 통신은 안전(전방향 안전성, Forward Secrecy)
DH, ECDH의 한계
- 중간자 공격을 막지 못함
  - 상대방의 공개키가 진짜 상대방의 것인지 확인하는 인증 과정이 없음
  - 공격자(Mallory)가 중간에서 Alice에게는 자신의 공개키를 Bob인 척, Bob에게는 Alice인 척 보내면 양쪽과 각각 공유키를 만들어 통신을 중계·열람 가능
- 해결 : 공개키를 인증서(PKI)로 보증하거나 ECDSA 서명을 함께 사용 → V2X에서는 SCMS가 발급한 인증서로 공개키를 보증

ECDSA(Elliptic Curve Digital Signature Algorithm)

ECDLP를 기반으로 한 디지털 서명 방식
방식
- 개인키로 서명 생성 -> 공개키로 검증
- 송신자의 개인키 없이 검증 가능
제공하는 보안 속성 : 무결성(메시지 변조 탐지), 인증(송신자 확인), 부인 방지
핵심 아이디어
서명자는 비밀 점 R = kG 를 만들고, 검증자는 개인키 없이 공개된 정보만으로 같은 점 R을 다시 만들어낸다
- 서명 = “나는 점 R을 만들었고, R을 다시 만들 수 있는 힌트 s를 줄게”
- 검증 = “힌트 s와 공개키로 계산해보니 정말 R이 나오네 → 진짜 서명”
- 힌트 s는 개인키 d를 가진 사람만 올바르게 만들 수 있으므로 위조 불가
등장하는 값

기호	의미	공개 여부
G, n	기준점과 그 차수 (곡선 파라미터)	공개
d	개인키	비밀
Q = dG	공개키	공개
e = Hash(m)	메시지의 해시값	공개
k	서명할 때마다 새로 뽑는 난수	비밀 (서명 후 폐기)
(r, s)	서명	공개

동작 과정
- 준비 : 곡선 파라미터(G, n), 개인키 d, 공개키 Q = dG

서명 생성
1. e = Hash(m) (P-256은 SHA-256)
2. 1 ~ n-1 사이의 임의의 값 k 선택 (매 서명마다 새로 생성)
3. (x1, y1) = kG
4. r = x1 mod n (r = 0 이면 k 재선택)
5. s = k^(-1) · (e + r·d) mod n (s = 0 이면 k 재선택)
6. 서명 = (r, s)

서명 검증
1. r, s가 1 ~ n-1 범위인지 확인
2. e = Hash(m)
3. w = s^(-1) mod n
4. u1 = e·w mod n, u2 = r·w mod n
5. (x1, y1) = u1·G + u2·Q
6. x1 mod n == r 이면 유효한 서명
검증이 성립하는 이유
- u1·G + u2·Q = (e·w)G + (r·w)dG = w(e + r·d)G = kG (∵ w = s^(-1) = k(e + r·d)^(-1))
- 풀어서 보면
  1. 공개키 Q = dG 를 대입하면 u1·G + u2·Q = (u1 + u2·d)·G
  2. s를 만들 때 (u1 + u2·d) 가 정확히 k 가 되도록 설계해 두었음
  3. 따라서 검증자가 계산한 점 = kG = 서명자가 만든 점 R
- 즉 검증자는
  - d를 직접 쓰지 않고, 공개키 Q 안에 들어 있는 d를 점 연산으로 간접 사용
  - k를 몰라도, s 안에 숨겨진 k를 역원(s^(-1))으로 꺼내서 R을 다시 만듦
- 메시지가 조금이라도 바뀌면 e가 달라져 전혀 다른 점이 나오므로 x 좌표가 r과 달라짐 → 검증 실패
각 단계가 필요한 이유

단계	이유
난수 k	서명마다 R이 달라져, s만 보고 d를 역산할 수 없게 함
r = R의 x 좌표	점 R 전체 대신 x 좌표만 보내 서명 크기를 줄임 (검증자는 R을 다시 만들어 비교)
s에 e를 넣음	서명을 이 메시지에 묶음 → 다른 메시지에 서명을 재사용할 수 없음
s에 d를 넣음	개인키 소유자만 올바른 s를 만들 수 있음 → 위조 방지
s에 k^(-1)를 곱함	검증 시 s^(-1)로 되돌렸을 때 정확히 k가 나오도록 함

한 줄 요약
- 서명 : 비밀 k로 점 R을 만들고, k·d·메시지를 섞은 힌트 s를 만든다
- 검증 : s와 공개키로 R을 다시 만들어, x 좌표가 r과 같은지 확인한다
유의점
- 서명용 난수 k가 재사용되거나 예측 가능하면 두 서명으로부터 개인키 d를 계산할 수 있음
  - 대책 : RFC 6979 결정적(deterministic) k 생성
IEEE 1609.2에서의 활용
- V2X 메시지(SPDU) 서명과 인증서 서명에 사용
- 서명 대상 해시 : Hash( Hash(데이터) ‖ Hash(서명자 인증서) ) → 서명을 특정 인증서에 묶음
- r 값을 좌표 전체가 아닌 x 좌표 또는 압축 점 형태로 표현해 서명 크기를 줄임

ECIES(Elliptic Curve Integrated Encryption Scheme)

타원곡선을 기반으로 한 공개키 암호화 방식
CPA(Chosen-Plaintext Attack, 공격자가 원하는 평문을 암호화해볼 수 있는 상황) 또는 CCA(Chosen-Ciphertext Attack, 공격자가 원하는 암호문을 복호화해볼 수 있는 상황)가 가능한 환경에서도 암호문을 통해 평문에 대한 어떠한 유의미한 정보를 유추할 수 없도록 설계됨
- IND-CCA2 안전성
공개키 암호(ECDH)로 키를 공유하고, 실제 데이터는 빠른 대칭키로 암호화하는 하이브리드 암호 구조
구성요소
- ECDH
  - 역할 : 송신자가 임시 키 쌍을 만들어 수신자의 공개키와 공유 비밀값(Shared Secret)을 생성
  - 사전에 키를 주고받지 않아도 수신자의 공개키만으로 암호화 가능
- KDF(Key Derivation Function)
  - 역할 : 공유 비밀값을 입력받아 필요한 길이의 균일한 키로 변환하고, 암호화 키와 MAC 키를 분리해서 생성
  - 공유 비밀값(점의 x 좌표)은 그대로 쓰기에 분포가 균일하지 않고 길이도 맞지 않기 때문에 사용
  - IEEE 1609.2 : SHA-256 기반 KDF2
- 대칭 암호화 + MAC
  - 역할 : 대칭 암호화로 기밀성, MAC으로 무결성·인증을 보장 (암호문이 변조되면 복호화 전에 거부)
  - AES-CCM
    - CTR 모드(암호화) + CBC-MAC(인증 태그) 조합
    - IEEE 1609.2 : AES-128-CCM, 12byte Nonce, 16byte 태그
  - AEAD(Authenticated Encryption with Associated Data)
    - 암호화와 인증을 한 번에 수행하는 방식
    - 헤더처럼 암호화하지 않고 평문으로 보내야 하는 데이터(Associated Data)도 함께 무결성 검증 가능
    - AES-CCM, AES-GCM이 대표적
핵심 흐름
- 송신자와 수신자는 키를 미리 주고받지 않았지만, ECDH 덕분에 같은 공유 비밀값 S를 각자 계산할 수 있음
  - 송신자 : v · K_R = v · k_R · G
  - 수신자 : k_R · V = k_R · v · G
- 같은 S → 같은 KDF → 같은 K_enc, K_mac 이 만들어지므로, 송신자가 잠근 것을 수신자가 그대로 열 수 있음
- 도청자는 V와 K_R(공개값)만 알고 v, k_R(비밀값)을 모르므로 S를 계산할 수 없음 (ECDLP)

암호화 과정 (IEEE 1609.2 기준)
1. 수신자의 공개키 K_R 획득 (인증서의 암호화 키)
2. 임시 키 쌍 생성 : 개인키 v, 공개키 V = vG
3. 공유 비밀값 S = v·K_R 의 x 좌표
4. KDF(S, P1) → 암호화 키 K_enc ‖ MAC 키 K_mac (P1 : 수신자 정보의 해시)
5. 데이터 암호화용 AES 키 생성 후 C = AES 키 ⊕ K_enc
6. T = HMAC-SHA256(K_mac, C) (16byte로 절삭)
7. 실제 데이터는 AES 키로 AES-128-CCM 암호화
8. (V, C, T) + 암호화된 데이터 전송

복호화 과정
1. 수신자 : S = k_R·V 의 x 좌표 계산 (k_R : 수신자 개인키, k_R·V = k_R·vG = v·K_R)
2. KDF(S, P1) → K_enc ‖ K_mac
3. HMAC-SHA256(K_mac, C) 가 T와 일치하는지 검증 (불일치 시 폐기)
4. AES 키 = C ⊕ K_enc
5. AES 키로 AES-128-CCM 복호화 및 태그 검증
SCMS, IEEE 1609.2에서 활용
- SCMS : 인증서 발급 응답을 차량만 열어볼 수 있도록 암호화 (아래 Cocoon Encryption)
- IEEE 1609.2 : 특정 수신자에게만 보내는 유니캐스트 메시지 암호화(EncryptedData)

Butterfly Key Mechanism

하나의 인증서 요청을 기반으로 여러 개의 익명 인증서를 생성
특징 : ECDLP 기반
- 공개키끼리 더해도 대응하는 개인키끼리 더한 것과 같다는 성질 이용 : aG + bG = (a + b)G
역할 : 익명성 보장, 추적 방지
- 같은 시간대에 유효한 인증서를 여러개 가지고, 시간이나 장소마다 각기 다른 인증서를 사용(Pseudonym 인증서)
- 차량이 수천 개의 인증서를 각각 요청하지 않아도 되므로 통신량과 연산량이 크게 줄어듦
한눈에 보기 : 애벌레(Caterpillar) → 고치(Cocoon) → 나비(Butterfly)

차량은 Caterpillar 공개키 1개만 보내고, RA가 이를 n개의 Cocoon 키로 늘리고, PCA가 각각에 랜덤값 c_i를 더해 최종 Butterfly 키를 만듦
공개키를 더하는 것(B_i + c_i·G)은 개인키를 더하는 것(b_i + c_i)과 대응하므로, 차량은 c_i만 받으면 개인키를 직접 계산할 수 있음
RA는 c_i를 모르고, PCA는 a와 ck를 모르므로 차량만 최종 개인키를 알 수 있음

버터플라이 키 확장(Butterfly Key Expansion)

이 그림은 V2X 보안 표준(IEEE 1609.2 / SCMS)에서 차량이 수십~수천 개의 익명 인증서(가명 인증서)를 한 번의 요청으로 받아내는 방법을 보여줍니다. 차량은 추적을 피하려고 인증서를 자주 바꿔 써야 하는데, 매번 키를 만들어 하나씩 요청하면 너무 비효율적입니다. 그래서 씨앗 키 하나를 보내면 서버 쪽에서 불려서(확장해서) 여러 개로 만들어 주는 구조를 씁니다.

기본 원리: 타원곡선 키의 “덧셈 성질”

타원곡선 암호에서 공개키는 공개키 = 개인키 × G(G는 고정된 기준점)입니다. 여기서 중요한 성질은 다음과 같습니다.

개인키에 어떤 수 x를 더하면, 공개키에는 x·G를 더한 것과 같다.
즉, (a + x)·G = A + x·G

덕분에 개인키를 모르는 서버도 공개키만으로 새 공개키를 만들 수 있고, 차량은 같은 x만 알면 그에 맞는 개인키를 스스로 계산할 수 있습니다. 그림 전체가 이 성질 하나로 돌아갑니다.

단계별 흐름 (위에서 아래로)

① End entity (차량) – 씨앗 키 생성
차량은 키 한 쌍을 만듭니다. 빨간 상자의 a(개인키)와 A(공개키)입니다(애벌레 키, caterpillar key라고도 부름). 그리고 확장 함수 f와 그 비밀값을 정합니다. 차량은 A와 확장 함수 정보만 서버로 보내고, a는 절대 내보내지 않습니다.

② Cocoon Key Expander (보통 RA, 등록기관) – 공개키 불리기
받은 A에 확장 함수를 적용해 B1, B2, …, Bn(고치 키, cocoon key)을 만듭니다.

Bi = A + f(i)·G

동시에 차량도 자기 쪽에서 같은 함수를 a에 적용해(그림 위쪽 “Exp.”) b1 … bn을 미리 계산해 둡니다. bi = a + f(i)이므로 bi와 Bi는 서로 짝이 맞는 키 쌍입니다.

③ Butterfly Key Expander – 무작위 값 c 섞기
각 Bi마다 새로운 무작위 수 c를 고르고 cG를 더해 최종 공개키를 만듭니다.

버터플라이 공개키 = Bi + c·G

이 단계가 핵심 보안 장치입니다. ②의 RA는 Bi는 알지만 c를 모르므로, 최종 인증서에 들어간 공개키를 보고 “이게 그 차량의 키구나” 하고 연결할 수 없습니다.

④ ACA (인증서 발급기관) – 인증서 발급
버터플라이 공개키에 대한 인증서(Cert)를 발급합니다. 이 인증서와 c 값은 (차량만 열 수 있도록 암호화되어) 차량에게 전달됩니다. 오른쪽의 긴 화살표 두 개가 각각 c와 Cert가 차량으로 돌아가는 경로입니다.

⑤ 다시 차량 – 최종 개인키 완성
차량은 미리 계산해 둔 bi에 받은 c를 더합니다(그림의 “+”).

최종 개인키 = bi + c

검산해 보면 (bi + c)·G = Bi + c·G = 버터플라이 공개키이므로, 인증서와 개인키가 정확히 짝이 맞습니다.

메시지 흐름 : 차량 → RA → PCA → RA → 차량
RA는 중간에서 전달만 하고, 응답은 차량만 열 수 있도록 암호화되어 있음
맨 아래 표처럼 각 기관이 아는 정보가 나뉘어 있어 익명성이 보장됨

동작방식

Caterpillar Key
- 차량(End Entity)이 생성하는 원본 키 쌍
- 서명용 : 개인키 a, 공개키 A = aG
- 암호화용 : 개인키 p, 공개키 P = pG
- 확장 함수용 AES 키 ck, ek 와 함께 공개키 A, P를 RA에 한 번만 전송
Cocoon Key
- RA가 확장 함수 f(AES 기반 의사난수 함수)로 Caterpillar 공개키를 여러 개로 확장
- B_i = A + f1(ck, i)·G
- Q_i = P + f2(ek, i)·G
- RA는 여러 차량의 Cocoon Key 요청을 섞어(shuffle) PCA에 전달 → PCA는 어떤 요청이 같은 차량의 것인지 알 수 없음
Butterfly Key
- PCA가 임의의 값 c_i를 선택해 최종 공개키 생성 : U_i = B_i + c_i·G
- U_i를 담은 Pseudonym 인증서 발급
- 인증서와 c_i를 Q_i로 암호화(Cocoon Encryption)하여 RA를 거쳐 차량에 전달

Butterfly 개인키 계산

차량은 q_i = p + f2(ek, i) 로 응답을 복호화해 c_i를 획득
개인키 u_i = a + f1(ck, i) + c_i
u_i·G == U_i 인지 확인해 키 쌍이 올바른지 검증
이해하기 : 공개키끼리 더하면 개인키끼리 더한 것과 같음
- kG 는 G를 k번 더한 점이므로 aG + bG = (G를 a번) + (G를 b번) = (a + b)G
- 즉, 점(공개키)끼리 더하면 그 결과의 개인키는 숫자(개인키)끼리 더한 값이 됨 (예: 3G + 4G = 7G)
- 각 단계의 공개키를 (숫자)·G 꼴로 정리하면, 괄호 안의 숫자가 곧 그 공개키의 개인키

Caterpillar : A   = a·G                               → 개인키 a
Cocoon      : B_i = A + f1·G   = (a + f1)·G           → 개인키 a + f1
Butterfly   : U_i = B_i + c_i·G = (a + f1 + c_i)·G     → 개인키 a + f1 + c_i

RA와 PCA는 점에 점을 더했을 뿐인데, 개인키 쪽에서는 숫자가 더해진 효과가 생김
왜 차량만 개인키를 알 수 있나 : u_i = a + f1 + c_i 를 계산하려면 세 값을 모두 알아야 함

값	차량	RA	PCA
a (Caterpillar 개인키)	✅ 직접 생성	❌ (A만 봄)	❌
f1 (ck로 계산)	✅ ck를 앎	✅ ck를 받음	❌
c_i (랜덤값)	✅ 응답을 복호화해 획득	❌ (암호화되어 못 봄)	✅ 직접 생성
u_i 계산 가능?	✅	❌	❌

복호화도 같은 원리
- Q_i = P + f2·G = p·G + f2·G = (p + f2)·G → 개인키 q_i = p + f2
- 차량은 p와 ek를 알므로 q_i를 계산해 응답을 열 수 있고, RA는 f2는 알지만 p를 몰라 열 수 없음
검증(u_i·G == U_i)이 필요한 이유
- 직접 계산한 u_i·G 와 인증서 안의 U_i 가 같으면 짝이 맞는 키 쌍
- 다르면 c_i가 잘못 왔거나 응답이 변조된 것 → 이 인증서로 서명하면 아무도 검증할 수 없으므로 사용 전에 미리 확인
작은 숫자로 확인 (y² = x³ + 2x + 2 mod 17, G = (5, 1))

a   = 5  →  A   = 5G              = (9, 16)
f1  = 3  →  B_i = A + 3G   = 8G   = (13, 7)
c_i = 7  →  U_i = B_i + 7G = 15G  = (3, 16)

차량 계산 : u_i = 5 + 3 + 7 = 15
검증      : 15G = (3, 16) == U_i  ✅

보관
- 계산한 개인키와 Pseudonym 인증서를 안전한 저장소(HSM 등)에 보관
- 유효 기간(예: 1주)마다 여러 개(예: 20개)의 인증서를 사용하며 주기적으로 교체

Cocoon Encryption
- PCA가 Cocoon 공개키(Q_i)로 응답을 ECIES 암호화하는 것
- 응답이 RA를 거쳐 전달되지만 RA는 개인키가 없어 인증서 내용을 볼 수 없음
- PCA가 c_i를 더하므로 RA는 최종 Butterfly 공개키를 알 수 없음 → RA가 인증서와 차량을 연결하지 못함

Butterfly Key의 종류 (OBK, UBK, CUBK)
- OBK(Original Butterfly Keys)
  - 서명용과 암호화용 Caterpillar Key를 각각 사용 (키 쌍 2개, 확장 함수 2개)
  - PCA는 응답을 Cocoon 암호화 키로 암호화하고 별도로 서명
- UBK(Unified Butterfly Keys)
  - 하나의 Caterpillar Key를 서명용·암호화용으로 함께 사용
  - Cocoon Key 하나로 인증서 공개키 유도와 응답 암호화를 동시에 수행
  - 요청 크기와 연산량이 OBK보다 줄어들며, 응답에 대한 별도 서명을 생략할 수 있음
- CUBK(Compact Unified Butterfly Keys)
  - UBK를 묵시적 인증서(Implicit Certificate)에 적용한 방식
  - 묵시적 인증서는 서명 대신 재구성 값(Reconstruction Value)으로 공개키를 복원하므로 인증서와 응답이 가장 작음
SCMS, IEEE 1609.2 에서 활용
- IEEE 1609.2.1 에서 인증서 요청·발급 절차로 정의
- 효과
  - RA
    - 차량의 신원은 알지만 발급된 인증서 내용(Butterfly 공개키)은 알 수 없음
    - 차량 대신 대량의 Cocoon Key를 생성하므로 차량의 요청 부담이 감소
  - ACA/PCA
    - 인증서를 발급하지만 요청한 차량이 누구인지 알 수 없음
    - RA가 요청을 섞고, 확장 함수의 키(ck, ek)를 모르므로 여러 인증서가 같은 차량의 것인지 연결할 수 없음
  - 결과적으로 어느 한 기관도 단독으로 “차량 ↔ 인증서”를 연결할 수 없어 내부자로부터도 프라이버시가 보호됨

정리 : SCMS 익명 인증서 발급에서의 활용

지금까지 정리한 ECC 기반 알고리즘들은 SCMS에서 익명 인증서(Pseudonym Certificate)를 발급하고 사용하는 과정 곳곳에 함께 쓰인다.

단계별 흐름
- 0. 등록 : ECA가 차량의 공개키에 서명한 등록 인증서(Enrollment Certificate)를 발급 → 차량의 “신분증”
- 1. 요청 : 차량이 Caterpillar 키를 만들고, 요청에 등록 인증서 키로 서명한 뒤 RA만 열 수 있게 암호화하여 한 번만 전송
- 2. 확장 : RA가 요청을 복호화하고 서명을 검증한 뒤, Cocoon 키를 n개로 확장하고 여러 차량의 요청을 섞어 PCA로 전달
- 3. 발급 : PCA가 랜덤값 c_i를 더해 Butterfly 공개키 U_i를 만들고, 이를 담은 익명 인증서에 서명
- 4. 암호화 : PCA가 Cocoon 공개키 Q_i로 응답을 암호화 → RA는 내용을 볼 수 없음
- 5. 전달 : RA는 암호화된 응답을 보관했다가 차량에 전달
- 6. 완성 : 차량이 응답을 복호화해 c_i를 얻고, 개인키 u_i를 계산한 뒤 u_i·G == U_i 와 PCA 서명을 확인
- 발급 후 : 차량은 익명 개인키로 BSM에 서명하고 익명 인증서를 첨부해 브로드캐스트, 수신 차량은 인증서 체인과 서명을 검증
- 참고 : 그림에서는 생략했지만, 실제 SCMS에는 폐기(Revocation)를 위한 연결값을 만드는 LA(Linkage Authority)와 오작동 차량을 판별하는 MA(Misbehavior Authority)도 존재
알고리즘별 역할 요약

알고리즘	SCMS에서 쓰이는 곳	목적
ECDSA	등록 인증서·익명 인증서 서명, 인증서 요청 서명, BSM 서명	누가 보냈는지 확인(인증), 변조 탐지(무결성)
ECIES (ECDH + KDF + AES-CCM)	차량 → RA 요청 암호화, PCA → 차량 응답 암호화(Cocoon Encryption)	지정된 수신자만 내용을 볼 수 있게 함(기밀성)
Butterfly Key	Caterpillar → Cocoon → Butterfly 키 확장	요청 1번으로 익명 인증서 n개 발급, 기관 간 정보 분리로 익명성 보장
ECC / ECDLP	위 모든 알고리즘의 기반	공개키로부터 개인키를 역산할 수 없음(단방향성)

마무리
- ECC : 짧은 키로 높은 보안 강도를 제공해 대역폭과 연산 자원이 제한된 V2X 환경에 적합
- ECDSA 로 “누가 보냈고 변조되지 않았는지”를, ECIES 로 “정해진 상대만 읽을 수 있는지”를, Butterfly Key 로 “누구인지는 드러나지 않는지”를 보장
- 세 가지가 맞물려 SCMS는 신뢰할 수 있지만 추적할 수 없는 V2X 통신을 가능하게 함

V2X

This post is licensed under CC BY 4.0 by the author.