In a Merkle-Hellman cryptosystem, plaintext message units are of length $3$ over the alphabet
$$ \begin{array}{cccc} &A&B&C&D&E&F&G&H&I&J&K&L&M&N&O \\ &0 &1 &2 &3 &4 &5 &6 &7 &8&9&10&11&12&13&14\\ \end{array} $$ $$ \begin{array}{cccc} &P&Q&R&S&T&U&V&W&X&Y&Z&\fbox{}&?&!&.&'&$&\\ &15&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31\\ \end{array} $$
The following sequence of ciphertext message units is received.
$$ \begin{array}{cccc} &152472, 116116, 68546, 165420, 168261 \end{array} $$
The public key is
$$ \begin{array}{cccc} &24038, 29756, 34172,34286,38334,1824,18255,19723,143,17146\\ &35366, 11204, 32395, 12958, 6479 \end{array} $$
and the secret key is $b=30966$, $m=47107$. Decrypt the message.
Myself and a classmate are struggling to do this exam question so we would really appreciate some help! :) Step-by-step if possible as we don't have any similar examples in our class notes. Thanks in advance.
You don't have the complete secret key, because the superincreasing sequence cannot be directly computed from the public key, even with known $b$ (multiplier) and $m$ (modulus); in our case $b^{-1} \pmod{m} = 6479$ But the Shamir paper see here does give some ideas about that.
How I solved the message is by completely ignoring the private key components and by building (using the public key only) a table (using a programme of course) that computes the encrpytion of all 3 letter combinations; a programme can do that in fewer than a second easily, and then match the observed cipher values.
There is no randomisation, so we just have a public key block cipher with a very small blocksize of 15 bits. This yielded
FOR MUL A S TOL EN!as the five plain blocks BTW.