< 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/