I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Elliptic Curve Digital Signature Algorithm

Elliptic Curve Digital Signature Algorithm
You are encouraged to solve this task according to the task description, using any language you may know.
Elliptic curves.

An 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 + 𝒪 = 𝒪 + P = P for all P ∈ E(ℤp).

2. If P = (x, y) ∈ E(ℤp), then inverse -P = (x,-y), and P + (-P) = 𝒪.

3. Let P = (xP, yP) and Q = (xQ, yQ), both ∈ E(ℤp), where P ≠ -Q.
Then R = P + Q = (xR, yR), where

xR = λ^2 - xP - xQ
yR = λ·(xP - xR) - yP,

with

λ = (yP - yQ) / (xP - xQ) if P ≠ Q,
(3·xP·xP + a) / 2·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”. 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 ECDSA:

Elliptic curve digital signature algorithm.

A 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 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 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 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 IEEE Std 1363-2000 (Standard Specifications for Public-Key Cryptography), see:

7. 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)

## 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 typetypedef long long int dlong;// rational ec pointtypedef struct {   dlong x, y;} epnt;// elliptic curve parameterstypedef struct {   long a, b;   dlong N;   epnt G;   dlong r;} curve;// signature pairtypedef 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 modulusconst long mxN = 1073741789;// max order G = mxN + 65536const long mxr = 1073807325;// symbolic infinityconst long inf = -2147483647; // single global curvecurve e;// point at infinity zerOepnt zerO;// impossible inverse mod Nint 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 Elong 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 = zerOint isO (epnt p){return (p.x == inf) && (p.y == 0);} // return 1 if P is on curve Eint 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);}  // full ec point additionvoid 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 kPvoid 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;}      padd(&q, q, q);   }*r = s;}  // print point P with prefix fvoid 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 curveint ellinit (long i[]){long a = i[0], b = i[1];   e.N = i[2]; inverr = 0; if ((e.N < 5) || (e.N > mxN)) return 0;    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) || (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 primitivepair 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 primitiveint 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);   padd (&V, V, 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 dvoid 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[6];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[10] = {//    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;   }} `
Output:

