Prior to the discovery of any specific public-key schemes such as RSA, an existence proof was developed
whose purpose was to demonstrate that public-key encryption is possible in theory. Consider the
following tables, as shown below:
M1=
5
4
2
3
1
M2=
5 2 3 4 1
4 2 5 1 3
1 3 2 4 5
3 1 4 2 5
2 5 3 4 1
M3=
M1 takes an input k and produces an output x, where the ith element of M1 corresponds to k=i.
M2 takes inputs x and p giving output z, where the ith row of M2 corresponds to x=i; the jth column of
M2 corresponds to p=j.
(a) If M3 takes inputs z and k and produces p, where the ith row of M3 corresponds to z=i; the jth
column of M3 corresponds to k=j, fill in the table M3.
(b) Describe the use of this set of tables to perform encryption and decryption between two users.
(c) Argue that this is a secure scheme.