< draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-02.txt | draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-03.txt > | |||
---|---|---|---|---|

Internet-Draft D. Brown | Internet-Draft D. Brown | |||

Intended status: Experimental BlackBerry | Intended status: Experimental BlackBerry | |||

Expires: 2019-04-07 2018-10-04 | Expires: 2019-10-06 2019-04-04 | |||

Elliptic curve 2y^2=x^3+x over field size 8^91+5 | Elliptic curve 2y^2=x^3+x over field size 8^91+5 | |||

<draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-02.txt> | <draft-brown-ec-2y2-x3-x-mod-8-to-91-plus-5-03.txt> | |||

Abstract | Abstract | |||

This document specifies a special elliptic curve with a compact | This document recommends using a special elliptic curve alongside | |||

description (see title) and an efficient endormorphism (complex | dissimilar curves, such as NIST P-256, Curve25519, sect283k1, | |||

multiplication by i). This curve is only recommended for | Brainpool, and random curves, as a cryptographic defense against an | |||

cryptographic use in a strongest-link combination with dissimilar | unlikely, undisclosed attack against mainstream curves. Features of | |||

elliptic curves (e.g. NIST P-256, Curve25519, extension-field | this curve 2y^2=x^3+x/GF(8^91+5) are: isomorphism to Miller curves | |||

curves, etc.). Used in this manner, the curve special features | from 1985; Montgomery form mappable to Edwards; simple field | |||

serve as a defense in depth against an unlikely event: a new or | powering for inversion, Legendre symbol, and square roots; efficient | |||

secret attack against the other types of elliptic curves. | endomorphism to speed up Diffie--Hellman with Bernstein's 2-D | |||

ladder; 34-byte keys; similarity to Bitcoin curve; hashing-to-point; | ||||

low Kolmogorov complexity (low risk of backdoor). | ||||

Status of This Memo | Status of This Memo | |||

This Internet-Draft is submitted in full conformance with the | This Internet-Draft is submitted in full conformance with the | |||

provisions of BCP 78 and BCP 79. Internet-Drafts are working | provisions of BCP 78 and BCP 79. Internet-Drafts are working | |||

documents of the Internet Engineering Task Force (IETF). Note that | documents of the Internet Engineering Task Force (IETF). Note that | |||

other groups may also distribute working documents as | other groups may also distribute working documents as | |||

Internet-Drafts. The list of current Internet-Drafts is at | Internet-Drafts. The list of current Internet-Drafts is at | |||

http://datatracker.ietf.org/drafts/current. | http://datatracker.ietf.org/drafts/current. | |||

Internet-Drafts are draft documents valid for a maximum of six | Internet-Drafts are draft documents valid for a maximum of six | |||

months and may be updated, replaced, or obsoleted by other documents | months and may be updated, replaced, or obsoleted by other documents | |||

at any time. It is inappropriate to use Internet-Drafts as | at any time. It is inappropriate to use Internet-Drafts as | |||

reference material or to cite them other than as "work in progress." | reference material or to cite them other than as "work in progress." | |||

Copyright Notice | Copyright Notice | |||

Copyright (c) 2018 IETF Trust and the persons identified as the | Copyright (c) 2019 IETF Trust and the persons identified as the | |||

document authors. All rights reserved. | document authors. All rights reserved. | |||

This document is subject to BCP 78 and the IETF Trust's Legal | This document is subject to BCP 78 and the IETF Trust's Legal | |||

Provisions Relating to IETF Documents | Provisions Relating to IETF Documents | |||

(http://trustee.ietf.org/license-info) in effect on the date of | (http://trustee.ietf.org/license-info) in effect on the date of | |||

publication of this document. Please review these documents | publication of this document. Please review these documents | |||

carefully, as they describe your rights and restrictions with | carefully, as they describe your rights and restrictions with | |||

respect to this document. | respect to this document. | |||

Internet-Draft 2019-04-04 | ||||

This document may not be modified, and derivative works of it may | This document may not be modified, and derivative works of it may | |||

not be created, except to format it for publication as an RFC or to | not be created, except to format it for publication as an RFC or to | |||

translate it into languages other than English. | translate it into languages other than English. | |||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

Table of Contents | Table of Contents | |||

1. Introduction | 1. Introduction | |||

1.1. Background | 1.1. Background | |||

1.2. Motivation | 1.1.1. Notation | |||

2. Requirements Language (RFC 2119) | 1.2. Motivation | |||

3. Encoding a point into 34 bytes | 2. Requirements Language (RFC 2119) | |||

3.1. Encoding a point into bytes | 3. Encoding a point into 34 bytes | |||

3.2. Decoding bytes into a point | 3.1. Encoding a point into bytes | |||

4. Point validation | 3.2. Decoding bytes into a point | |||

4.1. When a point MUST be validated | 4. Point validation | |||

4.2. How to validate a point (given only x) | 4.1. When a public key MAY, SHOULD or MUST be validated | |||

5. OPTIONAL encodings | 4.1.1. Precautionary mandatory validation | |||

5.1. Encoding scalar multipliers as 34 bytes | 4.1.2. Simplified validation | |||

5.2. Encoding 34 bytes into a point (sketch) | 4.1.3. Relatively safe cases of non-validation | |||

6. Cryptographic schemes | 4.1.4. Minimal validation | |||

6.1. Diffie--Hellman key agreement | 4.2. How to validate a point (given only x) | |||

6.2. Signatures | 5. OPTIONAL encodings | |||

6.3 Menezes--Qu--Vanstone key agreement | 5.1. Encoding scalar multipliers as 34 bytes | |||

7. IANA Considerations | 5.2. Encoding 34 bytes into a point (sketch) | |||

8. Security considerations | 6. IANA Considerations | |||

8.1. Field choice | 7. Security considerations | |||

8.2. Curve choice | 7.1. Field choice | |||

8.3. Encoding choices | 7.2. Curve choice | |||

8.4. General subversion concerns | 7.3. Encoding choices | |||

9. References | 7.4. General subversion concerns | |||

9.1. Normative References | 7.5. Concerns about 'aegis' | |||

9.2. Informative References | 8. References | |||

Appendix A. Test vectors | 8.1. Normative References | |||

Appendix B. Motivation: minimizing the room for backdoors | 8.2. Informative References | |||

Appendix C. Pseudocode | Appendix A. Test vectors | |||

C.1. Byte encoding | Appendix B. Motivation: minimizing the room for backdoors | |||

C.2. Byte decoding | Appendix C. Pseudocode | |||

C.3. Fermat inversion | C.1. Byte encoding | |||

C.4. Branchless Legendre symbol computation | C.2. Byte decoding | |||

C.5. Field multiplication and squaring | C.3. Fermat inversion | |||

C.6. Field element partial reduction | C.4. Branchless Legendre symbol computation | |||

C.7. Field element final reduction | C.5. Field multiplication and squaring | |||

C.8. Scalar point multiplication | C.6. Field element partial reduction | |||

C.9. Diffie--Hellman pseudocode | C.7. Field element final reduction | |||

C.10. Elligator i | C.8. Scalar point multiplication | |||

Appendix D. Primality proofs and certificates | C.9. Diffie--Hellman pseudocode | |||

D.1 Pratt certificate for the field size 8^91+5 | C.10. Elligator i | |||

D.2 Pratt certificate for size of the large elliptic curve subgroup | D. Primality proofs and certificates | |||

D.1. Pratt certificate for the field size 8^91+5 | ||||

D.2. Pratt certificate for subgroup order | ||||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

1. Introduction | 1. Introduction | |||

This document specifies some conventions for using the elliptic | This document relates to elliptic curve cryptography (ECC). It | |||

curve 2y^2=x^3+x over the field of size 8^91+5 in cryptography. | specifies methods for using the elliptic curve 2y^2=x^3+x over the | |||

field of size 8^91+5. It recommends using this curve in combination | ||||

This draft focuses on applications to Diffie--Hellman exchange. | with a diverse set of curves, as a strongest-link multi-layer | |||

defense-in-depth against undisclosed attacks against some subset of | ||||

curves. | ||||

1.1. Background | 1.1. Background | |||

This document presumes that its reader already has familiarity with | This document presumes that its reader already has familiarity with | |||

elliptic curve cryptography. | elliptic curve cryptography (ECC). | |||

1.1.1. Notation | ||||

The symbol '^', as used in '2y^2=x^3+x' and '8^91+5' means | The symbol '^', as used in '2y^2=x^3+x' and '8^91+5' means | |||

exponentiation, also known as powering. In particular, it does not | exponentiation, also known as powering. For example, y^3=yyy, or | |||

mean bit-wise exclusive-or (as in the C programming language | y*y*y, if * is used for multiplication, and 8^91 = 8*8*...*8, with | |||

operator). For example, y^3=yyy (or y*y*y, if * is used for | 91 eights in the product on the right. | |||

multiplication.) | ||||

In particular, p=8^91+5 is a (positive) prime number. Its encoding | Note: This document does not use '^' the way that C (and similar | |||

into bytes, using little-endian ordering (least significant bytes | programming languages) use it as bit-wise exclusive-or. | |||

first), requires 35 bytes, and has the form {5,0,0,...,2}, with the | ||||

first byte equal to 5, the last 2, and the 33 intermediate bytes are | In hexadecimal (base 16, big-endian) notation, the number 8^91+5 is | |||

each 0. A byte encoding of p is not needed for this document, and | ||||

is only shown here for illustrative purposes. Its hexadecimal | 200000000000000000000000000000000000000000000000000000000000000000005 | |||

representation (i.e. big-endian, base 16), is 20...05, with 67 zeros | ||||

between 2 and 5. | with with 67 zeros between 2 and 5. | |||

1.2. Motivation | 1.2. Motivation | |||

The motivations for curve 2y^2=x^3+x over field 8^91+5 are discussed | The main motivation is that the description of the curve is very | |||

in Appendix B (and in [B1]). | short (for an otherwise secure elliptic curve), thereby reducing the | |||

room for a secretly embedded trapdoor, as in [Teske]. | ||||

In short, the main motivation is that the description of the curve | The best countermeasure against a secretly embedded trapdoor in an | |||

is very short (for an elliptic curve), thereby reducing the room for | elliptic curve is to use a diverse combination of elliptic curves. | |||

a secretly embedded trapdoor, as in [Teske]. | So, this curve is only recommended for use in such a combination. | |||

The detailed motivations for curve 2y^2=x^3+x over field 8^91+5 are | ||||

discussed in Appendix B (and in [B1]). | ||||

Internet-Draft 2019-04-04 | ||||

2. Requirements Language (RFC 2119) | 2. Requirements Language (RFC 2119) | |||

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||

"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | |||

document are to be interpreted as described in RFC 2119 [BCP14]. | document are to be interpreted as described in RFC 2119 [BCP14]. | |||

Internet-Draft 2018-10-04 | ||||

3. Encoding a point into 34 bytes | 3. Encoding a point into 34 bytes | |||

Elliptic curve cryptography uses points for public keys and raw | Elliptic curve cryptography uses points for public keys and raw | |||

shared secrets. A point can be defined as either pair (x,y), where | shared secrets. | |||

x and y are field elements, or a special point O located at | ||||

infinity. Field elements for this curve are integers modulo 8^91+5. | ||||

Note: for practicality, an implementation will usually represent | Abstractly, points are mathematical objects. For curve 2y^2=x^3+x, | |||

the x-coordinate as a ratio (X:Z) of field elements. This | a point is either a pair (x,y), where x and y are elements of | |||

specification ignores that detail, assuming x has been normalized | mathematical field, or a special point O, both of whose coordinates | |||

to (x:1). | may be deemed as infinity. | |||

For 2y^2=x^3+x, the coordinates are x and y are field elements for | ||||

this curve are integers modulo 8^91+5. | ||||

Note: for practicality, an implementation will often represented | ||||

the x-coordinate as a ratio [X:Z] of field elements. Each field | ||||

element has multiple representations, but [x:1] can viewed as | ||||

normal representation of x. (Infinity can be then represented by | ||||

[1:0], though one must be careful.) | ||||

To interoperably communicate, points must be encoded as byte | To interoperably communicate, points must be encoded as byte | |||

strings. | strings. | |||

This draft specifies an encoding of finite points (x,y) as strings | This draft specifies an encoding of finite points (x,y) as strings | |||

of 34 bytes, as described in the following sections. | of 34 bytes, as described in the following sections. | |||

Note: The 34-byte encoding is not injective. Each point is | Note: The 34-byte encoding is not injective. Each point is | |||

generally among a group of four points that share the same byte | generally among a group of four points that share the same byte | |||

encoding. | encoding. | |||

Note: The 34-byte encoding is not surjective. Approximately half | Note: The 34-byte encoding is not surjective. Approximately half | |||

of 34-byte strings do not encode a finite point (x,y). | of 34-byte strings do not encode a finite point (x,y). | |||

Note: In many typical ECC schemes, the 34-byte encoding works | Note: In many typical ECC schemes, the 34-byte encoding works | |||

well, despite being neither injective nor surjective. | well, despite being neither injective nor surjective. | |||

3.1. Encoding a point into bytes | 3.1. Encoding a point into bytes | |||

In short: a finite point (x,y) by the little-endian byte | In short: a finite point (x,y) is encoded by the little-endian byte | |||

representation of x or -x, whichever fits into 34 bytes. | representation of x or -x, whichever fits into 34 bytes. | |||

Internet-Draft 2019-04-04 | ||||

In detail: a point (x,y) is encoded into 34 bytes, as follows. | In detail: a point (x,y) is encoded into 34 bytes, as follows. | |||

First, ensure that x is fully reduced mod p=8^91+5, so that | First, ensure that x is fully reduced mod p=8^91+5, so that | |||

0 <= x < 8^91+5. | 0 <= x < 8^91+5. | |||

Second, further reduce x by a flipping its sign. Let | Second, further reduce x by a flipping its sign. Let | |||

x' =: min(x,p-x) mod 2^272. | x' =: min(x,p-x) mod 2^272. | |||

Internet-Draft 2018-10-04 | ||||

Third, set the byte string b to be the little-endian encoding of the | Third, set the byte string b to be the little-endian encoding of the | |||

reduced integer x', by finding the unique integers b[i] such that | reduced integer x', by finding the unique integers b[i] such that | |||

0<=b[i]<256 and | 0<=b[i]<256 and | |||

(x' mod 2^272) = sum (0<=i<=33, b[i]*256^i). | (x' mod 2^272) = sum (0<=i<=33, b[i]*256^i). | |||

Pseudocode can be found in Appendix C. | Pseudocode can be found in Appendix C. | |||

Note: the loss of information that happens upon replacing x by -x | ||||

represents applying a complex multiplication by i on the curve, | ||||

since [i](x,y) = (-x,iy) = (u,v) is also a point on the curve, | ||||

because 2u^2 = 2(iy)^2 = -2y^2 = -(x^3+x) = (-x)^3 + (-x) = v^3 + | ||||

v. In many application, particularly Diffie--Hellman key | ||||

agreement, this loss of information is carried through the final | ||||

shared secret, which means that Alice and Bob can agree on the | ||||

same secret 34 bytes. | ||||

In elliptic curve algorithms where the original x coordinate and the | ||||

decoded x coordinate need to match exactly, then the 34-byte | ||||

encoding is probably not usable unless the following pre-encoding | ||||

procedure is practical: | ||||

Given a point x where x is larger than min(x,p-x), first replace x | ||||

by x'=p-x, on the encoder's side, using the new value x' (instead of | ||||

x) for any further step in the algorithm. In other words, replace | ||||

