密码杂凑算法XuanWu512设计原理详解什么是密码杂凑算法密码杂凑算法是一类单向压缩算法它的输入为任意长度(通常为不大于2^64位2^128位2^256位)的一段消息输出为固定长度(通常为128位160位224位256位384位512位)且看似随机的杂凑值。其可以应用于密码存储网盘文件上传密钥扩展算法区块链消息完整性验证随机数生成以及数字签名等。作为对称密码的重要分支之一密码杂凑算法在信息安全领域的重要性不言而喻同时该类算法的设计与分析是既是重点也是难点。密码杂凑算法的整体结构常见的密码杂凑算法整体结构有经典MD结构(MD5SHA-0SHA-1SHA-2SM3HAVALDHA-256等)宽管道结构(GrøstlGOST等)UBI模式(Unique Block Iteration链式结构)(Skein等)HAIFA结构(BLAKE等)和海绵结构(Sponge Structure)(SHA-3JHPHOTONQUARKKetjeKeyak等)。密码杂凑算法的设计应该满足三条基本准则抗碰撞性对于密码杂凑算法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为基于经典MD结构(消息填充消息扩展消息压缩)设计的迭代型密码杂凑算法。其支持输入的消息长度不大于2256比特输出杂凑值的长度为(256比特512比特1024比特)推荐使用512比特长度的杂凑值。本算法有2大亮点一是压缩函数使用先膨胀后挤压的设计理念这保证了算法的单向性(不可逆性)也即XuanWu512算法正向计算很容易反向计算很困难二是使用了基于4维二元非线性扩散函数MMMM4M(基于模加运算)因为模加运算相比异或运算更加复杂及其密码学性质更好所以这使得该算法保证了高效率的同时兼具安全性。容易证明MMMM4M为双射。证明过程详见基于4维二元扩散矩阵的线性变换和非线性变换的双射性质证明。XuanWu512算法的执行过程可以分为3个部分(消息填充算法消息扩展算法消息压缩算法)如下图所示其中初始链接变量如下图所示以下我将详细介绍XuanWu512算法的详细设计细节。1消息填充算法首先对输入的消息进行填充使其长度变为512的倍数。填充方法是在原始消息末尾添加一个“1”位然后添加一定数量的“0”位最后再添加256位的消息长度HEX(Length)使得填充后的消息长度为512的整数倍。然后将填充后的消息以512位为单位进行分组。2消息扩展算法(MsgExtend)MsgExtend的输入为512比特的当前消息分组M16个32比特常量Const输出为64个32比特的扩展消息ExtM。具体实现细节如下图所示3消息压缩算法(共16轮)将当前链接变量(2048位共64个32位字)与2048位扩展后的消息依次输入压缩函数进行压缩运算直到最后一个消息块处理完毕此时压缩函数的输出的结果的低512位(如果杂凑值为512位)即是该消息的杂凑值。XuanWu512的消息压缩算法如下图所示其中按行分组函数Row如下图所示其中按列分组函数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如下图所示其中行移位变换ShiftRow如下图所示其中列移位变换ShiftColumn如下图所示本文的总结密码杂凑算法的设计是一个高度专业化的领域需要在数学基础、密码学原理和工程效率之间取得精妙的平衡。其核心在于设计一个健壮的压缩函数或置换函数并将其嵌入到一个安全的结构如 Sponge中。分析则是一个持续的攻防过程利用各种密码分析技术不断检验算法的安全边界。理解密码杂凑算法的设计与分析对于构建安全的密码系统、评估现有系统的安全性以及应对未来威胁如量子计算都至关重要。注意本文中的XuanWu512算法未经公开的评估和测试学术设计仅用于教学与研究切记不要在工作环境中使用该算法违者后果自负。