```
#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 55]
Internet-Draft 2021-09-30
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 should not cause
64-bit overflow 20*2^58 < 32*2^58=2^63, while the sums of
128-bit numbers should 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 56]
Internet-Draft 2021-09-30
The additive functions potentially increase the limb length, because
they do not perform any reduction on the output. The additive
functions should 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 57]
Internet-Draft 2021-09-30
``````
#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 58]
Internet-Draft 2021-09-30
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 59]
Internet-Draft 2021-09-30
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 the version
the draft. (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 may
require 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
may 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 60]
Internet-Draft 2021-09-30
``````
//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 may 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
should 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 61]
Internet-Draft 2021-09-30
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 should 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 62]
Internet-Draft 2021-09-30
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 63]
Internet-Draft 2021-09-30
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 the curve 2y^2=x^3+x/GF(8^91+5) 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 may 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 should 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 64]
Internet-Draft 2021-09-30
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, may 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 should
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 65]
Internet-Draft 2021-09-30
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 should be 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 66]
Internet-Draft 2021-09-30
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 recommend 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
2y^2=x^3+x/GF(8^91+5).
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 require 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 may be stated as the
following gains.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 67]
Internet-Draft 2021-09-30
- 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 may 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 should 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 should 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 68]
Internet-Draft 2021-09-30
D.3. Risks of low Kolmogorov complexity
Low Kolmogorov complexity is not a panacea for cryptography.
Indeed, it may 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 may be the least secure, such as the identity function as
an encryption function.
Within ECC, however, some minimum threshold of complexity must be
met for 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 69]
Internet-Draft 2021-09-30
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 curve
2y^2=x^3+x/GF(8^91+5) in multi-curve elliptic curve cryptography,
in combination with at least one pseudo-randomized curve.
D.4. Alternative measures of Kolmogorov complexity
Decimal exponential complexity arguably favors decimal and the
exponentiation operators, rather than the arbitrary notion of
compressibility.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 70]
Internet-Draft 2021-09-30
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.
Note: Roll programs have a syntax implying some redundancy.
Further work may 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.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 71]
Internet-Draft 2021-09-30
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) should 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.
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.
Brown ECC with 2y^2=x^3+x/GF(8^91+5) [Page 72]
Internet-Draft 2021-09-30
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: One must verify that Z=8^91+5.
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 73]
Internet-Draft 2021-09-30
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 74]
Internet-Draft 2021-09-30
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 75]
```