the point (x,y) by the point (x',y')=(-x,iy). Most algorithms will | ||||

also require a discrete logarithm d of (x,y), meaning (x,y) = [d] G | ||||

for some point G. Since (x',y') = [i](x,y), we can replace by d' | ||||

such that [d']=[i][d]. Usually, [i] can be represented by an | ||||

integer, say j, and we can compute d' = jd (mod ord(G)). | ||||

3.2. Decoding bytes into a point | 3.2. Decoding bytes into a point | |||

In short: the bytes are little-endian decoded into an integer which | In short: the bytes are little-endian decoded into an integer which | |||

becomes the x-coordinate. The y-coordinate is implicit (in | becomes the x-coordinate. Public-key validation done if needed. If | |||

Diffie--Hellman). | needed, the y-coordinate is recovered. | |||

Internet-Draft 2019-04-04 | ||||

In greater detail: if byte i is b[i], with an integer value | ||||

between 0 and 255 inclusive, then | ||||

x = sum( 0<=i<=33, b[i]*256^i) | ||||

Note: a value of -x (mod p) will also be suitable, and results in | ||||

a point (-x,y') which might be different from the originally | ||||

encoded point. However, it will be one of the points [i](x,y) or | ||||

-[i](x,y) where [i] means complex multiplication by [i]. | ||||

In many cases, such as Diffie--Hellman key agreement using the | ||||

Montgomery ladder, neither the original value of x or -x nor | ||||

coordinate y of the point is needed. In these cases, the decoding | ||||

steps can be considered completed. | ||||

+-------------------------------------------------------+ | +-------------------------------------------------------+ | |||

| | | | | | |||

| \ W / /A\ |R) |N | I |N | /G ! | | | \ W / /A\ |R) |N | I |N | /G ! | | |||

| \/ \/ / \ |^\ | \| | | \| \_7 0 | | | \/ \/ / \ |^\ | \| | | \| \_7 0 | | |||

| | | | | | |||

| | | | | | |||

| WARNING: Some byte strings b decode to an invalid | | | WARNING: Some byte strings b decode to an invalid | | |||

| point (x,y) that does not belong to the curve | | | point (x,y) that does not belong to the curve | | |||

| 2y^2=x^3+x. In some situations, such invalid b can | | | 2y^2=x^3+x. In some situations, such invalid b can | | |||

| lead to a severe attack. In these situations, the | | | lead to a severe attack. In these situations, the | | |||

| decoded point (x,y) MUST be validated, as described | | | decoded point (x,y) MUST be validated, as described | | |||

| below in Section 4. | | | below in Section 4. | | |||

| | | | | | |||

+-------------------------------------------------------+ | +-------------------------------------------------------+ | |||

(TO DO: if y is needed explicitly, then one of y matching x must be | In cases, where a value for at least of y, -y, iy, or -iy is needed | |||

solved; in that case, y-needing application, after a point (x,y) is | such as Diffie--Hellman key agreement using some other coordinate | |||

encoded to b, it should be replaced by (x',y'), where (x',y') is the | system (such as one might need when converting to Edwards | |||

decoding of b. In the rare case that x and x' do not match, then | coordinates), the candidate value can be obtained by computing a | |||

(x,y) should be re-generated or rejected.) | square root: | |||

In greater detail: if byte i is b[i], with an integer value | y = ((x^3+x)/2)^(1/2). | |||

between 0 and 255 inclusive, then | ||||

x = sum( 0<=i<=33, b[i]*256^i) | In some cases, it is important for the decoded value of x to match | |||

the original value of x exactly. In that case, the encoder should | ||||

use the procedure that replace x by p-x, and adjusts the discrete | ||||

logarithm appropriately. These steps can be done by the encoder, | ||||

with the decoder doing nothing. | ||||

Internet-Draft 2019-04-04 | ||||

4. Point validation | 4. Point validation | |||

In elliptic curve cryptography, scalar multiplying an invalid public | In elliptic curve cryptography, scalar multiplying an invalid public | |||

key by a private key risks leaking information about the private | key by a private key risks leaking information about the private | |||

key. | key. | |||

Internet-Draft 2018-10-04 | Note: For curve 2y^2=x^3+x over 8^91+5, the underlying attacks are | |||

a little milder than the average a typical elliptic curve. | ||||

For curve 2y^2=x^3+x over 8^91+5, the underlying attacks are a | ||||

little milder than the average a typical elliptic curve. | ||||

4.1. When a public key MAY, SHOULD or MUST be validated | 4.1. When a public key MAY, SHOULD or MUST be validated | |||

Every public key MAY be validated, just as an extra precaution, or | 4.1.1. Precautionary mandatory validation | |||

defense in depth. | ||||

If an implementation cannot to afford validate every public key, but | Every public key (and point) MAY be validated, as an extra | |||

also cannot follow the more complicated rules that follow, the | precaution (i.e., defense in depth. | |||

implementation can use the following simple rule: | ||||

4.1.2. Simplified validation | ||||

If small but general implementation aims for high speed, then the | ||||

implementation might not be able to the cost mandatory public key | ||||

validation. | ||||

It SHOULD follow at least the rule that an distrusted public key is | ||||

validated before combination with a static secret key. | ||||

+---------------------------------------------------------------+ | +---------------------------------------------------------------+ | |||

| STATIC | | | STATIC | | |||

| SECRET | | | SECRET | | |||

| KEY ------\ _ ___ | | | KEY ------\ _ ___ | | |||

| + ) PUBLIC |\/| | | (_` | | | | + ) PUBLIC |\/| | | (_` | | | |||

| UNPROVEN ------/ KEY | | \_/ ._) | BE VALIDATED. | | | UNPROVEN ------/ KEY | | \_/ ._) | BE VALIDATED. | | |||

| PUBLIC | | | PUBLIC | | |||

| KEY | | | KEY | | |||

+---------------------------------------------------------------+ | +---------------------------------------------------------------+ | |||

However, the more complicated rules described below aim to only | 4.1.3. Relatively safe cases of non-validation | |||

impose a requirement to validate when there is a known attack, when | ||||

a requirement is absolutely necessary. | ||||

Public key validation has a non-negligible cost, and is sometimes | ||||

not necessary for security. Here are some criteria under which | ||||

public key validation becomes a SHOULD or MUST | ||||

1) The public key P potentially originates from an potential | ||||

adversary. | ||||

2) The public key P will be used in Diffie--Hellman key agreement to | ||||

compute a value sP, where: | ||||

a) s is a secret | ||||

b) s will be or has been re-used to compute other values (other | ||||

than just sP) | ||||

c) proof of knowledge of sP has not been received (see Note) | ||||

d) proof of knowledge of sP has been requested (see Note) | ||||

e) the direct value of sP has been requested | ||||

Internet-Draft 2018-10-04 | ||||

f) sP is computed by one of the following methods: | ||||

I) first explicitly decompressing P to (x,y), but without | ||||

checking (x,y) is on the true curve or that intermediate | ||||

candidate square root are correct, second computing sP | ||||

using formulas that are correct even if P lies on some | ||||

other (false) curve. | ||||

II) using a (1 or 2 dimensinoal) Montgomery ladder, or | ||||

similar method, that ensures P is internally represented | ||||

as point on the curve or its twist, regardless of the | ||||

bytes used to deliver P, | ||||

3) The public key P will be used in some other algorithm, such as | ||||

Menezes--Qu--Vanstone key agreement, that combines P with a | ||||

long-term (static) secret s and an ephemeral secret e. | ||||

4) The public key P will be used in some algorithm, such as | ||||

signature verification algorithm, that does not combine P with | ||||

any secrets. | ||||

g) The algorithm involving P is used primarily to prove some | ||||

property of P is itself, such as proof-of-possession. | ||||

Note: proof of knowledge of sP can take many forms. For example, | ||||

deriving an message authetnication code key (HMAC) from sP and then | ||||

computig a tag of a knowable message. For a second example, | ||||

deriving a symmetric encryption key from sP, then encrypting a | ||||

message that is non-random in the sense it contains enough | ||||

redundancy that decryption proves knowledge of sP. Obviously, | ||||

direct exposure (e) of sP is a proof of knowledge of sP. | ||||

Public key validation MUST be done when the following sets of | ||||

criteria hold, because of the attacks summarized. | ||||

- {1,2,a,b,f,I}: The attacker pre-computes values P that | ||||

decompress to a point (x,y) of a very low-order point P that is | ||||

neither on the curve nor its twist, but on some other false curve. | ||||

Finding such P may be hard. The adversary can prove knowledge of | ||||

sP by guessing s mod ord(P), due to their very low order, though | ||||

many proofs will fail. Using these points P finds the secret s | ||||

quickly, by the Chinese remainder theorem. The number of failed | ||||

interactions with the owner of s may be in the thousands. | ||||

Fortunately, in this situtation public key validation is very | ||||

fast, since it can be done by checking that 2y^2=x^3+x. | ||||

Internet-Draft 2018-10-04 | ||||

- {1,2,a,b,c,f,I}: The attacker pre-computes values P that | ||||

decompress to a point (x,y) of a very low-order point P that is | ||||

neither on the curve nor its twist, but on some other false curve. | ||||

Finding such P may be hard. The attacker guesses (s mod ord(P)). | ||||

The attacker ascertains whether the guess is correct by conducting | ||||

a reaction attack, seeing whether the owner of s acts as though is | ||||

proper. Using these points P finds the secret s quickly, by the | ||||

Chinese remainder theorem. Fortunately, in this situtation public | ||||

key validation is very fast, since it can be done by checking that | ||||

2y^2=x^3+x. | ||||

- {1,2,a,b,c,e,f,II}: The attacker, (easily) pre-computes moderately | ||||

low-order points P on the twist, receives sP, and solves the | ||||

discrete log (s mod ord(P)). The attack takes computation of | ||||

about 2^65 group operations. Only esotertic protocols require sP | ||||

to be directly exposed: usually sP is passed through a 1-way hash | ||||

before any other use. | ||||

- {1,2,a,b,c,d,f,II}: The attacker (easily) pre-computes moderately | In some application an implementation of ECC seem not to suffer an | |||

low-order points P on the twists, receives proof-of-knowledge of | invalid curve attack. This section lists these situations. | |||

sP, exhaustively searches values of (s mod ord(P)). The attack | ||||

takes computation of at least 2^70 group operations. | ||||

If an implementation of the compute of sP from s and P can be used | Note: The main reason to omit public key validation is save | |||

in one of the situtations above, then it MUST either validate P | time. | |||

before | ||||

computing sP, or it must have a clearly documented input flag to | ||||

indicate whether P can be trusted. | ||||

Public key validation SHOULD be done in the following situations, | Internet-Draft 2019-04-04 | |||

because of the following attacks: | ||||

- {1,2,a,b,d,f,II}: The attacker (easily) generates a point P on the | We classify these situations at two levels: safe, if it seems that | |||

twist of order 1526119141 and makes approximately 1526119141/2 | no harm is possible, and relatively safe, if it there the attack is | |||

guesses g such gP = sP, uses the guesses as proof of knowledge of | both no worse than another attack and requires something else to be | |||

sP towards the owner of the secret s. This involves the owner of | broken. | |||

s unwittingly or unstoppably participating in about half a billion | ||||

failed crypto operations. The attacker then learns about 30 bits | ||||

of the secret s, which could be used to speed up on discrete | ||||

logarithm attack on s to cost of about 2^120 group operations. | ||||

Public key validation SHOULD be also done in the following | To be verified. | |||

situtations, either because it is so efficient (in 2,f,I), or | ||||

because of potential attacks, in order of decreasing risk (as | ||||

estimated by me): | ||||

Internet-Draft 2018-10-04 | If the secret key is ephemeral, the public key is trusted (signed) | |||

and a Montgomery ladder is used, then omitting validation of the | ||||

public key seems relatively safe. This is mostly because if the | ||||

holder of the public key is the attacker, then the trust system has | ||||

been broken. Furthermore, the attacker, as the intended recipient | ||||

in a typical communication, should already be able to receive any | ||||

data hidden by the secret key. | ||||

- {1,2,a,b,e} | To be extended. | |||

- {1,2,a,b,c,d} | ||||

- {1,2,a,b,f,I} | ||||

- {1,2,a,b} | ||||

- {1,2,f,I,3} | ||||

- {1,2,f,I,4} | ||||

- {2,f,I} | ||||

Note that the twist has order: | 4.1.4. Minimal validation | |||

2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 * | To maximize efficiency, an implementation may wish to minimize the | |||

3452464930451677330036005252040328546941 | amount of validation done down to the point of only resisting a | |||

known | ||||

attack. | ||||

OLD TEXT BELOW: | To be completed. | |||

If a party Alice has a secret key a for the curve 2y^2=x^3+x over | Note: a given point need only be validated once, if the | |||

8^91+5, which she will to establish two (hashed) Diffie--Hellman | implementation can track validation state. | |||

keys, agreement with 2 or more public keys from other parties, say | ||||

Bob and Charles, then Alice SHOULD apply public-key validation to | ||||

the public key points of the other parties (Bob and Charlies). | ||||

MUST undergo validation if they are | The curve 2y^2=x^3+x is not twist-secure: using the Montgomery | |||

combined with private keys as part of multiple Diffie--Hellman | ladder for scalar multiplication is not enough to thwart invalid | |||

computations: | public key attacks. | |||

Additionally, public keys SHOULD undergo validation if they are | Note: the twist of 2y^2=x^3+x/GF(8^91+5) curve has order: | |||

received from an unauthenticated source, even if the scalar is | ||||

ephemeral or public. | ||||

ATTEMPT (TO BE CONFIRMED): | 2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 * | |||

3452464930451677330036005252040328546941 | ||||

4.2. How to validate a point (given only x) | 4.2. How to validate a point (given only x) | |||

Upon decoding the 34 bytes into x, the next step is to compute | Upon decoding the 34 bytes into x, the next step is to compute | |||

