키 합의 (X25519)

1. 각자 공개 키 만들기

2. 공개 키만 주고받고, 내 개인 키와 상대 공개 키로 계산

3. 엿들은 사람은 같은 값을 만들 수 없음

✗ 공유 비밀값과 다름 · A와 B로는 a나 b를 거꾸로 구할 수 없음

4. 공유 비밀값은 그대로 쓰지 않고 키로 바꿔서 씀

공유 비밀값 → HKDF-Extract · HKDF-Expand-Label → 키 → AES-256-GCM

X25519 안에서: 앨리스의 개인 키 a가 공개 키 A가 되기까지

1. 1

   바이트열을 정수로 (작은 자리부터): 𝔹³² → ℤ

   개인 키 a32바이트

   77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a

   ▶

   LE-OS2IP

   k = Σ bᵢ · 256ⁱ

   ▶

   정수 k77자리

   19076158533740022697853188432810029468508100820210985396154491514718125885303
2. 2

   클램핑: k′ = 2²⁵⁴ + 8 · ⌊(k mod 2²⁵⁴) / 8⌋

   정수 k↑ 1단계 결과

   19076158533740022697853188432810029468508100820210985396154491514718125885303

   ▶

   clamp

   ℤ → {2²⁵⁴ + 8m : 0 ≤ m < 2²⁵¹}

   ▶

   스칼라 k′77자리 · 8의 배수 · 2²⁵⁴ ≤ k′ < 2²⁵⁵

   48024180843069071553745934684982006431825596986621126406018887516696408295280
3. 3

   기준점 바이트를 u 좌표로: u = LE-OS2IP(U) mod 2²⁵⁵

   기준점 G 바이트32바이트

   0900000000000000000000000000000000000000000000000000000000000000

   ▶

   LE-OS2IP mod 2²⁵⁵

   𝔹³² → 𝔽ₚ

   ▶

   u₁

   9
4. 4

   몽고메리 래더: (x₂ : z₂) = [k′]u, 255단계

   스칼라 k′↑ 2단계 결과

   48024180843069071553745934684982006431825596986621126406018887516696408295280

   u₁↑ 3단계 결과

   9

   ▶

   [k]u

   ℤ × 𝔽ₚ → 𝔽ₚ² (사영 좌표)

   ▶

   (x₂ : z₂)

   559e436ff8a76fae783f6811a56e0289b51cd9b9c6359799c9344541a9fe2e45102fec2971a04eafa7ea7b1c1bd82d1f9da24b44dbe71c1b3a53537f12aca0fc
5. 5

   사영 좌표 → u 좌표: u = x₂ · z₂^(p−2) mod p

   지수 p − 232바이트

   7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeb

   ▼

   (x₂ : z₂)↑ 4단계 결과

   559e436ff8a76fae783f6811a56e0289b51cd9b9c6359799c9344541a9fe2e45102fec2971a04eafa7ea7b1c1bd82d1f9da24b44dbe71c1b3a53537f12aca0fc

   ▶

   x₂ · z₂^(p−2) mod p

   𝔽ₚ² → 𝔽ₚ

   ▶

   u = [k′]G의 u 좌표

   6a4e9baa8ea9a4ebf41a38260d3abf0d5af73eb4dc7d8b7454a7308909f02085
6. 6

   정수를 바이트열로 (작은 자리부터): 𝔽ₚ → 𝔹³²

   u 좌표↑ 5단계 결과

   6a4e9baa8ea9a4ebf41a38260d3abf0d5af73eb4dc7d8b7454a7308909f02085

   ▶

   I2OSP_LE(u, 32)

   bᵢ = ⌊u / 256ⁱ⌋ mod 256

   ▶

   공개 키 A32바이트

   8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a

몽고메리 래더 255단계 전부: t = 254 … 0

교환(↔)은 비트에 따라 두 점의 자리를 바꾸는 것이에요. 비트와 상관없이 매 단계 같은 계산을 해서, 걸린 시간으로 개인 키가 드러나지 않아요.

단위 연산: 래더 한 단계 · 첫 단계 t = 254 (교환 후 (x₂ : z₂) = (u₁ : 1), (x₃ : z₃) = (1 : 0))

모든 덧셈, 뺄셈, 곱셈은 mod p예요. 역원(나눗셈)은 마지막에 한 번만 해요.

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