2

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.

TMM
  • 9,976
kiwi
  • 21
  • Are you asking for someone to write up an exam question? Does your instructor allow this? Also, the typical parameters use $q$ and $r$ for what you call $b$ and $m$, so I cannot tell them apart. Can you add the equations for encryption and decryption to be sure? Regards – Amzoti May 02 '13 at 03:14
  • @Amzoti the larger number is $q$ the smaller $r$, obviously, as $r$ must be invertible modulo $q$. – Henno Brandsma Sep 15 '17 at 15:12

1 Answers1

1

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.

Henno Brandsma
  • 242,131