Rosetta Code

Elliptic Curve Digital Signature Algorithm: Difference between revisions

Page Discussion

Elliptic Curve Digital Signature Algorithm (view source)

Revision as of 00:54, 14 March 2020

14 bytes added ,  4 years ago
Rename Perl 6 -> Raku, alphabetize, minor clean-up
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)
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 110:
 
__TOC__
 
 
=={{header|C}}==
Line 487 ⟶ 486:
_____
</pre>
 
 
=={{header|FreeBASIC}}==
Line 1,110 ⟶ 1,108:
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
</pre>
 
=={{header|Perl 6}}==
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.
<lang perl6>#!/usr/bin/env perl6
 
use Digest::SHA256::Native;
 
# Following data taken from the C entry
our (\A,\B,\P,\O,\Gx,\Gy) = (355, 671, 1073741789, 1073807281, 13693, 10088);
 
#`{ Following data taken from the Julia entry; 256-bit; tested
our (\A,\B,\P,\O,\Gx,\Gy) = (0, 7, # https://en.bitcoin.it/wiki/Secp256k1
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8); # }
 
role Horizon { method gist { 'EC Point at horizon' } }
 
class Point { # modified from the Elliptic_curve_arithmetic entry
has ($.x, $.y); # handle modular arithmetic only
multi method new( \x, \y ) { self.bless(:x, :y) }
method gist { "EC Point at x=$.x, y=$.y" }
method isOn { modP(B + $.x * modP(A+$.x²)) == modP($.y²) }
sub modP ($a is copy) { ( $a %= P ) < 0 ?? ($a += P) !! $a }
}
 
multi infix:<⊞>(Point \p, Point \q) {
my \λ = $; # slope
if p.x ~~ q.x and p.y ~~ q.y {
return Horizon if p.y == 0 ;
λ = (3*p.x²+ A) * mult_inv(2*p.y, :modulo(P))
} else {
λ = (p.y - q.y) * mult_inv(p.x - q.x, :modulo(P))
}
my \xr = (λ²- p.x - q.x);
my \yr = (λ*(p.x - xr) - p.y);
return Point.bless: x => xr % P, y => yr % P
}
 
multi infix:<⊠>(Int \n, Point \p) {
return 0 if n == 0 ;
return p if n == 1 ;
return p ⊞ ((n-1) ⊠ p ) if n % 2 == 1 ;
return ( n div 2 ) ⊠ ( p ⊞ p )
}
 
sub mult_inv($n, :$modulo) { # rosettacode.org/wiki/Modular_inverse#Perl_6
my ($c, $d, $uc, $vd, $vc, $ud, $q) = $n % $modulo, $modulo, 1, 1, 0, 0, 0;
while $c != 0 {
($q, $c, $d) = ($d div $c, $d % $c, $c);
($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc);
}
return $ud % $modulo;
}
 
class Signature {
 
has ($.n, Point $.G); # Order and Generator point
 
method generate_signature(Int \private_key, Str \msg) {
my \z = :16(sha256-hex msg) % $.n; # self ref: Blob.list.fmt("%02X",'')
loop ( my $k = my $s = my $r = 0 ; $s == 0 ; ) {
loop ( $r = $s = 0 ; $r == 0 ; ) {
$r = (( $k = (1..^$.n).roll ) ⊠ $.G).x % $.n;
}
$s = ((z + $r*private_key) * mult_inv $k, :modulo($.n)) % $.n;
}
return $r, $s, private_key ⊠ $.G ;
}
 
method verify_signature(\msg, \r, \s, \public_key) {
my \z = :16(sha256-hex msg) % $.n;
my \w = mult_inv s, :modulo($.n);
my (\u1,\u2) = (z*w, r*w).map: { $_ % $.n }
my \p = (u1 ⊠ $.G ) ⊞ (u2 ⊠ public_key);
return (p.x % $.n) == (r % $.n)
}
}
 
