密码学：有限状态自动机
流密码的基本概念
-
加密思想： 先将明文流 m 划分成字符（单个字母），或者编码基本单元（如 0、1数字），之后利用** k1 （种子**）产生一个**流 k 与密文流 m 逐位加密得到密文 c，解密时以同步产生的同样的**流 k 与密文流 c 逐位解密来恢复明文 m。
设明文流为：
m = m 1 m 2 m 3 . . . m i . . , m ∈ M m = m_1m_2m_3...m_i.., m\in M m=m1m2m3...mi..,m∈M
**流为
k = k 1 k 2 . . . k i . . . , k ∈ K k = k_1 k_2 ... k_i ..., k \in K k=k1k2...ki...,k∈K
密文流为
c = c 1 c 2 . . . c i . . . , c ∈ C c = c_1 c_2 ... c_i ..., c \in C c=c1c2...ci...,c∈C则加密过程
c = c 1 c 2 . . . c i . . . = E k 1 ( m 1 ) E k 2 ( m 2 ) . . . E k i ( m i ) . . . ; c = c_1 c_2 ... c_i ... = E_{k_1}(m_1) E_{k_2}(m_2) ... E_{k_i}(m_i) ...; c=c1c2...ci...=Ek1(m1)Ek2(m2)...Eki(mi)...;
解密过程为
m = m 1 m 2 . . . m i . . . = D k 1 ( c 1 ) D k 2 ( c 2 ) . . . D k i ( c i ) . . . m = m_1 m_2 ... m_i ... = D_{k_1}(c_1) D_{k_2}(c_2) ... D_{k_i}(c_i) ... m=m1m2...mi...=Dk1(c1)Dk2(c2)...Dki(ci)... -
优点：软件实现简单，速度快，效率高
-
特点：流密码的强度完全取决于**流的随机性和不可预测性 -> 重点在于设计随机**流
流密码的分类
按照**流产生算法是否与明密文有关
同步流密码
-
定义：**流独立于明密文的流密码
-
加密过程
σ i + 1 = f ( σ i , k s e e d ) k i = g ( σ i , k s e e d ) c i = E ( k i , m i ) \sigma_{i+1} = f(\sigma_i, k_{seed}) \\ k_i = g(\sigma_i,k_{seed}) \\ c_i = E(k_i, m_i) σi+1=f(σi,kseed)ki=g(σi,kseed)ci=E(ki,mi)
其中，$ \sigma_0 $ 为初始时刻**流生成器内部的状态，与明文消息无关。 f 为状态转移函数， g为**流生成函数， E 是加密函数 -
优点：加密变换无记忆， 发生错误时只影响对应位而不影响其他位置
-
缺点：通信双方的同步
自同步流密码
-
定义：**流的产生与明密文有关的流密码
-
加密过程
σ i = ( c i − t , c i − t + 1 , . . . , c i − 1 ) k i = g ( σ i , k s e e d ) c i = E ( k i , m i ) \sigma_i = (c_{i-t}, c_{i-t+1}, ..., c_{i-1}) \\ k_i = g(\sigma_i, k_{seed}) \\ c_i = E(k_i, m_i) σi=(ci−t,ci−t+1,...,ci−1)ki=g(σi,kseed)ci=E(ki,mi)
其中 σ 0 = ( c − t , c − t + 1 , . . . , c − 1 ) \sigma_0 = (c_{-t}, c_{-t+1}, ..., c_{-1}) σ0=(c−t,c−t+1,...,c−1)是初始状态， k是**， g是产生**流的函数，E 是加密函数， t位与密文有关的位数 -
优点：强化了加密过程，具有较强的抗统计分析性
-
缺点：单个位错误将影响 t个密文位，发生有限的错误传播
有限状态机
定义
有限状态机是一种具有离散输入和输出的数学模型
组成部分
-
有限状态集 S = { s i ∣ i = 1 , 2 , . . . , l } S = \{{s_i|i=1,2,...,l}\} S={si∣i=1,2,...,l};
-
有限输入字符集 X = { X j ∣ j = 1 , 2 , . . , , m } X = \{{X_j}|j = 1,2, ..,, m\} X={Xj∣j=1,2,..,,m}
-
有限输出字符集 Y = { Y j ∣ j = 1 , 2 , . . , , n } Y = \{{Y_j}|j = 1,2, ..,, n\} Y={Yj∣j=1,2,..,,n}
-
转移函数
Y j = f 1 ( s j , X j ) S j + 1 = f 2 ( s j , X j ) Y_j = f_1(s_j, X_j) \\ S_{j+1} = f_2 (s_j, X_j) Yj=f1(sj,Xj)Sj+1=f2(sj,Xj)
代码
def generate_key(S, X, f_output, f_state):
""" 有限状态自动机
params:
S: 初始状态, 任何类型
X: 输入字符集， 列表
Y: 输出字符集， 列表
f_output: 输出转移函数， 函数或字典
f_state: 状态转移函数， 函数或字典
"""
if isinstance(f_output, dict) and isinstance(f_state, dict):
state, output = [S], []
for x in X:
cur_state = f_state[(S, x)] if (S, x) in f_state.keys() else None
cur_output = f_output[(S, x)] if (S, x) in f_output.keys() else None
state.append(cur_state)
output.append(cur_output)
S = cur_state
return state, output
elif callable(f_output) and callable(f_state):
state, output = [S], []
for x in X:
cur_state = f_state(S, x) if f_state.__code__.co_argcount >= 2 else None
cur_output = f_output(S, x) if f_output.__code__.co_argcount >= 2 else None
S = cur_state
state.append(cur_state)
output.append(cur_output)
return state, output
else:
print("""
f_output, f_state 为同一种类型，字典或者函数
""")