lib/Crypt/Perl/ECDSA/Math.pm

filter: Statementstmt 98.8% 82 / 83 Branchbran 82.5% 33 / 40 Conditioncond 83.3% 10 / 12 MC/DCmcdc 50.0% 4 / 8 Subroutinesub 100% 10 / 10 Podpod 0.0% 0 / 2 totaltotal 89.6% 139 / 155 CC 26 SCAR 21.6
CC
26
Cov
93%
_jacobi_backend
14.2
tonelli_shanks
9.0
_make_bigints
3.0
CRAP 8.6
« blib/lib/Crypt/Perl/X509/GeneralName.pm ↑ Summary blib/lib/Crypt/Perl/ECDSA/NIST.pm »
1 package Crypt::Perl::ECDSA::Math;
2  
3 #Math that’s really only useful for us in the context of ECDSA.
4  
5 8 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
6 8 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
7  
8 8 ▶use Crypt::Perl::BigInt ();
Subroutine BEGIN: called CC=1 SCAR=0.0
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 122 ▶ my ($n, $p) = @_;
Subroutine tonelli_shanks: called CC=9 SCAR=22.0
Pod undocumented
20  
21 122 _make_bigints($n, $p);
22  
23 122 ▶ return 0 if $n->is_zero();
Branch: 1 branch
BranchTrueFalseTotal
if $n->is_zero 0 122 122
24  
25 122 ▶ die "prime must be odd" if $p->beq(2);
Branch: 1 branch
BranchTrueFalseTotal
if $p->beq(2) 0 122 122
26  
27 122 ▶ if (jacobi($n, $p) == -1) {
Branch: 1 branch
BranchTrueFalseTotal
if (jacobi($n, $p) == -1) 0 122 122
28 0 die sprintf( "jacobi(%s, %s) must not be -1", $n->as_hex(), $p->as_hex());
29 }
30  
31 #HAC 3.36
32 122 ▶ if ( $p->copy()->bmod(4)->beq(3) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($p->copy->bmod(4)->beq(3)) 105 17 122
33 105 return $n->copy()->bmodpow( $p->copy()->binc()->brsft(2), $p );
34 }
35  
36 17 my $Si = 0;
37 17 my $Q = $p->copy()->bdec();
38 17 ▶ while ( $Q->is_even() ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($Q->is_even) 608 17 625
39 608 $Q->brsft(1);
40 608 $Si++;
41 }
42  
43 17 my $Z = Crypt::Perl::BigInt->new(2);
44 17 while (1) {
45 88 ▶ last if jacobi($Z, $p) == -1;
Branch: 1 branch
BranchTrueFalseTotal
if jacobi($Z, $p) == -1 17 71 88
46 71 $Z->binc();
47 }
48  
49 17 my $C = $Z->copy()->bmodpow($Q, $p);
50  
51 17 my $t1 = $Q->copy()->binc()->brsft(1);
52  
53 17 my $R = $n->copy()->bmodpow($t1, $p);
54  
55 17 my $T = $n->copy()->bmodpow($Q, $p);
56  
57 17 my $Mi = $Si;
58  
59 17 while (1) {
60 295 my $i = 0;
61  
62 295 $t1 = $T->copy();
63  
64 295 while (1) {
65 13856 ▶ last if $t1->is_one();
Branch: 1 branch
BranchTrueFalseTotal
if $t1->is_one 295 13561 13856
66 13561 $t1->bmodpow(2, $p);
67 13561 $i++;
68 }
69  
70 295 ▶ return $R if $i == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $i == 0 17 278 295
71  
72 278 $t1 = _bi2()->bmodpow($Mi - $i - 1, $p);
73  
74 278 $t1 = $C->bmodpow($t1, $p);
75  
76 278 $C = $t1->copy()->bmodpow(2, $p);
77 278 $R->bmul($t1)->bmod($p);
78 278 $T->bmul($C)->bmod($p);
79 278 $Mi = $i;
80 }
81 }
82  
83 8 my $BI2;
84 sub _bi2 {
85 278 ▶ return( ($BI2 ||= Crypt::Perl::BigInt->new(2))->copy() );
Subroutine _bi2: called CC=2 SCAR=7.2
Condition66%2/3
$BI2 ||= "Crypt::Perl::BigInt"->new(2)
l!l&&r!l&&!r
27620
MC/DC0%0/2
$BI2 ||= "Crypt::Perl::BigInt"->new(2)
$BI2 "Crypt::Perl::BigInt"->new(2)
Truth table66%2/3
A ||= B
A= $BI2B= "Crypt::Perl::BigInt"->new(2)
ABresult
1X1
011
000
86 }
87  
88 #cf. mp_jacobi()
89 #
90 #The return value is a plain scalar (-1, 0, or 1).
91 #
92 sub jacobi {
93 242 ▶ my ($a, $n) = @_;
Subroutine jacobi: called CC=2 SCAR=6.9
Pod undocumented
94  
95 242 _make_bigints($a, $n);
96  
97 242 my $ret = 1;
98  
99 #This loop avoids deep recursion.
100 242 while (1) {
101 10381 my ($ret2, $help) = _jacobi_backend($a, $n);
102  
103 10381 $ret *= $ret2;
104  
105 10381 ▶ last if !$help;
Branch: 1 branch
BranchTrueFalseTotal
unless $help 242 10139 10381
106  
107 10139 ($a, $n) = @$help;
108 }
109  
110 242 return $ret;
111 }
112  
113 sub _make_bigints {
114 364 ▶ ref || ($_ = _bi($_)) for @_;
Subroutine _make_bigints: called CC=3 SCAR=11.0
Branch: 1 branch
BranchTrueFalseTotal
ref $_ or $_ = _bi($_) 16 712 728
115 }
116  
117 sub _jacobi_backend {
118 10381 ▶ my ($a, $n) = @_;
Subroutine _jacobi_backend: called CC=14 SCAR=26.5
119  
120 10381 ▶ die "“a” can’t be negative!" if $a < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $a < 0 0 10381 10381
121  
122 10381 ▶ die "“n” must be positive!" if $n <= 0;
Branch: 1 branch
BranchTrueFalseTotal
if $n <= 0 0 10381 10381
123  
124 #step 1
125 10381 ▶ if ($a->is_zero()) {
Branch: 1 branch
BranchTrueFalseTotal
if ($a->is_zero) 5 10376 10381
126 5 ▶ return $n->is_one() ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$n->is_one ? : 0 5 5
127 }
128  
129 #step 2
130 10376 ▶ return 1 if $a->is_one();
Branch: 1 branch
BranchTrueFalseTotal
if $a->is_one 58 10318 10376
131  
132 #default
133 10318 my $si = 0;
134  
135 10318 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 10318 my $ki = _count_lsb($a1);
140  
141 10318 $a1->brsft($ki);
142  
143 #step 4
144 10318 ▶ if (($ki & 1) == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (($ki & 1) == 0) { } 6574 3744 10318
145 6574 $si = 1;
146 }
147 else {
148 3744 my $residue = $n->copy()->band(7)->numify();
149  
150 3744 ▶ if ( $residue == 1 || $residue == 7 ) {
Branch: 2 branches
BranchTrueFalseTotal
if ($residue == 1 or $residue == 7) { } 1913 1831 3744
elsif ($residue == 3 or $residue == 5) { } 1831 0 1831
Condition100%3/3
$residue == 1 or $residue == 7
l!l&&r!l&&!r
9349791831
MC/DC100%2/2
$residue == 1 or $residue == 7
$residue == 1 $residue == 7
Truth table100%3/3
A or B
A= $residue == 1B= $residue == 7
ABresult
1X1
011
000
151 1913 $si = 1;
152 }
153 ▶ elsif ( $residue == 3 || $residue == 5 ) {
Condition66%2/3
$residue == 3 or $residue == 5
l!l&&r!l&&!r
9448870
MC/DC0%0/2
$residue == 3 or $residue == 5
$residue == 3 $residue == 5
Truth table66%2/3
A or B
A= $residue == 3B= $residue == 5
ABresult
1X1
011
000
154 1831 $si = -1;
155 }
156 }
157  
158 #step 5
159 10318 ▶ if ( $n->copy()->band(3)->beq(3) && $a1->copy()->band(3)->beq(3) ) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->copy->band(3)->beq(3) and $a1->copy->band(3)->beq(3)) 2587 7731 10318
Condition100%3/3
$n->copy->band(3)->beq(3) and $a1->copy->band(3)->beq(3)
!ll&&!rl&&r
512026112587
MC/DC100%2/2
$n->copy->band(3)->beq(3) and $a1->copy->band(3)->beq(3)
$n->copy->band(3)->beq(3) $a1->copy->band(3)->beq(3)
Truth table100%3/3
A and B
A= $n->copy->band(3)->beq(3)B= $a1->copy->band(3)->beq(3)
ABresult
0X0
100
111
160 2587 $si = 0 - $si;
161 }
162  
163 10318 ▶ return $si if $a1->is_one();
Branch: 1 branch
BranchTrueFalseTotal
if $a1->is_one 179 10139 10318
164  
165 10139 my $p1 = $n->copy()->bmod($a1);
166  
167 10139 return( $si, [$p1, $a1] );
168 }
169  
170 #cf. mp_cnt_lsb()
171 sub _count_lsb {
172 10318 ▶ my ($num) = @_;
Subroutine _count_lsb: called CC=1 SCAR=0.0
173  
174 #sprintf('%b',$num) =~ m<(0*)\z>;
175 10318 $num->as_bin() =~ m<(0*)\z>;
176  
177 10318 return length $1;
178 }
179  
180 16 ▶sub _bi { return Crypt::Perl::BigInt->new(@_) }
Subroutine _bi: called CC=1 SCAR=0.0
181  
182 8 1;
« blib/lib/Crypt/Perl/X509/GeneralName.pm ↑ Summary blib/lib/Crypt/Perl/ECDSA/NIST.pm »