基于位运算的32位无符号整数比较函数原理解析

这段代码是无符号32位整数的常数时间小于比较实现，核心是通过位运算和减法，在无分支的情况下判断x < y，返回1或0，适合密码学场景避免侧信道攻击（比如通过执行时间差异泄露信息）。

代码回顾 #

int ct_lt_u32(uint32_t x, uint32_t y){
    return (x^((x^y)|((x-y)^y)))>>31;
}

分步拆解逻辑 #

我们从内到外逐步分析每个运算的作用：

1. x ^ y：标记x与y的差异位
   异或运算的特点是：二进制位上x和y取值不同时结果为1，相同时为0。这个结果能精准标记出x和y所有不一样的位。

2. x - y：利用无符号减法的溢出特性
   对于无符号32位整数：

   • 如果x < y，减法会产生溢出，结果是一个高位为1的大整数（本质是2^32 - (y - x)），最高位（第31位）为1；
   • 如果x >= y，减法结果正常，最高位为0。

3. (x - y) ^ y：结合减法结果与y的异或
   这一步将减法的溢出信息与y的二进制位结合，为后续的或运算提供需要的标记位。

4. (x^y) | ((x-y)^y)：合并有效标记位
   通过或运算，把x^y标记的差异位和(x-y)^y标记的溢出关联位合并，得到一个包含x和y大小关系关键信息的中间值。

5. x ^ 上述中间值：定位最高位标志
   将x与中间值异或后，只有当x < y时，最终结果的最高位会被置为1；其余情况（x >= y）最高位为0。

6. >>31：提取结果
   无符号整数的右移是逻辑右移，将结果右移31位后，最高位的1会变成1，0则保持0，最终返回1或0，正好对应x < y的判断结果。

本质总结 #

整个过程没有任何条件分支，所有运算都是固定时间完成的，完美避免了侧信道攻击的风险。核心是利用无符号减法的溢出特性，结合位运算精准提取出表示x < y的标志位。

内容的提问来源于stack exchange，提问作者Serenity