Elliptic Curve Digital Signature Algorithm: Difference between revisions
Elliptic Curve Digital Signature Algorithm (view source)
Revision as of 16:53, 28 November 2023
, 5 months ago→{{header|Wren}}: Minor tidy
(use superscripts) |
m (→{{header|Wren}}: Minor tidy) |
||
(7 intermediate revisions by 2 users not shown) | |||
Line 485:
Valid
_____
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <random>
#include <stdexcept>
#include <string>
#include <vector>
const int32_t MAX_MODULUS = 1073741789;
const int32_t MAX_ORDER_G = MAX_MODULUS + 65536;
std::random_device random;
std::mt19937 generator(random());
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
class Point {
public:
Point(const int64_t& x, const int64_t& y) : x(x), y(y) {}
Point() : x(0),y(0) {}
bool isZero() {
return x == INT64_MAX && y == 0;
}
int64_t x, y;
};
const Point ZERO_POINT(INT64_MAX, 0);
class Pair {
public:
Pair(const int64_t& a, const int64_t& b) : a(a), b(b) {}
const int64_t a, b;
};
class Parameter {
public:
Parameter(const int64_t& a, const int64_t& b, const int64_t& n, const Point& g, const int64_t& r)
: a(a), b(b), n(n), g(g), r(r) {}
const int64_t a, b, n;
const Point g;
const int64_t r;
};
int64_t signum(const int64_t& x) {
return ( x < 0 ) ? -1 : ( x > 0 ) ? 1 : 0;
}
int64_t floor_mod(const int64_t& num, const int64_t& mod) {
const int64_t signs = ( signum(num % mod) == -signum(mod) ) ? 1 : 0;
return ( num % mod ) + signs * mod;
}
int64_t floor_div(const int64_t& number, const int64_t& modulus) {
const int32_t signs = ( signum(number % modulus) == -signum(modulus) ) ? 1 : 0;
return ( number / modulus ) - signs;
}
// Return 1 / aV modulus aU
int64_t extended_GCD(int64_t v, int64_t u) {
if ( v < 0 ) {
v += u;
}
int64_t result = 0;
int64_t s = 1;
while ( v != 0 ) {
const int64_t quotient = floor_div(u, v);
u = floor_mod(u, v);
std::swap(u, v);
result -= quotient * s;
std::swap(result, s);
}
if ( u != 1 ) {
throw std::runtime_error("Cannot inverse modulo N, gcd = " + u);
}
return result;
}
class Elliptic_Curve {
public:
Elliptic_Curve(const Parameter& parameter) {
n = parameter.n;
if ( n < 5 || n > MAX_MODULUS ) {
throw std::invalid_argument("Invalid value for modulus: " + n);
}
a = floor_mod(parameter.a, n);
b = floor_mod(parameter.b, n);
g = parameter.g;
r = parameter.r;
if ( r < 5 || r > MAX_ORDER_G ) {
throw std::invalid_argument("Invalid value for the order of g: " + r);
}
std::cout << std::endl;
std::cout << "Elliptic curve: y^2 = x^3 + " << a << "x + " << b << " (mod " << n << ")" << std::endl;
print_point_with_prefix(g, "base point G");
std::cout << "order(G, E) = " << r << std::endl;
}
Point add(Point p, Point q) {
if ( p.isZero() ) {
return q;
}
if ( q.isZero() ) {
return p;
}
int64_t la;
if ( p.x != q.x ) {
la = floor_mod(( p.y - q.y ) * extended_GCD(p.x - q.x, n), n);
} else if ( p.y == q.y && p.y != 0 ) {
la = floor_mod(floor_mod(floor_mod(p.x * p.x, n) * 3 + a, n) * extended_GCD(2 * p.y, n), n);
} else {
return ZERO_POINT;
}
const int64_t x_coord = floor_mod(la * la - p.x - q.x, n);
const int64_t y_coord = floor_mod(la * ( p.x - x_coord ) - p.y, n);
return Point(x_coord, y_coord);
}
Point multiply(Point point, int64_t k) {
Point result = ZERO_POINT;
while ( k != 0 ) {
if ( ( k & 1 ) == 1 ) {
result = add(result, point);
}
point = add(point, point);
k >>= 1;
}
return result;
}
bool contains(Point point) {
if ( point.isZero() ) {
return true;
}
int64_t r = floor_mod(floor_mod(a + point.x * point.x, n) * point.x + b, n);
int64_t s = floor_mod(point.y * point.y, n);
return r == s;
}
uint64_t discriminant() {
const int64_t constant = 4 * floor_mod(a * a, n) * floor_mod(a, n);
return floor_mod(-16 * ( floor_mod(b * b, n) * 27 + constant ), n);
}
void print_point_with_prefix(Point point, const std::string& prefix) {
int64_t y = point.y;
if ( point.isZero() ) {
std::cout << prefix + " (0)" << std::endl;
} else {
if ( y > n - y ) {
y -= n;
}
std::cout << prefix + " (" << point.x << ", " << y << ")" << std::endl;
}
}
int64_t a, b, n, r;
Point g;
};
double random_number() {
return distribution(generator);
}
Pair signature(Elliptic_Curve curve, const int64_t& s, const int64_t& f) {
int64_t c, d, u;
Point v;
while ( true ) {
while ( true ) {
u = 1 + (int64_t) ( random_number() * (double) ( curve.r - 1 ) );
v = curve.multiply(curve.g, u);
c = floor_mod(v.x, curve.r);
if ( c != 0 ) {
break;
}
}
d = floor_mod(extended_GCD(u, curve.r) * floor_mod(f + s * c, curve.r), curve.r);
if ( d != 0 ) {
break;
}
}
std::cout << "one-time u = " << u << std::endl;
curve.print_point_with_prefix(v, "V = uG");
return Pair(c, d);
}
bool verify(Elliptic_Curve curve, Point point, const int64_t& f, const Pair& signature) {
if ( signature.a < 1 || signature.a >= curve.r || signature.b < 1 || signature.b >= curve.r ) {
return false;
}
std::cout << "\n" << "signature verification" << std::endl;
const int64_t h = extended_GCD(signature.b, curve.r);
const int64_t h1 = floor_mod(f * h, curve.r);
const int64_t h2 = floor_mod(signature.a * h, curve.r);
std::cout << "h1, h2 = " << h1 << ", " << h2 << std::endl;
Point v = curve.multiply(curve.g, h1);
Point v2 = curve.multiply(point, h2);
curve.print_point_with_prefix(v, "h1G");
curve.print_point_with_prefix(v2, "h2W");
v = curve.add(v, v2);
curve.print_point_with_prefix(v, "+ =");
if ( v.isZero() ) {
return false;
}
int64_t c1 = floor_mod(v.x, curve.r);
std::cout << "c' = " << c1 << std::endl;
return c1 == signature.a;
}
// Build the digital signature for a message using the hash aF with error bit aD
void ecdsa(Elliptic_Curve curve, int64_t f, int32_t d) {
Point point = curve.multiply(curve.g, curve.r);
if ( curve.discriminant() == 0 || curve.g.isZero() || ! point.isZero() || ! curve.contains(curve.g) ) {
throw std::invalid_argument("Invalid parameter in the method ecdsa");
}
std::cout << "\n" << "key generation" << std::endl;
const int64_t s = 1 + (int64_t) ( random_number() * (double) ( curve.r - 1 ) );
point = curve.multiply(curve.g, s);
std::cout << "private key s = " << s << std::endl;
curve.print_point_with_prefix(point, "public key W = sG");
// Find the next highest power of two minus one.
int64_t t = curve.r;
int64_t i = 1;
while ( i < 64 ) {
t |= t >> i;
i <<= 1;
}
while ( f > t ) {
f >>= 1;
}
std::cout << "\n" << "aligned hash " << std::hex << std::setfill('0') << std::setw(8) << f
<< std::dec << std::endl;
const Pair signature_pair = signature(curve, s, f);
std::cout << "signature c, d = " << signature_pair.a << ", " << signature_pair.b << std::endl;
if ( d > 0 ) {
while ( d > t ) {
d >>= 1;
}
f ^= d;
std::cout << "\n" << "corrupted hash " << std::hex << std::setfill('0') << std::setw(8) << f
<< std::dec << std::endl;
}
std::cout << ( verify(curve, point, f, signature_pair) ? "Valid" : "Invalid" ) << std::endl;
std::cout << "-----------------" << std::endl;
}
int main() {
// Test parameters for elliptic curve digital signature algorithm,
// using the short Weierstrass model: y^2 = x^3 + ax + b (mod N).
//
// Parameter: a, b, modulus N, base point G, order of G in the elliptic curve.
const std::vector<Parameter> parameters {
Parameter( 355, 671, 1073741789, Point(13693, 10088), 1073807281 ),
Parameter( 0, 7, 67096021, Point( 6580, 779), 16769911 ),
Parameter( -3, 1, 877073, Point( 0, 1), 878159 ),
Parameter( 0, 14, 22651, Point( 63, 30), 151 ),
Parameter( 3, 2, 5, Point( 2, 1), 5 ) };
// Parameters which cause failure of the algorithm for the given reasons
// the base point is of composite order
// Parameter( 0, 7, 67096021, Point( 2402, 6067), 33539822 ),
// the given order is of composite order
// Parameter( 0, 7, 67096021, Point( 6580, 779), 67079644 ),
// the modulus is not prime (deceptive example)
// Parameter( 0, 7, 877069, Point( 3, 97123), 877069 ),
// fails if the modulus divides the discriminant
// Parameter( 39, 387, 22651, Point( 95, 27), 22651 ) );
const int64_t f = 0x789abcde; // The message's digital signature hash which is to be verified
const int32_t d = 0; // Set d > 0 to simulate corrupted data
for ( const Parameter& parameter : parameters ) {
Elliptic_Curve elliptic_curve(parameter);
ecdsa(elliptic_curve, f, d);
}
}
</syntaxhighlight>
{{ out }}
<pre>
Elliptic curve: y^2 = x^3 + 355x + 671 (mod 1073741789)
base point G (13693, 10088)
order(G, E) = 1073807281
key generation
private key s = 1024325479
public key W = sG (717544485, -463545080)
aligned hash 789abcde
one-time u = 76017594
V = uG (231970881, 178344325)
signature c, d = 231970881, 762656688
signature verification
h1, h2 = 205763719, 179248000
h1G (757236523, -510136355)
h2W (118269957, 451962485)
+ = (231970881, 178344325)
c' = 231970881
Valid
-----------------
// continues ...
</pre>
Line 928 ⟶ 1,259:
// using the short Weierstrass model: y^2 = x^3 + ax + b (mod N).
//
// Parameter: a, b, modulus N, base point G, order
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);
}
Line 959 ⟶ 1,290:
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");
Line 973 ⟶ 1,305:
long i = 1;
while ( i < 64 ) {
i <<= 1;
}
Line 988 ⟶ 1,320:
if ( d > 0 ) {
while ( d > t ) {
}
System.out.println(System.lineSeparator() + "corrupted hash " + String.format("%08x", f));
}
Line 1,014 ⟶ 1,346:
v = aCurve.add(v, v2);
aCurve.printPointWithPrefix(v, "+ =");
if ( v.isZero() ) {
return false;
Line 1,050 ⟶ 1,383:
}
// Return 1 / aV
private static long extendedGCD(long aV, long aU) {
if ( aV < 0 ) {
Line 1,056 ⟶ 1,389:
}
long
long s = 1;
while ( aV != 0 ) {
final long
aU = Math.floorMod(aU, aV);
long temp = aU; aU = aV; aV = temp;
temp =
}
Line 1,069 ⟶ 1,402:
throw new AssertionError("Cannot inverse modulo N, gcd = " + aU);
}
return
}
Line 1,086 ⟶ 1,419:
a = Math.floorMod(aParameter.a, n);
b = Math.floorMod(aParameter.b, n);
r = aParameter.r;
Line 1,111 ⟶ 1,442:
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(
} else {
return Point.ZERO;
Line 1,124 ⟶ 1,455:
}
public Point multiply(Point aPoint, long aK) {
Point result = Point.ZERO;
while ( aK != 0 ) {
if ( ( aK & 1 )
result = add(result, aPoint);
}
Line 1,142 ⟶ 1,473:
}
final long r = Math.floorMod
final long s = Math.floorMod(aPoint.y * aPoint.y, n);
return r == s;
}
Line 1,164 ⟶ 1,495:
}
private final long a, b, n, r;
private final Point g;
}
Line 1,189 ⟶ 1,520:
private static record Pair(long a, long b) {}
private static record Parameter(long a, long b, long n,
private static final int MAX_MODULUS = 1073741789;
Line 2,361 ⟶ 2,692:
=={{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 {
multi method new(Str $message, UInt :$private-key) {
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
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
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
with
The private key is : 405586338
The public key is at : (457744420, 236326628)
The
The
ok 1 - good signature for <Show me the monKey>
=={{header|Wren}}==
Line 2,473 ⟶ 2,811:
{{libheader|Wren-math}}
As we don't have a signed 64 bit integer type, we use BigInt instead where needed.
<syntaxhighlight lang="
import "./big" for BigInt
import "./fmt" for Fmt
import "./math" for Boolean
import "random" for Random
|