Linear codes and ciphers¶

Ciphers¶

LFSRs¶

A special type of stream cipher is implemented in Sage, namely, a linear feedback shift register (LFSR) sequence defined over a finite field. Stream ciphers have been used for a long time as a source of pseudo-random number generators. {linear feedback shift register}

S. Golomb {G} gives a list of three statistical properties a sequence of numbers $a = {a_{n}}_{n = 1}^{\infty}$ , $a_{n} \in {0, 1}$ , should display to be considered “random”. Define the autocorrelation of $a$ to be

C (k) = C (k, a) = lim_{N \to \infty} \frac{1}{N} \sum_{n = 1}^{N} (- 1)^{a_{n} + a_{n + k}} .

In the case where $a$ is periodic with period $P$ then this reduces to

Assume $a$ is periodic with period $P$ .

balance: $| \sum_{n = 1}^{P} (- 1)^{a_{n}} | \leq 1$ .
low autocorrelation:

$\begin{array}{r} C (k) = {\begin{array}{cc} 1, & k = 0, \\ ϵ, & k \neq 0. \end{array} \end{array}$

(For sequences satisfying these first two properties, it is known that $ϵ = - 1 / P$ must hold.)
proportional runs property: In each period, half the runs have length $1$ , one-fourth have length $2$ , etc. Moveover, there are as many runs of $1$ ’s as there are of $0$ ’s.

A sequence satisfying these properties will be called pseudo-random. {pseudo-random}

A general feedback shift register is a map $f : F_{q}^{d} \to F_{q}^{d}$ of the form

\begin{array}{r} \begin{array}{c} f (x_{0}, . . ., x_{n - 1}) = (x_{1}, x_{2}, . . ., x_{n}), \\ x_{n} = C (x_{0}, . . ., x_{n - 1}), \end{array} \end{array}

where $C : F_{q}^{d} \to F_{q}$ is a given function. When $C$ is of the form

C (x_{0}, . . ., x_{n - 1}) = c_{0} x_{0} + . . . + c_{n - 1} x_{n - 1},

for some given constants $c_{i} \in F_{q}$ , the map is called a linear feedback shift register (LFSR). The sequence of coefficients $c_{i}$ is called the key and the polynomial

C (x) = 1 + c_{0} x + . . . + c_{n - 1} x^{n}

is sometimes called the connection polynomial.

Example: Over $G F (2)$ , if $[c_{0}, c_{1}, c_{2}, c_{3}] = [1, 0, 0, 1]$ then $C (x) = 1 + x + x^{4}$ ,

The LFSR sequence is then

\begin{array}{r} \begin{array}{c} 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, \\ 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, . . . . \end{array} \end{array}

The sequence of $0, 1$ ’s is periodic with period $P = 2^{4} - 1 = 15$ and satisfies Golomb’s three randomness conditions. However, this sequence of period 15 can be “cracked” (i.e., a procedure to reproduce $g (x)$ ) by knowing only 8 terms! This is the function of the Berlekamp-Massey algorithm {M}, implemented as lfsr_connection_polynomial (which produces the reverse of berlekamp_massey).

Sage

sage: F = GF(2)
sage: o = F(0)
sage: l = F(1)
sage: key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
sage: s = lfsr_sequence(key,fill,n); s
[1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0]
sage: lfsr_autocorrelation(s,15,7)
4/15
sage: lfsr_autocorrelation(s,15,0)
8/15
sage: lfsr_connection_polynomial(s)
x^4 + x + 1
sage: from sage.matrix.berlekamp_massey import berlekamp_massey
sage: berlekamp_massey(s)
x^4 + x^3 + 1

Python

>>> from sage.all import *
>>> F = GF(Integer(2))
>>> o = F(Integer(0))
>>> l = F(Integer(1))
>>> key = [l,o,o,l]; fill = [l,l,o,l]; n = Integer(20)
>>> s = lfsr_sequence(key,fill,n); s
[1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0]
>>> lfsr_autocorrelation(s,Integer(15),Integer(7))
4/15
>>> lfsr_autocorrelation(s,Integer(15),Integer(0))
8/15
>>> lfsr_connection_polynomial(s)
x^4 + x + 1
>>> from sage.matrix.berlekamp_massey import berlekamp_massey
>>> berlekamp_massey(s)
x^4 + x^3 + 1

Sage Live

F = GF(2)
o = F(0)
l = F(1)
key = [l,o,o,l]; fill = [l,l,o,l]; n = 20
s = lfsr_sequence(key,fill,n); s
lfsr_autocorrelation(s,15,7)
lfsr_autocorrelation(s,15,0)
lfsr_connection_polynomial(s)
from sage.matrix.berlekamp_massey import berlekamp_massey
berlekamp_massey(s)

Classical ciphers¶

has a type for cryptosystems (created by David Kohel, who also wrote the examples below), implementing classical cryptosystems. The general interface is as follows:

Sage

sage: S = AlphabeticStrings()
sage: S
Free alphabetic string monoid on A-Z
sage: E = SubstitutionCryptosystem(S)
sage: E
Substitution cryptosystem on Free alphabetic string monoid on A-Z
sage: K = S([ 25-i for i in range(26) ])
sage: e = E(K)
sage: m = S("THECATINTHEHAT")
sage: e(m)
GSVXZGRMGSVSZG

Python

>>> from sage.all import *
>>> S = AlphabeticStrings()
>>> S
Free alphabetic string monoid on A-Z
>>> E = SubstitutionCryptosystem(S)
>>> E
Substitution cryptosystem on Free alphabetic string monoid on A-Z
>>> K = S([ Integer(25)-i for i in range(Integer(26)) ])
>>> e = E(K)
>>> m = S("THECATINTHEHAT")
>>> e(m)
GSVXZGRMGSVSZG

Sage Live

S = AlphabeticStrings()
S
E = SubstitutionCryptosystem(S)
E
K = S([ 25-i for i in range(26) ])
e = E(K)
m = S("THECATINTHEHAT")
e(m)

Here’s another example:

Sage

sage: S = AlphabeticStrings()
sage: E = TranspositionCryptosystem(S,15);
sage: m = S("THECATANDTHEHAT")
sage: G = E.key_space()
sage: G
Symmetric group of order 15! as a permutation group
sage: g = G([ 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13 ])
sage: e = E(g)
sage: e(m)
EHTTACDNAEHTTAH

Python

>>> from sage.all import *
>>> S = AlphabeticStrings()
>>> E = TranspositionCryptosystem(S,Integer(15));
>>> m = S("THECATANDTHEHAT")
>>> G = E.key_space()
>>> G
Symmetric group of order 15! as a permutation group
>>> g = G([ Integer(3), Integer(2), Integer(1), Integer(6), Integer(5), Integer(4), Integer(9), Integer(8), Integer(7), Integer(12), Integer(11), Integer(10), Integer(15), Integer(14), Integer(13) ])
>>> e = E(g)
>>> e(m)
EHTTACDNAEHTTAH

Sage Live

S = AlphabeticStrings()
E = TranspositionCryptosystem(S,15);
m = S("THECATANDTHEHAT")
G = E.key_space()
G
g = G([ 3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13 ])
e = E(g)
e(m)

The idea is that a cryptosystem is a map $E : K S \to {Hom}_{Set} (M S, C S)$ where $K S$ , $M S$ , and $C S$ are the key space, plaintext (or message) space, and ciphertext space, respectively. $E$ is presumed to be injective, so e.key() returns the pre-image key.

Linear codes and ciphers¶

Codes¶

Ciphers¶

LFSRs¶

Classical ciphers¶