(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 pointtype epnt   as longint x, yend type'elliptic curve parameterstype curve   as long a, b   as longint N   as epnt G   as longint rend type'signature pairtype pair   as long a, bend 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 modulusconst mxN = 1073741789'max order G = mxN + 65536const mxr = 1073807325'symbolic infinityconst inf = -2147483647 'single global curvedim shared as curve e'point at infinity zerOdim shared as epnt zerO'impossible inverse mod Ndim shared as byte inverr  'return mod(v^-1, u)Function exgcd (byval v as long, byval u as long) as longdim as long q, tdim as long r = 0, s = 1if 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 = rEnd Function 'return mod(a, N)Function modn (byval a as longint) as longint   a mod= e.N   if a < 0 then a += e.Nmodn = aEnd Function 'return mod(a, r)Function modr (byval a as longint) as longint   a mod= e.r   if a < 0 then a += e.rmodr = aEnd Function  'return the discriminant of EFunction disc as longdim 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 = zerOFunction isO (byref p as epnt) as byteisO = (p.x = inf and p.y = 0)End Function 'return -1 if P is on curve EFunction ison (byref p as epnt) as bytedim as long r, sif not isO (p) then   r = modn(e.b + p.x * modn(e.a + p.x * p.x))   s = modn(p.y * p.y)end ifison = (r = s)End Function  'full ec point additionSub 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 subif 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 ifend 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 = zerOEnd Sub 'R:= multiple kPSub 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)   wendr = sEnd Sub  'print point P with prefix fSub 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 ifEnd Sub 'initialize elliptic curveFunction ellinit (i() as long) as bytedim 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 = -1End Function  'signature primitiveFunction signature (byval s as longint, byval f as long) as pairdim as long c, d, u, u1dim as pair sgdim 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 = 0print "one-time u ="; upprint ("V = uG", V) sg.a = c: sg.b = dsignature = sgEnd Function 'verification primitiveFunction verify (byref W as epnt, byval f as long, byref sg as pair) as bytedim as long c = sg.a, d = sg.bdim as long t, c1, h1, h2dim as longint hdim as epnt V, V2verify = 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)   padd (V, V, 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 dSub ec_dsa (byval f as long, byval d as long)dim as long i, s, tdim as pair sgdim 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  'maindim as long d, f, t, eparm(5)zerO.x = inf: zerO.y = 0randomize 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), cofactordata 355, 671, 1073741789, 13693, 10088, 1073807281data   0,   7,   67096021,  6580,   779,   16769911 '   4data  -3,   1,     877073,     0,     1,     878159data   0,  14,      22651,    63,    30,        151 ' 151data   3,   2,          5,     2,     1,          5 'ecdsa may fail if...'the base point is of composite orderdata   0,   7,   67096021,  2402,  6067,   33539822 '   2'the given order is a multiple of the true orderdata   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 discriminantdata  39, 387,      22651,    95,    27,      22651data   0, 0, 0 'Digital signature on message hash f,'set d > 0 to simulate corrupted dataf = &h789ABCDE : d = 0 do   for t = 0 to 5      read eparm(t): next    if ellinit (eparm()) then      ec_dsa (f, d)    else      exit do    end ifloop system `
Output:

(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() {    priv, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)    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 [32]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)}`
Output:

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

## Julia

`module ToyECDSA using SHA import Base.in, Base.==, Base.+, Base.* export ECDSA_Key, ECDSA_Public_Key, genkey, ECDSA_sign, isverifiedECDSA # T will be BigInt in most applicationsstruct CurveFP{T}    p::T    a::T    b::T    CurveFP(p, a::T, b::T) where T <: Number = new{T}(p, a, b)end struct PointEC{T}    curve::CurveFP{T}    x::T    y::T    order::Union{Number, Nothing}    function PointEC(curve, x::T, y::T, order=nothing) where T <: Number        @assert((x, y) in curve)        new{T}(curve, x, y, order)    endend struct PointINF endconst INFINITY = PointINF() function ==(point_a::PointEC, point_b::PointEC)    if point_a.curve == point_b.curve && point_a.x == point_b.x && point_a.y == point_b.y        return true    end    return falseend function ==(curve_a::CurveFP, curve_b::CurveFP)    if curve_a.a == curve_b.a && curve_a.b == curve_b.b && curve_a.p == curve_b.p        return true    end    return falseend +(point_a::PointINF, point_b::PointINF) = point_b+(point_a::PointINF, point_b::PointEC) = point_b+(point_a::PointEC, point_b::PointINF) = point_a function +(point_a::PointEC, point_b::PointEC)     @assert(point_a.curve == point_b.curve)     if point_a.x == point_b.x         if (point_a.y + point_b.y) % point_a.curve.p == 0             return INFINITY         else             return double(point_a)        end    end    p = point_a.curve.p    λ = (point_a.y - point_b.y) * invmod(point_a.x - point_b.x, p)    xr = mod(λ * λ - point_a.x - point_b.x, p)    yr = mod(λ * (point_a.x - xr) - point_a.y, p)    return PointEC(point_a.curve, xr, yr, point_a.order)end *(point_a::PointINF, int_b::Number) = INFINITY*(int_b::Number, point_a::PointINF) = INFINITY*(int_b::Number, point_a::PointEC) = point_a * int_b function *(point_a::PointEC, int_b::Number)    leftmost_bit(x) = big"2"^Int(trunc(log(2, x)))    if point_a.order != nothing        int_b %= point_a.order    end    if int_b == 0        return INFINITY    end    int_3b = 3 * int_b    negative_a = PointEC(point_a.curve, point_a.x, -point_a.y, point_a.order)    i = BigInt(leftmost_bit(int_3b) ÷ 2)    result = point_a    while i > 1        result = double(result)        if (int_3b & i) != 0 && (int_b & i) == 0            result += point_a        end        if (int_3b & i) == 0 && (int_b & i) != 0            result += negative_a        end        i ÷= 2    end    return resultend in(z::Tuple, curve::CurveFP) = (z[2]^2 - (z[1]^3 + curve.a*z[1] + curve.b)) % curve.p == 0in(x::Number,y::Number, curve::CurveFP) = (y^2 -(x^3 + curve.a*x + curve.b)) % curve.p == 0in(p::PointEC, curve::CurveFP) = (p.y^2 - (p.x^3 + curve.a * p.x + curve.b)) % curve.p == 0in(point::PointINF, curve::CurveFP) = true double(point_a::PointINF) = INFINITY function double(point_a::PointEC)  a, p = point_a.curve.a, point_a.curve.p  l = mod((3 * point_a.x^2 + a) * invmod(2 * point_a.y, p), p)  x3 = mod(l^2 - 2 * point_a.x, p)  y3 = mod(l * (point_a.x - x3) - point_a.y, p)  return PointEC(point_a.curve, x3, y3, point_a.order)end const secp256k1 = (  # use the Bitcoin ECDSA curve    p = big"0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F",    a = big"0x0",    b = big"0x7",    r = big"0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141",    Gx = big"0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",    Gy = big"0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8",)@assert((secp256k1.Gy^2 - secp256k1.Gx^3 - 7) % secp256k1.p == 0) function generatemultiplier(stdcurve)    return foldl((x, y) -> 16 * BigInt(x) + y, rand(0:16, ndigits(stdcurve.r - 1, base=16)))end struct ECDSA_Key    E::CurveFP    secret::BigInt    G::PointEC    r::BigInt    W::PointECend struct ECDSA_Public_Key    E::CurveFP    G::PointEC    r::BigInt    W::PointECend function genkey(curve=secp256k1) # default: use Bitcoin standard EC curve secp256k1    E = CurveFP(curve.p, curve.a, curve.b)    s = generatemultiplier(curve)    G = PointEC(E, curve.Gx, curve.Gy, curve.r)    W = s * G    return ECDSA_Key(E, s, G, curve.r, W)end aspublickey(k::ECDSA_Key) = ECDSA_Public_Key(k.E, k.G, k.r, k.W)privatekey(k::ECDSA_Key) = k.secret function ECDSA_sign(m::String, key::ECDSA_Key, digestfunction=sha256)    r, f = key.r, digestfunction(codeunits(m)) # f = H(m)    # order of curve points length must be >= sha digest length (in bytes)    @assert(ndigits(r, base=16) >= length(f))    c, d, bindigest = BigInt(0), BigInt(0), foldl((x, y) -> 16 * BigInt(x) + y, f)    while c == 0 || d == 0        u = generatemultiplier(secp256k1)        V = u * key.G        c = mod(V.x, r)        d = mod((invmod(u, r) * (bindigest + key.secret * c)), r)    end    return aspublickey(key), c, dend function isverifiedECDSA(m::String, publickey, c, d, digestfunction=sha256)    if 1 <= c < publickey.r && 1 <= d < publickey.r        r, f = publickey.r, digestfunction(codeunits(m))        h, bindigest = invmod(d, r), foldl((x, y) -> 16 * BigInt(x) + y, f)        h1, h2 = mod(bindigest * h, r), mod(c * h, r)        verifierpoint = h1 * publickey.G + h2 * publickey.W        return mod(verifierpoint.x, r) == c    end    return falseend end  # module using .ToyECDSA const key = genkey()const msg = "Bill says this is an elliptic curve digital signature algorithm."const altered = "Bill says this isn't an elliptic curve digital signature algorithm." publickey, c, d = ECDSA_sign(msg, key) println("ECDSA of message <\$msg> verified: ", isverifiedECDSA(msg, publickey, c, d)) println("ECDSA of message <\$altered> verified: ", isverifiedECDSA(altered, publickey, c, d)) `
Output:
```ECDSA of message <Bill says this is an elliptic curve digital signature algorithm.> verified: true
ECDSA of message <Bill says this isn't an elliptic curve digital signature algorithm.> verified: false
```

