PKI/Cryptography

EdDSA ์•Œ๊ณ ๋ฆฌ์ฆ˜ Ed25519 ๊ณผ Ed448์— ๊ด€ํ•˜์—ฌ

JayKim๐Ÿ™‚ 2023. 6. 15. 09:23

์ด ๊ธ€์€ [์ถœ์ฒ˜] Practical Cryptographiy for Developer ์—์„œ ๋‚˜์˜ค๋Š” EdDSA ์™€ Ed25519 ์— ๊ด€ํ•œ๊ธ€์„ ๋ฒˆ์—ญ ํ•œ ๊ฒƒ์ด๋‹ค.

EdDSA(Edwards-curve Digital Signature Algorithm)๋Š”
255๋น„ํŠธ ๊ณก์„  ๋ฐ 448๋น„ํŠธ ๊ณก์„ ๊ณผ ๊ฐ™์€ ์„ฑ๋Šฅ ์ตœ์ ํ™” ํƒ€์› ๊ณก์„ ์„ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•˜๋Š” ํ˜„๋Œ€์ ์ด๊ณ  ์•ˆ์ „ํ•œ ๋””์ง€ํ„ธ ์„œ๋ช… ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค.

EdDSA ์„œ๋ช…์€ ๊ฐ๊ฐ edwards25519 ๋ฐ edwards448์ธ ํƒ€์› ๊ณก์„ ์˜ Edwards ํ˜•์‹(์„ฑ๋Šฅ์ƒ์˜ ์ด์œ ๋กœ)์„ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.
EdDSA ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ECDLP ๋ฌธ์ œ์˜ ๋‚œ์ด๋„๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•˜๋ฉฐ ์ด์— ์˜์กดํ•ฉ๋‹ˆ๋‹ค.

EdDSA ์„œ๋ช… ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๊ทธ ๋ณ€ํ˜•์ธ Ed25519 ๋ฐ Ed448์€ RFC8032 ์— ๊ธฐ์ˆ ์ ์œผ๋กœ ์„ค๋ช…๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค.

EdDSA ํ‚ค ์ƒ์„ฑ

Ed25519 ๋ฐ Ed448์€ ์ž‘์€ ๊ฐœ์ธ ํ‚ค(๊ฐ๊ฐ 32 ๋˜๋Š” 57๋ฐ”์ดํŠธ), ์ž‘์€ ๊ณต๊ฐœ ํ‚ค(32 ๋˜๋Š” 57๋ฐ”์ดํŠธ) ๋ฐ
์ž‘์€ ์„œ๋ช…(64 ๋˜๋Š” 114๋ฐ”์ดํŠธ)์„ ๋™์‹œ์— ๋†’์€ ๋ณด์•ˆ ์ˆ˜์ค€(๊ฐ๊ฐ 128๋น„ํŠธ ๋˜๋Š” 224๋น„ํŠธ)์œผ๋กœ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.

EdDSA ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํƒ€์› ๊ณก์„ ์—๋Š” ์ƒ์„ฑ๊ธฐ ์  G์™€ G์—์„œ ์ƒ์„ฑ๋œ EC ์ ์— ๋Œ€ํ•œ ํ•˜์œ„ ๊ทธ๋ฃน ์ฐจ์ˆ˜ q๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ฉ๋‹ˆ๋‹ค.
EdDSA ํ‚ค ์Œ์€ ๋‹ค์Œ์œผ๋กœ ๊ตฌ์„ฑ๋ฉ๋‹ˆ๋‹ค.

  • ๊ฐœ์ธ ํ‚ค(์ •์ˆ˜): privKey
  • ๊ณต๊ฐœ ํ‚ค(EC ํฌ์ธํŠธ): pubKey = privKey * G

