File Coverage

lib/Crypt/Perl/ECDSA/EC/Point.pm
Criterion Covered Total %
statement 91 99 91.9
branch 13 22 59.0
condition 10 17 58.8
subroutine 14 15 93.3
pod 0 10 0.0
total 128 163 78.5


line stmt bran cond sub pod time code
1             package Crypt::Perl::ECDSA::EC::Point;
2              
3 7     7   37 use strict;
  7         14  
  7         154  
4 7     7   25 use warnings;
  7         10  
  7         118  
5              
6 7     7   27 use Crypt::Perl::BigInt ();
  7         15  
  7         8205  
7              
8             my ($bi1, $bi2, $bi3);
9              
10             END {
11 7     7   46591 undef $bi1, $bi2, $bi3;
12             }
13              
14             sub new_infinity {
15 345     345 0 1640 my ($class) = @_;
16              
17 345         1846 return $class->new( undef, undef );
18             }
19              
20             #$curve is ECCurve
21             #$x and $y are “ECFieldElement”
22             #$z isa bigint (?)
23             sub new {
24 275839     275839 0 707990 my ($class, $curve, $x, $y, $z) = @_;
25              
26 275839   66     976816 $bi1 ||= Crypt::Perl::BigInt->new(1);
27 275839   66     6315726 $bi2 ||= Crypt::Perl::BigInt->new(2);
28 275839   66     5012468 $bi3 ||= Crypt::Perl::BigInt->new(3);
29              
30 275839   66     5056568 my $self = {
31             curve => $curve,
32             x => $x,
33             y => $y,
34             z => $z || $bi1->copy(),
35             zinv => undef,
36             };
37              
38 275839         8087455 return bless $self, $class;
39             }
40              
41             sub is_infinity {
42 343431     343431 0 575951 my ($self) = @_;
43              
44 343431 0 33     864429 return 1 if !defined $self->{'x'} && !defined $self->{'y'};
45              
46 343431   50     833794 return( ($self->{'z'}->is_zero() && !$self->{'y'}->to_bigint()->is_zero()) || 0 );
47             }
48              
49             #returns ECFieldElement
50             sub get_x {
51 545     545 0 1651 my ($self) = @_;
52              
53 545         2962 return $self->_get_x_or_y('x');
54             }
55              
56             #returns ECFieldElement
57             #Used in key generation (not signing … ?)
58             sub get_y {
59 49     49 0 128 my ($self) = @_;
60              
61 49         138 return $self->_get_x_or_y('y');
62             }
63              
64             sub _get_x_or_y {
65 594     594   3778 my ($self, $to_get) = @_;
66              
67 594 100       2637 if (!defined $self->{'zinv'}) {
68 545         2450 $self->{'zinv'} = $self->{'z'}->copy()->bmodinv($self->{'curve'}{'q'});
69             }
70              
71             return $self->{'curve'}->from_bigint(
72 594         11989558 $self->{$to_get}->to_bigint()->copy()->bmul($self->{'zinv'})->bmod($self->{'curve'}{'q'})
73             );
74             }
75              
76             sub negate {
77 796     796 0 2221 my ($self) = @_;
78              
79 796         2125 my @args = @{$self}{qw( curve x y z )};
  796         3478  
80 796         4100 $args[2] = $args[2]->negate();
81              
82 796         3223 return (ref $self)->new(@args);
83             }
84              
85             #Did the quadratic formula explode???
86             sub twice {
87 205169     205169 0 395406 my ($self) = @_;
88              
89 205169 50       470923 return $self if $self->is_infinity();
90              
91             #if ($self->{'y'}->to_bigint()->signum() == 0) {
92             # return $self->{'curve'}->get_infinity();
93             #}
94              
95 205169         3291201 my $x1 = $self->{'x'}->to_bigint();
96 205169         486119 my $y1 = $self->{'y'}->to_bigint();
97              
98 205169         594783 my $y1z1 = $y1->copy()->bmul($self->{'z'});
99              
100 205169         77738301 my $y1sqz1 = $y1z1->copy()->bmul($y1)->bmod($self->{'curve'}{'q'});
101              
102 205169         358958642 my $a = $self->{'curve'}{'a'};
103              
104             # w = 3 * x1^2 + a * z1^2
105             #var w = x1.square().multiply(THREE);
106 205169         566755 my $w = $x1->copy()->bpow($bi2)->bmul($bi3);
107              
108 205169 100       111705142 if (!$a->is_zero()) {
109             #$w += ($self->{'z'} ** 2) * $a;
110 182911         2237689 $w->badd( $a->copy()->bmul( $self->{'z'} )->bmul($self->{'z'}) );
111             }
112              
113 205169         209287030 $w->bmod($self->{'curve'}{'q'});
114              
115             # x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
116             #var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.q);
117              
118 205169         225129444 my $x3 = $w->copy()->bmuladd( $w, $y1sqz1->copy()->bmul($x1)->blsft($bi3)->bneg() )->bmul($bi2)->bmul($y1z1);
119             #my $x3 = 2 * $y1z1 * (($w ** 2) - ($x1 << 3) * $y1sqz1);
120             #my $x3 = ($w ** 2) - (($x1 << 3) * $y1sqz1);
121             #$x3 = $x3 << 1;
122             #$x3 *= $y1z1;
123              
124             # y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
125             #var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.square().multiply(w)).mod(this.curve.q);
126             #my $y3 = 4 * $y1sqz1 * (3 * $w * $x1 - 2 * $y1sqz1) - ($w ** 3);
127              
128 205169         440732846 my $y3 = $y1sqz1->copy()->blsft($bi2);
129              
130 205169         28139844 $y3->bmuladd(
131              
132             #We don’t need y1sqz1 anymore
133             $w->copy()->bmul($bi3)->bmuladd($x1, $y1sqz1->blsft($bi1)->bneg()),
134              
135             #Don’t need $w anymore
136             $w->bpow($bi3)->bneg(),
137             );
138              
139             #// z3 = 8 * (y1 * z1)^3
140             #var z3 = y1z1.square().multiply(y1z1).shiftLeft(3).mod(this.curve.q);
141             #my $z3 = ($y1z1 ** 3) << 3;
142 205169         483892464 my $z3 = $y1z1->bpow($bi3)->blsft($bi3); #don’t need y1z1 anymore
143              
144             #In original JS logic
145 205169         683022193 $_->bmod($self->{'curve'}{'q'}) for ($x3, $y3, $z3);
146              
147             #return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
148             return (ref $self)->new(
149             $self->{'curve'},
150             $self->{'curve'}->from_bigint($x3),
151 205169         1079523098 $self->{'curve'}->from_bigint($y3),
152             $z3,
153             );
154             }
155              
156             #XXX clear
157             sub dump {
158 0     0 0 0 my ($self, $label) = @_;
159              
160 0         0 printf "$label.x: %s\n", $self->{'x'}->to_bigint()->as_hex();
161 0         0 printf "$label.y: %s\n", $self->{'y'}->to_bigint()->as_hex();
162 0         0 printf "$label.z: %s\n", $self->{'z'}->as_hex();
163             }
164              
165             #yowza ...
166             sub multiply {
167 796     796 0 2850 my ($self, $k) = @_;
168             #print "in mult\n";
169             #$self->dump('self');
170              
171 796 50       2867 if ($self->is_infinity()) {
172 0         0 return $self;
173             }
174              
175             #TODO
176             #if ($k->signum() == 0) {
177             # return $self->{'curve'}->getInfinity(); #should this happen?
178             #}
179              
180             #print "here2\n";
181 796         13946 my $e = $k;
182 796         2397 my $h = $e->copy()->bmul($bi3);
183             #print "h: " . $h->as_hex() . $/;
184              
185 796         77737 my $neg = $self->negate();
186             #$neg->dump('neg');
187 796         2921 my $R = $self;
188              
189             #print "start loop: " . (_MBI_bit_length($h) - 2) . $/;
190 796         4940 for my $i ( reverse( 1 .. ($h->bit_length() - 2) ) ) {
191 205169         1376666 $R = $R->twice();
192             #$R->dump("R, loop $i");
193              
194 205169         994406 my $hbit = $h->test_bit($i);
195 205169         595124 my $ebit = $e->test_bit($i);
196             #print "hbit [$hbit], ebit [$ebit]\n";
197              
198 205169 100       791528 if ($hbit != $ebit) {
199 68482 100       423928 $R = $R->add( $hbit ? $self : $neg );
200             }
201             #$R->dump("R, end of loop");
202             }
203              
204 796         22455 return $R;
205             }
206              
207             #$b isa ECPoint
208             sub add {
209 68733     68733 0 220881 my ($self, $b) = @_;
210             #$b->dump('$b');
211              
212             #if(this.isInfinity()) return b;
213             #if(b.isInfinity()) return this;
214              
215 68733 50       192995 return $b if $self->is_infinity();
216 68733 50       1146141 return $self if $b->is_infinity();
217              
218             #// u = Y2 * Z1 - Y1 * Z2
219             #var u = b.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(b.z)).mod(this.curve.q);
220             my $u = $b->{'y'}->to_bigint()->copy()->bmuladd(
221             $self->{'z'},
222 68733         1048509 $self->{'y'}->to_bigint()->copy()->bneg()->bmul($b->{'z'}),
223             );
224             # $b->{'z'};
225              
226             #// v = X2 * Z1 - X1 * Z2
227             #var v = b.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(b.z)).mod(this.curve.q);
228             my $v = $b->{'x'}->to_bigint()->copy()->bmuladd(
229             $self->{'z'},
230 68733         38402303 $self->{'x'}->to_bigint()->copy()->bneg()->bmul($b->{'z'}),
231             );
232              
233              
234 68733         36411494 $_->bmod($self->{'curve'}{'q'}) for ($u, $v);
235             #print "u: " . $u->as_hex() . $/;
236             #print "v: " . $v->as_hex() . $/;
237             #if(BigInteger.ZERO.equals(v)) {
238             # if(BigInteger.ZERO.equals(u)) {
239             # return this.twice(); // this == b, so double
240             # }
241             #return this.curve.getInfinity(); // this = -b, so infinity
242             #}
243 68733 50       90604757 if ($v->is_zero()) {
244 0 0       0 if ($u->is_zero()) {
245 0         0 return $self->twice();
246             }
247              
248 0         0 return $self->{'curve'}->get_infinity();
249             }
250              
251             #var THREE = new BigInteger("3");
252             #var x1 = this.x.toBigInteger();
253             #var y1 = this.y.toBigInteger();
254             #var x2 = b.x.toBigInteger();
255             #var y2 = b.y.toBigInteger();
256 68733         856296 my ($x1, $y1, $z1) = @{$self}{ qw( x y z ) };
  68733         238967  
257 68733         171149 my ($x2, $y2, $z2) = @{$b}{ qw( x y z ) };
  68733         176532  
258              
259 68733         282174 $_ = $_->to_bigint() for ($x1, $y1, $x2, $y2);
260              
261             #var v2 = v.square();
262             #var v3 = v2.multiply(v);
263             #var x1v2 = x1.multiply(v2);
264             #var zu2 = u.square().multiply(this.z);
265              
266 68733         242948 my $v2 = $v->copy()->bmul($v);
267 68733         26536908 my $v3 = $v->copy()->bmul($v2);
268              
269 68733         39606728 my $x1v2 = $x1->copy()->bmul($v2);
270 68733         39559717 my $zu2 = $u->copy()->bmul($u)->bmul($self->{'z'});
271             #use Data::Dumper;
272             #print Dumper( map { $_->as_hex() } $u, $v, $x1, $y1, $z1, $x2, $y2, $z2, $v2, $v3, $x1v2, $zu2 );
273              
274             #// x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
275             #var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.q);
276             #my $x3 = $v * ($z2 * ($z1 * ($u ** 2) - 2 * $x1 * ($v ** 2)) - ($v ** 3));
277 68733         67779887 my $x3 = $u->copy()->bmul($u);
278 68733         25981842 $x3->bmuladd( $z1, $x1->copy()->blsft($bi1)->bneg()->bmul($v)->bmul($v) );
279 68733         126157216 $x3->bmuladd( $z2, $v->copy()->bpow($bi3)->bneg() );
280 68733         87991166 $x3->bmul($v);
281              
282             #// y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
283             #var y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.curve.q);
284             #my $y3 = $z2 * (3 * $x1 * $u * $v2 - $y1 * $v3 - $z1 * ($u ** 3)) + $u * $v3;
285 68733         61174537 my $y3 = $u->copy()->bmul($bi3)->bmul($x1);
286 68733         29253081 $y3->bmuladd($v2, $y1->bmul($v3)->bneg()); #no more y1 after this
287 68733         137730089 $y3->bsub( $u->copy()->bpow($bi3)->bmul($z1) );
288              
289 68733         145766611 $y3->bmuladd( $z2, $u->bmul($v3) ); #we don’t need $u anymore
290              
291             #// z3 = v^3 * z1 * z2
292             #var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.q);
293 68733         72265510 my $z3 = $v3->bmul($z1)->bmul($z2);
294              
295 68733         68623620 $_->bmod($self->{'curve'}{'q'}) for ($x3, $y3, $z3);
296              
297             return (ref $self)->new(
298             $self->{'curve'},
299             $self->{'curve'}->from_bigint($x3),
300 68733         330773488 $self->{'curve'}->from_bigint($y3),
301             $z3,
302             );
303             }
304              
305             1;