## Nim

Translation of: C
`import math, random, strformat const  MaxN = 1073741789       # Maximum modulus.  MaxR = MaxN + 65536     # Maximum order "g".  Infinity = int64.high   # Symbolic infinity. type   Point = tuple[x, y: int64]   Curve = object    a, b: int64    n: int64    g: Point    r: int64   Pair = tuple[a, b: int64]   Parameters = tuple[a, b, n, gx, gy, r: int] const ZerO: Point = (Infinity, 0i64) type  InversionError = object of ValueError  InvalidParamError = object of ValueError  template `%`(a, n: int64): int64 =  ## To simplify the writing.  floorMod(a, n)  proc exgcd(v, u: int64): int64 =  ## Return 1/v mod u.  var u = u  var v = v  if v < 0: v += u   var r = 0i64  var s = 1i64  while v != 0:    let q = u div v    u = u mod v    swap u, v    r -= q * s    swap r, s   if u != 1:    raise newException(InversionError, "impossible inverse mod N, gcd = " & \$u)  result = r  func discr(e: Curve): int64 =  ## Return the discriminant of "e".  let c = e.a * e.a % e.n * e.a % e.n * 4  result = -16 * (e.b * e.b % e.n * 27 + c) % e.n  func isO(p: Point): bool =  ## Return true if "p" is zero.  p.x == Infinity and p.y == 0  func isOn(e: Curve; p: Point): bool =  ## Return true if "p" is on curve "e".  if p.isO: return true  let r = ((e.a + p.x * p.x) % e.n * p.x + e.b) % e.n  let s = p.y * p.y % e.n  result = r == s  proc add(e: Curve; p, q: Point): Point =  ## Full Point addition.   if p.isO: return q  if q.isO: return p   var la: int64  if p.x != q.x:    la = (p.y - q.y) * exgcd(p.x - q.x, e.n) % e.n  elif p.y == q.y and p.y != 0:    la = (p.x * p.x % e.n * 3 + e.a) % e.n * exgcd(2 * p.y, e.n) % e.n  else:    return ZerO   result.x = (la * la - p.x - q.x) % e.n  result.y = (la * (p.x - result.x) - p.y) % e.n  proc mul(e: Curve; p: Point; k: int64): Point =  ## Return "kp".  var q = p  var k = k  result = ZerO   while k != 0:    if (k and 1) != 0:      result = e.add(result, q)    q = e.add(q, q)    k = k shr 1  proc print(e: Curve; prefix: string; p: Point) =  ## Print a point with a prefix.  var y = p.y  if p.isO:    echo prefix, " (0)"  else:    if y > e.n - y: y -= e.n    echo prefix, &" ({p.x}, {y})"  proc initCurve(params: Parameters): Curve =  ## Initialize the curve.   result.n = params.n  if result.n notin 5..MaxN:    raise newException(ValueError, "invalid value for N: " & \$result.n)  result.a = params.a.int64 % result.n  result.b = params.b.int64 % result.n  result.g.x = params.gx.int64 % result.n  result.g.y = params.gy.int64 % result.n  result.r = params.r   if result.r notin 5..MaxR:    raise newException(ValueError, "invalid value for r: " & \$result.r)   echo &"\nE: y^2 = x^3 + {result.a}x + {result.b} (mod {result.n})"  result.print("base point G", result.g)  echo &"order(G, E) = {result.r}"  proc rnd(): float =  ## Return a pseudorandom number in range [0..1[.  while true:    result = rand(1.0)    if result != 1: break proc signature(e: Curve; s, f: int64): Pair =  ## Compute the signature.   var    c, d = 0i64    u: int64    v: Point   echo "Signature computation"   while true:    while true:      u = 1 + int64(rnd() * float(e.r - 1))      v = e.mul(e.g, u)      c = v.x % e.r      if c != 0: break    d = exgcd(u, e.r) * (f + s * c % e.r) % e.r    if d != 0: break   echo "one-time u = ", u  e.print("V = uG", v)   result = (c, d)  proc verify(e: Curve; w: Point; f: int64; sg: Pair): bool =  ## Verify a signature.   # Domain check.  if sg.a notin 1..<e.r or sg.b notin 1..<e.r:    return false   echo "\nsignature verification"  let h = exgcd(sg.b, e.r)  let h1 = f * h % e.r  let h2 = sg.a * h % e.r  echo &"h1, h2 = {h1}, {h2}"  var v = e.mul(e.g, h1)  let v2 = e.mul(w, h2)  e.print("h1G", v)  e.print("h2W", v2)  v = e.add(v, v2)  e.print("+ =", v)  if v.isO: return false  let c1 = v.x % e.r  echo "c’ = ", c1  result = c1 == sg.a  proc ecdsa(e: Curve; f: int64; d: int) =  ## Build digital signature for message hash "f" with error bit "d".   # Parameter check.  var w = e.mul(e.g, e.r)  if e.discr() == 0 or e.g.isO or not w.isO or not e.isOn(e.g):    raise newException(InvalidParamError, "invalid parameter set")   echo "\nkey generation"  let s = 1 + int64(rnd() * float(e.r - 1))  w = e.mul(e.g, s)  echo "private key s = ", s  e.print("public key W = sG", w)   # Find next highest power of two minus one.  var t = e.r  var i = 1  while i < 64:    t = t or t shr i    i = i shl 1  var f = f  while f > t: f = f shr 1  echo &"\naligned hash {f:x}"   let sg = e.signature(s, f)  echo &"signature c, d = {sg.a}, {sg.b}"   var d = d  if d > 0:    while d > t: d = d shr 1    f = f xor d    echo &"\ncorrupted hash {f:x}"   echo if e.verify(w, f, sg): "Valid" else: "Invalid" when isMainModule:   randomize()   # Test vectors: elliptic curve domain parameters,  # short Weierstrass model y^2 = x^3 + ax + b (mod N)   const Sets = [    #    a,   b,  modulus N, base point G, order(G, E), cofactor      (355, 671, 1073741789, 13693, 10088, 1073807281),      (  0,   7,   67096021,  6580,   779,   16769911),      ( -3,   1,     877073,     0,     1,     878159),      (  0,  14,      22651,    63,    30,        151),      (  3,   2,          5,     2,     1,          5),     # ECDSA may fail if...    # the base point is of composite order      (  0,   7,   67096021,  2402,  6067,   33539822),    # the given order is of composite order      (  0,   7,   67096021,  6580,   779,   67079644),    # 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.  let f = 0x789abcdei64  let d = 0   for s in Sets:    let e = initCurve(s)    try:      e.ecdsa(f, d)    except ValueError:      echo getCurrentExceptionMsg()    echo "——————————————"`
Output:

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 = 136992620
public key W = sG (1015940633, 345577760)