๊ฐœ์ธ ํ‚ค๋Š” ์‹œ๋“œ(๊ณก์„  ์ˆœ์„œ์™€ ๊ฐ™์ด ๋น„ํŠธ ๊ธธ์ด๊ฐ€ ์œ ์‚ฌํ•ด์•ผ ํ•จ)๋กœ ์•Œ๋ ค์ง„ ์ž„์˜์˜ ์ •์ˆ˜์—์„œ ์ƒ์„ฑ๋ฉ๋‹ˆ๋‹ค.
์‹œ๋“œ๊ฐ€ ๋จผ์ € ํ•ด์‹œ๋œ ๋‹ค์Œ ๊ณก์„  cofactor(Ed25519์˜ ๊ฒฝ์šฐ 8, X448์˜ ๊ฒฝ์šฐ 4)์— ํ•ด๋‹นํ•˜๋Š” ๋งˆ์ง€๋ง‰ ๋ช‡ ๋น„ํŠธ๊ฐ€ ์ง€์›Œ์ง„ ๋‹ค์Œ ๊ฐ€์žฅ ๋†’์€ ๋น„ํŠธ๊ฐ€ ์ง€์›Œ์ง€๊ณ  ๋‘ ๋ฒˆ์งธ๋กœ ๋†’์€ ๋น„ํŠธ๊ฐ€ ์„ค์ •๋ฉ๋‹ˆ๋‹ค.
์ด๋Ÿฌํ•œ ๋ณ€ํ™˜์€ ๊ฐœ์ธ ํ‚ค๊ฐ€ ํ•ญ์ƒ ๊ณก์„ ์˜ ๋™์ผํ•œ EC ์ง€์  ํ•˜์œ„ ๊ทธ๋ฃน์— ์†ํ•˜๊ณ  ๊ฐœ์ธ ํ‚ค๊ฐ€ ํ•ญ์ƒ ์œ ์‚ฌํ•œ ๋น„ํŠธ ๊ธธ์ด๋ฅผ ๊ฐ–๋„๋ก ๋ณด์žฅํ•ฉ๋‹ˆ๋‹ค(ํƒ€์ด๋ฐ ๊ธฐ๋ฐ˜ ์‚ฌ์ด๋“œ ์ฑ„๋„ ๊ณต๊ฒฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธ).
Ed25519์˜ ๊ฒฝ์šฐ ๊ฐœ์ธ ํ‚ค๋Š” 32๋ฐ”์ดํŠธ์ž…๋‹ˆ๋‹ค. Ed448์˜ ๊ฒฝ์šฐ ๊ฐœ์ธ ํ‚ค๋Š” 57๋ฐ”์ดํŠธ์ž…๋‹ˆ๋‹ค.
๊ณต๊ฐœ ํ‚ค pubKey๋Š” EC ํฌ์ธํŠธ ๊ณฑ์…ˆ: pubKey = privKey * G(๊ณก์„ ์— ๋Œ€ํ•ด ์ƒ์„ฑ๊ธฐ ํฌ์ธํŠธ G๋ฅผ ๊ณฑํ•œ ๊ฐœ์ธ ํ‚ค)๋กœ ๊ณ„์‚ฐ๋˜๋Š” ํƒ€์› ๊ณก์„ ์˜ ํ•œ ์ ์ž…๋‹ˆ๋‹ค.

๊ณต๊ฐœ ํ‚ค๋Š” x ์ขŒํ‘œ์˜ ์ตœํ•˜์œ„ ๋น„ํŠธ(ํŒจ๋ฆฌํ‹ฐ)์™€ ๊ฒฐํ•ฉ๋œ y ์ขŒํ‘œ์ธ ์••์ถ•๋œ EC ํฌ์ธํŠธ๋กœ ์ธ์ฝ”๋”ฉ๋ฉ๋‹ˆ๋‹ค. Ed25519์˜ ๊ฒฝ์šฐ ๊ณต๊ฐœ ํ‚ค๋Š” 32๋ฐ”์ดํŠธ์ž…๋‹ˆ๋‹ค. Ed448์˜ ๊ฒฝ์šฐ ๊ณต๊ฐœ ํ‚ค๋Š” 57๋ฐ”์ดํŠธ์ž…๋‹ˆ๋‹ค.

EdDSA ์„œ๋ช…

EdDSA ์„œ๋ช… ์•Œ๊ณ ๋ฆฌ์ฆ˜()์€ ๋ฌธ์ž ๋ฉ”์‹œ์ง€ msg + ์„œ๋ช…์ž์˜ EdDSA ๊ฐœ์ธ ํ‚ค privKey๋ฅผ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›์•„ ์ •์ˆ˜ ์Œ {R, s}๋ฅผ ์ถœ๋ ฅ์œผ๋กœ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค. EdDSA ์„œ๋ช…์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ž‘๋™ํ•ฉ๋‹ˆ๋‹ค(์•ฝ๊ฐ„ ๋‹จ์ˆœํ™”๋จ).

