2 /** @package php-gpg::GPG */
\r
4 /** assign globals */
\r
17 $bdm = (1 << $bd) - 1;
\r
37 echo("string too short, not a MPI");
\r
41 $len = ($sn - 2) * 8;
\r
42 $bits = ord($s[0]) * 256 + ord($s[1]);
\r
43 if ($bits > $len || $bits < $len - 8) {
\r
44 echo("not a MPI, bits = $bits, len = $len");
\r
48 for ($n = 0; $n < $len; $n++) {
\r
49 if (($sb <<= 1) > 255) {
\r
50 $sb = 1; $c = ord($s[--$sn]);
\r
56 if ($c & $sb) $r[$rn] |= $bn;
\r
79 $bits = count($b) * $bs;
\r
83 for ($n = 0; $n < $bits; $n++) {
\r
84 if ($b[$bc] & $bn) $r[$rn] |= $rb;
\r
85 if(($rb <<= 1) > 255) {
\r
86 $rb = 1; $r[++$rn]=0;
\r
88 if (($bn <<= 1) > $bm) {
\r
93 while ($rn && $r[$rn]==0) $rn--;
\r
96 for($bits = 8; $bits > 0; $bits--) if ($r[$rn] & ($bn >>= 1)) break;
\r
99 $rr .= chr($bits / 256 ) . chr($bits % 256);
\r
100 if ($bits) for($n = $rn; $n >= 0; $n--) $rr .= chr($r[$n]);
\r
107 function bmodexp($xx, $y, $m) {
\r
118 $x = array_merge((array)$xx);
\r
119 $n = count($m) * 2;
\r
120 $mu = array_fill(0, $n + 1, 0);
\r
123 for(; $n >= 0; $n--) $mu[$n] = 0;
\r
124 $dd = new bdiv($mu, $m);
\r
127 for($n = 0; $n < count($y); $n++) {
\r
128 for ($a = 1, $an = 0; $an < $bs; $an++, $a <<= 1) {
\r
129 if ($y[$n] & $a) $r = bmod2(bmul($r, $x), $m, $mu);
\r
130 $x = bmod2(bmul($x, $x), $m, $mu);
\r
139 function simplemod($i, $m) // returns the mod where m < 2^bd
\r
143 for ($n = count($i) - 1; $n >= 0; $n--)
\r
146 $c = (($v >> $bd) + ($c << $bd)) % $m;
\r
147 $c = (($v & $bdm) + ($c << $bd)) % $m;
\r
155 function bmod($p, $m) // binary modulo
\r
159 if (count($m) == 1) {
\r
160 if(count($p) == 1) return array($p[0] % $m[0]);
\r
161 if($m[0] < $bdm) return array(simplemod($p, $m[0]));
\r
164 $r = new bdiv($p, $m);
\r
170 function bmod2($x, $m, $mu) {
\r
171 $xl = count($x) - (count($m) << 1);
\r
172 if ($xl > 0) return bmod2(array_concat(array_slice($x, 0, $xl), bmod2(array_slice($x, $xl), $m, $mu)), $m, $mu);
\r
174 $ml1 = count($m) + 1;
\r
175 $ml2 = count($m) - 1;
\r
178 $q3 = array_slice(bmul(array_slice($x, $ml2), $mu), $ml1);
\r
179 $r1 = array_slice($x, 0, $ml1);
\r
180 $r2 = array_slice(bmul($q3, $m), 0, $ml1);
\r
182 $r = bsub($r1, $r2);
\r
183 if (count($r) == 0) {
\r
185 $r = bsub($r1, $r2);
\r
187 for ($n = 0;; $n++) {
\r
188 $rr = bsub($r, $m);
\r
189 if(count($rr) == 0) break;
\r
191 if($n >= 3) return bmod2($r, $m, $mu);
\r
199 function toppart($x, $start, $len) {
\r
203 while ($start >= 0 && $len-- > 0) $n = $n * $bx2 + $x[$start--];
\r
210 function zeros($n) {
\r
211 $r = array_fill(0, $n, 0);
\r
212 while ($n-- > 0) $r[$n] = 0;
\r
217 * @package verysimple::Encryption
\r
222 function bdiv($x, $y)
\r
231 $n = count($x) - 1;
\r
232 $t = count($y) - 1;
\r
235 if ($n < $t || $n == $t && ($x[$n] < $y[$n] || $n > 0 && $x[$n] == $y[$n] && $x[$n - 1] < $y[$n - 1])) {
\r
236 $this->q = array(0);
\r
237 $this->mod = array($x);
\r
241 if ($n == $t && toppart($x, $t, 2) / toppart($y, $t, 2) < 4) {
\r
245 $xx = bsub($x, $y);
\r
246 if(count($xx) == 0) break;
\r
249 $this->q = array($qq);
\r
254 $shift2 = floor(log($y[$t]) / M_LN2) + 1;
\r
255 $shift = $bs - $shift2;
\r
257 $x = array_merge((array)$x); $y = array_merge((array)$y);
\r
258 for($i = $t; $i > 0; $i--) $y[$i] = (($y[$i] << $shift) & $bm) | ($y[$i - 1] >> $shift2);
\r
259 $y[0] = ($y[0] << $shift) & $bm;
\r
260 if($x[$n] & (($bm << $shift2) & $bm)) {
\r
261 $x[++$n] = 0; $nmt++;
\r
263 for($i = $n; $i > 0; $i--) $x[$i] = (($x[$i] << $shift) & $bm) | ($x[$i - 1] >> $shift2);
\r
264 $x[0] = ($x[0] << $shift) & $bm;
\r
270 $q = zeros($nmt + 1);
\r
271 $y2 = array_merge(zeros($nmt), (array)$y);
\r
273 $x2 = bsub($x, $y2);
\r
274 if(count($x2) == 0) break;
\r
280 $top =toppart($y, $t, 2);
\r
281 for ($i = $n; $i > $t; $i--) {
\r
283 if ($i >= count($x)) $q[$m] = 1;
\r
284 else if($x[$i] == $yt) $q[$m] = $bm;
\r
285 else $q[$m] = floor(toppart($x, $i, 2) / $yt);
\r
287 $topx = toppart($x, $i, 3);
\r
288 while ($q[$m] * $top > $topx) $q[$m]--;
\r
290 $y2 = array_slice($y2, 1);
\r
291 $x2 = bsub($x, bmul(array($q[$m]), $y2));
\r
292 if (count($x2) == 0) {
\r
294 $x2 =bsub($x, bmul(array($q[m]), $y2));
\r
300 for($i = 0; $i < count($x) - 1; $i++) $x[$i] = ($x[$i] >> $shift) | (($x[$i + 1] << $shift2) & $bm);
\r
301 $x[count($x) - 1] >>= $shift;
\r
304 while ($n > 1 && $q[$n - 1] == 0) $n--;
\r
305 $this->q = array_slice($q, 0, $n);
\r
307 while ($n > 1 && $x[$n - 1] == 0) $n--;
\r
308 $this->mod = array_slice($x, 0, $n);
\r
314 function bsub($a, $b) {
\r
325 if ($bl > $al) return array();
\r
327 if($b[$bl - 1] > $a[$bl - 1]) return array();
\r
328 if($bl == 1) return array($a[0] - $b[0]);
\r
331 $r = array_fill(0, $al, 0);
\r
334 for ($n = 0; $n < $bl; $n++) {
\r
335 $c += $a[$n] - $b[$n];
\r
339 for (; $n < $al; $n++) {
\r
344 if ($c) return array();
\r
346 if ($r[$n - 1]) return $r;
\r
347 while ($n > 1 && $r[$n - 1] == 0) $n--;
\r
349 return array_slice($r, 0, $n);
\r
354 function bmul($a, $b) {
\r
362 $b = array_merge((array)$b, array(0));
\r
377 $r = zeros($al + $bl + 1);
\r
379 for ($n = 0; $n < $al; $n++) {
\r
383 $hh = $aa >> $bd; $h = $aa & $bdm;
\r
385 for ($nn = 0; $nn < $bl; $nn++, $m++) {
\r
386 $g = $b[$nn]; $gg = $g >> $bd; $g = $g & $bdm;
\r
387 $ghh = $g * $hh + $h * $gg;
\r
388 $ghhb = $ghh >> $bd; $ghh &= $bdm;
\r
389 $c += $r[$m] + $h * $g + ($ghh << $bd);
\r
391 $c = ($c >> $bs) + $gg * $hh + $ghhb;
\r
397 if ($r[$n - 1]) return $r;
\r
398 while ($n > 1 && $r[$n - 1] == 0) $n--;
\r
400 return array_slice($r, 0, $n);
\r