z=2(x^3+x). Then one checks if z has a nonzero square root. If z | z=2(x^3+x). Then one checks if z has a nonzero square root (in the | |||

has a nonzero square root, then the represented point is valid, | field of size 8^91+5). If z has a nonzero square root, then the | |||

otherwise it is not valid. | represented point is valid, otherwise it is not valid. | |||

Equivalently, one can check that x^3 + x has no square root (that | Equivalently, one can check that x^3 + x has no square root (that | |||

is, x^3+x is a quadratic non-residue). | is, x^3+x is a quadratic non-residue). | |||

Internet-Draft 2019-04-04 | ||||

To check z for a square root, one can compute the Legendre symbol | To check z for a square root, one can compute the Legendre symbol | |||

(z/p) and check that is 1. (Equivalently, one can check that | (z/p) and check that is 1. (Equivalently, one can check that | |||

((x^3+x)/p)=-1.) | ((x^3+x)/p)=-1.) | |||

Internet-Draft 2018-10-04 | ||||

The Legendre symbol can be computed using Gauss' quadratic | The Legendre symbol can be computed using Gauss' quadratic | |||

reciprocity law, but this requires implementing modular integer | reciprocity law, but this requires implementing modular integer | |||

arithmetic for moduli smaller than 8^91+5. | arithmetic for moduli smaller than 8^91+5. | |||

More slowly, but perhaps more simply, one compute the Legendre | More slowly, but perhaps more simply, one compute the Legendre | |||

symbol using powering in the field: (z/p) = z^((p-1)/2) = | symbol using powering in the field: (z/p) = z^((p-1)/2) = | |||

z^(2^272+2). This will have value 0,1 or p-1 (which is equivalent | z^(2^272+2). This will have value 0,1 or p-1 (which is equivalent | |||

to -1). | to -1). | |||

More generally, in signature applications, where the y-coordinate is | More generally, in signature applications, where the y-coordinate is | |||

also needed, the computation of y, which involves computing a square | also needed, the computation of y, which involves computing a square | |||

root will generally include a check that x is valid. | root will generally include a check that x is valid. | |||

The curve 2y^2=x^3+x is not twist-secure. So, using the Montgomery | ||||

ladder for scalar multiplication is not enough to thwart invalid | ||||

public key attacks. In other words, public key validation MUST be | ||||

combined with the Montgomery ladder, unless the scalar multiplier | ||||

involved is public or a single-DH-use secret (i.e. computing kG and | ||||

kP, counts as a single DH use of k). | ||||

Note: a given point need only be validated once, if the | ||||

implementation can track validation state. | ||||

OPTIONAL: In some rare situations, it is also necessary to ensure | OPTIONAL: In some rare situations, it is also necessary to ensure | |||

that the point has large order, not just that it is on the curve. | that the point has large order, not just that it is on the curve. | |||

For points on this curve, each point has large order, unless it has | For points on this curve, each point has large order, unless it has | |||

torsion by 12. In other words, if 12P != O, then the point P has | torsion by 12. In other words, if [12]P != O, then the point P has | |||

large order. | large order. | |||

OPTIONAL: In even rarer situations, it may be necessary to ensure | OPTIONAL: In even rarer situations, it may be necessary to ensure | |||

that the point also has prime order. To be completed. | that a point P also has a prime order n = ord(G). The costly method | |||

to check this is checking that [n]P = O. An alternative method is | ||||

to try to solve for Q in the equation [12]Q=P, which involves | ||||

methods such a division polynomials. | ||||

To be completed. | ||||

5. OPTIONAL encodings | 5. OPTIONAL encodings | |||

The following two encodings are not usually required to obtain | The following two encodings are not usually required to obtain | |||

interoperability in the typical ECC applications, but can sometimes | interoperability in the typical ECC applications, but can sometimes | |||

be useful. | be useful. | |||

5.1. Encoding scalar multipliers as 34 bytes | 5.1. Encoding scalar multipliers as 34 bytes | |||

To be completed. | To be completed. | |||

Basically, little-endian byte encoding of integers is recommended. | Basically, little-endian byte encoding of integers is recommended. | |||

The main application is to signatures. | The main application is to signatures. | |||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

Another application is for test vectors (to be completed). | Another application is for test vectors (to be completed). | |||

5.2. Encoding 34 bytes into a point (sketch) | 5.2. Encoding 34 bytes into a point (sketch) | |||

In special applications, beyond mere Diffie--Hellman key exchange or | In niche applications, it may be desired to encode arbitrary bytes | |||

digital signatures, it may be desired to encode arbitrary bytes as | as | |||

points. | points. | |||

Note: This type of encoding is sometimes called hashing to a | ||||

curve. | ||||

Note: Diffie--Hellman key exchange or digital signatures do not | ||||

require encoding of arbitrary byte strings. | ||||

Example reasons are anonymity, or hiding the presence of a key | Example reasons are anonymity, or hiding the presence of a key | |||

exchange. | exchange. | |||

Note: the point encoding described earlier does a different job. | Note: the point encoding described earlier does a different job. | |||

It encodes every point. The task here is to encode every byte | It encodes every point as a byte string. The task here is the | |||

string. | opposite: to encode every byte string as a point. | |||

This method is slower than the representations above, and yields | Note: Encoding a byte string as a point yields biased elliptic | |||

biased elliptic curve points, but has the advantage that the | curve points, but has the advantage that the byte-strings are | |||

byte-strings are unbiased. | unbiased. | |||

The idea is a minor variation of the Elligator 2 construction | The encoding is called Elligator i, (see also [B1]), and is just a | |||

[Elligator]. Unfortunately, Elligator 2 itself fails for curves | minor variation of the Elligator 2 construction [Elligator]. | |||

with j-invariant 1728, which includes 2y^2=x^3+x. In case of | Elligator 2 fails for curves with j-invariant 1728, which includes | |||

confusion, this map here can be called Elligator i, (see also [B1]). | 2y^2=x^3+x, so a minor tweak is made, obtain Elligator i. | |||

Fix a square root i of -1 in the field. | Fix a square root i of -1 in the field. | |||

Given any random field element r, compute | Given any random field element r, compute | |||

x=i- 3i/(1-ir^2) | x=i- 3i/(1-ir^2) | |||

If there is no y solving 2y^2=x^3+x for this x, then replace x by | If there is no y solving 2y^2=x^3+x for this x, then replace x by | |||

x+i and try to solve for y once again. | x+i and try to solve for y once again. | |||

If the first x fails, then the second x succeeds. | If the first x fails, then the second x succeeds. | |||

So, now r determines a unique x. To determine y, solve it per the | So, now r determines a unique x. To determine y, solve it per the | |||

equation, getting two roots. Label the 2 roots y0 and y1 according | equation, getting two roots. Label the 2 roots y0 and y1 according | |||

to a deterministic rule. Then choose y0 if the first x works, else | to a deterministic rule. Then choose y0 if the first x works, else | |||

choose y2. This ensures that the map from r^2 to (x,y) is | choose y2. This ensures that the map from r^2 to (x,y) is | |||

injective. | injective. | |||

Internet-Draft 2019-04-04 | ||||

Finally, to encode a byte string b, just let it represent a field | Finally, to encode a byte string b, just let it represent a field | |||

element r. Note that -r will be require more than 34 bytes. So the | element r. Note that -r will be require more than 34 bytes. So the | |||

map from b to (x,y) is now injective. | map from b to (x,y) is now injective. | |||

This map is reversible. | The Elligator i map is reversible. | |||

Internet-Draft 2018-10-04 | ||||

To be completed. | ||||

6. Cryptographic schemes | ||||

To be completed, or even removed! | ||||

List all possible cryptographic schemes in which this curve could be | ||||

used is outside the scope of this short document. Only a few | ||||

highlights are mentioned. | ||||

6.1. Diffie--Hellman key agreement | ||||

To be completed. | ||||

Question: should DH use cofactor multiplication? For now, let's say | ||||

no. | ||||

Non-cofactor multiplication risks leaking the private key mod 72, or | ||||

at least mod 12, or perhaps even worse (if the field arithmetic has | ||||

additional leaks). | ||||

But cofactor multiplication reduces the private key size similarly. | ||||

Also, if we start from a 34-byte private key scalar, then we achieve | ||||

a similar effect to cofactor multiplication. | ||||

6.2. Signatures | ||||

For signatures, such as ECDSA, the verifier must fully decompress | ||||

the 34-byte representation. The verifier must do this twice, once | ||||

with the signer's public key, and once with one component of the | ||||

signature. | ||||

To do this, the verifier can take, and make the most natural choice | ||||

of the two possible y. The signer, anticipating the verifier, then | ||||

must ensure that the signature will verify correctly under the | ||||

verifier's choices for the y values. The signer incurs only a small | ||||

extra cost for ensuring this. | ||||

To be completed. | ||||

Given that this curve is experimental and non-radically distinct | ||||

from previous curves, signers and may opt to consider an | ||||

experimental and non-radically distinct signature scheme with the | ||||

curve 2y^2=x^3+x. | ||||

The RKHD ElGamal signature scheme [B2] is an example of such a | ||||

signature scheme. | ||||

Internet-Draft 2018-10-04 | ||||

In short, fix a base point G. The signing key is d, the verifying | ||||

key is Q=dG. A pair (R,s), R is a point, and s is an integer, is a | ||||

(valid) signature of message with integer hash h, if | ||||

sG = rR + hQ | ||||

where r is obtained from R by re-interpreting its byte as an | ||||

integer. | ||||

To sign a message with hash h, the signer computes a | ||||

message-unique secret k, computes R=kG, computers r as above, and | ||||

computes | ||||

s = rk + hd mod n | ||||

where n is the order of G. | ||||

The signer may compute k as the hash of s and h, or through some | ||||

other method which ensures that k depends (pseudorandomly) on h. | ||||

The signer MUST choose k such that no linear relation between the k | ||||

for different h can be discovered by the adversary. The signer | ||||

SHOULD use some kind of pseudorandom function to achieve this. | ||||

Note: this ElGamal signature variant corresponds to type 4 ElGamal | ||||

signature in the Handbook of Applied Cryptography. | ||||

6.3 Menezes--Qu--Vanstone key agreement | ||||

To be completed. | To be completed. | |||

7. IANA Considerations | 6. IANA Considerations | |||

This document requires no actions by IANA, yet. | This document requires no actions by IANA, yet. | |||

8. Security considerations | 7. Security considerations | |||

No cryptographic algorithms is without risks. Consequently, risks | No cryptographic algorithms is without risks. Consequently, risks | |||

are comparative. This section will not fully list the risks of all | are comparative. This section will not fully list the risks of all | |||

other forms of elliptic curve cryptography. Instead it will list | other forms of elliptic curve cryptography. Instead it will list | |||

the most plausible risks of this curve, and only to a limited degree | the most plausible risks of this curve, and only to a limited degree | |||

contrast these to a few other standardized curves. | contrast these to a few other standardized curves. | |||

8.1. Field choice | 7.1. Field choice | |||

The field 8^91+5 has the following risks. | The field 8^91+5 has the following risks. | |||

Internet-Draft 2018-10-04 | ||||

- 8^91+5 is a special prime. As such, it is perhaps vulnerable to | - 8^91+5 is a special prime. As such, it is perhaps vulnerable to | |||

some kind of attack. For example, for some curve shapes, the | some kind of attack. For example, for some curve shapes, the | |||

supersingularity depends on the prime, and the curve size is | supersingularity depends on the prime, and the curve size is | |||

related in a simple way to the field size, causing a potential | related in a simple way to the field size, causing a potential | |||

correlation between the field size and the effectiveness of an | correlation between the field size and the effectiveness of an | |||

attack, such as the Pohlig--Hellman attack. | attack, such as the Pohlig--Hellman attack. | |||

Many other standard curves, such as the NIST P-256 and | Many other standard curves, such as the NIST P-256 and | |||

Curve25519, also use special prime field sizes, so have a similar | Curve25519, also use special prime field sizes, so have a similar | |||

risk. Yet other standard curves, such as the Brainpool, use | risk. Yet other standard curves, such as the Brainpool, use | |||

skipping to change at page 14, line 30 ¶ | skipping to change at page 13, line 5 ¶ | |||

overflowing, or of not fully reducing properly. Perhaps a smaller | overflowing, or of not fully reducing properly. Perhaps a smaller | |||

field, such as that used in Curve25519, has a simpler reduction | field, such as that used in Curve25519, has a simpler reduction | |||

and overflow-avoidance properties. | and overflow-avoidance properties. | |||

- 8^91+5, by virtue of being well-above 256 bits in size, risks its | - 8^91+5, by virtue of being well-above 256 bits in size, risks its | |||

user doing extra, and perhaps unnecessary, computation to protect | user doing extra, and perhaps unnecessary, computation to protect | |||

their 128-bit keys, whereas smaller curves might be faster (as | their 128-bit keys, whereas smaller curves might be faster (as | |||

expected) yet still provide enough security. In other words, the | expected) yet still provide enough security. In other words, the | |||

extra cost is wasteful, and partially a form of denial of service. | extra cost is wasteful, and partially a form of denial of service. | |||

- 8^91+5, is smaller than 8^95-9, yet uses no fewer symbols. Since | Internet-Draft 2019-04-04 | |||

larger field sizes lead to strong Pollard rho resistance, it can | ||||

be argued that this field size does not optimize security against | ||||

(specification) simplicity. (The main reason this document | ||||

prefers 8^91+5 over 8^95-9 is its simpler field inversion.) | ||||

Similarly, 8^91+5 is smaller than the six-symbol primes 9^99+4 and | ||||

9^87+4, but these are not close to powers of two, which means that | ||||

modular multiplication and reduction for them is not likely to be | ||||

as efficient as for 8^91+5. | ||||

- 8^91+5, is smaller than 2^283 (the field size for curve sect283k1 | - 8^91+5 is smaller than some other six-symbol primes: 8^95-9, | |||

9^99+4 and 9^87+4. Arguably, 8^91+5 fails to maximize field size, | ||||

and thus potential Pollard rho resistance of the ECDLP, among | ||||

six-symbol primes. The primes 9^99+4 and 9^87+4 are not close to | ||||

a power of two, so probably suffer from much slower implementation | ||||

than 8^91+5, which is a significant cost. The prime 8^95-9 is | ||||

just a little below a power of two, so should have comparable | ||||

efficiency for basic field arithmetic. The field 8^95-9 is a | ||||

little larger, but can still be implemented using five 64-bit | ||||

words. Being larger, 8^85-9, it has a slightly greater risk than | ||||

8^91+5 of leading to an arithmetic overflow implementation fault | ||||

in field arithmetic. Also, field size 8^91+5 has very simple | ||||

powering algorithms for computing field inverses, Legendre | ||||

symbols, and square roots, all because it is just slightly above a | ||||

power of two. For field size 8^85-9, these powering algorithms | ||||

require more complicated algorithms. | ||||

- 8^91+5 is smaller than 2^283 (the field size for curve sect283k1 | ||||

[SEC2], [Zigbee]), and many other five-symbol and four-symbol | [SEC2], [Zigbee]), and many other five-symbol and four-symbol | |||

