最近，我注意到人们在Arduino上自行实现加密算法，例如Stackoverflow中的这个主题：
https://stackoverflow.com/questions/39189065/rsa-encryption-decryption-functions-for-arduino
互联网上可以找到多个此类实现，其中一些甚至来自知名库。
我决定做这个小型的PoC（概念验证），以展示为什么不仅不应发明自己的加密算法，而且还要使用这些算法的稳健实现同样重要。
本PoC针对RSA实现中使用的辅助例程（快速幂）的不良实现，执行了一次侧信道攻击（功耗分析攻击）。
侧信道攻击是一种通过利用间接信息泄漏而非直接攻击加密算法或协议本身来破坏加密系统的方法。
这种泄漏可能源自多种来源，例如时序信息、功耗、电磁辐射甚至声音。
此类攻击在破解RSA等加密系统时非常有效，攻击者无需解决确保加密方案安全性的底层数学问题（Kocher, Jaffe, & Jun, 1999）。
本文将针对Arduino（Atmega328P）固件中RSA算法实现的一个已知漏洞，执行功耗分析攻击。
注：本工作仓促完成，若存在拼写或语法错误，敬请谅解。
功耗分析攻击通过测量设备在加密操作期间的功耗来进行。
差分功耗分析（DPA）涉及对多次加密操作的功耗模式进行统计分析以提取秘密，这比简单功耗分析（SPA）更为复杂。简单功耗分析则直接将功耗波动与特定加密操作相关联以推断秘密。
差分功耗分析（DPA）和简单功耗分析（SPA）可通过分析RSA计算过程中的功耗模式来提取私钥。
这些攻击能够通过识别与不同密钥位相关的独特功耗模式来揭示私钥（Kocher, Jaffe, & Jun, 1999）。
RSA（Rivest-Shamir-Adleman）是一种广泛使用的公钥加密算法，以其发明者Ron Rivest、Adi Shamir和Leonard Adleman命名，他们于1977年提出该算法（Paar & Pelzl, 2010）。
它至今仍是互联网上安全传输数据的最可靠方法之一。
RSA安全性的基础之一在于将大合数分解为其质因数的难度（Menezes, van Oorschot, & Vanstone, 1996）。
这个问题被称为因数分解问题，涉及找到相乘得到给定大数的质数。
RSA加密依赖于一个假设：因数分解问题在计算上足够困难，使得通过分解模数得到其质因数来破解加密是不现实的（Menezes, van Oorschot, & Vanstone, 1996）。
图1 通过一个简单示例说明了RSA加密和解密过程。
图1 - RSA示例。
请注意，在此示例中，3和33是公开的。数字7为私钥。
Phi(N) 函数，即欧拉函数，计算从1到33区间内所有与33互质的数的个数。
值33由P和Q相乘得到，此处为11乘以3。
Phi函数的结果通过将(P-1)乘以(Q-1)得到，此处为10乘以2。
操作e<sup>-1</sup> mod 20表示模逆运算（Menezes, van Oorschot, & Vanstone, 1996）。
注： 若希望深入了解RSA（并非理解本文所必需），本仓库中的文件number_theory.md提供了这些基础数论运算的快速介绍。该说明有助于增强对RSA运算的理解。
实验使用了Rigol公司生产的DS1102示波器（如图2所示）。
示波器手册可在参考文献中找到（RIGOL Technologies, Inc., 2017）。
同时使用了通用电源（如图3所示）。
图2 - 实验中使用的示波器。
图3 - 实验中使用的电源。
欧姆定律是电气工程和物理学领域的基本原理。
它指出，流过导体两点之间的电流与这两点间的电压成正比，与它们之间的电阻成反比（Boylestad, 2015）。
图4 展示了一个电路及欧姆定律。
图4 - 欧姆定律示意图。
欧姆定律意味着，如果增加导体两端的电压，电流也会增加，前提是电阻保持不变（Johnson & Hilburn, 2013）。图5 展示了一个欧姆定律的应用实例，其目标是求出电路中的电流。
图5 - 欧姆定律示例。
基尔霍夫电压定律（KVL）是电气工程和物理学中的一个基本原理（Boylestad, 2015）。
它指出，围绕任何闭合回路或网络，所有电势差（电压）的代数和为零（Boylestad, 2015）。
图6 说明了基尔霍夫电压定律。
图6 - 基尔霍夫定律示意图。
图7 展示了一个基尔霍夫定律的应用实例，用于求出流过电阻R1和R2的电流。
图7 - 基尔霍夫定律示例。
分压器是基尔霍夫电压定律（KVL）的一个推论，它给出了计算Vout（即电阻R1和R2之间的电压）的方法。
分压器公式如图8所示。
图9 展示了一个分压器的应用示例。
图8 - 分压器示意图。
图9 - 分压器示例。
分流电阻是一个低阻值电阻，串联在电路的电源供电线上，用于测量流过电路的电流。
使用分流电阻测量电流是现代万用表采用的技术之一（Boylestad, 2015）。
通过测量分流电阻两端的压降，并已知其电阻值，即可利用欧姆定律计算电流。
要测量Arduino设备的电流消耗，需要将一个分流电阻串联在VCC（正极）上。
其连接方式如图10所示。
注1： 请注意，在本PoC中，并未使用Arduino Uno板作为目标，而是将微控制器（Atmega328P）转移到了单独的洞洞板上，如图11所示。这样可以更方便地操作微控制器的引脚，无需焊接。
注2： 若不清楚如何操作，我之前关于故障注入（glitching）的文章说明了操作方法，可在以下链接找到： https://github.com/lord-feistel/hardware_hacking_lab
图10 - 带Arduino的分流电阻。
图11 - 洞洞板上的分流电路。
为了演示使用分流电阻测量电流消耗，将一个LED（Sedra & Smith, 2014）连接到微控制器的GPIO（图12），并使用示波器观察LED点亮和熄灭两种情况下，分流电阻上的功耗变化。
注意：提取密钥或观察充放电效应对功耗的影响时，无需使用欧姆定律计算电流，仅测量电压降已足够（Johnson & Hilburn, 2013）。
图12 - 功耗测量。
为更清晰地观察，请查看视频1，该视频展示了LED点亮时的电压降。
视频1 - LED消耗引起的电压降。
下面的代码用于控制LED闪烁，也可在本仓库中找到。```C const int PIN_CHARGE = 9 ; void setup() { pinMode(PIN_CHARGE, OUTPUT);
}
void loop() {
digitalWrite(PIN_CHARGE, HIGH);
delay(10);
digitalWrite(PIN_CHARGE, LOW);
delay(10);
}
需要说明的是，这种压降在发生复杂计算时也会出现（Kocher, Jaffe, & Jun, 1999）。
以下代码导致了**图13**所示的压降。```C
void setup() {
}
void loop() {
volatile unsigned long i = 0;
i = ((i + 1) * (i - 1) + (i * i) - (i / 2) * (i % 3) + (i * i * i * i)) * ((i + 2) * (i - 2) + (i * i) - (i / 3) * (i % 5) + (i * i * i * i));
delayMicroseconds(100);
}
如果电压降反映了计算，那么它可以用来确定正在处理的数据。
图 13 - 重度计算中的功耗。
传统的幂运算方法是，将底数相乘 n 次。
假设 23 会得到 2*2*2，因为 2 是底数，3 是 n。
这种方法运行得很好，但效率不够高，无法使 RSA 可行。
为了实现这样的算法，使用了快速幂算法。
快速幂，也称为平方求幂，是一种将数字进行幂运算的高效方法。
下面可以找到快速幂的伪代码。```C
function fast_exponentiation(a, b): result = 1 base = a exponent = b
while exponent > 0:
if (exponent % 2 == 1): // If exponent is odd
result = result * base
base = base * base // Square the base
exponent = exponent // 2 // Divide exponent by 2
return result
快速幂运算 2<sup>4</sup> 的步骤可在 **表 1** 中找到。
| 迭代 | 底数值 | 二进制形式的指数 | 操作 | 结果 |
|-----------|--------------|----------------------------|-----------|---------------------------|
| 初始 | 2 | 100 | 开始 | 1 |
| 1 | 4 | 010 | 平方 | 1 |
| 2 | 16 | 001 | 平方 | 1 |
| 3 | 256 | 000 | 相乘 | 16 |
| 最终 | - | - | 结束 | 16 |
**表 1** - 2<sup>4</sup> 的快速幂运算迭代过程。
接下来解释该过程：```
- **Initialization:**
Start with base = 2 , exponent = 4 ( binary 100) , result = 1.
- **Iteration 1:** exponent = 4 (binary 100, even)
Square base to get 4 .
result remains 1.
- **Iteration 2:** exponent = 2 (binary 010, even)
Square base to get 16 .
result remains 1.
- **Iteration 3:** exponent = 1 (binary: 001, odd)
Multiply result by a = 16 to get 16.
result becomes 16.
- **Final:** n = 0 (binary: 000)
The loop ends with result = 16.
注意，对于较小的数字，效率没有变化甚至会更差，然而对于大数字，它在效率上取得了显著的提升。
与朴素方法相比，它减少了乘法运算的次数，这对于大指数尤其有用。
表2 展示了使用朴素幂运算和快速幂运算时，这样一个数字的迭代次数比较。
快速幂运算在RSA的加密和解密过程中至关重要，因为这些过程涉及将大数字提升到大指数次幂，然后对另一个大数字取模（Paar & Pelzl, 2010）。
如RSA示例部分所述，密钥就是指数，通常是一个非常大的数字。