Question

Find the ciphertext for the message {100110101011011} using superincreasing sequence { 1, 3, 5, 11, 35 } and private keys a = 5 and m=37.

(a) C = ( 33, 47, 65 )

(b) C = ( 65, 33, 47 )

(c) C = ( 47, 33, 65 )

(d) C = ( 47, 65, 33 )

This question was posed to me in an interview for job.

My doubt stems from Knapsack/ Merkle topic in section Public Key Cryptography and RSA of Cryptograph & Network Security

Answer 1

Right option is (c) C = ( 47, 33, 65 )

To explain: {vi} = { 1, 3, 5, 11, 35 }

a = 5  and m = 37

Public key generation:

{wi} = avi mod m

wi = {5, 15, 25, 18, 27}

Break the message into k-bit tuple i.e. 5-bit tuple

10011   01010 11011

Encoding of M as follows:

 M  Ci

10011  47

01010  33

11011  65

Ciphertext sent will be: C = (47, 33, and 65).