> For the complete documentation index, see [llms.txt](https://davidjosearaujo.gitbook.io/notes-mcs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://davidjosearaujo.gitbook.io/notes-mcs/applied-cryptography/rsa-and-related-subjects/linear-maps.md).

# 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.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://davidjosearaujo.gitbook.io/notes-mcs/applied-cryptography/rsa-and-related-subjects/linear-maps.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.