Easy to understand
너의과학/기타

EdDSA: Ed25519 and Ed448][1. Introduction]

·16 min read

1. Introduction

The Edwards-curve Digital Signature Algorithm (EdDSA) is a varient of Schnorr's signature system with (possibly twisted) Edwards curves.

  • EdDSA는 (possibly twisted) Edwards curves를 사용하는 Schnorr's signature의 변형된 형태이다.

EdDSA needs to be instantiated with certain parameters, and this document describes some recommended variants.

  • ??EdDSA는 특정 파라메타로 instant화할 필요가 있고??, 이 문서는 몇몇 추천하는 variants들을 설명한다.

 

To facilitate adoption of EdDSA in the Internet community, this documnet describes the signature scheme in an implementataion-oriented way and provides sample code and test vectors.

  • 인터넷 커뮤니티에서 EdDSA의 채택을 촉진하기 위해서, 이 문서는 구현-지향 방식으로 signature scheme(체계)을 설명하고 샘플 코드와 테스트 벡터를 제공한다.

 

The advantages with EdDSA are as follows:

  • 장점은 아래와 같다:
  1. EdDSA provides high performce on variety of platforms;
    1. EdDSA는 다양한 platforms에서 고성능을 제공한다;
  1. The use of a unique random number for each signature is not required;
  • 각 signature마다 unique random number의 사용이 요구되지 않는다;
  1. It is more resilient to side-channel attacks;
  • side-channel 공격에 더 많은 탄력성을 가진다;
  1. EdDSA uses small public keys (32 or 57 bytes) and signatures (64 or 114 bytes) for Ed25519 and Ed448, respectively;
  • EdDSA는 Ed25519의 경우 32bytes의 public keys, 64bytes의 signatures를 그리고 Ed448의 경우 57bytes의 public keys와 114bytes의 signatures를 각각 사용한다.
  1. The formulas are "complete", i.e., they are valid for all points on the curve, with on exceptions.
  • 공식은 "완전"하고, 즉,예외 없이, curve 상 모든 points들은 유효합니다.

This obviates the need for EdDSA to perform expensive point validation on untrusted public values;

  • 이는 EdDSA가 신뢰할 수 없는 public values에 대해 비용이 많이 드는 포인트 검증을 수행할 필요성을 제거합니다.
  1. EdDSA provides collision resilience, meaning that hash-function collisions do not break this system (only holds fro PureEdDSA).
  • EdDSA는 충돌 복원력을 제공합니다, 즉, 해시 함수 충돌이 이 시스템을 손상시키지 않습니다(PureEdDSA에서만 유지됨).

 

The original EdDSA paper and the generalized version described in "EdDSA for more curves" provide further background.

  • 원본 EdDSA 논문[EDDSA]과 "EdDSA for more curves"[EDDSA2]에 설명된 일반 버전은 추가 배경 정보를 제공합니다.

RFC 7748 discusses specific curves, including Curve25519 and Ed448-Goldilocks.

  • RFC 7748에서는 Curve25519 및 Ed448-Goldilocks를 포함한 특정 곡선에 대해 설명합니다.

 

Ed25519 is intended to operate at around the 128-bit security level and Ed448 at around the 224-bit security level.

  • Ed25519는 약 128비트 보안 수준에서 작동하고 Ed448은 약 224비트 보안 수준에서 작동하도록 설계되었습니다.

A sufficiently large quantum computer would be able to break both.

  • 충분히 큰 양자 컴퓨터는 두 가지를 모두 깨뜨릴 수 있습니다.

Reasonable projections of the abilities of classical computers conclude that Ed25519 is perfectly safe.

  • classical 컴퓨터의 능력에 대한 합리적인 예측은 Ed25519가 완벽하게 안전하다는 결론을 내립니다.

Ed448 is provided for those applications with relaxed performance requirements and where there is a desire to hedge against analytical attacks on elliptic curves.

  • Ed448은 성능 요구 사항이 완화되고 타원 곡선에 대한 분석 공격을 방지하려는 애플리케이션에 제공됩니다.

2. Notation and Conventions

The following notation is used throughout the document:

  • 문서 전체에서 다음 표기법이 사용됩니다.

p : Denotes the prime number defining the underlying field

  • p : 기본 필드를 정의하는 소수를 나타냅니다.

GF(p) : Finite field with p elements

  • GF(p) : p개 요소가 있는 유한체

