基于元胞自动机置换网络的密码哈希函数设计

《Applied Sciences》:Design of a Cellular Automata-Based Permutation Network for Cryptographic Hash Functions

【字体: 大 中 小 】 时间:2026年09月19日 来源:Applied Sciences 2.5

编辑推荐:

  密码哈希函数依赖高效的内部置换机制来实现安全数据完整性验证所需的扩散与非线性变换。本文提出一种旨在集成于密码哈希函数的基于元胞自动机的置换网络(Cellular Automata-Based Permutation Network, CAPN)。所提出的方法将

  
密码哈希函数依赖高效的内部置换机制来实现安全数据完整性验证所需的扩散与非线性变换。本文提出一种旨在集成于密码哈希函数的基于元胞自动机的置换网络(Cellular Automata-Based Permutation Network, CAPN)。所提出的方法将初等元胞自动机与混合元胞自动机同互补非线性变换阶段相结合,构建一个能够在哈希处理全过程中增强信息扩散并引入动态状态变换的内部状态变换网络。为验证所提出的设计,该状态变换网络被集成到一款以C#语言开发的密码哈希算法软件实现中。研究人员实现了多种不同摘要长度的哈希配置并进行了实验评估。所得结果表明,所提出的状态变换网络实现了有效扩散,产生的雪崩效应值接近理论最优值,同时其软件实现利用并行位运算实现高效状态处理。这些发现表明,元胞自动机可为密码哈希函数的内部置换机制提供统一设计,并推动对其密码分析特性、性能优化以及在不同哈希架构中集成方式的进一步研究。

论文解读

一、研究背景与问题

密码哈希函数是现代网络安全基础设施的基础构建模块之一,广泛应用于数据完整性验证、数字签名、消息认证、密码保护、区块链技术及各类安全通信协议。与提供可逆变换以实现机密性的加密算法不同,密码哈希函数通过不可逆的单向变换,将任意长度的消息生成固定长度的摘要,任何对原始消息的比特级修改都应产生显著不同的输出摘要,从而实现可靠的完整性验证并防止原始输入的重构。
在现有标准中,SHA-2系列及其后继者SHA-3是最广泛部署的哈希算法。SHA-3基于海绵结构(sponge construction)和专用内部置换函数,其设计哲学与SHA-2存在根本差异。然而,无论采用何种结构,哈希函数的有效性在很大程度上取决于其内部置换机制在整个内部状态中高效分布信息、同时保持高非线性和抗密码分析攻击能力。
在此背景下,元胞自动机(Cellular Automata, CA)因其能够通过局部演化规则的重复应用产生高度复杂的全局行为而受到越来越多的关注。元胞自动机具有内在并行性、确定性演化以及可通过基本逻辑运算高效实现等特点,已在伪随机数生成、对称加密、图像加密及密码哈希函数设计等领域得到广泛应用。然而,现有基于元胞自动机的哈希方法大多仅将元胞自动机作为辅助组件或聚焦于特定变换阶段,系统性地基于元胞自动机原理构建完整内部状态变换网络的研究仍相对匮乏。这一研究空白构成了本研究的核心动机。

二、研究内容与主要结论

本研究提出了一种基于元胞自动机的置换网络(CAPN),旨在集成于密码哈希函数中。该方案在保留整体哈希框架的前提下,通过集成初等元胞自动机、确定性变换阶段和基于混合元胞自动机的轮值生成器,重新设计了内部置换机制。所提出的状态变换网络由八个连续轮次组成,每轮依次执行五个变换阶段,分别对应Keccak置换中的θ(Theta)、ρ(Rho)、π(Pi)、χ(Chi)和ι(Iota)函数,但每个阶段均通过专门的元胞自动机机制实现。
实验评估表明,所提出的CAPN在256位和512位两种摘要配置下均展现出接近理论最优值的雪崩效应,平均雪崩比率分别为49.89%和50.05%。NIST统计测试套件(SP 800-22)的评估结果显示,两种配置在所有适用测试中均达到98/100或更高的通过率,表明生成的输出序列在统计特性上与随机行为一致。内部差分传播分析显示,单个比特的初始差异在连续CAPN轮次中迅速扩散至整个内部状态。

三、关键技术方法

