第四十二个知识点：看看你的C代码为蒙哥马利乘法，你能确定它可能在哪里泄漏侧信道路吗?

几个月前(回到3月份)，您可能还记得我在这个系列的52件东西中发布了第23件(可以在这里找到)。这篇文章的标题是“编写一个C程序来实现蒙哥马利算法”，并包含了实现的一部分。在本文中，我们将研究这个实现，并了解它如何泄漏信息，从而对泄漏的情况有一个实际的了解。

在继续之前，我想提醒你一下我的上一篇文章，它研究了SPA和DPA攻击的区别。从那里你会记得,SPA攻击使用一个或很少的痕迹的发现趋势和工作模式(如时间或指令序列)而DPA攻击使用很多的痕迹,旨在推导算法的中间值,因此秘密信息通过使用机密数据和正确的泄漏模型的假设。之前看蒙哥马利乘法算法从一开始就那么值得说明的是,如果假设的秘密数据和相应的泄漏模型可以推导出算法,DPA攻击方式可以用来得到中间值将意味着该算法将泄漏被处理的数据。因此，如果这些数据是秘密的，那么我们已经可以说，通过使用DPA风格的攻击，这个算法将会泄漏。

然而，正如我在上一篇文章中提到的，我们知道DPA风格的攻击比SPA要难得多，因为它们需要形成秘密数据假设的能力，更多的痕迹和它们的成功将在很大程度上取决于设备产生的噪音。接下来的问题是，我们的实现将如何被利用正在执行的指令的时间或顺序等内容，实现SPA泄露攻击。为了理解这件事，我将算法分成了四个阶段，我们感兴趣的是条件语句或循环之类的东西，因为它们可能被用于时间侧信道攻击。

1.GCD操作

这里我们进行了一个GCD操作，为了计算\(r^{-1}\)和\(m\)满足\(rr^{-1} = 1 + mm^{'}\)。如果我们假设因此，如果我们假设扩展gcd操作的算法在恒定时间内运行，那么我们可以假设该操作是安全的。

2.将乘数转换到蒙哥马利空间

这个阶段计算\(abar = ar \mod m\)和\(bbar = br \mod m\)，因此这是一个简单操作，常数运行时间不会泄露信息。

3.进行蒙哥马利乘法运算

条件语句会泄露侧信道信息！

首先指令if (ulo<tlo) uhi=uhi+1会让我们在特定平台进行实现的时候，通过观察执行时间或功率跟踪，可以了解是否执行了这个条件，以及这些ulo是否高于tlo。

另外指令if (ov>0||ulo>=m) ulo=ulo-m，这回暴露条件是否达到，然后泄露内部值的信息。

4.取逆操作

这里我们计算了\(ur^{-1} \mod m\) ,实际上就是\(ab \mod m\)。就像阶段1和2没有泄漏一样，我们也可以说这个阶段不会泄漏。