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

> me := "The magic words are squeamish ossifrage":

seed3 := "d41a480c52d01a7c2faef86f94b3a35e6749a3d610fb8cebc507d7e26f206b1e6e3e18\
54992a1c2111005b58dd11f10ba57ea81a02cdc01b78ae371228c38a233d8b2e8c9168ea2138e171\
bb0efa1d65390e957ee931669b755a290fe46850a68bd42610f0d657bbd710e8040cae585eb1faf6\
505a20b443899ff84f566365fd":
Note that seed3 is a 128-byte string and hence, according to our implementation,
has the required size to be used with a key such as rk which has been obtained from
a security parameter k

= 256. The result of encrypting the above message with this

key and seed is then:
> RabinSAEPPlusEncrypt(rk[1], me, seed3, messagetype = 'text');
"01c9e281233ecfd0f9d048c99215f669245724d180ed65cb564f7262c7a962fcad55b8476d9c52b0e\
a7d79e7ad6cd4cd29d8caaf08d96e65df0b607a7ae1f40fa06ea8f927744114bb2f0b24ca5a99ff7\
5a2b4382f5a98825540431ec618143f2f883569be198a1337157134f333520e06b3e054384fe393c\
ccc17875259af0a059e9bba4f5044c79458f1e45347f08d7e46042cf3c46325eafaf1e5bc98cc283\
2c71a6d90b3f9de1e80f6b64f54af69622151092417d03e53c777839d7fe07e05c57387cadb459e6\
21fabfa9db38c49b14aecee50530d77a24047115232a015d9786d260155078e8ef17f3f1cf87da92\
7417ac5cac9864358635df65dd9406c92"
Now decryption proceeds as follows:
> RabinSAEPPlusDecrypt(rk[2], %, messagetype = text);
"The magic words are squeamish ossifrage"

8.5 The Elgamal Encryption Scheme

Aswe have seen inChap. 7 , the birth of public-key cryptography is associatedwith the
Diffie-Hellman protocol whichwasmotivated by the belief that the discrete logarithm
problem is hard. The two most important number-theoretic problems that are thought
to be hard are the factorization problem and the DL problem, and most computational
problems used as assumptions to obtain cryptographic security reductions are related
to one of these problems. The security of the first public-key encryption scheme, RSA,
is related through the RSA assumption to the integer factorization problem but it was
not clear how to define an encryption scheme similarly related to the DL problem.
Finally, in 1984 T. Elgamal [71] found a way to turn the Diffie-Hellman protocol
into a public-key encryption scheme.
The idea underlying the Elgamal encryption scheme is the following. Suppose
that we have a finite group G and define a private-key encryption scheme as follows:
•

Gen chooses an element a ∈ G uniformly at random.

• Enc uses G as message space and, given m ∈ G , encrypts it as c := am ∈ G .

a − 1 c .
This encryption scheme has perfect secrecy as a consequence of Shannon's theo-
rem (Theorem 3.1) because the probability distribution on the key space is uniform
by hypothesis and, for each m

• Dec decrypts c by computing m :=

∈ G and each c ∈ G , there is a unique key a ∈ G —

cm − 1 —such that Enc c . 6 The idea to turn this into a public-key namely, a = ( a , m ) =

6 We used this argument to prove the perfect secrecy of the one-time pad, which is obtained from
this construction by taking G equal to the group of binary strings of length n with the Xor operation.