EdDSA 알고리즘 Ed25519 과 Ed448에 관하여

이 글은 [출처] 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 경우 비교적 수학적으로 단순하고 효율적이라고 한다.
참고로 일반적으로 전자서명에서 해쉬 알고리즘을 선택 하는데 해쉬 선택도 없다.
단지 원문을 해쉬한 값을 입력 메세지로 이용해야 한다(확인이 필요함)
키 길이가 ECDSA 만큼 짧은 길이를 가지고 효율적이라고 하니 좋은 알고리즘이라 생각한다.

사실 아직 EdDSA 를 실제로 사용하는것을 만나지는 못했다.
하지만 CertMan 과 BerEditor 에서 OpenSSL 을 이용해 이 알고리즘도 지원 할 계획이라(역시 OpenSSL)
관련 내용을 번역해서 정리해 보았다.
번역이지 내가 완전히 이해 한건 아니다 ( 수학 어려워 T.T )

참고

아래 링크는 개발시 참조 할려구 걸어 둠

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