전자서명 (ECDSA)

Sign : ℤₙ × 𝔹* → 𝔹⁶⁴ · Verify : E(𝔽ₚ) × 𝔹* × 𝔹⁶⁴ → {유효, 무효} · P-256, SHA-256 · 키: 비대칭키 만들기

앨리스 개인 키 d32바이트

k (일회용 난수)32바이트

문서

서명: Sign(d, m)

k (일회용 난수)32바이트

a6e3c57dd01abe90086538398355dd4c3b17aa873382b0f24d6129493d8aad60

개인 키 d32바이트

c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721

문서 m

이 계약서의 내용에 동의합니다. - 앨리스

ECDSA 서명

ℤₙ × 𝔹* → 𝔹⁶⁴

서명 (r ‖ s)64바이트

efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633

Sign 안에서

1
문서를 해시해서 정수로: e = OS2IP(SHA-256(m))
문서 m
이 계약서의 내용에 동의합니다. - 앨리스
OS2IP(SHA-256(m))
𝔹* → ℤ
e32바이트
c7ddf8b1fbcd5efbadebc4e86233e85f34980efd61ef8bf819026786b15dcb30
2
R = [k]G
기준점 Gx, y 각 32바이트
6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
k (일회용 난수)32바이트
a6e3c57dd01abe90086538398355dd4c3b17aa873382b0f24d6129493d8aad60
[d]G
ℤₙ × E(𝔽ₚ) → E(𝔽ₚ)
R = [k]G
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf371634a7e72c423213443152c82df94fe0f6851bf894fd91c64b19555346093ff492
3
r = R.x mod n
n (위수)32바이트
ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
R.x↑ 2단계 결과
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716
R.x mod n
E(𝔽ₚ) → ℤₙ
r32바이트
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716
4
k⁻¹ = k^(n−2) mod n
지수 n − 232바이트
ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc63254f
k (일회용 난수)32바이트
a6e3c57dd01abe90086538398355dd4c3b17aa873382b0f24d6129493d8aad60
k⁻¹ mod n
ℤₙ* → ℤₙ*
k⁻¹32바이트
aaf7a4c4d10293a89370e2cc3e88ca623e38b5814d37eb5e96ffdea769cfe547
5
s = k⁻¹ · (e + r·d) mod n
k⁻¹32바이트↑ 4단계 결과
aaf7a4c4d10293a89370e2cc3e88ca623e38b5814d37eb5e96ffdea769cfe547
e32바이트↑ 1단계 결과
c7ddf8b1fbcd5efbadebc4e86233e85f34980efd61ef8bf819026786b15dcb30
r32바이트↑ 3단계 결과
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716
개인 키 d32바이트
c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721
k⁻¹ · (e + r·d) mod n
ℤₙ⁴ → ℤₙ
s32바이트
b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633
6
서명 = I2OSP(r, 32) ‖ I2OSP(s, 32)
r32바이트↑ 3단계 결과
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716
s32바이트↑ 5단계 결과
b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633
I2OSP(r, 32) ‖ I2OSP(s, 32)
ℤₙ² → 𝔹⁶⁴
서명 (r ‖ s)64바이트
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633

보내는 내용 (공개 키 Q는 미리 공개해 둠)

이 계약서의 내용에 동의합니다. - 앨리스‖efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633

공개 키 Q = [d]G

0460fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb67903fe1008b8bc99a41ae9e95628bc64f2f1b20c2d7e9f5177a3c294d4462299

검증: Verify(Q, m, 서명)

공개 키 Q = [d]G

60fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb67903fe1008b8bc99a41ae9e95628bc64f2f1b20c2d7e9f5177a3c294d4462299

받은 문서

받은 서명64바이트

ECDSA 검증

E(𝔽ₚ) × 𝔹* × 𝔹⁶⁴ → {유효, 무효}

✓ 유효

Verify 안에서

1
서명을 나누고 범위 확인: r, s ∈ [1, n−1]
받은 서명64바이트
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633
r, s ∈ [1, n−1]
𝔹⁶⁴ → ℤₙ² 또는 거부
r, s32바이트
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633✓ 범위 안
2
받은 문서를 해시해서 정수로: e = OS2IP(SHA-256(m))
받은 문서 m
이 계약서의 내용에 동의합니다. - 앨리스
OS2IP(SHA-256(m))
e32바이트
c7ddf8b1fbcd5efbadebc4e86233e85f34980efd61ef8bf819026786b15dcb30
3
w = s⁻¹ mod n
지수 n − 232바이트
ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc63254f
s32바이트↑ 1단계 결과
b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633
s⁻¹ mod n
w = s⁻¹32바이트
fa051dd4a81968e7079dfc14895330f55a3e34be7aac692c949b2969623d6b18
4
u₁ = e·w mod n, u₂ = r·w mod n
e32바이트↑ 2단계 결과
c7ddf8b1fbcd5efbadebc4e86233e85f34980efd61ef8bf819026786b15dcb30
r32바이트↑ 1단계 결과
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716
w = s⁻¹32바이트↑ 3단계 결과
fa051dd4a81968e7079dfc14895330f55a3e34be7aac692c949b2969623d6b18
e·w, r·w mod n
u₁, u₂각 32바이트
25970c793a06b2f8baeace910c22c59972acc555f0e4bc1a8865afeff0b628a3f1489bbc67ff6e03c1e65e843d2f1f7a89769c7f5828762a400441fc4a562d9f
5
X = [u₁]G + [u₂]Q
기준점 Gx, y 각 32바이트
6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
u₁, u₂각 32바이트↑ 4단계 결과
25970c793a06b2f8baeace910c22c59972acc555f0e4bc1a8865afeff0b628a3f1489bbc67ff6e03c1e65e843d2f1f7a89769c7f5828762a400441fc4a562d9f
공개 키 Q = [d]G
60fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb67903fe1008b8bc99a41ae9e95628bc64f2f1b20c2d7e9f5177a3c294d4462299
[u₁]G + [u₂]Q
스칼라 곱 두 번 + 점 덧셈
X = [u₁]G + [u₂]Q
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf371634a7e72c423213443152c82df94fe0f6851bf894fd91c64b19555346093ff492
6
X.x mod n이 r과 같은지
X.x mod n↑ 5단계 결과
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716
r32바이트↑ 1단계 결과
efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716
X.x mod n ≟ r
→ {유효, 무효}
결과64바이트
✓ 유효

