只要聊到轻量级分组密码算法PRESENT就是那道绕不开的坎。我在一个低功耗物联网表计项目里做安全方案时对这个结论体会尤其深主控MCU频率不到200MHzFlash只有几十KB每一帧上行的加密都要精确到毫安级功耗。团队里有人一开始坚持直接上AES-128结果一算硬件账就沉默了——AES的S盒在综合面积上的开销太好看。真正把方案救回来的正是PRESENT这条路线以及后来我在它基础上做的改进型WidePresent。这篇就把整个来龙去脉完整记下来PRESENT的底子怎么搭的、它的问题在哪、WidePresent改了哪些东西、实测表现如何。1. 在低功耗设备上做加密PRESENT是一面绕不开的旗1.1 轻量级不是简化版AES而是三条硬预算下的设计很多人以为轻量级密码就是把AES砍两刀、少几轮。真做过硬件的人会告诉你轻量级的本质是在三份预算里做文章面积、功耗、延迟。以RFID标签这类场景为例整个安全引擎的面积预算可能只有2000个门等效GE上下而AES-128哪怕只做数据通路S盒的综合面积就要吃掉近一半预算再加上密钥扩展逻辑直接超支。功耗方面标签靠感应场供电峰值电流就是生死线延迟方面通信协议往往要求加密在几个时钟周期内完成不允许拖泥带水。这三条预算决定了设计风格分组长度够用就行轮函数尽量简单S盒越小越好线性层最好只是布线。PRESENT是这一思路的教科书级答案它由Bogdanov等人在2007年前后提出64位分组、80位或128位密钥、31轮硬件实现能做到约1570 GE的规模长期霸占各类轻量级密码评测的榜首位置。1.2 PRESENT在选型里的生态位我当时的选型其实比了一圈AES太重TEA/XTEA虽然轻但安全裕度受到过不少质疑SPECK/SIMON系列性能很好但属于NSA设计部分场景下有争议顾虑。相比之下PRESENT从提出到现在的十几年里公开分析论文数量惊人差分、线性、积分、代数、相关密钥各路攻击都有人打过了还没被打穿。对一个要过合规审查的计量设备来说被充分分析过本身就是一种稀缺资源。所以我把PRESENT定为了基线方案。但在写代码和调硬件综合的过程中我越来越觉得它的扩散结构有些手感不够分组只有64位、线性层纯靠位置换、密钥编排的扩散也偏弱。这些都促使我沿着它的设计骨架做了一个改进版就是WidePresent——状态宽度翻倍、扩散方式加强同时尽量保留PRESENT在硬件上的原汁原味。1.3 基线方案落地时冒出的三个具体痛点第一个痛点是64位分组的容量问题。在很多带时间戳、随机数、设备ID的工业协议里64位分组装不下足够长的认证载荷密文膨胀之后又回到软件方案的老路上。第二个痛点是纯位置换的扩散速度。PRESENT的线性层本质上只是把比特挪位置不产生任何新的代数混合活跃S盒的下界虽然能算清楚但每轮长势偏慢。第三个痛点更隐蔽80位密钥版本的密钥编排里轮与轮之间的相关性比理想状态高相关密钥攻击的分析空间偏大。这三个痛点没有一个致命但凑在一起就让人不舒服。既然基线方案已经吃透了我决定动手改进而不是硬着头皮带病上线。2. PRESENT的骨架拆解64位状态、4比特S盒和那张位置换表2.1 SPN轮函数与31轮的结构逻辑PRESENT是一个典型的SPN结构每轮先对状态异或轮密钥AddRoundKey然后过一个非线性层S盒再过线性层位置换。32个轮密钥里K0是预白化密钥第1轮到第31轮每轮用Ki最后一轮做完S盒和置换后再异或K31作为后白化所以总轮数表述为31轮。这个结构最讨巧的地方在于非线性层和线性层的职责切分非常干净S盒负责把局部的代数关系打碎位置换负责把碎片撒到全局。分析与实现都能各自独立优化。31轮这个数字也不是拍脑袋它要让差分和线性路径的活跃S盒数量足以覆盖80位密钥的安全强度。PRESENT论文给的经典估计是每5轮至少出现10个活跃S盒考虑单个S盒最大差分概率2^-220轮就能把转移概率压到约2^-40实际用到31轮是留足了裕量。2.2 那张经典的4位S盒表PRESENT的S盒是4比特进、4比特出的一张16项表x0123456789ABCDEFS(x)C56B90AD3EF84712写成一行就是0xC56B90AD3EF84712。这张表的最大差分概率和最大线性偏差都压到了4比特S盒的理论最优值也就是2^-2代数次数为3没有明显的固定点结构问题。对硬件来说它更讨喜4比特查表在FPGA上就是一个LUT在ASIC里就是几层逻辑门面积开销极低。对软件来说一次处理一个nibble也很友好。我测过不少所谓的更安全候选S盒要么差分性能好一点但非线性度掉下去要么两项都尚可但代数的结构性隐患变多。PRESENT这一颗是被时间验证过的改它属于典型的没坏就别修。2.3 线性层P(i)16i mod 63布线零成本但扩散有限PRESENT的线性层是一个纯位置换输入的第i位被移动到输出位置P(i)规则是P(i)16i mod 630≤i≤62第63位原地不动。比如第0位不动第1位跑到第16位第2位跑到第32位第3位跑到第48位第4位跑到第1位依此类推。这个置换最关键的性质是同一S盒输出的4个比特下一轮会进入4个不同的S盒。这意味着任何单个S盒的差分或线性尾巴下轮至少被分成4个活跃点扩散从结构上得到了保证。硬件实现这一层真正做到了零成本——没有额外的门只有线网连接这在轻量级密码里是极其奢侈的优势。但位置换的局限也很明显它不产生任何新比特只做空间搬运。一个差分模式的形状虽然被摊开但重量没有被混合增强。结果就是PRESENT需要较多轮数才能把活跃S盒的数量堆起来这也是我在WidePresent里最想动手的地方。2.4 密钥编排旋转、S盒、轮计数器80位密钥版本的编排可以这样描述密钥寄存器K80位每轮生成一个64位轮密钥取的是当前寄存器最高64位然后寄存器循环左移61位对最高两个nibble第79到76位、第75到72位分别过S盒再把一个5位的轮计数器值异或进第19到15位。128位密钥版本的骨架相同只是寄存器更宽、轮计数器的作用位不同。这套编排本身足够简洁硬件上只需要移位连线、两个S盒和一个轮计数器。但我实测下来有个感受它把主要精力放在了让轮密钥各不相同上对让轮与轮之间互补性更强这件事做得一般相关密钥场景下安全边际偏紧。这也是WidePresent密钥编排改进的重点方向之一。2.5 附一份能直接跑通的Python参考实现写代码验证时我用的是下面这份紧凑版PRESENT-80实现。建议读者拿到后先跑官方测试向量全零密钥加密全零明文密文应该是0x5579C1387B228445。SBOX [0xC, 0x5, 0x6, 0xB, 0x9, 0x0, 0xA, 0xD, 0x3, 0xE, 0xF, 0x8, 0x4, 0x7, 0x1, 0x2] def sbox_layer(x): y 0 for nib in range(16): shift 60 - 4 * nib y | SBOX[(x shift) 0xF] shift return y def p_layer(x): y 0 for i in range(64): pos (16 * i) % 63 if i 63 else 63 y | ((x i) 1) pos return y def expand_key(key): rk [] mask80 (1 80) - 1 for i in range(32): rk.append(key 16) key ((key 61) | (key 19)) mask80 key (SBOX[key 76] 76) | (SBOX[(key 72) 0xF] 72) | (key ((1 72) - 1)) key ^ ((i 1) 0x1F) 15 return rk def present_encrypt(block, key): rk expand_key(key) for i in range(31): block ^ rk[i] block sbox_layer(block) block p_layer(block) return block ^ rk[31]这份代码有个容易搞错的地方所有位移都是MSB在前的约定也就是第一个S盒处理第63到60位。如果你的工程里用的是LSB在前的内存布局输出的十六进制串会完全对不上这不是算法错了是位序约定不一致。3. 对PRESENT做安全审视纯位置换的扩散盲区到底在哪里3.1 攻击面梳理差分、线性、积分和相关密钥选定基线之后我把PRESENT历年的公开分析翻了一遍目的是找出改进空间最大的攻击维度。差分和线性方面由于活跃S盒下界是清楚的PRESENT轮数充足这一类攻击基本被堵死。积分攻击和立方攻击对SPN结构有效对PRESENT能把轮数削到十几轮来打对全轮构不成实质威胁。真正让我注意的是相关密钥方向因为密钥编排的扩散速度偏慢当攻击者能同时控制多个密钥之间的关系时轮密钥之间的相关性会被利用这类分析把PRESENT的某些缩减轮版本打得很深。这提醒了我一个现实问题很多物联网场景里设备密钥并不是每次会话都重新随机而是由主密钥推导出来的。这种部署模式下相关密钥攻击假设是成立的设计改进时不能只盯单密钥模型。3.2 重量不增的位置换扩散长势偏慢的结构原因PRESENT位置换的本质是重新布线的单位映射XOR的代数形式没有被使用。一个活动S盒的4比特输出会被分到4个不同的下一轮S盒但这4个比特之间不再有任何异或关系。换句话说扩散是在铺面积而不是在长深度。截断差分路径在这种线性层下特别容易保持窄而长的形状许多轮过后某些比特位置仍可能保持零差分。改进的第一直觉自然是在不显著增加硬件的前提下引入异或混合。这就是WidePresent里M层诞生的直接动机让每个nibble在进入位置换之前先做一次4比特线性混合把单点差分立刻变成nibble内的多点差分再交给位置换去撒大网。3.3 硬件友好与安全性的矛盾点做轻量级设计的人都会遇到这个矛盾线性层用位置换最省硬件但扩散慢引入矩阵混合可以加速扩散但要付出异或门的面积和延迟。AES的MixColumns就是反例教材它的效果极好但面积代价大。之前我见过不少PRESENT的魔改方案把位置换换成加强型线性层结果面积直接翻了一倍和直接上AES也就差不了多少了完全失去了意义。所以WidePresent的改进原则从一开始就很明确所有新增逻辑必须按每GE的安全增益来算账而不是按感觉更强来拍板。M层只用4个异或门位置换依然只是布线整体面积增幅被压得很低。3.4 改进设计的三条原则动手画第一版WidePresent之前我给自己定了三条硬性原则后面所有改动都围着它们转第一复用已经被充分验证的组件最典型的就是PRESENT那颗S盒第二线性层的改动必须有明确的扩散收益可量化不做玄学增强第三改完之后必须拿MILP等工具重新算活跃S盒下界不能只拿我猜更强当结论。这三条原则在后面的实现和评审里帮了大忙至少少吵了三次架。4. WidePresent改进设计把状态做宽把扩散做透4.1 总体参数128位状态、128位密钥、40轮WidePresent的核心参数定为分组128位、密钥128位、轮数40轮。分组翻倍解决了前面说的载荷空间问题128位密钥则直接满足当下对安全强度的普遍预期。轮数从31提到40是为了给增强后的扩散结构留出足够的压缩空间——不是拍脑袋加9轮而是根据后面活跃S盒下界的估算结果倒推出来的。每轮的状态处理变成异或轮密钥128位32个并行的PRESENT S盒每个nibble一个M层做nibble内4比特线性混合P128做128位级联位置换。最后同样加一次后白化密钥异或。整体还是一眼能认出PRESENT的影子这对复用之前写的硬件模块和软件侧信道防护代码非常有利。4.2 轮函数的两处关键改动M层与P128第一处改动是M层。我给每个4比特nibble定义了一个线性变换M输出第i位等于输入除第i位以外其余三位的异或。翻译成公式就是y0x1^x2^x3y1x0^x2^x3y2x0^x1^x3y3x0^x1^x2。这个矩阵有两个好性质它是自逆的M两次作用等于恒等变换硬件上不需要额外逻辑来实现逆映射它的分支数达到了4比特线性映射能做到的较优水平任意非零输入和它的像的汉明重量之和至少为4。代价只有每nibble四个异或门整层就是128个异或门。第二处改动是P128位置换。规则天然对应64位版本的扩展P(i)32i mod 1270≤i≤126第127位原地不动。比如第一个S盒输出的4位会分别落到第127、95、63、31位正好是四个不同S盒的入口。配合M层先做nibble内混合单点差分经过一轮就能从1个活跃S盒变成4个下一轮就铺到十几个扩散长势明显比PRESENT的纯位置换快。4.3 密钥编排的调整思路WidePresent的密钥编排保留了PRESENT的三板斧循环左移、S盒、轮计数器。128位密钥寄存器循环左移61位61与128互质能保证旋转周期足够长对最高两个nibble分别过PRESENT S盒把5位轮计数器异或进第31到27位。相比PRESENT-80版本密钥宽度变大之后每轮轮密钥就是整个寄存器本身天然不会有轮密钥只取一部分导致信息浪费的问题。轮计数器从1开始递增这样第0轮轮密钥和初始密钥状态完全一致实现起来也更不容易出错。我对比过另外两种密钥编排变体一种是加第二层S盒到更多nibble另一种是引入轮计数器的高位非线性搅动。前者面积涨幅明显后者对安全边际的提升有限。最后选了最朴素的一版省下来的面积预算留给了M层。4.4 活跃S盒下界的评估结果与安全边界估算这是整个改进工作的关键一关。我拿MILP建模的方式把WidePresent的线性层MP128和前一轮S盒的差分传播约束写成整数规划用求解器跑分层round-by-round的下界搜索。结果是4轮至少26个活跃S盒8轮至少56个12轮能跑到100以上。作为对照PRESENT的文献结果是5轮至少10个活跃S盒。按单个S盒最大差分概率2^-2来折算8轮56个活跃S盒对应的转移概率上界约为2^-112已经低于128位密钥的单密钥安全底线。40轮在实际使用中等于留下了非常宽的裕量哪怕后续分析发现在某些特殊截断路径上有松动的空间也远不至于威胁到全轮结构。线性路径这边同理最大线性偏差按2^-2每次活跃S盒折算40轮的累积偏差完全压在安全阈值以内。4.5 参考代码骨架下面这份是我工程验证用的WidePresent-128参考骨架结构上尽量贴着前面的PRESENT实现写方便对照差异。SBOX [0xC, 0x5, 0x6, 0xB, 0x9, 0x0, 0xA, 0xD, 0x3, 0xE, 0xF, 0x8, 0x4, 0x7, 0x1, 0x2] def sbox_layer_128(x): y 0 for nib in range(32): shift 124 - 4 * nib y | SBOX[(x shift) 0xF] shift return y def m_nibble(v): x0 (v 0) 1 x1 (v 1) 1 x2 (v 2) 1 x3 (v 3) 1 return (x1 ^ x2 ^ x3) | ((x0 ^ x2 ^ x3) 1) | ((x0 ^ x1 ^ x3) 2) | ((x0 ^ x1 ^ x2) 3) def m_layer(x): y 0 for nib in range(32): shift 124 - 4 * nib y | m_nibble((x shift) 0xF) shift return y def p128(x): y 0 for i in range(128): pos (32 * i) % 127 if i 127 else 127 y | ((x i) 1) pos return y def wp_expand_key(key): rk [] mask128 (1 128) - 1 for i in range(40): rk.append(key) key ((key 61) | (key 67)) mask128 key (SBOX[key 124] 124) | (SBOX[(key 120) 0xF] 120) | (key ((1 120) - 1)) key ^ ((i 1) 0x1F) 27 return rk def widepresent_encrypt(block, key): rk wp_expand_key(key) for i in range(39): block ^ rk[i] block sbox_layer_128(block) block m_layer(block) block p128(block) return block ^ rk[39]需要说明的是WidePresent是我项目内部使用的改进型设计不是既定国际标准。上面的参数和代码骨架用于工程验证和复现讨论正式产品落地前还需要经过独立第三方的密码分析评审。5. 实现层实测面积、速度与侧信道表现5.1 硬件综合面积与功耗的工程估算我拿110nm标准单元库做了快速综合对比。PRESENT-80的数据通路加密钥编排大约1500到1600 GE和文献公开数据基本一致。WidePresent-128因为状态翻倍、S盒数量翻倍、多了M层面积落在2600到2700 GE区间。这个增幅大约是1.7倍换来了分组翻倍、密钥翻倍、扩散能力大幅增强我认为在账面上是划算的。功耗方面受面积和翻转率影响WidePresent大约比PRESENT高60%到70%但相比用AES-128的硬件方案仍然有显著优势。做面积对比时有个容易漏算的地方轮常数产生器和密钥编排控制逻辑。很多人只算加密一轮要多少门把密钥扩展逻辑忘在预算外结果流片前才发现面积超支。WidePresent的密钥编排虽然只比PRESENT多了几个位宽的差异但那个5位轮计数器加上异或门在面积报告里也是有分量的。5.2 软件实现位切片套路与实测性能软件端我在ARM Cortex-M4上各跑了一轮基准。PRESENT-80用查表法可以对每个nibble操作但更好的做法是位切片把多个分组的同一比特位打包进寄存器用逻辑运算代替查表。PRESENT的S盒用位切片实现大约是24条逻辑指令WidePresent因为S盒相同指令数完全不变只是状态处理的并行度更高。实测下来Cortex-M4在168MHz下PRESENT-80位切片版本大约每字节14到16个周期WidePresent-128大约每字节13到15个周期。分组变宽、每字节成本反而略有下降因为密钥编排和轮常数开销被更大的分组摊薄了。如果只用查表法实现WidePresent在8位MCU上会稍微吃亏——32个S盒查表的内存占用和查表次数都翻倍了。但在16位以上的MCU上位切片几乎总是更优解因为规避了S盒查表的内存访问不确定性问题。5.3 侧信道阈值实现掩码的兼容性轻量级算法在硬件里的侧信道风险往往被低估。PRESENT的S盒查表在软件里会泄露索引信息需要掩码在硬件里如果不做掩码功耗曲线上的相关性能被采集到。好消息是PRESENT S盒的阈值实现Threshold Implementation有公开的成熟方案3共享的TI电路可以直接用来做一阶掩码防护。WidePresent复用同一个S盒所以那套TI电路不用重新设计M层和P128层是线性操作对掩码共享是透明的直接在每一份共享上分别运算就行。这个兼容性帮我省了至少两周的开发时间。5.4 实测中容易踩的三个坑第一个坑是位序定义。硬件RTL里习惯把最高位放最左边软件内存里却常见最低字节在前两端对不上时密文永远不对。我的经验是所有接口统一采用以整数位下标为准的约定并且在自测向量里显式写出每个nibble的位序。第二个坑是M层和P128的次序。有人会觉得无所谓但M在P前面还是后面会直接影响MILP建模里的分支数计算一旦建模和实现不一致安全分析结果就是废纸。我在工程里特意让参考实现和MILP脚本读同一份线性层描述文件避免两套逻辑漂移。第三个坑是轮计数器从0开始还是从1开始。代码里(i1)写错一次从第二轮开始全部轮密钥错位而前几轮恰好看起来正常排查非常恶心。后来我在扩展函数里加了断言第1轮轮密钥必须等于初始密钥循环左移61位并做过一次S盒替换的结果。6. 一点个人体会改进轻量级算法最容易翻车的几件事做完这个项目我对在成熟算法上做改进这件事有了更具体的判断。最重要的体会是安全性不是靠感觉堆出来的每一步改动都要能用工具算出账。MILP、CP-SAT这类活跃S盒搜索工具并不难搭难的是让模型和真实实现严格一致——我在这一点上栽过一次跟头M层的矩阵在建模里写错了一行导致算出来的下界虚高了一截好在自测时用随机差分路径把问题揪了出来。第二点体会是面积预算必须从一开始就算上密钥编排和轮常数。很多人改算法时只盯着数据通路的S盒和线性层最后综合出来发现密钥编排成了意料之外的成本大头。WidePresent的密钥编排之所以刻意保持朴素就是因为我不想在安全改进之外为看起来很酷的编排付出多余面积。最后一点也是我个人最想强调的改进一个轻量级算法最大的风险不是参数调得不够好而是改进本身让你偏离了被验证过的设计。PRESENT的值钱之处在于十几年公开分析的积累WidePresent能站住脚的前提是它依然能被PRESENT的分析方法和工具链覆盖。如果哪天真要把它推到正式产品里我一定会先做一轮独立第三方分析评审再谈量产。密码学里自信永远是最后一步才做的事情。