侧信道攻击在密码学中的应用：基于时间分析的素数检测攻击

1. 侧信道攻击概述

侧信道攻击(Side-Channel Attack, SCA)是一种不直接攻击密码算法本身的数学结构，而是通过分析加密设备在执行加密运算时泄露出的物理信息(如时间、功耗、电磁辐射等)来推测密钥的攻击方式。

本文重点讨论时间侧信道攻击，即通过分析算法执行时间差异来获取敏感信息的攻击方法。

2. SageMath中is_prime()函数的时间分析

2.1 函数实现分析

在SageMath中，is_prime()函数的实现逻辑如下：

1. 首先调用mpz_fits_ulong_p()判断数字是否可以安全转换为无符号长整型(unsigned long)
   • 对于小于2^64的数字：
     • 先判断奇偶性
     • 对于小于1000的奇数：使用预存的素数列表快速判断
     • 对于大于1000的数字：调用pari_is_prime()函数
   • 对于大于2^64的数字：
     • 默认情况下会调用proof.arithmetic()进行更严格的素性证明

2.2 时间差异来源

关键时间差异点：

• 小于1000的数字判断速度明显快于大于1000的数字
• 在pari_is_prime()内部实现中：
  • 首先检查是否有小于103的小素因子
  • 如果没有，则进行更耗时的复合素性证明

3. 实际攻击案例：JQCTF2025 OnelineCrypto

3.1 题目场景

题目允许用户输入一个数字input_num，系统会计算flag ^ input_num并判断其是否为素数。攻击者可以通过控制input_num来构造特定的数值。

3.2 攻击原理

1. 利用is_prime()函数对有小素因子(<103)的数字响应更快的特点
2. 通过精心构造input_num使得flag ^ input_num覆盖小素数的完全剩余系
3. 观察到快速响应的输入意味着(flag ^ input_num) % p == 0对于某个小素数p
4. 由于题目中input_num只取了高于flag的位，因此实际上：

   flag ^ input_num = flag + input_num
   

5. 因此可以得到关系式：

   flag ≡ -input_num mod p
   

3.3 攻击步骤

1. 对于每个小素数p (<103且p≠2):

   • 构造多个input_num使得(flag + input_num)覆盖p的所有可能余数
   • 通过时间测量找出响应时间短的输入
   • 确定满足(flag + input_num) % p == 0的input_num
   • 计算flag ≡ -input_num mod p

2. 对多个小素数重复上述过程，得到一组同余方程

3. 使用中国剩余定理(CRT)组合这些同余方程，缩小flag的可能范围

4. 对剩余的可能值进行爆破，找出正确的flag

3.4 注意事项

• 有时没有小素因子的数字也会快速返回结果(假阳性)
• 需要通过统计方法(多次测试同一余数类)来排除假阳性
• 正确的余数类(即(flag+input_num)%p==0)通常会没有长时间响应

4. 防御措施

针对此类时间侧信道攻击的防御方法：

1. 恒定时间算法：确保所有执行路径耗时相同
2. 随机延迟：在算法中添加随机时间延迟
3. 避免分支：减少基于敏感数据的条件分支
4. 屏蔽技术：使用数学方法屏蔽中间值
5. 算法选择：使用对侧信道攻击不敏感的算法

5. 扩展思考

这种攻击方法可以推广到其他存在时间差异的密码学操作：

• RSA解密操作
• 椭圆曲线点乘法
• 哈希算法的比较操作
• 缓存访问模式分析

理解这些侧信道攻击的原理对于设计安全的密码系统至关重要。