path: root/README.md

# LS47 hand-computable cipher

This is a slight improvement of the ElsieFour cipher as described by Alan
Kaminsky [1]. We use 7x7 characters instead of original (barely fitting) 6x6,
to be able to encrypt some structured information. We also describe a simple
key-expansion algorithm, because remembering passwords is popular. Similar
security considerations as with ElsieFour hold.

There's also a 3D-printable SCAD model of the whole thing. Yay!

![Tiles printed out](tiles.jpg)

We suggest printing the model using more than one filament color to make the
letters easily recognizable. Thanks go to Martin Ptasek for providing the
picture.

If you trust your computer, there's an implementation in `ls47.py`.

### Version history

Historically, there were several other versions, e.g.:

- A nice Python version usuable as an actual binary (also supporting MANY
  versions of padding and the original ElsieFour cipher) was supplied by
  Bernhard Esslinger from the CrypTool project.
- Javascript version (npm-compatible) of the cipher implementations was created
  by Ulysse McConnell, now available at https://github.com/umcconnell/lc4
- Trevor Terris supplied a nicely arranged playing-cards version together with
  useful hints on how to encrypt with these.
- Stas Bushuev generated a nice alternate set of Russian tiles.

These versions can be found in git history of the repository.

In 2026, the board was reorganized, and we started using the version with
arrows instead of the numbers.

## Character board

Compared to LC4, we have added some real punctuation, basic stuff for writing
expressions, and some quotes. The letters of the board now look like this:

```
_ A B C D E F
G H I J K L M
N O P Q R S T
U V W X Y Z .
, : ? ! ' ( )
0 1 2 3 4 5 6
7 8 9 + - * /
```

The cipher works by changing positions of a marker over a set of tiles (with
arrows) and permuting the tiles. For the position changes, the tiles have
arrows on them (0-3 horizontally and vertically, in either direction):

```
.-----.  .-----.  .-----.  .-----.  .-----.
|     |  |     |  |<    |  |<    |  |    >|
|  _  |  |< A  |  |  B  |  |< C  |  |  D >|  ...
|     |  |     |  |<    |  |<    |  |    >|
'-----'  '-----'  '-----'  '-----'  '-----'

.-----.  .-----.
|  ^  |  |  ^  |
|  G  |  |< H  |  ...
|     |  |     |
'-----'  '-----'
   .        .
   .        .
   .        .
```

To run (hand-run) the encryption/decryption, you will also need some kind of a
marker (e.g. a small shiny stone, bolt nut or similar kind of well-shaped
trash).

## How-To

You may as well see the paper [1], there are also pictures. This is somewhat
more concentrated:

### Encryption

Initialization:

1. The symmetric key is the initial state of the board. Arrange your tiles to
   7x7 square, according to the key.
2. Put the marker on the tile in the upper left corner.

Encryption loop (repeat for all letters of the plaintext):

1. You need to encrypt one letter of the plaintext. First, find the position of
   the tile with that letter on the board. This is the *plaintext tile*.
2. Second, look at the tile under the marker (*marker tile*); we are interested
   in the arrows that are on the marker tile. Start at the *plaintext tile*,
   and make steps from it in the exact direction and count as there are arrows
   on the *marker tile*. In case you run out of board in any direction, wrap
   around to the other side of the board. The steps will end on a *ciphertext
   tile*.
3. Look at the letter on the *ciphertext tile*. This is the next letter of the
   ciphertext; write it down (or send it via telegraph, or such).
4. Do the rotations:
  - First, shift the row where the *plaintext tile* lies by one position to the
    right. The tile on the right will get shifted out out of the board, so wrap
    it around again to the now-empty spot on the left of the board. (We can
    call this *rotation*.). If the marker is sitting on any of the affected
    tiles, DO NOT MOVE IT with the tiles (or move it back after you do the
    rotation) -- it should stay on the exactly same coordinates.
  - Second, similarly, rotate the *column* that now (after the first rotation)
    contains the *ciphertext tile* one position down, again wrapping the last
    tile, and keeping the marker position intact.
5. Look at the arrows on the *ciphertext tile* `C` and move the marker
   according to the arrow directions (just like previously when you were
   following the arrows from the plaintext to ciphertext).
6. Repeat from 3 as many times as needed to encrypt the whole plaintext.

### Decryption

Decryption procedure is basically the same, except that instead of knowing the
plaintext tile and finding the ciphertext tile, you you *know the ciphertext
tile and need to trace back to the plaintext tile*.

This is done simply by reversing the step 2 of the encryption loop: Instead of
taking the arrows on the marker tile "forward" from plaintext to ciphertext,
you start at ciphertext, and *take the arrows "backwards"* to find the
plaintext.

Note that the rotations and marker position change is still done "forwards",
just like in encryption.

### Encryption example!

