⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

;Elliptic curves.

An [[wp:Elliptic_curve|elliptic curve]] E over ℤp (p ≥ 5) is defined by an equation of the form '''y^2 = x^3 + ax + b''', where a, b ∈ ℤp and the discriminant ≢ 0 (mod p), together with a special point 𝒪 called the point at infinity. The set '''E(ℤp)''' consists of all points (x, y), with x, y ∈ ℤp, which satisfy the above defining equation, together with 𝒪.

There is a rule for adding two points on an elliptic curve to give a third point. This addition operation and the set of points E(ℤp) form a group with identity 𝒪. It is this group that is used in the construction of elliptic curve cryptosystems.

The addition rule — which can be explained geometrically — is summarized as follows:

```
1. P + &#119978; = &#119978; + P = P for all P &#8712; E(&#8484;p).

2. If P = (x, y) &#8712; E(&#8484;p), then inverse -P = (x,-y), and P + (-P) = &#119978;.

3. Let P = (xP, yP) and Q = (xQ, yQ), both &#8712; E(&#8484;p), where P &#8800; -Q.
Then R = P + Q = (xR, yR), where

xR = &lambda;^2 - xP - xQ
yR = &lambda;&middot;(xP - xR) - yP,

with

&lambda; = (yP - yQ) / (xP - xQ) if P &#8800; Q,
(3&middot;xP&middot;xP + a) / 2&middot;yP  if P = Q (point doubling).

```

Remark: there already is a task page requesting “a simplified (without modular arithmetic) version of the [[Elliptic_curve_arithmetic|elliptic curve arithmetic]]”. Here we do add modulo operations. If also the domain is changed from reals to rationals, the elliptic curves are no longer continuous but break up into a finite number of distinct points. In that form we use them to implement [[wp:Elliptic_Curve_Digital_Signature_Algorithm|ECDSA]]:

;Elliptic curve digital signature algorithm.

A [[wp:Digital_signature|digital signature]] is the electronic analogue of a hand-written signature that convinces the recipient that a message has been sent intact by the presumed sender. Anyone with access to the public key of the signer may verify this signature. Changing even a single bit of a signed message will cause the verification procedure to fail.

'''ECDSA key generation.''' Party A does the following:

1. Select an elliptic curve E defined over ℤp.
The number of points in E(ℤp) should be divisible by a large prime r.
2. Select a base point G ∈ E(ℤp) of order r (which means that rG = 𝒪).
3. Select a random integer s in the interval [1, r - 1].
4. Compute W = sG.
The public key is (E, G, r, W), the private key is s.

'''ECDSA signature computation.''' To sign a message m, A does the following:

1. Compute message representative f = H(m), using a [[wp:Cryptographic_hash_function|cryptographic hash function]].
Note that f can be greater than r but not longer (measuring bits).
2. Select a random integer u in the interval [1, r - 1].
3. Compute V = uG = (xV, yV) and c ≡ xV mod r (goto (2) if c = 0).
4. Compute d ≡ u^-1·(f + s·c) mod r (goto (2) if d = 0).
The signature for the message m is the pair of integers (c, d).

'''ECDSA signature verification.''' To verify A's signature, B should do the following:

1. Obtain an authentic copy of A's public key (E, G, r, W).
Verify that c and d are integers in the interval [1, r - 1].
2. Compute f = H(m) and h ≡ d^-1 mod r.
3. Compute h1 ≡ f·h mod r and h2 ≡ c·h mod r.
4. Compute h1G + h2W = (x1, y1) and c1 ≡ x1 mod r.
Accept the signature if and only if c1 = c.

To be cryptographically useful, the parameter r should have at least 250 bits. The basis for the security of [[wp:Elliptic-curve_cryptography|elliptic curve cryptosystems]] is the intractability of the elliptic curve discrete logarithm problem (ECDLP) in a group of this size: given two points G, W ∈ E(ℤp), where W lies in the subgroup of order r generated by G, determine an integer k such that W = kG and 0 ≤ k < r.