3. EdDSA Algorithm

EdDSA is a digital signature system with 11 parameters.

  • EdDSA는 11개의 매개변수를 갖춘 디지털 서명 시스템입니다.

 

The generic EdDSA digital signature system with its 11 input parameters is not intended to be implemented directly.

  • 11개의 입력 매개변수가 있는 일반 EdDSA 디지털 서명 시스템은 직접 구현하기 위한 것이 아닙니다.

Choosing parameters is critical for secure and efficient operation.

  • 안전하고 효율적인 운영을 위해서는 매개변수를 선택하는 것이 중요합니다. Instead, you would implement a particular parameter choice for EdDSA (such as Ed25519 or Ed448), sometimes slightly generalized to achieve code reuse to cover Ed25519 and Ed448.

  • 대신, (Ed25519 또는 Ed448과 같은) EdDSA에 대한 특정 매개변수 선택을 구현하며, 때로는 Ed25519 및 Ed448을 포괄하는 코드 재사용을 달성하기 위해 약간 일반화됩니다.

 

Therefore, a precise explanation of the generic EdDSA is thus not particularly useful for implementers.

  • 따라서, 일반 EdDSA에 대한 정확한 설명은 구현자에게 특히 유용하지 않습니다.

For background and completeness, a succinct description of the generic EdDSA algorithm is given here.

  • 배경 및 완전성을 위해, 일반 EdDSA 알고리즘에 대한 간결한 설명이 여기에 제공됩니다.

 

The definition of some parameters, such as 'n' and 'c', may help to explain some steps of the algorithm that are not intuitive.

  • 'n' 및 'c'와 같은, 일부 매개변수의 정의는 직관적이지 않은 알고리즘의 일부 단계를 설명하는 데 도움이 될 수 있습니다.

 

This description closely follows [EDDSA2].

  • 이 설명은 [EDDSA2]를 밀접하게 따릅니다.

 

EdDSA has 11 parameters:

  • EdDSA에는 11개의 매개변수가 있습니다.

1. An odd prime power p.  EdDSA uses an elliptic curve over the finite field GF(p).

  • 1. 홀수 소수 p. EdDSA는 유한 필드 GF(p)에 대해 타원 곡선을 사용합니다.
  1. An integer b with 2^(b-1) > p.
  • 2^(b-1) > p인 정수 b.

EdDSA public keys have exactly b bits, and EdDSA signatures have exactly 2*b bits.

  • EdDSA 공개 키는 정확히 b 비트를 가지며 EdDSA 서명은 정확히 2*b 비트를 갖습니다.

b is recommended to be a multiple of 8, so public key and signature lengths are an integral number of octets.

  • b는 8의 배수를 권장하므로 공개 키와 서명 길이는 정수 옥텟(=8bits) 수입니다.
  1. A (b-1)-bit encoding of elements of the finite field GF(p).
  • 유한 필드 GF(p)의 요소에 대한 (b-1) 비트 인코딩.
  1. A cryptographic hash function H producing 2*b-bit output.

  • 2*b비트 출력을 생성하는 암호화 해시 함수 H. Conservative hash functions (i.e., hash functions where it is infeasible to create collisions) are recommended and do not have much impact on the total cost of EdDSA.

  • 보수적인 해시 함수(즉, 충돌 생성이 불가능한 해시 함수)가 권장되며 EdDSA의 총 비용에 큰 영향을 미치지 않습니다.

  1. An integer c that is 2 or 3.
  • 2 또는 3인 정수 c입니다.

Secret EdDSA scalars are multiples of 2^c.

  • 비밀 EdDSA 스칼라는 2^c의 배수입니다.

