```
p = 8^91+5
u = 104303302790113346778702926977288705144769
v = 65558536801757875228360405858731806281506
if ( p != u^2+v^2 ) { "u and v incorrect" ; halt }
s = (u+1)^2 + v^2
if ( 0 != (s % 72)) { "size not divisible by 72" ; halt}
q = s/72
q
``````
Note: Theory only indicates that s has one of four values, so an
extra step is needed to verify which of the four values is the
size. Scalar multiplication by s is a general method. A faster
method, which happens to work for 2y^2=x^3+x/GF(8^91+5), is to
show that only one of the four candidate sizes is divisible by 3,
and then demonstrate a point of order 3 on this curve. Symbolic
calculation with elliptic curve arithmetic show that the point
(x,y) has order 3 if 3x^4 + 1 = 0 in GF(p). The big integer
calculation (-(1+2p)/3)^((p-1)/4) = 1 mod p shows that such an x
exists in GF(p).
Note: The Schoof-Elkies-Atkin (SEA) point-counting algorithm can
compute the size of any general curve, but is slower than methods
for some special curves, which is why Miller had already suggested
in 1985 to use special curves with equation y^2=x^3-ax. Miller
suggested using supersingular curves, but restriction of the
coefficient a, but those curves are insecure. Instead, we have
chosen a different a (in this case a=-1 is isomorphic to
2y^2=x^3+x), which is not supersingular, but still has much easier
point counting than the generic SEA algorithm.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 47]
Internet-Draft March 21, 2022
A.4.3.2. Pollard Rho Security
The prime q is 267-bit number. The Pollard rho algorithm for
discrete logarithm to the base G (or any order q point) takes
(proportional to) sqrt(q) ~ 2^133 elliptic curve operations. The
curve provides at least 2^128 security against Pollard rho attacks,
with about 5 bits to spare.
Note: Arguably, the fact ECC operations are slower than
symmetric-key operations (such as hashing or block ciphers), means
that ECC security can reasonably be granted a few extra bits of
security, perhaps 5-10 bits, when trying to match ECC security
with symmetric-key security. In this case, one might say that
2y^2=x^3+x/GF(8^91+5) resists Pollard-rho with 2^140 security,
providing 12 bits of extra security. The extra security can be
viewed as a safety margin for error, or as an excessive to the
extent the smaller, and faster curves would more than suffice to
match 2^128 security of SHA-256 and AES-128.
Gallant, Lambert, Vanstone, show how to speed up Pollard rho
algorithms when the group has an extra endomorphism, which would
apply to 2y^2=x^3+x. The speed-up here amounts to a couple of bits
in the security,
A.4.3.3. Pohlig-Hellman Security
The small cofactor means the curve effectively resists
Pohlig-Hellman attack (a generic algorithm to solve discrete
logarithms in any group in time sqrt(m) where m is the largest
prime factor of the group size).
Note: Consensus in ECC is to use a small factor, such as 1, 2, 4,
or 8, despite the fact that, for random curves, the typical
cofactor is approximately p^(1/3), which is much larger. The
small cofactor helps resists Pohlig-Hellman without increasing the
field size. (A larger field size would be less efficient.)
A.4.3.4. Menezes-Okamoto-Vanstone Security
The curve has a large embedding degree. More precisely, the curve
size 72q has q with embedding degree (q-1)/2.
This means that the discrete logarithms to base G (a point of order
q) resist Menezes-Okamoto-Vanstone attack.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 48]
Internet-Draft March 21, 2022
The large embedding degree also means that that no feasible pairings
exist that could be used solve the decision Diffie-Hellman problem
(for points of order q). Similarly, the larger embedding degree
also means, it cannot be used for pairing-based cryptography (and it
would already too small to be used for pairing-based cryptography).
Note: Intuitively, a near-miss or a close-call could describe this
curve's resistance to the MOV attack. For about half of all
primes P, then curve 2y^2=x^3+x is supersingular over GF(P), with
embedding degree 2, making them vulnerable to the MOV attack
reduces the elliptic curve discrete logarithm to the finite field
discrete logarithm over GF(P^2). Miller suggested in 1985 to use
isomorphic equations, y^2=x^3-ax, without knowing about the 1992
MOV attack. These special curves would then be vulnerable with
~50% chance of being, depending on the prime P. This curve was
chosen in full knowledge of the MOV attack.
Note: The near-miss or close-call intuition is misleading, because
many cryptographic algorithms become insecure based on the
slightest adjustment to the algorithm.
Note: The non-supersingularity means that the endomorphism ring is
commutative. For this curve the endomorphism ring is isomorphic
to the ring Z[i] of Gaussian integers.
A.4.3.5. Semaev-Araki-Satoh-Smart Security
The fact that the curve size 72q does not equal p, means that the
curve resists the Semaev-Araki-Satoh-Smart attack.
A.4.3.6. Edwards and Hessian Form
The cofactor 72 is divisible by 4, so the curve isomorphic to a
curve with an Edwards equation, permitting implementation even more
efficient than the Montgomery ladder.
The Edwards form makes possible the Gallant-Lambert-Vanstone
method that used the efficient endomorphism.
The cofactor 72 is also divisible by 3, so the curve is isomorphic
to a curve with a Hessian equation, which is another type of
equation permitting efficient implementation.
Note: It is probably too optimistic and speculative to hope that
future research will show how to take advantage by combining the
efficiencies of Edwards and Hessian curve equations.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 49]
Internet-Draft March 21, 2022
A.4.3.7. Bleichenbacher Security
Bleichenbacher's attack against faulty implementations
discrete-log-based signatures fully affects 2y^2=x^3+x/GF(8^91+5),
because the base point order q is not particularly close to a power
of two. (Some other curves, such as NIST P-256 and Curve25519, have
the base point order is close to a power of two, which provides
built-in resistant to Bleichenbacher's faulty signature attack.)
Note: Bleichenbacher's attack exploits the signature
implementation fault of naively reducing uniformly random bit
strings modulo q, the order of the base point, which results in a
number biased towards the lower end of the interval [0,q-1].
So, q-uniformization of the pre-message secret numbers is critical
for signature applications of this document's curve. Various
uniformization methods are known, such as reducing extra large
numbers, repeated sampling, and so on.
A.4.3.8. Bernstein's "Twist" Security
Unlike Curve25519, curve 2y^2=x^3+x/GF(8^91+5) is not
"twist-secure", so a Montgomery ladder implementation for static
private keys often needs public-key validation, which is achievable
by computation of a Legendre symbol related to the received public
key.
In particular, a Montgomery ladder x-only implementation that does
not implement public-key validation will process a value x for which
no y satisfying the equation exists in GF(p). More precisely, a y
does exist, but it belongs to the extension field GF(p^2). In this
case, the Montgomery ladder treats x as though it were (x,y) where x
is GF(p) but y is not. Such points belong to a "twist" group, and
this group has order:
2^2 * 5 * 1526119141 * 788069478421 * 182758084524062861993 *
3452464930451677330036005252040328546941
An adversary can exploit this, by finding such invalid x that
correspond to a lower order group element, and thereby try to learn
partial information about a static private key used by a
non-validating Montgomery ladder implementation.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 50]
Internet-Draft March 21, 2022
A.4.3.9. Cheon Security
Niche applications in ECC involve revealing points [d^e]G for one
secret number d, and many different integer e, or at least one large
e. One way such points could be reveal is in protocols that employ
a static Diffie-Hellman oracle, a function to compute [d]P from any
point P, which might be applied e times, if e is reasonably small.
Typical ECDH, to be clear, would never reveal such points, for at
least two reasons:
- ECDH is ephemeral, so that the same d is never re-used across
ECDH sessions (because d is used to compute [d]G and [d]Q, and
then discarded),
- ECDH is hashed, so though P=[d]G is sent, the point [d]Q is
hashed to get k = H([d]Q), and then [d]Q is discarded, so,
assuming that the hash function is genuinely one-way means that
k does not reveal [d]Q, if k is ever somehow revealed.
The Brown-Gallant-Cheon q-1 algorithm finds d, given [d^e]G, if
e|(q-1). It uses approximately sqrt(q/e) elliptic curve operations.
The Cheon q+1 algorithm finds d, given all the points [d]G, [d^2]G,
..., [d^e]G, if e|(q+1), and takes a similar amount of computation.
These two algorithms rely on factors e of q-1 or q+1, so the
factorization of these numbers affects the security against the
algorithm.
Cheon security refers to the ability to resist these algorithms.
It is possible seek out special curves with relatively high Cheon
security, because q-1 and q+1 have no suitable factors e.
The curve 2y^2=x^3+x/GF(8^91+5) has typical Cheon security in terms
of the factorization of q-1 and q+1. Therefore, in the niche
applications that reveal the requisite points, mitigations ought to
be applied, such as limiting the rate of revealing points, or using
different value d as much as possible (one d per recipient).
For this document's curve, the factorization of q-1 and q+1 are:
q-1 = 2^3 * 101203 * 23810182454264420359 *
10934784357463776473342498062299965925956115086976992657
and
q+1 = 2 * 3 * 11 * 21577 * 54829 * 392473 * 854041 *
8054201530811151253753936635581206856381779711451564813041
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 51]
Internet-Draft March 21, 2022
The q-1 and q+1 algorithms convert an oracle for function P -> [d]P
into a way to find d. This can be viewed as a reduction of the
discrete logarithm problem to the problem of computing the function
P -> [d]P for the target d. In other words, computing P -> [d]P is
almost as difficulty as solving the discrete logarithm problem. In
many systems with a static Diffie-Hellman secret d, computing the
function P -> [d]P needs to be difficult, or the security will be
defeated. In these case, an efficient q-1 or q+1 algorithm provides
a security assurance, that the computing P -> [d]P without knowing d
is about as hard as solving the discrete logarithm problem.
A.4.3.10. Reductionist Security Assurance for Diffie-Hellman
A series of research work, from den Boer, from Maurer and Wolf, and
from Boneh and Lipton, shows that Diffie-Hellman oracle can be used
to solve a discrete logarithm, under certain conditions. In other
words, the discrete logarithm problem can sometimes be reduced to
the Diffie-Hellman problem.
This can be interpreted as a security assurance that Diffie-Hellman
problem is at least as hard the discrete logarithm problem, albeit
perhaps with some gap in the difficulty. This formalized security
assurance supplements the standard conjecture that the
Diffie-Hellman problem is at least as hard as the discrete
logarithm. (A contrarian view is that special conditions under
which such a reduction algorithm is possible might coincide with
special conditions under which the discrete logarithm problem is
easier.)
The general idea is to consider a Diffie-Hellman oracle in a group
of order q to provide multiplication in a special representation
field of order q. Recovering the ordinary field representation from
the special field representation amounts to solving the discrete
logarithm problem.
To recover the ordinary representation, the idea is to construct an
auxiliary group of smooth order, where the group is an algebraic
groups over the field of size q. Solving a discrete logarithm in
the auxiliary group is possible using the Pohlig-Hellman problem,
and solving the discrete logarithm in the auxiliary reveals the
ordinary representation of the field, which, as already noted
reveals the discrete logarithm in the original group.
The most obvious auxiliary groups have orders q-1 and q+1, but these
are not smooth numbers. The next most obvious auxiliary are
elliptic curve groups with complex multiplication by i, but none of
these four group have smooth orders either.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 52]
Internet-Draft March 21, 2022
A peculiar strategy to show the existence of an auxiliary group of
smooth order without having any effective means of constructing the
group. This can be done by finding a smooth number in the Hasse
interval of q.
Appendix B. Test Vectors
The following are some test vectors, with values explained further
below.
000000000000000029352b31395e382846472f782b335e783d325e79322054534554
00000000000000000000000000000000000000000000000000000000000000000117
c8c0f2f404a9fabc91c939d8ea1b9e258d82e21a427b549f05c832cf8d48296ffad7
5f336f56f86de3d52b0eab85e527f2ac7b9d77605c0d5018f5faa4243fd462b1badd
fc023b3f03b469dca32446db80d9b388d753cc77aa4c3ee7e2bb86e99e7bed38f509
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
8c2b0d58eb27185715a48d6071657273dfbb861e515ac8bac9bfe58f2baa85908221
The test vectors are explained as follows. (Pseudocode generating
them is supplied in Appendix C.2.)
Each line is 34 bytes, representing a non-negative 272-bit integer.
The integer encoding is hexadecimal, with most significant hex
digits on the left, which is to say, big-endian.
Note: Public keys are encoded as 34-byte strings are
little-endian. Encoded public keys reverse the order of the bytes
found in the test vectors. The pseudocode in Appendix C.2 aims to
make this clear: since bytes are printed in reverse order.
Each integer is either a scalar (a multiplier of curve points), or
the byte representation of a point P through its x-coordinate or the
x-coordinate of iP (which is the the mod 8^91+5 negation of the
x-coordinate of P).
The first line is a scalar integer x. Its nonzero bytes are the
ASCII representation of the string "TEST 2y^2=x^3+x/GF(8^91+5)",
with the byte order reversed. As a private key, this value of x
would be totally insecure, because it is too small, and like any
test vector, it is public.
The second line is a representation of G, a base point on the curve.
The third line is the representation of z = xG.
The fourth and fifth lines represent updated values of x and z,
obtained after application of the following 100000 scalar
multiplications.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 53]
Internet-Draft March 21, 2022
A loop of 50000 iterations is performed. Each iteration consists of
two re-assignments: z = xz and x = zG via scalar multiplications.
In the second assignment, the byte representation of the input point
z is used as the byte representation of an scalar. Similarly, the
output x is the byte representation of the point, which is will used
as as the byte representation of the scalar.
The purpose of the large number of iterations is to catch a bug that
has probability larger than 1/100000 of arising on pseudorandom
inputs. The iterations do nothing to find rarer bugs (such as those
that an adversary can invoke), or silent bugs (side channel leaks).
The sixth and seventh lines are equal to each other. As explained
below, the equality of these lines represents the fact the Alice and
Bob can compute the same shared DH secret. The purpose of these
lines is not to catch any more bugs, but rather a sanity check that
Diffie-Hellman is likely to work.
Alice initializes her DH private key to x, as already computed on
the fourth line of the test vectors (which was the result of 100000
iterations). She then replaces this x by x^900 mod q (where q is
the prime which is the order of the order of the base point G).
Bob sets his private key y as follows. He begins with y being the
34-byte ASCII string whose initial characters are "yet another test"
(not including the quotes, of course). He then reverses the order
of bytes, considers this to be a scalar, and reassigns y to yG.
(So, the y on the left is new, the y on the right is old, they are
not the same, after the assignment.) Another reassignment is done,
as y -> yy, where the on the right side of the equation one y is
treated as a scalar, the other as a point. Finally, Bob's replaces
y by y^900 mod order(G), similarly to Alice's transformation.
The test code in C.2 does not compute x^900 directly. Instead it
uses 900 scalar multiplication by x, to achieve multiplication by
x^900. The same is done for y^900.
Both lines are xyG. The first can be computed as y(xG), and the
second as x(yG). The equality of the two lines can be used to
self-test an implementation, even if the implementation being tested
disagrees with the test vectors above.
Appendix C. Sample Code (Pseudocode)
This section has sample C code that illustrates well-known elliptic
algorithms, with adaptations specific to 2y^2=x^3+x/GF(8^91+5).
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 54]
Internet-Draft March 21, 2022
Warning: the sample code has not been fully hardened against
side channels or any other implementation attacks; also, no
independent party has reviewed the sample code.
Note: The quality of the sample code is similar to pseudocode, not
reference code, or software. It compiles and runs on my personal
devices, but has not otherwise been tested for quality.
Note: Non-standard C language extensions are used the sample code:
the type __int128, available as an C language extension in the GNU
C compiler (gcc).
Note: Non-portable C is used (beyond the non-standard C), for
convenience. Two's complement integer representation of integers
is assumed. Bit-shifts negative integers are used, in a way that
considered non-portable under strict C, even though commonly used
elsewhere.
Note: Manually minified C is used: to reduce line and character
counts, and also to (arguably) aid objective code inspection by
cramming as much code into a single screen and by not misleading
reviewers with long comments or variable names.
Note: Automated tools, such as indent (used as in "gcc -E pseudo.c
| indent"), can partially revert the C sample code spacing to a
more conventional style, though other aspects of minification are
not so easy to remove.
Note: The minification is not total. It tries to organize the
code into meaningful units, such as placing single short functions
on one line or placing all variable declarations on the same line
with the function parameters. Python-like indentation is kept.
(Per Lisp styling, the code clumps closing delimiters (that mainly
serve the compilers.))
Note: Long sequence expressions, using the C comma operator, in
place of multiple expression statements, which would be more
conventional and terminated by semicolons, save some braces in
control statements, such as "for" loops and "if" conditionals, and
enable extra initializations in declarations.
C.1. Scalar Multiplication of 34-Byte Strings
The sample code for scalar multiplication provides an interface for
scalar multiplication. A function "mulch" takes as input 3 pointer
to unsigned character strings. The first input is the location
of the result, the second is the multiplier, and the third is the
base point.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 55]
Internet-Draft March 21, 2022
Note: The input ordering follows the convention of C assignment
expressions z=x*y.
Note: The function name "mulch" is short for multiply character
strings.
Mulch returns a Boolean value, indicating success or failure.
Failure is returned only if validation is requested, and the base
point is invalid.
Requesting validation is done implicitly, by comparison of pointers.
Validation is requested unless the base point is the known valid
base point G, or if the scalar multiple (2nd input) and the output
(1st input) pointers are equal, meaning that the scalar multiple
will be overwritten.
Note: The motivation here for implicitly requesting validation is
that if the scalar multiple is really ephemeral, the caller would
be willing, and eager, to overwrite it as soon as possible, in
order to achieve forward secrecy. In this case, the need for
input validation is usually negligible.
The sample code is to be considered as a single file "pseudo.c".
The file pseudo.c has two sections. The first section implements
arithmetic for the field GF(8^91+5). The second section implements
Montgomery's ladder for curve 2y^2=x^3+x. The two sections are not
entirely independent. In particular, the field arithmetic section
is not general-purpose, and could produce errors if used for
different elliptic curve algorithms, such as Edwards coordinates.
Note: The scalar multiplication sample code pseudo.c file is
included into 3 other sample (using a the C preprocessor directive
#include "pseudo.c").
Note: Compiler optimizations make a large difference when used on
the field arithmetic (for versions of the sample code where the
field and curve arithmetic are in separate source files). This
suggests that field arithmetic efficiency has room for further
improvement by hand assembly. (The curve arithmetic might be
improved by re-writing the source code.) In other words, the
sample code can be deemed as far from fully optimized.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 56]
Internet-Draft March 21, 2022
Note: Montgomery's ladder might not be the fastest scalar
multiplication algorithm for 2y^2=x^3+x/GF(8^91+5). Experimental
C implementations using Bernstein's 2-D ladder algorithm (see
[B1]) seem about ~10% faster . The experimental code somewhat
more complicated, and thus more likely to vulnerable to side
channels or overflows. Even more aggressive C code seems about
~20% faster, using Edwards coordinates, Hisil-Carter-Dawson-Wong,
and Gallant-Lambert-Vanstone, and pre-computed windows (see [B4]).
Again, these faster methods are more complicated, and might be
more vulnerable implementation attacks. The 10% and 20% gains
might be lost upon more thorough hardening against implementation
attacks, or upon more thorough hand-assembly optimizations.
C.1.1. Field Arithmetic for GF(8^91+5)
The field arithmetic sample code, is the first part of the file
pseudo.c. It implements the field operations used in the Montgomery
ladder algorithm for elliptic curve 2y^2=x^3+x. For example, point
decompression is not used in Montgomery ladders, so the square root
operation is not included the sample code. (The Legendre symbol
computation is included for validation, and is quite similar to the
square root operation.)
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 57]
Internet-Draft March 21, 2022
``````
#define RZ return z
#define F4j i j=5;for(;j--;)
#define FIX(j,r,k) q=z[j]>>r, z[j]-=q<
```b)-(a**>55*k&((k<2)*M-1))
#define MUL(m,E)\
zz[0]= m(0,0)E(1,4)E(2,3)E(3,2)E(4,1),\
zz[1]= m(0,1)m(1,0)E(2,4)E(3,3)E(4,2),\
zz[2]= m(0,2)m(1,1)m(2,0)E(3,4)E(4,3),\
zz[3]= m(0,3)m(1,2)m(2,1)m(3,0)E(4,4),\
zz[4]= m(0,4)m(1,3)m(2,2)m(3,1)m(4,0);\
z[0]=R(0,0)-R(4,1)*20-R(3,2)*20, z[1]=R(1,0)+R(0,1)-R(4,2)*20,\
z[2]=R(2,0)+R(1,1)+R(0,2), z[3]=R(3,0)+R(2,1)+R(1,2),\
z[4]=R(4,0)+R(3,1)+R(2,2); z[1]+=z[0]>>55; z[0]&=M-1;
typedef long long i;typedef i*f,F[5];typedef __int128 ii,FF[5];
i M=((i)1)<<55;F O={0},I={1};
f fix(f z){i j=0,q;
for(;j<5*2;j++) FIX(j%5,(j%5<4?55:53),(j%5<4?1:-5));
z[0]+=(q=z[0]<0)*5; z[4]+=q<<53; RZ;}
i cmp(f x,f y){i z=(fix(x),fix(y),0); F4j z+=!z*CMP(x[j],y[j]); RZ;}
f add(f z,f x,f y){F4j z[j]=x[j]+y[j]; RZ;}
f sub(f z,f x,f y){F4j z[j]=x[j]-y[j]; RZ;}
f mal(f z,i s,f y){F4j z[j]=y[j]*s; RZ;}
f mul(f z,f x,f y){FF zz; MUL(+XY,-20*XY); {F4j zz[j]=0;} RZ;}
f squ(f z,f x){mul(z,x,x); RZ;}
i inv(f z){F t;i j=272; for(mul(z,z,squ(t,z));j--;) squ(t,t);
return mul(z,t,z), (sub(t,t,t)), cmp(O,z);}
i leg(f y){F t;i j=270; for(squ(t,squ(y,y));j--;) squ(t,t);
return j=cmp(I,mul(y,y,t)), (sub(y,y,y),sub(t,t,t)), (2-j)%3-1;}
**```
Field elements are stored as five-element of arrays of limbs. Each
limb is an integer, possibly negative, with array z representing
integer
z[0] + z[1]*2^55 + z[2]*2^110 + z[3]*2^165 + z[4]*2^220
In other words, the radix (base) is 2^55. Say that z has m-bit
limbs if each |z[i]| < 2^m.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 58]
Internet-Draft March 21, 2022
The field arithmetic function input order follows the C assignment
order, as input z=x*y, so usually the first input is the location
for the result of the operation. The return value is usually just a
pointer to the result's location, the first input, indicated by the
preprocessor macro RZ. The functions, inv, cmp, and leg, also
return an integer, which is not a field element, but usually a
Boolean (or for function leg, a value in {-1,0,1}.)
The utility functions are fix and cmp. They are meant to take
inputs with 58-bit limbs, and produce an output with 55-bit
non-negative limbs, with the highest limb, a 53-bit value. The
purpose of fix is to provide a single array representation of each
field element. The function cmp fixes both its inputs, and then
returns a signed comparison indicator (in {-1,0,1}).
The multiplicative functions are mul, squ, inv and leg. They are
meant to take inputs with 58-bit limbs, and produce either an output
with 57-bit limbs, or a small integer output. They try to do this
as follows:
1. Some of the input limbs are multiplied by 20, then multiplied
in pairs to 128-bit limbs, and then summed in groups of five
(with at least one of the pairs having both elements not
multiplied by 20). The multiplications by 20 would not cause
64-bit overflow, because 20*2^58 < 32*2^58=2^63, while the sums
of 128-bit numbers would not cause overflow, because
(1+4*20)*2^58*2^58 = 81*2^116 < 2^7*2^116 = 2^123.
2. The five 128-bit limbs are partially reduced to five 57-bit
limbs. Each the five smaller limbs is obtained by summing two
55-bit limbs, extracted from sections of the 128-bit limbs, and
then summing one or two much smaller values summing to less
than a 55-bit limb. So, the final limbs in the multiplication
are a sum of at most three 55-bit sub-limbs, making each final
limb at most a 57-bit limb.
The additive functions are add, sub and mal. They are meant to take
inputs with 57-bit limbs, and product an output with 58-bit limbs.
The utility and multiplicative function can be used repeatedly,
because they do not lengthen the limbs.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 59]
Internet-Draft March 21, 2022
The additive functions potentially increase the limb length, because
they do not perform any reduction on the output. The additive
functions are not be applied repeatedly. For example, if the output
of additive additive function is fed directly as the input to an
additive function, then the final output might have 59-bit limbs.
In this case, if 2nd output might not be evaluated corrected if
given as input to one of the multiplicative functions, an error due
to overflow of 64-bit arithmetic might occur.
The lack of reduction in the additive functions trades generality
for efficiency. The elliptic curve arithmetic code aims to never
send the output of an additive function directly into the input of
another additive function.
Note: Zeroizing temporary field values is attempted by subtracting
them from themselves. Some compilers might remove these
zeroization steps.
Note: The defined types f and F are essentially the equivalent.
The main difference is that type F is an array, so it can be used
to allocate new memory (on the stack) for a field value.
C.1.2. Montgomery Ladder Scalar Multiplication
The second part of the file "pseudo.c" implements Montgomery's
well-known ladder algorithm for elliptic curve scalar point
multiplication, as it applies to the curve 2y^2=x^3+x.
The sample code, as part of the same file, is a continuation of the
sample code for field arithmetic. All previous definitions are
assumed.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 60]
Internet-Draft March 21, 2022
``````
#define X z[0]
#define Z z[1]
enum {B=34}; typedef void _;typedef volatile unsigned char *c,C[B];
typedef F*e,E[2];typedef E*v,V[2];
f feed(f x,c z){i j=((mal(x,0,x)),B);
for(;j--;) x[j/7]+=((i)z[j])<<((8*j)%55); return fix(x);}
c bite(c z,f x){F t;i j=((fix(mal(x,cmp(mal(t,-1,x),x),x))), B),k=5;
for(;j--;) z[j]=x[j/7]>>((8*j)%55); {(sub(t,t,t));}
for(;--k;) z[7*k-1]+=x[k]<<(8-k); {(sub(x,x,x));} RZ;}
i lift(e z,f x,i t){F y;return mal(X,1,x),mal(Z,1,I),t||
-1==leg(add(y,x,mul(y,x,squ(y,x))));}
i drop(f x,e z){return inv(Z)&&mul(x,X,Z)&&(sub(X,X,X)&&sub(Z,Z,Z));}
_ let(e z,e y){i j=2;for(;j--;)mal(z[j],1,y[j]);}
_ smv(v z,v y){i j=4;for(;j--;)add(((e)z)[j],((e)z)[j],((e)y)[j]);}
v mav(v z,i a){i j=4;for(;j--;)mal(((e)z)[j],a,((e)z)[j]);RZ;}
_ due(e z){F a,b,c,d;
mul(X,squ(a,add(a,X,Z)),mal(d,2,squ(b,sub(b,X,Z))));
mul(Z,add(c,a,b),sub(d,a,b));}
_ ade(e z,e u,f w){F a,b,c,d;f ad=a,bc=b;
mul(ad,add(a,u[0],u[1]),sub(d,X,Z)),
mul(bc,sub(b,u[0],u[1]),add(c,X,Z));
squ(X,add(X,ad,bc)),mul(Z,w,squ(Z,sub(Z,ad,bc)));}
_ duv(v a,e z){ade(a[1],a[0],z[0]);due(a[0]);}
v adv(v z,i b){V t;
let(t[0],z[1]),let(t[1],z[0]);smv(mav(z,!b),mav(t,b));mav(t,0);RZ;}
e mule(e z,c d){V a;E o={{1}};i
b=0,c,n=(let(a[0],o),let(a[1],z),8*B);
for(;n--;) c=1&d[n/8]>>n%8,duv(adv(a,c!=b),z),b=c;
let(z,*adv(a,b)); (due(*mav(a,0))); RZ;}
C G={23,1};
i mulch(c db,c d,c b){F x;E p; return
lift(p,feed(x,b),(db==d||b==G))&&drop(x,mule(p,d))&&bite(db,x);}
``````
This part of the sample code represents points and scalar
multipliers as character strings of 34 bytes.
Note: Types c and C are used for these 34-byte encodings.
Following the previous pattern for f and F, type C is an array,
used for allocating new memory (on the stack) for these arrays.
The conversion functions feed and bite convert
between a 34-byte string and a field value (recall, stored as five
element array, base 2^55).
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 61]
Internet-Draft March 21, 2022
The conversion functions lift and drop convert between field
elements and the projective line point, so that x <-> (X:1). The
function lift can also test if x is the x-coordinate of the a point
(x,y) on the curve 2y^2=x^3+x.
Note: Projective line points are stored in defined types e and E
(for extended field element).
Note: The Montgomery ladder can implemented by working with a
pair of extended field elements.
The raw scalar multiplication function "mule" takes a projective
point (with defined type e), multiplies it by a scalar (encoded as
byte string with defined type c), and then replaces the projective
point by the multiple.
The main loop of mule is written a double-and-always-add, acting on
pair projective line points. Basically it acts on the x-coordinates
of the points nB and (n+1)B, for n changing.
Because the Montgomery ladder algorithm is being used, the "adv"
called by mule function does nothing but swap the two values. With
an appropriate isogeny, this can be viewed as addition operation.
The function "duv" called by mule, does the hard work of finding
(2n)B and (2n+1)B from nB and (n+1)B. It does so, using doubling in
the function "due" and differential addition, in the function "ade".
The functions "due" and "ade" are non-trivial, and use field
arithmetic. They are fairly specific to 2y^2=x^3+x. They try to
avoid repeated application of additive field operations.
The function smv, mav and let are more utilitarian. They are used
for initialization, swapping, and zeroization.
C.1.3. Bernstein's 2-Dimensional Montgomery Ladder
Bernstein's 2-dimensional ladder is a variant of Montgomery's ladder
that computes aP+bQ, for any two points P and Q, more quickly than
computing aP and bQ separately.
Curve 2y^2=x^3+x has an efficient endomorphism, which allows a point
Q = [i+1]P to compute efficiently. Gallant, Lambert and Vanstone
introduced a method (now called the GLV method), to compute dP more
efficiently, given such an efficient endomorphism. They write d = a
+ eb where e is the integer multiplier corresponding to the
efficient endomorphism, and a and b are integers smaller than d.
(For example, 17 bytes each instead of 34 bytes.)
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 62]
Internet-Draft March 21, 2022
The GLV method can be combined with Bernstein's 2D ladder algorithm
to be applied to compute dP = (a+be)P = aP + beP = aP + bQ, where
e=i+1.
This algorithm is not implemented by any pseudocode in this version
of the document. (Previous versions had it.)
See [B1] for further explanation and example pseudocode.
I have estimate a ~10% speedup of this method compared to the plain
Montgomery ladder. However, the code is more complicated, and
potentially more vulnerable to implementation-based attacks.
C.1.4. GLV in Edwards Coordinates (Hisil-Carter-Dawson-Wong)
It is also possible to convert to Edwards coordinates, and then use
the Hisil-Wong-Carter-Dawson (HWCD) elliptic curve arithmetic.
The HWCD arithmetic can be combined with the GLV techniques to
obtain a scalar multiplication potentially more efficient than
Bernstein's 2-dimensional Montgomery. The downside is that it might
need key-dependent array look-ups, which can be a security risk.
My implementation of this (see [B4]) gives a ~20% speed-up over my
implementation of the Montgomery ladder. Of course, this speed-up
might disappear upon further optimization (e.g. assembly), or
further security hardening (safe table lookup code).
C.2. Sample Code for Test Vectors
The following sample code describes the contents of a file "tv.c",
with the purpose of generating the test vectors in Appendix B.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 63]
Internet-Draft March 21, 2022
``````
//gcc tv.c -o tv -O3 -flto -finline-limit=200;strip tv;time ./tv
#include
```
#include "pseudo.c"
#define M mulch
void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");}
int main (void){i n=1e5,j=n/2,wait=/*your mileage might vary*/7000;
C x="TEST 2y^2=x^3+x/GF(8^91+5)",y="yet another test",z;
M(z,x,G); hx(x),hx(G),hx(z);
fprintf(stderr,"%30s(wait=~%ds, ymmv)","",j/wait);
for(;j--;)if(fprintf(stderr,"\r%7d\r",j),!(M(z,x,z)&&M(x,z,G)))
j=0*printf("Mulch fail rate ~%f :(\n",(2*j)/n);//else//debug
fprintf(stderr,"\r%30s \r",""),hx(x),hx(z);
M(y,y,G);M(y,y,y);
for(M(z,G,G),j=900;j--;)M(z,x,z);for(j=900;j--;)M(z,y,z);hx(z);
for(M(z,G,G),j=900;j--;)M(z,y,z);for(j=900;j--;)M(z,x,z);hx(z);}
```
It includes the previously defined file pseudo.c, and the standard
header file stdio.h.
The first for-loop in main aims to terminate in the event of the bug
such that the output of mulch is an invalid value, not on the curve
2y^2=x^3+x.
Of the 100,000 scalar multiplication in this for-loop, the aim is
that 50,000 include public-key validation. All 100,000 include a
field-inversion, to encode points uniquely as 34-byte strings.
The second and three for-loops aims to test the compatibility with
Diffie-Hellman, by showing the 900 applications of scalar
multipliers x and y are the same, whether x or y is applied first.
The 1st line comment suggest possible compilation commands, with
some optimization options. The run-time depends on the system, and
would be slower on older and weaker systems.
Anecdotally, on a ~3 year-old personal computer, it runs in time as
low as 5.7 seconds, but these were under totally uncontrolled
conditions (with no objective benchmarking). (Experience has shown
that on a ~10 year-old personal computer, it could be ~5 times
slower.)
C.3. Sample Code for a Command-Line Demo of Diffie-Hellman
The next sample code is intended to demonstrate ephemeral (elliptic
curve) Diffie-Hellman: (EC)DHE in TLS terminology.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 64]
Internet-Draft March 21, 2022
The code can be considered as a file "dhe.c". It has both C and
bash code, intermixed within comments and strings. It is bilingual:
a valid bash script and valid C source code. The file "dhe.c" can
be made executable (using chmod, for example), so it can be run as a
bash script.
``````
#include "pseudo.c" /* dhe.c (also a bash script)
: demos ephemeral DH, also creates, clobbers files dhba dha dhb
: - Dan Brown, BlackBerry, '20 */
#include
```
_ get(c p,_*f){f&&fread ((_*)p,B,1,f)||mulch(p,p,G);}
_ put(c p,_*f){f&&fwrite((_*)p,B,1,f)&&fflush(f); bite(p,O);}
int main (_){C p="not validated",s="/dev/urandom" "\0"__TIME__;
get(s,fopen((_*)s,"r")), mulch(p,s,G), put(p,stdout);
get(p,stdin), mulch(s,s,p), put(s,stderr);} /*'
[ dhe.c -nt dhe ]&&gcc -O2 dhe.c -o dhe&&strip dhe&&echo "$(/dev/null || ([ ! -p dhba ] && :> dhba)
./dhe dha | ./dhe >dhba 2>dhb &
sha256sum dha & sha256sum dhb # these are to be equal
(for f in dh{a,b,ba} ; do [ -f $f ] && \rm -f $f; done)# '*/
```
Run as a bash script, file "dhe.c" will check if it needs compile
its own C code, into an executable named "dhe". Then the bash
script file "dhe.c" runs the compiled executable "dhe" twice. One
run is Alice's, and the other Bob's.
Each run of "dhe" generates an ephemeral secret key, by reading the
file "/dev/urandom". Each run then writes to "stdout", the
ephemeral public key. Each run then reads the peer's ephemeral
public key from "stdin". Each run then writes to "stderr" the
shared Diffie-Hellman secret. (Public-key validation is mostly
unnecessary, because the ephemeral is only used once, so it is
skipped by using the same pointer location for the ephemeral secret
and final shared secret.)
The script "dhe.c" connects the input and output of these two using
pipes. One pipe is generated by the shell command line using the
shell operator "|". The other pipe is a pipe name "dhab", created
with "mkfifo". The script captures the shared secrets from each run
by redirecting "stderr" (as file descriptor 2), to files "dha" and
"dhb", which will be made named pipes if possible.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 65]
Internet-Draft March 21, 2022
The scripts feeds each shared secret keys into SHA-256. This
demonstrates their equality. It also illustrates a typical way to
use Diffie-Hellman, by deriving symmetric keys using a hash
function. In multi-curve ECC, hashing a concatenation of such
shared secrets (one for each curve used), could be done instead.
C.4. Sample Code for Public-Key Validation and Curve Basics
The next sample code demonstrates the public-key validation issues
specific to 2y^2=x^3+x/GF(8^91+5). It also demonstrates the order
of the curve. It also demonstrates complex multiplication by i, and
the fact the 34-byte representation of points is unaffected by
multiplication by i.
The code can be considered to describe a file "pkv.c". It uses the
"mulch" function by including "pseudo.c".
``````
#include
```
#include "pseudo.c"
#define M mulch // works with +/- x, so P ~ -P ~ iP ~ -iP
void hx(c x){i j=B;for(;j--;)printf("%02x",x[j]);printf("\n");}
int main (void){i j;// sanity check, PKV, twist insecurity demo
C y="TEST 2y^2=x^3+x/GF(8^91+5)",z="zzzzzzzzzzzzzzzzzzzz",
q = "\xa9\x38\x04\xb8\xa7\xb8\x32\xb9\x69\x85\x41\xe9\x2a"
"\xd1\xce\x4a\x7a\x1c\xc7\x71\x1c\xc7\x71\x1c\xc7\x71\x1c"
"\xc7\x71\x1c\xc7\x71\x1c\x07", // q=order(G)
i = "\x36\x5a\xa5\x56\xd6\x4f\xb9\xc4\xd7\x48\x74\x76\xa0"
"\xc4\xcb\x4e\xa5\x18\xaf\xf6\x8f\x74\x48\x4e\xce\x1e\x64"
"\x63\xfc\x0a\x26\x0c\x1b\x04", // i^2=-1 mod q
w5= "\xb4\x69\xf6\x72\x2a\xd0\x58\xc8\x40\xe5\xb6\x7a\xfc"
"\x3b\xc4\xca\xeb\x65\x66\x66\x66\x66\x66\x66\x66\x66\x66"
"\x66\x66\x66\x66\x66\x66\x66"; // w5=(2p+2-72q)/5
for(j=0;j<=3;j++)M(z,(C){j},G),hx(z); // {0,1,2,3}G, but reject 0G
M(z,q,G),hx(z); // reject qG; but qG=O, under hood:
{F x;E p;lift(p,feed(x,G),1);mule(p,q);hx(bite(z,p[1]));}
for(j=0;j<0*25;j++){F x;E p;lift(p,feed(x,(C){j,1}),1);mule(p,q);
printf("%3d ",j),hx(bite(z,p[1]));}// see j=23 for choice of G
for(j=3;j--;)q[0]-=1,M(z,q,G),hx(z);// (q-{1,2,3})G ~ {1,2,3}G
M(z,i,G),hx(z); i[0]+=1,M(z,i,G),M(z,i,z),hx(z);// iG~G,(i+1)^2G~2G
M(w5,w5,(C){5}),hx(w5);// twist, ord(w5)=5, M(z,z,p) skipped PKV(p)
M(G,(C){1},w5),hx(G);// reject w5 (G unch.); but w5 leaks z mod 5:
for(j=10;j--;)M(z,y,G),z[0]+=j,M(z,z,w5),hx(z);}
```
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 66]
Internet-Draft March 21, 2022
The sample code demonstrates the need for public-key validation even
when using the Montgomery ladder for scalar multiplication. It does
this by finding points of low order on the twist of the curve. This
invalid points can leak bits of the secret multiplier. This is
because this document's curve is not fully "twist secure". (Its
twist security is typical of that of a random curve.)
Appendix D. Minimizing Trapdoors and Backdoors
The main advantage of curve 2y^2=x^3+x/GF(8^91+5) over almost all
other elliptic curves is its Kolmogorov complexity is almost minimal
among curves of sufficient resistance to the Pollard rho attack on
the discrete logarithm problem.
See [AB] and [B1] for some details.
D.1. Decimal Exponential Complexity
The curve can be described with 21 characters:
2 y ^ 2 = x ^ 3 + x / G F ( 8 ^ 9 1 + 5 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Those familiar with ECC will recognize that these 21 characters
suffice to specify the curve up to the level of detail needed to
describe the cost of the Pollard rho algorithm, as well as many
other security properties (especially resistance to other known
attacks on the discrete logarithm problem, such as Pohlig-Hellman
and Menezes-Okamoto-Vanstone).
Note: The letters GF mean Galois Field, and are quite traditional
mathematics, and every elliptic curve in cryptographic needs to
use some notation for the finite field.
We can therefore describe the curve's Kolmogorov complexity as 21
characters.
Note: The idea of low Kolmogorov complexity is hard to specify
exactly. Nonetheless, a claim of nearly minimal Kolmogorov
complexity is quite falsifiable. The falsifier need merely
specify several other (secure) elliptic curves using 21 or fewer
characters. (But if the other curves use a different
specification language, then a fair comparison would re-specify
2y^2=x^3+x/GF(8^91+5) in this specification language.)
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 67]
Internet-Draft March 21, 2022
D.1.1. A Shorter Isomorphic Curve
The curve is isomorphic to a curve specifiable in 20 characters:
y^2=x^3-x/GF(8^91+5)
Generally, isomorphic curves have essentially equivalently hard
discrete logarithm problems, so one could argue that curve
2y^2=x^3+x/GF(8^91+5) could be rated as having Kolmogorov complexity
at most 20 characters.
Isomorphic curves, however, can differ slightly in security, due to
issues of efficiency, and implementability. The 21-character
specification uses an equation in Montgomery form, which creates an
incentive to use the Montgomery ladder algorithm, which is both safe
and efficient [Bernstein?].
D.1.2. Other Short Curves
Allowing for non-prime fields, then the binary-field curve known as
sect283k1 has a 22-character description:
y^2+xy=x^3+1/GF(2^283)
This curve was formerly one of the fifteen curves recommended by
NIST. Today, a binary curve is curve is considered risky, due to
advances in elliptic curve discrete logarithm problem over extension
fields, such as recent asymptotic advances on discrete logarithms in
low-characteristic fields [HPST] and [Nagao]. According to [Teske],
some characteristic-two elliptic curves could be equipped with a
secretly embedded backdoor (but sect283k1's short description would
help mitigate that risk).
This has a longer overall specification than curve
2y^2=x^3+x/GF(8^91+5), but the field part is shorter field
specification. Perhaps an isomorphic curve can be found (one with
three terms), so that total length is 21 or fewer characters.
A non-prime field tends to be slower in software. A non-prime field
is therefore perhaps riskier due to some recent research on
attacking non-prime field discrete logarithms and elliptic curves,
D.1.3. Converting DEC Characters to Bits
The units of characters as measuring Kolmogorov complexity is not
calibrated as bits of information. Doing so formally would be very
difficult, but the following approach might be reasonable.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 68]
Internet-Draft March 21, 2022
Set the criteria for the elliptic curve. For example, e.g. prime
field, size, resistance (of say 2^128 bit operations) to known
attacks on the discrete logarithm problem (Pollard rho, MOV, etc.).
Then list all the possible ECC curve specification with Kolmogorov
complexity of 21 characters or less. Take the base two logarithm of
this number. This is then an calibrated estimate of the number of
bits needed to specify the curve. It can viewed as a lower bound,
in case some curves were missed.
D.1.4. Common Acceptance of Decimal Exponential Notation
The decimal exponentiation notation used in to measure decimal
exponential complexity is quite commonly accepted, almost standard,
in mathematical computer programming.
For example, as evidence of this common acceptance, here is a
slightly edited session of the program "bc" (versions of which are
standardized in POSIX).
``````
$ BC_LINE_LENGTH=70 bc
bc 1.06.95
Copyright ... Free Software Foundation, Inc.
...
p=8^91+5 ; p; obase=16; p
15177100720513508366558296147058741458143803430094840009779784451085\
189728165691397
200000000000000000000000000000000000000000000000000000000000000000005
define v(b,e,m){
auto a; for(a=1;e>0;e/=2){
if(e%2==1) {a=(a*b)%m;}
b=(b^2)%m;}
return(a);}
v(571,p-1,p)
1
x = (1*256) + (23*1)
v(2*(x^3+x),(p-1)/2,p)
1
y = (((p+1)/2)*v(2*(x^3+x),(p+3)/8,p))%p
(2*y^2)%p == (x^3+x)%p
1
(2*y^2 -(x^3+x))%(8^91+5)
0
``````
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 69]
Internet-Draft March 21, 2022
Note: Input lines have been indented at least two extra spaces,
and can be pasted into a "bc" session. (Pasting the output lines
causes a few spurious results.)
The sample code demonstrates that "bc" directly accepts the
notations "8^91+5" and "x^3+x": parts parts of the curve
specification "2y^2=x^3+x/GF(8^91+5)", which goes to show how much
of the notation used in this specification is commonly accepted.
Note: Defined function "v" implements modular exponentiation,
with returning v(b,e,m) returning (b^e mod m). Then, "v" is used
to show that p=8^91+5 is a Fermat pseudoprime to base 571
(evidence that p is prime). The value x defined is the
x-coordinate of the base point G. Then, another computation with
"v" shows that 2(x^3+x) has Legendre symbol 1, which implies
(assuming p is prime) that there exists y with 2y^2=x^3+x, namely
y = (1/2)sqrt(2(x^3+x)). The value of y is computed, again using
"v" (but also a little luck). The curve equation is then tested
twice with two different expressions, somewhat similar to the
mathematical curve specification.
D.2. General Benefits of Low Kolmogorov Complexity to ECC
The intuitive benefit of low Kolmogorov complexity to cryptography
is well known, but very informal and heuristic. The general benefit
is believed to be a form of subversion-resistance, where the
attacker is the designer of the cryptography. The idea is that low
Kolmogorov complexity thwarts that type of subversion which causes
high Kolmogorov complexity. Exhaustive searches for weaknesses
would seem to imply relatively high Kolmogorov complexity, compared
to lowest complexity non-weak examples in the search.
Often, fixed numbers in cryptographic algorithms with low Kolmogorov
complexity are called "nothing-up-my-sleeve" numbers. (Bernstein et
al. uses terms in "rigid", for a very similar idea, but with an
emphasis on efficiency instead of compressibility.)
For elliptic curves, the informal benefit can be stated as the
following gains.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 70]
Internet-Draft March 21, 2022
- Low Kolmogorov complexity defends against insertion of a keyed
trapdoor, meaning the curve can broken using a secret trapdoor,
by an algorithm (eventually discovered by the public at large).
For example, the Dual EC DRBG is known to capable of having such
a trapdoor. Such a trapdoor would information-theoretically
imply an amount of information, comparable the size of the
secret, to be embedded in the curve specification. If the
calibrated estimate for the number of bits is sufficiently
accurate, then such a key cannot be large.
- Low Kolmogorov complexity defends against a secret attack
(presumably difficult to discover), which affects a subset of
curves such that (a) whether or not a specific curve is affected
is a somewhat pseudorandom function of its natural
specification, and (b) the probably of a curve being affected
(when drawn uniformly from some sensible of curve
specification), is low. For an example of real-world attacks
meeting the conditions (a) and (b) consider the MOV attack.
Exhaustively finding curve meeting these two conditions is
likely to result in relatively high Kolmogorov complexity.
The supply of low Kolmogorov complexity curves is so low that
the probability of any falling into the weak class is low.
- Even more hypothetically, there might yet exist undisclosed
classes of weak curves, or attacks, which 2y^2=x^3+x/GF(8^91+5)
avoids somehow. A real-world example is prime-order, or low
cofactor curves, which are rare among all curves, but which
better resist the Pohlig-Hellman attack. If this happens, then
it can reasonably be considered a fluke.
Low Kolmogorov complexity is not a panacea. The worst failure would
be attacks that increase in strength as Kolmogorov complexity gets
lower. Two examples illustrate this strongly.
D.2.1. Precedents of Low Kolmogorov Complexity in ECC
The standard curves sect283k1 and Curve25519 can be argued as
mitigating the risk of manipulated designed-in weakness, by virtue
of the low Kolmogorov complexity.
Furthermore, the Brainpool curves also make use of low Kolmogorov
complexity, except that a hash function is used in the computation
of the curve coefficients. Arguably, since a hash function is very
useful in cryptography, for key derivation and message digesting,
the complexity of the hash function can reasonably be discounted
from the overall Kolmogorov complexity of the Brainpool curve
coefficients.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 71]
Internet-Draft March 21, 2022
D.3. Risks of Low Kolmogorov Complexity
Low Kolmogorov complexity is not a panacea for cryptography.
Indeed, it might even add its own risks, if some weakness are
positively correlated with low Kolmogorov complexity, making some
attacks stronger.
In other words, choosing low Kolmogorov complexity might just
accidentally weaken the cryptography. Or worse, if attackers find
and hold secret such weaknesses, then attackers can intentionally
include the weakness, by using low Kolmogorov serving as a cover,
thereby subverting the algorithm.
Evidence of positive correlations between curve weakness and low
Kolmogorov complexity might help assess this risk.
In general cryptography (not ECC), the shortest cryptography
algorithms might be the least secure, such as the identity function
as an encryption function.
Within ECC, however, some minimum threshold of complexity needs to
be met to achieve interoperability. But curve size is positively
correlated with security (via Pollard rho) and negatively correlated
with complexity (at least for fields, larger fields needs larger
specifications). Therefore, there is a somewhat negative
correlation between Pollard rho security of ECC and Kolmogorov
complexity of the field size.
Beyond field size in ECC, there is some negative correlations in the
curve equation.
Singular cubics have equations that look very similar to those
commonly used elliptic curves. For smooth singular curves
(irreducible cubics) a group can be defined, using more or less the
same arithmetic as for a elliptic curve. For example
y^2=x^3/GF(8^91+5) is such a cubic. The resulting group has an easy
discrete logarithm problem, because it can be mapped to the field.
Supersingular elliptic curves can also be specified with low
Kolmogorov complexity, and these are vulnerable to MOV attack,
another negative correlation.
Combining the above, a low Kolmogorov complexity elliptic curve,
y^2=x^3+1/GF(2^127-1), with 21-character decimal exponential
complexity, suffers from three well-known attacks:
1. The MOV (Menezes-Okamato-Vanstone) attack.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 72]
Internet-Draft March 21, 2022
2. The Pohlig-Hellman attack (since it has 2^127 points).
3. The Pollard rho attack (taking 2^63 steps, instead of the 2^126
of exhaustive).
Had all three attacks been unknown, an implementer seeking low
Kolmogorov complexity, might have been drawn to curve
y^2=x^3+1/GF(2^127-1). (This document's curve 2y^2=x^3+x/GF(8^91+5)
uses 1 more character and is much slower since, the field size has
twice as many bits.)
Had an attacker known one of three attacks, the attacker could found
y^2=x^3+1/GF(2^127-1), proposed it, touted its low Kolmogorov
complexity, and maybe successfully subverted the system security.
Note: The curve y^2=x^3+1/GF(2^127-1) not only has low decimal
exponential complexity, it also has high efficiency: fast field
arithmetic and fairly fast curve arithmetic (for its bit lengths).
So high efficiency can also be positively correlated with
weakness.
It can be argued, that pseudorandomized curves, such as NIST P-256
and Brainpool curves, are an effective way mitigate such attacks
positively correlated with low complexity. More precisely, strong
pseudorandomization somewhat mitigates the attacker's subversion
ability, by reducing an easy look up of the weakest curve to an
exhaustive search by trial and error, intuitively implying a
probable high Kolmogorov complexity (proportional the rarity of the
weakness).
It can be further argued that all major known weak classes of curves
in ECC are positively correlated with low complexity, in that the
weakest curves have very low complexity. No major known weak
classes of curves imply an increase in Kolmogorov complexity, except
perhaps Teske's class of curves.
In defense of low complexity, it can be argued that the strongest
way to resist secret attacks is to find the attacks.
For these reasons, this specification suggests to use this
document's curve in multi-curve elliptic curve cryptography, in
combination with at least one pseudo-randomized curve, or at least a
another curve that lacks an efficient endomorphism.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 73]
Internet-Draft March 21, 2022
D.4. Alternative Measures of Kolmogorov Complexity
Decimal exponential complexity arguably favors decimal and the
exponentiation operators, rather than the arbitrary notion of
compressibility.
Allowing more arbitrary compression schemes introduces another
possible level of complexity, the compression scheme itself,
somewhat defeating the purpose of nothing-up-sleeve number. An
attacker might be able to choose a compression scheme among
many that somehow favors a weak curve.
Despite this potential extra complexity, one can still seek a
measure more objective than decimal complexity. To this end, in
[B3], I adapted the Godel's approach for general recursive
functions, which breaks down all computation into succession,
composition, repetition, and minimization.
The adaption is a miniature programming language called Roll to
describe number-related functions, including constant functions. A
Roll program for the constant function that always return 8^91+5 is:
``````
8^91+5 subs 8^91+1 in +4
8^91+1 subs 2^273 in +1
2^273 subs 273 in 2^
273 subs 17 in *16+1
17 subs 1 in *16+1
*16+1 roll +16 up 1
+16 subs +8 in +8
+8 subs +4 in +4
+4 subs +2 in +2
2^ roll *2 up 1
1 subs in +2
*2 roll +2 up 0
+2 subs +1 in +1
0 subs in +1
``````
A Roll program has complexity measured in its length in number of
words (space-separated substrings). This program has 68 words.
Constants (e.g. field sizes) can be compared using roll complexity,
the shortest known length of their implementations in Roll.
In [B3], several other ECC field sizes are given programs. The only
prime field size implemented with 68 or fewer words was 2^521-1.
(The non-prime field size (2^127-1)^2 has 58-word "roll" program.)
Further programming effort might produce shorter programs.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 74]
Internet-Draft March 21, 2022
Note: Roll programs have a syntax implying some redundancy.
Further work might yet establish a reasonable normalization for
roll programs, resulting in a more calibrated complexity measure
in bits, making the units closed to a universal kind of Kolmogorov
complexity.
Appendix E. Primality Proofs and Certificates
Recent work of Albrecht and others [AMPS] has shown the combination
of an adversarially chosen prime, and users using improper
probabilistic primality tests can make user vulnerable to an attack.
The adversarial primes in their attack are typically the result of
an exhaustive search. These bad primes would therefore typically
contain an amount of information corresponding to the length of
their search, putting a predictable lower bound on their Kolmogorov
complexity.
The two primes involved for 2y^2=x^3+x/GF(8^91+5) perhaps already
resist [AMPS] because of the following compact representation of
these primes:
p = 8^91+5
q = #(2y^2=x^3+x/GF(8^91+5))/72
This attack [AMPS] can also be resisted by:
- properly implementing probabilistic primality test, or
- implementing provable primality tests.
Provable primality tests can be very slow, but can be separated into
two steps:
- a slow certificate generation, and
- a fast certificate verification.
The certificate is a set of data, representing an intermediate step
in the provable primality test, after which the completion of the
test is quite efficient.
Pratt primality certificate generation for any prime p, involves
factorizing p-1, which can be very slow, and then recursively
generating a Pratt primality certificate for each prime factor of
p-1. Essentially, each prime has a unique Pratt primality
certificate.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 75]
Internet-Draft March 21, 2022
Pratt primality certificate verification of (p-1), involves search
for g such that 1 = (g^(p-1) mod p) and 1 < (g^((p-1)/q) mod p) for
each q dividing p-1, and then recursively verifying each Pratt
primality certificate for each prime factor q of p-1.
In this document, we specify a Pratt primality certificate as a
sequence of (candidate) primes each being 1 plus a product of
previous primes in the list, with certificate stating this product.
Although Pratt primality certificate verification is quite
efficient, an ECC implementation can opt to trust 8^91+5 by virtue
of verifying the certificate once, perhaps before deployment or
compile time.
E.1. Pratt Certificate for the Field Size 8^91+5
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
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
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
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
Y=1+aaaaauX Z=1+aabzUVY.
``````
Note: variable concatenation is used to indicate multiplication.
For example, f = 1+aab = 1+2*2*(1+2) = 13.
Note: The final part of verification of the Pratt primality
certificate is to check that Z=8^91+5 holds.
Note: The Pratt primality certificate involves finding a generator
g for each the prime (after the initial prime). It is possible to
list these in the certificate, which can speed up verification by
a small factor.
(2,b), (2,c), (3,d), (2,e), (2,f), (3,g), (2,h), (5,i), (6,j),
(3,k), (2,l), (3,m), (2,n), (5,o), (2,p), (3,q), (6,r), (2,s),
(2,t), (6,u), (7,v), (2,w), (2,x), (14,y),(3,z), (5,A), (3,B),
(7,C), (3,D), (7,E), (5,F), (2,G), (2,H), (2,I), (3,J), (2,K),
(2,L),(10,M), (5,N), (10,O),(2,P), (10,Q),(6,R), (7,S), (5,T),
(3,U), (5,V), (2,W), (2,X), (3,Y), (7,Z).
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 76]
Internet-Draft March 21, 2022
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,
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,
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,
R=98305423, S=446424961, T=170464833767, U=115417966565804897,
V=4635260015873357770993, W=1561512307516024940642967698779,
X=167553393621084508180871720014384259,
Y=1453023029482044854944519555964740294049.
E.2. Pratt Certificate for Subgroup Order
Define 56 variables a,b,...,z,A,B,...,Z,!,@,#,$, with new
values:
``````
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 Z=1+ab3oHOT !=1+a3SUX @=1+abNY!
#=1+a4kzF@ $=1+a3QZ#
``````
Note: numeral after variable names represent powers. For example,
f = 1 + a2b = 1 + 2^2 * 3 = 13.
The last variable, $, is the order of the base point, and the order
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 multi-letter variable names.
E.g. replace, Z,!,@,#,$ by Za,Zb,Zc,Zd,Ze:
Acknowledgments
Thanks to John Goyo and various other BlackBerry employees for past
technical review, and to Gaelle Martin-Cocher and Takashi Suzuki for
encouraging work on this I-D. Thanks to David Jacobson for sending
Pratt primality certificates.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 77]
Internet-Draft March 21, 2022
Author's Address
Dan Brown
BlackBerry
4701 Tahoe Blvd., 5th Floor
Mississauga, ON
Canada
danibrown@blackberry.com
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 78]
```