Elliptic Curve Digital Signature Algorithm
- 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.
- Task.
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 <lang c> /* 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); }
// full ec point addition
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;} padd(&q, q, q); }
- 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[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 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); 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 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[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; }
} </lang>
- 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 <lang freebasic> '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
'full ec point addition
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) 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 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 read eparm(t): next
if ellinit (eparm()) then ec_dsa (f, d)
else exit do
end if
loop
system </lang>
- 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. <lang 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)
}</lang>
- 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
<lang 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 applications
struct 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) end
end
struct PointINF end const 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 false
end
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 false
end
+(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 result
end
in(z::Tuple, curve::CurveFP) = (z[2]^2 - (z[1]^3 + curve.a*z[1] + curve.b)) % curve.p == 0 in(x::Number,y::Number, curve::CurveFP) = (y^2 -(x^3 + curve.a*x + curve.b)) % curve.p == 0 in(p::PointEC, curve::CurveFP) = (p.y^2 - (p.x^3 + curve.a * p.x + curve.b)) % curve.p == 0 in(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::PointEC
end
struct ECDSA_Public_Key
E::CurveFP G::PointEC r::BigInt W::PointEC
end
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, d
end
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 false
end
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))
</lang>
- 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
Perl 6
Reference: Many routines are translated from this Ruby repository, by Stephen Blackstone. The rest are taken here and there from RC. <lang perl6>#!/usr/bin/env perl6
use Digest::SHA256::Native;
- Following data taken from the C entry
our (\A,\B,\P,\O,\Gx,\Gy) = (355, 671, 1073741789, 1073807281, 13693, 10088);
- `{ Following data taken from the Julia entry; 256-bit; tested
our (\A,\B,\P,\O,\Gx,\Gy) = (0, 7, # https://en.bitcoin.it/wiki/Secp256k1 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F, 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#Perl_6
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)</lang>
- 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
Phix
<lang Phix>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
function padd(sequence p, q) -- full ec point addition 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 s = padd(s, q) end if if inverr then s = zerO; exit end if k = floor(k/2) q = padd(q, q) 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) V = padd(V, 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</lang>
- 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 _____