The integer c is the base-2 logarithm of the so-called cofactor.

  • 정수 c는 소위 보조 인자(cofactor)의 밑이 2인 로그입니다.
  1. An integer n with c <= n < b.

  • c <= n < b인 정수 n. Secret EdDSA scalars have exactly n + 1 bits, with the top bit (the 2^n position) always set and the bottom c bits always cleared.

  • 비밀 EdDSA 스칼라에는 정확히 n + 1 비트가 있으며, 상위 비트(2^n 위치)는 항상 설정되고 하위 c 비트는 항상 지워집니다.

  1. A non-square element d of GF(p).

  • GF(p)의 정사각형이 아닌 요소 d. The usual recommendation is to take it as the value nearest to zero that gives an acceptable curve.

  • 일반적인 권장 사항은 허용 가능한 곡선을 제공하는 0에 가장 가까운 값을 사용하는 것입니다.

  1. A non-zero square element a of GF(p).

  • GF(p)의 0이 아닌 정사각형 요소 a. The usual recommendation for best performance is a = -1 if p mod 4 = 1, and a = 1 if p mod 4 = 3.

  • 최상의 성능을 위한 일반적인 권장 사항은 p mod 4 = 1이면 a = -1이고, p mod 4 = 3이면 a = 1입니다.

  1. An element B != (0,1) of the set E = { (x,y) is a member of GF(p) x GF(p) such that a * x^2 + y^2 = 1 + d * x^2 * y^2 }.
  • 집합 E = { (x,y)의 요소 B != (0,1)은 a * x^2 + y^2 = 1 + d *가 되는 GF(p) x GF(p)의 멤버입니다. x^2 * y^2 }.
  1. An odd prime L such that [L]B = 0 and 2^c * L = #E.

  • [L]B = 0이고 2^c * L = #E인 홀수 소수 L입니다. The number #E (the number of points on the curve) is part of the standard data provided for an elliptic curve E, or it can be computed as cofactor * order.

  • 숫자 #E(곡선의 점 수)는 타원 곡선 E에 대해 제공되는 표준 데이터의 일부이거나 보조인자 * 순서로 계산될 수 있습니다.

  1. A "prehash" function PH.

  • "프리해시" 함수 PH. PureEdDSA means EdDSA where PH is the identity function, i.e., PH(M) = M.

  • PureEdDSA는 PH가 항등함수인 EdDSA를 의미합니다. 즉, PH(M) = M입니다. HashEdDSA means EdDSA where PH generates a short output, no matter how long the message is;

  • HashEdDSA는 메시지 길이에 관계없이 PH가 짧은 출력을 생성하는 EdDSA를 의미합니다.

for example, PH(M) = SHA-512(M).

  • 예를 들어 PH(M) = SHA-512(M)입니다.

Points on the curve form a group under addition, (x3, y3) = (x1, y1) + (x2, y2), with the formulas

  • 곡선의 점은 다음 공식을 사용하여 덧셈((x3, y3) = (x1, y1) + (x2, y2)) 아래 그룹을 형성합니다.

                   x1 * y2 + x2 * y1                             y1 * y2 - a * x1 * x2    x3 = --------------------------,   y3 = ---------------------------              1 + d * x1 * x2 * y1 * y2                     1 - d * x1 * x2 * y1 * y2

The neutral element in the group is (0,1).

  • 그룹의 중립 요소는 (0,1)입니다.

 

Unlike many other curves used for cryptographic applications, these formulas are "complete"; they are valid for all points on the curve, with no exceptions.

  • 암호화 애플리케이션에 사용되는 다른 많은 곡선과 달리 이러한 공식은 "완전"합니다. 이는 예외 없이 곡선의 모든 점에 유효합니다. In particular, the denominators are non-zero for all input points.

  • 특히, 모든 입력 포인트에 대해 분모는 0이 아닙니다.

 

There are more efficient formulas, which are still complete, that use homogeneous coordinates to avoid the expensive modulo p inversions.

  • 비용이 많이 드는 모듈로 p 반전을 피하기 위해 동종 좌표를 사용하는 더 효율적인 공식이 있으며 여전히 완전합니다. See [Faster-ECC] and [Edwards-revisited].

  • [Faster-ECC] 및 [Edwards-revisited]를 참조하세요.

 

3.1. Encoding

An integer 0 < S < L - 1 is encoded in little-endian form as a b-bit string ENC(S).

  • 정수 0 < S < L - 1은 리틀 엔디안 형식으로 b비트 문자열 ENC(S)로 인코딩됩니다.

 

An element (x,y) of E is encoded as a b-bit string called ENC(x,y), which is the (b-1)-bit encoding of y concatenated with one bit that is 1 if x is negative and 0 if x is not negative.

  • E의 요소 (x,y)는 ENC(x,y)라는 b비트 문자열로 인코딩됩니다. 이는 x가 음수이고 x가 음수가 아니면 0입니다.

 

