Linear Maps

When working modulo $m$ it suffices to work with integers in the range $0, 1, ..., m-1$.

Let $f(x;m,a) = (ax)modm$ be the linear map $x$-> $(ax) mod m$ from $\mathbb{Z}_m$ into itself.

Recall that a function $f(x)$ is said to be linear if $f( \alpha x * \beta y) = \alpha f(x) + \beta f(y)$ for all $\alpha , \beta , x$ and $y$.

For example, for $m=4$ the linear map with $a = 2$ (on the left) is not invertible, but the linear map with $a = 3$ (on the right) is invertible.

map for m=4 and a=2	map for m=4 and a=3
0 -> 0	0 -> 0
1 -> 2	1 -> 3
2 -> 0	2 -> 2
3 -> 2	3 -> 1

Why are we interested in inverting the map? Because the map scambles the elements of $\mathbb{Z}_m$ and we may be interested in unscrambling them (think in cryptographic terms).

So, what is the inverse map?

It turns out that the inverse map if it exists, is also linear.

More specifically, the inverse map of $f(x, m, a mod m)$ is $f(x, m, a^{-1} mod m)$, where $a^{-1} mod m$ is the modular inverse of $a mod m$. Indeed, if $y = f(x; m,a) = ax mod m$ then $x = a^{-1}y mod m$.

Since the modular inverse of $a$ modulo $m$ only exists when $gcd(a, m) = 1$ the linear map is invertible if and only if $gcd(a,m) = 1$.

Keep in mind that we wish to devise a way to encrypt information by providing public data to do so (in this case it would be $m$ and $a$).

Alas, this way of scrambling information is very easy to unscramble, so useless from a cryptography point of view.

Modular multiplication scrambles the information but it is easy to undo if we know $m$ and $a$. What about modular exponentiation?

A Failed Cryptosystem

The Merklw-Hellman knapsack cryptosystem keeps the following information secret:

• a set $W = \lbrace w_1, w_2, ..., w_n \rbrace$ of $n$ positive integers, such that $w_k$ is a super-increasing sequence. i.e: $w_k \gt \sum^{k-1}_{i=1}w_ i$ for $2 \le k \le n$.

• a modulus $m$ such that $m \gt \sum^n_{i=1} w_i$

• a scrambling integer $a$ such that $gcd(a,m) = 1$.

and publishes the following information: set $W' = \lbrace w'_1, w'_2, ..., w'_n \rbrace$, where $w'_i = (aw_i)mod m$, for $1 \le i \le n$.

It is much better to publish a random permutation of $W'$. To send a message composed by the $n$ bits $\alpha_k, 1 \le k \le n$, compute and send.

$$C = \sum^n_{k=1}a_kw'_k$$

This is a hard knapsack problem (in this case a subset sum problem). To decipher transform it into a trivial knapsack problem by computing $a^{-1}C mod m$, which is equal to $\sum^n_{k=1}a_kw_k$ and so can be solved by a greedy algorithm.

Merkle-Hellman Knapsack Example

The following example shows the Merklw-Hellman cryptosystem in action.

• Secret data: $W = \lbrace 1, 3, 5, 12, 22, 47 \rbrace, m = 100$ and $a = 13$.

• Public data: $W' = \lbrace 13, 39, 65, 56, 86, 11 \rbrace$.

• Unencrypted message to be sent: $A = \lbrace 0, 0, 1, 1, 0, 1 \rbrace$

• Encrypted message sent: $C = 0*13 + 0*39 + 1*65 + 1*56 + 0*86 + 1*11 = 132$

• To decrypt compute $132 * 13^{-1} mod 100 = 32 * 77 mod 100 = 64$ and then reason as follows [greedy algorithm for the easy subset sum problem]:

  • $47$ must be used to form the sum because $64 \gt 47$. Hence $\alpha_6 = 1$. The rest of the sum is $64-47=17$.

  • $22$ cannot be used to form the sum because $17 \lt 22$. Hence $\alpha_5 = 0$.

  • $12$ must be used to form the sum because $17 \gt 12$. Hence $\alpha_4 = 1$. The rest of the sum is $17-12=5$.

  • As so on. In this particular case, the next iteration finishes the deciphering process.