Public-Key Encryption - Introduction to Cryptography with Maple - page 508

8.6.2 A Variant of the Cramer-Shoup Encryption Scheme
in Maple

We are going to give a simple Maple implementation of a variant of Cramer-Shoup
using the algorithm of [57] (algorithm CS1a in [59]) in the setting described in [59,
Example 1, Example 2]. G will be a cyclic group of order q , where q is a Sophie
Germain prime, which means that p = QR p ⊆ Z p .

= 2 q + 1 is (a safe) prime and G

Z p and its elements are precisely the Thus G is the unique subgroup of order q of

Z p .
In the Cramer-Shoup scheme there are several elements that must be randomly
chosen but we cannot use Maple for this purpose. These elements could be externally
generated and supplied to the functions but, for convenience, we will give a variant
that uses smaller random parameters that serve to pseudo-randomly generate the
required elements by means of Blum-Blum-Shub. The preceding proof will not
apply to this variant since the elements obtained this way will not be really random
(the PRG merely “ stretches ” the randomness already present in the seed) and, in
particular, if short seeds are used the scheme will be vulnerable to brute-force attacks.
But this approach should be secure in practice if sufficiently long random seeds are
used.
The implementation will make use of a series of functions previously used for
handling input/output, format conversions and the like, including several functions
defined in Appendix A as well as others defined and used in the implementation
of RSAES-OAEP in 8.3.7 . This includes the SHA-256 based function MGF1 which
implements the “mask generating function” defined in PKCS #1 v2.1 and was also
used in our previous implementation of Rabin-SAEP + . We will use MGF1 as our
(hopefully) collision resistant hash function.
We start with the key generation algorithm, which will be split into two functions
although it can be run by executing only the second of these functions. The reason
is that we will consider the group where encryption and decryption takes place,
together with the two generators that, as we have seen in the previous description
of the scheme, are used in the public key, as system-wide parameters which can be
shared by all users. Thus we will separate the generation of the group (and the group
generators) from the generation of the rest of the key, allowing the possibility of
generating public and private keys for a previously given group.
The groups we will use in this implementation are entirely determined by their
order, namely the Sophie Germain prime q , because once q is given we know that
G

quadratic residues in

Z p , with p = QR p is the group of quadratic residues in = 2 q + 1 and, as we

Z p belong to

have seen in Sect. 2.9 , it is easy to determine which elements of QR p

by computing the Legendre symbol. Since G has prime order, every element 1is

a generator of G by Corollary 2.1. Moreover, the same efficient algorithms used for
the group

=

Z p serve to compute the group operation and to compute inverses in G .
The next function generates the group together with two pseudo-randomly cho-
sen generators. Since all the generated parameters will be publicly known, we
do not worry about the lack of unpredictability and use Mersenne Twister with