The encoding of GF(p) is used to define "negative" elements of GF(p): specifically, x is negative if the (b-1)-bit encoding of x is lexicographically larger than the (b-1)-bit encoding of -x.

  • GF(p)의 인코딩은 GF(p)의 "음수" 요소를 정의하는 데 사용됩니다. 특히 x의 (b-1) 비트 인코딩이 (b-1) 비트보다 사전순으로 큰 경우 x는 음수입니다. -x 인코딩.

 

3.2. Keys

An EdDSA private key is a b-bit string k.

  • EdDSA 개인 키는 b비트 문자열 k입니다. Let the hash H(k) = (h_0, h_1, ..., h_(2b-1)) determine an integer s, which is 2^n plus the sum of m = 2^i * h_i for all integer i, c <= i < n.

  • 해시 H(k) = (h_0, h_1, ..., h_(2b-1))이 정수 s를 결정한다고 가정합니다. 이는 2^n에 모든 정수 i에 대한 m = 2^i * h_i의 합을 더한 것입니다. c <= i < n.

Let's determine the multiple A = [s]B.

  • 배수 A = [s]B를 결정해 봅시다. The EdDSA public key is ENC(A).

  • EdDSA 공개 키는 ENC(A)입니다. The bits h_b, ..., h_(2b-1) are used below during signing.

  • h_b, ..., h_(2b-1) 비트는 서명 중에 아래에서 사용됩니다.

 

3.3. Sign

The EdDSA signature of a message M under a private key k is defined as the PureEdDSA signature of PH(M).

  • 개인 키 k 아래에 있는 메시지 M의 EdDSA 서명은 PH(M)의 PureEdDSA 서명으로 정의됩니다.

In other words, EdDSA simply uses PureEdDSA to sign PH(M).

  • 즉, EdDSA는 단순히 PureEdDSA를 사용하여 PH(M)에 서명합니다.

 

The PureEdDSA signature of a message M under a private key k is the 2*b-bit string ENC(R) || ENC(S).

  • 개인 키 k 아래에 있는 메시지 M의 PureEdDSA 서명은 2*b 비트 문자열 ENC(R) || ENC(들).

R and S are derived as follows.

  • R과 S는 다음과 같이 도출됩니다. First define r = H(h_b || ... || h_(2b-1) || M) interpreting 2b-bit strings in little-endian form as integers in {0, 1, ..., 2^(2b) - 1}.

  • 먼저 리틀 엔디안 형식의 2b 비트 문자열을 {0, 1, ..., 2^의 정수로 해석하는 r = H(h_b || ... || h_(2b-1) || M)을 정의합니다. (2b) - 1}. Let R = [r]B and S = (r + H(ENC(R) || ENC(A) || PH(M)) * s) mod L.

  • R = [r]B 및 S = (r + H(ENC(R) || ENC(A) || PH(M)) * s) mod L로 설정합니다. The s used here is from the previous section.

  • 여기에 사용된 s는 이전 섹션에서 가져온 것입니다.

 

3.4. Verify

To verify a PureEdDSA signature ENC(R) || ENC(S) on a message M under a public key ENC(A), proceed as follows.

  • PureEdDSA 서명을 확인하려면 ENC(R) || 공개 키 ENC(A) 아래 메시지 M에 대한 ENC(S)는 다음과 같이 진행됩니다. Parse the inputs so that A and R are elements of E, and S is a member of the set {0, 1, ..., L-1}.

  • A와 R이 E의 요소이고 S가 집합 {0, 1, ..., L-1}의 구성원이 되도록 입력을 구문 분석합니다. Compute h = H(ENC(R) || ENC(A) || M), and check the group equation [2^c * S] B = 2^c * R + [2^c * h] A in E.

  • h = H(ENC(R) || ENC(A) || M)을 계산하고 E에서 그룹 방정식 [2^c * S] B = 2^c * R + [2^c * h] A를 확인합니다. . The signature is rejected if parsing fails (including S being out of range) or if the group equation does not hold.

  • 구문 분석이 실패하거나(S가 범위를 벗어난 경우 포함) 그룹 방정식이 유지되지 않는 경우 서명이 거부됩니다.

 

EdDSA verification for a message M is defined as PureEdDSA verification for PH(M).

  • 메시지 M에 대한 EdDSA 확인은 PH(M)에 대한 PureEdDSA 확인으로 정의됩니다.

 

 

  1. PureEdDSA, HashEdDSA, and Naming

 

https://datatracker.ietf.org/doc/html/rfc8032#page-3