aligned hash 789abcde
Signature computation
one-time u = 183069978
V = uG (565985545, 303688609)
signature c, d = 565985545, 1060545485

signature verification
h1, h2 = 668000030, 564517193
h1G (801378704, -375265150)
h2W (77432102, 301215724)
+ = (565985545, 303688609)
c’ = 565985545
Valid
——————————————```

</pre>

## Perl

Translation of: Go
`# 20200828 added Perl programming solution use strict;use warnings; use Crypt::EC_DSA; my \$ecdsa = new Crypt::EC_DSA; my (\$pubkey, \$prikey) = \$ecdsa->keygen; print "Message: ", my \$msg = 'Rosetta Code', "\n"; print "Private Key :\n\$prikey \n";print "Public key  :\n", \$pubkey->x, "\n", \$pubkey->y, "\n"; my \$signature = \$ecdsa->sign( Message => \$msg, Key => \$prikey );print "Signature   :\n";for (sort keys %\$signature) { print "\$_ => \$signature->{\$_}\n"; } \$ecdsa->verify( Message => \$msg, Key => \$pubkey, Signature => \$signature ) and   print "Signature verified.\n"`
Output:
```Message: Rosetta Code
Private Key :
50896950174101144529764022934807089163030534967278433074982207331912857967110
Public key  :
98639220601877298644829563208621497413822596683110596662237522364057856411416
69976521993624103693270429074404825634551369215777879408776019358694823367135
Signature   :
r => 113328268998856048369024784426817827689451364968174533291969247274701793929451
s => 102496515866716695113707075780391660331998173218829535655149484671019624453603
Signature verified.```

## Phix

Translation of: FreeBASIC
```requires(64)
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 = deep_copy(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[1], b = i[2]
inverr = false
e[N] = i[3]

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[4])
e[G][Y] = modn(i[5])
e[R] = i[6]

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

--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
```
Output:

Note the above only performs tests[1], 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
_____
```

## Python

` from collections import namedtuplefrom hashlib import sha256from math import ceil, logfrom random import randintfrom typing import NamedTuple # Bitcoin ECDSA curvesecp256k1_data = dict(    p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,  # Field characteristic    a=0x0,  # Curve param a    b=0x7,  # Curve param b    r=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,  # Order n of basepoint G. Cofactor is 1 so it's ommited.    Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,  # Base point x    Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,  # Base point y)secp256k1 = namedtuple("secp256k1", secp256k1_data)(**secp256k1_data)assert (secp256k1.Gy ** 2 - secp256k1.Gx ** 3 - 7) % secp256k1.p == 0  class CurveFP(NamedTuple):    p: int  # Field characteristic    a: int  # Curve param a    b: int  # Curve param b  def extended_gcd(aa, bb):    # https://rosettacode.org/wiki/Modular_inverse#Iteration_and_error-handling    lastremainder, remainder = abs(aa), abs(bb)    x, lastx, y, lasty = 0, 1, 1, 0    while remainder:        lastremainder, (quotient, remainder) = remainder, divmod(            lastremainder, remainder        )        x, lastx = lastx - quotient * x, x        y, lasty = lasty - quotient * y, y    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)  def modinv(a, m):    # https://rosettacode.org/wiki/Modular_inverse#Iteration_and_error-handling    g, x, _ = extended_gcd(a, m)    if g != 1:        raise ValueError    return x % m  class PointEC(NamedTuple):    curve: CurveFP    x: int    y: int     @classmethod    def build(cls, curve, x, y):        x = x % curve.p        y = y % curve.p        rv = cls(curve, x, y)        if not rv.is_identity():            assert rv.in_curve()        return rv     def get_identity(self):        return PointEC.build(self.curve, 0, 0)     def copy(self):        return PointEC.build(self.curve, self.x, self.y)     def __neg__(self):        return PointEC.build(self.curve, self.x, -self.y)     def __sub__(self, Q):        return self + (-Q)     def __equals__(self, Q):        # TODO: Assert same curve or implement logic for that.        return self.x == Q.x and self.y == Q.y     def is_identity(self):        return self.x == 0 and self.y == 0     def __add__(self, Q):        # TODO: Assert same curve or implement logic for that.        p = self.curve.p        if self.is_identity():            return Q.copy()        if Q.is_identity():            return self.copy()        if Q.x == self.x and (Q.y == (-self.y % p)):            return self.get_identity()         if self != Q:            l = ((Q.y - self.y) * modinv(Q.x - self.x, p)) % p        else:            # Point doubling.            l = ((3 * self.x ** 2 + self.curve.a) * modinv(2 * self.y, p)) % p        l = int(l)         Rx = (l ** 2 - self.x - Q.x) % p        Ry = (l * (self.x - Rx) - self.y) % p        rv = PointEC.build(self.curve, Rx, Ry)        return rv     def in_curve(self):        return ((self.y ** 2) % self.curve.p) == (            (self.x ** 3 + self.curve.a * self.x + self.curve.b) % self.curve.p        )     def __mul__(self, s):        # Naive method is exponential (due to invmod right?) so we use an alternative method:        # https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder        r0 = self.get_identity()        r1 = self.copy()        # pdbsas        for i in range(ceil(log(s + 1, 2)) - 1, -1, -1):            if ((s & (1 << i)) >> i) == 0:                r1 = r0 + r1                r0 = r0 + r0            else:                r0 = r0 + r1                r1 = r1 + r1        return r0     def __rmul__(self, other):        return self.__mul__(other)  class ECCSetup(NamedTuple):    E: CurveFP    G: PointEC    r: int  secp256k1_curve = CurveFP(secp256k1.p, secp256k1.a, secp256k1.b)secp256k1_basepoint = PointEC(secp256k1_curve, secp256k1.Gx, secp256k1.Gy)  class ECDSAPrivKey(NamedTuple):    ecc_setup: ECCSetup    secret: int     def get_pubkey(self):        # Compute W = sG to get the pubkey        W = self.secret * self.ecc_setup.G        pub = ECDSAPubKey(self.ecc_setup, W)        return pub  class ECDSAPubKey(NamedTuple):    ecc_setup: ECCSetup    W: PointEC  class ECDSASignature(NamedTuple):    c: int    d: int  def generate_keypair(ecc_setup, s=None):    # Select a random integer s in the interval [1, r - 1] for the secret.    if s is None:        s = randint(1, ecc_setup.r - 1)    priv = ECDSAPrivKey(ecc_setup, s)    pub = priv.get_pubkey()    return priv, pub  def get_msg_hash(msg):    return int.from_bytes(sha256(msg).digest(), "big")  def sign(priv, msg, u=None):    G = priv.ecc_setup.G    r = priv.ecc_setup.r     # 1. Compute message representative f = H(m), using a cryptographic hash function.    #    Note that f can be greater than r but not longer (measuring bits).    msg_hash = get_msg_hash(msg)     while True:        # 2. Select a random integer u in the interval [1, r - 1].        if u is None:            u = randint(1, r - 1)         # 3. Compute V = uG = (xV, yV) and c ≡ xV mod r  (goto (2) if c = 0).        V = u * G        c = V.x % r        if c == 0:            print(f"c={c}")            continue        d = (modinv(u, r) * (msg_hash + priv.secret * c)) % r        if d == 0:            print(f"d={d}")            continue        break     signature = ECDSASignature(c, d)    return signature  def verify_signature(pub, msg, signature):    r = pub.ecc_setup.r    G = pub.ecc_setup.G    c = signature.c    d = signature.d     # Verify that c and d are integers in the interval [1, r - 1].    def num_ok(n):        return 1 < n < (r - 1)     if not num_ok(c):        raise ValueError(f"Invalid signature value: c={c}")    if not num_ok(d):        raise ValueError(f"Invalid signature value: d={d}")     # Compute f = H(m) and h ≡ d^-1 mod r.    msg_hash = get_msg_hash(msg)    h = modinv(d, r)     # Compute h1 ≡ f·h mod r and h2 ≡ c·h mod r.    h1 = (msg_hash * h) % r    h2 = (c * h) % r     # Compute h1G + h2W = (x1, y1) and c1 ≡ x1 mod r.    # Accept the signature if and only if c1 = c.    P = h1 * G + h2 * pub.W    c1 = P.x % r    rv = c1 == c    return rv  def get_ecc_setup(curve=None, basepoint=None, r=None):    if curve is None:        curve = secp256k1_curve    if basepoint is None:        basepoint = secp256k1_basepoint    if r is None:        r = secp256k1.r     # 1. Select an elliptic curve E defined over ℤp.    #    The number of points in E(ℤp) should be divisible by a large prime r.    E = CurveFP(curve.p, curve.a, curve.b)     # 2. Select a base point G ∈ E(ℤp) of order r (which means that rG = 𝒪).    G = PointEC(E, basepoint.x, basepoint.y)    assert (G * r) == G.get_identity()     ecc_setup = ECCSetup(E, G, r)    return ecc_setup  def main():    ecc_setup = get_ecc_setup()    print(f"E: y^2 = x^3 + {ecc_setup.E.a}x + {ecc_setup.E.b} (mod {ecc_setup.E.p})")    print(f"base point G({ecc_setup.G.x}, {ecc_setup.G.y})")    print(f"order(G, E) = {ecc_setup.r}")     print("Generating keys")    priv, pub = generate_keypair(ecc_setup)    print(f"private key s = {priv.secret}")    print(f"public key W = sG ({pub.W.x}, {pub.W.y})")     msg_orig = b"hello world"    signature = sign(priv, msg_orig)    print(f"signature ({msg_orig}, priv) = (c,d) = {signature.c}, {signature.d}")     validation = verify_signature(pub, msg_orig, signature)    print(f"verify_signature(pub, {msg_orig}, signature) = {validation}")     msg_bad = b"hello planet"    validation = verify_signature(pub, msg_bad, signature)    print(f"verify_signature(pub, {msg_bad}, signature) = {validation}")  if __name__ == "__main__":    main() `
Output:
```E: y^2 = x^3 + 0x + 7 (mod 115792089237316195423570985008687907853269984665640564039457584007908834671663)
base point G(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
order(G, E) = 115792089237316195423570985008687907852837564279074904382605163141518161494337
Generating keys
private key s = 82303800204859706726056108314364152573031639016623313275752312395463491677949
public key W = sG (114124711379379930034967744084997669072230999039555829167372300365264253950871, 3360309271473421344413510933284750262871091919289744186713753032606174460281)
signature (b'hello world', priv) = (c,d) = 1863861291106464538398514909960950901792292936913306559193916523058660671107, 62559673485398527884210590428202308573799357197699075411868464552455123994884
verify_signature(pub, b'hello world', signature) = True
verify_signature(pub, b'hello planet', signature) = False
```

