最近，我注意到人们在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示例部分所述，密钥就是指数，通常是一个非常大的数字。
表2 - 常规幂运算与快速幂运算效率对比
我们在Arduino上实现了一个快速幂运算，并上传到atmega328p。由于这是一个概念验证，我们以最直观的方式实现了它，以便观察。
例如，通常我们会使用移位操作处理整数变量，但为了便于理解，我们将指数实现为一个数组。
注意，代表密钥的指数是数组 {0, 1, 0, 1, 0, 1, 0, 1}，这会在示波器获取的测量结果中形成一个模式，作为其工作正常的证明。```C
#include <Arduino.h>
volatile long long dumb_vulnerableExponentiation(volatile long long base, const volatile int* exponentArray, volatile int arrayLength, volatile long long modulo) { volatile long long result = 1; base %= modulo;
for (volatile int i = 0; i < arrayLength; ++i) {
result = (result * result) % modulo;
if (exponentArray[i] == 1) {
result = (result * base) % modulo;
}
}
return result;
}
void setup() { }
void loop() { volatile long long base = 3; volatile long long modulo = 1000000007; const volatile int exponentArray[] = {0, 1, 0, 1, 0, 1, 0, 1}; volatile int arrayLength = sizeof(exponentArray) / sizeof(exponentArray[0]); delay(2); volatile long long result = dumb_vulnerableExponentiation(base, exponentArray, arrayLength, modulo); }
### Results
正如本文开头所述，加密和解密操作的关键是指数，因此一旦发现指数，RSA密钥就会暴露。
使用前面提到的硬件，可以在示波器中看到功耗频谱，如**图* 14* 和**图15**所示。
电压长时间下降的时段表示密钥的比特`1`正在被处理，否则是比特`0`。
请注意，当指数为偶数时，会多一次乘法，使得能耗下降时间更长，从而暴露密钥信息。
**视频2**展示了密钥的捕获。要了解如何调节周期和幅值，请参考示波器手册。
**图14** - 密钥捕获
**图15** - 使用示波器展示密钥的0和1
[](https://youtu.be/MBZ1abtTN_k)
**视频2** - 使用示波器捕获密钥
这种攻击可以应用于微控制器使用知名库但固件被锁定、攻击者无法直接从内存获取密钥的场景。
此类攻击也可用于针对硬件。
### 结论
实现自己的RSA（Rivest-Shamir-Adleman）加密系统是非常不推荐的，原因有几个关键点，特别是容易受到如功耗分析攻击等高级攻击的影响。
RSA加密虽然在正确实现时数学上很健壮，但在实现时需要极其注意细节以确保安全性。
即使是微小的实现缺陷或疏忽也可能无意中泄露私钥信息，从而危及整个系统的安全性。
此外，成熟的密码库和框架经过安全社区的严格审查和测试，确保它们能抵御已知攻击和漏洞。使用这些经过验证的库不仅节省时间和精力，还能显著降低无意中引入系统漏洞的风险。
### 参考文献
1. Understanding Cryptography - Paar, C., & Pelzl, J. (2010). **Understanding Cryptography**. Springer.
2. Handbook of Applied Cryptography - Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). **Handbook of Applied Cryptography**. CRC Press.
3. Differential Power Analysis - Kocher, P., Jaffe, J., & Jun, B. (1999). **Differential Power Analysis**. Proceedings of CRYPTO '99, Lecture Notes in Computer Science, vol 1666. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48405-1_25.
4. DS1102 Oscilloscope Datasheet - RIGOL Technologies, Inc. (2017). **DS1000E, DS1000D Series Digital Oscilloscope Datasheet**. Retrieved from [RIGOL Datasheet](https://beyondmeasure.rigoltech.com/acton/attachment/1579/f-03b8/1/-/-/-/-/DS1000E_DS1000D_DataSheet_EN.pdf)
5. Introductory Circuit Analysis - Boylestad, R. L. (2015). **Introductory Circuit Analysis** (13th ed.). Pearson.
6. Fundamentals of Electrical Circuits - Johnson, D., & Hilburn, J. L. (2013). **Fundamentals of Electrical Circuits**. McGraw-Hill Education.
7. Microelectronic Circuits - Sedra, A. S., & Smith, K. C. (2014). **Microelectronic Circuits** (7th ed.). Oxford University Press.
| 指数 (b) | 二进制 (b) | 常规幂运算次数 | 快速幂运算次数 |
|---|
| 1 | 1 | 1 | 1 |
| 2 | 10 | 1 | 1 |
| 4 | 100 | 3 | 2 |
| 8 | 1000 | 7 | 3 |
| 16 | 10000 | 15 | 4 |
| 32 | 100000 | 31 | 5 |
| 64 | 1000000 | 63 | 6 |
| 128 | 10000000 | 127 | 7 |
| 256 | 100000000 | 255 | 8 |
| 512 | 1000000000 | 511 | 9 |
| 1024 | 10000000000 | 1023 | 10 |