print "The Curve E is : ";
"𝑦² = 𝑥³ + %s 𝑥 + %s (mod %s) \n".printf(A,B,P);
"with Generator G at : (%s,%s)\n".printf(Gx,Gy);
my $ec = Signature.new: n => O, G => Point.new: x => Gx, y => Gy ;
say "Order(G, E) is : ", O;
say "Is G ∈ E ? : ", $ec.G.isOn;
say "Message : ", my \message = "Show me the monKey";
say "The private key dA is : ", my \dA = (1..^O).roll;
my ($r, $s, \Qa) = $ec.generate_signature(dA, message);
say "The public key Qa is : ", Qa;
say "Is Qa ∈ E ? : ", Qa.isOn;
say "Is signature valid? : ", $ec.verify_signature(message, $r, $s, Qa);
say "Message (Tampered) : ", my \altered = "Show me the money";
say "Is signature valid? : ", $ec.verify_signature(altered, $r, $s, Qa)</lang>
{{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>
 
Line 1,541 ⟶ 1,432:
Valid
_____
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
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.
<lang perl6>#!/usr/bin/env perl6
 
use Digest::SHA256::Native;
 
# Following data taken from the C entry
our (\A,\B,\P,\O,\Gx,\Gy) = (355, 671, 1073741789, 1073807281, 13693, 10088);
 
#`{ Following data taken from the Julia entry; 256-bit; tested
our (\A,\B,\P,\O,\Gx,\Gy) = (0, 7, # https://en.bitcoin.it/wiki/Secp256k1
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8); # }
 
role Horizon { method gist { 'EC Point at horizon' } }
 
class Point { # modified from the Elliptic_curve_arithmetic entry
has ($.x, $.y); # handle modular arithmetic only
multi method new( \x, \y ) { self.bless(:x, :y) }
method gist { "EC Point at x=$.x, y=$.y" }
method isOn { modP(B + $.x * modP(A+$.x²)) == modP($.y²) }
sub modP ($a is copy) { ( $a %= P ) < 0 ?? ($a += P) !! $a }
}
 
multi infix:<⊞>(Point \p, Point \q) {
my \λ = $; # slope
if p.x ~~ q.x and p.y ~~ q.y {
return Horizon if p.y == 0 ;
λ = (3*p.x²+ A) * mult_inv(2*p.y, :modulo(P))
} else {
λ = (p.y - q.y) * mult_inv(p.x - q.x, :modulo(P))
}
my \xr = (λ²- p.x - q.x);
my \yr = (λ*(p.x - xr) - p.y);
return Point.bless: x => xr % P, y => yr % P
}
 
multi infix:<⊠>(Int \n, Point \p) {
return 0 if n == 0 ;
return p if n == 1 ;
return p ⊞ ((n-1) ⊠ p ) if n % 2 == 1 ;
return ( n div 2 ) ⊠ ( p ⊞ p )
}
 
sub mult_inv($n, :$modulo) { # rosettacode.org/wiki/Modular_inverse#Perl_6
my ($c, $d, $uc, $vd, $vc, $ud, $q) = $n % $modulo, $modulo, 1, 1, 0, 0, 0;
while $c != 0 {
($q, $c, $d) = ($d div $c, $d % $c, $c);
($uc, $vc, $ud, $vd) = ($ud - $q*$uc, $vd - $q*$vc, $uc, $vc);
}
return $ud % $modulo;
}
 
class Signature {
 
has ($.n, Point $.G); # Order and Generator point
 
method generate_signature(Int \private_key, Str \msg) {
my \z = :16(sha256-hex msg) % $.n; # self ref: Blob.list.fmt("%02X",'')
loop ( my $k = my $s = my $r = 0 ; $s == 0 ; ) {
loop ( $r = $s = 0 ; $r == 0 ; ) {
$r = (( $k = (1..^$.n).roll ) ⊠ $.G).x % $.n;
}
$s = ((z + $r*private_key) * mult_inv $k, :modulo($.n)) % $.n;
}
return $r, $s, private_key ⊠ $.G ;
}
 
method verify_signature(\msg, \r, \s, \public_key) {
my \z = :16(sha256-hex msg) % $.n;
my \w = mult_inv s, :modulo($.n);
my (\u1,\u2) = (z*w, r*w).map: { $_ % $.n }
my \p = (u1 ⊠ $.G ) ⊞ (u2 ⊠ public_key);
return (p.x % $.n) == (r % $.n)
}
}
 
print "The Curve E is : ";
"𝑦² = 𝑥³ + %s 𝑥 + %s (mod %s) \n".printf(A,B,P);
"with Generator G at : (%s,%s)\n".printf(Gx,Gy);
my $ec = Signature.new: n => O, G => Point.new: x => Gx, y => Gy ;
say "Order(G, E) is : ", O;
say "Is G ∈ E ? : ", $ec.G.isOn;
say "Message : ", my \message = "Show me the monKey";
say "The private key dA is : ", my \dA = (1..^O).roll;
my ($r, $s, \Qa) = $ec.generate_signature(dA, message);
say "The public key Qa is : ", Qa;
say "Is Qa ∈ E ? : ", Qa.isOn;
say "Is signature valid? : ", $ec.verify_signature(message, $r, $s, Qa);
say "Message (Tampered) : ", my \altered = "Show me the money";
say "Is signature valid? : ", $ec.verify_signature(altered, $r, $s, Qa)</lang>
{{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>
Thundergnat
10,327

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/285931"