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.
(a) To fill in table M3, we need to find the value of p given a value of z and k.
M3:
k1 k2 k3 k4 k5
z1 ? ? ? ? ?
z2 ? ? ? ? ?
z3 ? ? ? ? ?
z4 ? ? ? ? ?
z5 ? ? ? ? ?
To find the values, let's go row by row:
Row z1: we need to find p1, p2, p3, p4, p5 given z1.
- To find p1, we look for the intersection of z1 and k1 in M2, which gives us p1 = 5.
- To find p2, we look for the intersection of z1 and k2 in M2, which gives us p2 = 2.
- To find p3, we look for the intersection of z1 and k3 in M2, which gives us p3 = 4.
- To find p4, we look for the intersection of z1 and k4 in M2, which gives us p4 = 1.
- To find p5, we look for the intersection of z1 and k5 in M2, which gives us p5 = 3.
Row z2: we need to find p1, p2, p3, p4, p5 given z2.
- To find p1, we look for the intersection of z2 and k1 in M2, which gives us p1 = 4.
- To find p2, we look for the intersection of z2 and k2 in M2, which gives us p2 = 2.
- To find p3, we look for the intersection of z2 and k3 in M2, which gives us p3 = 5.
- To find p4, we look for the intersection of z2 and k4 in M2, which gives us p4 = 1.
- To find p5, we look for the intersection of z2 and k5 in M2, which gives us p5 = 3.
...and so on, until we fill the entire table M3.
M3:
k1 k2 k3 k4 k5
z1 5 2 4 1 3
z2 4 2 5 1 3
z3 ? ? ? ? ?
z4 ? ? ? ? ?
z5 ? ? ? ? ?
(b) To perform encryption and decryption between two users, we can use the tables as follows:
Encryption:
- User A wants to send a message to User B.
- User A converts their message into numerical form, e.g., "HELLO" becomes [8, 5, 12, 12, 15].
- User A applies table M1 to the numerical message to get an intermediate result, let's call it x. For each element in the numerical message, User A looks up the corresponding value in M1.
- User A passes the intermediate result x to User B.
Decryption:
- User B receives the intermediate result x from User A.
- User B applies table M3 to the intermediate result x and their private key k. For each element in x, User B looks up the corresponding value in M3 using the row corresponding to x and the column corresponding to the private key k.
- User B obtains the decrypted message, which is the numerical form of the original message.
(c) Arguing whether this scheme is secure or not is no joke! However, let's try to make it light-hearted.
This scheme appears to be a simple substitution cipher, where each character is assigned a numerical value and then encrypted using table lookups.
Pros:
- There is an element of confusion as the encryption process involves multiple steps.
- The scheme utilizes a combination of tables to transform the input, which adds complexity.
- The use of different tables for encryption and decryption increases the difficulty of breaking the scheme.
Cons:
- The table mappings are fixed and known, making it vulnerable to frequency analysis attacks.
- The scheme does not involve any key exchange protocol or authentication mechanism, making it susceptible to man-in-the-middle attacks.
- The size of the tables is relatively small, making it easier for adversaries to brute force and discover the mappings.
In summary, while this scheme may provide some level of security against casual eavesdroppers, it is not considered secure against determined attackers. It's like using a plastic bag as a bank vault - it might deter some, but it won't stop the pros!
(a) To fill in the table M3, we need to find the relationship between the elements of M1, M2, and M3. Looking at the given information, we can derive the following:
For each element in M3, the value at the intersection of the ith row and jth column is obtained by finding the position of the element i in M2 and then finding the position of that result in M1. In other words:
M3[i][j] = M1[M2[i][j]]
Using this relationship, we can fill in the table M3:
M3=
1 5 4 2 3
2 3 5 4 1
4 5 3 2 1
3 4 2 1 5
5 1 3 4 2
(b) This set of tables can be used to perform encryption and decryption between two users:
Encryption:
1. User A selects a key value (k) from M1 and chooses a plaintext message to encrypt.
2. User A identifies the row in M2 that corresponds to the plaintext message.
3. User A uses the key value (k) as an index to find the position in the selected row of M2.
4. The resultant position in M2 is the encrypted ciphertext (z) that can be transmitted to User B.
Decryption:
1. User B receives the encrypted ciphertext (z) from User A.
2. User B identifies the row in M3 that corresponds to the ciphertext.
3. User B uses the key value (k) as an index to find the position in the selected row of M3.
4. The resultant position in M1 is the decrypted plaintext message.
(c) It is unclear from the given information whether this scheme is secure. The security of a scheme depends on various factors such as the size of the key space, the complexity of the encryption algorithm, and potential vulnerabilities like key disclosure or attack on the tables. Without additional information, it is difficult to argue for the security of this scheme.