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

1. 侧信道攻击概述<\/h2>
侧信道攻击(Side-Channel Attack, SCA)是一种不直接攻击密码算法本身的数学结构，而是通过分析加密设备在执行加密运算时泄露出的物理信息(如时间、功耗、电磁辐射等)来推测密钥的攻击方式。<\/p>
本文重点讨论时间侧信道攻击<\/strong>，即通过分析算法执行时间差异来获取敏感信息的攻击方法。<\/p>

2. SageMath中is_prime()<\/code>函数的时间分析<\/h2> 2.1 函数实现分析<\/h3> 在SageMath中，is_prime()<\/code>函数的实现逻辑如下：<\/p> 首先调用mpz_fits_ulong_p()<\/code>判断数字是否可以安全转换为无符号长整型(unsigned long) 对于小于2^64的数字：先判断奇偶性<\/li> 对于小于1000的奇数：使用预存的素数列表快速判断<\/li> 对于大于1000的数字：调用pari_is_prime()<\/code>函数<\/li> <\/ul> <\/li> 对于大于2^64的数字：默认情况下会调用proof.arithmetic()<\/code>进行更严格的素性证明<\/li> <\/ul> <\/li> <\/ul> <\/li> <\/ol> 2.2 时间差异来源<\/h3> 关键时间差异点：<\/p> 小于1000的数字判断速度明显快于大于1000的数字<\/li> 在pari_is_prime()<\/code>内部实现中：首先检查是否有小于103的小素因子<\/li> 如果没有，则进行更耗时的复合素性证明<\/li> <\/ul> <\/li> <\/ul> 3. 实际攻击案例：JQCTF2025 OnelineCrypto<\/h2> 3.1 题目场景<\/h3> 题目允许用户输入一个数字input_num<\/code>，系统会计算flag ^ input_num<\/code>并判断其是否为素数。攻击者可以通过控制input_num<\/code>来构造特定的数值。<\/p> 3.2 攻击原理<\/h3> 利用is_prime()<\/code>函数对有小素因子(<103)的数字响应更快的特点<\/li> 通过精心构造input_num<\/code>使得flag ^ input_num<\/code>覆盖小素数的完全剩余系<\/li> 观察到快速响应的输入意味着(flag ^ input_num) % p == 0<\/code>对于某个小素数p<\/li> 由于题目中input_num<\/code>只取了高于flag的位，因此实际上： flag ^ input_num = flag + input_num <\/code><\/pre> <\/li> 因此可以得到关系式： flag ≡ -input_num mod p <\/code><\/pre> <\/li> <\/ol> 3.3 攻击步骤<\/h3> 对于每个小素数p (<103且p≠2):<\/p> 构造多个input_num<\/code>使得(flag + input_num)<\/code>覆盖p的所有可能余数<\/li> 通过时间测量找出响应时间短的输入<\/li> 确定满足(flag + input_num) % p == 0<\/code>的input_num<\/code><\/li> 计算flag ≡ -input_num mod p<\/code><\/li> <\/ul> <\/li> 对多个小素数重复上述过程，得到一组同余方程<\/p> <\/li> 使用中国剩余定理(CRT)组合这些同余方程，缩小flag的可能范围<\/p> <\/li> 对剩余的可能值进行爆破，找出正确的flag<\/p> <\/li> <\/ol> 3.4 注意事项<\/h3> 有时没有小素因子的数字也会快速返回结果(假阳性)<\/li> 需要通过统计方法(多次测试同一余数类)来排除假阳性<\/li> 正确的余数类(即(flag+input_num)%p==0<\/code>)通常会没有<\/strong>长时间响应<\/li> <\/ul> 4. 防御措施<\/h2> 针对此类时间侧信道攻击的防御方法：<\/p> 恒定时间算法<\/strong>：确保所有执行路径耗时相同<\/li> 随机延迟<\/strong>：在算法中添加随机时间延迟<\/li> 避免分支<\/strong>：减少基于敏感数据的条件分支<\/li> 屏蔽技术<\/strong>：使用数学方法屏蔽中间值<\/li> 算法选择<\/strong>：使用对侧信道攻击不敏感的算法<\/li> <\/ol> 5. 扩展思考<\/h2> 这种攻击方法可以推广到其他存在时间差异的密码学操作：<\/p> RSA解密操作<\/li> 椭圆曲线点乘法<\/li> 哈希算法的比较操作<\/li> 缓存访问模式分析<\/li> <\/ul> 理解这些侧信道攻击的原理对于设计安全的密码系统至关重要。<\/p>