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   36 use strict;
  7         35  
  7         152  
4 7     7   29 use warnings;
  7         9  
  7         122  
5              
6 7     7   28 use Crypt::Perl::BigInt ();
  7         10  
  7         8358  
7              
8             my ($bi1, $bi2, $bi3);
9              
10             END {
11 7     7   45157 undef $bi1, $bi2, $bi3;
12             }
13              
14             sub new_infinity {
15 345     345 0 1049 my ($class) = @_;
16              
17 345         2221 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 275830     275830 0 690267 my ($class, $curve, $x, $y, $z) = @_;
25              
26 275830   66     1058113 $bi1 ||= Crypt::Perl::BigInt->new(1);
27 275830   66     6102279 $bi2 ||= Crypt::Perl::BigInt->new(2);
28 275830   66     4739800 $bi3 ||= Crypt::Perl::BigInt->new(3);
29              
30 275830   66     4765066 my $self = {
31             curve => $curve,
32             x => $x,
33             y => $y,
34             z => $z || $bi1->copy(),
35             zinv => undef,
36             };
37              
38 275830         8091851 return bless $self, $class;
39             }
40              
41             sub is_infinity {
42 343395     343395 0 512736 my ($self) = @_;
43              
44 343395 0 33     922781 return 1 if !defined $self->{'x'} && !defined $self->{'y'};
45              
46 343395   50     828662 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 1409 my ($self) = @_;
52              
53 545         4242 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 116 my ($self) = @_;
60              
61 49         126 return $self->_get_x_or_y('y');
62             }
63              
64             sub _get_x_or_y {
65 594     594   3122 my ($self, $to_get) = @_;
66              
67 594 100       2088 if (!defined $self->{'zinv'}) {
68 545         2219 $self->{'zinv'} = $self->{'z'}->copy()->bmodinv($self->{'curve'}{'q'});
69             }
70              
71             return $self->{'curve'}->from_bigint(
72 594         11531875 $self->{$to_get}->to_bigint()->copy()->bmul($self->{'zinv'})->bmod($self->{'curve'}{'q'})
73             );
74             }
75              
76             sub negate {
77 796     796 0 1884 my ($self) = @_;
78              
79 796         1614 my @args = @{$self}{qw( curve x y z )};
  796         3304  
80 796         4527 $args[2] = $args[2]->negate();
81              
82 796         2535 return (ref $self)->new(@args);
83             }
84              
85             #Did the quadratic formula explode???
86             sub twice {
87 205187     205187 0 489872 my ($self) = @_;
88              
89 205187 50       502517 return $self if $self->is_infinity();
90              
91             #if ($self->{'y'}->to_bigint()->signum() == 0) {
92             # return $self->{'curve'}->get_infinity();
93             #}
94              
95 205187         3229161 my $x1 = $self->{'x'}->to_bigint();
96 205187         467546 my $y1 = $self->{'y'}->to_bigint();
97              
98 205187         642831 my $y1z1 = $y1->copy()->bmul($self->{'z'});
99              
100 205187         76499103 my $y1sqz1 = $y1z1->copy()->bmul($y1)->bmod($self->{'curve'}{'q'});
101              
102 205187         345732572 my $a = $self->{'curve'}{'a'};
103              
104             # w = 3 * x1^2 + a * z1^2
105             #var w = x1.square().multiply(THREE);
106 205187         632541 my $w = $x1->copy()->bpow($bi2)->bmul($bi3);
107              
108 205187 100       109200976 if (!$a->is_zero()) {
109             #$w += ($self->{'z'} ** 2) * $a;
110 182947         2301397 $w->badd( $a->copy()->bmul( $self->{'z'} )->bmul($self->{'z'}) );
111             }
112              
113 205187         203771759 $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 205187         215586493 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 205187         430025588 my $y3 = $y1sqz1->copy()->blsft($bi2);
129              
130 205187         27321182 $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 205187         469461446 my $z3 = $y1z1->bpow($bi3)->blsft($bi3); #don’t need y1z1 anymore
143              
144             #In original JS logic
145 205187         664827756 $_->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 205187         1032817972 $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 2371 my ($self, $k) = @_;
168             #print "in mult\n";
169             #$self->dump('self');
170              
171 796 50       2822 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         12334 my $e = $k;
182 796         2381 my $h = $e->copy()->bmul($bi3);
183             #print "h: " . $h->as_hex() . $/;
184              
185 796         74220 my $neg = $self->negate();
186             #$neg->dump('neg');
187 796         1517 my $R = $self;
188              
189             #print "start loop: " . (_MBI_bit_length($h) - 2) . $/;
190 796         4592 for my $i ( reverse( 1 .. ($h->bit_length() - 2) ) ) {
191 205187         1335153 $R = $R->twice();
192             #$R->dump("R, loop $i");
193              
194 205187         1050734 my $hbit = $h->test_bit($i);
195 205187         665025 my $ebit = $e->test_bit($i);
196             #print "hbit [$hbit], ebit [$ebit]\n";
197              
198 205187 100       767001 if ($hbit != $ebit) {
199 68455 100       405249 $R = $R->add( $hbit ? $self : $neg );
200             }
201             #$R->dump("R, end of loop");
202             }
203              
204 796         21683 return $R;
205             }
206              
207             #$b isa ECPoint
208             sub add {
209 68706     68706 0 187718 my ($self, $b) = @_;
210             #$b->dump('$b');
211              
212             #if(this.isInfinity()) return b;
213             #if(b.isInfinity()) return this;
214              
215 68706 50       212316 return $b if $self->is_infinity();
216 68706 50       1068948 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 68706         976894 $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 68706         37893965 $self->{'x'}->to_bigint()->copy()->bneg()->bmul($b->{'z'}),
231             );
232              
233              
234 68706         35283409 $_->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 68706 50       86885065 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 68706         758714 my ($x1, $y1, $z1) = @{$self}{ qw( x y z ) };
  68706         224420  
257 68706         164519 my ($x2, $y2, $z2) = @{$b}{ qw( x y z ) };
  68706         203290  
258              
259 68706         279739 $_ = $_->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 68706         196177 my $v2 = $v->copy()->bmul($v);
267 68706         25745559 my $v3 = $v->copy()->bmul($v2);
268              
269 68706         38544168 my $x1v2 = $x1->copy()->bmul($v2);
270 68706         38535694 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 68706         65953399 my $x3 = $u->copy()->bmul($u);
278 68706         25267417 $x3->bmuladd( $z1, $x1->copy()->blsft($bi1)->bneg()->bmul($v)->bmul($v) );
279 68706         123227088 $x3->bmuladd( $z2, $v->copy()->bpow($bi3)->bneg() );
280 68706         85654353 $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 68706         59524671 my $y3 = $u->copy()->bmul($bi3)->bmul($x1);
286 68706         28318147 $y3->bmuladd($v2, $y1->bmul($v3)->bneg()); #no more y1 after this
287 68706         134176712 $y3->bsub( $u->copy()->bpow($bi3)->bmul($z1) );
288              
289 68706         141620221 $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 68706         70335108 my $z3 = $v3->bmul($z1)->bmul($z2);
294              
295 68706         66760234 $_->bmod($self->{'curve'}{'q'}) for ($x3, $y3, $z3);
296              
297             return (ref $self)->new(
298             $self->{'curve'},
299             $self->{'curve'}->from_bigint($x3),
300 68706         317481623 $self->{'curve'}->from_bigint($y3),
301             $z3,
302             );
303             }
304              
305             1;