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

Next comes the Cramer-Shoup decryption function following the algorithm out-
lined in [59, Fig. 2 ] , including the tests to ensure that the elements obtained really
belong to the group G as indicated in [59, 6.1, Remark 2].
The required input parameters are the private key in the format output by
CSKeyGen and the ciphertext string. There is also an optional keyword parame-
ter, messagetype which, as in the preceding function, is used to specify whether
the plaintext is a hexadecimal string or an ordinary text string. The output is either
an error message if the ciphertext is incorrectly formatted (or invalid) or the original
plaintext. As in the case of the encryption function, there is the possibility of adding
optional parameters that will be accepted by MGF1 and allow this function to use a
hash function different from SHA-256.
> CSDecrypt := proc(privatekey::list, ciphertext::string,
{messagetype::(identical(hex, text)):= hex})
local sk, q, p, maskLen, k, c, u1, u2, e, v, alpha, test, m;
if type(privatekey[1], string) then
sk := OS2IP ∼ (privatekey)
else
sk := privatekey
end if;
q := sk[1];
p := 2*q+1;
maskLen := intlog[256](q);
k := maskLen+1;
if StringTools:-Length(ciphertext) <> 8*k then
error "incorrectly formatted ciphertext"
end if;
c := StringTools:-LengthSplit(ciphertext, 2*k);
u1 := OS2IP(c[1]);
u2 := OS2IP(c[2]);
e := OS2IP(c[3]);
v := OS2IP(c[4]);
if not evalb(numtheory:-legendre ∼ ([u1, u2, e], p) = [1$3]) then
error "invalid ciphertext"
end if;
alpha := OS2IP(cat("01", MGF1(cat(c[1], c[2], c[3]), maskLen)));
test := evalb((Power(u1, (sk[2] + alpha * sk[4]) mod q) mod p)*
(Power(u2, (sk[3] + alpha * sk[5]) mod q) mod p) mod p = v);
if not test then
error "invalid ciphertext"
else
m := e*(Power(u1, q-sk[6]) mod p) mod p
end if;
hextomessage(QRDec(m, q), messagetype)
end proc:
Exercise 8.30 Write modified versions of the functions CSEncrypt and
CSDecrypt that are able to encrypt and decrypt messages of arbitrary size.
Exercise 8.31 Modify the functions CSEncrypt and CSDecrypt in order to
allow them to encrypt and decrypt binary files.
Exercise 8.32 Write aMaple implementation of Cramer-Shoup that closely follows
algorithm CS1a in [59] and uses only random parameters instead of pseudo-random
ones. For this, modify the functions CSKeyGen and CSEncrypt in such a way
that they do not make use of the Blum-Blum-Shub PRG and, instead, work only
with random parameters that are externally generated and supplied as inputs to the
functions.