File Coverage

blib/lib/Crypt/DSA/Util.pm
Criterion Covered Total %
statement 81 96 84.4
branch 17 32 53.1
condition 5 6 83.3
subroutine 14 16 87.5
pod 5 9 55.6
total 122 159 76.7


line stmt bran cond sub pod time code
1             # $Id: Util.pm 1938 2006-05-03 06:20:36Z btrott $
2              
3             package Crypt::DSA::Util;
4 7     7   3547 use strict;
  7         269  
  7         183  
5              
6 7     7   111 use Math::BigInt lib => 'GMP';
  7         63  
  7         219  
7 7     7   114 use Fcntl;
  7         65  
  7         144  
8 7     7   814 use Carp qw( croak );
  7         69  
  7         145  
9              
10 7     7   139 use vars qw( @EXPORT_OK @ISA );
  7         62  
  7         134  
11 7     7   107 use Exporter;
  7         64  
  7         114  
12             @EXPORT_OK = qw( bitsize bin2mp mp2bin mod_inverse mod_exp makerandom isprime );
13             @ISA = qw( Exporter );
14              
15             ## Nicked from Crypt::RSA::DataFormat.
16             ## Copyright (c) 2001, Vipul Ved Prakash.
17             sub bitsize {
18 22     22 1 328     length(Math::BigInt->new($_[0])->as_bin) - 2;
19             }
20              
21             sub bin2mp {
22 440     440 1 6459     my $s = shift;
23 440 100       10111     $s eq '' ?
24                     Math::BigInt->new(0) :
25                     Math::BigInt->new("0b" . unpack("B*", $s));
26             }
27              
28             sub mp2bin {
29 3     3 1 43     my $p = Math::BigInt->new(shift);
30 3         307     my $base = Math::BigInt->new(256);
31 3         226     my $res = '';
32 3         36     while ($p != 0) {
33 41         490         my $r = $p % $base;
34 41         440         $p = ($p-$r) / $base;
35 41         461         $res = chr($r) . $res;
36                 }
37 3         976     $res;
38             }
39              
40             sub mod_exp {
41 26     26 1 313     my($a, $exp, $n) = @_;
42 26         344     $a->copy->bmodpow($exp, $n);
43             }
44              
45             sub mod_inverse {
46 10     10 1 101     my($a, $n) = @_;
47 10         125     $a->copy->bmodinv($n);
48             }
49              
50             sub makerandom {
51 9     9 0 4840     my %param = @_;
52 9         260     my $size = $param{Size};
53 9         138     my $bytes = int($size / 8) + 1;
54 9         156     my $r = '';
55 9 50       432     if ( sysopen my $fh, '/dev/random', O_RDONLY ) {
    0          
56 9         2045         my $read = 0;
57 9         114         while ($read < $bytes) {
58 9         2711             my $got = sysread $fh, my($chunk), $bytes - $read;
59 9 50       448             next unless $got;
60 9 50       136             die "Error: $!" if $got == -1;
61 9         89             $r .= $chunk;
62 9         100             $read = length $r;
63                     }
64 9         189         close $fh;
65                 }
66                 elsif ( require Data::Random ) {
67 0         0         $r .= Data::Random::rand_chars( set=>'numeric' ) for 1..$bytes;
  0         0  
68                 }
69                 else {
70 0         0         croak "makerandom requires /dev/random or Data::Random";
71                 }
72 9         133     my $down = $size - 1;
73 9 50       705     $r = unpack 'H*', pack 'B*', '0' x ( $size % 8 ? 8 - $size % 8 : 0 ) .
74                     '1' . unpack "b$down", $r;
75 9         241     Math::BigInt->new('0x' . $r);
76             }
77              
78             # For testing, let us choose our isprime function:
79             *isprime = \&isprime_algorithms_with_perl;
80              
81             # from the book "Mastering Algorithms with Perl" by Jon Orwant,
82             # Jarkko Hietaniemi, and John Macdonald
83             sub isprime_algorithms_with_perl {
84 7     7   156     use integer;
  7         67  
  7         122  
85 107     107 0 14380     my $n = shift;
86 107         3113     my $n1 = $n - 1;
87 107         1785     my $one = $n - $n1; # not just 1, but a bigint
88 107         1592     my $witness = $one * 100;
89              
90             # find the power of two for the top bit of $n1
91 107         41914     my $p2 = $one;
92 107         1278     my $p2index = -1;
93 107         1221     ++$p2index, $p2 *= 2
94             while $p2 <= $n1;
95 107         1221     $p2 /= 2;
96              
97             # number of interations: 5 for 260-bit numbers, go up to 25 for smaller
98 107         108689     my $last_witness = 5;
99 107 100       1276     $last_witness += (260 - $p2index) / 13 if $p2index < 260;
100              
101 107         1115     for my $witness_count (1..$last_witness) {
102 122         1264 $witness *= 1024;
103 122         1432 $witness += int(rand(1024)); # XXXX use good rand
104 122 50       1508 $witness = $witness % $n if $witness > $n;
105 122 50       101369 $witness = $one * 100, redo if $witness == 0;
106              
107 122         162045 my $prod = $one;
108 122         1211 my $n1bits = $n1;
109 122         1022 my $p2next = $p2;
110              
111             # compute $witness ** ($n - 1)
112 122         983 while (1) {
113 58240   100     3062001 my $rootone = $prod == 1 || $prod == $n1;
114 58240         2139206 $prod = ($prod * $prod) % $n;
115 58240 50 66     3197748 return 0 if $prod == 1 && ! $rootone;
116 58240 100       1583547 if ($n1bits >= $p2next) {
117 29252         1253544 $prod = ($prod * $witness) % $n;
118 29252         1262094 $n1bits -= $p2next;
119             }
120 58240 100       2276571 last if $p2next == 1;
121 58118         1995360 $p2next /= 2;
122             }
123 122 100       1540 return 0 unless $prod == 1;
124                 }
125 2         579     return 1;
126             }
127              
128             sub isprime_gp_pari {
129 0     0 0       my $n = shift;
130              
131 0               my $sn = "$n";
132 0 0             die if $sn =~ /\D/;
133              
134 0               my $is_prime = `echo "isprime($sn)" | gp -f -q`;
135 0 0             die "No gp installed?" if $?;
136              
137 0               chomp $is_prime;
138 0               return $is_prime;
139             }
140              
141             sub isprime_paranoid {
142 0     0 0       my $n = shift;
143              
144 0               my $perl = isprime_algorithms_with_perl($n);
145 0               my $pari = isprime_gp_pari($n);
146              
147 0 0             die "Perl vs. PARI don't match on '$n'\n" unless $perl == $pari;
148 0               return $perl;
149             }
150              
151             1;
152             __END__
153            
154             =head1 NAME
155            
156             Crypt::DSA::Util - DSA Utility functions
157            
158             =head1 SYNOPSIS
159            
160             use Crypt::DSA::Util qw( func1 func2 ... );
161            
162             =head1 DESCRIPTION
163            
164             I<Crypt::DSA::Util> contains a set of exportable utility functions
165             used through the I<Crypt::DSA> set of libraries.
166            
167             =head2 bitsize($n)
168            
169             Returns the number of bits in the I<Math::Pari> integer object
170             I<$n>.
171            
172             =head2 bin2mp($string)
173            
174             Given a string I<$string> of any length, treats the string as a
175             base-256 representation of an integer, and returns that integer,
176             a I<Math::Pari> object.
177            
178             =head2 mp2bin($int)
179            
180             Given a biginteger I<$int> (a I<Math::Pari> object), linearizes
181             the integer into an octet string, and returns the octet string.
182            
183             =head2 mod_exp($a, $exp, $n)
184            
185             Computes $a ^ $exp mod $n and returns the value. The calculations
186             are done using I<Math::Pari>, and the return value is a I<Math::Pari>
187             object.
188            
189             =head2 mod_inverse($a, $n)
190            
191             Computes the multiplicative inverse of $a mod $n and returns the
192             value. The calculations are done using I<Math::Pari>, and the
193             return value is a I<Math::Pari> object.
194            
195             =head1 AUTHOR & COPYRIGHTS
196            
197             Please see the Crypt::DSA manpage for author, copyright,
198             and license information.
199            
200             =cut
201