240 lines
6.2 KiB
HTML
240 lines
6.2 KiB
HTML
<html>
|
|
|
|
<body BGCOLOR="#00E0E0" link="#001fC0" vlink="#000080" text="#00000f">
|
|
|
|
|
|
<h1><title> Mathematics of Large Exponents : Algorithms for Tackling extremely large intermediate results </title></h1>
|
|
<h1>Mathematics of Large Exponents : Algorithms for Tackling extremely large intermediate results </h1>
|
|
|
|
|
|
Consider a 256 bit capable key.
|
|
<p>
|
|
The Modulus (n) must be greater than 2<sup>256</sup>.
|
|
<p>
|
|
This number represented in decimal is very large.
|
|
90 odd decimal digits !
|
|
<p>
|
|
2^256 == 115792089237316195423570985008687907853269984665640564039457584007913129639936
|
|
</p>
|
|
|
|
<p>
|
|
Compared to the numbers generated by raising large numbers to large exponents,
|
|
though, 2<sup>256</sup> seems quite trivial.
|
|
</p>
|
|
|
|
The RSA encryption algorithms are based on taking large numbers
|
|
to the power of a key value, and then applying the modulus
|
|
of that result with a large pre-calculated value (n) based on a
|
|
prime number multiplication.
|
|
|
|
<h3>encoded = c<sup>d</sup>%n</h3>
|
|
|
|
<p>
|
|
For instance 2<sup>256</sup> to the power of a 6 digit key (say 5,000,000)
|
|
produces a number of approximately <b> 385,318,394 </b> digits !
|
|
</p>
|
|
|
|
<p>
|
|
Obviously, such large intermediate results are impractical.
|
|
For the purpose of this tool, intermediate values with up to
|
|
100,000 digits are shown (and can be dealt with directly using the
|
|
<a href="bc.html"> unix bc utility </a>).
|
|
</p>
|
|
|
|
<p>
|
|
An effective way to break this problem down is to use results from
|
|
<a href="http://mathworld.wolfram.com/Residue.html"> residue theory </a>.
|
|
|
|
From
|
|
<a href="http://mathworld.wolfram.com/Residue.html"> residue theory </a>
|
|
we can state that where d is even:
|
|
<p>
|
|
<center> <b> c<sup>d</sup>%n == ((c^2%n)<sup>d/2</sup>)%n </b> </center>
|
|
</p>
|
|
If d is an integer power of 2, (i.e. d == 2<sup>n</sup> where
|
|
n is a positive integer) this can be extended to a recursive algorithm.
|
|
|
|
<h3> Recursive algorithm for simplifying equations of the form
|
|
c<sup>d</sup>%n where d is an integer power of 2 </h3>
|
|
|
|
<hr>
|
|
<pre>
|
|
calc_residue ( bigint c, bigint d, bigint n ) {
|
|
if ( d == 1 ) return ( c ^ d % n );
|
|
return calc_residue ( c^2, d/2, n ) % n; # recursion
|
|
}
|
|
</pre>
|
|
<hr>
|
|
|
|
This is all very well, and solves the large exponentiation problem.
|
|
But most exponents used in RSA are not integer powers of 2 !
|
|
Some way of breaking the exponent up and handling each integer power
|
|
of 2 part is required.
|
|
|
|
<h3>Breaking down exponent to Powers of 2 As pseudo code</h3>
|
|
|
|
|
|
Consider for instance the number 323
|
|
can be represented by
|
|
<p>
|
|
<center> <b> 323 == 2<sup>8</sup> + 2<sup>6</sup> + 2<sup>1</sup> + 2<sup>0</sup> </b> </center>
|
|
<p>
|
|
|
|
Thus 'c' to the power of 323, could be written as
|
|
(where ^ means to the power of, as in c and bc scripts)
|
|
|
|
<p>
|
|
<center> <b>c<sup>(2^8+2^6+2^1+2^0)</sup></b> </center>
|
|
<p>
|
|
<br>
|
|
|
|
<p>
|
|
or written as
|
|
<p>
|
|
<center> <b>c<sup>2^8</sup>*c<sup>2^6</sup>*c<sup>2^1</sup>*c<sup>2^0</sup></b> </center>
|
|
<p>
|
|
In this form it is easy to see that any exponent can be broken down into
|
|
powers of two for processing by the <b>calc_residues</b> algorithm.
|
|
|
|
<p>
|
|
The following pseudo code takes the variable d, and breaks it down into
|
|
into its integer power of 2 parts.
|
|
</P>
|
|
|
|
<hr>
|
|
<pre>
|
|
|
|
break_down_into_powers_of_two ( bigint d ) {
|
|
|
|
|
|
integer i = 0;
|
|
|
|
# find biggest power of 2 left in exponentiation
|
|
#
|
|
while(d >= (2^i)) { i = i+1; }
|
|
|
|
# subtract highest power of 2 possible from d
|
|
#
|
|
d = (d - (2^(i-1)));
|
|
|
|
PRINT (2^(i-1));
|
|
|
|
if (d>0) {
|
|
# d is greater than 0 so we need to break this down further
|
|
#
|
|
break_down_into_powers_of_two(d); # recurse with new d value
|
|
return (2^(i-1));
|
|
}
|
|
if (d == 0) {
|
|
# d is 0, we have found the last power of 2 required
|
|
#
|
|
return (2^(i-1);
|
|
}
|
|
}
|
|
</pre>
|
|
<hr>
|
|
|
|
In order to implement code that can process any
|
|
d exponent in a c^d%n equation in a <a href="bc.html">bc</a>
|
|
script the problem has been divided into two distinct
|
|
but linked stages:
|
|
<ul>
|
|
<li> Recursively break down the exponent into powers of two </li>
|
|
<li> Recursively process each power of two c<sup>d</sup>%n equation </li>
|
|
</ul>
|
|
|
|
|
|
<h3> Script to calculate c<sup>d</sup>%n equations without incredibly large intermediate results</h3>
|
|
|
|
Integrating these together produces the following
|
|
<a href="bc.html">bc</a> program.
|
|
<hr>
|
|
<pre>
|
|
# bc program. Call with -q parameter
|
|
# R.P. Clark 10APR2004
|
|
|
|
# recursive routine to calculate c^d%n
|
|
# by breaking it down. Works only where
|
|
# d is a power of 2.
|
|
#
|
|
define x ( c,d,n) {
|
|
if ( d == 1 ) return (c^d%n);
|
|
return x(c^2,d/2,n)%n;
|
|
}
|
|
|
|
r = 1;
|
|
|
|
# recursive routine to break d into powers of 2
|
|
# and then to collect multiply the results
|
|
# of the 2^n exponents.
|
|
#
|
|
define t(c,d,n) {
|
|
auto i
|
|
i = 0;
|
|
|
|
# find biggest power of 2 left in exponentiation
|
|
#
|
|
while(d >= (2^i)) { i = i+1; }
|
|
|
|
# subtract from exponent
|
|
#
|
|
d = (d - (2^(i-1)));
|
|
|
|
|
|
if (d>0) {
|
|
r=(r*x(c,2^(i-1),n))%n; # calculate this large exponentiation
|
|
t(c,d,n); # recursion with new d value
|
|
return (2^(i-1));
|
|
}
|
|
if (d == 0) {
|
|
r = (r*x(c,2^(i-1),n))%n; # last one
|
|
return (2^(i-1));
|
|
}
|
|
}
|
|
</pre>
|
|
<hr>
|
|
<p>
|
|
Thus the function t(c,d,n), will break down the exponent,
|
|
and pass it on as powers of 2, to calculate the residues using
|
|
the 'x' function. Thus very large
|
|
exponentiation and mod
|
|
equations,will be calculated without having to handle
|
|
incredibly large intermediate results.
|
|
</p>
|
|
|
|
Some results, of timings for the equation
|
|
<b>21255511<sup>266511</sup>%999999</b> run
|
|
on a 1 Ghz Celeron laptop (Redhat 8.0 : <a href="bc.html">bc</a> version 1.06).
|
|
Note that larger numbers than
|
|
this in the exponent
|
|
are rejected by bc.
|
|
<p>
|
|
To see how large <b>21255511<sup>266511</sup></b> is,
|
|
a text file containing it is included <a href="21255511to266511.txt"> here </a>.
|
|
</p>
|
|
<pre>
|
|
[robin@localhost bc]$ date; bc < calc_big_expon.bc | tail -1; date
|
|
Sun Apr 11 17:21:10 BST 2004
|
|
407926
|
|
Sun Apr 11 17:26:37 BST 2004
|
|
[robin@localhost bc]$ date ; echo "21255511^266511%999999" | bc ; date
|
|
Sun Apr 11 17:36:13 BST 2004
|
|
407926
|
|
Sun Apr 11 17:43:29 BST 2004
|
|
[robin@localhost bc]$ bc -v
|
|
bc 1.06
|
|
</pre>
|
|
|
|
|
|
Thus the recursive algorithm is faster, and large exponents are
|
|
not rejected.
|
|
|
|
<br>
|
|
<br>
|
|
<center>
|
|
<a href="javascript:history.back();">
|
|
<img src=back.png align=center border=0> </a>
|
|
</center>
|
|
</body>
|
|
</html>
|