The task is to write a '''toy version''' of the ECDSA, quasi the equal of a real-world implementation, but utilizing parameters that fit into standard arithmetic types. To keep things simple there's no need for key export or a hash function (just a sample hash value and a way to tamper with it). The program should be lenient where possible (for example: if it accepts a composite modulus N it will either function as expected, or demonstrate the principle of [[wp:Lenstra_elliptic-curve_factorization|elliptic curve factorization]]) — but strict where required (a point G that is not on E will always cause failure).
Toy ECDSA is of course completely useless for its cryptographic purpose. If this bothers you, please add a multiple-precision version.

;Reference.

Elliptic curves are in the [https://perso.telecom-paristech.fr/guilley/recherche/cryptoprocesseurs/ieee/00891000.pdf IEEE Std 1363-2000] (Standard Specifications for Public-Key Cryptography), see:

1. Primitives based on the elliptic curve discrete logarithm problem (p. 27ff.)

7.1 The EC setting
7.1.2 EC domain parameters
7.1.3 EC key pairs

7.2 Primitives
7.2.7 ECSP-DSA (p. 35)
7.2.8 ECVP-DSA (p. 36)

Annex A. Number-theoretic background
A.9 Elliptic curves: overview (p. 115)
A.10 Elliptic curves: algorithms (p. 121)

TOC

## C

Parallel to: FreeBASIC

```
/*
subject: Elliptic curve digital signature algorithm,
toy version for small modulus N.
tested : gcc 4.6.3, tcc 0.9.27
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 64-bit integer type
typedef long long int dlong;
// rational ec point
typedef struct {
dlong x, y;
} epnt;
// elliptic curve parameters
typedef struct {
long a, b;
dlong N;
epnt G;
dlong r;
} curve;
// signature pair
typedef struct {
long a, b;
} pair;

// dlong for holding intermediate results,
// long variables in exgcd() for efficiency,
// maximum parameter size 2 * p.y (line 129)
// limits the modulus size to 30 bits.

// maximum modulus
const long mxN = 1073741789;
// max order G = mxN + 65536
const long mxr = 1073807325;
// symbolic infinity
const long inf = -2147483647;

// single global curve
curve e;
// point at infinity zerO
epnt zerO;
// impossible inverse mod N
int inverr;

// return mod(v^-1, u)
long exgcd (long v, long u)
{
register long q, t;
long r = 0, s = 1;
if (v < 0) v += u;

while (v) {
q = u / v;
t = u - q * v;
u = v; v = t;
t = r - q * s;
r = s; s = t;
}
if (u != 1) {
printf (" impossible inverse mod N, gcd = %d\n", u);
inverr = 1;
}
return r;
}

// return mod(a, N)
static inline dlong modn (dlong a)
{
a %= e.N;
if (a < 0) a += e.N;
return a;
}

// return mod(a, r)
dlong modr (dlong a)
{
a %= e.r;
if (a < 0) a += e.r;
return a;
}

// return the discriminant of E
long disc (void)
{
dlong c, a = e.a, b = e.b;
c = 4 * modn(a * modn(a * a));
return modn(-16 * (c + 27 * modn(b * b)));
}

// return 1 if P = zerO
int isO (epnt p)
{
return (p.x == inf) && (p.y == 0);
}

// return 1 if P is on curve E
int ison (epnt p)
{
long r, s;
if (! isO (p)) {
r = modn(e.b + p.x * modn(e.a + p.x * p.x));
s = modn(p.y * p.y);
}
return (r == s);
}

void padd (epnt *r, epnt p, epnt q)
{
dlong la, t;

if (isO(p)) {*r = q; return;}
if (isO(q)) {*r = p; return;}

if (p.x != q.x) {                    // R:= P + Q
t = p.y - q.y;
la = modn(t * exgcd(p.x - q.x, e.N));
}
else                                 // P = Q, R := 2P
if ((p.y == q.y) && (p.y != 0)) {
t = modn(3 * modn(p.x * p.x) + e.a);
la = modn(t * exgcd (2 * p.y, e.N));
}
else
{*r = zerO; return;}           // P = -Q, R := O

t = modn(la * la - p.x - q.x);
r->y = modn(la * (p.x - t) - p.y);
r->x = t; if (inverr) *r = zerO;
}

// R:= multiple kP
void pmul (epnt *r, epnt p, long k)
{
epnt s = zerO, q = p;

for (; k; k >>= 1) {
if (k & 1) padd(&s, s, q);
if (inverr) {s = zerO; break;}
}
*r = s;
}

// print point P with prefix f
void pprint (char *f, epnt p)
{
dlong y = p.y;

if (isO (p))
printf ("%s (0)\n", f);

else {
if (y > e.N - y) y -= e.N;
printf ("%s (%lld, %lld)\n", f, p.x, y);
}
}

// initialize elliptic curve
int ellinit (long i[])
{
long a = i, b = i;
e.N = i; inverr = 0;

if ((e.N < 5) || (e.N > mxN)) return 0;

e.a = modn(a);
e.b = modn(b);
e.G.x = modn(i);
e.G.y = modn(i);
e.r = i;

if ((e.r < 5) || (e.r > mxr)) return 0;

printf ("\nE: y^2 = x^3 + %dx + %d", a, b);
printf (" (mod %lld)\n", e.N);
pprint ("base point G", e.G);
printf ("order(G, E) = %lld\n", e.r);

return 1;
}

// pseudorandom number [0..1)
double rnd(void)
{
return rand() / ((double)RAND_MAX + 1);
}

// signature primitive
pair signature (dlong s, long f)
{
long c, d, u, u1;
pair sg;
epnt V;

printf ("\nsignature computation\n");
do {
do {
u = 1 + (long)(rnd() * (e.r - 1));
pmul (&V, e.G, u);
c = modr(V.x);
}
while (c == 0);

u1 = exgcd (u, e.r);
d = modr(u1 * (f + modr(s * c)));
}
while (d == 0);
printf ("one-time u = %d\n", u);
pprint ("V = uG", V);

sg.a = c; sg.b = d;
return sg;
}

// verification primitive
int verify (epnt W, long f, pair sg)
{
long c = sg.a, d = sg.b;
long t, c1, h1, h2;
dlong h;
epnt V, V2;

// domain check
t = (c > 0) && (c < e.r);
t &= (d > 0) && (d < e.r);
if (! t) return 0;

printf ("\nsignature verification\n");
h = exgcd (d, e.r);
h1 = modr(f * h);
h2 = modr(c * h);
printf ("h1,h2 = %d, %d\n", h1,h2);
pmul (&V, e.G, h1);
pmul (&V2, W, h2);
pprint ("h1G", V);
pprint ("h2W", V2);
pprint ("+ =", V);
if (isO (V)) return 0;
c1 = modr(V.x);
printf ("c' = %d\n", c1);

return (c1 == c);
}

// digital signature on message hash f, error bit d
void ec_dsa (long f, long d)
{
long i, s, t;
pair sg;
epnt W;

// parameter check
t = (disc() == 0);
t |= isO (e.G);
pmul (&W, e.G, e.r);
t |= ! isO (W);
t |= ! ison (e.G);
if (t) goto errmsg;

printf ("\nkey generation\n");
s = 1 + (long)(rnd() * (e.r - 1));
pmul (&W, e.G, s);
printf ("private key s = %d\n", s);
pprint ("public key W = sG", W);

// next highest power of 2 - 1
t = e.r;
for (i = 1; i < 32; i <<= 1)
t |= t >> i;
while (f > t) f >>= 1;
printf ("\naligned hash %x\n", f);

sg = signature (s, f);
if (inverr) goto errmsg;
printf ("signature c,d = %d, %d\n", sg.a, sg.b);

if (d > 0) {
while (d > t) d >>= 1;
f ^= d;
printf ("\ncorrupted hash %x\n", f);
}

t = verify (W, f, sg);
if (inverr) goto errmsg;
if (t)
printf ("Valid\n_____\n");
else
printf ("invalid\n_______\n");

return;

errmsg:
printf ("invalid parameter set\n");
printf ("_____________________\n");
}

void main (void)
{
typedef long eparm;
long d, f;
zerO.x = inf; zerO.y = 0;
srand(time(NULL));

// Test vectors: elliptic curve domain parameters,
// short Weierstrass model y^2 = x^3 + ax + b (mod N)
eparm *sp, sets = {
//    a,   b,  modulus N, base point G, order(G, E), cofactor
{355, 671, 1073741789, 13693, 10088, 1073807281},
{  0,   7,   67096021,  6580,   779,   16769911}, // 4
{ -3,   1,     877073,     0,     1,     878159},
{  0,  14,      22651,    63,    30,        151}, // 151
{  3,   2,          5,     2,     1,          5},

// ecdsa may fail if...
// the base point is of composite order
{  0,   7,   67096021,  2402,  6067,   33539822}, // 2
// the given order is a multiple of the true order
{  0,   7,   67096021,  6580,   779,   67079644}, // 1
// the modulus is not prime (deceptive example)
{  0,   7,     877069,     3, 97123,     877069},
// fails if the modulus divides the discriminant
{ 39, 387,      22651,    95,    27,      22651},
};
// Digital signature on message hash f,
// set d > 0 to simulate corrupted data
f = 0x789abcde; d = 0;

for (sp = sets; ; sp++) {
if (ellinit (*sp))
ec_dsa (f, d);

else
break;
}
}

```

{{out}} (tcc, srand(1); first set only)

```
E: y^2 = x^3 + 355x + 671 (mod 1073741789)
base point G (13693, 10088)
order(G, E) = 1073807281

key generation
private key s = 1343570
public key W = sG (817515107, -192163292)

aligned hash 789abcde

signature computation
one-time u = 605163545
V = uG (464115167, -267961770)
signature c,d = 464115167, 407284989

signature verification
h1,h2 = 871754294, 34741072
h1G (708182134, 29830217)
h2W (270156466, -328492261)
+ = (464115167, -267961770)
c' = 464115167
Valid
_____

```

## FreeBASIC

Parallel to: C

```
'subject: Elliptic curve digital signature algorithm,
'         toy version for small modulus N.
'tested : FreeBasic 1.05.0

'rational ec point
type epnt
as longint x, y
end type
'elliptic curve parameters
type curve
as long a, b
as longint N
as epnt G
as longint r
end type
'signature pair
type pair
as long a, b
end type

'longint for holding intermediate results,
'long variables in exgcd() for efficiency,
'maximum parameter size 2 * p.y (line 118)
'limits the modulus size to 30 bits.

'maximum modulus
const mxN = 1073741789
'max order G = mxN + 65536
const mxr = 1073807325
'symbolic infinity
const inf = -2147483647

'single global curve
dim shared as curve e
'point at infinity zerO
dim shared as epnt zerO
'impossible inverse mod N
dim shared as byte inverr

'return mod(v^-1, u)
Function exgcd (byval v as long, byval u as long) as long
dim as long q, t
dim as long r = 0, s = 1
if v < 0 then v += u

while v
q = u \ v
t = u - q * v
u = v: v = t
t = r - q * s
r = s: s = t
wend

if u <> 1 then
print " impossible inverse mod N, gcd ="; u
inverr = -1
end if

exgcd = r
End Function

'return mod(a, N)
Function modn (byval a as longint) as longint
a mod= e.N
if a < 0 then a += e.N
modn = a
End Function

'return mod(a, r)
Function modr (byval a as longint) as longint
a mod= e.r
if a < 0 then a += e.r
modr = a
End Function

'return the discriminant of E
Function disc as long
dim as longint c, a = e.a, b = e.b
c = 4 * modn(a * modn(a * a))
disc = modn(-16 * (c + 27 * modn(b * b)))
End Function

'return -1 if P = zerO
Function isO (byref p as epnt) as byte
isO = (p.x = inf and p.y = 0)
End Function

'return -1 if P is on curve E
Function ison (byref p as epnt) as byte
dim as long r, s
if not isO (p) then
r = modn(e.b + p.x * modn(e.a + p.x * p.x))
s = modn(p.y * p.y)
end if
ison = (r = s)
End Function

Sub padd (byref r as epnt, byref p as epnt, byref q as epnt)
dim as longint la, t

if isO (p) then r = q: exit sub
if isO (q) then r = p: exit sub

if p.x <> q.x then '                   R := P + Q
t = p.y - q.y
la = modn(t * exgcd (p.x - q.x, e.N))

else '                                 P = Q, R := 2P
if (p.y = q.y) and (p.y <> 0) then
t = modn(3 * modn(p.x * p.x) + e.a)
la = modn(t * exgcd (2 * p.y, e.N))

else
r = zerO: exit sub '             P = -Q, R := O
end if
end if

t = modn(la * la - p.x - q.x)
r.y = modn(la * (p.x - t) - p.y)
r.x = t: if inverr then r = zerO
End Sub

'R:= multiple kP
Sub pmul (byref r as epnt, byref p as epnt, byval k as long)
dim as epnt s = zerO, q = p

while k
if k and 1 then padd (s, s, q)
if inverr then s = zerO: exit while
k shr= 1: padd (q, q, q)
wend
r = s
End Sub

'print point P with prefix f
Sub pprint (byref f as string, byref p as epnt)
dim as longint y = p.y

if isO (p) then
print f;" (0)"

else
if y > e.N - y then y -= e.N
print f;" (";str(p.x);",";y;")"

end if
End Sub

'initialize elliptic curve
Function ellinit (i() as long) as byte
dim as long a = i(0), b = i(1)
ellinit = 0: inverr = 0
e.N = i(2)

if (e.N < 5) or (e.N > mxN) then exit function

e.a = modn(a)
e.b = modn(b)
e.G.x = modn(i(3))
e.G.y = modn(i(4))
e.r = i(5)

if (e.r < 5) or (e.r > mxr) then exit function

print : ? "E: y^2 = x^3 + ";str(a);"x +";b;
print " (mod ";str(e.N);")"
pprint ("base point G", e.G)
print "order(G, E) ="; e.r

ellinit = -1
End Function

'signature primitive
Function signature (byval s as longint, byval f as long) as pair
dim as long c, d, u, u1
dim as pair sg
dim as epnt V

print : ? "signature computation"
do
do
u = 1 + int(rnd * (e.r - 1))
pmul (V, e.G, u)
c = modr(V.x)
loop while c = 0

u1 = exgcd (u, e.r)
d = modr(u1 * (f + modr(s * c)))
loop while d = 0
print "one-time u ="; u
pprint ("V = uG", V)

sg.a = c: sg.b = d
signature = sg
End Function

'verification primitive
Function verify (byref W as epnt, byval f as long, byref sg as pair) as byte
dim as long c = sg.a, d = sg.b
dim as long t, c1, h1, h2
dim as longint h
dim as epnt V, V2
verify = 0

'domain check
t = (c > 0) and (c < e.r)
t and= (d > 0) and (d < e.r)
if not t then exit function

print : ? "signature verification"
h = exgcd (d, e.r)
h1 = modr(f * h)
h2 = modr(c * h)
print "h1,h2 ="; h1;",";h2
pmul (V, e.G, h1)
pmul (V2, W, h2)
pprint ("h1G", V)
pprint ("h2W", V2)
pprint ("+ =", V)
if isO (V) then exit function
c1 = modr(V.x)
print "c' ="; c1

verify = (c1 = c)
End Function

'digital signature on message hash f, error bit d
Sub ec_dsa (byval f as long, byval d as long)
dim as long i, s, t
dim as pair sg
dim as epnt W

'parameter check
t = (disc = 0)
t or= isO (e.G)
pmul (W, e.G, e.r)
t or= not isO (W)
t or= not ison (e.G)
if t then goto errmsg

print : ? "key generation"
s = 1 + int(rnd * (e.r - 1))
pmul (W, e.G, s)
print "private key s ="; s
pprint ("public key W = sG", W)

'next highest power of 2 - 1
t = e.r: i = 1
while i < 32
t or= t shr i: i shl= 1
wend
while f > t
f shr= 1: wend
print : ? "aligned hash "; hex(f)

sg = signature (s, f)
if inverr then goto errmsg
print "signature c,d ="; sg.a;",";sg.b

if d > 0 then
while d > t
d shr= 1: wend
f xor= d
print : ? "corrupted hash "; hex(f)
end if

t = verify (W, f, sg)
if inverr then goto errmsg
if t then
print "Valid" : ? "_____"
else
print "invalid" : ? "_______"
end if

exit sub

errmsg:
print "invalid parameter set"
print "_____________________"
End Sub

'main
dim as long d, f, t, eparm(5)
zerO.x = inf: zerO.y = 0
randomize timer

'Test vectors: elliptic curve domain parameters,
'short Weierstrass model y^2 = x^3 + ax + b (mod N)

'      a,   b,  modulus N, base point G, order(G, E), cofactor
data 355, 671, 1073741789, 13693, 10088, 1073807281
data   0,   7,   67096021,  6580,   779,   16769911 '   4
data  -3,   1,     877073,     0,     1,     878159
data   0,  14,      22651,    63,    30,        151 ' 151
data   3,   2,          5,     2,     1,          5

'ecdsa may fail if...
'the base point is of composite order
data   0,   7,   67096021,  2402,  6067,   33539822 '   2
'the given order is a multiple of the true order
data   0,   7,   67096021,  6580,   779,   67079644 '   1
'the modulus is not prime (deceptive example)
data   0,   7,     877069,     3, 97123,     877069
'fails if the modulus divides the discriminant
data  39, 387,      22651,    95,    27,      22651
data   0, 0, 0

'Digital signature on message hash f,
'set d > 0 to simulate corrupted data
f = &h789ABCDE : d = 0

do
for t = 0 to 5

if ellinit (eparm()) then
ec_dsa (f, d)

else
exit do

end if
loop

system

```

{{out}} (randomize 1, first set only)

```
E: y^2 = x^3 + 355x + 671 (mod 1073741789)
base point G (13693, 10088)
order(G, E) = 1073807281

key generation
private key s = 509100772
public key W = sG (992563138, 238074938)

aligned hash 789ABCDE

signature computation
one-time u = 571533488
V = uG (896670665, 183547995)
signature c,d = 896670665, 728505276

signature verification
h1,h2 = 667118700, 709185150
h1G (315367421, 343743703)
h2W (1040319975,-262613483)
+ = (896670665, 183547995)
c' = 896670665
Valid
_____

```

## Go

Since Go has an ECDSA package in its standard library which uses 'big integers', we use that rather than translating one of the reference implementations for a 'toy' version into Go.

```package main

import (
"crypto/ecdsa"
"crypto/elliptic"
"crypto/rand"
"crypto/sha256"
"encoding/binary"
"fmt"
"log"
)

func check(err error) {
if err != nil {
log.Fatal(err)
}
}

func main() {
check(err)
fmt.Println("Private key:\nD:", priv.D)
pub := priv.Public().(*ecdsa.PublicKey)
fmt.Println("\nPublic key:")
fmt.Println("X:", pub.X)
fmt.Println("Y:", pub.Y)

msg := "Rosetta Code"
fmt.Println("\nMessage:", msg)
hash := sha256.Sum256([]byte(msg)) // as byte
hexHash := fmt.Sprintf("0x%x", binary.BigEndian.Uint32(hash[:]))
fmt.Println("Hash   :", hexHash)

r, s, err := ecdsa.Sign(rand.Reader, priv, hash[:])
check(err)
fmt.Println("\nSignature:")
fmt.Println("R:", r)
fmt.Println("S:", s)

valid := ecdsa.Verify(&priv.PublicKey, hash[:], r, s)
fmt.Println("\nSignature verified:", valid)
}
```

{{out}} Sample run:

```
Private key:
D: 25700608762903774973512323993645267346590725880891580901973011512673451968935

Public key:
X: 37298454876588653961191059192981094503652951300904260069480867699946371240473
Y: 69073688506493709421315518164229531832022167466292360349457318041854718641652

Message: Rosetta Code
Hash   : 0xe6f9ed0d

Signature:
R: 91827099055706804696234859308003894767808769875556550819128270941615405955877
S: 20295707309473352071389945163735458699476300346398176659149368970668313772860

Signature verified: true

```

## Phix

{{trans|FreeBASIC}}

```enum X, Y            -- rational ec point
enum A, B, N, G, R  -- elliptic curve parameters
-- also signature pair(A,B)

constant mxN = 1073741789   -- maximum modulus
constant mxr = 1073807325   -- max order G = mxN + 65536
constant inf = -2147483647  -- symbolic infinity

sequence e = {0,0,0,{0,0},0}    -- single global curve
constant zerO = {inf,0}         -- point at infinity zerO

bool inverr -- impossible inverse mod N

function exgcd(atom v, u)
-- return mod(v^-1, u)
atom q, t, r = 0, s = 1
if v<0 then v += u end if

while v do
q = floor(u/v)
t = u-q*v
u = v
v = t
t = r-q*s
r = s
s = t
end while

if u!=1 then
printf(1," impossible inverse mod N, gcd = %d\n",{u})
inverr = true
end if

return r
end function

function modn(atom a)
-- return mod(a, N)
a = mod(a,e[N])
if a<0 then a += e[N] end if
return a
end function

function modr(atom a)
-- return mod(a, r)
a = mod(a,e[R])
if a<0 then a += e[R] end if
return a
end function

function disc()
-- return the discriminant of E
atom a = e[A], b = e[B],
c = 4*modn(a*modn(a*a))
return modn(-16*(c+27*modn(b*b)))
end function

function isO(sequence p)
-- return true if P = zerO
return (p[X]=inf and p[Y]=0)
end function

function ison(sequence p)
-- return true if P is on curve E
atom r = 0, s = 0
if not isO(p) then
r = modn(e[B]+p[X]*modn(e[A]+p[X]*p[X]))
s = modn(p[Y]*p[Y])
end if
return (r=s)
end function

procedure pprint(string f, sequence p)
-- print point P with prefix f
if isO(p) then
printf(1,"%s (0)\n",{f})
else
atom y = p[Y]
if y>e[N]-y then y -= e[N] end if
printf(1,"%s (%d,%d)\n",{f,p[X],y})
end if
end procedure

atom la, t

if isO(p) then return q end if
if isO(q) then return p end if

if p[X]!=q[X] then --                   R := P + Q
t = p[Y]-q[Y]
la = modn(t*exgcd(p[X]-q[X], e[N]))

else --                                 P = Q, R := 2P
if (p[Y]=q[Y]) and (p[Y]!=0) then
t = modn(3*modn(p[X]*p[X])+e[A])
la = modn(t*exgcd(2*p[Y], e[N]))
else
return zerO --                  P = -Q, R := O
end if
end if

t = modn(la*la-p[X]-q[X])
sequence r = zerO
r[Y] = modn(la*(p[X]-t)-p[Y])
r[X] = t
if inverr then r = zerO end if
return r
end function

function pmul(sequence p, atom k)
-- R:= multiple kP
sequence s = zerO, q = p

while k do
if and_bits(k,1) then
end if
if inverr then s = zerO; exit end if
k = floor(k/2)
end while
return s
end function

function ellinit(sequence i)
-- initialize elliptic curve
atom a = i, b = i
inverr = false
e[N] = i

if (e[N]<5) or (e[N]>mxN) then return 0 end if

e[A] = modn(a)
e[B] = modn(b)
e[G][X] = modn(i)
e[G][Y] = modn(i)
e[R] = i

if (e[R]<5) or (e[R]>mxr) then return 0 end if

printf(1,"E: y^2 = x^3 + %dx + %d (mod %d)\n",{a,b,e[N]})
pprint("base point G", e[G])
printf(1,"order(G, E) = %d\n",{e[R]})

return -1
end function

function signature(atom s, f)
-- signature primitive
atom c, d, u, u1
sequence V

printf(1,"signature computation\n")
while true do
while true do
--          u = rand(e[R]-1)
u = 571533488       -- match FreeBASIC output
--          u = 605163545       -- match C output
V = pmul(e[G], u)
c = modr(V[X])
if c!=0 then exit end if
end while

u1 = exgcd(u, e[R])
d = modr(u1*(f+modr(s*c)))
if d!=0 then exit end if
end while
printf(1,"one-time u = %d\n",u)
pprint("V = uG", V)
return {c,d}
end function

function verify(sequence W, atom f, sequence sg)
-- verification primitive
atom c = sg[A], d = sg[B],
t, c1, h1, h2, h
sequence V, V2

--domain check
t = (c>0) and (c<e[R])
t = t and (d>0) and (d<e[R])
if not t then return 0 end if

printf(1,"\nsignature verification\n")
h = exgcd(d, e[R])
h1 = modr(f*h)
h2 = modr(c*h)
printf(1,"h1,h2 = %d,%d\n",{h1,h2})
V = pmul(e[G], h1)
V2 = pmul(W, h2)
pprint("h1G", V)
pprint("h2W", V2)
pprint("+ =", V)
if isO(V) then return 0 end if
c1 = modr(V[X])
printf(1,"c' = %d\n",c1)

return (c1=c)
end function

procedure errmsg()
printf(1,"invalid parameter set\n")
printf(1,"_____________________\n")
end procedure

procedure ec_dsa(atom f, d)
-- digital signature on message hash f, error bit d
atom i, s, t
sequence sg, W

--parameter check
t = (disc()=0)
t = t or isO(e[G])
W = pmul(e[G], e[R])
t = t or not isO(W)
t = t or not ison(e[G])
if t then errmsg() return end if

puts(1,"\nkey generation\n")
--  s = rand(e[R] - 1)
s = 509100772       -- match FreeBASIC output
--  s = 1343570         -- match C output
W = pmul(e[G], s)
printf(1,"private key s = %d\n",{s})
pprint("public key W = sG", W)

--next highest power of 2 - 1
t = e[R]
i = 1
while i<32 do
t = or_bits(t,floor(t/power(2,i)))
i *= 2
end while
while f>t do
f = floor(f/2)
end while
printf(1,"\naligned hash %x\n\n",{f})

sg = signature(s, f)
if inverr then errmsg() return end if
printf(1,"signature c,d = %d,%d\n",sg)

if d>0 then
while d>t do
d = floor(d/2)
end while
f = xor_bits(f,d)
printf(1,"corrupted hash %x\n",{f})
end if

t = verify(W, f, sg)
if inverr then errmsg() return end if
if t then
printf(1,"Valid\n_____\n")
else
printf(1,"invalid\n_______\n")
end if
end procedure

--Test vectors: elliptic curve domain parameters,
--short Weierstrass model y^2 = x^3 + ax + b (mod N)

constant tests = {
--                  a,   b,  modulus N, base point G, order(G, E), cofactor
{355, 671, 1073741789, 13693, 10088, 1073807281},
{  0,   7,   67096021,  6580,   779,   16769911}, --   4
{ -3,   1,     877073,     0,     1,     878159},
{  0,  14,      22651,    63,    30,        151}, -- 151
{  3,   2,          5,     2,     1,          5},

--ecdsa may fail if...
--the base point is of composite order
{  0,   7,   67096021,  2402,  6067,   33539822}, --   2
--the given order is a multiple of the true order
{  0,   7,   67096021,  6580,   779,   67079644}, --   1
--the modulus is not prime (deceptive example)
{  0,   7,     877069,     3, 97123,     877069},
--fails if the modulus divides the discriminant
{ 39, 387,      22651,    95,    27,      22651}}

--Digital signature on message hash f,
--set d > 0 to simulate corrupted data
atom f = #789ABCDE,
d = 0

if machine_bits()!=64 then crash("needs 64 bit") end if
--for i=1 to length(tests) do
for i=1 to 1 do
if not ellinit(tests[i]) then exit end if
ec_dsa(f, d)
end for
```

{{out}} Note the above only performs tests, and assigns literal values in place of rand(), in order to exactly match the FreeBASIC/C output.

```
E: y^2 = x^3 + 355x + 671 (mod 1073741789)
base point G (13693,10088)
order(G, E) = 1073807281

key generation
private key s = 509100772
public key W = sG (992563138,238074938)

aligned hash 789ABCDE

signature computation
one-time u = 571533488
V = uG (896670665,183547995)
signature c,d = 896670665,728505276

signature verification
h1,h2 = 667118700,709185150
h1G (315367421,343743703)
h2W (1040319975,-262613483)
+ = (896670665,183547995)
c' = 896670665
Valid
_____

```