本研究采用的主要技术方法包括:基于海绵结构的哈希处理框架,采用1600位内部状态,组织为5×5×64的三维结构;初等元胞自动机(ECA)用于θCA扩散阶段和χCA非线性混合阶段,每轮采用不同演化规则;规则240的重复演化用于实现ρCA传播阶段和πCA车道重分布阶段;基于规则90和150的混合元胞自动机(HCA)生成器用于ιCA轮相关值注入;软件实现采用C#语言,利用64位无符号整数数组表示内部状态,通过位级并行运算实现高效的元胞自动机演化。

四、研究结果

元胞自动机基础与CAPN架构设计。 研究首先建立了适用于密码应用的元胞自动机理论基础,包括初等元胞自动机和混合元胞自动机的演化规则与边界条件。所提出的CAPN采用周期边界条件的初等元胞自动机构成状态变换网络,而混合元胞自动机生成器则在固定边界条件下运行。
θCA扩散阶段。 该阶段对应原始θ变换,将25条车道中的每一条视为沿z轴分布的64个二元单元组成的一维元胞自动机,每轮采用不同的初等元胞自动机规则(规则30、86、90、101、105、150、153和165),以增强状态演化的多样性。
ρCA传播阶段。 该阶段对应原始ρ变换,通过规则240的重复演化实现车道内的信息位移。在周期边界条件下,规则240的一次演化在数学上等价于一位循环移位,因此保留了原始变换的旋转偏移量和最终位位置。
πCA车道重分布阶段。 该阶段对应原始π变换,将内部状态的每行和每列解释为一维元胞自动机,其单元为完整的64位车道而非单个比特。通过规则240的连续应用实现车道在5×5状态平面上的重新分布,生成的新映射与原始映射不同但实现相同的车道分散功能。
χCA非线性混合阶段。 该阶段对应原始χ变换,是主要的非线性变换。对于每行和每位位置,沿x轴分布的五个对应单元构成独立的周期五单元元胞自动机。每轮采用不同的布尔转移函数(规则30、86、90、101、105、150、153和165),增加了局部变换的多样性。
ιCA轮值注入阶段。 该阶段对应原始ι变换,采用两个独立的32单元混合元胞自动机(规则90和150组合),以公开种子初始化,生成64位轮相关值并注入到状态中的三个不同车道(车道0、7和18),通过异或操作打破潜在的结构对称性。
软件实现与计算优化。 1600位内部状态以25个64位无符号整数表示,利用原生位运算实现所有64个元胞的并行演化,显著减少了显式操作数量。
雪崩效应评估。 对100对独立生成的输入消息(每对包含原始消息及其单比特修改版本)进行实验,CAPN-256和CAPN-512配置的平均雪崩比率分别为49.89%和50.05%,95%置信区间分别为49.25–50.53%和49.61–50.49%,均接近理论最优值50%。
NIST统计测试。 对约1,000,000比特的哈希输出序列进行NIST STS评估,两种配置在所有适用测试中均达到98/100或更高的通过率,表明输出序列在统计特性上与随机行为一致。
布尔函数特性分析。 对θCA和χCA阶段使用的所有初等元胞自动机规则进行了布尔函数特性表征,除规则110外,所有规则均为平衡函数,布尔非线性度达到三变量平衡布尔函数的最大值2,代数次数为2。

五、讨论与结论

研究讨论指出,所提出的CAPN在扩散行为和输出统计特性方面提供了初步的实验证据,但这些结果不应被解释为确立了原像抗性、第二原像抗性或碰撞抗性。对于理想哈希函数,256位和512位摘要的通用穷举搜索复杂度参考值分别为2256和2512次操作(原像和第二原像攻击),碰撞搜索复杂度分别为2128和2256次操作。这些值由摘要长度决定,作为理想哈希参考复杂度而非所提出配置的经验验证安全级别。
研究结论表明,所提出的CAPN在两种评估的摘要配置下均展现出有效扩散和统计分布良好的哈希输出,同时引入了基于元胞自动机的内部状态变换网络实现。结合观察到的内部差分传播特性,这些结果为所提出的架构提供了令人鼓舞的实验支持,并推动其作为海绵哈希中内部状态变换的替代方法继续研究。未来工作将聚焦于扩展CAPN、进行专门的密码分析评估(包括差分和线性传播、代数次数演化、降轮分析等)、性能优化以及FPGA硬件加速实现。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号