blib/lib/Crypt/Perl/ECDSA/Math.pm untested

filter: Statementstmt 0.0% 0 / 85 Branchbran 0.0% 0 / 36 Conditioncond 0.0% 0 / 15 MC/DCmcdc n/a Subroutinesub 0.0% 0 / 10 Podpod 0.0% 0 / 7 totaltotal 0.0% 0 / 153 CC 19 SCAR 43.0
CC
19
Cov
0%
_jacobi_backend
132.0
tonelli_shanks
72.0
jacobi
6.0
CRAP 73.4
1 package Crypt::Perl::ECDSA::Math;
2  
3 #Math that’s really only useful for us in the context of ECDSA.
4  
5 use strict;
6 use warnings;
7  
8 use Crypt::Perl::BigInt ();
9  
10 #A port of libtomcrypt’s mp_sqrtmod_prime().
11 #The return value will be a Crypt::Perl::BigInt reference.
12 #
13 #See also implementations at:
14 # https://rosettacode.org/wiki/Tonelli-Shanks_algorithm
15 #
16 #See “Handbook of Applied Cryptography”, algorithms 3.34 and 3.36,
17 #for reference.
18 sub tonelli_shanks {
19 my ($n, $p) = @_;
20  
21 _make_bigints($n, $p);
22  
23 return 0 if $n->is_zero();
24  
25 die "prime must be odd" if $p->beq(2);
26  
27 if (jacobi($n, $p) == -1) {
28 die sprintf( "jacobi(%s, %s) must not be -1", $n->as_hex(), $p->as_hex());
29 }
30  
31 #HAC 3.36
32 if ( $p->copy()->bmod(4)->beq(3) ) {
33 return $n->copy()->bmodpow( $p->copy()->binc()->brsft(2), $p );
34 }
35  
36 my $Si = 0;
37 my $Q = $p->copy()->bdec();
38 while ( $Q->is_even() ) {
39 $Q->brsft(1);
40 $Si++;
41 }
42  
43 my $Z = Crypt::Perl::BigInt->new(2);
44 while (1) {
45 last if jacobi($Z, $p) == -1;
46 $Z->binc();
47 }
48  
49 my $C = $Z->copy()->bmodpow($Q, $p);
50  
51 my $t1 = $Q->copy()->binc()->brsft(1);
52  
53 my $R = $n->copy()->bmodpow($t1, $p);
54  
55 my $T = $n->copy()->bmodpow($Q, $p);
56  
57 my $Mi = $Si;
58  
59 while (1) {
60 my $i = 0;
61  
62 $t1 = $T->copy();
63  
64 while (1) {
65 last if $t1->is_one();
66 $t1->bmodpow(2, $p);
67 $i++;
68 }
69  
70 return $R if $i == 0;
71  
72 $t1 = _bi2()->bmodpow($Mi - $i - 1, $p);
73  
74 $t1 = $C->bmodpow($t1, $p);
75  
76 $C = $t1->copy()->bmodpow(2, $p);
77 $R->bmul($t1)->bmod($p);
78 $T->bmul($C)->bmod($p);
79 $Mi = $i;
80 }
81 }
82  
83 my $BI2;
84 sub _bi2 {
85 return( ($BI2 ||= Crypt::Perl::BigInt->new(2))->copy() );
86 }
87  
88 #cf. mp_jacobi()
89 #
90 #The return value is a plain scalar (-1, 0, or 1).
91 #
92 sub jacobi {
93 my ($a, $n) = @_;
94  
95 _make_bigints($a, $n);
96  
97 my $ret = 1;
98  
99 #This loop avoids deep recursion.
100 while (1) {
101 my ($ret2, $help) = _jacobi_backend($a, $n);
102  
103 $ret *= $ret2;
104  
105 last if !$help;
106  
107 ($a, $n) = @$help;
108 }
109  
110 return $ret;
111 }
112  
113 sub _make_bigints {
114 ref || ($_ = _bi($_)) for @_;
115 }
116  
117 sub _jacobi_backend {
118 my ($a, $n) = @_;
119  
120 die "“a” can’t be negative!" if $a < 0;
121  
122 die "“n” must be positive!" if $n <= 0;
123  
124 #step 1
125 if ($a->is_zero()) {
126 return $n->is_one() ? 1 : 0;
127 }
128  
129 #step 2
130 return 1 if $a->is_one();
131  
132 #default
133 my $si = 0;
134  
135 my $a1 = $a->copy();
136  
137 #Determine $a1’s greatest factor that is a power of 2,
138 #which is the number of lest-significant 0 bits.
139 my $ki = _count_lsb($a1);
140  
141 $a1->brsft($ki);
142  
143 #step 4
144 if (($ki & 1) == 0) {
145 $si = 1;
146 }
147 else {
148 my $residue = $n->copy()->band(7)->numify();
149  
150 if ( $residue == 1 || $residue == 7 ) {
151 $si = 1;
152 }
153 elsif ( $residue == 3 || $residue == 5 ) {
154 $si = -1;
155 }
156 }
157  
158 #step 5
159 if ( $n->copy()->band(3)->beq(3) && $a1->copy()->band(3)->beq(3) ) {
160 $si = 0 - $si;
161 }
162  
163 return $si if $a1->is_one();
164  
165 my $p1 = $n->copy()->bmod($a1);
166  
167 return( $si, [$p1, $a1] );
168 }
169  
170 #cf. mp_cnt_lsb()
171 sub _count_lsb {
172 my ($num) = @_;
173  
174 #sprintf('%b',$num) =~ m<(0*)\z>;
175 $num->as_bin() =~ m<(0*)\z>;
176  
177 return length $1;
178 }
179  
180 sub _bi { return Crypt::Perl::BigInt->new(@_) }
181  
182 1;