## Raku

(formerly Perl 6)

Reference: Many routines are translated from this Ruby repository, by Stephen Blackstone. The rest are taken here and there from RC.

`use Digest::SHA256::Native; # Following data taken from the C entryour (\A,\B,\P,\O,\Gx,\Gy) = (355, 671, 1073741789, 1073807281, 13693, 10088); #`{ Following data taken from the Julia entry; 256-bit; testedour (\A,\B,\P,\O,\Gx,\Gy) = (0, 7, # https://en.bitcoin.it/wiki/Secp256k10xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8); # } role Horizon { method gist { 'EC Point at horizon' } } class Point {             # modified from the Elliptic_curve_arithmetic entry   has (\$.x, \$.y);        # handle modular arithmetic only   multi method new( \x, \y ) { self.bless(:x, :y) }   method gist { "EC Point at x=\$.x, y=\$.y" }   method isOn { modP(B + \$.x * modP(A+\$.x²)) == modP(\$.y²) }   sub modP (\$a is copy) { ( \$a %= P ) < 0 ?? (\$a += P) !! \$a }} multi infix:<⊞>(Point \p, Point \q) {   my \λ = \$; # slope   if p.x ~~ q.x and p.y ~~ q.y {      return Horizon if p.y == 0 ;      λ = (3*p.x²+ A) * mult_inv(2*p.y, :modulo(P))   } else {      λ = (p.y - q.y) * mult_inv(p.x - q.x, :modulo(P))   }   my \xr = (λ²- p.x - q.x);   my \yr = (λ*(p.x - xr) - p.y);   return Point.bless: x =>  xr % P, y => yr % P} multi infix:<⊠>(Int \n, Point \p) {   return 0                if n == 0 ;   return p                if n == 1 ;   return p ⊞ ((n-1) ⊠ p ) if n % 2 == 1 ;   return ( n div 2 ) ⊠ ( p ⊞ p )} sub mult_inv(\$n, :\$modulo) { # rosettacode.org/wiki/Modular_inverse#Raku   my (\$c, \$d, \$uc, \$vd, \$vc, \$ud, \$q) = \$n % \$modulo, \$modulo, 1, 1, 0, 0, 0;   while \$c != 0 {      (\$q, \$c, \$d) = (\$d div \$c, \$d % \$c, \$c);      (\$uc, \$vc, \$ud, \$vd) = (\$ud - \$q*\$uc, \$vd - \$q*\$vc, \$uc, \$vc);   }   return \$ud % \$modulo;} class Signature {    has (\$.n, Point \$.G); # Order and Generator point    method generate_signature(Int \private_key, Str \msg) {      my \z = :16(sha256-hex msg) % \$.n; # self ref: Blob.list.fmt("%02X",'')      loop ( my \$k = my \$s = my \$r = 0 ; \$s == 0 ; ) {         loop ( \$r = \$s = 0 ; \$r == 0 ; ) {            \$r = (( \$k = (1..^\$.n).roll ) ⊠ \$.G).x % \$.n;         }         \$s = ((z + \$r*private_key) * mult_inv \$k, :modulo(\$.n)) % \$.n;      }      return \$r, \$s, private_key ⊠ \$.G ;   }    method verify_signature(\msg, \r, \s, \public_key) {      my \z = :16(sha256-hex msg) % \$.n;      my \w = mult_inv s, :modulo(\$.n);      my (\u1,\u2) = (z*w, r*w).map: { \$_ % \$.n }      my \p = (u1 ⊠ \$.G ) ⊞ (u2 ⊠ public_key);      return (p.x % \$.n) == (r % \$.n)   }} print "The Curve E is        : ";"𝑦² = 𝑥³ + %s 𝑥 + %s (mod %s) \n".printf(A,B,P);"with Generator G at   : (%s,%s)\n".printf(Gx,Gy);my \$ec = Signature.new: n => O, G => Point.new: x => Gx, y => Gy ;say "Order(G, E) is        : ", O;say "Is G  ∈ E ?           : ", \$ec.G.isOn;say "Message               : ", my \message = "Show me the monKey";say "The private key dA is : ", my \dA = (1..^O).roll;my (\$r, \$s, \Qa) = \$ec.generate_signature(dA, message);say "The public  key Qa is : ", Qa;say "Is Qa ∈ E ?           : ", Qa.isOn;say "Is signature valid?   : ", \$ec.verify_signature(message, \$r, \$s, Qa);say "Message (Tampered)    : ", my \altered = "Show me the money";say "Is signature valid?   : ", \$ec.verify_signature(altered, \$r, \$s, Qa)`
Output:
```The Curve E is        : 𝑦² = 𝑥³ + 355 𝑥 + 671 (mod 1073741789)
with Generator G at   : (13693,10088)
Order(G, E) is        : 1073807281
Is G  ∈ E ?           : True
Message               : Show me the monKey
The private key dA is : 384652035
The public  key Qa is : EC Point at x=919494857, y=18030536
Is Qa ∈ E ?           : True
Is signature valid?   : True
Message (Tampered)    : Show me the money
Is signature valid?   : False
```

## Wren

Translation of: C
Library: Wren-dynamic
Library: Wren-big
Library: Wren-fmt
Library: Wren-math

As we don't have a signed 64 bit integer type, we use BigInt instead where needed.

`import "/dynamic" for Structimport "/big" for BigIntimport "/fmt" for Fmtimport "/math" for Booleanimport "random" for Random var rand = Random.new() // rational ec point: x and y are BigIntsvar Epnt = Struct.create("Epnt", ["x", "y"]) // elliptic curve parameters: N is a BigInt, G is an Epnt, rest are integral Numsvar Curve = Struct.create("Curve", ["a", "b", "N", "G", "r"]) // signature pair: a and b are integral Numsvar Pair = Struct.create("Pair", ["a", "b"]) // maximum modulusvar mxN = 1073741789 // max order G = mxN + 65536var mxr = 1073807325 // symbolic infinityvar inf = BigInt.new(-2147483647) // single global curvevar e = Curve.new(0, 0, BigInt.zero, Epnt.new(inf, BigInt.zero), 0) // impossible inverse mod Nvar inverr = false // return mod(v^-1, u)var exgcd = Fn.new { |v, u|    var r = 0    var s = 1    if (v < 0) v = v + u    while (v != 0) {        var q = (u / v).truncate        var t = u - q * v        u = v        v = t        t = r - q * s        r = s        s = t    }    if (u != 1) {        System.print(" impossible inverse mod N, gcd = %(u)")        inverr = true    }    return r} // returns mod(a, N), a is a BigIntvar modn = Fn.new { |a|    var b = a.copy()    b = b % e.N    if (b < 0) b = b + e.N    return b} // returns mod(a, r), a is a BigIntvar modr = Fn.new { |a|   var b = a.copy()   b = b % e.r   if (b < 0) b = b + e.r   return b} // returns the discriminant of Evar disc = Fn.new {    var a = BigInt.new(e.a)    var b = BigInt.new(e.b)    var c = modn.call(a * modn.call(a * a)) * 4    return modn.call((c + modn.call(b * b) * 27) * (-16)).toSmall} // return true if P is 'zero' point (at inf, 0)var isZero = Fn.new { |p| p.x == inf && p.y == 0 } // return true if P is on curve Evar isOn = Fn.new { |p|    var r = 0    var s = 0    if (!isZero.call(p)) {        r = modn.call(p.x * modn.call(p.x * p.x + e.a) + e.b).toSmall        s = modn.call(p.y * p.y).toSmall    }    return r == s} // full ec point additionvar padd = Fn.new { |p, q|    var la = BigInt.zero    var t  = BigInt.zero    if (isZero.call(p)) return Epnt.new(q.x, q.y)    if (isZero.call(q)) return Epnt.new(p.x, p.y)    if (p.x != q.x) { // R = P + Q        t = p.y - q.y        la = modn.call(t * exgcd.call((p.x - q.x).toSmall, e.N.toSmall))    } else { // P = Q, R = 2P        if (p.y == q.y && p.y != 0) {            t = modn.call(modn.call(p.x * p.x) * 3 + e.a)            la = modn.call(t * exgcd.call((p.y * 2).toSmall, e.N.toSmall))        } else {            return Epnt.new(inf, BigInt.zero) // P = -Q, R = O        }    }    if (inverr) return Epnt.new(inf, BigInt.zero)    t = modn.call(la * la - p.x - q.x)    return Epnt.new(t, modn.call(la * (p.x - t) - p.y))} // R = multiple kPvar pmul = Fn.new { |p, k|    var s = Epnt.new(inf, BigInt.zero)    var q = Epnt.new(p.x, p.y)    while (k != 0) {        if (k % 2 == 1) s = padd.call(s, q)        if (inverr) {            s.x = inf            s.y = BigInt.zero            break        }        q = padd.call(q, q)        k = (k/2).floor    }    return s} // print point P with prefix fvar pprint = Fn.new { |f, p|    var y = p.y    if (isZero.call(p)) {        Fmt.print("\$s (0)", f)    } else {        if (y > e.N - y) y = y - e.N        Fmt.print("\$s (\$i, \$i)", f, p.x, y)    }} // initialize elliptic curvevar ellinit = Fn.new { |i|    var a  = BigInt.new(i[0])    var b  = BigInt.new(i[1])    e.N    = BigInt.new(i[2])    inverr = false    if (e.N < 5 || e.N > mxN) return false    e.a = modn.call(a).toSmall    e.b = modn.call(b).toSmall    e.G.x = modn.call(BigInt.new(i[3]))    e.G.y = modn.call(BigInt.new(i[4]))    e.r = i[5]    if (e.r < 5 || e.r > mxr) return false    Fmt.write("\nE: y^2 = x^3 + \$ix + \$i", a, b)    Fmt.print(" (mod \$i)", e.N)    pprint.call("base point G", e.G)    Fmt.print("order(G, E) = \$d", e.r)    return true} // signature primitivevar signature = Fn.new { |s, f|    var c    var d    var u    var u1    var sg = Pair.new(0, 0)    var V    System.print("\nsignature computation")    while (true) {        while (true) {            u = 1 + (rand.float() * (e.r - 1)).truncate            V = pmul.call(e.G, u)            c = modr.call(V.x).toSmall            if (c != 0) break        }        u1 = exgcd.call(u, e.r)        d = modr.call((modr.call(s * c) + f) * u1).toSmall        if (d != 0) break    }    Fmt.print("one-time u = \$d", u)    pprint.call("V = uG", V)    sg.a = c    sg.b = d    return sg} // verification primitivevar verify = Fn.new { |W, f, sg|    var c = sg.a    var d = sg.b     // domain check    var t = (c > 0) && (c < e.r)    t = Boolean.and(t, d > 0 && d < e.r)    if (!t) return false    System.print("\nsignature verification")    var h = BigInt.new(exgcd.call(d, e.r))    var h1 = modr.call(h * f).toSmall    var h2 = modr.call(h * c).toSmall    Fmt.print ("h1, h2 = \$d, \$d", h1, h2)    var V = pmul.call(e.G, h1)    var V2 = pmul.call(W, h2)    pprint.call("h1G", V)    pprint.call("h2W", V2)    V = padd.call(V, V2)    pprint.call("+ =", V)    if (isZero.call(V)) return false    var c1 = modr.call(V.x).toSmall    Fmt.print("c' = \$d", c1)    return c1 == c} var errmsg = Fn.new {    System.print("invalid parameter set")    System.print("_____________________")} // digital signature on message hash f, error bit dvar ec_dsa = Fn.new { |f, d|    // parameter check    var t = disc.call() == 0    t = Boolean.or(t, isZero.call(e.G))    var W = pmul.call(e.G, e.r)    t = Boolean.or(t, !isZero.call(W))    t = Boolean.or(t, !isOn.call(e.G))    if (t) {        errmsg.call()        return    }    System.print("\nkey generation")    var s = 1 + (rand.float() * (e.r - 1)).truncate    W = pmul.call(e.G, s)    Fmt.print("private key s = \$d\n", s)    pprint.call("public key W = sG", W)     // next highest power of 2 - 1    t = e.r    var i = 1    while (i < 32) {        t = t | (t >> i)        i = i << 1    }    while (f > t) f = f >> 1    Fmt.print("\naligned hash \$x", f)    var sg = signature.call(BigInt.new(s), f)    if (inverr) {        errmsg.call()        return    }    Fmt.print("signature c, d = \$d, \$d", sg.a, sg.b)    if (d > 0) {        while (d > t) d = d >> 1        f = f ^ d        Fmt.print("\ncorrupted hash \$x", f)    }    t = verify.call(W, f, sg)    if (inverr) {        errmsg.call()        return    }    if (t) {        System.print("Valid\n_____")   } else {        System.print("invalid\n_______")   }} // Test vectors: elliptic curve domain parameters,// short Weierstrass model y^2 = x^3 + ax + b (mod N)var 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 datavar f = 0x789abcdevar d = 0 for (s in sets) {    if (ellinit.call(s)) {        ec_dsa.call(f, d)    } else {        break    }}`
Output:

Sample output - 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 = 121877962

public key W = sG (320982025, 402911160)

aligned hash 789abcde

signature computation
one-time u = 899439563
V = uG (105563482, 310387297)
signature c, d = 105563482, 270442619

signature verification
h1, h2 = 123954960, 653133035
h1G (623038071, 220475456)
h2W (893517020, -249809739)
+ = (105563482, 310387297)
c' = 105563482
Valid
```