线性码和密码¶

电码¶

长度的线性码 \(n\) 是的有限维子空间 \(GF(q)^n\) 。SAGE可以在有限的范围内使用线性纠错码进行计算。它基本上有一些用于GAP和芭乐命令的包装器。GAP的Sage 4.0‘S安装程序中不包括芭乐2.8，但可以作为可选程序包进行安装。

Sage可以计算汉明码

sage: C = codes.HammingCode(GF(3), 3)
sage: C
[13, 10] Hamming Code over GF(3)
sage: C.minimum_distance()
3
sage: C.generator_matrix()
[1 0 0 0 0 0 0 0 0 0 1 2 0]
[0 1 0 0 0 0 0 0 0 0 0 1 2]
[0 0 1 0 0 0 0 0 0 0 1 0 2]
[0 0 0 1 0 0 0 0 0 0 1 1 1]
[0 0 0 0 1 0 0 0 0 0 1 1 2]
[0 0 0 0 0 1 0 0 0 0 2 0 2]
[0 0 0 0 0 0 1 0 0 0 1 2 1]
[0 0 0 0 0 0 0 1 0 0 2 1 1]
[0 0 0 0 0 0 0 0 1 0 2 2 0]
[0 0 0 0 0 0 0 0 0 1 0 1 1]

四个格雷密码

sage: C = codes.GolayCode(GF(3))
sage: C
[12, 6, 6] Extended Golay code over GF(3)
sage: C.minimum_distance()
6
sage: C.generator_matrix()
[1 0 0 0 0 0 2 0 1 2 1 2]
[0 1 0 0 0 0 1 2 2 2 1 0]
[0 0 1 0 0 0 1 1 1 0 1 1]
[0 0 0 1 0 0 1 1 0 2 2 2]
[0 0 0 0 1 0 2 1 2 2 0 1]
[0 0 0 0 0 1 0 2 1 2 2 1]

以及二进制Reed-Muller码、二次剩余码、准二次剩余码、“随机”线性码，以及由满秩矩阵生成的码(通常使用行作为基础)。

对于给定的代码， \(C\) ，Sage可以返回生成矩阵、校验矩阵和对偶码：

sage: C = codes.HammingCode(GF(2), 3)
sage: Cperp = C.dual_code()
sage: C; Cperp
[7, 4] Hamming Code over GF(2)
[7, 3] linear code over GF(2)
sage: C.generator_matrix()
  [1 0 0 0 0 1 1]
  [0 1 0 0 1 0 1]
  [0 0 1 0 1 1 0]
  [0 0 0 1 1 1 1]
sage: C.parity_check_matrix()
  [1 0 1 0 1 0 1]
  [0 1 1 0 0 1 1]
  [0 0 0 1 1 1 1]
sage: C.dual_code()
[7, 3] linear code over GF(2)
sage: C = codes.HammingCode(GF(4,'a'), 3)
sage: C.dual_code()
[21, 3] linear code over GF(4)

为 \(C\) 和一个向量 \(v\in GF(q)^n\) ，Sage可以尝试解码 \(v\) (即，找到码字 \(c\in C\) 最接近 \(v\) 在汉明度量中)使用校正子解码。到目前为止，还没有实现特殊的解码方法。

sage: C = codes.HammingCode(GF(2), 3)
sage: MS = MatrixSpace(GF(2),1,7)
sage: F = GF(2); a = F.gen()
sage: v = vector([a,a,F(0),a,a,F(0),a])
sage: c = C.decode_to_code(v, "Syndrome"); c
(1, 1, 0, 1, 0, 0, 1)
sage: c in C
True

要绘制代码的权重分布(直方图)，可以使用Sage附带的matplotlib包：

sage: C = codes.HammingCode(GF(2), 4)
sage: C
[15, 11] Hamming Code over GF(2)
sage: w = C.weight_distribution(); w
 [1, 0, 0, 35, 105, 168, 280, 435, 435, 280, 168, 105, 35, 0, 0, 1]
sage: J = range(len(w))
sage: W = IndexedSequence([ZZ(w[i]) for i in J],J)
sage: P = W.plot_histogram()

现在键入 show(P) 查看此内容。

有几个编码理论功能我们完全跳过了。请参阅参考手册或文件 coding/linear_codes.py 举个例子。

Sage can also compute algebraic-geometric codes, called AG codes, via the Singular interface § sec:agcodes. One may also use the AG codes implemented in GUAVA via the Sage interface to GAP gap_console(). See the GUAVA manual for more details. {GUAVA}

密码¶

LFSRs¶

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

S. Golomb {G} gives a list of three statistical properties a sequence of numbers \({\bf a}=\{a_n\}_{n=1}^\infty\), \(a_n\in \{0,1\}\), should display to be considered "random". Define the autocorrelation of \({\bf a}\) to be

\[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\) 那么这就会降低到

假设 \(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\) 的。

满足这些性质的序列称为伪随机序列。{伪随机}

一般的反馈移位寄存器是一个映射 \(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+...+c_{n-1}x^n\]

有时被称为连接多项式。

示例：Over \(GF(2)\) ，如果 \([c_0,c_1,c_2,c_3]=[1,0,0,1]\) 然后 \(C(x) = 1 + x + x^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}\]

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: 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

经典密码¶

有一种用于密码系统的类型(由David Kohel创建，他还编写了下面的示例)，实现了经典密码系统。通用界面如下：

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

下面是另一个例子：

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

其想法是，密码系统就是一张地图 \(E: KS \to \text{Hom}_\text{Set}(MS,CS)\) 哪里 \(KS\) ， \(MS\) ，以及 \(CS\) 分别是密钥空间、明文(或消息)空间和密文空间。 \(E\) 被认为是注射的，所以 e.key() 返回前映像密钥。

线性码和密码¶

电码¶

密码¶

LFSRs¶

经典密码¶

目录

上一主题

下一主题