Cryptography Reference
In-Depth Information
2
3
while the standard computation will require
(
)
+
(
)
proportional to 4len
p
2len
p
3
).
This algorithm is implemented in Maple as follows:
(
)
time proportional to 8len
p
> ChineseModExp :=
(m,e,p,q) -> chrem([Power(m,e mod (p-1)) mod p,Power(m,e mod (q-1)) mod q],[p,q]):
Example 2.16
We perform an experiment to test whether the running times of the
two exponentiation algorithms—with and without the CRT—in Maple behave as
expected. For this wewill use two 1024-bit primes and an exponent chosen as follows:
> p := nextprime(2ˆ1023):
q := prevprime(2ˆ1024):
n := p*q:
e := rand(1..(p-1)*(q-1))():
e1:= e mod (p-1):
e2:= e mod (q-1):
We remark that the primes
p
and
q
above are decidedly non-random and are not
suitable for cryptographic use but they are OK for the purposes of this experiment.
The next function performs
k
modular exponentiations (where
k
is a positive integer)
and outputs the CPU time spent. Note that the bases
m
are chosen bymeans ofMaple's
default pseudo-random algorithm
7
in the range
2
..
n
−
2
.
In fact, we do not seed this
generator (this would be accomplished, for example, by the use of
randomize()
)
so that, after calling
restart
, the same sequence of bases is always obtained. This
way, these bases are far from random but we can use the same ones to compare the
speed of the two methods.
> ChineseTimeTest := proc(k)
local i, m, x, t;
t := time();
foritokdo
m := (rand(2 .. n-2))();
x := chrem([Power(m, e1) mod p, Power(m, e2) mod q], [p, q]);
end do;
time()-t
end proc:
The next function is similar to the preceding one and records the time spent by
Maple's modular exponentiation algorithm without using the CRT. As mentioned
before, after a
restart
and the recomputation of the primes and the exponent, the
same numbers will be used in both tests.
> TimeTest := proc(k)
local i, m, x, t;
t := time();
foritokdo
m := (rand(2 .. n-2))();
x := Power(m, e) mod n;
end do;
time()-t
end proc:
