简介Simon算法的C实现程序面向密码学初学者和对轻量级对称加密感兴趣的开发者以简洁代码演示了NSA提出的Simon分组密码核心流程。资源共1个文件为单个.cpp源文件压缩包整体仅1KB轻量易读适合快速查看算法骨架。目前已有604人浏览/学习。程序通过Simon类封装初始化、密钥扩展、加密与解密方法完整覆盖轮函数中的异或、循环移位、按位与非操作并针对常用变种说明不同块大小与密钥长度的处理方式可结合Simon32/64、Simon48/72等参数理解密钥扩展与加解密迭代逻辑。需要说明的是此实现侧重教学参考可能存在边界条件或性能优化空间阅读者可借此练习代码审查、单测编写与算法比对进而自行完善为可用的嵌入式或实验版本。1. 先分清是哪个 Simon这个标题背后是一族轻量级分组密码GitHub 上以 Simon 命名的仓库一半是四色记忆小游戏另一半是我下面要讲的轻量级分组密码 SIMON。区分它们只需要看标题里的伴随词出现 algorithm、cipher、blockcipher 的基本都是在做加解密实现而像“simon周期查找”这类搜索词往往是从实现往密码分析方向走的信号。SIMON 的价值主要体现在资源受限场景块小、密钥扩展简单、轮函数只有移位和与运算在 Cortex-M 这类平台上代码体积和栈占用都能压得很低。这篇文章会用 C 把 SIMON 32/64 完整实现一遍然后以轮函数迭代为主做周期查找验证状态扩散行为最后落到嵌入式移植时容易踩的坑和回归验证方法。适合正在做 IoT 安全选型、想读懂开源 SIMON 源码或者需要自己维护一个轻量对称加密实现的人。2. SIMON 轮函数与密钥调度用 C 落地 32/64 的完整实现2.1 SIMON 参数族先决定块长、密钥长和轮数SIMON 的命名规则是“SIMON 2n/nk”前面的数字是分组长度bit后面是密钥长度bit。分组长度始终是字长 n 的两倍密钥长度由密钥字个数 m 决定。下面是几个常见变体也是我日常用得最多的几档算法块长 bit字长 n密钥 bit密钥字 m轮数 TSIMON 32/64321664432SIMON 48/72482472336SIMON 64/96643296342SIMON 64/1286432128444SIMON 128/12812864128268SIMON 128/25612864256472本文拿 SIMON 32/64 做例子原因有三个字长 16 位所有中间值都能用uint16_t装下调试时一眼能看懂测试向量网上随处可查轮数只有 32 轮单轮函数在 PC 上做周期查找和差分传播实验都很快。换到其他参数族时只需要把数据类型从uint16_t换成相应宽度并把轮常数和 Z 序列换成对应值结构完全不变。2.2 轮函数里那三次循环移位在做什么SIMON 的轮函数是所有分组密码里最朴素的造型之一。对两个字(x, y)一轮做的事是new_x y ^ ((x 1) (x 8)) ^ (x 2) ^ rk new_y x这里的是循环左移。主心骨是((x 1) (x 8))按位与提供一个非线性项两个移位一个取邻近 bit一个取相隔较远的 bit让输入的某一位在输出里扩散到不同位置。外面的(x 2)再把结果往另一个方向搬一次。理解这个结构有个关键点SIMON 没有 S 盒全部非线性来自一个 AND所以它不怕 FPGA 没有 LUT也不怕 MCU 没有乘加指令。代价是单轮扩散弱必须靠足够多轮数把雪崩效应堆起来。这也是为什么 SIMON 32/64 要 32 轮而同样 32 bit 块的分组密码通常只要 16 轮左右。2.3 密钥调度与 Z 常数线性部分的“调味料”SIMON 的密钥扩展是纯线性运算加轮常数。对 m4 的情况前 4 个轮密钥直接取自主密钥之后的扩展公式是rk[i] rk[i-4] ^ ror(rk[i-1], 3) ^ ror(rk[i-3], 1) ^ c ^ (z_j)_i其中c 0xFFFC也就是2^16 - 4n32 时是0xFFFFFFFC规律是按字长变化。Z 序列是论文里给定的一组固定比特串作用是让每一轮都有一点“不一样的味道”破坏轮与轮之间的对称性否则密钥全零或明文全零时整个加密过程会表现出很强的周期性滑动攻击会变得非常容易。下面这段是我在 PC 上验证用的完整实现密钥扩展和加密写在一起可以直接编译运行#include stdint.h #include stdio.h #define ROL16(x, r) (((x) (r)) | ((x) ((16 - (r)) 15))) #define ROR16(x, r) (((x) (r)) | ((x) ((16 - (r)) 15))) /* Z_0 序列共 62 bit打包成 uint64_t 后最高有效位对应序列第 0 位 */ static const uint64_t Z0 0x3E895873D7D12B0E6ULL; static void simon32_64_keyexp(const uint16_t key[4], uint16_t rk[32]) { int i; for (i 0; i 4; i) rk[i] key[i]; for (i 4; i 32; i) { uint16_t t ROR16(rk[i - 1], 3) ^ ROR16(rk[i - 3], 1); rk[i] rk[i - 4] ^ t ^ 0xFFFC ^ ((uint16_t)((Z0 (61 - (i - 4))) 1)); } } static void simon32_64_encrypt(const uint16_t rk[32], const uint16_t pt[2], uint16_t ct[2]) { uint16_t x pt[0], y pt[1]; int i; for (i 0; i 32; i) { uint16_t old_x x; x y ^ ((ROL16(x, 1) ROL16(x, 8)) ^ ROL16(x, 2)) ^ rk[i]; y old_x; } ct[0] x; ct[1] y; } int main(void) { const uint16_t key[4] {0x0100, 0x0908, 0x1110, 0x1918}; const uint16_t pt[2] {0x6565, 0x6877}; uint16_t rk[32], ct[2]; simon32_64_keyexp(key, rk); simon32_64_encrypt(rk, pt, ct); printf(ct %04x %04x\n, ct[0], ct[1]); return (ct[0] 0xc69b ct[1] 0xe9bb) ? 0 : 1; }这段代码有两个地方需要特别说明。第一是ROL16宏里的 15当 r 为 0 时16 - r等于 16而在 C 里对 16 位整数移位 16 位是未定义行为 15把移位数折回 0。第二是 Z 常数的取位方式Z0是一个 62 bit 序列打包装进 64 位整数后最高两位是 0所以序列第 i 位要右移61 - i提取而不是63 - i。最常见的手滑就是把这两个数写反结果第一轮正确、第二轮开始密钥全是乱的。加密主循环里先保存old_x再更新x因为轮函数里新的右半字是上一轮的左半字这个赋值顺序一旦写反整个密文就不对了。2.4 用公开测试向量做自检上面代码的 main 函数里已经放了一组公开测试向量密钥1918 1110 0908 0100明文6565 6877密文应为c69b e9bb。这里的密钥在内存里的排列是key[0] 0x0100也就是说第一个参与轮函数的是最低位字。如果编译运行后输出一致说明密钥扩展和加密主循环的位序、字节序都对了不一致时先查 Z0 的取位再查ror(rk[i-1], 3)和ror(rk[i-3], 1)的下标是不是写反了。3. SIMON 周期查找用迭代和差分找轮函数的退化点3.1 为什么要对轮函数做周期查找轮函数本质上是一个定义在有限状态集合上的映射。任意给定一个初始状态反复迭代这个映射最终一定会进入一个环前面可能有若干步“尾巴”之后就是不断重复的循环。周期查找就是去量这个尾巴长度和环长。密码学里关心环长的原因很直接如果大量状态能在很短步数内落入同一个短环说明这个映射的状态空间在坍缩输出的随机性比理论值差代数攻击和区分攻击就有了可乘之机。对 SIMON 来说有个更具体的背景它的非线性只来自一个 AND单论代数复杂度肯定不如 AES 的 S 盒。设计者把安全性押在“轮数足够多”上所以周期查找能给一个直观感受——迭代多少轮之后状态不再“看起来像随机”。我在做这类检查时习惯先去掉轮密钥把轮函数当成一个无密钥的映射(x, y) - (y ^ f(x), x)来分析。原因是轮密钥只是对其中一个字做异或相当于对整个状态空间做一个平移单点轨迹的环长分布不会改变太多但计算量小一个量级。这个映射其实是个置换因为给定(x, y)可以唯一还原(x, y) (y, x ^ f(y))。置换的轨迹没有尾巴每一点都在环上。所以对 SIMON 轮函数做周期查找找到的mu应该恒为 0而环长lam的分布可以跟随机置换的理论值对照。3.2 状态迭代的周期查找脚本下面的 Python 脚本把状态打包成一个 32 位整数用字典记录每个状态首次出现的步数一旦某个状态第二次出现就同时得到进入环的步数和环长from collections import defaultdict import random MASK 0xFFFF def rol(x, r): return ((x r) | (x (16 - r))) MASK def f(x): return (rol(x, 1) rol(x, 8)) ^ rol(x, 2) def round_fn(st): x (st 16) MASK y st MASK return ((y ^ f(x)) 16) | x def cycle_measure(x, y, max_step1 22): start (x 16) | y s start seen {} step 0 while s not in seen and step max_step: seen[s] step s round_fn(s) step 1 if step max_step: return None, None mu seen[s] lam step - seen[s] return mu, lam def sample(): stats defaultdict(int) for _ in range(2000): x random.getrandbits(16) y random.getrandbits(16) mu, lam cycle_measure(x, y) if mu is None: stats[over_budget] 1 elif lam 16: stats[tiny(16)] 1 elif lam 4096: stats[short] 1 elif lam 65536: stats[mid] 1 else: stats[long] 1 return dict(stats) print(sample()) for x in (0x0000, 0xFFFF): mu, lam cycle_measure(x, x) print(fx{x:04x} mu{mu} lam{lam})脚本里max_step是预算上限防止某些轨迹太长把进程挂住。seen记录“状态 - 第一次出现的步数”当某个状态第二次出现时当前步数减去第一次出现步数就是环长。由于 SIMON 轮函数是置换mu对绝大多数输入都应该是 0如果你看到大量非零mu说明你传入的映射不可逆那你要检查round_fn是不是少保留了一个字。最后两行针对的是两个已知退化状态(0,0)和(0xFFFF,0xFFFF)。这两个点在单轮函数下都是不动点也就是环长为 1。原因是f(0)0且f(0xFFFF)0全 0 和全 1 经过(x1) (x8)之后都被消掉了。随机映射里出现这种点的概率极低SIMON 里存在它们是结构使然不是实现 bug但做周期查找时如果采样正好抽到这类点会拉低“短环”的统计印象所以我会把它们单独打印出来观察。3.3 从环长分布到差分传播查找环长分布只能说明状态空间有没有坍缩但密码分析更关心的是差分怎么扩散。把“周期查找”的思路平移一下对一个单 bit 差分反复迭代看它经过多少轮才从 1 bit 涨成两个 32 bit 字都充满变化。这个“饱和轮数”其实就是一条差分路径的生命周期。下面的脚本对输入差分(0x0001, 0x0000)做了 16 轮追踪def diff_weight(hd): return bin(hd).count(1) x, y 0x0001, 0x0000 for r in range(1, 17): x, y y ^ f(x), x print(fround {r:02d} weight_x{diff_weight(x):2d} weight_y{diff_weight(y):2d})这个脚本输出的是一个二维重量序列第 1 轮 x 的权重通常很小因为f(1)只产生少量 bit之后的轮次里AND 项会让差分活跃 bit 数快速上涨。正常情况下一两条路径会在 5 到 8 轮内达到接近 32 的总重量。如果你找到某条路径在 10 轮之后仍然只有个位数重量那是一条高概率差分路径是后面做差分攻击的起点。做这个查找时要注意bin(hd).count(1)统计的是当前差分状态里 1 的个数不是活跃 S 盒数量SIMON 里真正的密码分析活跃度要看 AND 项的输出差分是否为零所以这个脚本只能拿来做工程自检不能替代正式的差分分析工具。4. 从原型到 MCUSIMON 实现的参数调优与常见坑4.1 轮数改动的边界为什么不能只跑 20 轮SIMON 32/64 的 32 轮是设计者给的一个相对保守的余量。网上能查到的差分分析、线性分析论文很多只攻到 20 轮左右但这不等于你可以把轮数减到 20 去换性能。原因是这类攻击的研究方法在持续进化而且 SIMON 的线性分支数只有 2比 AES 低得多安全余量的边际本来就薄。工程上我的原则是参数族和轮数严格按照算法定义来性能不够就换一个更小的参数族比如从 64/128 换到 32/64而不是削减轮数。你每次削减轮数都是在把密码安全变成“我觉得够用”。4.2 面向 Cortex-M 的优化移位、内联与常数时间SIMON 在 Cortex-M 上最容易做的优化是让编译器把循环移位翻译成立即数移位。M0/M0 没有桶形移位器但立即数移位仍然是单周期的所以ROL16(x, 1)这类运算比变量移位快得多。M3/M4 有桶形移位器情况更好。需要注意的坑是ROL16宏里的 15它把一个三元运算变成了两条指令加上最后的|一共三条。性能敏感时可以针对 1、2、3、8 这几个固定轮数各写一个内联函数避免宏展开后每次都做一次 15。常数时间实现是另一个必须考虑的维度。SIMON 没有查表操作从结构上就比 AES 更容易做到时间恒定。要注意的是别为了性能引入查表去实现 AND 或移位那会把常数时间性质毁掉。下面这段代码是 Cortex-M3/M4 上测量加密耗时的常用写法CoreDebug-DEMCR | CoreDebug_DEMCR_TRCENA_Msk; DWT-CYCCNT 0; DWT-CTRL | DWT_CTRL_CYCCNTENA_Msk; uint32_t t0 DWT-CYCCNT; simon32_64_encrypt(rk, pt, ct); uint32_t cycles DWT-CYCCNT - t0;这里TRCENA是 DWT 的总开关必须先置位否则CYCCNT不递增。DWT-CYCCNT在多数 Cortex-M3/M4 上是自由运行的计数器减出来的就是这段代码消耗的内核周期数。M0 没有 DWT我一般用 GPIO 翻转加逻辑分析仪来测或者直接按指令数估算。测出来的周期数要注明编译器优化等级-O0和-O2的结果可能差 5 倍以上。4.3 字节序、Z 常数位序与全零状态三个容易踩的坑坑现象对策Z 常数取位方向反了第 1 轮正确第 2 轮起密钥全错确认序列第 0 位对应常数的哪一位SIMON 32/64 用(Z0 (61 - i)) 1明文按 memcpy 转 uint16_t小端 MCU 上测试向量对不上手动拼 (buf[0] 8)用全 0 明文做自检密文恰好在某些密钥下表现出特殊规律用随机明文 公开测试向量双轨验证Z 常数的取位是这几个坑里最隐蔽的因为它的错误表现不是“完全跑不出结果”而是“第一轮对后面全错”。两个常见的可取错位是62 - i和63 - i。62 - i错在把序列第 0 位对到了第 62 位而 Z0 打包后最高有效位在第 61 位63 - i错在把两个补零位也算进去了。处理方式只有一种先把自己要用的 Z 序列完整展开成二进制串逐个 bit 对一遍别凭记忆写偏移。大端组装那段代码要写在最高一层也就是明文从字节流读进来时x (uint16_t)(buf[0] 8) | buf[1]。很多 MCU 默认小端直接memcpy会把字面顺序搞反明文和密文看着都对不上任何公开向量。全零状态的坑我在第 3 章提过这里再强调一下它不影响算法安全性但影响你调试验证的效率不要在写自检时把全零明文当成“最基础的那条用例”。5. 用测试向量和差分基线把 SIMON 实现锁死验证 SIMON 实现最可靠的方法是双轨制一轨是公开测试向量确认密钥扩展和加密主循环的位序完全正确另一轨是差分基线确认对实现的任何后续修改没有悄悄改变轮函数行为。第一轨只需要一个简单的 selftest 函数int simon32_64_selftest(void) { const uint16_t key[4] {0x0100, 0x0908, 0x1110, 0x1918}; const uint16_t pt[2] {0x6565, 0x6877}; uint16_t rk[32], ct[2]; simon32_64_keyexp(key, rk); simon32_64_encrypt(rk, pt, ct); if (ct[0] ! 0xc69b || ct[1] ! 0xe9bb) return -1; return 0; }测试向量只能证明你的代码“在一个输入上是对的”不能证明你改过一轮指令之后还是对的。所以我会同时维护一个差分基线对全部 65536 个单 bit 输入差分做 16 轮迭代统计每条路径在第几轮总差分重量达到某个阈值把分布结果固化成一个签名文件。以后任何代码改动都先跑一遍这个脚本签名和基线不一致就说明轮函数被改动了。这个技巧在从 PC 原型往 MCU 移植时尤其有用——你要移植的往往是一大段改动后的优化代码测试向量太稀疏而差分基线会把任何位序、循环、常量上的手滑直接暴露出来。把差分基线脚本挂进提交前检查里配合上面的 selftestSIMON 实现就能一直保持“换平台不改语义”的状态。之后再做性能优化时你只需要盯着周期数和基线两个数不用再担心优化过程里把算法改坏。本文还有配套的精品资源点击获取 SIMON轻量级分组密码：C语言实现、周期查找与嵌入式移植
简介Simon算法的C实现程序面向密码学初学者和对轻量级对称加密感兴趣的开发者以简洁代码演示了NSA提出的Simon分组密码核心流程。资源共1个文件为单个.cpp源文件压缩包整体仅1KB轻量易读适合快速查看算法骨架。目前已有604人浏览/学习。程序通过Simon类封装初始化、密钥扩展、加密与解密方法完整覆盖轮函数中的异或、循环移位、按位与非操作并针对常用变种说明不同块大小与密钥长度的处理方式可结合Simon32/64、Simon48/72等参数理解密钥扩展与加解密迭代逻辑。需要说明的是此实现侧重教学参考可能存在边界条件或性能优化空间阅读者可借此练习代码审查、单测编写与算法比对进而自行完善为可用的嵌入式或实验版本。1. 先分清是哪个 Simon这个标题背后是一族轻量级分组密码GitHub 上以 Simon 命名的仓库一半是四色记忆小游戏另一半是我下面要讲的轻量级分组密码 SIMON。区分它们只需要看标题里的伴随词出现 algorithm、cipher、blockcipher 的基本都是在做加解密实现而像“simon周期查找”这类搜索词往往是从实现往密码分析方向走的信号。SIMON 的价值主要体现在资源受限场景块小、密钥扩展简单、轮函数只有移位和与运算在 Cortex-M 这类平台上代码体积和栈占用都能压得很低。这篇文章会用 C 把 SIMON 32/64 完整实现一遍然后以轮函数迭代为主做周期查找验证状态扩散行为最后落到嵌入式移植时容易踩的坑和回归验证方法。适合正在做 IoT 安全选型、想读懂开源 SIMON 源码或者需要自己维护一个轻量对称加密实现的人。2. SIMON 轮函数与密钥调度用 C 落地 32/64 的完整实现2.1 SIMON 参数族先决定块长、密钥长和轮数SIMON 的命名规则是“SIMON 2n/nk”前面的数字是分组长度bit后面是密钥长度bit。分组长度始终是字长 n 的两倍密钥长度由密钥字个数 m 决定。下面是几个常见变体也是我日常用得最多的几档算法块长 bit字长 n密钥 bit密钥字 m轮数 TSIMON 32/64321664432SIMON 48/72482472336SIMON 64/96643296342SIMON 64/1286432128444SIMON 128/12812864128268SIMON 128/25612864256472本文拿 SIMON 32/64 做例子原因有三个字长 16 位所有中间值都能用uint16_t装下调试时一眼能看懂测试向量网上随处可查轮数只有 32 轮单轮函数在 PC 上做周期查找和差分传播实验都很快。换到其他参数族时只需要把数据类型从uint16_t换成相应宽度并把轮常数和 Z 序列换成对应值结构完全不变。2.2 轮函数里那三次循环移位在做什么SIMON 的轮函数是所有分组密码里最朴素的造型之一。对两个字(x, y)一轮做的事是new_x y ^ ((x 1) (x 8)) ^ (x 2) ^ rk new_y x这里的是循环左移。主心骨是((x 1) (x 8))按位与提供一个非线性项两个移位一个取邻近 bit一个取相隔较远的 bit让输入的某一位在输出里扩散到不同位置。外面的(x 2)再把结果往另一个方向搬一次。理解这个结构有个关键点SIMON 没有 S 盒全部非线性来自一个 AND所以它不怕 FPGA 没有 LUT也不怕 MCU 没有乘加指令。代价是单轮扩散弱必须靠足够多轮数把雪崩效应堆起来。这也是为什么 SIMON 32/64 要 32 轮而同样 32 bit 块的分组密码通常只要 16 轮左右。2.3 密钥调度与 Z 常数线性部分的“调味料”SIMON 的密钥扩展是纯线性运算加轮常数。对 m4 的情况前 4 个轮密钥直接取自主密钥之后的扩展公式是rk[i] rk[i-4] ^ ror(rk[i-1], 3) ^ ror(rk[i-3], 1) ^ c ^ (z_j)_i其中c 0xFFFC也就是2^16 - 4n32 时是0xFFFFFFFC规律是按字长变化。Z 序列是论文里给定的一组固定比特串作用是让每一轮都有一点“不一样的味道”破坏轮与轮之间的对称性否则密钥全零或明文全零时整个加密过程会表现出很强的周期性滑动攻击会变得非常容易。下面这段是我在 PC 上验证用的完整实现密钥扩展和加密写在一起可以直接编译运行#include stdint.h #include stdio.h #define ROL16(x, r) (((x) (r)) | ((x) ((16 - (r)) 15))) #define ROR16(x, r) (((x) (r)) | ((x) ((16 - (r)) 15))) /* Z_0 序列共 62 bit打包成 uint64_t 后最高有效位对应序列第 0 位 */ static const uint64_t Z0 0x3E895873D7D12B0E6ULL; static void simon32_64_keyexp(const uint16_t key[4], uint16_t rk[32]) { int i; for (i 0; i 4; i) rk[i] key[i]; for (i 4; i 32; i) { uint16_t t ROR16(rk[i - 1], 3) ^ ROR16(rk[i - 3], 1); rk[i] rk[i - 4] ^ t ^ 0xFFFC ^ ((uint16_t)((Z0 (61 - (i - 4))) 1)); } } static void simon32_64_encrypt(const uint16_t rk[32], const uint16_t pt[2], uint16_t ct[2]) { uint16_t x pt[0], y pt[1]; int i; for (i 0; i 32; i) { uint16_t old_x x; x y ^ ((ROL16(x, 1) ROL16(x, 8)) ^ ROL16(x, 2)) ^ rk[i]; y old_x; } ct[0] x; ct[1] y; } int main(void) { const uint16_t key[4] {0x0100, 0x0908, 0x1110, 0x1918}; const uint16_t pt[2] {0x6565, 0x6877}; uint16_t rk[32], ct[2]; simon32_64_keyexp(key, rk); simon32_64_encrypt(rk, pt, ct); printf(ct %04x %04x\n, ct[0], ct[1]); return (ct[0] 0xc69b ct[1] 0xe9bb) ? 0 : 1; }这段代码有两个地方需要特别说明。第一是ROL16宏里的 15当 r 为 0 时16 - r等于 16而在 C 里对 16 位整数移位 16 位是未定义行为 15把移位数折回 0。第二是 Z 常数的取位方式Z0是一个 62 bit 序列打包装进 64 位整数后最高两位是 0所以序列第 i 位要右移61 - i提取而不是63 - i。最常见的手滑就是把这两个数写反结果第一轮正确、第二轮开始密钥全是乱的。加密主循环里先保存old_x再更新x因为轮函数里新的右半字是上一轮的左半字这个赋值顺序一旦写反整个密文就不对了。2.4 用公开测试向量做自检上面代码的 main 函数里已经放了一组公开测试向量密钥1918 1110 0908 0100明文6565 6877密文应为c69b e9bb。这里的密钥在内存里的排列是key[0] 0x0100也就是说第一个参与轮函数的是最低位字。如果编译运行后输出一致说明密钥扩展和加密主循环的位序、字节序都对了不一致时先查 Z0 的取位再查ror(rk[i-1], 3)和ror(rk[i-3], 1)的下标是不是写反了。3. SIMON 周期查找用迭代和差分找轮函数的退化点3.1 为什么要对轮函数做周期查找轮函数本质上是一个定义在有限状态集合上的映射。任意给定一个初始状态反复迭代这个映射最终一定会进入一个环前面可能有若干步“尾巴”之后就是不断重复的循环。周期查找就是去量这个尾巴长度和环长。密码学里关心环长的原因很直接如果大量状态能在很短步数内落入同一个短环说明这个映射的状态空间在坍缩输出的随机性比理论值差代数攻击和区分攻击就有了可乘之机。对 SIMON 来说有个更具体的背景它的非线性只来自一个 AND单论代数复杂度肯定不如 AES 的 S 盒。设计者把安全性押在“轮数足够多”上所以周期查找能给一个直观感受——迭代多少轮之后状态不再“看起来像随机”。我在做这类检查时习惯先去掉轮密钥把轮函数当成一个无密钥的映射(x, y) - (y ^ f(x), x)来分析。原因是轮密钥只是对其中一个字做异或相当于对整个状态空间做一个平移单点轨迹的环长分布不会改变太多但计算量小一个量级。这个映射其实是个置换因为给定(x, y)可以唯一还原(x, y) (y, x ^ f(y))。置换的轨迹没有尾巴每一点都在环上。所以对 SIMON 轮函数做周期查找找到的mu应该恒为 0而环长lam的分布可以跟随机置换的理论值对照。3.2 状态迭代的周期查找脚本下面的 Python 脚本把状态打包成一个 32 位整数用字典记录每个状态首次出现的步数一旦某个状态第二次出现就同时得到进入环的步数和环长from collections import defaultdict import random MASK 0xFFFF def rol(x, r): return ((x r) | (x (16 - r))) MASK def f(x): return (rol(x, 1) rol(x, 8)) ^ rol(x, 2) def round_fn(st): x (st 16) MASK y st MASK return ((y ^ f(x)) 16) | x def cycle_measure(x, y, max_step1 22): start (x 16) | y s start seen {} step 0 while s not in seen and step max_step: seen[s] step s round_fn(s) step 1 if step max_step: return None, None mu seen[s] lam step - seen[s] return mu, lam def sample(): stats defaultdict(int) for _ in range(2000): x random.getrandbits(16) y random.getrandbits(16) mu, lam cycle_measure(x, y) if mu is None: stats[over_budget] 1 elif lam 16: stats[tiny(16)] 1 elif lam 4096: stats[short] 1 elif lam 65536: stats[mid] 1 else: stats[long] 1 return dict(stats) print(sample()) for x in (0x0000, 0xFFFF): mu, lam cycle_measure(x, x) print(fx{x:04x} mu{mu} lam{lam})脚本里max_step是预算上限防止某些轨迹太长把进程挂住。seen记录“状态 - 第一次出现的步数”当某个状态第二次出现时当前步数减去第一次出现步数就是环长。由于 SIMON 轮函数是置换mu对绝大多数输入都应该是 0如果你看到大量非零mu说明你传入的映射不可逆那你要检查round_fn是不是少保留了一个字。最后两行针对的是两个已知退化状态(0,0)和(0xFFFF,0xFFFF)。这两个点在单轮函数下都是不动点也就是环长为 1。原因是f(0)0且f(0xFFFF)0全 0 和全 1 经过(x1) (x8)之后都被消掉了。随机映射里出现这种点的概率极低SIMON 里存在它们是结构使然不是实现 bug但做周期查找时如果采样正好抽到这类点会拉低“短环”的统计印象所以我会把它们单独打印出来观察。3.3 从环长分布到差分传播查找环长分布只能说明状态空间有没有坍缩但密码分析更关心的是差分怎么扩散。把“周期查找”的思路平移一下对一个单 bit 差分反复迭代看它经过多少轮才从 1 bit 涨成两个 32 bit 字都充满变化。这个“饱和轮数”其实就是一条差分路径的生命周期。下面的脚本对输入差分(0x0001, 0x0000)做了 16 轮追踪def diff_weight(hd): return bin(hd).count(1) x, y 0x0001, 0x0000 for r in range(1, 17): x, y y ^ f(x), x print(fround {r:02d} weight_x{diff_weight(x):2d} weight_y{diff_weight(y):2d})这个脚本输出的是一个二维重量序列第 1 轮 x 的权重通常很小因为f(1)只产生少量 bit之后的轮次里AND 项会让差分活跃 bit 数快速上涨。正常情况下一两条路径会在 5 到 8 轮内达到接近 32 的总重量。如果你找到某条路径在 10 轮之后仍然只有个位数重量那是一条高概率差分路径是后面做差分攻击的起点。做这个查找时要注意bin(hd).count(1)统计的是当前差分状态里 1 的个数不是活跃 S 盒数量SIMON 里真正的密码分析活跃度要看 AND 项的输出差分是否为零所以这个脚本只能拿来做工程自检不能替代正式的差分分析工具。4. 从原型到 MCUSIMON 实现的参数调优与常见坑4.1 轮数改动的边界为什么不能只跑 20 轮SIMON 32/64 的 32 轮是设计者给的一个相对保守的余量。网上能查到的差分分析、线性分析论文很多只攻到 20 轮左右但这不等于你可以把轮数减到 20 去换性能。原因是这类攻击的研究方法在持续进化而且 SIMON 的线性分支数只有 2比 AES 低得多安全余量的边际本来就薄。工程上我的原则是参数族和轮数严格按照算法定义来性能不够就换一个更小的参数族比如从 64/128 换到 32/64而不是削减轮数。你每次削减轮数都是在把密码安全变成“我觉得够用”。4.2 面向 Cortex-M 的优化移位、内联与常数时间SIMON 在 Cortex-M 上最容易做的优化是让编译器把循环移位翻译成立即数移位。M0/M0 没有桶形移位器但立即数移位仍然是单周期的所以ROL16(x, 1)这类运算比变量移位快得多。M3/M4 有桶形移位器情况更好。需要注意的坑是ROL16宏里的 15它把一个三元运算变成了两条指令加上最后的|一共三条。性能敏感时可以针对 1、2、3、8 这几个固定轮数各写一个内联函数避免宏展开后每次都做一次 15。常数时间实现是另一个必须考虑的维度。SIMON 没有查表操作从结构上就比 AES 更容易做到时间恒定。要注意的是别为了性能引入查表去实现 AND 或移位那会把常数时间性质毁掉。下面这段代码是 Cortex-M3/M4 上测量加密耗时的常用写法CoreDebug-DEMCR | CoreDebug_DEMCR_TRCENA_Msk; DWT-CYCCNT 0; DWT-CTRL | DWT_CTRL_CYCCNTENA_Msk; uint32_t t0 DWT-CYCCNT; simon32_64_encrypt(rk, pt, ct); uint32_t cycles DWT-CYCCNT - t0;这里TRCENA是 DWT 的总开关必须先置位否则CYCCNT不递增。DWT-CYCCNT在多数 Cortex-M3/M4 上是自由运行的计数器减出来的就是这段代码消耗的内核周期数。M0 没有 DWT我一般用 GPIO 翻转加逻辑分析仪来测或者直接按指令数估算。测出来的周期数要注明编译器优化等级-O0和-O2的结果可能差 5 倍以上。4.3 字节序、Z 常数位序与全零状态三个容易踩的坑坑现象对策Z 常数取位方向反了第 1 轮正确第 2 轮起密钥全错确认序列第 0 位对应常数的哪一位SIMON 32/64 用(Z0 (61 - i)) 1明文按 memcpy 转 uint16_t小端 MCU 上测试向量对不上手动拼 (buf[0] 8)用全 0 明文做自检密文恰好在某些密钥下表现出特殊规律用随机明文 公开测试向量双轨验证Z 常数的取位是这几个坑里最隐蔽的因为它的错误表现不是“完全跑不出结果”而是“第一轮对后面全错”。两个常见的可取错位是62 - i和63 - i。62 - i错在把序列第 0 位对到了第 62 位而 Z0 打包后最高有效位在第 61 位63 - i错在把两个补零位也算进去了。处理方式只有一种先把自己要用的 Z 序列完整展开成二进制串逐个 bit 对一遍别凭记忆写偏移。大端组装那段代码要写在最高一层也就是明文从字节流读进来时x (uint16_t)(buf[0] 8) | buf[1]。很多 MCU 默认小端直接memcpy会把字面顺序搞反明文和密文看着都对不上任何公开向量。全零状态的坑我在第 3 章提过这里再强调一下它不影响算法安全性但影响你调试验证的效率不要在写自检时把全零明文当成“最基础的那条用例”。5. 用测试向量和差分基线把 SIMON 实现锁死验证 SIMON 实现最可靠的方法是双轨制一轨是公开测试向量确认密钥扩展和加密主循环的位序完全正确另一轨是差分基线确认对实现的任何后续修改没有悄悄改变轮函数行为。第一轨只需要一个简单的 selftest 函数int simon32_64_selftest(void) { const uint16_t key[4] {0x0100, 0x0908, 0x1110, 0x1918}; const uint16_t pt[2] {0x6565, 0x6877}; uint16_t rk[32], ct[2]; simon32_64_keyexp(key, rk); simon32_64_encrypt(rk, pt, ct); if (ct[0] ! 0xc69b || ct[1] ! 0xe9bb) return -1; return 0; }测试向量只能证明你的代码“在一个输入上是对的”不能证明你改过一轮指令之后还是对的。所以我会同时维护一个差分基线对全部 65536 个单 bit 输入差分做 16 轮迭代统计每条路径在第几轮总差分重量达到某个阈值把分布结果固化成一个签名文件。以后任何代码改动都先跑一遍这个脚本签名和基线不一致就说明轮函数被改动了。这个技巧在从 PC 原型往 MCU 移植时尤其有用——你要移植的往往是一大段改动后的优化代码测试向量太稀疏而差分基线会把任何位序、循环、常量上的手滑直接暴露出来。把差分基线脚本挂进提交前检查里配合上面的 selftestSIMON 实现就能一直保持“换平台不改语义”的状态。之后再做性能优化时你只需要盯着周期数和基线两个数不用再担心优化过程里把算法改坏。本文还有配套的精品资源点击获取