基于Feistel结构的分组加密算法Smart设计原理详解

基于Feistel结构的分组加密算法Smart设计原理详解Smart属于对称加密算法5大分支之一的分组加密算法基于经典Feistel结构设计轮函数为SPNSubstitution-Permutation Network结构。Smart的分组长度为128比特根据主密钥长度的不同Smart算法可以分为Smart128Smart192和Smart256这3个版本对应的算法循环轮数分别为2428和32。当主密钥长度为128比特Smart128算法的加密过程如下图所示Smart128算法的解密过程如下图所示当主密钥长度为192比特Smart192算法的加密过程如下图所示Smart192算法的解密过程如下图所示当主密钥长度为256比特Smart256算法的加密过程如下图所示Smart256算法的解密过程如下图所示其中轮函数F如下图所示由以上3图我们可以发现Smart128Smart192和Smart256加密算法之间除了密钥扩展算法不同和轮函数循环的轮数不同之外其它地方基本一致。这里我们只介绍Smart128算法对于Smart192和Smart256算法可以依此类推。我们先来看Smart128的轮函数(由3步构成)。1AddRoundKey(轮密钥加)将Ri的8个字节的中间状态分别依次异或对应位的密钥字节具体操作如下图所示AddRoundKey(轮密钥加)的设计目的分组加密中引入轮密钥而非所有轮次共用主密钥的核心目的是破坏轮与轮之间的同构性并充分混入密钥的随机性以抵御多种已知密码分析攻击。具体体现在以下三个层面1.打破对称性抵御“滑动攻击”如果每轮都使用相同的主密钥整个加密过程会呈现“周期自相似性”即轮函数的迭代重复。攻击者可以利用这种结构弱点通过滑动攻击Slide Attack将破解复杂度从指数级降至线性级。轮密钥的差异性直接切断了这种利用路径使每一轮的变换都具有独特的密钥约束。2.实现密钥的充分混淆与扩散非线性关联轮密钥并非简单切分主密钥而是通过密钥编排算法Key Schedule通常含循环移位、S盒替换等非线性操作生成。这确保了充分扩散主密钥的每一个比特都能影响到多个不同轮密钥的多个比特。强非线性密文与主密钥之间的统计关系变得极其复杂有效抵御线性攻击和差分攻击攻击者无法通过线性逼近或差分传递来猜测密钥3.保障轮间独立性抵御相关密钥攻击复杂的密钥编排确保各轮子密钥之间、子密钥与主密钥之间不存在简单的线性或代数关系。即使攻击者通过旁路攻击如功耗分析部分泄露了某一轮的子密钥也无法反向推导出主密钥或其他轮密钥从而提升了整体的安全冗余。2Substitution(S盒替换)如上图所示加密过程中的8字节x0x1…,x6x7中间状态平行独立地进入8个相同的S盒输出被S盒替换后的16个字节y0y1…,y6y7。该8比特S盒的查找表如下图所示S盒的各项密码学指标如下图所示由上图可以看出Smart算法的S盒密码学性质与AES算法的S盒相当能够很好的抵抗差分和线性密码分析故该S盒可以在分组加密算法中使用。Substitution(S盒替换)的设计目的1. 抵抗差分和线性密码分析如果整个加密过程都是线性的仅包含异或、移位等操作攻击者就可以通过高斯消元法等数学手段将加密过程表示为线性方程组从而直接求解出密钥。S盒通过非线性映射即输出比特是输入比特的非线性函数彻底破坏了这种线性结构使得差分密码分析Differential Cryptanalysis和线性密码分析Linear Cryptanalysis在计算上不可行。2.提供加密算法必需的混淆性S盒是实现克劳德·香农提出的“混淆”原则的关键。它旨在掩盖密钥与密文之间的统计关系。即使明文或密钥只改变1个比特经过S盒替换后输出端会有多个比特发生不可预测的剧烈变化这使得攻击者无法从密文中推导出密钥的任何有效信息。3.抵抗侧信道攻击在实际硬件如FPGA/ASIC中S盒通常以查找表Look-up Table的形式实现仅需极小的门电路即可在单时钟周期内完成替换执行效率极高。同时S盒的非线性特性也能有效抵御侧信道攻击如功耗分析因为非线性运算在物理层面产生的功耗波动比线性运算更难建模。3LLLLLLLL(线性变换)将上个过程中输出的64比特的中间状态当做64位字X然后将X输入LLLLLLLL输出为Y。具体操作如下图所示其中LLLLLLLL的分支数为7扩散性较好强于Camellia算法。LLLLLLLL(线性变换)的设计目的LLLLLLLL变换是克劳德·香农提出的安全密码设计两大基本原则混淆与扩散之一。1. 引发“雪崩效应”P盒负责将S盒非线性替换层输出的数据位进行重新排列和打乱将这一轮输出位的影响分散到下一轮的不同输入位中。这使得明文中任意一位的改变都能通过多轮P盒的扩散影响到后续密文中大约一半的位从而掩盖明文数据的统计结构。2. 实现跨S盒的“层间混合”现代分组密码如AES和DES通常采用“S-P网络”结构。P盒专门负责将不同S盒的输出重新分配并馈送到下一轮的不同S盒中。这种“交叉连接”确保了某一个S盒的非线性变换结果能够影响其他多个S盒打破局部关联性防止密码分析者针对单个S盒进行差分或线性攻击。3. 提升抗攻击能力通过打乱比特位置P盒能有效破坏明文和密文之间的线性关系大幅增加差分密码分析和线性密码分析的难度。攻击者即使掌握了输入输出的差值规律也会因为P盒的扩散作用而无法将其追踪到具体的密钥位。特别需要强调的是P盒本身是线性变换它不能单独提供安全性。如果只使用P盒加密就等于简单的换位置换密码极易被破解。P盒必须与提供“混淆”的S盒非线性替换配合使用——S盒负责掩盖密钥与密文的关系P盒负责打乱数据的分布二者交替迭代才能构成安全的乘积密码。这也是为什么几乎所有现代分组密码都在每轮中交替使用S盒和P盒或线性混合层。Smart128的密钥扩展算法(KeyExtend128)KeyExtend128的实现细节如下图(伪代码)所示其中LLLLLLLL0LLL1LLL2LLL3和ShiftLeft如下图所示KeyExtend(密钥扩展算法)的设计目的分组加密算法使用密钥扩展Key Schedule的核心目的本质上是将“用户输入的短密钥”转化为“多轮迭代所需的多个子密钥”从而用计算复杂度换取安全强度。具体可拆解为以下四大目的1.破除密钥的线性与统计相关性核心安全目的如果直接在每一轮截取主密钥的一部分作为轮密钥那么轮密钥之间会存在极强的线性关系如简单的位移。密钥扩展通过引入非线性变换如AES中的S盒替换和扩散如循环移位、异或确保主密钥中任意1比特的变化都会像“雪崩”一样剧烈影响到所有轮密钥。这能有效抵御相关密钥攻击和差分密码分析让攻击者无法通过已知的轮密钥规律反推出主密钥。2.打破轮函数间的对称性抵御滑动攻击如果每一轮使用的密钥都相同那么算法的轮函数就具有高度对称性。攻击者可以利用这种对称性发起滑动攻击Slide Attack通过寻找明文和密文之间的平移关系来破解。密钥扩展使每一轮使用唯一且不重复的子密钥相当于给每一轮的变换都加入了独一无二的“扰动”彻底破坏了轮结构之间的对性。3.将主密钥的熵均匀“搅拌”到整个加密流程中用户输入的密钥长度通常有限如128位但加密过程往往有10轮甚至更多轮次。密钥扩展将主密钥的“随机性熵”均匀地分散到所有轮次中避免出现某些轮次密钥过强、某些轮次密钥过弱的短板确保加密过程的每一环节都有足够强度的密钥参与混淆和扩散。4.兼顾实现效率与预计算能力虽然密钥扩展本身需要额外计算但它支持提前预计算。在实际应用中如网络加密会话密钥一旦建立CPU可以提前把所有轮密钥算好并存储在内存中当处理大量数据块时每一轮直接查表使用子密钥即可省去了实时派生密钥的时间从而提高在线加密的吞吐量。如果不使用密钥扩展分组密码就像用同一把钥匙重复锁很多道门而密钥扩展的作用就是把一把主钥匙“搓”成十几把形态各异的子钥匙每道门用不同的钥匙且钥匙之间毫无规律可循极大增加了攻击者暴力破解或推导演算的难度。大家对于Smart算法有什么意见和建议欢迎在评论区交流。