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

keys match according to the formulas given in the description of the key generation
algorithm.

We next implement the Cramer-Shoup encryption algorithm. Before doing so
we remark that the groups chosen have the nice property that they allow the easy
encoding of arbitrary bit strings of length len

( q ) − 1 as elements of G = QR p (where

1 as usual) as indicated in [59, Example 2]. Such a string can be uniquely
identified with an integer x in the interval

p = 2 q +

[ 1 , q ] and then x can be mapped to x ∈ G

in case p G in case p = 1 and to p − x ∈ =− 1 (note that the safe prime p is

a Blum prime and hence − p

is a quadratic
residue in this case). This mapping is injective and allows for easy decoding. The
Maple function that performs this encoding is given next. The function has two
required input parameters. The first one, message , is used to specify the message
to be encoded, which should be given as a hexadecimal string. The second parameter
is for the Sophie Germain prime q . The function checks that the byte length of the
message is less than that of q and, if this is the case, it concatenates a leading '01'
byte to the message string which serves to easily recover it when decoding, even if
it has leading zeros. Note that the resulting string has the same byte length as q but
the integer it represents is always

=− 1, so that p − x ≡− x ( mod p )

≤ q because its seven leading bits are '0' bits; in

fact,itis < q if q was generated by GroupGen above because in that case q is an

( 8 k − 1 ) -bit prime while the string is encoded by an ( 8 k − 7 ) -bit integer. The output

Z p .

of the function is an element of G given as an element of

> QREnc := proc(message::string, q::posint)
local mLen, qLen, p, M, md;
mLen := iquo(StringTools:-Length(message), 2);
qLen := intlog[256](q)+1;
if qLen <= mLen then
error "message too long"
end if;
p := 2*q+1;
M := cat("01", message);
md := OS2IP(M);
if numtheory:-legendre(md, p) = 1 then
md
else
p-md
end if
end proc:

We next give the decoding function QRDec , which reverses the encoding done
by QREnc . On input a quadratic residue in Z p 1 is a safe prime)

and the Sophie Germain prime q , the function recovers the encoded string.
> QRDec := proc(qr::posint, q::posint)
local p, x, s;
p := 2*q+1;
x:=qr;
if numtheory:-legendre(x, p) <> 1 then
error "%1 is not a quadratic residue modulo %2", x, p
end if;

(where p = 2 q +