powers of primes (such as 9^97). So, it less to provide less | prime powers (such as 9^97). It provides less resistance to | |||

resistance to Pollard rho. Recent progress in the elliptic curve | Pollard rho than such larger prime powers. Recent progress in the | |||

discrete logarithm problem, [HPST] and [Nagao], is the main reason | elliptic curve discrete logarithm problem, [HPST] and [Nagao], is | |||

to prefer prime fields instead of power of prime fields. A second | the main reason to prefer prime fields instead of power of prime | |||

reason to prefer prime field 8^91+5 (and other large | fields. A second reason to prefer a prime field (including the | |||

characteristic fields) over small characteristic fields, is the | field of size 8^91+5) over small characteristic fields is the | |||

generally better software speed of large characteristic fields: | generally better software speed of large characteristic field. | |||

which arises because most software is implemented on a general | (Better software speed is mainly due to general-purpose hardware | |||

purpose hardware processor that has fast multiplication circuits. | often having dedicated fast multiplication circuits: | |||

(This speed advantage probably does not apply for hardware.) | special-purpose hardware should make small characteristic field | |||

faster.) | ||||

See [B1] for further discussion. | See [B1] for further discussion. | |||

Internet-Draft 2018-10-04 | 7.2. Curve choice | |||

8.2. Curve choice | ||||

A first risk of using 2y^2=x^3+x is the fact that it is a special | A first risk of using 2y^2=x^3+x is the fact that it is a special | |||

curve, with complex multiplication leading to an efficient | curve, with complex multiplication leading to an efficient | |||

endomorphism. Many other standard curves, NIST P-256 [NIST-P-256], | endomorphism. Many other standard curves, NIST P-256 [NIST-P-256], | |||

Curve25519, Brainpool [Brainpool], do not have any efficient | Curve25519, Brainpool [Brainpool], do not have any efficient | |||

endomorphisms. Yet some standard curves do, NIST K-283 and | endomorphisms. Yet some standard curves do, NIST K-283 and | |||

secp256k1 (see [SEC2] and [BitCoin]). Furthermore, it is not | secp256k1 (see [SEC2] and [BitCoin]). Furthermore, it is not | |||

implausible [KKM] that special curves, including those efficient | implausible [KKM] that special curves, including those efficient | |||

endomorphisms, may survive an attack on random curves. | endomorphisms, may survive an attack on random curves. | |||

Internet-Draft 2019-04-04 | ||||

A second risk of 2y^2=x^3+x over 8^91+5 is the fact that it is not | A second risk of 2y^2=x^3+x over 8^91+5 is the fact that it is not | |||

twist-secure. What may happen is that an implementer may use the | twist-secure. What may happen is that an implementer may use the | |||

Montgomery ladder in Diffie--Hellman and re-use private keys. They | Montgomery ladder in Diffie--Hellman and re-use private keys. They | |||

may think, despite the (ample?) warnings in this document, that | may think, despite the (ample?) warnings in this document, that | |||

public key validation in unnecessary, modeling their implementation | public key validation in unnecessary, modeling their implementation | |||

after Curve25519 or some other twist-secure curve. This implementer | after Curve25519 or some other twist-secure curve. This implementer | |||

is at risk of an invalid public key attack. Moreover, the | is at risk of an invalid public key attack. Moreover, the | |||

implementer has an incentive to skip public-key validation, for | implementer has an incentive to skip public-key validation, for | |||

better performance. Finally, even if the implementer uses | better performance. Finally, even if the implementer uses | |||

public-key validation, then the cost of public-key validation is | public-key validation, then the cost of public-key validation is | |||

non-negligible. | non-negligible. | |||

A third risk is a biased ephemeral private key generation in a | A third risk is a biased ephemeral private key generation in a | |||

digital signature scheme. Most standard curve lack this risk | digital signature scheme. Most standard curves lack this risk | |||

because the field is close to a power of two, and the cofactor is a | because the field size is close to a power of two, and the cofactor | |||

power of two. | is a power of two. Curve 2y^2=x^3+x over 8^91+5 has a base point | |||

order which is approximately a power of two divided by nine (because | ||||

its cofactor is 72=8*9.) As such, it is more vulnerable than | ||||

typical curves to biased ephemeral keys in a signature scheme. | ||||

A fourth risk is a Cheon-type attack. Few standard curves address | A fourth risk is a Cheon-type attack. Few standard curves address | |||

this risk. | this risk, and 2y^2=x^3+x over 8^91+5 is not much different. | |||

A fifth risk is a small-subgroup confinement attack, which can also | A fifth risk is a small-subgroup confinement attack, which can also | |||

leak a few bits of the private key. | leak a few bits of the private key. Curve 2y^2=x^3+x over 8^91+5 | |||

has 72 elements whose order divides 12. | ||||

8.3. Encoding choices | 7.3. Encoding choices | |||

To be completed. | To be completed. | |||

8.4. General subversion concerns | 7.4. General subversion concerns | |||

Although the main motivation of curve 2y^2=x^3+x over 8^91+5 is to | Although the main motivation of curve 2y^2=x^3+x over 8^91+5 is to | |||

minimize the risk of subversion via a backdoor ([Gordon], [YY], | minimize the risk of subversion via a backdoor ([Gordon], [YY], | |||

[Teske]), it is only fair to point out that its appearance in this | [Teske]), it is only fair to point out that its appearance in this | |||

very document can be viewed with suspicion as an possible effort at | very document can be viewed with suspicion as an possible effort at | |||

subversion (via a front-door). (See [BCCHLV] for some further | subversion (via a front-door). (See [BCCHLV] for some further | |||

discussion.) | discussion.) | |||

Internet-Draft 2018-10-04 | ||||

Any other standardized curve can be view with a similar suspicion | Any other standardized curve can be view with a similar suspicion | |||

(except, perhaps, by the honest authors of those standards for whom | (except, perhaps, by the honest authors of those standards for whom | |||

such suspicion seems absurd and unfair). A skeptic can then examine | such suspicion seems absurd and unfair). A skeptic can then examine | |||

both (a) the reputation of the (alleged) author of the standard, | both (a) the reputation of the (alleged) author of the standard, | |||

making an ad hominem argument, and (b) the curve's intrinsic merits. | making an ad hominem argument, and (b) the curve's intrinsic merits. | |||

By the very definition of this document, the user is encouraged to | Internet-Draft 2019-04-04 | |||

By the very definition of this document, the reader is encouraged to | ||||

take an especially skeptical viewpoint of curve 2y^2=x^3+x over | take an especially skeptical viewpoint of curve 2y^2=x^3+x over | |||

8^91+5. So, it is expected that skeptical users of the curve will | 8^91+5. So, it is expected that skeptical users of the curve will | |||

either | either | |||

- use the curve for its other merits (other than its backdoor | - use the curve for its other merits (other than its backdoor | |||

mitigations), such as efficient endomorphism, field inversion, | mitigations), such as efficient endomorphism, field inversion, | |||

high Pollard rho resistance within five 64-bit words, meanwhile | high Pollard rho resistance within five 64-bit words, meanwhile | |||

holding to the evidence-supported belief ECC that is now so mature | holding to the evidence-supported belief ECC that is now so mature | |||

that worries about subverted curves are just far-fetched nonsense, | that worries about subverted curves are just far-fetched nonsense, | |||

or | or | |||

skipping to change at page 16, line 39 ¶ | skipping to change at page 15, line 33 ¶ | |||

To paraphrase, consider users seriously worried about subverted | To paraphrase, consider users seriously worried about subverted | |||

curves (or other cryptographic algorithms), either because they | curves (or other cryptographic algorithms), either because they | |||

estimate as high either the probability of subversion or the value | estimate as high either the probability of subversion or the value | |||

of the data needing protection. These users have good reason to | of the data needing protection. These users have good reason to | |||

like 2y^2=x^3+x over 8^91+5 for its compact description. | like 2y^2=x^3+x over 8^91+5 for its compact description. | |||

Nevertheless, the best way to resist subversion of cryptographic | Nevertheless, the best way to resist subversion of cryptographic | |||

algorithms seems to be combine multiple dissimilar cryptographic | algorithms seems to be combine multiple dissimilar cryptographic | |||

algorithms, in a strongest-link manner. Diversity hedges against | algorithms, in a strongest-link manner. Diversity hedges against | |||

subversion, and should the first defense against it. | subversion, and should the first defense against it. | |||

8.5. Concerns about 'aegis' | 7.5. Concerns about 'aegis' | |||

The exact curve 2y^2=x^3+x over 8^91+5 was (seemingly) first | The exact curve 2y^2=x^3+x over 8^91+5 was (seemingly) first | |||

described to the public in 2017 [AB]. So, it has a very low age. | described to the public in 2017 [AB]. So, it has a very low age. | |||

Furthermore, it has not been submitted for a publication with peer | Furthermore, it has not been submitted for a publication with peer | |||

review to any cryptographic forum such as the IACR conferences like | review to any cryptographic forum such as the IACR conferences like | |||

Crypto and Eurocrypt. So, it has been review by very few eyes, most | Crypto and Eurocrypt. So, it has only been reviewed by very few | |||

of which had little incentive to study it seriously. | eyes, most of which had little incentive to study it critically. | |||

Under the metric of aegis, as in age * eyes, it scores low. | Under the metric of aegis, as in age * eyes, it scores low. | |||

Counting myself (but not quantifying incentive) it gets an aegis | Counting myself (but not quantifying incentive) it gets an aegis | |||

score of 0.1 (using a rating 0.1 of my eyes factor in the aegis | score of 0.1 (using a rating 0.1 of my eyes factor in the aegis | |||

score: I have not discovered any major ECC attacks of my own.) This | score: I have not discovered any major ECC attacks of my own.) This | |||

is far smaller than some more well-studied curves. | is far smaller than some more well-studied curves. | |||

Internet-Draft 2018-10-04 | ||||

However, in its defense, the curve 2y^2=x^3+x over 8^91+5 has | However, in its defense, the curve 2y^2=x^3+x over 8^91+5 has | |||

similarities to some of the better-studied curves with much higher | similarities to some of the better-studied curves with much higher | |||

aegis: | aegis: | |||

Internet-Draft 2019-04-04 | ||||

- Curve25519: has field size 8^85-19, which a little similar to | - Curve25519: has field size 8^85-19, which a little similar to | |||

8^91+5; has equation of the form by^2=x^3+ax+x, with b and a | 8^91+5; has equation of the form by^2=x^3+ax+x, with b and a | |||

small, which is similar to 2y^2=x^3+x. Curve25519 has been around | small, which is similar to 2y^2=x^3+x. Curve25519 has been around | |||

for over 10 years, has (presumably) many eyes looking at it, and | for over 10 years, has (presumably) many eyes looking at it, and | |||

has been deployed thereby creating an incentive to study. An | has been deployed thereby creating an incentive to study. An | |||

estimated aegis score is 10000. | estimated aegis for Curve25519 is 10000. | |||

- P-256: has a special field size, and maybe an estimated aegis | - P-256: has a special field size, and maybe an estimated aegis of | |||

