Elliptic Curve Digital Signature Algorithm
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>
Last updated