File Coverage

blib/lib/Math/Prime/Util/ECAffinePoint.pm
Criterion Covered Total %
statement 74 114 64.9
branch 19 46 41.3
condition 7 25 28.0
subroutine 10 19 52.6
pod 10 10 100.0
total 120 214 56.0


line stmt bran cond sub pod time code
1             package Math::Prime::Util::ECAffinePoint;
2 1     1   7 use strict;
  1         1  
  1         30  
3 1     1   5 use warnings;
  1         2  
  1         34  
4 1     1   6 use Carp qw/carp croak confess/;
  1         1  
  1         175  
5              
6             BEGIN {
7 1     1   4 $Math::Prime::Util::ECAffinePoint::AUTHORITY = 'cpan:DANAJ';
8 1         51 $Math::Prime::Util::ECAffinePoint::VERSION = '0.69';
9             }
10              
11             BEGIN {
12 1 50   1   994 do { require Math::BigInt; Math::BigInt->import(try=>"GMP,Pari"); }
  0         0  
  0         0  
13             unless defined $Math::BigInt::VERSION;
14             }
15              
16             # Pure perl (with Math::BigInt) manipulation of Elliptic Curves
17             # in affine coordinates. Should be split into a point class.
18              
19             sub new {
20 9     9 1 38 my ($class, $a, $b, $n, $x, $y) = @_;
21 9 50       37 $a = Math::BigInt->new("$a") unless ref($a) eq 'Math::BigInt';
22 9 50       28 $b = Math::BigInt->new("$b") unless ref($b) eq 'Math::BigInt';
23 9 50       24 $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt';
24 9 50       26 $x = Math::BigInt->new("$x") unless ref($x) eq 'Math::BigInt';
25 9 50       22 $y = Math::BigInt->new("$y") unless ref($y) eq 'Math::BigInt';
26              
27 9 50       25 croak "n must be >= 2" unless $n >= 2;
28 9         996 $a->bmod($n);
29 9         972 $b->bmod($n);
30              
31 9         812 my $self = {
32             a => $a,
33             b => $b,
34             n => $n,
35             x => $x,
36             y => $y,
37             f => $n->copy->bone,
38             };
39              
40 9         851 bless $self, $class;
41 9         25 return $self;
42             }
43              
44             sub _add {
45 0     0   0 my ($self, $P1x, $P1y, $P2x, $P2y) = @_;
46 0         0 my $n = $self->{'n'};
47              
48 0 0       0 if ($P1x == $P2x) {
49 0         0 my $t = ($P1y + $P2y) % $n;
50 0 0       0 return (Math::BigInt->bzero,Math::BigInt->bone) if $t == 0;
51             }
52 0         0 my $deltax = ($P2x - $P1x) % $n;
53 0         0 $deltax->bmodinv($n);
54 0 0       0 return (Math::BigInt->bzero,Math::BigInt->bone) if $deltax eq "NaN";
55              
56 0         0 my $deltay = ($P2y - $P1y) % $n;
57 0         0 my $m = ($deltay * $deltax) % $n; # m = deltay / deltax
58              
59 0         0 my $x = ($m*$m - $P1x - $P2x) % $n;
60 0         0 my $y = ($m*($P1x - $x) - $P1y) % $n;
61 0         0 return ($x,$y);
62             }
63              
64             sub _double {
65 0     0   0 my ($self, $P1x, $P1y) = @_;
66 0         0 my $n = $self->{'n'};
67              
68 0         0 my $m = 2*$P1y;
69 0         0 $m->bmodinv($n);
70 0 0       0 return (Math::BigInt->bzero,Math::BigInt->bone) if $m eq "NaN";
71              
72 0         0 $m = ((3*$P1x*$P1x + $self->{'a'}) * $m) % $n;
73              
74 0         0 my $x = ($m*$m - 2*$P1x) % $n;
75 0         0 my $y = ($m*($P1x - $x) - $P1y) % $n;
76 0         0 return ($x,$y);
77             }
78              
79             sub _inplace_add {
80 147     147   367 my ($P1x, $P1y, $x, $y, $n) = @_;
81              
82 147 100       431 if ($P1x == $x) {
83 9         354 my $t = ($P1y + $y) % $n;
84 9 50       1507 if ($t == 0) {
85 9         1618 ($_[2],$_[3]) = (Math::BigInt->bzero,Math::BigInt->bone);
86 9         500 return;
87             }
88             }
89 138         5689 my $deltax = ($x - $P1x) % $n;
90 138         31320 $deltax->bmodinv($n);
91 138 50       413241 if ($deltax eq 'NaN') {
92 0         0 ($_[2],$_[3]) = (Math::BigInt->bzero,Math::BigInt->bone);
93 0         0 return;
94             }
95 138         3754 my $deltay = ($y - $P1y) % $n;
96 138         33352 my $m = ($deltay * $deltax) % $n; # m = deltay / deltax
97              
98 138         41582 $_[2] = ($m*$m - $P1x - $x) % $n;
99 138         72594 $_[3] = ($m*($P1x - $_[2]) - $P1y) % $n;
100             }
101             sub _inplace_double {
102 331     331   800 my($x, $y, $a, $n) = @_;
103 331         893 my $m = $y+$y;
104 331         24978 $m->bmodinv($n);
105 331 50       912188 if ($m eq 'NaN') {
106 0         0 ($_[0],$_[1]) = (Math::BigInt->bzero,Math::BigInt->bone);
107 0         0 return;
108             }
109 331         9452 $m->bmul($x->copy->bmul($x)->bmul(3)->badd($a))->bmod($n);
110              
111 331         207710 my $xin = $x->copy;
112 331         6450 $_[0] = ($m*$m - $x - $x) % $n;
113 331         175029 $_[1] = ($m*($xin - $_[0]) - $y) % $n;
114             }
115              
116             sub mul {
117 18     18 1 1618 my ($self, $k) = @_;
118 18         48 my $x = $self->{'x'};
119 18         41 my $y = $self->{'y'};
120 18         33 my $a = $self->{'a'};
121 18         33 my $n = $self->{'n'};
122 18         28 my $f = $self->{'f'};
123 18 50 33     99 if (ref($k) eq 'Math::BigInt' && $k < ''.~0) {
124 18 50 50     2389 if ($] >= 5.008 || ~0 == 4294967295) {
    0 0        
      0        
125 18         49 $k = int($k->bstr);
126             } elsif ($] < 5.008 && ~0 > 4294967295 && $k < 562949953421312) {
127 0         0 $k = unpack('Q',pack('Q',$k->bstr));
128             }
129             }
130              
131 18         337 my $Bx = $n->copy->bzero;
132 18         674 my $By = $n->copy->bone;
133 18         1413 my $v = 1;
134              
135 18         48 while ($k > 0) {
136 496 100       240085 if ( ($k % 2) != 0) {
137 165         315 $k--;
138 165         454 $f->bmul($Bx-$x)->bmod($n);
139 165 50 33     60596 if ($x->is_zero && $y->is_one) { }
    100 66        
140 18         653 elsif ($Bx->is_zero && $By->is_one) { ($Bx,$By) = ($x,$y); }
141 147         3352 else { _inplace_add($x,$y,$Bx,$By,$n); }
142             } else {
143 331         591 $k >>= 1;
144 331         896 $f->bmul(2*$y)->bmod($n);
145 331         136458 _inplace_double($x,$y,$a,$n);
146             }
147             }
148 18         3355 $f = Math::BigInt::bgcd($f, $n);
149 18         9033 $self->{'x'} = $Bx;
150 18         58 $self->{'y'} = $By;
151 18         54 $self->{'f'} = $f;
152 18         109 return $self;
153             }
154              
155             sub add {
156 0     0 1 0 my ($self, $other) = @_;
157 0 0       0 croak "add takes a EC point"
158             unless ref($other) eq 'Math::Prime::Util::ECAffinePoint';
159             croak "second point is not on the same curve"
160             unless $self->{'a'} == $other->{'a'} &&
161             $self->{'b'} == $other->{'b'} &&
162 0 0 0     0 $self->{'n'} == $other->{'n'};
      0        
163              
164             ($self->{'x'}, $self->{'y'}) = $self->_add($self->{'x'}, $self->{'y'},
165 0         0 $other->{'x'}, $other->{'y'});
166 0         0 return $self;
167             }
168              
169              
170 0     0 1 0 sub a { return shift->{'a'}; }
171 0     0 1 0 sub b { return shift->{'b'}; }
172 0     0 1 0 sub n { return shift->{'n'}; }
173 0     0 1 0 sub x { return shift->{'x'}; }
174 0     0 1 0 sub y { return shift->{'y'}; }
175 0     0 1 0 sub f { return shift->{'f'}; }
176              
177             sub is_infinity {
178 18     18 1 36 my $self = shift;
179 18   66     48 return ($self->{'x'}->is_zero() && $self->{'y'}->is_one());
180             }
181              
182             1;
183              
184             __END__