score of 200000. (It is a high-incentive target. Also, it has | 200000. (It is a high-incentive target. Also, it has received | |||

received much criticism, showing some intent of cryptanalysis. | much criticism, showing some intent of cryptanalysis. Indeed, | |||

Indeed, there has been incremental progress in finding minor | there has been incremental progress in finding minor weakness | |||

weakness (implementation security flaws), suggestive of actual | (implementation security flaws), suggestive of actual | |||

cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5 | cryptanalytic effort.) The similarity to 2y^2=x^3+x over 8^91+5 | |||

is very minor, so very little of the P-256 aegis would be relevant | is very minor, so very little of the P-256 aegis would be relevant | |||

to this document. | to this document. | |||

- secp256k1: has a special field size, though not quite as special | - secp256k1: has a special field size, though not quite as special | |||

as 8^91+5, and has special field equation with an efficient | as 8^91+5, and has special field equation with an efficient | |||

endomorphism by a low-norm complex algebraic integer, quite | endomorphism by a low-norm complex algebraic integer, quite | |||

similar to 2y^2=x^3+x. It is about 17 years old, and though not | similar to 2y^2=x^3+x. It is about 17 years old, and though not | |||

studied much in academic work, its deployment in Bitcoin has at | studied much in academic work, its deployment in Bitcoin has at | |||

least created an incentive to attack it. An estimated aegis score | least created an incentive to attack it. An estimated aegis for | |||

is 10000. | secp256k1 is 10000. | |||

- Miller's curve: Miller's 1985 paper introducing ECC suggested, | - Miller's curve: Miller's 1985 paper introducing ECC suggested, | |||

among other choices, a curve equation y^2=x^3-ax, where a is a | among other choices, a curve equation y^2=x^3-ax, where a is a | |||

quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to | quadratic non-residue. Curve 2y^2=x^3+x is isomorphic to | |||

y^2=x^3-x, which is essentially one of Miller's curves, except | y^2=x^3-x, essentially one of Miller's curves, except that a=1 is | |||

that a=1 is a quadratic residue. Miller's curve has not been | a quadratic residue. Miller's curve may not have been studied | |||

studied directly, but probably much more so than this than the | intensely as other curves, but its age matches that ECC itself. | |||

curve in this document. Miller also hinted that it was not | Miller also hinted that it was not prudent to use a special curve | |||

prudent to use a special curve y^2=x^3-ax: such a comment may have | y^2=x^3-ax: such a comment may have encouraged some cryptanalysts, | |||

encourage some cryptanalysts, but discouraged cryptographers, | but discouraged cryptographers, perhaps balancing out the effect | |||

perhaps balancing out the effect on the eyes factor the aegis | on the eyes factor the aegis. An estimated aegis for Miller's | |||

score. An estimate aegis score is 300. | curves is 300. | |||

Obvious cautions to the reader: | Obvious cautions to the reader: | |||

- Small changes in a cryptographic algorithm sometimes cause large | - Small changes in a cryptographic algorithm sometimes cause large | |||

differences in security. So security arguments based on | differences in security. So security arguments based on | |||

similarity in cryptographic schemes should be given low priority. | similarity in cryptographic schemes should be given low priority. | |||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

- Security flaws have sometimes remained undiscovered for years, | - Security flaws have sometimes remained undiscovered for years, | |||

despite both incentives and peer reviews (and lack of hard | despite both incentives and peer reviews (and lack of hard | |||

evidence of conspiracy). So, the eyes-part of the aegis score is | evidence of conspiracy). So, the eyes-part of the aegis score is | |||

very subjective, and perhaps vulnerable false positives by a herd | very subjective, and perhaps vulnerable false positives by a herd | |||

effect. Despite this caveat, it is not recommended to ignore the | effect. Despite this caveat, it is not recommended to ignore the | |||

eyes factor in the aegis score: don't just flip through old books | eyes factor in the aegis score: don't just flip through old books | |||

(of say, fiction), looking for cryptographic algorithms that might | (of say, fiction), looking for cryptographic algorithms that might | |||

never have been studied. | never have been studied. | |||

9. References | 8. References | |||

9.1. Normative References | 8.1. Normative References | |||

[BCP14] Bradner, S., "Key words for use in RFCs to Indicate | [BCP14] Bradner, S., "Key words for use in RFCs to Indicate | |||

Requirement Levels", BCP 14, RFC 2119, March 1997, | Requirement Levels", BCP 14, RFC 2119, March 1997, | |||

<http://www.rfc-editor.org/info/bcp14>. | <http://www.rfc-editor.org/info/bcp14>. | |||

9.2. Informative References | 8.2. Informative References | |||

To be completed. | To be completed. | |||

[AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG, | [AB] A. Allen and D. Brown. ECC mod 8^91+5, presentation to CFRG, | |||

2017. | 2017. | |||

<https://datatracker.ietf.org/doc/slides-99-cfrg-ecc-mod-8915/> | <https://datatracker.ietf.org/doc/slides-99-cfrg-ecc-mod-8915/> | |||

[AMPS] Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and | [AMPS] Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, and | |||

Juraj Somorovsky. Prime and Prejudice: Primality Testing Under | Juraj Somorovsky. Prime and Prejudice: Primality Testing Under | |||

Adversarial Conditions, IACR ePrint, | Adversarial Conditions, IACR ePrint, | |||

skipping to change at page 18, line 52 ¶ | skipping to change at page 17, line 52 ¶ | |||

[KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve | [KKM] A. Koblitz, N. Koblitz and A. Menezes. Elliptic Curve | |||

Cryptography: The Serpentine Course of a Paradigm Shift, IACR | Cryptography: The Serpentine Course of a Paradigm Shift, IACR | |||

ePrint, 2008. <https://ia.cr/2008/390> | ePrint, 2008. <https://ia.cr/2008/390> | |||

[BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing, | [BCCHLV] D. Bernstein, T. Chou, C. Chuengsatiansup, A. Hulsing, | |||

T. Lange, R. Niederhagen and C. van Vredendaal. How to | T. Lange, R. Niederhagen and C. van Vredendaal. How to | |||

manipulate curve standards: a white paper for the black hat, IACR | manipulate curve standards: a white paper for the black hat, IACR | |||

ePrint, 2014. <https://ia.cr/2014/571> | ePrint, 2014. <https://ia.cr/2014/571> | |||

[Elligator] To do: fill in this reference. | [Elligator] (((To do:))) fill in this reference. | |||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

[NIST-P-256] To do: NIST recommended 15 elliptic curves for | [NIST-P-256] (((To do:))) NIST recommended 15 elliptic curves for | |||

cryptography, the most popular of which is P-256. | cryptography, the most popular of which is P-256. | |||

[Zigbee] To do: Zigbee allows the use of a small-characteristic | [Zigbee] (((To do:))) Zigbee allows the use of a | |||

small-characteristic | ||||

special curve, which was also recommended by NIST, called K-283, | special curve, which was also recommended by NIST, called K-283, | |||

and also known as sect283k1. These types of curves were | and also known as sect283k1. These types of curves were | |||

introduced by Koblitz. These types of curves were not | introduced by Koblitz. These types of curves were not | |||

recommended by NSA in Suite B. | recommended by NSA in Suite B. | |||

[Brainpool] To do: the Brainpool consortium (???) recommended some | [Brainpool] (((To do:))) the Brainpool consortium (???) recommended | |||

elliptic curves in which both the field size and the curve | some elliptic curves in which both the field size and the curve | |||

equation were derived pseudorandomly from a nothing-up-my-sleeve | equation were derived pseudorandomly from a nothing-up-my-sleeve | |||

number. | number. | |||

[SEC2] Standards for Efficient Cryptography. SEC 2: Recommended | [SEC2] Standards for Efficient Cryptography. SEC 2: Recommended | |||

Elliptic Curve Domain Parameters, version 2.0, 2010. | Elliptic Curve Domain Parameters, version 2.0, 2010. | |||

<http://www.secg.org/sec2-v2.pdf> | <http://www.secg.org/sec2-v2.pdf> | |||

[IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic | [IT] T. Izu and T. Takagi. Exceptional procedure attack on elliptic | |||

curve cryptosystems, Public key cryptography -- PKC 2003, Lecture | curve cryptosystems, Public key cryptography -- PKC 2003, Lecture | |||

Notes in Computer Science, Springer, pp. 224--239, 2003. | Notes in Computer Science, Springer, pp. 224--239, 2003. | |||

[PSM] To do: Projective coordinates leak. Pointcheval, Smart, | [PSM] (((To do:))) Pointcheval, Smart, Malone-Lee. Projective | |||

Malone-Lee? | coordinates leak. | |||

[BitCoin] To do: BitCoin uses curve secp256k1, which has an | [BitCoin] (((To do:))) BitCoin uses curve secp256k1, which has an | |||

efficient endomorphism. | efficient endomorphism. | |||

[Bleichenbacher] To do: Bleichenbacher showed how to attack DSA | [Bleichenbacher] To do: Bleichenbacher showed how to attack DSA | |||

using a bias in the per-message secrets. | using a bias in the per-message secrets. | |||

[Gordon] To do: Gordon showed how to embed a trapdoor in DSA | [Gordon] (((To do:))) Gordon showed how to embed a trapdoor in DSA | |||

parameters. | parameters. | |||

[HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On | [HPST] Y. Huang, C. Petit, N. Shinohara and T. Takagi. On | |||

Generalized First Fall Degree Assumptions, IACR ePrint 2015. | Generalized First Fall Degree Assumptions, IACR ePrint 2015. | |||

<https://ia.cr/2015/358> | <https://ia.cr/2015/358> | |||

[Nagao] K. Nagao. Equations System coming from Weil descent and | [Nagao] K. Nagao. Equations System coming from Weil descent and | |||

subexponential attack for algebraic curve cryptosystem, IACR | subexponential attack for algebraic curve cryptosystem, IACR | |||

ePrint, 2015. <http://ia.cr/2013/549> | ePrint, 2015. <http://ia.cr/2013/549> | |||

[Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint, | [Teske] E. Teske. An Elliptic Curve Trapdoor System, IACR ePrint, | |||

2003. <http://ia.cr/2003/058> | 2003. <http://ia.cr/2003/058> | |||

[YY] To do: Yung and Young, generalized Gordon's ideas [Gordon] into | Internet-Draft 2019-04-04 | |||

Secretly-embedded trapdoor ... also known as a backdoor. | ||||

Internet-Draft 2018-10-04 | [YY] (((To do:))) Yung and Young, generalized Gordon's ideas | |||

[Gordon] into | ||||

Secretly-embedded trapdoor ... also known as a backdoor. | ||||

Appendix A. Test vectors | Appendix A. Test vectors | |||

To be completed. | To be completed. | |||

Appendix B. Motivation: minimizing the room for backdoors | Appendix B. Motivation: minimizing the room for backdoors | |||

To be completed. | To be completed. | |||

See [AB] and [B1] for some details. | See [AB] and [B1] for some details. | |||

skipping to change at page 20, line 47 ¶ | skipping to change at page 20, line 5 ¶ | |||

pseudocode only for comparison. | pseudocode only for comparison. | |||

Note: the pseudocode relies on some C idioms (hacks?), which might | Note: the pseudocode relies on some C idioms (hacks?), which might | |||

make the pseudocode unclear to those unfamiliar with these idioms. | make the pseudocode unclear to those unfamiliar with these idioms. | |||

Note: this pseudocode was adapted from a few different | Note: this pseudocode was adapted from a few different | |||

experimental prototypes of the author, (which might not be | experimental prototypes of the author, (which might not be | |||

consistent). The pseudocode has not yet received any independent | consistent). The pseudocode has not yet received any independent | |||

review. | review. | |||

Internet-Draft 2019-04-04 | ||||

Note: this pseudocode uses a terse non-conventional coding style, | Note: this pseudocode uses a terse non-conventional coding style, | |||

partly as an exercise in arbitrary source code compression (code | partly as an exercise in arbitrary source code compression (code | |||

golf), but also in the mathematics tradition of using many | golf), but also in the mathematics tradition of using many | |||

single-letter variable names, which enables seeing an entire | single-letter variable names, which enables seeing an entire | |||

formula in a single view and emphasizes the essential mathematical | formula in a single view and emphasizes the essential mathematical | |||

operations rather than the variable's purpose. | operations rather than the variable's purpose. | |||

Internet-Draft 2018-10-04 | ||||

Note: the pseudocode does not use the C operator ^ for bitwise XOR | Note: the pseudocode does not use the C operator ^ for bitwise XOR | |||

of integers, which (luckily) avoid possible confusion with the use | of integers, which (luckily) avoid possible confusion with the use | |||

of ^ as exponentiation operator in the rest of this document. | of ^ as exponentiation operator in the rest of this document. | |||

C.1. Byte encoding | C.1. Byte encoding | |||

Pseudocode for byte representation encoding process is | Pseudocode for byte representation encoding process is | |||

<CODE BEGINS> | <CODE BEGINS> | |||

bite(c b,f x) { | bite(c b,f x) { | |||

skipping to change at page 21, line 46 ¶ | skipping to change at page 21, line 5 ¶ | |||

- type i: 64-bit integers (e.g. entries of f), | - type i: 64-bit integers (e.g. entries of f), | |||

- function mal: multiply a field element by a small integer (result | - function mal: multiply a field element by a small integer (result | |||

stored in 1st argument), | stored in 1st argument), | |||

- function fix: fully reduce an integer modulo 8^91+5, | - function fix: fully reduce an integer modulo 8^91+5, | |||

- function cmp: compare two field element (after fixing), returning | - function cmp: compare two field element (after fixing), returning | |||

-1, 0 or 1. | -1, 0 or 1. | |||

Internet-Draft 2019-04-04 | ||||

Note: The two for-loops in the pseudocode are just radix | Note: The two for-loops in the pseudocode are just radix | |||

conversion, from base 2^55 to base 2^8. Because both bases are | conversion, from base 2^55 to base 2^8. Because both bases are | |||

powers of two, this amount to moving bits around. The entries of | powers of two, this amount to moving bits around. The entries of | |||

array b are compute modulo 256. The second loop copies the bits | array b are compute modulo 256. The second loop copies the bits | |||

that the first loop misses (the bottom bits of each entry of f). | that the first loop misses (the bottom bits of each entry of f). | |||

Note: Encoding is lossy, several different (x,y) may encode to the | Note: Encoding is lossy, several different (x,y) may encode to the | |||

same byte string b. Usually, if (x,y) generated as a part of | same byte string b. Usually, if (x,y) generated as a part of | |||

Diffie--Hellman key exchange, this lossiness has no effect. | Diffie--Hellman key exchange, this lossiness has no effect. | |||

Internet-Draft 2018-10-04 | ||||

Note: Encoding should not be confused with encryption. Encoding | Note: Encoding should not be confused with encryption. Encoding | |||

is merely a conversion or representation process, whose inverse is | is merely a conversion or representation process, whose inverse is | |||

called decoding. | called decoding. | |||

C.2. Byte decoding | C.2. Byte decoding | |||

Pseudocode for decoding is: | Pseudocode for decoding is: | |||

<CODE BEGINS> | <CODE BEGINS> | |||

feed(f x,c b) { | feed(f x,c b) { | |||

skipping to change at page 22, line 43 ¶ | skipping to change at page 22, line 5 ¶ | |||

function 'bite'. The reason the 'bite' needs the 2nd for-loop is | function 'bite'. The reason the 'bite' needs the 2nd for-loop is | |||

due to the lossy conversion from integers to bytes, whereas in the | due to the lossy conversion from integers to bytes, whereas in the | |||

other direction the conversion is not lossy. The second loop | other direction the conversion is not lossy. The second loop | |||

recovers the lost information. | recovers the lost information. | |||

C.3. Fermat inversion | C.3. Fermat inversion | |||

Projective coordinates help avoid costly inversion steps during | Projective coordinates help avoid costly inversion steps during | |||

scalar multiplication. | scalar multiplication. | |||

Internet-Draft 2019-04-04 | ||||

Projective coordinates are not suitable as the final representation | Projective coordinates are not suitable as the final representation | |||

of an elliptic curve point, for two reasons. | of an elliptic curve point, for two reasons. | |||

- Projective coordinates for a point are generally not unique: each | - Projective coordinates for a point are generally not unique: each | |||

point can be represented in projective coordinates in multiple | point can be represented in projective coordinates in multiple | |||

different ways. So, projective coordinates are unsuitable for | different ways. So, projective coordinates are unsuitable for | |||

finalizing a shared secret, because the two parties computing the | finalizing a shared secret, because the two parties computing the | |||

shared secret point may end up with different projective | shared secret point may end up with different projective | |||

coordinates. | coordinates. | |||

Internet-Draft 2018-10-04 | ||||

- Projective coordinates have been shown to leak information about | - Projective coordinates have been shown to leak information about | |||

the scalar multiplier [PSM], which could be the private | the scalar multiplier [PSM], which could be the private | |||

key. It would be unacceptable for a public key to leak | key. It would be unacceptable for a public key to leak | |||

information about the private key. In digital signatures, even a | information about the private key. In digital signatures, even a | |||

few leaked bits can be fatal, over a few signatures | few leaked bits can be fatal, over a few signatures | |||

[Bleichenbacher]. | [Bleichenbacher]. | |||

Therefore, the final computation of an elliptic curve point, after | Therefore, the final computation of an elliptic curve point, after | |||

scalar multiplication, should translate the point to a unique | scalar multiplication, should translate the point to a unique | |||

representation, such as the affine coordinates described in this | representation, such as the affine coordinates described in this | |||

skipping to change at page 23, line 33 ¶ | skipping to change at page 23, line 5 ¶ | |||

The safest, most prudent way to compute 1/Z is to use a side-channel | The safest, most prudent way to compute 1/Z is to use a side-channel | |||

resistant method, in particular at least, a constant-time method. | resistant method, in particular at least, a constant-time method. | |||

This reduces the risk of leaking information about Z, which might in | This reduces the risk of leaking information about Z, which might in | |||

turn leak information about X or the scalar multiplier. Fermat | turn leak information about X or the scalar multiplier. Fermat | |||

inversion, computation of Z^(p-2) mod p, is one method to compute | inversion, computation of Z^(p-2) mod p, is one method to compute | |||

the inverse in constant time (if the inverse exists). | the inverse in constant time (if the inverse exists). | |||

Pseudocode for Fermat inversion is: | Pseudocode for Fermat inversion is: | |||

Internet-Draft 2019-04-04 | ||||

<CODE BEGINS> | <CODE BEGINS> | |||

i inv(f y,f x) { | i inv(f y,f x) { | |||

i j=272;f z; | i j=272;f z; | |||

squ(z,x); | squ(z,x); | |||

mul(y,x,z); | mul(y,x,z); | |||

for(;j--;) squ(z,z); | for(;j--;) squ(z,z); | |||

mul(y,z,y); | mul(y,z,y); | |||

return !!cmp(y,(f){}); | return !!cmp(y,(f){}); | |||

} | } | |||

<CODE ENDS> | <CODE ENDS> | |||

skipping to change at page 24, line 5 ¶ | skipping to change at page 23, line 29 ¶ | |||

faster, but generally run in variable-time. | faster, but generally run in variable-time. | |||

When field elements are sometimes secret keys, using a variable-time | When field elements are sometimes secret keys, using a variable-time | |||

algorithm risk leaking these secrets, and defeating security. | algorithm risk leaking these secrets, and defeating security. | |||

C.4. Branchless Legendre symbol computation | C.4. Branchless Legendre symbol computation | |||

Pseudocode for branchlessly computing if a field element x has a | Pseudocode for branchlessly computing if a field element x has a | |||

square root: | square root: | |||

Internet-Draft 2018-10-04 | ||||

<CODE BEGINS> | <CODE BEGINS> | |||

i has_root(f x) { | i has_root(f x) { | |||

i j=270;f y,z; | i j=270;f y,z; | |||

squ(y,x);squ(z,y); | squ(y,x);squ(z,y); | |||

for(;j--;)squ(z,z); | for(;j--;)squ(z,z); | |||

mul(y,y,z); | mul(y,y,z); | |||

return 0==cmp(y,(f){1}); | return 0==cmp(y,(f){1}); | |||

} | } | |||

<CODE ENDS> | <CODE ENDS> | |||

Note: Legendre symbol is usually most appropriately applied to | Note: Legendre symbol is usually most appropriately applied to | |||

public keys, which mostly obviates the need for side-channel | public keys, which mostly obviates the need for side-channel | |||

resistance. In this case, the implementer can use quadratic | resistance. In this case, the implementer can use quadratic | |||

reciprocity for greater speed. | reciprocity for greater speed. | |||

C.5. Field multiplication and squaring | C.5. Field multiplication and squaring | |||

To be completed. | To be completed. | |||

Internet-Draft 2019-04-04 | ||||

Note (on security): Field multiplication can be achieved most | Note (on security): Field multiplication can be achieved most | |||

quickly by using hardware integer multiplication circuits. It is | quickly by using hardware integer multiplication circuits. It is | |||

critical that those circuits have no bugs or backdoors. | critical that those circuits have no bugs or backdoors. | |||

Furthermore, those circuits typically can only multiple integers | Furthermore, those circuits typically can only multiple integers | |||

smaller than the field elements. Larger inputs to the circuits | smaller than the field elements. Larger inputs to the circuits | |||

will cause overflows. It is critical to avoid these overflows, | will cause overflows. It is critical to avoid these overflows, | |||

not just to avoid interoperability failures, but also to avoid | not just to avoid interoperability failures, but also to avoid | |||

attacks where the attackers supplies inputs likely induce | attacks where the attackers supplies inputs likely induce | |||

overflows [bug attacks], [IT]. The following pseudocode | overflows [bug attacks], [IT]. The following pseudocode | |||

should therefore be considered only for illustrative purposes. | should therefore be considered only for illustrative purposes. | |||

The implementer is responsible for ensuring that inputs cannot | The implementer is responsible for ensuring that inputs cannot | |||

cause overflows or bugs. | cause overflows or bugs. | |||

The pseudocode below for multiplying and squaring: uses unrolled | The pseudocode below for multiplying and squaring: uses unrolled | |||

loops for efficiency, uses refactoring for source code compression, | loops for efficiency, uses refactoring for source code compression, | |||

relies on a compiler optimizer to detect common sub-expressions (in | relies on a compiler optimizer to detect common sub-expressions (in | |||

squaring). | squaring). | |||

Internet-Draft 2018-10-04 | ||||

<CODE BEGINS> | <CODE BEGINS> | |||

#define TRI(m,_)\ | #define TRI(m,_)\ | |||

zz[0]=m(0,0)_(1,4)_(2,3)_(3,2)_(4,1);\ | zz[0]=m(0,0)_(1,4)_(2,3)_(3,2)_(4,1);\ | |||

zz[1]=m(0,1)_(1,0)_(2,4)_(3,3)_(4,2);\ | zz[1]=m(0,1)_(1,0)_(2,4)_(3,3)_(4,2);\ | |||

zz[2]=m(0,2)_(1,1)_(2,0)_(3,4)_(4,3);\ | zz[2]=m(0,2)_(1,1)_(2,0)_(3,4)_(4,3);\ | |||

zz[3]=m(0,3)_(1,2)_(2,1)_(3,0)_(4,4);\ | zz[3]=m(0,3)_(1,2)_(2,1)_(3,0)_(4,4);\ | |||

zz[4]=m(0,4)_(1,3)_(2,2)_(3,1)_(4,0); | zz[4]=m(0,4)_(1,3)_(2,2)_(3,1)_(4,0); | |||

#define CYC(M) ff zz; TRI(+M,-20*M); mod(z,zz); | #define CYC(M) ff zz; TRI(+M,-20*M); mod(z,zz); | |||

#define MUL(j,k) x[j]*(ii)y[k] | #define MUL(j,k) x[j]*(ii)y[k] | |||

#define SQR(j,k) x[j]*(ii)x[k] | #define SQR(j,k) x[j]*(ii)x[k] | |||

skipping to change at page 25, line 34 ¶ | skipping to change at page 25, line 5 ¶ | |||

- #define is used to create macros, which expand within the source | - #define is used to create macros, which expand within the source | |||

code (as in C pre-processing). | code (as in C pre-processing). | |||

- type ii is 128-bit integer | - type ii is 128-bit integer | |||

- multiplying a type i by a type ii variable yields a type ii | - multiplying a type i by a type ii variable yields a type ii | |||

variable. If both inputs can fit into a type i variable, then | variable. If both inputs can fit into a type i variable, then | |||

the result has no overflow or reduction: it is exact as a product | the result has no overflow or reduction: it is exact as a product | |||

of integers. | of integers. | |||

Internet-Draft 2019-04-04 | ||||

- type ff is array of five type ii values. It is used to represent | - type ff is array of five type ii values. It is used to represent | |||

a field in a radix expansion, except the limbs (digits) can be | a field in a radix expansion, except the limbs (digits) can be | |||

128-bits instead of 64-bits. The variable zz has type ff and is | 128-bits instead of 64-bits. The variable zz has type ff and is | |||

used to intermediately store the product of two field element | used to intermediately store the product of two field element | |||

variables x and y (of type f). | variables x and y (of type f). | |||

- function mod takes an ff variable and produce f variable | - function mod takes an ff variable and produce f variable | |||

representing the same field element. A pseudocode example may be | representing the same field element. A pseudocode example may be | |||

defined further below. | defined further below. | |||

skipping to change at page 26, line 5 ¶ | skipping to change at page 25, line 28 ¶ | |||

- How small the limbs of the inputs to function mul and squ must be | - How small the limbs of the inputs to function mul and squ must be | |||

to ensure no overflow occurs? | to ensure no overflow occurs? | |||

- How small are the limbs of the output of functions mul and squ? | - How small are the limbs of the output of functions mul and squ? | |||

C.6. Field element partial reduction | C.6. Field element partial reduction | |||

To be completed. | To be completed. | |||

Internet-Draft 2018-10-04 | ||||

The function mod used by pseudocode function mul and squ above is | The function mod used by pseudocode function mul and squ above is | |||

defined below. | defined below. | |||

<CODE BEGINS> | <CODE BEGINS> | |||

#define QUO(x)(x>>55) | #define QUO(x)(x>>55) | |||

#define MOD(x)(x&((((i)1)<<5)-1)) | #define MOD(x)(x&((((i)1)<<5)-1)) | |||

#define Q(j) QUO(QUO(zz[j])) | #define Q(j) QUO(QUO(zz[j])) | |||

#define P(j) MOD(QUO(zz[j])) | #define P(j) MOD(QUO(zz[j])) | |||

#define R(j) MOD(zz[j]) | #define R(j) MOD(zz[j]) | |||

mod(f z,ff zz){ | mod(f z,ff zz){ | |||

skipping to change at page 26, line 34 ¶ | skipping to change at page 26, line 5 ¶ | |||

} | } | |||

<CODE ENDS> | <CODE ENDS> | |||

TO DO: add notes answering these questions: | TO DO: add notes answering these questions: | |||

- How small must be the input limbs to avoid overflow? | - How small must be the input limbs to avoid overflow? | |||

- How small are the output limbs (to know how to safely use of | - How small are the output limbs (to know how to safely use of | |||

output in further calculations). | output in further calculations). | |||

Internet-Draft 2019-04-04 | ||||

C.7. Field element final reduction | C.7. Field element final reduction | |||

To be completed. | To be completed. | |||

The partial reduction technique is sometimes known as lazy | The partial reduction technique is sometimes known as lazy | |||

reduction. It is an optimization technique. It aims to do only | reduction. It is an optimization technique. It aims to do only | |||

enough calculation to avoid overflow errors. | enough calculation to avoid overflow errors. | |||

For interoperability, field elements need to be fully reduced, | For interoperability, field elements need to be fully reduced, | |||

because partial reduction means the elements still have multiple | because partial reduction means the elements still have multiple | |||

different representations. | different representations. | |||

Pseudocode that aims for final reduction is the following: | Pseudocode that aims for final reduction is the following: | |||

Internet-Draft 2018-10-04 | ||||

<CODE BEGINS> | <CODE BEGINS> | |||

#define FIX(j,r,k) {q=x[j]>>r;\ | #define FIX(j,r,k) {q=x[j]>>r;\ | |||

x[j]-=q<<r; x[(j+1)%5]+=q*k;} | x[j]-=q<<r; x[(j+1)%5]+=q*k;} | |||

fix(f x) { | fix(f x) { | |||

i j,q,t=2; | i j,q,t=2; | |||

for(;t--;) for(j=0;j<5;j++) FIX(j,(j<4?55:53),(j<4?1:-5)); | for(;t--;) for(j=0;j<5;j++) FIX(j,(j<4?55:53),(j<4?1:-5)); | |||

q=x[0]<0; | q=x[0]<0; | |||

x[0]+=q*5; x[4]+=q>>53; | x[0]+=q*5; x[4]+=q>>53; | |||

} | } | |||

<CODE ENDS> | <CODE ENDS> | |||

skipping to change at page 28, line 5 ¶ | skipping to change at page 27, line 5 ¶ | |||

Combining both GLV and Montgomery is also possible, such as | Combining both GLV and Montgomery is also possible, such as | |||

suggested as by Bernstein. | suggested as by Bernstein. | |||

Note: The following pseudocode is not entirely consistent with | Note: The following pseudocode is not entirely consistent with | |||

previous pseudocode examples. | previous pseudocode examples. | |||

Note and Warning: The following pseudocode uses secret indices to | Note and Warning: The following pseudocode uses secret indices to | |||

access (small) arrays. This has a risk of cache-timing attacks. | access (small) arrays. This has a risk of cache-timing attacks. | |||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

<CODE BEGINS> | <CODE BEGINS> | |||

typedef f p[2]; | typedef f p[2]; | |||

typedef struct rung {i x0; i x1; i y; i z;} k[137]; | typedef struct rung {i x0; i x1; i y; i z;} k[137]; | |||

monty_2d (f ps,k sk,f px) { | monty_2d (f ps,k sk,f px) { | |||

i j,h; f z; p w[3],x[3],y[2]={{{},{1}}},z[2]; | i j,h; f z; p w[3],x[3],y[2]={{{},{1}}},z[2]; | |||

fix(px);mal(y[0][0],1,px); | fix(px);mal(y[0][0],1,px); | |||

endomorphism_1_plus_i(z[0],px); | endomorphism_1_plus_i(z[0],px); | |||

endo_i(y[1],y[0]); endo_i(z[1],z[0]); | endo_i(y[1],y[0]); endo_i(z[1],z[0]); | |||

copy(x[1],y[0]); copy(x[2],z[0]); | copy(x[1],y[0]); copy(x[2],z[0]); | |||

skipping to change at page 29, line 5 ¶ | skipping to change at page 28, line 5 ¶ | |||

To be completed. | To be completed. | |||

This pseudocode would show how to use to scalar multiplication, | This pseudocode would show how to use to scalar multiplication, | |||

combined with point validation, and so on. | combined with point validation, and so on. | |||

C.10. Elligator i | C.10. Elligator i | |||

To be completed. | To be completed. | |||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

This pseudocode would show how to implement to the Elligator i map | This pseudocode would show how to implement to the Elligator i map | |||

from byte strings to points. | from byte strings to points. | |||

Pseudocode (to be verified): | Pseudocode (to be verified): | |||

<CODE BEGINS> | <CODE BEGINS> | |||

typedef f xy[2] ; | typedef f xy[2] ; | |||

#define X p[0] | #define X p[0] | |||

#define Y p[1] | #define Y p[1] | |||

skipping to change at page 30, line 5 ¶ | skipping to change at page 29, line 5 ¶ | |||

mal(t,3,t); // 3/(i-x) | mal(t,3,t); // 3/(i-x) | |||

add(t,I,t); // i+ 3/(i-x) | add(t,I,t); // i+ 3/(i-x) | |||

mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i | mal(t,-1,t); // -i-3/(i-x)) = (1-3i/(i-x))/i | |||

b = root(r,t) ; | b = root(r,t) ; | |||

fix(r); | fix(r); | |||

h = (r[4]<(1LL<<52)) ; | h = (r[4]<(1LL<<52)) ; | |||

mal(r,2*h-1,r); | mal(r,2*h-1,r); | |||

fix(r); | fix(r); | |||

} | } | |||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

elligator(xy p,c b) {f r; feed(r,b); lift(p,r);} | elligator(xy p,c b) {f r; feed(r,b); lift(p,r);} | |||

crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);} | crocodile(c b,xy p) {f r; drop(r,p); bite(b,r);} | |||

<CODE ENDS> | <CODE ENDS> | |||

D. Primality proofs and certificates | D. Primality proofs and certificates | |||

In most cases, probablistic primality tests, if conducted properly, | Recent work of Albrecht and others [AMPS] has shown the combination | |||

can ensure more than adequate security. But recent work of Albrecht | of adversarially chosen prime and improper probabilistic primality | |||

and others [AMPS] has shown the combination of adversarially chosen | tests can result in attacks. | |||

prime and improper probabilistic primality tests can result in | ||||

attacks. | ||||

Three countermeasures to the attacks in [AMPS] are (1) using proper | ||||

probabilistic prime tests, (2) using provable prime tests, and (3) | ||||

using nothing-up-my-sleeve primes which seem immune to the [AMPS] | ||||

attack. | ||||

It seems that field size 8^91+5 should already resist [AMPS] based | ||||

on the third countermeasure (its especially compact representation). | ||||

This document cannot really accomplish the first countermeasure, | ||||

because the first countermeasure requires fresh randomness for each | ||||

test. This document can help with the second countermeasure by | ||||

providing primality certificate. | ||||

A primality certificate is essentially a rapidly verifiable proof of | The two primes involved for 2y^2=x^3+x/GF(8^91+5) should already | |||

primality. More precisely, it involves some rigorous logic and and | resist [AMPS] because compact representation of these primes. | |||

some calculations. The calculations, although too tedious to be | ||||

done by hand, have a cost that is polynomial time, and usually | ||||

amounting only to some number of modular expontiations, with the | ||||

number comparable to the bit length of the prime being tested. | ||||

Typically, generation of the primality certificate is much more | For further assurance, this section provides Pratt primality | |||

costly than verifying it: generation is not polynomial-time. For | certificates for the two primes. | |||

example, Pratt certificates require the factorization of p-1, which | ||||

is typically expensive for large primes. Nevertheless, for the | ||||

prime 8^91+5, software exists that can generate a Pratt certificate | ||||

in minutes on a personal computer. Yet other kinds of primality | ||||

certificates (those using elliptic curves) can be generated even | ||||

more quickly, except their verification requires an elliptic curve | ||||

implementation, and uses less elementary rigor in their proofs. | ||||

For these reasons, a primality certificate for primes of size 8^91+5 | Note: Recall that every prime p has a unique Pratt certificate, | |||

is nearly redundant. Nonetheless, it does not hurt to provide the | which consists of the factorization of p into primes, and, | |||

proofs within this curve, if only for completeness. | recursively, Pratt primality certificates for each of those | |||

primes. Verification of a Pratt certificates is also recursive: | ||||

it uses the factorization data to conduct Fermat and Lehmer | ||||

tests, which together verify primality. | ||||

D.1 Pratt certificate for the field size 8^91+5 | D.1. Pratt certificate for the field size 8^91+5 | |||

Internet-Draft 2018-10-04 | ||||

Define 52 positive integers, a,b,c,...,z,A,...,Z as follows: | Define 52 positive integers, a,b,c,...,z,A,...,Z as follows: | |||

a=2 b=1+a c=1+aa d=1+ab e=1+ac f=1+aab g=1+aaaa h=1+abb i=1+ae | a=2 b=1+a c=1+aa d=1+ab e=1+ac f=1+aab g=1+aaaa h=1+abb i=1+ae | |||

j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag | j=1+aaac k=1+abd l=1+aaf m=1+abf n=1+aacc o=1+abg p=1+al q=1+aaag | |||

r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi | r=1+abcc s=1+abbbb t=1+aak u=1+abbbc v=1+ack w=1+aas x=1+aabbi | |||

y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA | y=1+aco z=1+abu A=1+at B=1+aaaadh C=1+acu D=1+aaav E=1+aeff F=1+aA | |||

G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt | G=1+aB H=1+aD I=1+acx J=1+aaacej K=1+abqr L=1+aabJ M=1+aaaaaabdt | |||

N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM | N=1+abdpw O=1+aaaabmC P=1+aabeK Q=1+abcfgE R=1+abP S=1+aaaaaaabcM | |||

T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW | T=1+aIO U=1+aaaaaduGS V=1+aaaabbnuHT W=1+abffLNQR X=1+afFW | |||

Y=1+aaaaauX Z=1+aabzUVY. | Y=1+aaaaauX Z=1+aabzUVY. | |||

Note: variable concatentation is used to indicate multiplication. | Note: variable concatenation is used to indicate multiplication. | |||

For example, f = 1+aab = 1+2*2*(1+2) = 13. This brevity was only | For example, f = 1+aab = 1+2*2*(1+2) = 13. | |||

possible by a fluke: only 52 integers were needed, obviating the | ||||

need for multi-letter variable names. | ||||

Note: the information above can suffice as a Pratt certificate for | ||||

the primality of Z, but only if the following further sequence of | ||||

computations are done. (The information suffices because it | ||||

deducibly implies the sequence of computations.) | ||||

Writing % for modular reduction (with lower precedence than | Note: Writing % for modular reduction (with lower precedence than | |||

exponention ^), verify that following 51 modular exponentiations all | exponentiation ^), a first step in verifying the Pratt certificate | |||

result in value 1: | is a Fermat pseudoprime test for each prime in the list, meaning | |||

the all the numbers below are 1: | ||||

2^(b-1)%b, 2^(c-1)%c, 3^(d-1)%d, 2^(e-1)%e, 2^(f-1)%f, 3^(g-1)%g, | Internet-Draft 2019-04-04 | |||

2^(h-1)%h, 5^(i-1)%i, 6^(j-1)%j, 3^(k-1)%k, 2^(l-1)%l, 3^(m-1)%m, | ||||

2^(n-1)%n, 5^(o-1)%o, 2^(p-1)%p, 3^(q-1)%q, 6^(r-1)%r, 2^(s-1)%s, | ||||

2^(t-1)%t, 6^(u-1)%u, 7^(v-1)%v, 2^(w-1)%w, 2^(x-1)%x, 14^(y-1)%y, | ||||

3^(z-1)%z, 5^(A-1)%A, 3^(B-1)%B, 7^(C-1)%C, 3^(D-1)%D, 7^(E-1)%E, | ||||

5^(F-1)%F, 2^(G-1)%G, 2^(H-1)%H, 2^(I-1)%I, 3^(J-1)%J, 2^(K-1)%K, | ||||

2^(L-1)%L, 10^(M-1)%M, 5^(N-1)%N, 10^(O-1)%O, 2^(P-1)%P, | ||||

10^(Q-1)%Q, 6^(R-1)%R, 7^(S-1)%S, 5^(T-1)%T, 3^(U-1)%U, 5^(V-1)%V, | ||||

2^(W-1)%W, 2^(X-1)%X, 3^(Y-1)%Y, 7^(Z-1)%Z. | ||||

This shows that b,c,...,Z are Fermat pseudoprimes to the Fermat | 2^(b-1)%b, 2^(c-1)%c, 3^(d-1)%d, 2^(e-1)%e, 2^(f-1)%f, 3^(g-1)%g, | |||

bases indicated (for example, Z is a Fermat pseudoprime to Fermat | 2^(h-1)%h, 5^(i-1)%i, 6^(j-1)%j, 3^(k-1)%k, 2^(l-1)%l, 3^(m-1)%m, | |||

base 7). | 2^(n-1)%n, 5^(o-1)%o, 2^(p-1)%p, 3^(q-1)%q, 6^(r-1)%r, 2^(s-1)%s, | |||

2^(t-1)%t, 6^(u-1)%u, 7^(v-1)%v, 2^(w-1)%w, 2^(x-1)%x, 14^(y-1)%y, | ||||

3^(z-1)%z, 5^(A-1)%A, 3^(B-1)%B, 7^(C-1)%C, 3^(D-1)%D, 7^(E-1)%E, | ||||

5^(F-1)%F, 2^(G-1)%G, 2^(H-1)%H, 2^(I-1)%I, 3^(J-1)%J, 2^(K-1)%K, | ||||

2^(L-1)%L, 10^(M-1)%M, 5^(N-1)%N, 10^(O-1)%O, 2^(P-1)%P, | ||||

10^(Q-1)%Q, 6^(R-1)%R, 7^(S-1)%S, 5^(T-1)%T, 3^(U-1)%U, 5^(V-1)%V, | ||||

2^(W-1)%W, 2^(X-1)%X, 3^(Y-1)%Y, 7^(Z-1)%Z. | ||||

Note: Each Fermat base above was chosen as the minimal possible | Note: Each Fermat base above was chosen as the minimal possible | |||

value. These bases can be deduced from b,c,...,Z by searching | value. These bases can be deduced from b,c,...,Z by searching | |||

bases 2,3,4,... until a Fermat is found. The results of these | bases 2,3,4,... until a Fermat is found. The results of these | |||

search are included above for convenience. | search are included above for convenience. | |||

Verify that a is prime (because it is just two). | Note: A second step to verifying a Pratt certificate is to apply | |||

Lehmer's theorem to each Fermat psuedoprime. To prove b,c,d,...,Z | ||||

Internet-Draft 2018-10-04 | are prime, it now suffices to verify that all of following 154 | |||

modular exponentiations result in a value different from 1. | ||||

Lehmer's theorem provides the Lehmer test that a Fermat pseudoprime | ||||

is prime: if the Fermat base raised to each integer power of the | ||||

form (pseudoprime-1)/(a prime factor) is not congruent to 1 modulo | ||||

the pseudoprime. Consequently, to prove b,c,d,...,Z are prime, it | ||||

suffices to do all the necessary Lehmer tests, which means to verify | ||||

that all of following 154 modular exponentiations result in a value | ||||

different from 1. | ||||

2^((b-1)/a)%b, 2^((c-1)/a)%c, 3^((d-1)/a)%d, 3^((d-1)/b)%d, | ||||

2^((e-1)/a)%e, 2^((e-1)/c)%e, 3^((f-1)/a)%f, 3^((f-1)/b)%f, | ||||

3^((g-1)/a)%g, 2^((h-1)/a)%h, 2^((h-1)/b)%h, 5^((i-1)/a)%i, | ||||

5^((i-1)/e)%i, 6^((j-1)/a)%j, 6^((j-1)/c)%j, 3^((k-1)/a)%k, | ||||

2^((l-1)/a)%l, 2^((l-1)/f)%l, 3^((m-1)/a)%m, 3^((m-1)/b)%m, | ||||

3^((m-1)/f)%m, 2^((n-1)/a)%n, 2^((n-1)/c)%n, 5^((o-1)/a)%o, | ||||

5^((o-1)/b)%o, 5^((o-1)/f)%o, 2^((p-1)/a)%p, 2^((p-1)/l)%p, | ||||

3^((q-1)/a)%q, 3^((q-1)/g)%q, 6^((r-1)/a)%r, 6^((r-1)/a)%r, | ||||

2^((s-1)/a)%s, 2^((s-1)/b)%s, 2^((t-1)/a)%t, 2^((t-1)/k)%t, | ||||

6^((u-1)/a)%u, 6^((u-1)/b)%u, 6^((u-1)/c)%u, 7^((v-1)/a)%v, | ||||

7^((v-1)/c)%v, 7^((v-1)/k)%v, 2^((w-1)/a)%w, 2^((w-1)/s)%w, | ||||

2^((x-1)/a)%x, 2^((x-1)/b)%x, 2^((x-1)/i)%x, 14^((y-1)/a)%y, | ||||

14^((y-1)/c)%y, 14^((y-1)/o)%y, 3^((z-1)/a)%z, 3^((z-1)/b)%z, | ||||

3^((z-1)/u)%z, 5^((A-1)/a)%A, 5^((A-1)/t)%A, 3^((B-1)/a)%B, | ||||

3^((B-1)/d)%B, 3^((B-1)/h)%B, 7^((C-1)/a)%C, 7^((C-1)/c)%C, | ||||

7^((C-1)/u)%C, 3^((D-1)/a)%D, 3^((D-1)/v)%D, 7^((E-1)/a)%E, | ||||

7^((E-1)/e)%E, 7^((E-1)/f)%E, 5^((F-1)/a)%F, 5^((F-1)/A)%F, | ||||

2^((G-1)/a)%G, 2^((G-1)/B)%G, 2^((H-1)/a)%H, 2^((H-1)/D)%H, | ||||

2^((I-1)/a)%I, 2^((I-1)/c)%I, 2^((I-1)/x)%I, 3^((J-1)/a)%J, | ||||

3^((J-1)/c)%J, 3^((J-1)/e)%J, 3^((J-1)/j)%J, 2^((K-1)/a)%K, | ||||

2^((K-1)/b)%K, 2^((K-1)/q)%K, 2^((K-1)/r)%K, 2^((L-1)/a)%L, | ||||

2^((L-1)/b)%L, 2^((L-1)/J)%L, 10^((M-1)/a)%M, 10^((M-1)/b)%M, | ||||

10^((M-1)/d)%M, 10^((M-1)/t)%M, 5^((N-1)/a)%N, 5^((N-1)/b)%N, | ||||

5^((N-1)/d)%N, 5^((N-1)/p)%N, 5^((N-1)/w)%N, 10^((O-1)/a)%O, | ||||

10^((O-1)/b)%O, 10^((O-1)/m)%O, 10^((O-1)/C)%O, 2^((P-1)/a)%P, | ||||

2^((P-1)/b)%P, 2^((P-1)/e)%P, 2^((P-1)/K)%P, 10^((Q-1)/a)%Q, | ||||

10^((Q-1)/b)%Q, 10^((Q-1)/c)%Q, 10^((Q-1)/f)%Q, 10^((Q-1)/g)%Q, | ||||

10^((Q-1)/E)%Q, 6^((R-1)/a)%R, 6^((R-1)/b)%R, 6^((R-1)/P)%R, | ||||

7^((S-1)/a)%S, 7^((S-1)/b)%S, 7^((S-1)/c)%S, 7^((S-1)/M)%S, | ||||

5^((T-1)/a)%T, 5^((T-1)/I)%T, 5^((T-1)/O)%T, 3^((U-1)/a)%U, | ||||

3^((U-1)/d)%U, 3^((U-1)/u)%U, 3^((U-1)/G)%U, 3^((U-1)/S)%U, | ||||

5^((V-1)/a)%V, 5^((V-1)/b)%V, 5^((V-1)/n)%V, 5^((V-1)/u)%V, | ||||

5^((V-1)/H)%V, 5^((V-1)/T)%V, 2^((W-1)/a)%W, 2^((W-1)/b)%W, | ||||

2^((W-1)/f)%W, 2^((W-1)/L)%W, 2^((W-1)/N)%W, 2^((W-1)/Q)%W, | ||||

2^((W-1)/R)%W, 2^((X-1)/a)%X, 2^((X-1)/f)%X, 2^((X-1)/F)%X, | ||||

2^((X-1)/W)%X, 3^((Y-1)/a)%Y, 3^((Y-1)/u)%Y, 3^((Y-1)/X)%Y, | ||||

7^((Z-1)/a)%Z, 7^((Z-1)/b)%Z, 7^((Z-1)/z)%Z, 7^((Z-1)/U)%Z, | ||||

7^((Z-1)/V)%Z, 7^((Z-1)/Y)%Z. | ||||

Internet-Draft 2018-10-04 | ||||

Note: Each base above is the same as the base in the previous | ||||

Fermat pseudoprime stage, and each list of prime factors is | ||||

deduced from the definition of positive integers b,c,...,Z. The | ||||

consistency between these stages of the proof must be verified for | ||||

rigor. For example, the Fermat base for Z was 7, and the | ||||

factorization of Z-1 was aabzUVY, so we must test 7^((Z-1)/a)%Z, | ||||

7^((Z-1)/b)%Z, ..., 7^((Z-1)/Y)%Z. | ||||

This proves that a,b,...,Z are primes. | ||||

Verify that Z=8^91+5 to conclude that 8^91+5 is prime. | Internet-Draft 2019-04-04 | |||

Note: the Pratt certificate is essentially unique for each prime. | 2^((b-1)/a)%b, 2^((c-1)/a)%c, 3^((d-1)/a)%d, 3^((d-1)/b)%d, | |||

The presentation above is for illustrative purposes: the | 2^((e-1)/a)%e, 2^((e-1)/c)%e, 3^((f-1)/a)%f, 3^((f-1)/b)%f, | |||

formatting is not intended for an automated verification. A | 3^((g-1)/a)%g, 2^((h-1)/a)%h, 2^((h-1)/b)%h, 5^((i-1)/a)%i, | |||

sensible automation of the verification would simply generate the | 5^((i-1)/e)%i, 6^((j-1)/a)%j, 6^((j-1)/c)%j, 3^((k-1)/a)%k, | |||

154 Lehmer tests from integer definitions and the Fermat | 2^((l-1)/a)%l, 2^((l-1)/f)%l, 3^((m-1)/a)%m, 3^((m-1)/b)%m, | |||

pseudoprime tests, rather than rely on the listing provided above. | 3^((m-1)/f)%m, 2^((n-1)/a)%n, 2^((n-1)/c)%n, 5^((o-1)/a)%o, | |||

With only slightly greater cost, the Fermat pseudoprime test can | 5^((o-1)/b)%o, 5^((o-1)/f)%o, 2^((p-1)/a)%p, 2^((p-1)/l)%p, | |||

be derived from integers, by a separate search for each Fermat | 3^((q-1)/a)%q, 3^((q-1)/g)%q, 6^((r-1)/a)%r, 6^((r-1)/a)%r, | |||

base. | 2^((s-1)/a)%s, 2^((s-1)/b)%s, 2^((t-1)/a)%t, 2^((t-1)/k)%t, | |||

6^((u-1)/a)%u, 6^((u-1)/b)%u, 6^((u-1)/c)%u, 7^((v-1)/a)%v, | ||||

7^((v-1)/c)%v, 7^((v-1)/k)%v, 2^((w-1)/a)%w, 2^((w-1)/s)%w, | ||||

2^((x-1)/a)%x, 2^((x-1)/b)%x, 2^((x-1)/i)%x, 14^((y-1)/a)%y, | ||||

14^((y-1)/c)%y, 14^((y-1)/o)%y, 3^((z-1)/a)%z, 3^((z-1)/b)%z, | ||||

3^((z-1)/u)%z, 5^((A-1)/a)%A, 5^((A-1)/t)%A, 3^((B-1)/a)%B, | ||||

3^((B-1)/d)%B, 3^((B-1)/h)%B, 7^((C-1)/a)%C, 7^((C-1)/c)%C, | ||||

7^((C-1)/u)%C, 3^((D-1)/a)%D, 3^((D-1)/v)%D, 7^((E-1)/a)%E, | ||||

7^((E-1)/e)%E, 7^((E-1)/f)%E, 5^((F-1)/a)%F, 5^((F-1)/A)%F, | ||||

2^((G-1)/a)%G, 2^((G-1)/B)%G, 2^((H-1)/a)%H, 2^((H-1)/D)%H, | ||||

2^((I-1)/a)%I, 2^((I-1)/c)%I, 2^((I-1)/x)%I, 3^((J-1)/a)%J, | ||||

3^((J-1)/c)%J, 3^((J-1)/e)%J, 3^((J-1)/j)%J, 2^((K-1)/a)%K, | ||||

2^((K-1)/b)%K, 2^((K-1)/q)%K, 2^((K-1)/r)%K, 2^((L-1)/a)%L, | ||||

2^((L-1)/b)%L, 2^((L-1)/J)%L, 10^((M-1)/a)%M, 10^((M-1)/b)%M, | ||||

10^((M-1)/d)%M, 10^((M-1)/t)%M, 5^((N-1)/a)%N, 5^((N-1)/b)%N, | ||||

5^((N-1)/d)%N, 5^((N-1)/p)%N, 5^((N-1)/w)%N, 10^((O-1)/a)%O, | ||||

10^((O-1)/b)%O, 10^((O-1)/m)%O, 10^((O-1)/C)%O, 2^((P-1)/a)%P, | ||||

2^((P-1)/b)%P, 2^((P-1)/e)%P, 2^((P-1)/K)%P, 10^((Q-1)/a)%Q, | ||||

10^((Q-1)/b)%Q, 10^((Q-1)/c)%Q, 10^((Q-1)/f)%Q, 10^((Q-1)/g)%Q, | ||||

10^((Q-1)/E)%Q, 6^((R-1)/a)%R, 6^((R-1)/b)%R, 6^((R-1)/P)%R, | ||||

7^((S-1)/a)%S, 7^((S-1)/b)%S, 7^((S-1)/c)%S, 7^((S-1)/M)%S, | ||||

5^((T-1)/a)%T, 5^((T-1)/I)%T, 5^((T-1)/O)%T, 3^((U-1)/a)%U, | ||||

3^((U-1)/d)%U, 3^((U-1)/u)%U, 3^((U-1)/G)%U, 3^((U-1)/S)%U, | ||||

5^((V-1)/a)%V, 5^((V-1)/b)%V, 5^((V-1)/n)%V, 5^((V-1)/u)%V, | ||||

5^((V-1)/H)%V, 5^((V-1)/T)%V, 2^((W-1)/a)%W, 2^((W-1)/b)%W, | ||||

2^((W-1)/f)%W, 2^((W-1)/L)%W, 2^((W-1)/N)%W, 2^((W-1)/Q)%W, | ||||

2^((W-1)/R)%W, 2^((X-1)/a)%X, 2^((X-1)/f)%X, 2^((X-1)/F)%X, | ||||

2^((X-1)/W)%X, 3^((Y-1)/a)%Y, 3^((Y-1)/u)%Y, 3^((Y-1)/X)%Y, | ||||

7^((Z-1)/a)%Z, 7^((Z-1)/b)%Z, 7^((Z-1)/z)%Z, 7^((Z-1)/U)%Z, | ||||

7^((Z-1)/V)%Z, 7^((Z-1)/Y)%Z. | ||||

Note: A reader who wishes to verify, with greatest certainty, that | Note: The verifier should verify that each base in the Fermat and | |||

8^91+5 is prime, would be probably be most convinced by running a | Lehmer test are equal. For example, the Fermat base for Z was 7, | |||

provable prime test entirely independent of this document and the | and the factorization of Z-1 was aabzUVY, so the Lehmer theorem | |||

primality certificate given in this section. | test 7^((Z-1)/a)%Z, 7^((Z-1)/b)%Z, ..., 7^((Z-1)/Y)%Z. | |||

Note: the most expensive step in generating the Pratt certificate | Note: The final step is to verify that Z=8^91+5. | |||

for 8^91+5 was factoring the integer 8^91+4 = Z-1 = aabzUVY. The | ||||

other integers were generated in reverse alphabetical order, as | ||||

Y,X,...,c,b,a, with each integer appearing as an (seemingly) prime | ||||

factor of one less than number previously computed. All | ||||

subsequent integer factorizations took time negligible compared to | ||||

the factorization of Z-1. | ||||

Internet-Draft 2018-10-04 | Internet-Draft 2019-04-04 | |||

Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3, | Note: The decimal values for a,b,c,...,Y are given by: a=2, b=3, | |||

c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79, | c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=41, k=43, l=53, m=79, | |||

n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431, | n=101, o=103, p=107, q=137, r=151, s=163, t=173, u=271, v=431, | |||

w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449, | w=653, x=829, y=1031, z=1627, A=2063, B=2129, C=2711, D=3449, | |||

E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123, | E=3719, F=4127, G=4259, H=6899, I=8291, J=18041, K=124123, | |||

L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971, | L=216493, M=232513, N=2934583, O=10280113, P=16384237, Q=24656971, | |||

R=98305423, S=446424961, T=170464833767, U=115417966565804897, | R=98305423, S=446424961, T=170464833767, U=115417966565804897, | |||

V=4635260015873357770993, W=1561512307516024940642967698779, | V=4635260015873357770993, W=1561512307516024940642967698779, | |||

X=167553393621084508180871720014384259, | X=167553393621084508180871720014384259, | |||

Y=1453023029482044854944519555964740294049. If the reader has a | Y=1453023029482044854944519555964740294049. | |||

tool to generate a Pratt certificate (with decimal notation), the | ||||

reader should be able to find these numbers in the Pratt | ||||

certifcate for 8^91+5. (Since Pratt certificate generation is | ||||

slower than for other primality certificate types, some tools | ||||

require special configuration to generate a Pratt certificate.) | ||||

Note: the Pratt certificate for 8^91+5 might not be shortest | ||||

possible primality certificate (under some measure of length), but | ||||

optimizing the shortness of a primality certificate seems to add | ||||

little value. | ||||

D.2 Pratt certificate for size of the large elliptic curve subgroup | D.2. Pratt certificate for subgroup order | |||

Using the same verification strategy of the previous strategy, but | Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new | |||

now with 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new | values: | |||

definitions: | ||||

a=2 b=1+a c=1+a2 d=1+ab e=1+ac f=1+a2b g=1+a4 h=1+ab2 i=1+ae | a=2 b=1+a c=1+a2 d=1+ab e=1+ac f=1+a2b g=1+a4 h=1+ab2 i=1+ae | |||

j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b | j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b | |||

r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e | r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e | |||

z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck | z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck | |||

G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG | G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG | |||

O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ | O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ | |||

V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY! | V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Z=1+ab3oHOT !=1+a3SUX @=1+abNY! | |||

#=1+a4kzF@ $=1+a3QZ# | #=1+a4kzF@ $=1+a3QZ# | |||

Note: numeral after variable names represent powers. For example, | Note: numeral after variable names represent powers. For example, | |||

f = 1 + a2b = 1 + 2^2 * 3 = 13. | f = 1 + a2b = 1 + 2^2 * 3 = 13. | |||

Note: The use of punctuation for variable names !,@,#,$, does not | Note: The same process (Fermat and Lehmer tests) verifies that $ | |||

scale (or fit into most programming languages), so is really just | is prime. This process includes search for bases for each of the | |||

a hack to avoid a multiplication operator. | prime. These bases have not been included in the certificate. | |||

A routine but tedious verification (Fermat and Lehmer tests) | ||||

converts the information above into a proof that $ is prime. (The | ||||

information above, obtained by repeated factorization, is also | ||||

routine, but more computatinally expensive, because it involves | ||||

integer factorization.) | ||||

Internet-Draft 2018-10-04 | ||||

The last variable, $, is the order of the base point, and the order | The last variable, $, is the order of the base point, and the order | |||

of the curve is 72$. | of the curve is 72$. | |||

Note: Punctuation used for variable names !,@,#,$, would not scale | ||||

for larger primes. For larger primes, a similar format might work | ||||

by using a prefix-free set of multil-letter variable names. | ||||

E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze: | ||||

Internet-Draft 2019-04-04 | ||||

a=2 b=1+a c=1+a2 d=1+ab e=1+ac f=1+a2b g=1+a4 h=1+ab2 i=1+ae | ||||

j=1+a2d k=1+a3c l=1+abd m=1+a2f n=1+acd o=1+a3b2 p=1+ak q=1+a5b | ||||

r=1+a2c2 s=1+am t=1+ab2d u=1+abi v=1+ap w=1+a2l x=1+abce y=1+a5e | ||||

z=1+a2t A=1+a3bc2 B=1+a7c C=1+agh D=1+a2bn E=1+a7b2 F=1+abck | ||||

G=1+a5bf H=1+aB I=1+aceg J=1+a3bc3 K=1+abA L=1+abD M=1+abcx N=1+acG | ||||

O=1+aqs P=1+aqy Q=1+abrv R=1+ad2eK S=1+a3bCL T=1+a2bewM U=1+aijsJ | ||||

V=1+auEP W=1+agIR X=1+a2bV Y=1+a2cW Za=1+ab3oHOT Zb=1+a3SUX | ||||

Zc=1+abNYZb Zd=1+a4kzFZc Ze=1+a3QZaZd | ||||

When parsing this, say 2nd last item Zd=1+a4kzFZc, the string Zd on | ||||

the left of = defines a new variables, while the string on the | ||||

right = gives its value. The string a4kzFZc can be unambiguously | ||||

parsed as a^4*k*z*F*Zc, scanning from left to right for previous | ||||

variables, or integers as powers. | ||||

Acknowledgments | Acknowledgments | |||

Thanks to John Goyo and various other BlackBerry employees for past | Thanks to John Goyo and various other BlackBerry employees for past | |||

technical review, to Gaelle Martin-Cocher for encouraging | technical review, to Gaelle Martin-Cocher for encouraging submission | |||

submission of this I-D. Thanks to David Jacobson for sending me | of this I-D. Thanks to David Jacobson for sending Pratt primality | |||

Pratt primality certificates (generated with mathetmatic, and | certificates. | |||

re-generated by me). | ||||

Author's Address | Author's Address | |||

Dan Brown | Dan Brown | |||

4701 Tahoe Blvd. | 4701 Tahoe Blvd. | |||

BlackBerry, 5th Floor | BlackBerry, 5th Floor | |||

Mississauga, ON | Mississauga, ON | |||

Canada | Canada | |||

danibrown@blackberry.com | danibrown@blackberry.com | |||

End of changes. 134 change blocks. | ||||

627 lines changed or deleted | | 463 lines changed or added | ||

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |