Cryptography Reference
In-Depth Information
Exercise 8.22
Write a Maple function that generates public and private keys for
Rabin encryption. On input a security parameter
k
and two random seeds, it should
pseudo-randomly generate two
k
-bit Blumprimes whose product is a 2
k
-bit modulus.
Make the function able to output Rabin keys in either decimal or hexadecimal format
(as byte strings in the latter case).
Exercise 8.23
Modify the functions
Rabin
and
InvRabin
so that they accept as
argument the public and private Rabin keys, respectively, generated by the function
defined in the previous exercise, either in decimal or in hexadecimal format.
Exercise 8.24
Modify the function
InvRabin
to make it check that both
p
and
q
are Blum primes.
Example 8.11
Let us give an example of how the functions
Rabin
and
InvRabin
work. We will consider the RSA key
rsakey
generated in Example 8.10, whose
2048-bit modulus is a product of two 1024-bit Blum primes
p
,
q
.Weset:
> drsakey := convert
∼∼
(rsakey, decimal, hex);
rkey := [drsakey[1][1], op(drsakey[2][3 .. 4]), op(drsakey[2][7 .. 8])]:
This way,
rkey
is a Rabin key of the form
pq
and
p
,
q
are Blum primes. Let us now check the behavior of
Rabin
and
InvRabin
.
Choose, for example,
m
[
n
,
p
,
q
,
pinv
,
qinv
]
, where
n
=
∈ Z
n
and apply
Rabin
followed by
InvRabin
:
> InvRabin(Rabin(10ˆ600, rkey[1]), op(rkey[2 .. 5]));
[1000000000000000000000000000000[...540 digits...]000000000000000000000000000000,
2697428680153510286212176381377257718558715581015565487856686059687370986773...,
9961089806046858479115662813501211939956485381862914110892706751012786491829...,
1701319699548824538300610100027136524563067042829274076767415384586092337590...]
We have recovered the four square roots of 10
1200
mod
n
which is the image
of 10
600
under the map
Rabin(-,n)
. Note that the first root is precisely 10
600
.
Now, observe that 10
600
is obviously a quadratic residue in
10
600
:=
Z
n
and so we may do the
analogous computation using the Blum-Williams function
BW
n
:
> InvRabin(Rabin(10ˆ600, rkey[1]), op(rkey[2 .. 5]), BW = true);
1000000000000000000000000000000[...540 digits...]000000000000000000000000000000
In this case, we used the option
BW = true
and so the result of successively
applying the Blum-Williams permutation and its inverse to 10
600
is, again, this same
number.
Example 8.12
We use the key
rkey
in the previous example to illustrate how the
modulus can be factored—and hence the scheme can be broken—given oracle access
to the decryption function. The decryption function is given here by the inverseBlum-
Williams function implemented above and, for the purpose of this example, we may
assume that the function is simulating the decryption oracle and acting as a black
box, so that we do not need to know the prime factors of the modulus and only need
to know the result of applying the function to the elements we submit. For brevity,
let us call this modulus
n
, that is:
> n := rkey[1]:
To factor the modulus we follow the method sketched just after Proposition 8.6.
Instead of taking a random element of
Z
n
, we will start by taking a small element
