Elliptic Curve Digital Signature Algorithm: Difference between revisions
m (→{{header|Perl 6}}: Thanks to Thundergnat for the advice ; use the correct lib ; remove unnecessary int/str round trip ; echo the Julia entry by showing a failure and suppress naughty hyper) |
m (→{{header|Wren}}: Minor tidy) |
||
(23 intermediate revisions by 10 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task|Cryptography}} |
||
;Elliptic curves. |
;Elliptic curves. |
||
An [[wp:Elliptic_curve|elliptic curve]] E over ℤp (p ≥ 5) is defined by an equation of the form |
An [[wp:Elliptic_curve|elliptic curve]] E over ℤp (p ≥ 5) is defined by an equation of the form |
||
'''y |
'''y²= x³ + ax + b''', where a, b ∈ ℤp and the discriminant ≢ 0 (mod p), |
||
together with a special point 𝒪 called the point at infinity. |
together with a special point 𝒪 called the point at infinity. |
||
The set '''E(ℤp)''' consists of all points (x, y), with x, y ∈ ℤp, |
The set '''E(ℤp)''' consists of all points (x, y), with x, y ∈ ℤp, |
||
Line 110: | Line 110: | ||
__TOC__ |
__TOC__ |
||
=={{header|C}}== |
=={{header|C}}== |
||
Parallel to: FreeBASIC |
Parallel to: FreeBASIC |
||
<syntaxhighlight lang="c"> |
|||
<lang c> |
|||
/* |
/* |
||
subject: Elliptic curve digital signature algorithm, |
subject: Elliptic curve digital signature algorithm, |
||
Line 459: | Line 458: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
(tcc, srand(1); first set only) |
(tcc, srand(1); first set only) |
||
Line 488: | Line 487: | ||
</pre> |
</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}}== |
=={{header|FreeBASIC}}== |
||
Parallel to: C |
Parallel to: C |
||
< |
<syntaxhighlight lang="freebasic"> |
||
'subject: Elliptic curve digital signature algorithm, |
'subject: Elliptic curve digital signature algorithm, |
||
' toy version for small modulus N. |
' toy version for small modulus N. |
||
Line 825: | Line 1,154: | ||
system |
system |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
(randomize 1, first set only) |
(randomize 1, first set only) |
||
Line 856: | Line 1,185: | ||
=={{header|Go}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 897: | Line 1,226: | ||
valid := ecdsa.Verify(&priv.PublicKey, hash[:], r, s) |
valid := ecdsa.Verify(&priv.PublicKey, hash[:], r, s) |
||
fmt.Println("\nSignature verified:", valid) |
fmt.Println("\nSignature verified:", valid) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 917: | Line 1,246: | ||
Signature verified: true |
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> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">module ToyECDSA |
||
using SHA |
using SHA |
||
Line 1,106: | Line 1,745: | ||
println("ECDSA of message <$altered> verified: ", isverifiedECDSA(altered, publickey, c, d)) |
println("ECDSA of message <$altered> verified: ", isverifiedECDSA(altered, publickey, c, d)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
ECDSA of message <Bill says this is an elliptic curve digital signature algorithm.> verified: true |
ECDSA of message <Bill says this is an elliptic curve digital signature algorithm.> verified: true |
||
Line 1,112: | Line 1,751: | ||
</pre> |
</pre> |
||
=={{header| |
=={{header|Nim}}== |
||
{{trans|C}} |
|||
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. |
|||
<syntaxhighlight lang="nim">import math, random, strformat |
|||
<lang perl6>#!/usr/bin/env perl6 |
|||
const |
|||
use Digest::SHA256::Native; |
|||
MaxN = 1073741789 # Maximum modulus. |
|||
MaxR = MaxN + 65536 # Maximum order "g". |
|||
Infinity = int64.high # Symbolic infinity. |
|||
type |
|||
# Following data taken from the C entry |
|||
our (\A,\B,\P,\O,\Gx,\Gy) = (355, 671, 1073741789, 1073807281, 13693, 10088); |
|||
Point = tuple[x, y: int64] |
|||
#`{ Following data taken from the Julia entry; 256-bit; tested |
|||
our (\A,\B,\P,\O,\Gx,\Gy) = (0, 7, # https://en.bitcoin.it/wiki/Secp256k1 |
|||
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F, |
|||
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141, |
|||
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, |
|||
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8); # } |
|||
Curve = object |
|||
role Horizon { method gist { 'EC Point at horizon' } } |
|||
a, b: int64 |
|||
n: int64 |
|||
g: Point |
|||
r: int64 |
|||
Pair = tuple[a, b: int64] |
|||
class Point { # modified from the Elliptic_curve_arithmetic entry |
|||
has ($.x, $.y); # handle modular arithmetic only |
|||
multi method new( \x, \y ) { self.bless(:x, :y) } |
|||
method gist { "EC Point at x=$.x, y=$.y" } |
|||
method isOn { modP(B + $.x * modP(A+$.x²)) == modP($.y²) } |
|||
sub modP ($a is copy) { ( $a %= P ) < 0 ?? ($a += P) !! $a } |
|||
} |
|||
Parameters = tuple[a, b, n, gx, gy, r: int] |
|||
multi infix:<⊞>(Point \p, Point \q) { |
|||
my \λ = $; # slope |
|||
if p.x ~~ q.x and p.y ~~ q.y { |
|||
return Horizon if p.y == 0 ; |
|||
λ = (3*p.x²+ A) * mult_inv(2*p.y, :modulo(P)) |
|||
} else { |
|||
λ = (p.y - q.y) * mult_inv(p.x - q.x, :modulo(P)) |
|||
} |
|||
my \xr = (λ²- p.x - q.x); |
|||
my \yr = (λ*(p.x - xr) - p.y); |
|||
return Point.bless: x => xr % P, y => yr % P |
|||
} |
|||
const ZerO: Point = (Infinity, 0i64) |
|||
multi infix:<⊠>(Int \n, Point \p) { |
|||
return 0 if n == 0 ; |
|||
return p if n == 1 ; |
|||
return p ⊞ ((n-1) ⊠ p ) if n % 2 == 1 ; |
|||
return ( n div 2 ) ⊠ ( p ⊞ p ) |
|||
} |
|||
type |
|||
sub mult_inv($n, :$modulo) { # rosettacode.org/wiki/Modular_inverse#Perl_6 |
|||
InversionError = object of ValueError |
|||
my ($c, $d, $uc, $vd, $vc, $ud, $q) = $n % $modulo, $modulo, 1, 1, 0, 0, 0; |
|||
InvalidParamError = object of ValueError |
|||
while $c != 0 { |
|||
($q, $c, $d) = ($d div $c, $d % $c, $c); |
|||
($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc); |
|||
} |
|||
return $ud % $modulo; |
|||
} |
|||
class Signature { |
|||
template `%`(a, n: int64): int64 = |
|||
has ($.n, Point $.G); # Order and Generator point |
|||
## To simplify the writing. |
|||
floorMod(a, n) |
|||
method generate_signature(Int \private_key, Str \msg) { |
|||
my \z = :16(sha256-hex msg) % $.n; # self ref: Blob.list.fmt("%02X",'') |
|||
loop ( my $k = my $s = my $r = 0 ; $s == 0 ; ) { |
|||
loop ( $r = $s = 0 ; $r == 0 ; ) { |
|||
$r = (( $k = (1..^$.n).roll ) ⊠ $.G).x % $.n; |
|||
} |
|||
$s = ((z + $r*private_key) * mult_inv $k, :modulo($.n)) % $.n; |
|||
} |
|||
return $r, $s, private_key ⊠ $.G ; |
|||
} |
|||
proc exgcd(v, u: int64): int64 = |
|||
method verify_signature(\msg, \r, \s, \public_key) { |
|||
## Return 1/v mod u. |
|||
my \z = :16(sha256-hex msg) % $.n; |
|||
var u = u |
|||
my \w = mult_inv s, :modulo($.n); |
|||
var v = v |
|||
my (\u1,\u2) = (z*w, r*w).map: { $_ % $.n } |
|||
if v < 0: v += u |
|||
my \p = (u1 ⊠ $.G ) ⊞ (u2 ⊠ public_key); |
|||
return (p.x % $.n) == (r % $.n) |
|||
} |
|||
} |
|||
var r = 0i64 |
|||
print "The Curve E is : "; |
|||
var s = 1i64 |
|||
"𝑦² = 𝑥³ + %s 𝑥 + %s (mod %s) \n".printf(A,B,P); |
|||
while v != 0: |
|||
"with Generator G at : (%s,%s)\n".printf(Gx,Gy); |
|||
let q = u div v |
|||
my $ec = Signature.new: n => O, G => Point.new: x => Gx, y => Gy ; |
|||
u = u mod v |
|||
say "Order(G, E) is : ", O; |
|||
swap u, v |
|||
say "Is G ∈ E ? : ", $ec.G.isOn; |
|||
r -= q * s |
|||
say "Message : ", my \message = "Show me the monKey"; |
|||
swap r, s |
|||
say "The private key dA is : ", my \dA = (1..^O).roll; |
|||
my ($r, $s, \Qa) = $ec.generate_signature(dA, message); |
|||
say "The public key Qa is : ", Qa; |
|||
say "Is Qa ∈ E ? : ", Qa.isOn; |
|||
say "Is signature valid? : ", $ec.verify_signature(message, $r, $s, Qa); |
|||
say "Message (Tampered) : ", my \altered = "Show me the money"; |
|||
say "Is signature valid? : ", $ec.verify_signature(altered, $r, $s, Qa)</lang> |
|||
{{out}} |
|||
<pre>The Curve E is : 𝑦² = 𝑥³ + 355 𝑥 + 671 (mod 1073741789) |
|||
with Generator G at : (13693,10088) |
|||
Order(G, E) is : 1073807281 |
|||
Is G ∈ E ? : True |
|||
Message : Show me the monKey |
|||
The private key dA is : 384652035 |
|||
The public key Qa is : EC Point at x=919494857, y=18030536 |
|||
Is Qa ∈ E ? : True |
|||
Is signature valid? : True |
|||
Message (Tampered) : Show me the money |
|||
Is signature valid? : False |
|||
</pre> |
|||
if u != 1: |
|||
=={{header|Phix}}== |
|||
raise newException(InversionError, "impossible inverse mod N, gcd = " & $u) |
|||
{{trans|FreeBASIC}} |
|||
result = r |
|||
<lang Phix>enum X, Y -- rational ec point |
|||
enum A, B, N, G, R -- elliptic curve parameters |
|||
-- also signature pair(A,B) |
|||
constant mxN = 1073741789 -- maximum modulus |
|||
constant mxr = 1073807325 -- max order G = mxN + 65536 |
|||
constant inf = -2147483647 -- symbolic infinity |
|||
func discr(e: Curve): int64 = |
|||
sequence e = {0,0,0,{0,0},0} -- single global curve |
|||
## Return the discriminant of "e". |
|||
constant zerO = {inf,0} -- point at infinity zerO |
|||
let c = e.a * e.a % e.n * e.a % e.n * 4 |
|||
result = -16 * (e.b * e.b % e.n * 27 + c) % e.n |
|||
bool inverr -- impossible inverse mod N |
|||
func isO(p: Point): bool = |
|||
function exgcd(atom v, u) |
|||
## Return true if "p" is zero. |
|||
-- return mod(v^-1, u) |
|||
p.x == Infinity and p.y == 0 |
|||
if v<0 then v += u end if |
|||
while v do |
|||
q = floor(u/v) |
|||
t = u-q*v |
|||
u = v |
|||
v = t |
|||
t = r-q*s |
|||
r = s |
|||
s = t |
|||
end while |
|||
func isOn(e: Curve; p: Point): bool = |
|||
if u!=1 then |
|||
## Return true if "p" is on curve "e". |
|||
printf(1," impossible inverse mod N, gcd = %d\n",{u}) |
|||
if p.isO: return true |
|||
let r = ((e.a + p.x * p.x) % e.n * p.x + e.b) % e.n |
|||
end if |
|||
let s = p.y * p.y % e.n |
|||
result = r == s |
|||
return r |
|||
end function |
|||
proc add(e: Curve; p, q: Point): Point = |
|||
function modn(atom a) |
|||
## Full Point addition. |
|||
-- return mod(a, N) |
|||
a = mod(a,e[N]) |
|||
if a<0 then a += e[N] end if |
|||
return a |
|||
end function |
|||
if p.isO: return q |
|||
function modr(atom a) |
|||
if q.isO: return p |
|||
-- return mod(a, r) |
|||
a = mod(a,e[R]) |
|||
if a<0 then a += e[R] end if |
|||
return a |
|||
end function |
|||
var la: int64 |
|||
function disc() |
|||
if p.x != q.x: |
|||
-- return the discriminant of E |
|||
la = (p.y - q.y) * exgcd(p.x - q.x, e.n) % e.n |
|||
elif p.y == q.y and p.y != 0: |
|||
c = 4*modn(a*modn(a*a)) |
|||
la = (p.x * p.x % e.n * 3 + e.a) % e.n * exgcd(2 * p.y, e.n) % e.n |
|||
return modn(-16*(c+27*modn(b*b))) |
|||
else: |
|||
end function |
|||
return ZerO |
|||
result.x = (la * la - p.x - q.x) % e.n |
|||
function isO(sequence p) |
|||
result.y = (la * (p.x - result.x) - p.y) % e.n |
|||
-- return true if P = zerO |
|||
return (p[X]=inf and p[Y]=0) |
|||
end function |
|||
function ison(sequence p) |
|||
-- return true if P is on curve E |
|||
atom r = 0, s = 0 |
|||
if not isO(p) then |
|||
r = modn(e[B]+p[X]*modn(e[A]+p[X]*p[X])) |
|||
s = modn(p[Y]*p[Y]) |
|||
end if |
|||
return (r=s) |
|||
end function |
|||
proc mul(e: Curve; p: Point; k: int64): Point = |
|||
procedure pprint(string f, sequence p) |
|||
## Return "kp". |
|||
-- print point P with prefix f |
|||
var q = p |
|||
var k = k |
|||
printf(1,"%s (0)\n",{f}) |
|||
result = ZerO |
|||
atom y = p[Y] |
|||
if y>e[N]-y then y -= e[N] end if |
|||
printf(1,"%s (%d,%d)\n",{f,p[X],y}) |
|||
end if |
|||
end procedure |
|||
while k != 0: |
|||
function padd(sequence p, q) |
|||
if (k and 1) != 0: |
|||
-- full ec point addition |
|||
result = e.add(result, q) |
|||
atom la, t |
|||
q = e.add(q, q) |
|||
k = k shr 1 |
|||
if isO(p) then return q end if |
|||
if isO(q) then return p end if |
|||
proc print(e: Curve; prefix: string; p: Point) = |
|||
if p[X]!=q[X] then -- R := P + Q |
|||
## Print a point with a prefix. |
|||
var y = p.y |
|||
la = modn(t*exgcd(p[X]-q[X], e[N])) |
|||
if p.isO: |
|||
echo prefix, " (0)" |
|||
else: |
|||
if y > e.n - y: y -= e.n |
|||
echo prefix, &" ({p.x}, {y})" |
|||
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 |
|||
proc initCurve(params: Parameters): Curve = |
|||
t = modn(la*la-p[X]-q[X]) |
|||
## Initialize the curve. |
|||
sequence r = zerO |
|||
r[Y] = modn(la*(p[X]-t)-p[Y]) |
|||
r[X] = t |
|||
if inverr then r = zerO end if |
|||
return r |
|||
end function |
|||
result.n = params.n |
|||
function pmul(sequence p, atom k) |
|||
if result.n notin 5..MaxN: |
|||
-- R:= multiple kP |
|||
raise newException(ValueError, "invalid value for N: " & $result.n) |
|||
sequence s = zerO, q = p |
|||
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: |
|||
while k do |
|||
raise newException(ValueError, "invalid value for r: " & $result.r) |
|||
if and_bits(k,1) then |
|||
s = padd(s, q) |
|||
end if |
|||
if inverr then s = zerO; exit end if |
|||
k = floor(k/2) |
|||
q = padd(q, q) |
|||
end while |
|||
return s |
|||
end function |
|||
echo &"\nE: y^2 = x^3 + {result.a}x + {result.b} (mod {result.n})" |
|||
function ellinit(sequence i) |
|||
result.print("base point G", result.g) |
|||
-- initialize elliptic curve |
|||
echo &"order(G, E) = {result.r}" |
|||
inverr = false |
|||
e[N] = i[3] |
|||
if (e[N]<5) or (e[N]>mxN) then return 0 end if |
|||
proc rnd(): float = |
|||
e[A] = modn(a) |
|||
## Return a pseudorandom number in range [0..1[. |
|||
e[B] = modn(b) |
|||
while true: |
|||
e[G][X] = modn(i[4]) |
|||
result = rand(1.0) |
|||
if result != 1: break |
|||
proc signature(e: Curve; s, f: int64): Pair = |
|||
if (e[R]<5) or (e[R]>mxr) then return 0 end if |
|||
## Compute the signature. |
|||
var |
|||
printf(1,"E: y^2 = x^3 + %dx + %d (mod %d)\n",{a,b,e[N]}) |
|||
c, d = 0i64 |
|||
u: int64 |
|||
printf(1,"order(G, E) = %d\n",{e[R]}) |
|||
v: Point |
|||
echo "Signature computation" |
|||
return -1 |
|||
end function |
|||
while true: |
|||
function signature(atom s, f) |
|||
while true: |
|||
-- signature primitive |
|||
u = 1 + int64(rnd() * float(e.r - 1)) |
|||
atom c, d, u, u1 |
|||
v = e.mul(e.g, u) |
|||
sequence V |
|||
c = v.x % e.r |
|||
if c != 0: break |
|||
d = exgcd(u, e.r) * (f + s * c % e.r) % e.r |
|||
if d != 0: break |
|||
echo "one-time u = ", u |
|||
printf(1,"signature computation\n") |
|||
e.print("V = uG", v) |
|||
while true do |
|||
while true do |
|||
-- u = rand(e[R]-1) |
|||
u = 571533488 -- match FreeBASIC output |
|||
-- u = 605163545 -- match C output |
|||
V = pmul(e[G], u) |
|||
c = modr(V[X]) |
|||
if c!=0 then exit end if |
|||
end while |
|||
result = (c, d) |
|||
d = modr(u1*(f+modr(s*c))) |
|||
if d!=0 then exit end if |
|||
end while |
|||
printf(1,"one-time u = %d\n",u) |
|||
pprint("V = uG", V) |
|||
return {c,d} |
|||
end function |
|||
function verify(sequence W, atom f, sequence sg) |
|||
-- verification primitive |
|||
atom c = sg[A], d = sg[B], |
|||
t, c1, h1, h2, h |
|||
sequence V, V2 |
|||
proc verify(e: Curve; w: Point; f: int64; sg: Pair): bool = |
|||
--domain check |
|||
## Verify a signature. |
|||
t = (c>0) and (c<e[R]) |
|||
t = t and (d>0) and (d<e[R]) |
|||
if not t then return 0 end if |
|||
# Domain check. |
|||
printf(1,"\nsignature verification\n") |
|||
if sg.a notin 1..<e.r or sg.b notin 1..<e.r: |
|||
h = exgcd(d, e[R]) |
|||
return false |
|||
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) |
|||
echo "\nsignature verification" |
|||
return (c1=c) |
|||
let h = exgcd(sg.b, e.r) |
|||
end function |
|||
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 |
|||
procedure errmsg() |
|||
printf(1,"invalid parameter set\n") |
|||
printf(1,"_____________________\n") |
|||
end procedure |
|||
proc ecdsa(e: Curve; f: int64; d: int) = |
|||
procedure ec_dsa(atom f, d) |
|||
## Build digital signature for message hash "f" with error bit "d". |
|||
atom i, s, t |
|||
sequence sg, W |
|||
# 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") |
|||
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 |
|||
echo "\nkey generation" |
|||
let s = 1 + int64(rnd() * float(e.r - 1)) |
|||
w = e.mul(e.g, s) |
|||
s = 509100772 -- match FreeBASIC output |
|||
echo "private key s = ", s |
|||
-- s = 1343570 -- match C output |
|||
W = |
e.print("public key W = sG", w) |
||
printf(1,"private key s = %d\n",{s}) |
|||
pprint("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 = t or t shr i |
||
i = i shl 1 |
|||
var f = f |
|||
while f > t: f = f shr 1 |
|||
echo &"\naligned hash {f:x}" |
|||
f = floor(f/2) |
|||
end while |
|||
printf(1,"\naligned hash %x\n\n",{f}) |
|||
let sg = e.signature(s, f) |
|||
echo &"signature c, d = {sg.a}, {sg.b}" |
|||
if inverr then errmsg() return end if |
|||
printf(1,"signature c,d = %d,%d\n",sg) |
|||
var d = d |
|||
if d > 0: |
|||
while d > t: d = d shr 1 |
|||
f = f xor d |
|||
echo &"\ncorrupted hash {f:x}" |
|||
f = xor_bits(f,d) |
|||
printf(1,"corrupted hash %x\n",{f}) |
|||
end if |
|||
echo if e.verify(w, f, sg): "Valid" else: "Invalid" |
|||
if inverr then errmsg() return end if |
|||
if t then |
|||
printf(1,"Valid\n_____\n") |
|||
else |
|||
printf(1,"invalid\n_______\n") |
|||
end if |
|||
end procedure |
|||
when isMainModule: |
|||
--Test vectors: elliptic curve domain parameters, |
|||
--short Weierstrass model y^2 = x^3 + ax + b (mod N) |
|||
randomize() |
|||
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}, |
|||
# Test vectors: elliptic curve domain parameters, |
|||
--ecdsa may fail if... |
|||
# short Weierstrass model y^2 = x^3 + ax + b (mod N) |
|||
--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}} |
|||
const Sets = [ |
|||
--Digital signature on message hash f, |
|||
# a, b, modulus N, base point G, order(G, E), cofactor |
|||
--set d > 0 to simulate corrupted data |
|||
(355, 671, 1073741789, 13693, 10088, 1073807281), |
|||
atom f = #789ABCDE, |
|||
( 0, 7, 67096021, 6580, 779, 16769911), |
|||
d = 0 |
|||
( -3, 1, 877073, 0, 1, 878159), |
|||
( 0, 14, 22651, 63, 30, 151), |
|||
( 3, 2, 5, 2, 1, 5), |
|||
# ECDSA may fail if... |
|||
if machine_bits()!=64 then crash("needs 64 bit") end if |
|||
# the base point is of composite order |
|||
--for i=1 to length(tests) do |
|||
( 0, 7, 67096021, 2402, 6067, 33539822), |
|||
for i=1 to 1 do |
|||
# the given order is of composite order |
|||
if not ellinit(tests[i]) then exit end if |
|||
( 0, 7, 67096021, 6580, 779, 67079644), |
|||
ec_dsa(f, d) |
|||
# the modulus is not prime (deceptive example) |
|||
end for</lang> |
|||
( 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 > 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}} |
{{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. |
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,541: | Line 2,398: | ||
Valid |
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 { |
|||
use FiniteField; |
|||
our class Point { |
|||
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 } |
|||
multi infix:<+>(Point $A, Point:U) is export { $A } |
|||
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 { |
|||
return Point.new: $_, $λ*($A.x - $_) - $A.y; |
|||
} |
|||
} |
|||
multi infix:<*>(0, Point ) is export { Point } |
|||
multi infix:<*>(1, Point $p) is export { $p } |
|||
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; |
|||
module ECDSA { |
|||
use Digest::SHA256::Native; |
|||
our class Signature { |
|||
has UInt ($.c, $.d); |
|||
multi method new(Str $message, UInt :$private-key) { |
|||
my $z = :16(sha256-hex $message) % $*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; |
|||
my $*modulus = my $*p = 1073741789; |
|||
my $*G = EC::Point.new: 13693, 10088; |
|||
my $*n = 1073807281; |
|||
die "G is not of order n" if $*n*$*G; |
|||
my $private-key = ^$*n .pick; |
|||
my $public-key = $private-key*$*G; |
|||
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 |
|||
var modn = Fn.new { |a| |
|||
var b = a.copy() |
|||
b = b % e.N |
|||
if (b < 0) b = b + e.N |
|||
return b |
|||
} |
|||
// returns mod(a, r), a is a BigInt |
|||
var modr = Fn.new { |a| |
|||
var b = a.copy() |
|||
b = b % e.r |
|||
if (b < 0) b = b + e.r |
|||
return b |
|||
} |
|||
// returns the discriminant of E |
|||
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) |
|||
var isZero = Fn.new { |p| p.x == inf && p.y == 0 } |
|||
// return true if P is on curve E |
|||
var isOn = Fn.new { |p| |
|||
var r = 0 |
|||
var s = 0 |
|||
if (!isZero.call(p)) { |
|||
r = modn.call(p.x * modn.call(p.x * p.x + e.a) + e.b).toSmall |
|||
s = modn.call(p.y * p.y).toSmall |
|||
} |
|||
return r == s |
|||
} |
|||
// full ec point addition |
|||
var padd = Fn.new { |p, q| |
|||
var la = BigInt.zero |
|||
var t = BigInt.zero |
|||
if (isZero.call(p)) return Epnt.new(q.x, q.y) |
|||
if (isZero.call(q)) return Epnt.new(p.x, p.y) |
|||
if (p.x != q.x) { // R = P + Q |
|||
t = p.y - q.y |
|||
la = modn.call(t * exgcd.call((p.x - q.x).toSmall, e.N.toSmall)) |
|||
} else { // P = Q, R = 2P |
|||
if (p.y == q.y && p.y != 0) { |
|||
t = modn.call(modn.call(p.x * p.x) * 3 + e.a) |
|||
la = modn.call(t * exgcd.call((p.y * 2).toSmall, e.N.toSmall)) |
|||
} else { |
|||
return Epnt.new(inf, BigInt.zero) // P = -Q, R = O |
|||
} |
|||
} |
|||
if (inverr) return Epnt.new(inf, BigInt.zero) |
|||
t = modn.call(la * la - p.x - q.x) |
|||
return Epnt.new(t, modn.call(la * (p.x - t) - p.y)) |
|||
} |
|||
// R = multiple 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, |
|||
// short Weierstrass model y^2 = x^3 + ax + b (mod N) |
|||
var sets = [ |
|||
// a, b, modulus N, base point G, order(G, E), cofactor |
|||
[355, 671, 1073741789, 13693, 10088, 1073807281], |
|||
[ 0, 7, 67096021, 6580, 779, 16769911], // 4 |
|||
[ -3, 1, 877073, 0, 1, 878159], |
|||
[ 0, 14, 22651, 63, 30, 151], // 151 |
|||
[ 3, 2, 5, 2, 1, 5], |
|||
// ecdsa may fail if... |
|||
// the base point is of composite order |
|||
[ 0, 7, 67096021, 2402, 6067, 33539822], // 2 |
|||
// the given order is a multiple of the true order |
|||
[ 0, 7, 67096021, 6580, 779, 67079644], // 1 |
|||
// the modulus is not prime (deceptive example) |
|||
[ 0, 7, 877069, 3, 97123, 877069], |
|||
// fails if the modulus divides the discriminant |
|||
[ 39, 387, 22651, 95, 27, 22651] |
|||
] |
|||
// Digital signature on message hash f, |
|||
// set d > 0 to simulate corrupted 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> |
|||
E: y^2 = x^3 + 355x + 671 (mod 1073741789) |
|||
base point G (13693, 10088) |
|||
order(G, E) = 1073807281 |
|||
key generation |
|||
private key s = 121877962 |
|||
public key W = sG (320982025, 402911160) |
|||
aligned hash 789abcde |
|||
signature computation |
|||
one-time u = 899439563 |
|||
V = uG (105563482, 310387297) |
|||
signature c, d = 105563482, 270442619 |
|||
signature verification |
|||
h1, h2 = 123954960, 653133035 |
|||
h1G (623038071, 220475456) |
|||
h2W (893517020, -249809739) |
|||
+ = (105563482, 310387297) |
|||
c' = 105563482 |
|||
Valid |
|||
</pre> |
</pre> |
Latest revision as of 16:53, 28 November 2023
You are encouraged to solve this task according to the task description, using any language you may know.
- Elliptic curves.
An elliptic curve E over ℤp (p ≥ 5) is defined by an equation of the form y²= x³ + ax + b, where a, b ∈ ℤp and the discriminant ≢ 0 (mod p), together with a special point 𝒪 called the point at infinity. The set E(ℤp) consists of all points (x, y), with x, y ∈ ℤp, which satisfy the above defining equation, together with 𝒪.
There is a rule for adding two points on an elliptic curve to give a third point. This addition operation and the set of points E(ℤp) form a group with identity 𝒪. It is this group that is used in the construction of elliptic curve cryptosystems.
The addition rule — which can be explained geometrically — is summarized as follows:
1. P + 𝒪 = 𝒪 + P = P for all P ∈ E(ℤp). 2. If P = (x, y) ∈ E(ℤp), then inverse -P = (x,-y), and P + (-P) = 𝒪. 3. Let P = (xP, yP) and Q = (xQ, yQ), both ∈ E(ℤp), where P ≠ -Q. Then R = P + Q = (xR, yR), where xR = λ^2 - xP - xQ yR = λ·(xP - xR) - yP, with λ = (yP - yQ) / (xP - xQ) if P ≠ Q, (3·xP·xP + a) / 2·yP if P = Q (point doubling).
Remark: there already is a task page requesting “a simplified (without modular arithmetic) version of the elliptic curve arithmetic”. Here we do add modulo operations. If also the domain is changed from reals to rationals, the elliptic curves are no longer continuous but break up into a finite number of distinct points. In that form we use them to implement ECDSA:
- Elliptic curve digital signature algorithm.
A digital signature is the electronic analogue of a hand-written signature that convinces the recipient that a message has been sent intact by the presumed sender. Anyone with access to the public key of the signer may verify this signature. Changing even a single bit of a signed message will cause the verification procedure to fail.
ECDSA key generation. Party A does the following:
1. Select an elliptic curve E defined over ℤp.
The number of points in E(ℤp) should be divisible by a large prime r.
2. Select a base point G ∈ E(ℤp) of order r (which means that rG = 𝒪).
3. Select a random integer s in the interval [1, r - 1].
4. Compute W = sG.
The public key is (E, G, r, W), the private key is s.
ECDSA signature computation. To sign a message m, A does the following:
1. Compute message representative f = H(m), using a
cryptographic hash function.
Note that f can be greater than r but not longer (measuring bits).
2. Select a random integer u in the interval [1, r - 1].
3. Compute V = uG = (xV, yV) and c ≡ xV mod r (goto (2) if c = 0).
4. Compute d ≡ u^-1·(f + s·c) mod r (goto (2) if d = 0).
The signature for the message m is the pair of integers (c, d).
ECDSA signature verification. To verify A's signature, B should do the following:
1. Obtain an authentic copy of A's public key (E, G, r, W).
Verify that c and d are integers in the interval [1, r - 1].
2. Compute f = H(m) and h ≡ d^-1 mod r.
3. Compute h1 ≡ f·h mod r and h2 ≡ c·h mod r.
4. Compute h1G + h2W = (x1, y1) and c1 ≡ x1 mod r.
Accept the signature if and only if c1 = c.
To be cryptographically useful, the parameter r should have at least 250 bits. The basis for the security of elliptic curve cryptosystems is the intractability of the elliptic curve discrete logarithm problem (ECDLP) in a group of this size: given two points G, W ∈ E(ℤp), where W lies in the subgroup of order r generated by G, determine an integer k such that W = kG and 0 ≤ k < r.
- Task.
The task is to write a toy version of the ECDSA, quasi the equal of a real-world
implementation, but utilizing parameters that fit into standard arithmetic types.
To keep things simple there's no need for key export or a hash function (just a sample
hash value and a way to tamper with it). The program should be lenient where possible
(for example: if it accepts a composite modulus N it will either function as expected,
or demonstrate the principle of elliptic curve factorization)
— but strict where required (a point G that is not on E will always cause failure).
Toy ECDSA is of course completely useless for its cryptographic purpose.
If this bothers you, please add a multiple-precision version.
- Reference.
Elliptic curves are in the IEEE Std 1363-2000 (Standard Specifications for Public-Key Cryptography), see:
7. Primitives based on the elliptic curve discrete logarithm problem (p. 27ff.)
7.1 The EC setting
7.1.2 EC domain parameters
7.1.3 EC key pairs
7.2 Primitives
7.2.7 ECSP-DSA (p. 35)
7.2.8 ECVP-DSA (p. 36)
Annex A. Number-theoretic background
A.9 Elliptic curves: overview (p. 115)
A.10 Elliptic curves: algorithms (p. 121)
C
Parallel to: FreeBASIC
/*
subject: Elliptic curve digital signature algorithm,
toy version for small modulus N.
tested : gcc 4.6.3, tcc 0.9.27
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 64-bit integer type
typedef long long int dlong;
// rational ec point
typedef struct {
dlong x, y;
} epnt;
// elliptic curve parameters
typedef struct {
long a, b;
dlong N;
epnt G;
dlong r;
} curve;
// signature pair
typedef struct {
long a, b;
} pair;
// dlong for holding intermediate results,
// long variables in exgcd() for efficiency,
// maximum parameter size 2 * p.y (line 129)
// limits the modulus size to 30 bits.
// maximum modulus
const long mxN = 1073741789;
// max order G = mxN + 65536
const long mxr = 1073807325;
// symbolic infinity
const long inf = -2147483647;
// single global curve
curve e;
// point at infinity zerO
epnt zerO;
// impossible inverse mod N
int inverr;
// return mod(v^-1, u)
long exgcd (long v, long u)
{
register long q, t;
long r = 0, s = 1;
if (v < 0) v += u;
while (v) {
q = u / v;
t = u - q * v;
u = v; v = t;
t = r - q * s;
r = s; s = t;
}
if (u != 1) {
printf (" impossible inverse mod N, gcd = %d\n", u);
inverr = 1;
}
return r;
}
// return mod(a, N)
static inline dlong modn (dlong a)
{
a %= e.N;
if (a < 0) a += e.N;
return a;
}
// return mod(a, r)
dlong modr (dlong a)
{
a %= e.r;
if (a < 0) a += e.r;
return a;
}
// return the discriminant of E
long disc (void)
{
dlong c, a = e.a, b = e.b;
c = 4 * modn(a * modn(a * a));
return modn(-16 * (c + 27 * modn(b * b)));
}
// return 1 if P = zerO
int isO (epnt p)
{
return (p.x == inf) && (p.y == 0);
}
// return 1 if P is on curve E
int ison (epnt p)
{
long r, s;
if (! isO (p)) {
r = modn(e.b + p.x * modn(e.a + p.x * p.x));
s = modn(p.y * p.y);
}
return (r == s);
}
// full ec point addition
void padd (epnt *r, epnt p, epnt q)
{
dlong la, t;
if (isO(p)) {*r = q; return;}
if (isO(q)) {*r = p; return;}
if (p.x != q.x) { // R:= P + Q
t = p.y - q.y;
la = modn(t * exgcd(p.x - q.x, e.N));
}
else // P = Q, R := 2P
if ((p.y == q.y) && (p.y != 0)) {
t = modn(3 * modn(p.x * p.x) + e.a);
la = modn(t * exgcd (2 * p.y, e.N));
}
else
{*r = zerO; return;} // P = -Q, R := O
t = modn(la * la - p.x - q.x);
r->y = modn(la * (p.x - t) - p.y);
r->x = t; if (inverr) *r = zerO;
}
// R:= multiple kP
void pmul (epnt *r, epnt p, long k)
{
epnt s = zerO, q = p;
for (; k; k >>= 1) {
if (k & 1) padd(&s, s, q);
if (inverr) {s = zerO; break;}
padd(&q, q, q);
}
*r = s;
}
// print point P with prefix f
void pprint (char *f, epnt p)
{
dlong y = p.y;
if (isO (p))
printf ("%s (0)\n", f);
else {
if (y > e.N - y) y -= e.N;
printf ("%s (%lld, %lld)\n", f, p.x, y);
}
}
// initialize elliptic curve
int ellinit (long i[])
{
long a = i[0], b = i[1];
e.N = i[2]; inverr = 0;
if ((e.N < 5) || (e.N > mxN)) return 0;
e.a = modn(a);
e.b = modn(b);
e.G.x = modn(i[3]);
e.G.y = modn(i[4]);
e.r = i[5];
if ((e.r < 5) || (e.r > mxr)) return 0;
printf ("\nE: y^2 = x^3 + %dx + %d", a, b);
printf (" (mod %lld)\n", e.N);
pprint ("base point G", e.G);
printf ("order(G, E) = %lld\n", e.r);
return 1;
}
// pseudorandom number [0..1)
double rnd(void)
{
return rand() / ((double)RAND_MAX + 1);
}
// signature primitive
pair signature (dlong s, long f)
{
long c, d, u, u1;
pair sg;
epnt V;
printf ("\nsignature computation\n");
do {
do {
u = 1 + (long)(rnd() * (e.r - 1));
pmul (&V, e.G, u);
c = modr(V.x);
}
while (c == 0);
u1 = exgcd (u, e.r);
d = modr(u1 * (f + modr(s * c)));
}
while (d == 0);
printf ("one-time u = %d\n", u);
pprint ("V = uG", V);
sg.a = c; sg.b = d;
return sg;
}
// verification primitive
int verify (epnt W, long f, pair sg)
{
long c = sg.a, d = sg.b;
long t, c1, h1, h2;
dlong h;
epnt V, V2;
// domain check
t = (c > 0) && (c < e.r);
t &= (d > 0) && (d < e.r);
if (! t) return 0;
printf ("\nsignature verification\n");
h = exgcd (d, e.r);
h1 = modr(f * h);
h2 = modr(c * h);
printf ("h1,h2 = %d, %d\n", h1,h2);
pmul (&V, e.G, h1);
pmul (&V2, W, h2);
pprint ("h1G", V);
pprint ("h2W", V2);
padd (&V, V, V2);
pprint ("+ =", V);
if (isO (V)) return 0;
c1 = modr(V.x);
printf ("c' = %d\n", c1);
return (c1 == c);
}
// digital signature on message hash f, error bit d
void ec_dsa (long f, long d)
{
long i, s, t;
pair sg;
epnt W;
// parameter check
t = (disc() == 0);
t |= isO (e.G);
pmul (&W, e.G, e.r);
t |= ! isO (W);
t |= ! ison (e.G);
if (t) goto errmsg;
printf ("\nkey generation\n");
s = 1 + (long)(rnd() * (e.r - 1));
pmul (&W, e.G, s);
printf ("private key s = %d\n", s);
pprint ("public key W = sG", W);
// next highest power of 2 - 1
t = e.r;
for (i = 1; i < 32; i <<= 1)
t |= t >> i;
while (f > t) f >>= 1;
printf ("\naligned hash %x\n", f);
sg = signature (s, f);
if (inverr) goto errmsg;
printf ("signature c,d = %d, %d\n", sg.a, sg.b);
if (d > 0) {
while (d > t) d >>= 1;
f ^= d;
printf ("\ncorrupted hash %x\n", f);
}
t = verify (W, f, sg);
if (inverr) goto errmsg;
if (t)
printf ("Valid\n_____\n");
else
printf ("invalid\n_______\n");
return;
errmsg:
printf ("invalid parameter set\n");
printf ("_____________________\n");
}
void main (void)
{
typedef long eparm[6];
long d, f;
zerO.x = inf; zerO.y = 0;
srand(time(NULL));
// Test vectors: elliptic curve domain parameters,
// short Weierstrass model y^2 = x^3 + ax + b (mod N)
eparm *sp, sets[10] = {
// a, b, modulus N, base point G, order(G, E), cofactor
{355, 671, 1073741789, 13693, 10088, 1073807281},
{ 0, 7, 67096021, 6580, 779, 16769911}, // 4
{ -3, 1, 877073, 0, 1, 878159},
{ 0, 14, 22651, 63, 30, 151}, // 151
{ 3, 2, 5, 2, 1, 5},
// ecdsa may fail if...
// the base point is of composite order
{ 0, 7, 67096021, 2402, 6067, 33539822}, // 2
// the given order is a multiple of the true order
{ 0, 7, 67096021, 6580, 779, 67079644}, // 1
// the modulus is not prime (deceptive example)
{ 0, 7, 877069, 3, 97123, 877069},
// fails if the modulus divides the discriminant
{ 39, 387, 22651, 95, 27, 22651},
};
// Digital signature on message hash f,
// set d > 0 to simulate corrupted data
f = 0x789abcde; d = 0;
for (sp = sets; ; sp++) {
if (ellinit (*sp))
ec_dsa (f, d);
else
break;
}
}
- Output:
(tcc, srand(1); first set only)
E: y^2 = x^3 + 355x + 671 (mod 1073741789) base point G (13693, 10088) order(G, E) = 1073807281 key generation private key s = 1343570 public key W = sG (817515107, -192163292) aligned hash 789abcde signature computation one-time u = 605163545 V = uG (464115167, -267961770) signature c,d = 464115167, 407284989 signature verification h1,h2 = 871754294, 34741072 h1G (708182134, 29830217) h2W (270156466, -328492261) + = (464115167, -267961770) c' = 464115167 Valid _____
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);
}
}
- Output:
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 ...
FreeBASIC
Parallel to: C
'subject: Elliptic curve digital signature algorithm,
' toy version for small modulus N.
'tested : FreeBasic 1.05.0
'rational ec point
type epnt
as longint x, y
end type
'elliptic curve parameters
type curve
as long a, b
as longint N
as epnt G
as longint r
end type
'signature pair
type pair
as long a, b
end type
'longint for holding intermediate results,
'long variables in exgcd() for efficiency,
'maximum parameter size 2 * p.y (line 118)
'limits the modulus size to 30 bits.
'maximum modulus
const mxN = 1073741789
'max order G = mxN + 65536
const mxr = 1073807325
'symbolic infinity
const inf = -2147483647
'single global curve
dim shared as curve e
'point at infinity zerO
dim shared as epnt zerO
'impossible inverse mod N
dim shared as byte inverr
'return mod(v^-1, u)
Function exgcd (byval v as long, byval u as long) as long
dim as long q, t
dim as long r = 0, s = 1
if v < 0 then v += u
while v
q = u \ v
t = u - q * v
u = v: v = t
t = r - q * s
r = s: s = t
wend
if u <> 1 then
print " impossible inverse mod N, gcd ="; u
inverr = -1
end if
exgcd = r
End Function
'return mod(a, N)
Function modn (byval a as longint) as longint
a mod= e.N
if a < 0 then a += e.N
modn = a
End Function
'return mod(a, r)
Function modr (byval a as longint) as longint
a mod= e.r
if a < 0 then a += e.r
modr = a
End Function
'return the discriminant of E
Function disc as long
dim as longint c, a = e.a, b = e.b
c = 4 * modn(a * modn(a * a))
disc = modn(-16 * (c + 27 * modn(b * b)))
End Function
'return -1 if P = zerO
Function isO (byref p as epnt) as byte
isO = (p.x = inf and p.y = 0)
End Function
'return -1 if P is on curve E
Function ison (byref p as epnt) as byte
dim as long r, s
if not isO (p) then
r = modn(e.b + p.x * modn(e.a + p.x * p.x))
s = modn(p.y * p.y)
end if
ison = (r = s)
End Function
'full ec point addition
Sub padd (byref r as epnt, byref p as epnt, byref q as epnt)
dim as longint la, t
if isO (p) then r = q: exit sub
if isO (q) then r = p: exit sub
if p.x <> q.x then ' R := P + Q
t = p.y - q.y
la = modn(t * exgcd (p.x - q.x, e.N))
else ' P = Q, R := 2P
if (p.y = q.y) and (p.y <> 0) then
t = modn(3 * modn(p.x * p.x) + e.a)
la = modn(t * exgcd (2 * p.y, e.N))
else
r = zerO: exit sub ' P = -Q, R := O
end if
end if
t = modn(la * la - p.x - q.x)
r.y = modn(la * (p.x - t) - p.y)
r.x = t: if inverr then r = zerO
End Sub
'R:= multiple kP
Sub pmul (byref r as epnt, byref p as epnt, byval k as long)
dim as epnt s = zerO, q = p
while k
if k and 1 then padd (s, s, q)
if inverr then s = zerO: exit while
k shr= 1: padd (q, q, q)
wend
r = s
End Sub
'print point P with prefix f
Sub pprint (byref f as string, byref p as epnt)
dim as longint y = p.y
if isO (p) then
print f;" (0)"
else
if y > e.N - y then y -= e.N
print f;" (";str(p.x);",";y;")"
end if
End Sub
'initialize elliptic curve
Function ellinit (i() as long) as byte
dim as long a = i(0), b = i(1)
ellinit = 0: inverr = 0
e.N = i(2)
if (e.N < 5) or (e.N > mxN) then exit function
e.a = modn(a)
e.b = modn(b)
e.G.x = modn(i(3))
e.G.y = modn(i(4))
e.r = i(5)
if (e.r < 5) or (e.r > mxr) then exit function
print : ? "E: y^2 = x^3 + ";str(a);"x +";b;
print " (mod ";str(e.N);")"
pprint ("base point G", e.G)
print "order(G, E) ="; e.r
ellinit = -1
End Function
'signature primitive
Function signature (byval s as longint, byval f as long) as pair
dim as long c, d, u, u1
dim as pair sg
dim as epnt V
print : ? "signature computation"
do
do
u = 1 + int(rnd * (e.r - 1))
pmul (V, e.G, u)
c = modr(V.x)
loop while c = 0
u1 = exgcd (u, e.r)
d = modr(u1 * (f + modr(s * c)))
loop while d = 0
print "one-time u ="; u
pprint ("V = uG", V)
sg.a = c: sg.b = d
signature = sg
End Function
'verification primitive
Function verify (byref W as epnt, byval f as long, byref sg as pair) as byte
dim as long c = sg.a, d = sg.b
dim as long t, c1, h1, h2
dim as longint h
dim as epnt V, V2
verify = 0
'domain check
t = (c > 0) and (c < e.r)
t and= (d > 0) and (d < e.r)
if not t then exit function
print : ? "signature verification"
h = exgcd (d, e.r)
h1 = modr(f * h)
h2 = modr(c * h)
print "h1,h2 ="; h1;",";h2
pmul (V, e.G, h1)
pmul (V2, W, h2)
pprint ("h1G", V)
pprint ("h2W", V2)
padd (V, V, V2)
pprint ("+ =", V)
if isO (V) then exit function
c1 = modr(V.x)
print "c' ="; c1
verify = (c1 = c)
End Function
'digital signature on message hash f, error bit d
Sub ec_dsa (byval f as long, byval d as long)
dim as long i, s, t
dim as pair sg
dim as epnt W
'parameter check
t = (disc = 0)
t or= isO (e.G)
pmul (W, e.G, e.r)
t or= not isO (W)
t or= not ison (e.G)
if t then goto errmsg
print : ? "key generation"
s = 1 + int(rnd * (e.r - 1))
pmul (W, e.G, s)
print "private key s ="; s
pprint ("public key W = sG", W)
'next highest power of 2 - 1
t = e.r: i = 1
while i < 32
t or= t shr i: i shl= 1
wend
while f > t
f shr= 1: wend
print : ? "aligned hash "; hex(f)
sg = signature (s, f)
if inverr then goto errmsg
print "signature c,d ="; sg.a;",";sg.b
if d > 0 then
while d > t
d shr= 1: wend
f xor= d
print : ? "corrupted hash "; hex(f)
end if
t = verify (W, f, sg)
if inverr then goto errmsg
if t then
print "Valid" : ? "_____"
else
print "invalid" : ? "_______"
end if
exit sub
errmsg:
print "invalid parameter set"
print "_____________________"
End Sub
'main
dim as long d, f, t, eparm(5)
zerO.x = inf: zerO.y = 0
randomize timer
'Test vectors: elliptic curve domain parameters,
'short Weierstrass model y^2 = x^3 + ax + b (mod N)
' a, b, modulus N, base point G, order(G, E), cofactor
data 355, 671, 1073741789, 13693, 10088, 1073807281
data 0, 7, 67096021, 6580, 779, 16769911 ' 4
data -3, 1, 877073, 0, 1, 878159
data 0, 14, 22651, 63, 30, 151 ' 151
data 3, 2, 5, 2, 1, 5
'ecdsa may fail if...
'the base point is of composite order
data 0, 7, 67096021, 2402, 6067, 33539822 ' 2
'the given order is a multiple of the true order
data 0, 7, 67096021, 6580, 779, 67079644 ' 1
'the modulus is not prime (deceptive example)
data 0, 7, 877069, 3, 97123, 877069
'fails if the modulus divides the discriminant
data 39, 387, 22651, 95, 27, 22651
data 0, 0, 0
'Digital signature on message hash f,
'set d > 0 to simulate corrupted data
f = &h789ABCDE : d = 0
do
for t = 0 to 5
read eparm(t): next
if ellinit (eparm()) then
ec_dsa (f, d)
else
exit do
end if
loop
system
- Output:
(randomize 1, first set only)
E: y^2 = x^3 + 355x + 671 (mod 1073741789) base point G (13693, 10088) order(G, E) = 1073807281 key generation private key s = 509100772 public key W = sG (992563138, 238074938) aligned hash 789ABCDE signature computation one-time u = 571533488 V = uG (896670665, 183547995) signature c,d = 896670665, 728505276 signature verification h1,h2 = 667118700, 709185150 h1G (315367421, 343743703) h2W (1040319975,-262613483) + = (896670665, 183547995) c' = 896670665 Valid _____
Go
Since Go has an ECDSA package in its standard library which uses 'big integers', we use that rather than translating one of the reference implementations for a 'toy' version into Go.
package main
import (
"crypto/ecdsa"
"crypto/elliptic"
"crypto/rand"
"crypto/sha256"
"encoding/binary"
"fmt"
"log"
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func main() {
priv, err := ecdsa.GenerateKey(elliptic.P256(), rand.Reader)
check(err)
fmt.Println("Private key:\nD:", priv.D)
pub := priv.Public().(*ecdsa.PublicKey)
fmt.Println("\nPublic key:")
fmt.Println("X:", pub.X)
fmt.Println("Y:", pub.Y)
msg := "Rosetta Code"
fmt.Println("\nMessage:", msg)
hash := sha256.Sum256([]byte(msg)) // as [32]byte
hexHash := fmt.Sprintf("0x%x", binary.BigEndian.Uint32(hash[:]))
fmt.Println("Hash :", hexHash)
r, s, err := ecdsa.Sign(rand.Reader, priv, hash[:])
check(err)
fmt.Println("\nSignature:")
fmt.Println("R:", r)
fmt.Println("S:", s)
valid := ecdsa.Verify(&priv.PublicKey, hash[:], r, s)
fmt.Println("\nSignature verified:", valid)
}
- Output:
Sample run:
Private key: D: 25700608762903774973512323993645267346590725880891580901973011512673451968935 Public key: X: 37298454876588653961191059192981094503652951300904260069480867699946371240473 Y: 69073688506493709421315518164229531832022167466292360349457318041854718641652 Message: Rosetta Code Hash : 0xe6f9ed0d Signature: R: 91827099055706804696234859308003894767808769875556550819128270941615405955877 S: 20295707309473352071389945163735458699476300346398176659149368970668313772860 Signature verified: true
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();
}
- Output:
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 ...
Julia
module ToyECDSA
using SHA
import Base.in, Base.==, Base.+, Base.*
export ECDSA_Key, ECDSA_Public_Key, genkey, ECDSA_sign, isverifiedECDSA
# T will be BigInt in most applications
struct CurveFP{T}
p::T
a::T
b::T
CurveFP(p, a::T, b::T) where T <: Number = new{T}(p, a, b)
end
struct PointEC{T}
curve::CurveFP{T}
x::T
y::T
order::Union{Number, Nothing}
function PointEC(curve, x::T, y::T, order=nothing) where T <: Number
@assert((x, y) in curve)
new{T}(curve, x, y, order)
end
end
struct PointINF end
const INFINITY = PointINF()
function ==(point_a::PointEC, point_b::PointEC)
if point_a.curve == point_b.curve && point_a.x == point_b.x && point_a.y == point_b.y
return true
end
return false
end
function ==(curve_a::CurveFP, curve_b::CurveFP)
if curve_a.a == curve_b.a && curve_a.b == curve_b.b && curve_a.p == curve_b.p
return true
end
return false
end
+(point_a::PointINF, point_b::PointINF) = point_b
+(point_a::PointINF, point_b::PointEC) = point_b
+(point_a::PointEC, point_b::PointINF) = point_a
function +(point_a::PointEC, point_b::PointEC)
@assert(point_a.curve == point_b.curve)
if point_a.x == point_b.x
if (point_a.y + point_b.y) % point_a.curve.p == 0
return INFINITY
else
return double(point_a)
end
end
p = point_a.curve.p
λ = (point_a.y - point_b.y) * invmod(point_a.x - point_b.x, p)
xr = mod(λ * λ - point_a.x - point_b.x, p)
yr = mod(λ * (point_a.x - xr) - point_a.y, p)
return PointEC(point_a.curve, xr, yr, point_a.order)
end
*(point_a::PointINF, int_b::Number) = INFINITY
*(int_b::Number, point_a::PointINF) = INFINITY
*(int_b::Number, point_a::PointEC) = point_a * int_b
function *(point_a::PointEC, int_b::Number)
leftmost_bit(x) = big"2"^Int(trunc(log(2, x)))
if point_a.order != nothing
int_b %= point_a.order
end
if int_b == 0
return INFINITY
end
int_3b = 3 * int_b
negative_a = PointEC(point_a.curve, point_a.x, -point_a.y, point_a.order)
i = BigInt(leftmost_bit(int_3b) ÷ 2)
result = point_a
while i > 1
result = double(result)
if (int_3b & i) != 0 && (int_b & i) == 0
result += point_a
end
if (int_3b & i) == 0 && (int_b & i) != 0
result += negative_a
end
i ÷= 2
end
return result
end
in(z::Tuple, curve::CurveFP) = (z[2]^2 - (z[1]^3 + curve.a*z[1] + curve.b)) % curve.p == 0
in(x::Number,y::Number, curve::CurveFP) = (y^2 -(x^3 + curve.a*x + curve.b)) % curve.p == 0
in(p::PointEC, curve::CurveFP) = (p.y^2 - (p.x^3 + curve.a * p.x + curve.b)) % curve.p == 0
in(point::PointINF, curve::CurveFP) = true
double(point_a::PointINF) = INFINITY
function double(point_a::PointEC)
a, p = point_a.curve.a, point_a.curve.p
l = mod((3 * point_a.x^2 + a) * invmod(2 * point_a.y, p), p)
x3 = mod(l^2 - 2 * point_a.x, p)
y3 = mod(l * (point_a.x - x3) - point_a.y, p)
return PointEC(point_a.curve, x3, y3, point_a.order)
end
const secp256k1 = ( # use the Bitcoin ECDSA curve
p = big"0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F",
a = big"0x0",
b = big"0x7",
r = big"0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141",
Gx = big"0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798",
Gy = big"0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8",
)
@assert((secp256k1.Gy^2 - secp256k1.Gx^3 - 7) % secp256k1.p == 0)
function generatemultiplier(stdcurve)
return foldl((x, y) -> 16 * BigInt(x) + y, rand(0:16, ndigits(stdcurve.r - 1, base=16)))
end
struct ECDSA_Key
E::CurveFP
secret::BigInt
G::PointEC
r::BigInt
W::PointEC
end
struct ECDSA_Public_Key
E::CurveFP
G::PointEC
r::BigInt
W::PointEC
end
function genkey(curve=secp256k1) # default: use Bitcoin standard EC curve secp256k1
E = CurveFP(curve.p, curve.a, curve.b)
s = generatemultiplier(curve)
G = PointEC(E, curve.Gx, curve.Gy, curve.r)
W = s * G
return ECDSA_Key(E, s, G, curve.r, W)
end
aspublickey(k::ECDSA_Key) = ECDSA_Public_Key(k.E, k.G, k.r, k.W)
privatekey(k::ECDSA_Key) = k.secret
function ECDSA_sign(m::String, key::ECDSA_Key, digestfunction=sha256)
r, f = key.r, digestfunction(codeunits(m)) # f = H(m)
# order of curve points length must be >= sha digest length (in bytes)
@assert(ndigits(r, base=16) >= length(f))
c, d, bindigest = BigInt(0), BigInt(0), foldl((x, y) -> 16 * BigInt(x) + y, f)
while c == 0 || d == 0
u = generatemultiplier(secp256k1)
V = u * key.G
c = mod(V.x, r)
d = mod((invmod(u, r) * (bindigest + key.secret * c)), r)
end
return aspublickey(key), c, d
end
function isverifiedECDSA(m::String, publickey, c, d, digestfunction=sha256)
if 1 <= c < publickey.r && 1 <= d < publickey.r
r, f = publickey.r, digestfunction(codeunits(m))
h, bindigest = invmod(d, r), foldl((x, y) -> 16 * BigInt(x) + y, f)
h1, h2 = mod(bindigest * h, r), mod(c * h, r)
verifierpoint = h1 * publickey.G + h2 * publickey.W
return mod(verifierpoint.x, r) == c
end
return false
end
end # module
using .ToyECDSA
const key = genkey()
const msg = "Bill says this is an elliptic curve digital signature algorithm."
const altered = "Bill says this isn't an elliptic curve digital signature algorithm."
publickey, c, d = ECDSA_sign(msg, key)
println("ECDSA of message <$msg> verified: ", isverifiedECDSA(msg, publickey, c, d))
println("ECDSA of message <$altered> verified: ", isverifiedECDSA(altered, publickey, c, d))
- Output:
ECDSA of message <Bill says this is an elliptic curve digital signature algorithm.> verified: true ECDSA of message <Bill says this isn't an elliptic curve digital signature algorithm.> verified: false
Nim
import math, random, strformat
const
MaxN = 1073741789 # Maximum modulus.
MaxR = MaxN + 65536 # Maximum order "g".
Infinity = int64.high # Symbolic infinity.
type
Point = tuple[x, y: int64]
Curve = object
a, b: int64
n: int64
g: Point
r: int64
Pair = tuple[a, b: int64]
Parameters = tuple[a, b, n, gx, gy, r: int]
const ZerO: Point = (Infinity, 0i64)
type
InversionError = object of ValueError
InvalidParamError = object of ValueError
template `%`(a, n: int64): int64 =
## To simplify the writing.
floorMod(a, n)
proc exgcd(v, u: int64): int64 =
## Return 1/v mod u.
var u = u
var v = v
if v < 0: v += u
var r = 0i64
var s = 1i64
while v != 0:
let q = u div v
u = u mod v
swap u, v
r -= q * s
swap r, s
if u != 1:
raise newException(InversionError, "impossible inverse mod N, gcd = " & $u)
result = r
func discr(e: Curve): int64 =
## Return the discriminant of "e".
let c = e.a * e.a % e.n * e.a % e.n * 4
result = -16 * (e.b * e.b % e.n * 27 + c) % e.n
func isO(p: Point): bool =
## Return true if "p" is zero.
p.x == Infinity and p.y == 0
func isOn(e: Curve; p: Point): bool =
## Return true if "p" is on curve "e".
if p.isO: return true
let r = ((e.a + p.x * p.x) % e.n * p.x + e.b) % e.n
let s = p.y * p.y % e.n
result = r == s
proc add(e: Curve; p, q: Point): Point =
## Full Point addition.
if p.isO: return q
if q.isO: return p
var la: int64
if p.x != q.x:
la = (p.y - q.y) * exgcd(p.x - q.x, e.n) % e.n
elif p.y == q.y and p.y != 0:
la = (p.x * p.x % e.n * 3 + e.a) % e.n * exgcd(2 * p.y, e.n) % e.n
else:
return ZerO
result.x = (la * la - p.x - q.x) % e.n
result.y = (la * (p.x - result.x) - p.y) % e.n
proc mul(e: Curve; p: Point; k: int64): Point =
## Return "kp".
var q = p
var k = k
result = ZerO
while k != 0:
if (k and 1) != 0:
result = e.add(result, q)
q = e.add(q, q)
k = k shr 1
proc print(e: Curve; prefix: string; p: Point) =
## Print a point with a prefix.
var y = p.y
if p.isO:
echo prefix, " (0)"
else:
if y > e.n - y: y -= e.n
echo prefix, &" ({p.x}, {y})"
proc initCurve(params: Parameters): Curve =
## Initialize the curve.
result.n = params.n
if result.n notin 5..MaxN:
raise newException(ValueError, "invalid value for N: " & $result.n)
result.a = params.a.int64 % result.n
result.b = params.b.int64 % result.n
result.g.x = params.gx.int64 % result.n
result.g.y = params.gy.int64 % result.n
result.r = params.r
if result.r notin 5..MaxR:
raise newException(ValueError, "invalid value for r: " & $result.r)
echo &"\nE: y^2 = x^3 + {result.a}x + {result.b} (mod {result.n})"
result.print("base point G", result.g)
echo &"order(G, E) = {result.r}"
proc rnd(): float =
## Return a pseudorandom number in range [0..1[.
while true:
result = rand(1.0)
if result != 1: break
proc signature(e: Curve; s, f: int64): Pair =
## Compute the signature.
var
c, d = 0i64
u: int64
v: Point
echo "Signature computation"
while true:
while true:
u = 1 + int64(rnd() * float(e.r - 1))
v = e.mul(e.g, u)
c = v.x % e.r
if c != 0: break
d = exgcd(u, e.r) * (f + s * c % e.r) % e.r
if d != 0: break
echo "one-time u = ", u
e.print("V = uG", v)
result = (c, d)
proc verify(e: Curve; w: Point; f: int64; sg: Pair): bool =
## Verify a signature.
# Domain check.
if sg.a notin 1..<e.r or sg.b notin 1..<e.r:
return false
echo "\nsignature verification"
let h = exgcd(sg.b, e.r)
let h1 = f * h % e.r
let h2 = sg.a * h % e.r
echo &"h1, h2 = {h1}, {h2}"
var v = e.mul(e.g, h1)
let v2 = e.mul(w, h2)
e.print("h1G", v)
e.print("h2W", v2)
v = e.add(v, v2)
e.print("+ =", v)
if v.isO: return false
let c1 = v.x % e.r
echo "c’ = ", c1
result = c1 == sg.a
proc ecdsa(e: Curve; f: int64; d: int) =
## Build digital signature for message hash "f" with error bit "d".
# Parameter check.
var w = e.mul(e.g, e.r)
if e.discr() == 0 or e.g.isO or not w.isO or not e.isOn(e.g):
raise newException(InvalidParamError, "invalid parameter set")
echo "\nkey generation"
let s = 1 + int64(rnd() * float(e.r - 1))
w = e.mul(e.g, s)
echo "private key s = ", s
e.print("public key W = sG", w)
# Find next highest power of two minus one.
var t = e.r
var i = 1
while i < 64:
t = t or t shr i
i = i shl 1
var f = f
while f > t: f = f shr 1
echo &"\naligned hash {f:x}"
let sg = e.signature(s, f)
echo &"signature c, d = {sg.a}, {sg.b}"
var d = d
if d > 0:
while d > t: d = d shr 1
f = f xor d
echo &"\ncorrupted hash {f:x}"
echo if e.verify(w, f, sg): "Valid" else: "Invalid"
when isMainModule:
randomize()
# Test vectors: elliptic curve domain parameters,
# short Weierstrass model y^2 = x^3 + ax + b (mod N)
const Sets = [
# a, b, modulus N, base point G, order(G, E), cofactor
(355, 671, 1073741789, 13693, 10088, 1073807281),
( 0, 7, 67096021, 6580, 779, 16769911),
( -3, 1, 877073, 0, 1, 878159),
( 0, 14, 22651, 63, 30, 151),
( 3, 2, 5, 2, 1, 5),
# ECDSA may fail if...
# the base point is of composite order
( 0, 7, 67096021, 2402, 6067, 33539822),
# the given order is of composite order
( 0, 7, 67096021, 6580, 779, 67079644),
# the modulus is not prime (deceptive example)
( 0, 7, 877069, 3, 97123, 877069),
# fails if the modulus divides the discriminant
( 39, 387, 22651, 95, 27, 22651)
]
# Digital signature on message hash f,
# set d > 0 to simulate corrupted data.
let f = 0x789abcdei64
let d = 0
for s in Sets:
let e = initCurve(s)
try:
e.ecdsa(f, d)
except ValueError:
echo getCurrentExceptionMsg()
echo "——————————————"
- Output:
First set only.
E: y^2 = x^3 + 355x + 671 (mod 1073741789) base point G (13693, 10088) order(G, E) = 1073807281 key generation private key s = 136992620 public key W = sG (1015940633, 345577760) aligned hash 789abcde Signature computation one-time u = 183069978 V = uG (565985545, 303688609) signature c, d = 565985545, 1060545485 signature verification h1, h2 = 668000030, 564517193 h1G (801378704, -375265150) h2W (77432102, 301215724) + = (565985545, 303688609) c’ = 565985545 Valid ——————————————
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"
- Output:
Message: Rosetta Code Private Key : 50896950174101144529764022934807089163030534967278433074982207331912857967110 Public key : 98639220601877298644829563208621497413822596683110596662237522364057856411416 69976521993624103693270429074404825634551369215777879408776019358694823367135 Signature : r => 113328268998856048369024784426817827689451364968174533291969247274701793929451 s => 102496515866716695113707075780391660331998173218829535655149484671019624453603 Signature verified.
Phix
requires(64) enum X, Y -- rational ec point enum A, B, N, G, R -- elliptic curve parameters -- also signature pair(A,B) constant mxN = 1073741789 -- maximum modulus constant mxr = 1073807325 -- max order G = mxN + 65536 constant inf = -2147483647 -- symbolic infinity sequence e = {0,0,0,{0,0},0} -- single global curve constant zerO = {inf,0} -- point at infinity zerO bool inverr -- impossible inverse mod N function exgcd(atom v, u) -- return mod(v^-1, u) atom q, t, r = 0, s = 1 if v<0 then v += u end if while v do q = floor(u/v) t = u-q*v u = v v = t t = r-q*s r = s s = t end while if u!=1 then printf(1," impossible inverse mod N, gcd = %d\n",{u}) inverr = true end if return r end function function modn(atom a) -- return mod(a, N) a = mod(a,e[N]) if a<0 then a += e[N] end if return a end function function modr(atom a) -- return mod(a, r) a = mod(a,e[R]) if a<0 then a += e[R] end if return a end function function disc() -- return the discriminant of E atom a = e[A], b = e[B], c = 4*modn(a*modn(a*a)) return modn(-16*(c+27*modn(b*b))) end function function isO(sequence p) -- return true if P = zerO return (p[X]=inf and p[Y]=0) end function function ison(sequence p) -- return true if P is on curve E atom r = 0, s = 0 if not isO(p) then r = modn(e[B]+p[X]*modn(e[A]+p[X]*p[X])) s = modn(p[Y]*p[Y]) end if return (r=s) end function procedure pprint(string f, sequence p) -- print point P with prefix f if isO(p) then printf(1,"%s (0)\n",{f}) else atom y = p[Y] if y>e[N]-y then y -= e[N] end if printf(1,"%s (%d,%d)\n",{f,p[X],y}) end if end procedure function padd(sequence p, q) -- full ec point addition atom la, t if isO(p) then return q end if if isO(q) then return p end if if p[X]!=q[X] then -- R := P + Q t = p[Y]-q[Y] la = modn(t*exgcd(p[X]-q[X], e[N])) else -- P = Q, R := 2P if (p[Y]=q[Y]) and (p[Y]!=0) then t = modn(3*modn(p[X]*p[X])+e[A]) la = modn(t*exgcd(2*p[Y], e[N])) else return zerO -- P = -Q, R := O end if end if t = modn(la*la-p[X]-q[X]) sequence r = deep_copy(zerO) r[Y] = modn(la*(p[X]-t)-p[Y]) r[X] = t if inverr then r = zerO end if return r end function function pmul(sequence p, atom k) -- R:= multiple kP sequence s = zerO, q = p while k do if and_bits(k,1) then s = padd(s, q) end if if inverr then s = zerO; exit end if k = floor(k/2) q = padd(q, q) end while return s end function function ellinit(sequence i) -- initialize elliptic curve atom a = i[1], b = i[2] inverr = false e[N] = i[3] if (e[N]<5) or (e[N]>mxN) then return 0 end if e[A] = modn(a) e[B] = modn(b) e[G][X] = modn(i[4]) e[G][Y] = modn(i[5]) e[R] = i[6] if (e[R]<5) or (e[R]>mxr) then return 0 end if printf(1,"E: y^2 = x^3 + %dx + %d (mod %d)\n",{a,b,e[N]}) pprint("base point G", e[G]) printf(1,"order(G, E) = %d\n",{e[R]}) return -1 end function function signature(atom s, f) -- signature primitive atom c, d, u, u1 sequence V printf(1,"signature computation\n") while true do while true do -- u = rand(e[R]-1) u = 571533488 -- match FreeBASIC output -- u = 605163545 -- match C output V = pmul(e[G], u) c = modr(V[X]) if c!=0 then exit end if end while u1 = exgcd(u, e[R]) d = modr(u1*(f+modr(s*c))) if d!=0 then exit end if end while printf(1,"one-time u = %d\n",u) pprint("V = uG", V) return {c,d} end function function verify(sequence W, atom f, sequence sg) -- verification primitive atom c = sg[A], d = sg[B], t, c1, h1, h2, h sequence V, V2 --domain check t = (c>0) and (c<e[R]) t = t and (d>0) and (d<e[R]) if not t then return 0 end if printf(1,"\nsignature verification\n") h = exgcd(d, e[R]) h1 = modr(f*h) h2 = modr(c*h) printf(1,"h1,h2 = %d,%d\n",{h1,h2}) V = pmul(e[G], h1) V2 = pmul(W, h2) pprint("h1G", V) pprint("h2W", V2) V = padd(V, V2) pprint("+ =", V) if isO(V) then return 0 end if c1 = modr(V[X]) printf(1,"c' = %d\n",c1) return (c1=c) end function procedure errmsg() printf(1,"invalid parameter set\n") printf(1,"_____________________\n") end procedure procedure ec_dsa(atom f, d) -- digital signature on message hash f, error bit d atom i, s, t sequence sg, W --parameter check t = (disc()=0) t = t or isO(e[G]) W = pmul(e[G], e[R]) t = t or not isO(W) t = t or not ison(e[G]) if t then errmsg() return end if puts(1,"\nkey generation\n") -- s = rand(e[R] - 1) s = 509100772 -- match FreeBASIC output -- s = 1343570 -- match C output W = pmul(e[G], s) printf(1,"private key s = %d\n",{s}) pprint("public key W = sG", W) --next highest power of 2 - 1 t = e[R] i = 1 while i<32 do t = or_bits(t,floor(t/power(2,i))) i *= 2 end while while f>t do f = floor(f/2) end while printf(1,"\naligned hash %x\n\n",{f}) sg = signature(s, f) if inverr then errmsg() return end if printf(1,"signature c,d = %d,%d\n",sg) if d>0 then while d>t do d = floor(d/2) end while f = xor_bits(f,d) printf(1,"corrupted hash %x\n",{f}) end if t = verify(W, f, sg) if inverr then errmsg() return end if if t then printf(1,"Valid\n_____\n") else printf(1,"invalid\n_______\n") end if end procedure --Test vectors: elliptic curve domain parameters, --short Weierstrass model y^2 = x^3 + ax + b (mod N) constant tests = { -- a, b, modulus N, base point G, order(G, E), cofactor {355, 671, 1073741789, 13693, 10088, 1073807281}, { 0, 7, 67096021, 6580, 779, 16769911}, -- 4 { -3, 1, 877073, 0, 1, 878159}, { 0, 14, 22651, 63, 30, 151}, -- 151 { 3, 2, 5, 2, 1, 5}, --ecdsa may fail if... --the base point is of composite order { 0, 7, 67096021, 2402, 6067, 33539822}, -- 2 --the given order is a multiple of the true order { 0, 7, 67096021, 6580, 779, 67079644}, -- 1 --the modulus is not prime (deceptive example) { 0, 7, 877069, 3, 97123, 877069}, --fails if the modulus divides the discriminant { 39, 387, 22651, 95, 27, 22651}} --Digital signature on message hash f, --set d > 0 to simulate corrupted data atom f = #789ABCDE, d = 0 --for i=1 to length(tests) do for i=1 to 1 do if not ellinit(tests[i]) then exit end if ec_dsa(f, d) end for
- Output:
Note the above only performs tests[1], and assigns literal values in place of rand(), in order to exactly match the FreeBASIC/C output.
E: y^2 = x^3 + 355x + 671 (mod 1073741789) base point G (13693,10088) order(G, E) = 1073807281 key generation private key s = 509100772 public key W = sG (992563138,238074938) aligned hash 789ABCDE signature computation one-time u = 571533488 V = uG (896670665,183547995) signature c,d = 896670665,728505276 signature verification h1,h2 = 667118700,709185150 h1G (315367421,343743703) h2W (1040319975,-262613483) + = (896670665,183547995) c' = 896670665 Valid _____
Python
from collections import 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()
- Output:
E: y^2 = x^3 + 0x + 7 (mod 115792089237316195423570985008687907853269984665640564039457584007908834671663) base point G(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) order(G, E) = 115792089237316195423570985008687907852837564279074904382605163141518161494337 Generating keys private key s = 82303800204859706726056108314364152573031639016623313275752312395463491677949 public key W = sG (114124711379379930034967744084997669072230999039555829167372300365264253950871, 3360309271473421344413510933284750262871091919289744186713753032606174460281) signature (b'hello world', priv) = (c,d) = 1863861291106464538398514909960950901792292936913306559193916523058660671107, 62559673485398527884210590428202308573799357197699075411868464552455123994884 verify_signature(pub, b'hello world', signature) = True verify_signature(pub, b'hello planet', signature) = False
Raku
(formerly Perl 6)
module EC {
use FiniteField;
our class Point {
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 }
multi infix:<+>(Point $A, Point:U) is export { $A }
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 {
return Point.new: $_, $λ*($A.x - $_) - $A.y;
}
}
multi infix:<*>(0, Point ) is export { Point }
multi infix:<*>(1, Point $p) is export { $p }
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;
module ECDSA {
use Digest::SHA256::Native;
our class Signature {
has UInt ($.c, $.d);
multi method new(Str $message, UInt :$private-key) {
my $z = :16(sha256-hex $message) % $*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;
my $*modulus = my $*p = 1073741789;
my $*G = EC::Point.new: 13693, 10088;
my $*n = 1073807281;
die "G is not of order n" if $*n*$*G;
my $private-key = ^$*n .pick;
my $public-key = $private-key*$*G;
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>";
}
- Output:
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>
Wren
As we don't have a signed 64 bit integer type, we use BigInt instead where needed.
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
var modn = Fn.new { |a|
var b = a.copy()
b = b % e.N
if (b < 0) b = b + e.N
return b
}
// returns mod(a, r), a is a BigInt
var modr = Fn.new { |a|
var b = a.copy()
b = b % e.r
if (b < 0) b = b + e.r
return b
}
// returns the discriminant of E
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)
var isZero = Fn.new { |p| p.x == inf && p.y == 0 }
// return true if P is on curve E
var isOn = Fn.new { |p|
var r = 0
var s = 0
if (!isZero.call(p)) {
r = modn.call(p.x * modn.call(p.x * p.x + e.a) + e.b).toSmall
s = modn.call(p.y * p.y).toSmall
}
return r == s
}
// full ec point addition
var padd = Fn.new { |p, q|
var la = BigInt.zero
var t = BigInt.zero
if (isZero.call(p)) return Epnt.new(q.x, q.y)
if (isZero.call(q)) return Epnt.new(p.x, p.y)
if (p.x != q.x) { // R = P + Q
t = p.y - q.y
la = modn.call(t * exgcd.call((p.x - q.x).toSmall, e.N.toSmall))
} else { // P = Q, R = 2P
if (p.y == q.y && p.y != 0) {
t = modn.call(modn.call(p.x * p.x) * 3 + e.a)
la = modn.call(t * exgcd.call((p.y * 2).toSmall, e.N.toSmall))
} else {
return Epnt.new(inf, BigInt.zero) // P = -Q, R = O
}
}
if (inverr) return Epnt.new(inf, BigInt.zero)
t = modn.call(la * la - p.x - q.x)
return Epnt.new(t, modn.call(la * (p.x - t) - p.y))
}
// R = multiple 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,
// short Weierstrass model y^2 = x^3 + ax + b (mod N)
var sets = [
// a, b, modulus N, base point G, order(G, E), cofactor
[355, 671, 1073741789, 13693, 10088, 1073807281],
[ 0, 7, 67096021, 6580, 779, 16769911], // 4
[ -3, 1, 877073, 0, 1, 878159],
[ 0, 14, 22651, 63, 30, 151], // 151
[ 3, 2, 5, 2, 1, 5],
// ecdsa may fail if...
// the base point is of composite order
[ 0, 7, 67096021, 2402, 6067, 33539822], // 2
// the given order is a multiple of the true order
[ 0, 7, 67096021, 6580, 779, 67079644], // 1
// the modulus is not prime (deceptive example)
[ 0, 7, 877069, 3, 97123, 877069],
// fails if the modulus divides the discriminant
[ 39, 387, 22651, 95, 27, 22651]
]
// Digital signature on message hash f,
// set d > 0 to simulate corrupted data
var f = 0x789abcde
var d = 0
for (s in sets) {
if (ellinit.call(s)) {
ec_dsa.call(f, d)
} else {
break
}
}
- Output:
Sample output - first set only.
E: y^2 = x^3 + 355x + 671 (mod 1073741789) base point G (13693, 10088) order(G, E) = 1073807281 key generation private key s = 121877962 public key W = sG (320982025, 402911160) aligned hash 789abcde signature computation one-time u = 899439563 V = uG (105563482, 310387297) signature c, d = 105563482, 270442619 signature verification h1, h2 = 123954960, 653133035 h1G (623038071, 220475456) h2W (893517020, -249809739) + = (105563482, 310387297) c' = 105563482 Valid