=======================
The algorithms of TESID
=======================

Here are prose descriptions of the TESID encoding and decoding algorithms,
including the pieces that make them up.

This is the Table of Ranges, used in encoding and decoding:

┌─────────────┬────────┬─────────┬─────────────┐
│    Range    │ Length │ 5peck n │  ~№ values  │
┝━━━━━━━━━━━━━┿━━━━━━━━┿━━━━━━━━━┿━━━━━━━━━━━━━┥
│ [0,   2²⁰)  │    4   │    10   │   1 million │
│ [2²⁰, 2³⁰)  │    6   │    15   │   1 billion │
│ [2³⁰, 2⁴⁰)  │    8   │    20   │  1 trillion │
│ [2⁴⁰, 2⁵⁰)  │   10   │    25   │ Quadrillion │
│ [2⁵⁰, 2⁶⁰)  │   12   │    30   │      ⋮      │
│ [2⁶⁰, 2⁷⁰)  │   14   │    35   │             │
│ [2⁷⁰, 2⁸⁰)  │   16   │    40   │             │
│ [2⁸⁰, 2⁹⁰)  │   18   │    45   │             │
│ [2⁹⁰, 2¹⁰⁰) │   20   │    50   │             │
└─────────────┴────────┴─────────┴─────────────┘

(The *approximate number of values* column is purely informational,
not being used in the algorithm. It’s the size of the range,
showing how many IDs you can expect to encode at each length,
given sparsity=1 and discriminant=0.)

See also <design-rationale.txt>,
which explores some of the reasoning behind TESID.

5peck
=====

Encryption is done with 5peck, a slight variant of Speck with different parameter values and a slightly different key expansion technique.

Speck is defined in the paper
*The SIMON and SPECK Families of Lightweight Block Ciphers*
which can be found at <https://eprint.iacr.org/2013/404>.

5peck is defined for word sizes n={10, 15, 20, 25, 30, 35, 40, 45, 50}.
In all cases, T=30, α=9, β=2, and m is not applicable.

Key expansion is shared across all word sizes.
A single 128-bit key is expanded in the usual Speck way,
with parameters n=64, m=2, T=30, α=9, β=2.

For 5peck encryption and decryption with word size n,
take the n least significant bits of each 64-bit round key.

Thus, a single key and single expansion can be used for all sizes.

Where Speck’s convention is to operate on byte sequences,
5peck overtly takes unsigned integers as its blocks,
with the least significant bits forming the first word (x),
and the most significant bits forming the second word (y),
following Speck’s endianness convention.

Base-32
=======

Stringification is done by numeric base conversion with the following alphabet:

   23456789abcdefghijkmnpqrstuvwxyz

The decimal 311177248 encodes to “base32”,
as 9×32⁵ + 8×32⁴ + 24×32³ + 12×32² + 1×32¹ + 0×32⁰.

Because TESID wants strings of certain lengths,
values are padded with leading zeroes (“2” in this alphabet).

“base32” padded to length nine would be “222base32”.

TESID encoding
==============

Takes:

 • an *ID* (non-negative integer),
 • an *expanded key*,
 • a *sparsity* factor (positive integer, default 1), and
 • a *discriminant* (non-negative integer, default 0).

Method:

 1. Multiply *ID* by *sparsity*, and add *discriminant*.
    This is the *ID to encrypt*.
 2. Select the row in the Table of Ranges where the *ID to encrypt* lies within the row’s *range*.
    Take the *length* and *n*.
    If no row matches (that is, the ID to encrypt is 2¹⁰⁰ or higher), fail.
 3. Encrypt the ID with the 5peck cipher,
    using the *expanded key* and *n*.
 4. Convert the encrypted ID to base-32,
    padding to *length*.
    This string is the encoded TESID.

TESID decoding
==============

Takes:

 • a string *TESID*,
 • an *expanded key*,
 • a *sparsity* factor (positive integer, default 1), and
 • a *discriminant* (non-negative integer, default 0).

Method:

 1. Select the row in the Table of Ranges where *TESID*’s length matches.
    Take the *range* and *n*.
    If there is no matching row, fail.
 2. Convert *TESID* from base-32 into an integer.
 3. Decrypt this value with the 5peck cipher,
    using the *expanded key* and *n*.
 4. If the decrypted value is not in *range*, fail.
 5. Divide the decrypted value by *sparsity*, and subtract *discriminant*.
    If the division leaves a remainder, or if the subtraction goes negative, fail.
    The result is the decoded TESID.