Elliptic Curve Digital Signature Algorithm: Difference between revisions

m
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
m (→‎{{header|Wren}}: Minor tidy)
 
(22 intermediate revisions by 10 users not shown)
Line 1:
{{draft task|Cryptography}}
 
;Elliptic curves.
 
An [[wp:Elliptic_curve|elliptic curve]] E over ℤp (p ≥ 5) is defined by an equation of the form
'''y^2 ²= x^3³ + ax + b''', where a, b ∈ ℤp and the discriminant ≢ 0 (mod p),
together with a special point 𝒪 called the point at infinity.
The set '''E(ℤp)''' consists of all points (x, y), with x, y ∈ ℤp,
Line 113:
=={{header|C}}==
Parallel to: FreeBASIC
<syntaxhighlight lang="c">
<lang c>
/*
subject: Elliptic curve digital signature algorithm,
Line 458:
}
}
</syntaxhighlight>
</lang>
{{out}}
(tcc, srand(1); first set only)
Line 485:
Valid
_____
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <random>
#include <stdexcept>
#include <string>
#include <vector>
 
const int32_t MAX_MODULUS = 1073741789;
const int32_t MAX_ORDER_G = MAX_MODULUS + 65536;
 
std::random_device random;
std::mt19937 generator(random());
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
 
class Point {
public:
Point(const int64_t& x, const int64_t& y) : x(x), y(y) {}
 
Point() : x(0),y(0) {}
 
bool isZero() {
return x == INT64_MAX && y == 0;
}
 
int64_t x, y;
};
 
const Point ZERO_POINT(INT64_MAX, 0);
 
class Pair {
public:
Pair(const int64_t& a, const int64_t& b) : a(a), b(b) {}
 
const int64_t a, b;
};
 
class Parameter {
public:
Parameter(const int64_t& a, const int64_t& b, const int64_t& n, const Point& g, const int64_t& r)
: a(a), b(b), n(n), g(g), r(r) {}
 
const int64_t a, b, n;
const Point g;
const int64_t r;
};
 
int64_t signum(const int64_t& x) {
return ( x < 0 ) ? -1 : ( x > 0 ) ? 1 : 0;
}
 
int64_t floor_mod(const int64_t& num, const int64_t& mod) {
const int64_t signs = ( signum(num % mod) == -signum(mod) ) ? 1 : 0;
return ( num % mod ) + signs * mod;
}
 
int64_t floor_div(const int64_t& number, const int64_t& modulus) {
const int32_t signs = ( signum(number % modulus) == -signum(modulus) ) ? 1 : 0;
return ( number / modulus ) - signs;
}
 
// Return 1 / aV modulus aU
int64_t extended_GCD(int64_t v, int64_t u) {
if ( v < 0 ) {
v += u;
}
 
int64_t result = 0;
int64_t s = 1;
while ( v != 0 ) {
const int64_t quotient = floor_div(u, v);
u = floor_mod(u, v);
std::swap(u, v);
result -= quotient * s;
std::swap(result, s);
}
 
if ( u != 1 ) {
throw std::runtime_error("Cannot inverse modulo N, gcd = " + u);
}
return result;
}
 
class Elliptic_Curve {
public:
Elliptic_Curve(const Parameter& parameter) {
n = parameter.n;
if ( n < 5 || n > MAX_MODULUS ) {
throw std::invalid_argument("Invalid value for modulus: " + n);
}
 
a = floor_mod(parameter.a, n);
b = floor_mod(parameter.b, n);
g = parameter.g;
r = parameter.r;
 
if ( r < 5 || r > MAX_ORDER_G ) {
throw std::invalid_argument("Invalid value for the order of g: " + r);
}
 
std::cout << std::endl;
std::cout << "Elliptic curve: y^2 = x^3 + " << a << "x + " << b << " (mod " << n << ")" << std::endl;
print_point_with_prefix(g, "base point G");
std::cout << "order(G, E) = " << r << std::endl;
}
 
Point add(Point p, Point q) {
if ( p.isZero() ) {
return q;
}
if ( q.isZero() ) {
return p;
}
 
int64_t la;
if ( p.x != q.x ) {
la = floor_mod(( p.y - q.y ) * extended_GCD(p.x - q.x, n), n);
} else if ( p.y == q.y && p.y != 0 ) {
la = floor_mod(floor_mod(floor_mod(p.x * p.x, n) * 3 + a, n) * extended_GCD(2 * p.y, n), n);
} else {
return ZERO_POINT;
}
 
const int64_t x_coord = floor_mod(la * la - p.x - q.x, n);
const int64_t y_coord = floor_mod(la * ( p.x - x_coord ) - p.y, n);
return Point(x_coord, y_coord);
}
 
Point multiply(Point point, int64_t k) {
Point result = ZERO_POINT;
 
while ( k != 0 ) {
if ( ( k & 1 ) == 1 ) {
result = add(result, point);
}
point = add(point, point);
k >>= 1;
}
return result;
}
 
bool contains(Point point) {
if ( point.isZero() ) {
return true;
}
 
int64_t r = floor_mod(floor_mod(a + point.x * point.x, n) * point.x + b, n);
int64_t s = floor_mod(point.y * point.y, n);
return r == s;
}
 
uint64_t discriminant() {
const int64_t constant = 4 * floor_mod(a * a, n) * floor_mod(a, n);
return floor_mod(-16 * ( floor_mod(b * b, n) * 27 + constant ), n);
}
 
void print_point_with_prefix(Point point, const std::string& prefix) {
int64_t y = point.y;
if ( point.isZero() ) {
std::cout << prefix + " (0)" << std::endl;
} else {
if ( y > n - y ) {
y -= n;
}
std::cout << prefix + " (" << point.x << ", " << y << ")" << std::endl;
}
}
 
int64_t a, b, n, r;
Point g;
};
 
double random_number() {
return distribution(generator);
}
 
Pair signature(Elliptic_Curve curve, const int64_t& s, const int64_t& f) {
int64_t c, d, u;
Point v;
 
while ( true ) {
while ( true ) {
u = 1 + (int64_t) ( random_number() * (double) ( curve.r - 1 ) );
v = curve.multiply(curve.g, u);
c = floor_mod(v.x, curve.r);
if ( c != 0 ) {
break;
}
}
 
d = floor_mod(extended_GCD(u, curve.r) * floor_mod(f + s * c, curve.r), curve.r);
if ( d != 0 ) {
break;
}
}
 
std::cout << "one-time u = " << u << std::endl;
curve.print_point_with_prefix(v, "V = uG");
return Pair(c, d);
}
 
bool verify(Elliptic_Curve curve, Point point, const int64_t& f, const Pair& signature) {
if ( signature.a < 1 || signature.a >= curve.r || signature.b < 1 || signature.b >= curve.r ) {
return false;
}
 
std::cout << "\n" << "signature verification" << std::endl;
const int64_t h = extended_GCD(signature.b, curve.r);
const int64_t h1 = floor_mod(f * h, curve.r);
const int64_t h2 = floor_mod(signature.a * h, curve.r);
std::cout << "h1, h2 = " << h1 << ", " << h2 << std::endl;
Point v = curve.multiply(curve.g, h1);
Point v2 = curve.multiply(point, h2);
curve.print_point_with_prefix(v, "h1G");
curve.print_point_with_prefix(v2, "h2W");
v = curve.add(v, v2);
curve.print_point_with_prefix(v, "+ =");
 
if ( v.isZero() ) {
return false;
}
int64_t c1 = floor_mod(v.x, curve.r);
std::cout << "c' = " << c1 << std::endl;
return c1 == signature.a;
}
 
// Build the digital signature for a message using the hash aF with error bit aD
void ecdsa(Elliptic_Curve curve, int64_t f, int32_t d) {
Point point = curve.multiply(curve.g, curve.r);
 
if ( curve.discriminant() == 0 || curve.g.isZero() || ! point.isZero() || ! curve.contains(curve.g) ) {
throw std::invalid_argument("Invalid parameter in the method ecdsa");
}
 
std::cout << "\n" << "key generation" << std::endl;
const int64_t s = 1 + (int64_t) ( random_number() * (double) ( curve.r - 1 ) );
point = curve.multiply(curve.g, s);
std::cout << "private key s = " << s << std::endl;
curve.print_point_with_prefix(point, "public key W = sG");
 
// Find the next highest power of two minus one.
int64_t t = curve.r;
int64_t i = 1;
while ( i < 64 ) {
t |= t >> i;
i <<= 1;
}
while ( f > t ) {
f >>= 1;
}
std::cout << "\n" << "aligned hash " << std::hex << std::setfill('0') << std::setw(8) << f
<< std::dec << std::endl;
 
const Pair signature_pair = signature(curve, s, f);
std::cout << "signature c, d = " << signature_pair.a << ", " << signature_pair.b << std::endl;
 
if ( d > 0 ) {
while ( d > t ) {
d >>= 1;
}
f ^= d;
std::cout << "\n" << "corrupted hash " << std::hex << std::setfill('0') << std::setw(8) << f
<< std::dec << std::endl;
}
 
std::cout << ( verify(curve, point, f, signature_pair) ? "Valid" : "Invalid" ) << std::endl;
std::cout << "-----------------" << std::endl;
}
 
int main() {
// Test parameters for elliptic curve digital signature algorithm,
// using the short Weierstrass model: y^2 = x^3 + ax + b (mod N).
//
// Parameter: a, b, modulus N, base point G, order of G in the elliptic curve.
 
const std::vector<Parameter> parameters {
Parameter( 355, 671, 1073741789, Point(13693, 10088), 1073807281 ),
Parameter( 0, 7, 67096021, Point( 6580, 779), 16769911 ),
Parameter( -3, 1, 877073, Point( 0, 1), 878159 ),
Parameter( 0, 14, 22651, Point( 63, 30), 151 ),
Parameter( 3, 2, 5, Point( 2, 1), 5 ) };
 
// Parameters which cause failure of the algorithm for the given reasons
// the base point is of composite order
// Parameter( 0, 7, 67096021, Point( 2402, 6067), 33539822 ),
// the given order is of composite order
// Parameter( 0, 7, 67096021, Point( 6580, 779), 67079644 ),
// the modulus is not prime (deceptive example)
// Parameter( 0, 7, 877069, Point( 3, 97123), 877069 ),
// fails if the modulus divides the discriminant
// Parameter( 39, 387, 22651, Point( 95, 27), 22651 ) );
 
const int64_t f = 0x789abcde; // The message's digital signature hash which is to be verified
const int32_t d = 0; // Set d > 0 to simulate corrupted data
 
for ( const Parameter& parameter : parameters ) {
Elliptic_Curve elliptic_curve(parameter);
ecdsa(elliptic_curve, f, d);
}
}
</syntaxhighlight>
{{ out }}
<pre>
 
Elliptic curve: y^2 = x^3 + 355x + 671 (mod 1073741789)
base point G (13693, 10088)
order(G, E) = 1073807281
 
key generation
private key s = 1024325479
public key W = sG (717544485, -463545080)
 
aligned hash 789abcde
one-time u = 76017594
V = uG (231970881, 178344325)
signature c, d = 231970881, 762656688
 
signature verification
h1, h2 = 205763719, 179248000
h1G (757236523, -510136355)
h2W (118269957, 451962485)
+ = (231970881, 178344325)
c' = 231970881
Valid
-----------------
 
// continues ...
</pre>
 
=={{header|FreeBASIC}}==
Parallel to: C
<langsyntaxhighlight lang="freebasic">
'subject: Elliptic curve digital signature algorithm,
' toy version for small modulus N.
Line 823 ⟶ 1,154:
 
system
</syntaxhighlight>
</lang>
{{out}}
(randomize 1, first set only)
Line 854 ⟶ 1,185:
=={{header|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.
<langsyntaxhighlight lang="go">package main
 
import (
Line 895 ⟶ 1,226:
valid := ecdsa.Verify(&priv.PublicKey, hash[:], r, s)
fmt.Println("\nSignature verified:", valid)
}</langsyntaxhighlight>
 
{{out}}
Line 915 ⟶ 1,246:
 
Signature verified: true
</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
 
public final class EllipticCurveDigitalSignatureAlgorithm {
 
public static void main(String[] aArgs) {
// Test parameters for elliptic curve digital signature algorithm,
// using the short Weierstrass model: y^2 = x^3 + ax + b (mod N).
//
// Parameter: a, b, modulus N, base point G, order of G in the elliptic curve.
 
List<Parameter> parameters = List.of(
new Parameter( 355, 671, 1073741789, new Point(13693, 10088), 1073807281 ),
new Parameter( 0, 7, 67096021, new Point( 6580, 779), 16769911 ),
new Parameter( -3, 1, 877073, new Point( 0, 1), 878159 ),
new Parameter( 0, 14, 22651, new Point( 63, 30), 151 ),
new Parameter( 3, 2, 5, new Point( 2, 1), 5 ) );
 
// Parameters which cause failure of the algorithm for the given reasons
// the base point is of composite order
// new Parameter( 0, 7, 67096021, new Point( 2402, 6067), 33539822 ),
// the given order is of composite order
// new Parameter( 0, 7, 67096021, new Point( 6580, 779), 67079644 ),
// the modulus is not prime (deceptive example)
// new Parameter( 0, 7, 877069, new Point( 3, 97123), 877069 ),
// fails if the modulus divides the discriminant
// new Parameter( 39, 387, 22651, new Point( 95, 27), 22651 ) );
final long f = 0x789abcde; // The message's digital signature hash which is to be verified
final int d = 0; // Set d > 0 to simulate corrupted data
 
for ( Parameter parameter : parameters ) {
EllipticCurve ellipticCurve = new EllipticCurve(parameter);
ecdsa(ellipticCurve, f, d);
}
}
// Build the digital signature for a message using the hash aF with error bit aD
private static void ecdsa(EllipticCurve aCurve, long aF, int aD) {
Point point = aCurve.multiply(aCurve.g, aCurve.r);
if ( aCurve.discriminant() == 0 || aCurve.g.isZero() || ! point.isZero() || ! aCurve.contains(aCurve.g) ) {
throw new AssertionError("Invalid parameter in method ecdsa");
}
 
System.out.println(System.lineSeparator() + "key generation");
final long s = 1 + (long) ( random() * (double) ( aCurve.r - 1 ) );
point = aCurve.multiply(aCurve.g, s);
System.out.println("private key s = " + s);
aCurve.printPointWithPrefix(point, "public key W = sG");
 
// Find the next highest power of two minus one.
long t = aCurve.r;
long i = 1;
while ( i < 64 ) {
t |= t >> i;
i <<= 1;
}
long f = aF;
while ( f > t ) {
f >>= 1;
}
System.out.println(System.lineSeparator() + "aligned hash " + String.format("%08x", f));
 
Pair signature = signature(aCurve, s, f);
System.out.println("signature c, d = " + signature.a + ", " + signature.b);
 
long d = aD;
if ( d > 0 ) {
while ( d > t ) {
d >>= 1;
}
f ^= d;
System.out.println(System.lineSeparator() + "corrupted hash " + String.format("%08x", f));
}
 
System.out.println(verify(aCurve, point, f, signature) ? "Valid" : "Invalid");
System.out.println("-----------------");
}
private static boolean verify(EllipticCurve aCurve, Point aPoint, long aF, Pair aSignature) {
if ( aSignature.a < 1 || aSignature.a >= aCurve.r || aSignature.b < 1 || aSignature.b >= aCurve.r ) {
return false;
}
 
System.out.println(System.lineSeparator() + "signature verification");
final long h = extendedGCD(aSignature.b, aCurve.r);
final long h1 = Math.floorMod(aF * h, aCurve.r);
final long h2 = Math.floorMod(aSignature.a * h, aCurve.r);
System.out.println("h1, h2 = " + h1 + ", " + h2);
Point v = aCurve.multiply(aCurve.g, h1);
Point v2 = aCurve.multiply(aPoint, h2);
aCurve.printPointWithPrefix(v, "h1G");
aCurve.printPointWithPrefix(v2, "h2W");
v = aCurve.add(v, v2);
aCurve.printPointWithPrefix(v, "+ =");
if ( v.isZero() ) {
return false;
}
long c1 = Math.floorMod(v.x, aCurve.r);
System.out.println("c' = " + c1);
return c1 == aSignature.a;
}
private static Pair signature(EllipticCurve aCurve, long aS, long aF) {
long c = 0;
long d = 0;
long u;
Point v;
System.out.println("Signature computation");
 
while ( true ) {
while ( true ) {
u = 1 + (long) ( random() * (double) ( aCurve.r - 1 ) );
v = aCurve.multiply(aCurve.g, u);
c = Math.floorMod(v.x, aCurve.r);
if ( c != 0 ) {
break;
}
}
d = Math.floorMod(extendedGCD(u, aCurve.r) * Math.floorMod(aF + aS * c, aCurve.r), aCurve.r);
if ( d != 0 ) {
break;
}
}
 
System.out.println("one-time u = " + u);
aCurve.printPointWithPrefix(v, "V = uG");
return new Pair(c, d);
}
// Return 1 / aV modulus aU
private static long extendedGCD(long aV, long aU) {
if ( aV < 0 ) {
aV += aU;
}
 
long result = 0;
long s = 1;
while ( aV != 0 ) {
final long quotient = Math.floorDiv(aU, aV);
aU = Math.floorMod(aU, aV);
long temp = aU; aU = aV; aV = temp;
result -= quotient * s;
temp = result; result = s; s = temp;
}
 
if ( aU != 1 ) {
throw new AssertionError("Cannot inverse modulo N, gcd = " + aU);
}
return result;
}
private static double random() {
return RANDOM.nextDouble();
}
 
private static class EllipticCurve {
public EllipticCurve(Parameter aParameter) {
n = aParameter.n;
if ( n < 5 || n > MAX_MODULUS ) {
throw new AssertionError("Invalid value for modulus: " + n);
}
a = Math.floorMod(aParameter.a, n);
b = Math.floorMod(aParameter.b, n);
g = aParameter.g;
r = aParameter.r;
 
if ( r < 5 || r > MAX_ORDER_G ) {
throw new AssertionError("Invalid value for the order of g: " + r);
}
 
System.out.println();
System.out.println("Elliptic curve: y^2 = x^3 + " + a + "x + " + b + " (mod " + n + ")");
printPointWithPrefix(g, "base point G");
System.out.println("order(G, E) = " + r);
}
private Point add(Point aP, Point aQ) {
if ( aP.isZero() ) {
return aQ;
}
if ( aQ.isZero() ) {
return aP;
}
 
long la;
if ( aP.x != aQ.x ) {
la = Math.floorMod(( aP.y - aQ.y ) * extendedGCD(aP.x - aQ.x, n), n);
} else if ( aP.y == aQ.y && aP.y != 0 ) {
la = Math.floorMod(Math.floorMod(Math.floorMod(
aP.x * aP.x, n) * 3 + a, n) * extendedGCD(2 * aP.y, n), n);
} else {
return Point.ZERO;
}
 
final long xCoordinate = Math.floorMod(la * la - aP.x - aQ.x, n);
final long yCoordinate = Math.floorMod(la * ( aP.x - xCoordinate ) - aP.y, n);
return new Point(xCoordinate, yCoordinate);
}
public Point multiply(Point aPoint, long aK) {
Point result = Point.ZERO;
 
while ( aK != 0 ) {
if ( ( aK & 1 ) == 1 ) {
result = add(result, aPoint);
}
aPoint = add(aPoint, aPoint);
aK >>= 1;
}
return result;
}
public boolean contains(Point aPoint) {
if ( aPoint.isZero() ) {
return true;
}
final long r = Math.floorMod(Math.floorMod(a + aPoint.x * aPoint.x, n) * aPoint.x + b, n);
final long s = Math.floorMod(aPoint.y * aPoint.y, n);
return r == s;
}
public long discriminant() {
final long constant = 4 * Math.floorMod(a * a, n) * Math.floorMod(a, n);
return Math.floorMod(-16 * ( Math.floorMod(b * b, n) * 27 + constant ), n);
}
public void printPointWithPrefix(Point aPoint, String aPrefix) {
long y = aPoint.y;
if ( aPoint.isZero() ) {
System.out.println(aPrefix + " (0)");
} else {
if ( y > n - y ) {
y -= n;
}
System.out.println(aPrefix + " (" + aPoint.x + ", " + y + ")");
}
}
private final long a, b, n, r;
private final Point g;
}
private static class Point {
public Point(long aX, long aY) {
x = aX;
y = aY;
}
public boolean isZero() {
return x == INFINITY && y == 0;
}
private long x, y;
private static final long INFINITY = Long.MAX_VALUE;
private static final Point ZERO = new Point(INFINITY, 0);
}
 
private static record Pair(long a, long b) {}
 
private static record Parameter(long a, long b, long n, Point g, long r) {}
private static final int MAX_MODULUS = 1073741789;
private static final int MAX_ORDER_G = MAX_MODULUS + 65536;
private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
 
}
</syntaxhighlight>
{{ out }}
<pre>
 
Elliptic curve: y^2 = x^3 + 355x + 671 (mod 1073741789)
base point G (13693, 10088)
order(G, E) = 1073807281
 
key generation
private key s = 631324603
public key W = sG (789657939, 162653307)
 
aligned hash 789abcde
Signature computation
one-time u = 978377271
V = uG (40748926, -184905705)
signature c, d = 40748926, 938914492
 
signature verification
h1, h2 = 903203729, 29256237
h1G (286322818, -482840260)
h2W (31139810, 45550525)
+ = (40748926, -184905705)
c' = 40748926
Valid
-----------------
 
// continues ...
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">module ToyECDSA
 
using SHA
Line 1,104 ⟶ 1,745:
 
println("ECDSA of message <$altered> verified: ", isverifiedECDSA(altered, publickey, c, d))
</langsyntaxhighlight>{{out}}
<pre>
ECDSA of message <Bill says this is an elliptic curve digital signature algorithm.> verified: true
Line 1,110 ⟶ 1,751:
</pre>
 
=={{header|PhixNim}}==
{{trans|FreeBASICC}}
<syntaxhighlight lang="nim">import math, random, strformat
<lang Phix>enum X, Y -- rational ec point
enum A, B, N, G, R -- elliptic curve parameters
-- also signature pair(A,B)
 
const
constant mxN = 1073741789 -- maximum modulus
MaxN = 1073741789 # Maximum modulus.
constant mxr = 1073807325 -- max order G = mxN + 65536
MaxR = MaxN + 65536 # Maximum order "g".
constant inf = -2147483647 -- symbolic infinity
Infinity = int64.high # Symbolic infinity.
 
type
sequence e = {0,0,0,{0,0},0} -- single global curve
constant zerO = {inf,0} -- point at infinity zerO
 
Point = tuple[x, y: int64]
bool inverr -- impossible inverse mod N
 
Curve = object
function exgcd(atom v, u)
a, b: int64
-- return mod(v^-1, u)
atom q, t, r =n: 0, s = 1int64
g: Point
if v<0 then v += u end if
r: int64
 
Pair = whiletuple[a, vb: doint64]
q = floor(u/v)
t = u-q*v
u = v
v = t
t = r-q*s
r = s
s = t
end while
 
Parameters = tuple[a, b, n, gx, gy, r: int]
if u!=1 then
printf(1," impossible inverse mod N, gcd = %d\n",{u})
inverr = true
end if
 
const ZerO: Point = (Infinity, 0i64)
return r
end function
 
type
function modn(atom a)
InversionError = object of ValueError
-- return mod(a, N)
InvalidParamError = object of ValueError
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
 
template `%`(a, n: int64): int64 =
function disc()
## To simplify the writing.
-- return the discriminant of E
floorMod(a, n)
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
 
proc exgcd(v, u: int64): int64 =
function ison(sequence p)
## Return 1/v mod u.
-- return true if P is on curve E
var atom r = 0, su = 0u
var v = v
if not isO(p) then
if v < 0: v += u
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
 
var r = 0i64
procedure pprint(string f, sequence p)
var s = 1i64
-- print point P with prefix f
while v if!= isO(p) then0:
let q = u printf(1,"%sdiv (0)\n",{f})v
elseu = u mod v
swap u, atom y = p[Y]v
if y>e[N]-y then yr -= e[N]q end* ifs
swap r, s
printf(1,"%s (%d,%d)\n",{f,p[X],y})
end if
end procedure
 
if u != 1:
function padd(sequence p, q)
raise newException(InversionError, "impossible inverse mod N, gcd = " & $u)
-- full ec point addition
result = r
atom la, t
 
if isO(p) then return q end if
if isO(q) then return p end if
 
func discr(e: Curve): int64 =
if p[X]!=q[X] then -- R := P + Q
## Return the discriminant of "e".
t = p[Y]-q[Y]
let c = e.a * e.a la% =e.n modn(t*exgcd(p[X]-q[X], e[N])).a % e.n * 4
result = -16 * (e.b * e.b % e.n * 27 + c) % 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
 
func isO(p: Point): bool =
t = modn(la*la-p[X]-q[X])
## Return true if "p" is zero.
sequence r = zerO
p.x == Infinity and p.y == 0
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
 
func isOn(e: Curve; p: Point): bool =
while k do
## Return true if "p" is ifon and_bits(k,1)curve then"e".
if p.isO: return true
s = padd(s, q)
let r = ((e.a + p.x * p.x) % e.n * p.x + e.b) % e.n
end if
if inverr thenlet s = zerO;p.y * exitp.y end% ife.n
result = r k == floor(k/2)s
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]
 
proc add(e: Curve; p, q: Point): Point =
if (e[N]<5) or (e[N]>mxN) then return 0 end if
## Full Point addition.
 
if p.isO: return q
e[A] = modn(a)
if q.isO: return p
e[B] = modn(b)
e[G][X] = modn(i[4])
e[G][Y] = modn(i[5])
e[R] = i[6]
 
var la: int64
if (e[R]<5) or (e[R]>mxr) then return 0 end if
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
printf(1,"E: y^2 = x^3 + %dx + %d (mod %d)\n",{a,b,e[N]})
result.y = (la * (p.x - result.x) - p.y) % e.n
pprint("base point G", e[G])
printf(1,"order(G, E) = %d\n",{e[R]})
 
return -1
end function
 
proc mul(e: Curve; p: Point; k: int64): Point =
function signature(atom s, f)
## Return "kp".
-- signature primitive
atom c, d,var u,q u1= p
var k = k
sequence V
result = ZerO
 
while k != 0:
printf(1,"signature computation\n")
whileif true(k doand 1) != 0:
result = whilee.add(result, true doq)
-- uq = rande.add(e[R]-1q, q)
k = k shr 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
 
proc print(e: Curve; prefix: string; p: Point) =
function verify(sequence W, atom f, sequence sg)
## Print a point with a prefix.
-- verification primitive
atom c = sg[A],var dy = sg[B],p.y
if p.isO:
t, c1, h1, h2, h
echo prefix, " (0)"
sequence V, V2
else:
if y > e.n - y: y -= e.n
echo prefix, &" ({p.x}, {y})"
 
--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
 
proc initCurve(params: Parameters): Curve =
printf(1,"\nsignature verification\n")
## Initialize the curve.
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)
 
result.n = params.n
return (c1=c)
if result.n notin 5..MaxN:
end function
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:
procedure errmsg()
printfraise newException(1ValueError, "invalid parametervalue for r: set\n" & $result.r)
printf(1,"_____________________\n")
end procedure
 
echo &"\nE: y^2 = x^3 + {result.a}x + {result.b} (mod {result.n})"
procedure ec_dsa(atom f, d)
result.print("base point G", result.g)
-- digital signature on message hash f, error bit d
echo &"order(G, E) = {result.r}"
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
 
proc rnd(): float =
puts(1,"\nkey generation\n")
## Return a pseudorandom number in range [0..1[.
-- s = rand(e[R] - 1)
while true:
s = 509100772 -- match FreeBASIC output
result = rand(1.0)
-- s = 1343570 -- match C output
Wif result != pmul(e[G],1: s)break
printf(1,"private key s = %d\n",{s})
pprint("public key W = sG", W)
 
proc signature(e: Curve; s, f: int64): Pair =
--next highest power of 2 - 1
## Compute the signature.
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})
 
var
sg = signature(s, f)
c, d = 0i64
if inverr then errmsg() return end if
u: int64
printf(1,"signature c,d = %d,%d\n",sg)
v: Point
 
echo "Signature computation"
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
 
while true:
t = verify(W, f, sg)
while true:
if inverr then errmsg() return end if
u = 1 + int64(rnd() * float(e.r - 1))
if t then
v = printfe.mul(1e.g,"Valid\n_____\n" u)
else c = v.x % e.r
if c != 0: break
printf(1,"invalid\n_______\n")
d = exgcd(u, e.r) * (f + s * c % e.r) % e.r
end if
if d != 0: break
end procedure
 
echo "one-time u = ", u
--Test vectors: elliptic curve domain parameters,
e.print("V = uG", v)
--short Weierstrass model y^2 = x^3 + ax + b (mod N)
 
result = (c, d)
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}}
 
proc verify(e: Curve; w: Point; f: int64; sg: Pair): bool =
--Digital signature on message hash f,
## Verify a signature.
--set d > 0 to simulate corrupted data
atom f = #789ABCDE,
d = 0
 
# Domain check.
if machine_bits()!=64 then crash("needs 64 bit") end if
if sg.a notin 1..<e.r or sg.b notin 1..<e.r:
--for i=1 to length(tests) do
return false
for i=1 to 1 do
 
if not ellinit(tests[i]) then exit end if
echo "\nsignature verification"
ec_dsa(f, d)
let h = exgcd(sg.b, e.r)
end for</lang>
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 "——————————————"</syntaxhighlight>
 
{{out}}
First set only.
<pre>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>
</pre>
 
=={{header|Perl}}==
{{trans|Go}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use Crypt::EC_DSA;
 
my $ecdsa = Crypt::EC_DSA->new;
 
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"</syntaxhighlight>
{{out}}
<pre>Message: Rosetta Code
Private Key :
50896950174101144529764022934807089163030534967278433074982207331912857967110
Public key :
98639220601877298644829563208621497413822596683110596662237522364057856411416
69976521993624103693270429074404825634551369215777879408776019358694823367135
Signature :
r => 113328268998856048369024784426817827689451364968174533291969247274701793929451
s => 102496515866716695113707075780391660331998173218829535655149484671019624453603
Signature verified.</pre>
 
=={{header|Phix}}==
{{trans|FreeBASIC}}
<!--<syntaxhighlight lang="phix">(notonline)-->
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #000000;">64</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Y</span> <span style="color: #000080;font-style:italic;">-- rational ec point</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">A</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">B</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">N</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">G</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">R</span> <span style="color: #000080;font-style:italic;">-- elliptic curve parameters
-- also signature pair(A,B)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">mxN</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1073741789</span> <span style="color: #000080;font-style:italic;">-- maximum modulus</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">mxr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1073807325</span> <span style="color: #000080;font-style:italic;">-- max order G = mxN + 65536</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">inf</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2147483647</span> <span style="color: #000080;font-style:italic;">-- symbolic infinity</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- single global curve</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">zerO</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">inf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- point at infinity zerO</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">inverr</span> <span style="color: #000080;font-style:italic;">-- impossible inverse mod N</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">exgcd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return mod(v^-1, u)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">v</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">v</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">u</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">v</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">/</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">-</span><span style="color: #000000;">q</span><span style="color: #0000FF;">*</span><span style="color: #000000;">v</span>
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
<span style="color: #000000;">v</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">-</span><span style="color: #000000;">q</span><span style="color: #0000FF;">*</span><span style="color: #000000;">s</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" impossible inverse mod N, gcd = %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">u</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">inverr</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return mod(a, N)</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">modr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return mod(a, r)</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">a</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">disc</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- return the discriminant of E</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">A</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">B</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">*</span><span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">*</span><span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">*</span><span style="color: #000000;">a</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">16</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">+</span><span style="color: #000000;">27</span><span style="color: #0000FF;">*</span><span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">*</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return true if P = zerO</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">inf</span> <span style="color: #008080;">and</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ison</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return true if P is on curve E</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">B</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">A</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]))</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">pprint</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- print point P with prefix f</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s (0)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">f</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">></span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">y</span> <span style="color: #008080;">then</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s (%d,%d)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">],</span><span style="color: #000000;">y</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- full ec point addition</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">la</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">q</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">p</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- R := P + Q</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">la</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #000000;">exgcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">else</span> <span style="color: #000080;font-style:italic;">-- P = Q, R := 2P</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">*</span><span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">A</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">la</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #000000;">exgcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">zerO</span> <span style="color: #000080;font-style:italic;">-- P = -Q, R := O</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">la</span><span style="color: #0000FF;">*</span><span style="color: #000000;">la</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">])</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zerO</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">la</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">inverr</span> <span style="color: #008080;">then</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zerO</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pmul</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- R:= multiple kP</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zerO</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">inverr</span> <span style="color: #008080;">then</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">zerO</span><span style="color: #0000FF;">;</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ellinit</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- initialize elliptic curve</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">inverr</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]></span><span style="color: #000000;">mxN</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">A</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">B</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">[</span><span style="color: #000000;">4</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">][</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">[</span><span style="color: #000000;">5</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">[</span><span style="color: #000000;">6</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]></span><span style="color: #000000;">mxr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"E: y^2 = x^3 + %dx + %d (mod %d)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">N</span><span style="color: #0000FF;">]})</span>
<span style="color: #000000;">pprint</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"base point G"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"order(G, E) = %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">signature</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- signature primitive</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">u1</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">V</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"signature computation\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- u = rand(e[R]-1)</span>
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">571533488</span> <span style="color: #000080;font-style:italic;">-- match FreeBASIC output
-- u = 605163545 -- match C output</span>
<span style="color: #000000;">V</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">V</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">u1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">exgcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u1</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">+</span><span style="color: #000000;">modr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">*</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"one-time u = %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">pprint</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"V = uG"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">V</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">verify</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">W</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">sg</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- verification primitive</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">A</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sg</span><span style="color: #0000FF;">[</span><span style="color: #000000;">B</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">V</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">V2</span>
<span style="color: #000080;font-style:italic;">--domain check</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;"><</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">t</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nsignature verification\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">exgcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">h1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">*</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">h2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">*</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"h1,h2 = %d,%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">h1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">V</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">h1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">V2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">pprint</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"h1G"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">V</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">pprint</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"h2W"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">V2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">V</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">padd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">V</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">V2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">pprint</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"+ ="</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">V</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #000000;">V</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">c1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">modr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">V</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">])</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"c' = %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">c1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">errmsg</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"invalid parameter set\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"_____________________\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">ec_dsa</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- digital signature on message hash f, error bit d</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sg</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">W</span>
<span style="color: #000080;font-style:italic;">--parameter check</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">disc</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span> <span style="color: #008080;">or</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">W</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #000000;">isO</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span> <span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #000000;">ison</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span> <span style="color: #008080;">then</span> <span style="color: #000000;">errmsg</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nkey generation\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- s = rand(e[R] - 1)</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">509100772</span> <span style="color: #000080;font-style:italic;">-- match FreeBASIC output
-- s = 1343570 -- match C output</span>
<span style="color: #000000;">W</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pmul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">G</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"private key s = %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">pprint</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"public key W = sG"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">W</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--next highest power of 2 - 1</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">[</span><span style="color: #000000;">R</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">32</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">or_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">/</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)))</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">></span><span style="color: #000000;">t</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\naligned hash %x\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">f</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">sg</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">signature</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">inverr</span> <span style="color: #008080;">then</span> <span style="color: #000000;">errmsg</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"signature c,d = %d,%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sg</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">t</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">xor_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"corrupted hash %x\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">f</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">verify</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sg</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">inverr</span> <span style="color: #008080;">then</span> <span style="color: #000000;">errmsg</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Valid\n_____\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"invalid\n_______\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000080;font-style:italic;">--Test vectors: elliptic curve domain parameters,
--short Weierstrass model y^2 = x^3 + ax + b (mod N)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>
<span style="color: #000080;font-style:italic;">-- a, b, modulus N, base point G, order(G, E), cofactor</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">355</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">671</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1073741789</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">13693</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10088</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1073807281</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67096021</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6580</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">779</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">16769911</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- 4</span>
<span style="color: #0000FF;">{</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">877073</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">878159</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22651</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">63</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">30</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">151</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- 151</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">},</span>
<span style="color: #000080;font-style:italic;">--ecdsa may fail if...
--the base point is of composite order</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67096021</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2402</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6067</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">33539822</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- 2
--the given order is a multiple of the true order</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67096021</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6580</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">779</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">67079644</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- 1
--the modulus is not prime (deceptive example)</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">877069</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">97123</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">877069</span><span style="color: #0000FF;">},</span>
<span style="color: #000080;font-style:italic;">--fails if the modulus divides the discriminant</span>
<span style="color: #0000FF;">{</span> <span style="color: #000000;">39</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">387</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22651</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">95</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">27</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22651</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">--Digital signature on message hash f,
--set d &gt; 0 to simulate corrupted data</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">#789ABCDE</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000080;font-style:italic;">--for i=1 to length(tests) do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">ellinit</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ec_dsa</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
Note the above only performs tests[1], and assigns literal values in place of rand(), in order to exactly match the FreeBASIC/C output.
Line 1,432 ⟶ 2,398:
Valid
_____
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">
from collections import namedtuple
from hashlib import sha256
from math import ceil, log
from random import randint
from typing import NamedTuple
 
# Bitcoin ECDSA curve
secp256k1_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()
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>module EC {
Reference: Many routines are translated from this [https://github.com/sblackstone/toy-ecdsa Ruby repository], by Stephen Blackstone. The rest are taken here and there from RC.
use FiniteField;
<lang perl6>#!/usr/bin/env perl6
 
our class Point {
use Digest::SHA256::Native;
has ($.x, $.y);
submethod TWEAK { fail unless $!y**2 == $!x**3 + $*a*$!x + $*b }
multi method gist(::?CLASS:U:) { "Point at Horizon" }
multi method new($x, $y) { samewith :$x, :$y }
}
multi infix:<==>(Point:D $A, Point:D $B) is export { $A.x == $B.x and $A.y == $B.y }
 
multi prefix:<->(Point $P) returns Point is export { Point.new: $P.x, -$P.y }
# Following data taken from the C entry
multi infix:<+>(Point $A, Point:U) is export { $A }
our (\A,\B,\P,\O,\Gx,\Gy) = (355, 671, 1073741789, 1073807281, 13693, 10088);
multi infix:<+>(Point:U, Point $B) is export { $B }
multi infix:<+>(Point:D $A, Point:D $B) returns Point is export {
my $λ;
if $A.x == $B.x and $A.y == -$B.y { return Point }
elsif $A == $B {
return Point if $A.y == 0;
$λ = (3*$A.x² + $*a) / (2*$A.y);
}
else { $λ = ($A.y - $B.y) / ($A.x - $B.x); }
 
given $λ**2 - $A.x - $B.x {
#`{ Following data taken from the Julia entry; 256-bit; tested
return Point.new: $_, $λ*($A.x - $_) - $A.y;
our (\A,\B,\P,\O,\Gx,\Gy) = (0, 7, # https://en.bitcoin.it/wiki/Secp256k1
}
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,
}
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
multi infix:<*>(0, Point ) is export { Point }
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
multi infix:<*>(1, Point $p) is export { $p }
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8); # }
multi infix:<*>(2, Point:D $p) is export { $p + $p }
multi infix:<*>(Int $n, Point $p) is export { 2*(($n div 2)*$p) + ($n mod 2)*$p }
}
 
import EC;
role Horizon { method gist { 'EC Point at horizon' } }
 
module ECDSA {
class Point { # modified from the Elliptic_curve_arithmetic entry
use Digest::SHA256::Native;
has ($.x, $.y); # handle modular arithmetic only
our class Signature {
multi method new( \x, \y ) { self.bless(:x, :y) }
method gisthas {UInt "EC Point at x=($.xc, y=$.y" }d);
multi method new(Str $message, UInt :$private-key) {
method isOn { modP(B + $.x * modP(A+$.x²)) == modP($.y²) }
sub modP ($a is copy) { (my $az %= P:16(sha256-hex ) < 0 ?? ($a += Pmessage) !!% $a }*n;
loop (my $k = my $s = my $r = 0; $r == 0; ) {
loop ( $r = $s = 0 ; $r == 0 ; ) {
$r = (( $k = (1..^$*n).roll ) * $*G).x % $*n;
}
{
use FiniteField; my $*modulus = $*n;
$s = ($z + $r*$private-key) / $k;
}
}
samewith c => $r, d => $s;
}
multi method verify(Str $message, EC::Point :$public-key) {
my $z = :16(sha256-hex $message) % $*n;
my ($u1, $u2);
{
use FiniteField;
my $*modulus = $*n;
my $w = 1/$!d;
($u1, $u2) = $z*$w, $!c*$w;
}
my $p = ($u1 * $*G) + ($u2 * $public-key);
die unless ($p.x mod $*n) == ($!c mod $*n);
}
}
}
 
my ($*a, $*b) = 355, 671;
multi infix:<⊞>(Point \p, Point \q) {
my $*modulus = my $*p = $1073741789; # slope
 
if p.x ~~ q.x and p.y ~~ q.y {
my $*G = EC::Point.new: 13693, 10088;
return Horizon if p.y == 0 ;
my $*n = 1073807281;
λ = (3*p.x²+ A) * mult_inv(2*p.y, :modulo(P))
 
} else {
die "G is not of order n" if $*n*$*G;
λ = (p.y - q.y) * mult_inv(p.x - q.x, :modulo(P))
 
}
my \xr$private-key = (λ²- p.x -^$*n q.x)pick;
my $public-key = $private-key*$*G;
my \yr = (λ*(p.x - xr) - p.y);
 
return Point.bless: x => xr % P, y => yr % P
my $message = "Show me the monKey";
my $signature = ECDSA::Signature.new: $message, :$private-key;
 
printf "The curve E is : 𝑦² = 𝑥³ + %s 𝑥 + %s (mod %s)\n", $*a, $*b, $*p;
printf "with generator G at : (%s, %s)\n", $*G.x, $*G.y;
printf "G's order is : %d\n", $*n;
printf "The private key is : %d\n", $private-key;
printf "The public key is at : (%s, %s)\n", $public-key.x, $public-key.y;
printf "The message is : %s\n", $message;
printf "The signature is : (%s, %s)\n", $signature.c, $signature.d;
 
{
use Test;
 
lives-ok {
$signature.verify: $message, :$public-key;
}, "good signature for <$message>";
 
my $altered = $message.subst(/monKey/, "money");
dies-ok {
$signature.verify: $altered, :$public-key
}, "wrong signature for <$altered>";
}</syntaxhighlight>
{{out}}
<pre>The curve E is : 𝑦² = 𝑥³ + 355 𝑥 + 671 (mod 1073741789)
with generator G at : (13693, 10088)
G's order is : 1073807281
The private key is : 405586338
The public key is at : (457744420, 236326628)
The message is : Show me the monKey
The signature is : (839907635, 23728690)
ok 1 - good signature for <Show me the monKey>
ok 2 - wrong signature for <Show me the money></pre>
 
=={{header|Wren}}==
{{trans|C}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-big}}
{{libheader|Wren-fmt}}
{{libheader|Wren-math}}
As we don't have a signed 64 bit integer type, we use BigInt instead where needed.
<syntaxhighlight lang="wren">import "./dynamic" for Struct
import "./big" for BigInt
import "./fmt" for Fmt
import "./math" for Boolean
import "random" for Random
 
var rand = Random.new()
 
// rational ec point: x and y are BigInts
var Epnt = Struct.create("Epnt", ["x", "y"])
 
// elliptic curve parameters: N is a BigInt, G is an Epnt, rest are integral Nums
var Curve = Struct.create("Curve", ["a", "b", "N", "G", "r"])
 
// signature pair: a and b are integral Nums
var Pair = Struct.create("Pair", ["a", "b"])
 
// maximum modulus
var mxN = 1073741789
 
// max order G = mxN + 65536
var mxr = 1073807325
 
// symbolic infinity
var inf = BigInt.new(-2147483647)
 
// single global curve
var e = Curve.new(0, 0, BigInt.zero, Epnt.new(inf, BigInt.zero), 0)
 
// impossible inverse mod N
var 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 BigInt
multi infix:<⊠>(Int \n, Point \p) {
var modn = Fn.new { |a|
return 0 if n == 0 ;
var b = a.copy()
return p if n == 1 ;
b = b % e.N
return p ⊞ ((n-1) ⊠ p ) if n % 2 == 1 ;
return if (b n div 2< 0) b (= pb + p )e.N
return b
}
 
// returns mod(a, r), a is a BigInt
sub mult_inv($n, :$modulo) { # rosettacode.org/wiki/Modular_inverse#Perl_6
var modr = Fn.new { |a|
my ($c, $d, $uc, $vd, $vc, $ud, $q) = $n % $modulo, $modulo, 1, 1, 0, 0, 0;
whilevar $cb != 0 {a.copy()
b = b % e.r
($q, $c, $d) = ($d div $c, $d % $c, $c);
if (b < 0) b = b + e.r
($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc);
}return b
return $ud % $modulo;
}
 
// returns the discriminant of E
class Signature {
var 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)
has ($.n, Point $.G); # Order and Generator point
var isZero = Fn.new { |p| p.x == inf && p.y == 0 }
 
// return true if P is on curve E
method generate_signature(Int \private_key, Str \msg) {
var isOn = Fn.new { |p|
my \z = :16(sha256-hex msg) % $.n; # self ref: Blob.list.fmt("%02X",'')
var r = 0
loop ( my $k = my $s = my $r = 0 ; $s == 0 ; ) {
var loop ( $r = $s = 0 ; $r == 0 ; ) {
if (!isZero.call(p)) {
$r = (( $k = (1..^$.n).roll ) ⊠ $.G).x % $.n;
r = modn.call(p.x * modn.call(p.x * p.x + e.a) + e.b).toSmall
}
$s = modn.call((zp.y + $r*private_key) * mult_inv $k, :modulo($p.ny)) % $.n;toSmall
}
return $r, $== s, private_key ⊠ $.G ;
}
 
// full ec point addition
method verify_signature(\msg, \r, \s, \public_key) {
var padd = Fn.new { |p, q|
my \z = :16(sha256-hex msg) % $.n;
var my \wla = mult_inv s, :modulo($BigInt.n);zero
var t = BigInt.zero
my (\u1,\u2) = (z*w, r*w).map: { $_ % $.n }
if (isZero.call(p)) return Epnt.new(q.x, q.y)
my \p = (u1 ⊠ $.G ) ⊞ (u2 ⊠ public_key);
if (isZero.call(q)) return Epnt.new(p.x, % $.n) == (r % $p.ny)
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 kP
var 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 f
var 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 curve
var 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 primitive
var 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 primitive
var 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 d
var 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,
print "The Curve E is : ";
// short Weierstrass model y^2 = x^3 + ax + b (mod N)
"𝑦² = 𝑥³ + %s 𝑥 + %s (mod %s) \n".printf(A,B,P);
var sets = [
"with Generator G at : (%s,%s)\n".printf(Gx,Gy);
// a, b, modulus N, base point G, order(G, E), cofactor
my $ec = Signature.new: n => O, G => Point.new: x => Gx, y => Gy ;
[355, 671, 1073741789, 13693, 10088, 1073807281],
say "Order(G, E) is : ", O;
say "Is G [ E0, ? 7, 67096021, 6580, 779, : " 16769911], $ec.G.isOn;// 4
say "Message [ -3, 1, 877073, : "0, my \message = "Show me1, the monKey"; 878159],
[ 0, 14, 22651, 63, 30, 151], // 151
say "The private key dA is : ", my \dA = (1..^O).roll;
[ 3, 2, 5, 2, 1, 5],
my ($r, $s, \Qa) = $ec.generate_signature(dA, message);
 
say "The public key Qa is : ", Qa;
// ecdsa may fail if...
say "Is Qa ∈ E ? : ", Qa.isOn;
// the base point is of composite order
say "Is signature valid? : ", $ec.verify_signature(message, $r, $s, Qa);
[ 0, 7, 67096021, 2402, 6067, 33539822], // 2
say "Message (Tampered) : ", my \altered = "Show me the money";
// the given order is a multiple of the true order
say "Is signature valid? : ", $ec.verify_signature(altered, $r, $s, Qa)</lang>
[ 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
var f = 0x789abcde
var d = 0
 
for (s in sets) {
if (ellinit.call(s)) {
ec_dsa.call(f, d)
} else {
break
}
}</syntaxhighlight>
 
{{out}}
Sample output - first set only.
<pre>The Curve E is : 𝑦² = 𝑥³ + 355 𝑥 + 671 (mod 1073741789)
<pre>
with Generator G at : (13693,10088)
E: y^2 = x^3 + 355x + 671 (mod 1073741789)
Order(G, E) is : 1073807281
base point G (13693, 10088)
Is G ∈ E ? : True
order(G, E) = 1073807281
Message : Show me the monKey
 
The private key dA is : 384652035
key generation
The public key Qa is : EC Point at x=919494857, y=18030536
private key s = 121877962
Is Qa ∈ E ? : True
 
Is signature valid? : True
public key W = sG (320982025, 402911160)
Message (Tampered) : Show me the money
 
Is signature valid? : False
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
</pre>
9,476

edits