Let's use this as the starting key:
```
 E F _ A B C D
 L M G H I J K
 ( ) / : ? ! '
 S T N O P Q R
 Z . U V W X Y
 5 6 0 1 2 3 4
 + * 7 8 9 , -
```

The marker starts in the upper right, thus sitting on `E`. We label the marker
with brackets, a marked tile is shown as `[E]`:

```
[E]F _ A B C D
 L M G H I J K
 ( ) / : ? ! '
 S T N O P Q R
 Z . U V W X Y
 5 6 0 1 2 3 4
 + * 7 8 9 , -
```

Initialization is done, we start the encryption loop.

**We want to encrypt `Q`.** Look at the arrows at the marked tile:

```
.-----.
|    >|
|  E  |
|    >|
'-----'
```

This means that the ciphertext tile is 2 positions to the right from the
plaintext tile. We find `Q` on the board, move 2 positions to the right
(wrapping around to the left side), and finish at `S`. **`S` is the next letter
of the ciphertext.**

Now, let's do the rotation: First we rotate plaintext tile to the right:

```
[E]F _ A B C D
 L M G H I J K
 ( ) / : ? ! '
 R S T N O P Q   <--- this row moved, and R wrapped around
 Z . U V W X Y
 5 6 0 1 2 3 4
 + * 7 8 9 , -
```

After that, we rotate the ciphertext tile downwards:

```
[E]* _ A B C D
 L F G H I J K
 ( M / : ? ! '
 R ) T N O P Q
 Z S U V W X Y
 5 . 0 1 2 3 4
 + 6 7 8 9 , -

   ^
   '------- this column moved, and the * got wrapped to the top
```

Now we look at the ciphertext:
```
.-----.
| ^ ^>|
|  S  |
|    >|
'-----'
```

It says that we move the marker 2 positions up and 2 to the right, so we end up
with a new marker position:
```
 E * _ A B C D
 L F G H I J K
 ( M / : ? ! '
 R ) T N O P Q
 Z S U V W X Y
 5 .[0]1 2 3 4
 + 6 7 8 9 , -
```

That's it for encrypting the `Q`; now we can continue the encryption loop with
another letter.

### Key generation

Grab a bag full of tiles and randomly draw them one by one. Key is the 49-item
permutation of them.

## Extensions and modifications

### Key expansion from a password

Remembering 49-position random permutation that includes weird characters is
not very handy. There are many methods to do key expansion, so we show a simple
(although not super secure) one here:

1. Think a password as a string of letters from the board.
2. Start with a board in the "canonical order".
3. In series, take all letters of your password from the board and place them
   to the new board, starting at bottom right, and contining by rows going to
   the left, and wrapping upwards to the next line. If some letter is already
   moved out of the board, ignore it.
4. If the password did not include the space tile (`_`), add it as if it was
   the last letter of the password.
5. Finally, take the rest of the board in the order (line-by-line from the
   bottom right) and continue adding it to the password lines (again adding
   line-by-line, as with the password). This will squash any blanks left over
   after removing the password tiles.

The new board is the expanded key.

For any notion of real security, it is quite adviseable to **not** rely on the
mixing provided by this procedure (it **is** insufficient). Instead, run a few
encryption rounds of random padding characters (i.e., a *nonce*) before
starting the encryption of the actual plaintext (see below).

### Undistinguishable ciphertexts

To get a different ciphertext even if the same plaintext is encrypted
repeatedly, prepend the plaintext with a *nonce*. A nonce is a completely
random sequence of letters, usually of pre-negotiated length or with an easily
distinguishable separator.

You can e.g. agree to always draw exactly 10 random tiles from a bag as the
nonce, or to use nonces of random length while keeping the space tile as a
separator that is guaranteed to not occur in the nonce.

Randomization of ciphertext length is quite beneficial for short messages; even
if not using nonces, it is quite beneficial to add a random number of spaces to
the end of the ciphertext: It prevents the adversary from seeing the difference
between plaintexts such as 'yes please' and 'no', the ciphertexts of whese
would otherwise be easily distinguishable by length, like `qwc3w_cs'(` and
`+v`.

### Authenticated encryption

Because ciphertext may be altered in the transfer or during the error-prone
human processing, it is advised to append a simple human-readable "signature"
to the end of the message. That may look as simple as `__YourNameHere`. In case
there's any error or manipulation in the ciphertext, the signature will quite
likely come out completely garbled with overwhelming probability, serving
essentially as an authenticated checksum.

This works because the cipher output is message-dependent: Taking a different
input (or making a different step) anywhere in the middle of the encryption
causes an avalanche effect, and effectively erases any meaning from the text
after several iterations.

## References

[1] *Kaminsky, Alan. "ElsieFour: A Low-Tech Authenticated Encryption Algorithm For Human-to-Human Communication." IACR Cryptology ePrint Archive 2017 (2017): 339.*