代数密码类型

Source: Dev.to

代数密码类型

在我们能够定义密码函子之前，需要先定义我们将要使用的代数结构。密码函子提供了一种将幺半群提升为密码幺半群的方法。

群与幺半群

群是一个集合 $G$，以及一个运算 $* : G \times G \to G$，它将任意两个元素 $a$ 和 $b$ 组合成另一个元素 $a*b$。要成为群，集合与运算 $(G, *)$ 必须满足四条被称为群公理的要求：

• 闭合性：对所有 $a,b \in G$，运算结果 $a*b$ 仍然属于 $G$。
• 结合性：对所有 $a,b,c \in G$，有 $(ab)c = a(bc)$。
• 单位元：存在一个元素 $e \in G$，使得对每个元素 $a \in G$，都有 $ea = ae = a$。该元素唯一，因而称为单位元。
• 逆元：对每个 $a \in G$，存在一个元素 $a’ \in G$ 使得 $a*a’ = a’*a = e$，其中 $e$ 为单位元。

幺半群 $(S,*)$ 通过去除逆元的要求而放宽了群的条件。

密码函子

在密码函子中，我们将幺半群 $(S,)$ 提升为 $c_A(S,)$，其定义如下：

• $A$ 是 $S$ 的一个子集。
• $s : S \times \mathbb{N} \to c_A S$ 将 $S$ 映射到 $c_A S$ 中的表示，即 $s(a,k)$ 将元素 $a \in S$ 映射为 $c_A S$ 中的第 $k$ 个表示。
• $s’ : c_A S \to S$ 满足 $s’(s(a,k)) = a$ 且 $s(s’(j),k) = c_A a$，对任意 $a \in S$ 和 $k \in \mathbb{N}$ 均成立。

通常，$s$ 由另一个以密钥和每个表示的固定比特长度为参数的函数生成。

$c_A(S,*,e)$ 具有一个运算 $(c_A *) : (c_A S, c_A S) \to c_A S$，其由以下公理给出：

• 结合性：对所有 $x,y,z \in A$，
  $s’((c_A x * c_A y) * c_A z) = s’(c_A x * (c_A y * c_A z))$。