blib/lib/Crypt/Perl/Ed25519/Math.pm

filter: Statementstmt 98.8% 250 / 253 Branchbran 87.5% 21 / 24 Conditioncond 66.6% 6 / 9 MC/DCmcdc 60.0% 3 / 5 Subroutinesub 100% 36 / 36 Podpod 0.0% 0 / 10 totaltotal 93.7% 316 / 337 CC 40 SCAR 11.6
CC
40
Cov
97%
modL
6.0
_sel25519
6.0
unpackneg
5.0
CRAP 3.2
« blib/lib/Crypt/Perl/RSA/Parse.pm ↑ Summary blib/lib/Crypt/Perl/KeyBase.pm »
1 package Crypt::Perl::Ed25519::Math;
2  
3 3 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 3 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5  
6 3 ▶use Math::Utils ();
Subroutine BEGIN: called CC=1 SCAR=0.0
7  
8 sub reduce {
9 49 ▶ my ($r) = @_;
Subroutine reduce: called CC=2 SCAR=6.9
Pod undocumented
10  
11 49 my @x;
12  
13 49 for my $i ( 0 .. 63 ) {
14 3136 $x[$i] = $r->[$i];
15 3136 $r->[$i] = 0;
16 }
17  
18 49 modL( $r, \@x );
19  
20 49 return;
21 }
22  
23 # p and q are arrays of arrays; s is an array of numbers
24 sub scalarmult {
25 69 ▶ my ($p, $q, $s) = @_;
Subroutine scalarmult: called CC=2 SCAR=6.9
Pod undocumented
26  
27 69 @{$p}[0 .. 3] = ( [ gf0() ], [ gf1() ], [ gf1() ], [ gf0() ] );
28  
29 69 my $b;
30  
31 69 for my $i ( reverse( 0 .. 255 ) ) {
32 17664 $b = ( $s->[ ( $i >> 3 ) | 0 ] >> ($i & 7) ) & 1;
33 17664 _cswap( $p, $q, $b );
34 17664 add( $q, $p );
35 17664 add( $p, $p );
36 17664 _cswap( $p, $q, $b );
37 }
38  
39 69 return;
40 }
41  
42 # p is an array of arrays; s is an array of numbers
43 sub scalarbase {
44 48 ▶ my ($p, $s) = @_;
Subroutine scalarbase: called CC=1 SCAR=0.0
Pod undocumented
45  
46 48 my @q = ( [ X() ], [ Y() ], [ gf1() ], [ gf0() ] );
47  
48 48 _M( $q[3], [X()], [Y()] );
49  
50 48 scalarmult($p, \@q, $s);
51 }
52  
53 # p is an array of arrays
54 sub pack {
55 48 ▶ my ($p) = @_;
Subroutine pack: called CC=1 SCAR=0.0
Pod undocumented
56  
57 48 my $tx = [ gf0() ];
58 48 my $ty = [ gf0() ];
59 48 my $zi = [ gf0() ];
60  
61 48 _inv25519( $zi, $p->[2] );
62  
63 48 _M( $tx, $p->[0], $zi );
64 48 _M( $ty, $p->[1], $zi );
65  
66 48 my $r = _pack25519($ty);
67  
68 48 $r->[31] ^= (_par25519($tx) << 7);
69  
70 48 return $r;
71 }
72  
73 sub add {
74 35349 ▶ my ($p, $q) = @_;
Subroutine add: called CC=1 SCAR=0.0
Pod undocumented
75  
76 35349 my $a = [ gf0() ];
77 35349 my $b = [ gf0() ];
78 35349 my $c = [ gf0() ];
79 35349 my $d = [ gf0() ];
80 35349 my $e = [ gf0() ];
81 35349 my $f = [ gf0() ];
82 35349 my $g = [ gf0() ];
83 35349 my $h = [ gf0() ];
84 35349 my $t = [ gf0() ];
85  
86 35349 _Z($a, $p->[1], $p->[0]);
87 35349 _Z($t, $q->[1], $q->[0]);
88 35349 _M($a, $a, $t);
89 35349 _A($b, $p->[0], $p->[1]);
90 35349 _A($t, $q->[0], $q->[1]);
91 35349 _M($b, $b, $t);
92 35349 _M($c, $p->[3], $q->[3]);
93 35349 _M($c, $c, [ D2() ]);
94 35349 _M($d, $p->[2], $q->[2]);
95 35349 _A($d, $d, $d);
96 35349 _Z($e, $b, $a);
97 35349 _Z($f, $d, $c);
98 35349 _A($g, $d, $c);
99 35349 _A($h, $b, $a);
100  
101 35349 _M($p->[0], $e, $f);
102 35349 _M($p->[1], $h, $g);
103 35349 _M($p->[2], $g, $f);
104 35349 _M($p->[3], $e, $h);
105 }
106  
107 sub modL {
108 63 ▶ my ($r, $x) = @_;
Subroutine modL: called CC=6 SCAR=17.9
Pod undocumented
109  
110 63 my ($k);
111  
112 63 for my $i ( reverse( 32 .. 63 ) ) {
113 2016 my $carry = 0;
114  
115 2016 my ($j, $k);
116  
117 2016 ▶ for (
Branch: 1 branch
BranchTrueFalseTotal
if ($j < $k) 40320 2016 42336
118 ($j = $i - 32), ($k = $i - 12);
119 $j < $k;
120 ++$j
121 ) {
122 40320 $x->[$j] += $carry - 16 * $x->[$i] * (L())[$j - ($i - 32)];
123  
124 # originally “>> 8” rather than “/ 256”;
125 40320 $carry = Math::Utils::floor( ($x->[$j] + 128) / 256 );
126  
127 40320 $x->[$j] -= $carry * 256;
128 }
129  
130 2016 $x->[$j] += $carry;
131 2016 $x->[$i] = 0;
132 }
133  
134 63 my $carry = 0;
135  
136 # In Perl, -98 >> 4 = 1152921504606846969. :-<
137 63 my $x31_rshift_4 = Math::Utils::floor( $x->[31] / 16 );
138  
139 63 for my $j ( 0 .. 31 ) {
140 2016 $x->[$j] += $carry - $x31_rshift_4 * (L())[$j];
141  
142 # originally “>> 8” rather than “/ 256”; we also need floor
143 2016 $carry = Math::Utils::floor( $x->[$j] / 256 );
144  
145 2016 $x->[$j] &= 255;
146 }
147  
148 63 $x->[$_] -= $carry * (L())[$_] for 0 .. 31;
149  
150 63 for my $i ( 0 .. 31 ) {
151 2016 $x->[$i + 1] += $x->[$i] >> 8;
152 2016 $r->[$i] = $x->[$i] & 255;
153 }
154  
155 63 return;
156 }
157  
158 3 ▶use constant gf0 => (0) x 16;
Subroutine BEGIN: called CC=1 SCAR=0.0
159  
160 #----------------------------------------------------------------------
161  
162 3 ▶use constant gf1 => ( 1, (0) x 15 );
Subroutine BEGIN: called CC=1 SCAR=0.0
163  
164 3 use constant L => (
165 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
166 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
167 (0) x 15, 0x10,
168 3 ▶);
Subroutine BEGIN: called CC=1 SCAR=0.0
169  
170 3 use constant D2 => (
171 0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0,
172 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406,
173 3 ▶);
Subroutine BEGIN: called CC=1 SCAR=0.0
174  
175 3 use constant X => (
176 0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c,
177 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169,
178 3 ▶);
Subroutine BEGIN: called CC=1 SCAR=0.0
179  
180 3 use constant Y => (
181 0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666,
182 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666,
183 3 ▶);
Subroutine BEGIN: called CC=1 SCAR=0.0
184  
185 17568 ▶sub _S { _M( $_[0], $_[1], $_[1] ) }
Subroutine _S: called CC=1 SCAR=0.0
186  
187 sub _inv25519 {
188 48 ▶ my ($o, $i) = @_;
Subroutine _inv25519: called CC=4 SCAR=13.9
189  
190 48 my $c = [ @{$i}[0 .. 15] ];
191  
192 48 for my $a ( reverse( 0 .. 253 ) ) {
193 12192 _S($c, $c);
194  
195 12192 ▶ next if $a == 2;
Branch: 1 branch
BranchTrueFalseTotal
if $a == 2 48 12144 12192
196 12144 ▶ next if $a == 4;
Branch: 1 branch
BranchTrueFalseTotal
if $a == 4 48 12096 12144
197  
198 12096 _M( $c, $c, $i );
199 }
200  
201 48 @{$o}[0 .. 15] = @{$c}[0 .. 15];
202  
203 48 return;
204 }
205  
206 sub _pack25519 {
207 201 ▶ my ($n) = @_;
Subroutine _pack25519: called CC=5 SCAR=16.1
208  
209 201 my $b;
210  
211 201 my $o = [];
212  
213 201 my $t = [ @{$n}[0 .. 15] ];
214  
215 201 my $m = [ gf0() ];
216  
217 201 _car25519($t) for 1 .. 3;
218  
219 201 for my $j (0, 1) {
220 402 $m->[0] = $t->[0] - 0xffed;
221  
222 402 for my $i ( 1 .. 14 ) {
223 5628 $m->[$i] = $t->[$i] - 0xffff - (($m->[$i - 1] >> 16) & 1);
224 5628 $m->[$i - 1] &= 0xffff;
225 }
226  
227 402 $m->[15] = $t->[15] - 0x7fff - (($m->[14] >> 16) & 1);
228  
229 402 $b = ($m->[15] >> 16) & 1;
230  
231 402 $m->[14] &= 0xffff;
232  
233 402 _sel25519( $t, $m, 1 - $b );
234 }
235  
236 201 for my $i ( 0 .. 15 ) {
237 3216 $o->[2 * $i] = $t->[$i] & 0xff;
238 3216 $o->[2 * $i + 1] = $t->[$i] >> 8;
239 }
240  
241 201 return $o;
242 }
243  
244 sub _par25519 {
245 69 ▶ my ($a) = @_;
Subroutine _par25519: called CC=1 SCAR=0.0
246  
247 69 my $d = _pack25519($a);
248  
249 69 return $d->[0] & 1;
250 }
251  
252 # o, a, and b are arrays of numbers
253 sub _A {
254 176766 ▶ my ($o, $a, $b) = @_;
Subroutine _A: called CC=2 SCAR=6.9
255  
256 176766 $o->[$_] = $a->[$_] + $b->[$_] for 0 .. 15;
257  
258 176766 return;
259 }
260  
261 # o, a, and b are arrays of numbers
262 sub _Z {
263 141424 ▶ my ($o, $a, $b) = @_;
Subroutine _Z: called CC=2 SCAR=6.9
264  
265 141424 $o->[$_] = $a->[$_] - $b->[$_] for 0 .. 15;
266  
267 141424 return;
268 }
269  
270 # o, a, and b are arrays of numbers
271 sub _M {
272 353438 ▶ my ($o, $a, $b) = @_;
Subroutine _M: called CC=4 SCAR=13.9
273  
274 353438 my @t = (0) x 31;
275  
276 353438 for my $a_idx ( 0 .. 15 ) {
277 5655008 $t[$a_idx + $_] += $a->[$a_idx] * $b->[$_] for 0 .. 15;
278 }
279  
280 # $t->[15] left as-is
281 353438 for my $t_idx ( 0 .. 14 ) {
282 5301570 $t[$t_idx] += 38 * $t[16 + $t_idx];
283 }
284  
285 353438 my ($c, $v);
286  
287 353438 _car25519(\@t);
288 353438 _car25519(\@t);
289  
290 353438 @{$o}[0 .. 15] = @t[0 .. 15];
291  
292 353438 return;
293 }
294  
295 sub _car25519 {
296 707479 ▶ my ($o) = @_;
Subroutine _car25519: called CC=3 SCAR=11.0
297  
298 707479 my $c = 1;
299 707479 my $v;
300  
301 707479 for my $o_item ( @{$o}[0 .. 15] ) {
302 11319664 $v = $o_item + $c + 65535;
303  
304 # c = Math.floor(v / 65536)
305 11319664 $c = int( $v / 65536 );
306 11319664 ▶ $c-- if $v < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $v < 0 896259 10423405 11319664
307  
308 # t0 = v - c * 65536
309 11319664 $o_item = $v - ($c * 65536);
310 }
311  
312 707479 $o->[0] += $c - 1 + 37 * ($c - 1);
313  
314 707479 return;
315 }
316  
317 # p and q are arrays of numbers
318 sub _sel25519 {
319 141714 ▶ my ($p, $q, $b) = @_;
Subroutine _sel25519: called CC=6 SCAR=17.9
320  
321 # $b is either 0 or 1.
322 141714 ▶ my $c = $b && -1;
Condition100%2/2
$b && -1
!ll
7193369781
MC/DC100%1/1
$b && -1
$b
Truth table100%2/2
A
A= $b
Aresult
00
11
323  
324 141714 for my $i ( 0 .. 15 ) {
325 2267424 ▶ my $t = $c && ($c & signed_xor($p->[$i], $q->[$i]));
Condition100%3/3
$c && $c & signed_xor($p->[$i], $q->[$i])
!ll&&!rl&&r
115092824181114078
MC/DC100%2/2
$c && $c & signed_xor($p->[$i], $q->[$i])
$c $c & signed_xor($p->[$i], $q->[$i])
Truth table100%3/3
A && B
A= $cB= $c & signed_xor($p->[$i], $q->[$i])
ABresult
0X0
100
111
326  
327 2267424 ▶ $p->[$i] = signed_xor($p->[$i], $t) if $t;
Branch: 1 branch
BranchTrueFalseTotal
if $t 1114078 1153346 2267424
328 2267424 ▶ $q->[$i] = signed_xor($q->[$i], $t) if $t;
Branch: 1 branch
BranchTrueFalseTotal
if $t 1114078 1153346 2267424
329 }
330 }
331  
332 # p and q are arrays of arrays
333 sub _cswap {
334 35328 ▶ my ($p, $q, $b) = @_;
Subroutine _cswap: called CC=2 SCAR=6.9
335  
336 35328 for my $i ( 0 .. 3 ) {
337 141312 _sel25519( $p->[$i], $q->[$i], $b );
338 }
339 }
340  
341 # Perl’s ^ operator isn’t signed-savvy,
342 # so (-60116 ^ 0) = 18446744073709491500.
343 #
344 # TODO: add tests
345 sub signed_xor {
346  
347 3346668 ▶ if ( ($_[0] < 0) xor ($_[1] < 0) ) {
Subroutine signed_xor: called CC=3 SCAR=15.1
Pod undocumented
Branch: 1 branch
BranchTrueFalseTotal
if ($_[0] < 0 xor $_[1] < 0) 0 3346668 3346668
Condition25%1/4
$_[0] < 0 xor $_[1] < 0
l&&rl&&!r!l&&r!l&&!r
0003346668
MC/DC0%0/2
$_[0] < 0 xor $_[1] < 0
$_[0] < 0 $_[1] < 0
Truth table25%1/4
A xor B
A= $_[0] < 0B= $_[1] < 0
ABresult
110
101
011
000
348 0 return ($_[0] ^ $_[1]) - ~0 - 1;
349 }
350  
351 # signs are same -> can use native xor
352 3346668 return $_[0] ^ $_[1];
353 }
354  
355 sub signed_or {
356  
357 # signs are same -> can use native xor
358 2016 ▶ if ( ($_[0] < 0) eq ($_[1] < 0) ) {
Subroutine signed_or: called CC=2 SCAR=8.1
Pod undocumented
Branch: 1 branch
BranchTrueFalseTotal
if ($_[0] < 0 eq $_[1] < 0) 2016 0 2016
359 2016 return $_[0] | $_[1];
360 }
361  
362 0 return ($_[0] | $_[1]) - ~0 - 1;
363 }
364  
365 #----------------------------------------------------------------------
366 # Verify logic
367  
368 sub unpackneg {
369 21 ▶ my ($r, $p) = @_;
Subroutine unpackneg: called CC=5 SCAR=16.1
Pod undocumented
370  
371 21 $_ = [ gf0() ] for my (
372 $t,
373 $chk,
374 $num,
375 $den,
376 $den2,
377 $den4,
378 $den6,
379 );
380  
381 21 _set25519( $r->[2], [ gf1() ]);
382  
383 21 _unpack25519($r->[1], $p);
384  
385 21 _S($num, $r->[1]);
386 21 _M($den, $num, [ D() ]);
387 21 _Z($num, $num, $r->[2]);
388 21 _A($den, $r->[2], $den);
389  
390 21 _S($den2, $den);
391 21 _S($den4, $den2);
392 21 _M($den6, $den4, $den2);
393 21 _M($t, $den6, $num);
394 21 _M($t, $t, $den);
395  
396 21 _pow2523($t, $t);
397 21 _M($t, $t, $num);
398 21 _M($t, $t, $den);
399 21 _M($t, $t, $den);
400 21 _M($r->[0], $t, $den);
401  
402 21 _S($chk, $r->[0]);
403 21 _M($chk, $chk, $den);
404  
405 21 ▶ if (_neq25519($chk, $num)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_neq25519($chk, $num)) 8 13 21
406 8 _M($r->[0], $r->[0], [ I() ]);
407 }
408  
409 21 _S($chk, $r->[0]);
410 21 _M($chk, $chk, $den);
411  
412 21 ▶ if (_neq25519($chk, $num)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_neq25519($chk, $num)) 0 21 21
413 0 die "-1??";
414 }
415  
416 # “>>” appears to be safe here.
417 21 ▶ if (_par25519($r->[0]) == ($p->[31] >> 7)) {
Branch: 1 branch
BranchTrueFalseTotal
if (_par25519($r->[0]) == $p->[31] >> 7) 7 14 21
418 7 _Z($r->[0], [ gf0() ], $r->[0]);
419 }
420  
421 21 _M( $r->[3], $r->[0], $r->[1] );
422  
423 21 return 0;
424 }
425  
426 sub crypto_verify_32 {
427 63 ▶ my ($x, $xi, $y, $yi) = @_;
Subroutine crypto_verify_32: called CC=1 SCAR=0.0
Pod undocumented
428  
429 63 return _vn($x, $xi, $y, $yi, 32);
430 }
431  
432 3 use constant D => (
433 0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070,
434 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203,
435 3 ▶);
Subroutine BEGIN: called CC=1 SCAR=0.0
436  
437 3 use constant I => (
438 0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43,
439 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83,
440 3 ▶);
Subroutine BEGIN: called CC=1 SCAR=0.0
441  
442 sub _set25519 {
443 21 ▶ my ($r, $a) = @_;
Subroutine _set25519: called CC=2 SCAR=6.9
444  
445 21 $r->[$_] = $a->[$_] | 0 for 0 .. 15;
446 }
447  
448 sub _unpack25519 {
449 21 ▶ my ($o, $n) = @_;
Subroutine _unpack25519: called CC=2 SCAR=6.9
450  
451 21 for my $i (0 .. 15) {
452  
453 # originally “<< 8” rather than “256 *”
454 336 $o->[$i] = $n->[ 2 * $i ] + (256 * $n->[ 2 * $i + 1 ])
455 }
456  
457 21 $o->[15] &= 0x7fff;
458 }
459  
460 sub _pow2523 {
461 21 ▶ my ($o, $i) = @_;
Subroutine _pow2523: called CC=3 SCAR=11.0
462  
463 21 my $c = [ @{$i}[0 .. 15] ];
464  
465 21 for my $a ( reverse( 0 .. 250 ) ) {
466 5271 _S( $c, $c );
467  
468 5271 ▶ if ($a != 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($a != 1) 5250 21 5271
469 5250 _M( $c, $c, $i );
470 }
471 }
472  
473 21 @{$o}[0 .. 15] = @{$c}[0 .. 15];
474 }
475  
476 sub _neq25519 {
477 42 ▶ my ($a, $b) = @_;
Subroutine _neq25519: called CC=1 SCAR=0.0
478  
479 42 my $c = _pack25519($a);
480 42 my $d = _pack25519($b);
481  
482 42 return crypto_verify_32($c, 0, $d, 0);
483 }
484  
485 sub _vn {
486 63 ▶ my ($x, $xi, $y, $yi, $n) = @_;
Subroutine _vn: called CC=2 SCAR=6.9
487  
488 63 my $d = 0;
489  
490 63 for my $i ( 0 .. ($n - 1) ) {
491 2016 $d = signed_or( $d, signed_xor($x->[ $xi + $i ], $y->[ $yi + $i ]) );
492 }
493  
494 # Originally “>>> 8”, which appears to be JS’s equivalent
495 # operator to Perl’s >>.
496 63 return (1 & (($d - 1) >> 8)) - 1;
497 }
498  
499 3 1;
« blib/lib/Crypt/Perl/RSA/Parse.pm ↑ Summary blib/lib/Crypt/Perl/KeyBase.pm »