密码杂凑算法XuanWu512设计原理详解
密码杂凑算法XuanWu512设计原理详解
什么是密码杂凑算法？
密码杂凑算法是一类单向压缩算法，它的输入为任意长度(通常为不大于2^64位，2^128位，2^256位)的一段消息，输出为固定长度(通常为128位，160位，224位，256位，384位，512位)且看似随机的杂凑值。其可以应用于密码存储，网盘文件上传，密钥扩展算法，区块链，消息完整性验证，随机数生成，以及数字签名等。作为对称密码的重要分支之一，密码杂凑算法在信息安全领域的重要性不言而喻，同时该类算法的设计与分析是既是重点也是难点。
密码杂凑算法的整体结构
常见的密码杂凑算法整体结构有经典MD结构(MD5，SHA-0，SHA-1，SHA-2，SM3，HAVAL，DHA-256等)，宽管道结构(Grøstl，GOST等)，UBI模式(Unique Block Iteration链式结构)(Skein等)，HAIFA结构(BLAKE等)和海绵结构(Sponge Structure)(SHA-3，JH，PHOTON，QUARK，Ketje，Keyak等)。
密码杂凑算法的设计应该满足三条基本准则：
- 抗碰撞性：对于密码杂凑算法Hash，找到消息M1不等于M2，使得Hash(M1)= Hash(M2)是困难的；
- 抗原像攻击：对于密码杂凑算法Hash，找到给定杂凑值H对应的原像M是困难的；
- 抗第二原像攻击：对于密码杂凑算法Hash，给点原像M找到不同的M2使得Hash(M)=Hash(M2)是困难的。
其次，好的密码杂凑算法也应该满足不可逆性，伪随机性和雪崩效应。
不可逆性：正向计算是简单的，逆向计算是困难的；
伪随机性：密码杂凑算法的输出在统计上应与真正的随机函数无法区分。即使知道部分输入或输出的关系，也无法有效预测其他输出；
雪崩效应：输入消息的微小改变（例如翻转一个比特），会导致输出哈希值发生巨大的、不可预测的改变（大约一半的比特翻转）。
本文提出的XuanWu512算法是基于经典MD结构设计的，其使用了SBOX32To128和SBOX512To2048两个4倍膨胀S盒(不是双射)和非线性扩散函数MMMM4M(是双射)，分别提供了密码杂凑算法必须的混淆性和扩散性，更加保证了该算法具有良好的雪崩效应和不可逆性。
XuanWu512算法的执行过程可以分为3个部分(消息填充算法，消息扩展算法，消息压缩算法)，如下图所示：
其中初始链接变量如下图所示：
以下我将详细介绍XuanWu512算法的详细设计细节。
（1）消息填充算法
首先对输入的消息进行填充，使其长度变为512的倍数。填充方法是在原始消息末尾添加一个“1”位，然后添加一定数量的“0”位，最后再添加256位的消息长度HEX(Length)，使得填充后的消息长度为512的整数倍。然后将填充后的消息以512位为单位进行分组。
（2）消息扩展算法(MsgExtend)
MsgExtend的输入为512比特的当前消息分组M，16个32比特常量Const，输出为64个32比特的扩展消息ExtM。具体实现细节如下图所示：
（3）消息压缩算法(共16轮)
将当前链接变量(2048位共64个32位字)与2048位扩展后的消息依次输入压缩函数进行压缩运算，直到最后一个消息块处理完毕，此时压缩函数的输出的结果的低512位(如果杂凑值为512位)即是该消息的杂凑值。XuanWu512的消息压缩算法如下图所示：
其中按列分组函数Column如下图所示：
其中512位到2048位膨胀函数SBOX512To2048AC如下图所示：
其中512位到2048位膨胀函数SBOX512To2048BD如下图所示：
其中512位到2048位膨胀函数SBOX512To2048EG如下图所示：
其中512位到2048位膨胀函数SBOX512To2048FH如下图所示：
其中32位到128位膨胀函数SBOX32To128AC如下图所示：
其中32位到128位膨胀函数SBOX32To128BD如下图所示：
其中32位到128位膨胀函数SBOX32To128EG如下图所示：
其中32位到128位膨胀函数SBOX32To128FH如下图所示：
其中非线性扩散函数MMMM4M如下图所示：
其中列移位变换ShiftColumn如下图所示：
本文的总结
密码杂凑算法的设计是一个高度专业化的领域，需要在数学基础、密码学原理和工程效率之间取得精妙的平衡。其核心在于设计一个健壮的压缩函数（或置换函数）并将其嵌入到一个安全的结构（如 Sponge）中。分析则是一个持续的攻防过程，利用各种密码分析技术不断检验算法的安全边界。
理解密码杂凑算法的设计与分析，对于构建安全的密码系统、评估现有系统的安全性以及应对未来威胁（如量子计算）都至关重要。