The algorithms of TESID

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

(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 the design rationale page, 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.

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.