线性码与密码¶

代码¶

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

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还可以通过奇异接口§第二节：agcodes。也可以通过Sage接口使用GUAVA中实现的AG代码 gap_console() . 更多详情请参阅番石榴手册。{GUAVA}

密码¶

LFSRs¶

在Sage中实现了一种特殊类型的流密码，即定义在有限域上的线性反馈移位寄存器（LFSR）序列。流密码作为伪随机数发生器的来源已经有很长一段时间了。{线性反馈移位寄存器}

S、 Golomb{G}给出了一个由三个统计属性组成的一系列数字 \({{\bf a}}=\{{a_n\}}_{{n=1}}^\infty\) ， \(a_n\in \{{0,1\}}\) ，应显示为“随机”。定义的自相关 \({{\bf a}}\) 成为

\[C（k）=C（k，{bfa}）=lim{Nrightarrowinfty}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\) .
低自相关：

\[C（k）=left{begin{array}{cc}1，&k=0，\epsilon，&knot=0。右结束{array}右。\]

（对于满足前两个性质的序列，已知 \(\epsilon=-1/P\) 必须保持住。）
比例运行特性：在每个周期中，有一半的运行具有长度 \(1\) 四分之一有长度 \(2\) 等等。移动，有很多次 \(1\) 就像现在一样 \(0\) s。

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

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

\[begin{array}{c}f（x_0，…，x{n-1}）=（x_1，x_2，…，x_n），\x_n=c（x_0，…，x{n-1}），结束{array}\]

在哪里？ \(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_x+…+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\) ，

LFSR序列是

\[开始{array}{c}1，1，0，1，0，1，1，0，0，1，1，1，\1，1，0，1，1，0，1，1，0，0，1，0，0，1，1，…。结束{array}\]

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

经典密码¶

有一个密码系统类型（由davidkohel创建，他也写了下面的例子），实现了经典密码系统。一般界面如下：

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¶

经典密码¶

Sage 中文文档

导航

Related Topics