Cryptography Reference
In-Depth Information
Exercise 8.9
Modify
RSAKeyGen
in order to make it more efficient when
e
is
small. This requires modifying
RSAPrime
to make it test whether a prime candidate
x
satisfies the condition gcd
(
x
−
1
,
e
)
=
1 before submitting
x
to a primality test.
Exercise 8.10
Modify
RSAKeyGen
in order to provide the option of generating the
encryption exponent in a pseudo-random way.
Exercise 8.11
Modify
RSAKeyGen
so that it chooses a 2
k
-bit modulus
n
that is
a product of two
k
-bit primes
p
,
q
, where
p
and
q
are pseudo-randomly chosen in
the interval
2
(
2
k
−
1
)/
2
2
k
[
,
−
1
]
. To find the primes, use Blum-Blum-Shub to choose
2
k
−
1
2
k
2
(
2
k
−
1
)/
2
.
candidates in the interval
[
,
−
1
]
and discard themwhen they are
<
Exercise 8.12
Define a Maple function that, on input an RSA key in the format
output by
RSAKeyGen
, checks compliance with the definition by making sure that
ed
≡
(
(
−
)(
−
))
1
mod
p
1
q
1
. Additional checks such as testing
p
and
q
for
primality could also be included.
Exercise 8.13
Write a variant of
RSAKeyGen
that generates RSA keys in which
the decryption exponent corresponding to the public key
(
n
,
e
)
is the inverse of
e
Z
λ(
n
)
Z
φ(
n
)
in
instead of the inverse in
. (Hint: Since the factorization of
n
=
pq
is
known,
λ(
n
)
may be efficiently computed as
λ(
n
)
=
lcm
(
p
−
1
,
q
−
1
)
=
(
p
−
1
)
(
q
−
1
)/
gcd
(
p
−
1
,
q
−
1
)
. Maple's built-in function
numtheory:-lambda
computes
but cannot be used for our purpose because it tries to factor
n
, which
should be infeasible.)
λ(
n
)
We are now ready to give the plain RSA encryption and decryption functions. As
we have mentioned, RSA is mainly used for short messages that can be encrypted
in just one encryption operation (a modular exponentiation). However, we will also
allow longer plaintexts that will be dealt with by dividing them into smaller blocks in
the form explained above. Although it is easy to deal with plaintexts and ciphertexts
given as files, in the same way we have seen for private-key encryption schemes, in
the following we will deal exclusively with plaintexts and ciphertexts given as Maple
strings and we leave to the reader the task of making the straightforward adaptations
to deal with messages in file format.
We will start with a function called
bytestoblocks
that does the low-level
conversion of a list of integers in the 0
255 range (bytes) of suitable size to 'blocks'
that are ready to be processed by the RSA encryption function. The higher level
encryption function will convert the plaintext string to a list of bytes using the 8-bit
ASCII codes and then this list will be processed by this function that will partition
it in suitable sublists (or blocks) each of which may be regarded as the integer in
base 256 it defines, which will be close in size to but strictly smaller than the RSA
modulus. This is achieved by forming the blocks in such a way that the number of
bytes in each block is just one less than the number of digits (or bytes) of the modulus
in base 256. The function converts a list of bytes given by the parameter
lis
to a
list of blocks (lists of bytes) of length specified by the parameter
length
:
..
