Lecture Notes on Cryptography

Subsection 10.1 Merkle–Hellman cryptosystem

The super-increasing knapsack is easy and general knapsacks are difficult that suggested the idea behind the Merkle-Hellman knapsack encryption. Let us see the details of this cryptosystem.

• Alice chooses a super-increasing sequence \(\omega_1,\omega_2,\ldots,\omega_n\) and a prime \(p\) such that

  \begin{equation*} p>\sum_{i=1}^{n}\omega_i. \end{equation*}

  She also fix an integer \(1<r<p.\)

• The public weights \(\Omega_1,\Omega_2,\ldots,\Omega_n\) are computed by the formula

  \begin{equation*} \Omega_i\equiv r\cdot\omega_i\pmod{p}. \end{equation*}

• Bob only knows the general knapsack weights \(\Omega_1,\Omega_2,\ldots,\Omega_n\) and he wants to send the (binary) message \([b_1,b_2,\ldots,b_n].\) He computes

  \begin{equation*} M=\sum_{i=1}^n b_i\Omega_i, \end{equation*}

  that is the encrypted message. To encrypt longer messages, multiple blocks are encrypted.

• Alice receives \(M\) and she can easily compute \(r^{-1} \pmod{p}\) by means of the extended Euclidean algorithm. She determines \(r^{-1}M\) and solves the super-increasing knapsack problem.

A SageMath implementation of the above procedure is as follows.

It creates a random super-increasing sequences and an appropriate prime number \(p\) and an integer \(1<r<p.\) A random binary message is also composed and the corresponding encrypted message is computed.

Subsection 10.2 Attack based on the LLL-algorithm

Unfortunately, the knapsack cryptosystem that has been introduced is not secure against cryptanalysis attacks as pointed out by Shamir. The problem can be reduced to find short vectors in lattices. The purpose of the Lenstra-Lenstra-Lovász (LLL) algorithm is exactly this. Let us consider the example given above. We define vectors in the following form

Our lattice is given by

If we have a solution of the knapsack problem, then there exists a vector in the lattice having coordinates from the set \(\{0,1\},\) that is a short vector. Let us see a SageMath code to apply the LLL-algorithm to the knapsack problem.

In the first row of the second matrix we see the binary message appearing.

Subsection 10.3 Chor-Rivest cryptosystem

Cryptosystems based on knapsack problems used to be popular in public key cryptography, however many variants have been shown insecure by lattice reduction techniques. The Chor-Rivest cryptosystem is one of the exceptions. We consider a finite field \(\mathbb{F}_q,\) where \(q=p^h\) for some prime number \(p\) and positive integer \(h\leq p.\) To represent elements of \(\mathbb{F}_q\) we fix a monic irreducible polynomial \(f(x)\) of degree \(h\) over \(\mathbb{F}_p.\) The polynomials of degree at most \(h-1\) over \(\mathbb{F}_p\) are the elements of \(\mathbb{F}_q.\) The product of two elements \(f_1(x)\) and \(f_2(x)\) is the polynomial \(f_1(x)f_2(x)\pmod{f(x)}\) of degree less than \(h.\) We determine a generator \(g(x)\) of \(\mathbb{F}_q.\) We compute certain discrete logarithms of the form

where \(i\in\mathbb{F}_p.\) We also take a random permutation \(\pi\) of the set \(\{0,1,\ldots,p-1\}\) and a random integer \(d\) for which \(0\leq d\leq p^h-2.\) We compute

The private key of Alice is given by \((f(x),g(x),d,\pi)\) and the public key is \((p,h,(c_0,c_1,\ldots,c_{p-1})).\) Let us describe the encryption.

• Bob would like to send to Alice a binary message \(M = (M_0 , M_1 , \ldots , M_{p-1} )\) containing exactly \(h\) ones.

• He computes

  \begin{equation*} c=\sum_{i=0}^{p-1}M_ic_i. \end{equation*}

  The ciphertext is \(c.\)

Alice receives \(c\) and follows the decryption algorithm given below.

• She determines \(r\equiv (c-hd)\pmod{p^h-1}.\)

• She computes \(s(x)\equiv g(x)^r\pmod{f(x)}.\)

• She takes the monic polynomial \(t(x)=f(x)+s(x)\) of degree \(h.\)

• She factors the polynomial \(t(x),\) let say she has

  \begin{equation*} t(x)=\prod_{j=1}^h (x+t_j). \end{equation*}

• She applies the inverse of the permutation \(\pi\) to recover the positions of the ones in \(M.\)

This algorithm indeed will yield the original binary vector. This fact follows from the steps given below. We have that

We obtain that

and applying the inverse of \(\pi\) to the roots of \(t(x)\) gives the coordinates of \(M\) that are 1.