EdDSA_sign(msg, privKey) --> { R, s }

  1. Calculate pubKey = privKey * G
  2. ๊ฒฐ์ •๋ก ์ ์œผ๋กœ ๋น„๋ฐ€ ์ •์ˆ˜ r = hash(hash(privKey) + msg) mod q๋ฅผ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค(์•ฝ๊ฐ„ ๋‹จ์ˆœํ™”๋จ).
  3. ๊ณก์„  ์ƒ์„ฑ๊ธฐ๋ฅผ ๊ณฑํ•˜์—ฌ r ๋’ค์— ์žˆ๋Š” ๊ณต๊ฐœ ํ‚ค ํฌ์ธํŠธ๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. R = r * G
  4. Calculate h = hash(R + pubKey + msg) mod q
  5. Calculate s = (r + h * privKey) mod q
  6. ์„œ๋ช… ๋ฆฌํ„ด { R, s }

์ƒ์„ฑ๋œ ๋””์ง€ํ„ธ ์„œ๋ช…์€ Ed25519์˜ ๊ฒฝ์šฐ 64๋ฐ”์ดํŠธ(32 + 32๋ฐ”์ดํŠธ), Ed448์˜ ๊ฒฝ์šฐ 114๋ฐ”์ดํŠธ(57 + 57๋ฐ”์ดํŠธ)์ž…๋‹ˆ๋‹ค.
์••์ถ•๋œ ์ง€์  R + ์ •์ˆ˜ s๋ฅผ ๋ณด์œ ํ•ฉ๋‹ˆ๋‹ค(์„œ๋ช…์ž๊ฐ€ msg ๋ฐ privKey๋ฅผ ์•Œ๊ณ  ์žˆ์Œ์„ ํ™•์ธ).

EdDSA ์„œ๋ช… ๊ฒ€์ฆ

EdDSA ์„œ๋ช… ํ™•์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜()์€ ํ…์ŠคํŠธ ๋ฉ”์‹œ์ง€ msg + ์„œ๋ช…์ž์˜ EdDSA ๊ณต๊ฐœ ํ‚ค pubKey + EdDSA ์„œ๋ช… {R, s}๋ฅผ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›์•„
boolean ๊ฐ’(์œ ํšจ ๋˜๋Š” ๋ฌดํšจ ์„œ๋ช…)์„ ์ถœ๋ ฅ์œผ๋กœ ์ƒ์„ฑํ•ฉ๋‹ˆ๋‹ค.
EdDSA ํ™•์ธ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ž‘๋™ํ•ฉ๋‹ˆ๋‹ค(์•ฝ๊ฐ„ ๋‹จ์ˆœํ™”๋จ).

EdDSA_signature_verify(msg, pubKey, signature { R, s } ) --> ์œ ํšจ/๋ฌดํšจ

  1. Calculate h = hash(R + pubKey + msg) mod q
  2. Calculate P1 = s * G
  3. Calculate P2 = R + h * pubKey
  4. Return P1 == P2

How Does it Work?

ํ™•์ธํ•˜๋Š” ๋™์•ˆ ์  P1์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ณ„์‚ฐ๋ฉ๋‹ˆ๋‹ค. P1 = s * G.
์„œ๋ช…ํ•˜๋Š” ๋™์•ˆ s = (r + h * privKey) mod q. ์ด์ œ ์œ„ ๋ฐฉ์ •์‹์—์„œ s๋ฅผ ๋ฐ”๊ฟ‰๋‹ˆ๋‹ค.

  • P1 = s * G = (r + h * privKey) mod q * G = r * G + h * privKey * G = R + h * pubKey

์œ„๋Š” ์ •ํ™•ํžˆ ๋‹ค๋ฅธ ์  P2์ž…๋‹ˆ๋‹ค.
P1๊ณผ P2 ํฌ์ธํŠธ๊ฐ€ ๋™์ผํ•œ EC ํฌ์ธํŠธ๋ผ๋ฉด ๊ฐœ์ธ ํ‚ค๋กœ ๊ณ„์‚ฐํ•œ P1 ํฌ์ธํŠธ์™€
ํ•ด๋‹น ๊ณต๊ฐœ ํ‚ค๋กœ ์ƒ์„ฑํ•œ ํฌ์ธํŠธ P2๊ฐ€ ์ผ์น˜ํ•จ์„ ์ฆ๋ช…ํ•ฉ๋‹ˆ๋‹ค.

ECDSA ๋Œ€ EdDSA

