基于4维二元扩散矩阵的线性变换和非线性变换的双射性质证明

什么是单射？

设f是由集合A到集合B的映射，如果对所有x，y∈A，且x≠y，都有f(x)≠f(y)，则称f为由A到B的单射。

什么是满射？

设A和B是两个集合，如果从A到B的对应f：A→B是映射，并且集合B中的每一个元素在集合A中都有原象，那么映射f就叫做从A到B的满射。也即如果对于所有的y∈B，都存在x∈A，满足f(x)=y，那么f为满射。

什么是双射？

双射是满足既是单射又是满射的映射，亦称“一一映射”。

     简单来说，一个双射函数是一个既是单射（Injective） 又是满射（Surjective） 的函数，即集合A中的每一个元素都唯一地对应集合B中的一个元素，并且集合B中的每一个元素也都被对应。这意味着双射是可逆的，存在一个明确的逆函数能将输出还原回唯一的原始输入。

加密本质上是一个从明文空间到密文空间的映射过程。

加密过程 (E): 明文 M -> 密文 C

解密过程 (D): 密文 C -> 明文 M

为了确保解密能够正确且唯一地还原出原始明文，加密函数 E 必须是一个双射。

为什么？

单射（一对一）保证了唯一性： 如果两个不同的明文（M1 ≠ M2）被加密成了同一个密文（C），那么当收到密文C时，解密算法将无法确定它原本是M1还是M2。这会造成歧义，解密失败。单射属性杜绝了这种情况，确保每个明文对应唯一的密文。

满射（覆盖全部）确保了有效性： 虽然满射在实践中的重要性稍低（因为密文空间可以比明文空间大），但它保证了每一个可能的密文输出都对应着一个有效的明文输入，使得解密函数对于所有密文都是定义良好的。

结论：一个设计良好的分组密码（如AES）在固定密钥的情况下，其加密函数对单个明文分组而言，应该是一个双射。 这确保了“加密-解密”这个回合的可靠性。

     反过来看，如果加密函数不是双射（比如不是单射），就意味着发生了碰撞（Collision）：多个明文被加密成了相同的密文。这会导致：

信息永久丢失： 无法从密文唯一确定明文。

安全性降低： 攻击者即使不能解密，也能知道某些明文对应的密文是相同的，这会泄露明文的结构信息（例如，加密的数据库中两个用户的薪水密文相同，那么即使不知道具体数额，也知道他们薪水一样）。

     双射属性从根本上避免了加密过程中的信息丢失，保证了数据的完整性能够在解密后完全恢复。

     学过对称加密算法(分组密码算法，序列密码算法，密码杂凑算法，认证加密算法和消息鉴别算法)的都知道，混淆性和扩散性是设计对称密码的两个基本准则。

混淆性：使明文，密钥和密文之间的关系变得尽可能地复杂和难以捉摸。

扩散性：使明文和密钥中的每一位影响密文中的尽可能多的位。

     通过分析我们容易发现，不管是非线性的混淆层S(S盒，与运算，模加运算，模乘运算)，还是线性的扩散层P(MDS矩阵，MDBL矩阵，异或循环移位，循环移位，异或运算，比特置换，字节置换)，它们都满足一个基本的要求：就是双射(既是单射又是满射)。这是因为考虑到对称加密算法必须满足可逆性(分组密码算法，序列密码算法和认证加密算法)和输出比特的平衡性(密码杂凑算法和消息鉴别算法)。所以我们在设计对称加密算法时首先要考虑到的一点就是混淆层和扩散层必须为双射。

本文我将给出两个类似的扩散层(MMMM4X和MMMM4M)的双射性质的证明。

线性变换MMMM4X如下图所示：

而MMMM4X变换又等价于4维向量左乘4维二元矩阵：

非线性变换MMMM4M如下图所示：

结论1：当Xi和Yj(i，j=0，1，2，3)∈F2n时，MMMM4X为双射。

证明(反证法)：

首先定义一些记号，记

A=(A0，A1，A2，A3)，C=(C0，C1，C2，C3)=MMMM4X(A)；

B=(B0，B1，B2，B3)，D=(D0，D1，D2，D3)=MMMM4X(B)。

E=A⊕B=(A0⊕B0，A1⊕B1，A2⊕B2，A3⊕B3)=(E0，E1，E2，E3)；

F=C⊕D=(C0⊕D0，C1⊕D1，C2⊕D2，C3⊕D3) =(F0，F1，F2，F3)。

假设MMMM4X不是双射，则存在A≠B，使得C=D。

也即存在(E0，E1，E2，E3)不全为0，使得(F0，F1，F2，F3)全为0。

由F=C⊕D=MMMM4X(A)⊕MMMM4X(B)=MMMM4X(A⊕B)=MMMM4X(E)可得：

F0=E1⊕E2⊕E3     ①

F1=E2⊕E3⊕E0     ②

F2=E3⊕E0⊕E1     ③

[培训]Windows内核深度攻防：从Hook技术到Rootkit实战！