线性码与密码¶

密码¶

线性反馈移位寄存器 (LFSR)¶

在 Sage 中实现了一种特殊类型的流密码，即定义在有限域上的线性反馈移位寄存器（LFSR）序列。流密码长期以来一直被用作伪随机数生成器的来源。 {linear feedback shift register}

S. Golomb {G} 给出了数字序列 \({\bf a}=\{a_n\}_{n=1}^\infty\) (\(a_n\in \{0,1\}\)) 被认为是“随机”的三个统计特征。将 \({\bf a}\) 的自相关定义为：

\[C(k)=C(k,{\bf a})=\lim_{N\rightarrow \infty} \frac{1}{N}\sum_{n=1}^N (-1)^{a_n+a_{n+k}}.\]

如果 \(a\) 是周期性的，周期为 \(P\)，则该公式可以简化为：

\[C(k)=\frac{1}{P}\sum_{n=1}^P (-1)^{a_n+a_{n+k}}\]

假设 \(a\) 是周期性的，周期为 \(P\)。

平衡： \(|\sum_{n=1}^P(-1)^{a_n}|\leq 1\).
低自相关：

\[\begin{split}C(k)= \left\{ \begin{array}{cc} 1,& k=0,\\ \epsilon, & k\not= 0. \end{array} \right.\end{split}\]

（对于满足头两个特性的序列，已知 \(\epsilon=-1/P\) 必然成立。）
比例运行特性：在每个周期中，一半的递推序列长度为 \(1\), 四分之一长度为 \(2\), 等等。此外，\(1\) 的递推次数和 \(0\) 的递推次数相等。

满足这些特性的序列将被称为伪随机数列。{pseudo-random}

一般反馈移位寄存器是一个映射 \(f:{\bf F}_q^d\rightarrow {\bf F}_q^d\)，形式为：

\[\begin{split}\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{split}\]

其中 \(C:{\bf F}_q^d\rightarrow {\bf F}_q\) 是一个给定的函数。当 \(C\) 形式为：

\[C(x_0,...,x_{n-1}) = c_0 x_0 + ... + c_{n-1} x_{n-1},\]

对于某些给定常数 \(c_i\in {\bf F}_q\), 该映射被称为线性反馈移位寄存器（LFSR）。系数序列 \(c_i\) 被称为密钥，多项式

\[C(x) = 1+ c_0x + \dots + c_{n-1}x^n\]

有时被称为连接多项式。

例如：在 \(GF(2)\) 上，如果 \([c_0,c_1,c_2,c_3]=[1,0,0,1]\) 则 \(C(x) = 1 + x + x^4\),

\[\]

x_n = x_{n-4} + x_{n-1},ngeq 4.

那么 LFSR 序列为

\[\begin{split}\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{split}\]

此 \(0,1\) 序列是周期性的，周期为 \(P=2^4-1=15\)，并满足 Golomb 的三个随机性条件。然而，这个以 15 为周期的序列可以通过只知道 8 个项被“破解”（即生成 \(g(x)\) 的过程）！这是 Berlekamp-Massey 算法 {M} 的功能，已通过 lfsr_connection_polynomial 实现（产生 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

经典密码¶

有一个用于加密系统的类型（由 David Kohel 创建，他还编写了下面的示例），实现了经典加密系统。一般接口如下：

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

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

其思想是加密系统是一个映射 \(E: KS \to \text{Hom}_\text{Set}(MS,CS)\)，其中 math:\(KS\), \(MS\) 和 \(CS\) 分别是密钥空间、明文（或消息）空间和密文空间。假设 \(E\) 为单射，所以 e.key() 返回原像密钥。