EdDSA์˜ ์„œ๋ช… ๋ฐ ๊ฒ€์ฆ์„ ๋น„๊ตํ•˜๋ฉด EdDSA๊ฐ€ ECDSA๋ณด๋‹ค ๊ฐ„๋‹จํ•˜๊ณ  ์ดํ•ดํ•˜๊ณ  ๊ตฌํ˜„ํ•˜๊ธฐ ์‰ฝ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
๋‘ ์„œ๋ช… ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ‚ค ๊ธธ์ด๊ฐ€ ๋น„์Šทํ•œ ๊ณก์„ ์— ๋Œ€ํ•ด ์œ ์‚ฌํ•œ ๋ณด์•ˆ ๊ฐ•๋„๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.
๊ฐ€์žฅ ์ธ๊ธฐ ์žˆ๋Š” ๊ณก์„ (์˜ˆ: edwards25519 ๋ฐ edwards448)์˜ ๊ฒฝ์šฐ
EdDSA ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ECDSA๋ณด๋‹ค ์•ฝ๊ฐ„ ๋น ๋ฅด์ง€๋งŒ ์‚ฌ์šฉ๋œ ๊ณก์„ ๊ณผ ํŠน์ • ๊ตฌํ˜„์— ๋”ฐ๋ผ ํฌ๊ฒŒ ๋‹ฌ๋ผ์ง‘๋‹ˆ๋‹ค.
ECDSA์™€ ๋‹ฌ๋ฆฌ EdDSA ์„œ๋ช…์€ ์„œ๋ช… ๋ฐ ๋ฉ”์‹œ์ง€์—์„œ ์„œ๋ช…์ž์˜ ๊ณต๊ฐœ ํ‚ค๋ฅผ ๋ณต๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์ œ๊ณตํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
์ผ๋ฐ˜์ ์œผ๋กœ EdDSA๋Š” ๋Œ€๋ถ€๋ถ„์˜ ์ตœ์‹  ์•ฑ์— ๊ถŒ์žฅ๋˜๋Š” ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผ๋ฉ๋‹ˆ๋‹ค.

๋งˆ๋ฌด๋ฆฌ

EdDSA ๊ฒฝ์šฐ ๋น„๊ต์  ์ˆ˜ํ•™์ ์œผ๋กœ ๋‹จ์ˆœํ•˜๊ณ  ํšจ์œจ์ ์ด๋ผ๊ณ  ํ•œ๋‹ค.
์ฐธ๊ณ ๋กœ ์ผ๋ฐ˜์ ์œผ๋กœ ์ „์ž์„œ๋ช…์—์„œ ํ•ด์‰ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์„ ํƒ ํ•˜๋Š”๋ฐ ํ•ด์‰ฌ ์„ ํƒ๋„ ์—†๋‹ค.
Ed25519 ๊ฒฝ์šฐ SHA-512 ๊ณ ์ •์ด๊ตฌ Ed448 ๊ฒฝ์šฐ๋Š” SHAKE-256 ๊ณ ์ • ํ•ด์‹œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ๋‹ค.
ํ‚ค ๊ธธ์ด๊ฐ€ ECDSA ๋งŒํผ ์งง์€ ๊ธธ์ด๋ฅผ ๊ฐ€์ง€๊ณ  ํšจ์œจ์ ์ด๋ผ๊ณ  ํ•˜๋‹ˆ ์ข‹์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ ์ƒ๊ฐํ•œ๋‹ค.

์‚ฌ์‹ค ์•„์ง EdDSA ๋ฅผ ์‹ค์ œ๋กœ ์‚ฌ์šฉํ•˜๋Š”๊ฒƒ์„ ๋งŒ๋‚˜์ง€๋Š” ๋ชปํ–ˆ๋‹ค.
ํ•˜์ง€๋งŒ CertMan ๊ณผ BerEditor ์—์„œ OpenSSL ์„ ์ด์šฉํ•ด ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ์ง€์› ํ•  ๊ณ„ํš์ด๋ผ(์—ญ์‹œ OpenSSL)
๊ด€๋ จ ๋‚ด์šฉ์„ ๋ฒˆ์—ญํ•ด์„œ ์ •๋ฆฌํ•ด ๋ณด์•˜๋‹ค.
๋ฒˆ์—ญ์ด์ง€ ๋‚ด๊ฐ€ ์™„์ „ํžˆ ์ดํ•ด ํ•œ๊ฑด ์•„๋‹ˆ๋‹ค ( ์ˆ˜ํ•™ ์–ด๋ ค์›Œ T.T )

์ฐธ๊ณ 

์•„๋ž˜ ๋งํฌ๋Š” ๊ฐœ๋ฐœ์‹œ ์ฐธ์กฐ ํ• ๋ ค๊ตฌ ๊ฑธ์–ด ๋‘ 

OpenSSL Man Ed25519
OpenSSL Man Ed448
EdDSA:Sign/Verify - Examples