Cryptography Multiple Choice Questions on “Knapsack/ Merkle – Hellman/ RSA Cryptosystem”.
1. Imagine you had a set of weights {62, 93, 26, 52, 166, 48, 91, and 141}. Find subset that sums to V = 302.
a] {62, 48, 166, 52}
b] {141, 26, 52, 48}
c] {93, 26, 91, 48}
d] {62, 26, 166, 48}
Answer: d
Clarification: {62, 26, 166, 48} =302.
2. For the Knapsack: {1 6 8 15 24}, Find the cipher text value for the plain text 10011.
a] 40
b]
22
c] 31
d] 47
Answer: a
Clarification: 1+15+24 = 40.
3. For the Knapsack: {1 6 8 15 24}, find the plain text code if the ciphertext is 38.
a] 10010
b] 01101
c] 01001
d] 01110
Answer: b
Clarification: If someone sends you the code 38 this can only have come from the plain text 01101.
4. Set {1, 2, 3, 9, 10, and 24} is superincreasing.
a] True
b] False
Answer: b
Clarification: It is
not because 10 < 1+2+3+9.
5. A superincreasing knapsack problem is ____ to solve than a jumbled knapsack.
a] Easier
b] Tougher
c] Shorter
d] Lengthier
Answer: a
Clarification: A superincreasing knapsack is chosen to make computations easier while manual calculations of knapsack problems.
6. Consider knapsack that weighs 23 that has been made from the weights of the superincreasing series {1, 2, 4, 9, 20, and 38}. Find the ‘n’.
a]
011111
b] 010011
c] 010111
d] 010010
Answer: b
Clarification: v0=1, v1=2, v2=4, v3=9, v4=20, v5=38
K=6, V=23
Starting from largest number:
v5 > V then ϵ_5=0
v4 < V then V = V – v4 = 23 – 20 = 3 ϵ_4=1
v3 > V then ϵ_3=0
v2> V then ϵ_2=0
v1 < V then V = V – v1= 3 – 2 = 1 ϵ_1=1
v0 =1 then V = V – v0= 1 – 1 = 0 ϵ_0=1
n= ϵ_5 ϵ_4 ϵ_3 ϵ_2 ϵ_1 ϵ_0 = 010011.
7. Another name for Merkle-Hellman Cryptosystem is
a]
RC4
b] Knapsack
c] Rijndael
d] Diffie-Hellman
Answer: b
Clarification: Knapsack is another name for Merkel-Hellman Cryptosystem.
8. In Merkle-Hellman Cryptosystem, the hard knapsack becomes the private key and the easy knapsack becomes the public key.
a] True
b] False
Answer: b
Clarification: The hard knapsack becomes the public key and the easy knapsack becomes the private key.
9. In Merkle-Hellman Cryptosystem, the
public key can be used to decrypt messages, but cannot be used to decrypt messages. The private key encrypts the messages.
a] True
b] False
Answer: b
Clarification: The public key can be used to encrypt messages, but cannot be used to decrypt messages. The private key decrypts the messages.
10. The plaintext message consist of single letters with 5-bit numerical equivalents from [00000]2 to [11001]2. The secret deciphering key is the superincreasing 5-tuple
[2, 3, 7, 15, 31], m = 61 and a = 17. Find the ciphertext for the message “WHY”.
a] C= [148, 143, 50]
b] C= [148, 143, 56]
c] C= [143, 148, 92]
d] C= [148, 132,92]
Answer: a
Clarification: {wi }= {a vi mod m}
{wi} = { 17×2 mod 61, 17×3 mod 61, 17×7 mod 61, 17×15 mod 61, 17×31 mod 61}
{wi} = {34, 51, 58, 11, and 39}
PlainText In binary Ci
W- 22 10110 148
H – 7 00111 143
Y – 24 11000 50
So that the ciphertext sent will be C= [148,
143, 50].
11. For p = 11 and q = 17 and choose e=7. Apply RSA algorithm where PT message=88 and thus find the CT.
a] 23
b] 64
c] 11
d] 54
Answer: c
Clarification: n = pq = 11 × 19 = 187.
C=Me mod n ; C=887 mod 187 ; C = 11 mod 187.
12. For p = 11 and q = 17 and choose e=7. Apply RSA algorithm where Cipher message=11 and thus find the plain text.
a] 88
b] 122
c] 143
d] 111
Answer: a
Clarification: n = pq = 11 × 19 = 187.
C=Me mod n ; C=1123 mod 187 ; C = 88 mod 187.
13. In an RSA system the public key of a given user is e = 31, n = 3599. What is the private key of this user?
a] 3031
b] 2412
c] 2432
d] 1023
Answer: a
Clarification: By trail and error, we determine that p = 59 and q = 61. Hence f[n] = 58 x 60 = 3480.
Then, using the extended Euclidean algorithm, we find that the multiplicative
inverse of 31 modulo f[n] is 3031.
14. Compute private key [d, p, q] given public key [e=23, n=233 ´ 241=56,153].
a] 35212
b] 12543
c] 19367
d] 32432
Answer: c
Clarification: Since n=233 ´ 241=56,153, p=233 and q=241
f[n] = [p – 1][q – 1] = 55,680
Using Extended Euclidean algorithm, we obtain
d = 23–1 mod 55680 = 19,367.
[Theory] RSA is just one way of doing public key encryption. Merkle-hellman-knapsack is a good alternative where we can create a public key and a private one. The knapsack problem defines a problem where we have a number of weights and then must pack our knapsack with the minimum number of weights that will make it a given weight:
Other examples
- On this Wiki page [Here], the private key is {2, 7, 11, 21, 42, 89, 180, 354}, n=792, m=881, with data of "01100001" which gives a public key of {295, 592, 301, 14, 28, 353, 120, 236} and gives a cipher of "1129". Try:. here
- On this page [here] we have a private key of {1,2,4,7,12,20,33,54} and n of 147, with m of 250, and gives a public key of {1,2,4,7,12,20,33,54}. Try:. here
- On this page [Slide 18/19] [here] we have a private key of {3, 5, 15, 25, 54, 110, 225} and n of 10, with m of 439, and data of "hello" [1001000 1100101 1101100 1101111]. This gives a public key of {30, 50, 150, 250, 101, 222, 55} and a cipher of {280,236,431,708}. Try:. here
In Case 1 our private key is [{2, 7, 11, 21, 42, 89, 180, 354},588,881] and the public key is [{295, 592, 301, 14, 28, 353, 120, 236}], as we have no need to reveal the n and m value.
In Case 2 our private key is [{1,2,4,7,12,20,33,54},147,250] and the public key is [{1,2,4,7,12,20,33,54}]
In Case 3 our private key is [{3, 5, 15, 25, 54, 110, 225},10,439] and the public key is [{30, 50, 150, 250, 101, 222, 55}]
Making the Public Key
We first start with our super-increasing sequence, such as {1,2,4,10,20,40} and take the values and multiply by a number n, and take a modulus [m] of a value which is greater than the total [m - such as 120]. For n we make sure that there are no common factors with any of the numbers. Let's select an n value of 53, so we get:
1×53 mod[120] = 53 2×53 mod[120] = 106 4×53 mod[120] = 92 10×53 mod[120] = 50 20×53 mod[120] = 100 40×53 mod[120] = 80So the public key is: [{53,106,92,50,100,80},53,120] and the private key is {1, 2, 4, 10, 20,40}. The public key will be difficult to factor while the private key will be easy. Let's try to send a message that is in binary code:
111010 101101 111001We have six weights so we split into three groups of six weights:
111010 = 53 + 106 + 92 + 100 = 351 101101 = 53+ 92 + 50 + 80 = 275 111001 = 53 + 106 + 92 + 80 = 331Our cipher text is thus 351 275 331.
The two numbers known by the receiver is thus 120 [m - modulus] and 53 [n multiplier].
We need n-1, which is a multiplicative inverse of n mod m, i.e. n[n−1] = 1 mod m. For this we find the inverse of n:
n-1 = 53-1 mod 120 [53 x _n] mod 120 = 1So we try values of n-1 in [53 x n-1 mod 120] in order to get a result of 1:
n-1 Result 1 53 2 106 3 39 ... 75 15 76 68 77 1So the inverse is 77. [Calculate]
The coded message is 351 275 331 and is now easy to calculate the plain text:
351×77 mod[120] = 27 = 111010 [1+2+4+20] 275×77 mod[120] = 55 = 101101 331×77 mod[120] = 47 = 111001The decoded message is thus:
111010 101101 110001which is the same as our original message:
111010 101101 111001Code
A quick overview of the code is:
string get_public=getknap[priv, n,m]; string cipher = getcipher[get_public,data]; int solv = solve[Convert.ToInt32[n], Convert.ToInt32[m]]; string plain = getknap[cipher, Convert.ToString[solv], m]; public string getcipher[string publickey, string data] { string data_result = ""; string[] vals = publickey.Split[',']; int[] weights = new int[vals.Length]; for [int i=0;i