검증이 맞는 이유: X = R

X: [u₁]G + [u₂]Q = [e·w]G + [r·w]([d]G)
: = [w · (e + r·d)] G
: = [k · (e + r·d)⁻¹ · (e + r·d)] G (s = k⁻¹(e + r·d) 이므로 w = k · (e + r·d)⁻¹)
: = [k]G = R → X.x mod n = r

k가 새면: d = r⁻¹ · (s·k − e) mod n

r32바이트

efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716

s32바이트

b2c38bf837ad7696440f90d9a593020a3fe3614352d0c3bc301e307c64c44633

새어 나간 k32바이트

a6e3c57dd01abe90086538398355dd4c3b17aa873382b0f24d6129493d8aad60

e32바이트

c7ddf8b1fbcd5efbadebc4e86233e85f34980efd61ef8bf819026786b15dcb30

r⁻¹ · (s·k − e) mod n

알아낸 개인 키 d32바이트

c9afa9d845ba75166b5c215767b1d6934e50c3db36e89b127b8a622b120f6721

✗ 앨리스의 개인 키와 같음 · k는 절대 새거나 다시 쓰면 안 됨

상수 · 표준이 정해 두어 누구나 같은 값

P-256 (secp256r1)FIPS 186-5 · SEC 2

기호	이름	정의 · 출처	값
p	소수 p (체의 크기)	2²⁵⁶ − 2²²⁴ + 2¹⁹² + 2⁹⁶ − 1	ffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a	곡선 계수 a	−3 ≡ p − 3	ffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b	곡선 계수 b	시드의 SHA-1에서 생성	5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
G	기준점 G (생성원)	(Gx, Gy)	6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c2964fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
n	위수 n	[n]G = O인 가장 작은 n (소수)	ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
h	보조인자 h (cofactor)	곡선 위 점의 개수 / n	1

SHA-256FIPS 180-4

기호	이름	정의 · 출처	값
H⁽⁰⁾	초기 해시값 (IV)	처음 8개 소수 2 … 19의 제곱근 소수부 앞 32비트	6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19
K₀ … K₆₃	라운드 상수	처음 64개 소수 2 … 311의 세제곱근 소수부 앞 32비트	428a2f9871374491b5c0fbcfe9b5dba53956c25b59f111f1923f82a4ab1c5ed5d807aa9812835b01243185be550c7dc372be5d7480deb1fe9bdc06a7c19bf174e49b69c1efbe47860fc19dc6240ca1cc2de92c6f4a7484aa5cb0a9dc76f988da983e5152a831c66db00327c8bf597fc7c6e00bf3d5a7914706ca63511429296727b70a852e1b21384d2c6dfc53380d13650a7354766a0abb81c2c92e92722c85a2bfe8a1a81a664bc24b8b70c76c51a3d192e819d6990624f40e3585106aa07019a4c1161e376c082748774c34b0bcb5391c0cb34ed8aa4a5b9cca4f682e6ff3748f82ee78a5636f84c878148cc7020890befffaa4506cebbef9a3f7c67178f2
	블록 크기	압축 함수 한 번에 넣는 크기	512비트 (64바이트)
	워드 크기	모든 연산의 단위, mod 2³²	32비트 (4바이트)
	라운드 수	블록 하나당 (= K의 개수)	64
	출력 길이	H⁽ᴺ⁾의 8워드	256비트 (32바이트)

전자서명 (ECDSA)

서명: Sign(d, m)

Sign 안에서

문서를 해시해서 정수로: e = OS2IP(SHA-256(m))

R = [k]G

r = R.x mod n

k⁻¹ = k^(n−2) mod n

s = k⁻¹ · (e + r·d) mod n

서명 = I2OSP(r, 32) ‖ I2OSP(s, 32)

보내는 내용 (공개 키 Q는 미리 공개해 둠)

검증: Verify(Q, m, 서명)

Verify 안에서

서명을 나누고 범위 확인: r, s ∈ [1, n−1]

받은 문서를 해시해서 정수로: e = OS2IP(SHA-256(m))

w = s⁻¹ mod n

u₁ = e·w mod n, u₂ = r·w mod n

X = [u₁]G + [u₂]Q

X.x mod n이 r과 같은지

검증이 맞는 이유: X = R

k가 새면: d = r⁻¹ · (s·k − e) mod n

상수 · 표준이 정해 두어 누구나 같은 값

P-256 (secp256r1)FIPS 186-5 · SEC 2

SHA-256FIPS 180-4