从部分信息中恢复加密密钥（通过一些例子）

从部分信息中恢复加密密钥（通过一些例子）（Recovering cryptographic keys from partial information, by example)

[TOC]

0 写在前面

0.1 综述

针对密码学的侧信道攻击可能仅泄露有关密钥的部分或间接信息。本篇文献中有多种技术可用于从部分信息中恢复密钥。在本文中，我们研究了RSA，(EC)DSA 和 (EC)Diffie-Hellman（当今常用的公钥密码系统）的几个主要部分密钥恢复算法家族。我们根据攻击者收集到的信息结构对已知的攻击方式进行分类，并为每种攻击方式提供简化示例以说明其背后思想。

0.2 译者想说的

这篇paper目前在国内还没有翻译文本，我自己在翻译之前大致看了一遍这篇paper，感觉和上次翻译的二十年内RSA攻击综述类型相同，都是一篇文章汇总了很多的攻击方式，其中一些攻击方式在最近的CTF比赛中也有出现过，所以就打算翻译这篇paper。当然由于本人能力有限，翻译水平不高，借鉴了一部分机翻，也会在原文的基础上写上一点点自己的看法什么的，各位师傅在阅读的时候如有疑惑或感觉不妥的地方，还请批评教正。原文链接：1506.pdf (iacr.org)

1 引入

You are dangling in a rope sling hung from the ceiling of a data center in an undisclosed location, high above the laser tripwires crisscrossing the floor. You hold an antenna over the target’s computer, watching the bits of their private key appear one by one on your smartwatch display. Suddenly you hear a scuffling at the door, the soft beep of keypad presses. You’d better get out of there! You pull your emergency release cable and retreat back to the safety of the ventilation 2 duct. Drat! You didn’t have time to get all the bits! Mr. Bond is going to be very disappointed in you. Whatever are you going to do?

（上面是一个很幽默的场景描述，写了一个特工去数据中心窃取私钥时的突发状况，这里翻译了就没内味儿了）

在侧信道攻击中，攻击者利用计算或存储的副作用来窃取表面上的秘密信息。许多侧信道攻击源于计算机是现实世界中的物理对象这一事实，因此计算可能需要不同的时间 [Koc96]，导致功耗变化 [KJJ99]，产生电磁辐射 [QS01]，或产生声音 [GST14]、光线 [FH08] 或温度 [HS14] 波动。泄露信息的具体特征取决于算法的顶层和底层的实现细节，通常还取决于计算机硬件本身：分支条件、错误条件、内存缓存收回行为或电容器放电的具体情况。

已发表文献中关于侧信道攻击的第一项工作并未直接针对密码学 [EL85]，但自从 Kocher 在 90 年代开展时序和功率分析方面的工作 [Koc96, KJJ99] 以来，密码学已成为侧信道工作的热门对象。然而，攻击者很少能通过侧信道简单地读取完整的密码密钥。许多侧信道攻击所揭示的信息通常是间接的或不完整的，甚至可能包含错误。

因此，为了充分了解给定漏洞的性质，侧信道分析师通常需要使用额外的密码分析技术。在这种情况下，密码分析者的主要目标通常是：“我获得了以下类型的关于密钥的不完整信息，它能不能让我可以高效地恢复剩下的密钥？” 不幸的是，没有一个万能的答案：它取决于所使用的特定算法，以及已得到信息的性质。

这项工作的目标是在一个地方收集该领域中一些最有用的技术，并为实践中最常见的场景提供一个合理全面的分类。也就是说，这是一个非详尽的研究和一个带有引导性例子的具体教程。该领域的许多算法论文都给出了完全通用的结构，这有时会模糊读者对方法为何有效的直觉。在这里，我们的目标是提供最少的工作示例来说明每种算法用于简单但不平凡的情况。我们将重点放在公钥密码学上，特别是目前广泛使用的算法（因此也是最流行的攻击目标）：RSA，(EC)DSA 和 (EC)Diffie-Hellman。

在整篇文章中，我们将用如下方式表示已知信息：

本次研究的分类情况见表1。

Table 1: 公钥加密系统密钥恢复方法的可视化目录

2 动机

虽然本教程主要是在更高的数学抽象层次上操作，而不是我们预想的侧通道攻击，但我们将给出一些示例来说明攻击者如何得到有关密钥的剩余部分信息。

模幂运算。我们讨论的所有公钥密码算法都涉及对值进行模幂运算或者椭圆曲线标量加法运算。对于RSA签名，受害者需要计算 $s\equiv{m^d\pmod{N}}$ ，其中 $d$ 是私钥指数。对于DSA签名受害者需要计算每个签名的密钥 $k$ ，并计算 $r\equiv{g^k\pmod{p}}$ ，其中 $g,p$ 是公钥对。对于DH密钥交换，受害者生成一个密钥指数 $a$ ，并计算公钥交换值 $A\equiv{g^a\pmod{p}}$ ，其中 $g,p$ 是公钥对。

朴素的模幂运算算法，如平方和乘法，对指数的位进行逐位运算：每次迭代将执行一次平方运算，如果指数的该位为 1，则将执行一次乘法运算。更复杂的模幂运算算法使用非相邻形式(non-adjacent form) (NAF)、窗口非相邻形式(windowed non-adjacent form) (wNAF) [Möl03]、滑动窗口(sliding windows)或Booth recoding [Boo51]进行预先计算，然后对预计算的数字表示进行操作。 [Gor98]。

对模幂的缓存攻击。缓存定时攻击是学术文献 [Pag02, TTMH02, TSS 03, Per05, Ber05, OST06] 中最常被利用的侧信道攻击家族之一。这些攻击有许多变体，但它们都有一个共同点，即攻击者能够在与受害进程位于同一位置并共享 CPU 缓存上的执行代码。当受害者代码执行时，攻击者测量从缓存中的地址加载信息所需的时间，从而推断出受害进程在执行期间，加载到这些缓存地址的数据的信息。在上面讨论的模幂运算或标量加法算法的语境下，如果攻击者可以检测到执行乘法指令的代码是否已加载到其中，那么对易受攻击的实现发起缓存攻击，就可能会反应乘法运算是否在特定比特位置执行缓存。或者，对于一个数的预计算数字表示，攻击者可能用缓存攻击来观察被访问的数字值 [ASK07, AS08, BvSY14]。

对模幂的其他攻击。现在还有一些其他侧信道攻击家族已经用于分析易受攻击的模幂实现，其中就包括功率分析和差分功率分析攻击 [KJJ99, KJJR11]、电磁辐射 [QS01]、声发射 [GST14]、原始时序 [Koc96]、光子发射 [ FH08] 和温度 [HS14]。这些攻击同样利用代码或电路，其执行因密钥而异。

冷启动和内存攻击。一种完全不同类别的侧信道攻击（可以针对密钥泄露部分信息）包括可能泄露内存内容的攻击。这其中包括冷启动攻击 [HSH 08]、DMA (Direct Memory Access)（直接内存访问）、Heartbleed 和 Spectre/Meltdown [LSG+18,KHF+19]。虽然这些攻击可能会泄露不完整的信息，因此可以作为我们讨论的某些算法的理论动机，但这类攻击中的大多数漏洞都可以简单地用于读取任意内存（以几乎完美的精度），并且很少需要密码分析算法。

依赖于长度的攻击。最后一个漏洞类是实现的行为取决于密钥的长度，因此行为的变化可能会泄露有关密钥中高位零的数量信息。一个简单的例子是将密钥复制到缓冲区中，以显示密钥的位长度。在另一个例子中，Raccoon 攻击观察到 TLS 版本 1.2 及以下版本在应用密钥派生函数之前从Diffie-Hellman共享密钥中去除高位零，从而导致时间差异取决于密钥长度所需的哈希输入块的数量。 [MBA 20]

3 数学背景

格和格规约算法。我们提出的几种算法都使用格和格算法。我们将陈述一些关于格的事实，但尽量避免过于正式。

出于本文的目的，我们将通过给出一个基矩阵 $B$ 来指定一个格，它是一个 $n×n$ 的线性独立行向量矩阵，具有有理向量（但在我们的程序中通常是整数）。 $B$ 生成的格，记作 $L(B)$ ，由所有向量组成，这些向量是 $B$ 的行向量的整数线性组合。格的行列式是基矩阵行列式的绝对值： $\det{L(B)}=\vert\det{B}\vert$ 。

在几何上，格类似于n维空间中的离散的、可能倾斜的点网格。这种离散性确保了格中存在最短的向量：格中的向量有一个非无穷小的最小长度，并且至少有一个向量 $v_1$ 可以达到这个长度。对于随机格，该向量的欧几里得长度近似于高斯启发式： $|v_1|_2\approx{\sqrt{n/(2\pi e)}(\det{L})^{1/n}}$ 。我们通常不需要这么高的精度，对于尺寸非常小的格，我们经常使用快速而粗略的近似： $|v_1|_2\approx{(\det{L})^{1/n}}$ 。

任意格中的最短向量要想精确计算是 NP困难的，但是 LLL 算法 [LLL82] 能在多项式时间内计算这个最短向量的指数近似值：在最坏的情况下，它将返回一个向量 $b_1$ 满足 $||b_1||_2\leq{2^{(n-1)/4}(\det{L})^{1/n}}$ 。在实践中，对于随机格，LLL算法获得了更好的逼近因子 $||b_1||_2\leq{1.02^n(\det{L})^{1/n}}$ [NS06]。事实上，LLL 算法将返回格的整个基，其向量很好地近似于格的连续最小值。就我们的目的而言，我们需要知道的是这些向量非常短，并且对于随机晶格，它们将接近相同的长度。 LLL 算法的当前实现可以很容易地在几百维的格上运行。

为了计算比 LLL 更接近最短向量的近似值，可以使用 BKZ 算法 [Sch87, SE94]。该算法在块大小中按时间指数运行，这是确定近似因子质量的算法参数。该算法的理论依据难以表达；就我们的目的而言，我们只需要知道对于维度低于 100 左右的格，我们可以很容易地计算出，使用 BKZ 算法的启发式随机格中的最短向量，并且通常可以找到最短向量，或者通过使用较小的块大小，“足够好”的近似值。理论上，LLL 算法等价于使用块大小为 2 的 BKZ。

4 对于RSA的密钥恢复方法

4.1 RSA初步

参数生成。要生成 RSA 密钥对，实现通常从选择公钥指数 $e$ 开始。到目前为止，最常见的选择是简单地固定 $e = 65537$ 。一些实现使用像 3 或 17 这样的小素数。几乎没有实现使用大于 32 位的公钥指数。这意味着涉及小于 $e$ 的暴力破解值的攻击在实践中通常是可行的。

下一步，实现生成两个随机素数 $p,q$ ，使得 $p-1,q-1$ 和 $e$ 互素。公共模数为 $N=pq$ 。私钥指数为 $d\equiv{e^{-1}}\pmod{(p-1)(q-1)}$ 。

公钥对为 $(e,N)$ ，理论上私钥对是 $(d,N)$ ，但是实际上很多实现将密钥存储在数据结构中，这就包括了更多信息。例如PKCS#1中，私钥格式包括字段 $p,q,d_p\equiv{d}\pmod{p-1}$ 和 $q_{inv}\equiv{q^{-1}}\pmod{p}$ ，用CRT来加速加密过程。

加密和签名。在教科书里的 RSA 中，Alice 通过计算 $c\equiv{m^e}\pmod{N}$ 将消息 $m$ 加密给 Bob。实际上，消息 $m$ 不是“原始”消息，而是首先使用填充方案从内容转换而来。网络协议中最常见的加密填充方案是 PKCS#1v1.5，但有时也会在协议中使用或指定 OAEP [BR95]。为了解密加密的密文，Bob 计算 $m\equiv{c^d}\pmod{N}$ 并验证 m 具有正确的填充。

为了生成数字签名，Bob 首先使用 PKCS#1v1.5 签名填充（最常见）或 PSS（不太常见）等填充方案对他希望签名的消息进行哈希和填充；令 $m$ 是这种形式的哈希和填充消息。然后 Bob 生成签名为 $s\equiv{m^d}\pmod{N}$ 。Alice 可以通过计算值 $m'\equiv{s^e}\pmod{N}$ 并验证 $m'$ 是正确的哈希和填充值来验证签名。

由于加密和签名验证只使用公钥，解密和签名生成过程就成为侧信道攻击的典型目标。

RSA-CRT。为了加速解密过程，避免直接计算 $c^d\pmod{N}$ ，实现通常使用中国剩余定理（CRT）。RSA-CRT把 $d$ 分为 $d_p,d_q$ 两个部分，其中 $d_p\equiv{d}\pmod{p-1},d_q\equiv{d}\pmod{q-1}$ 。

为了在解密中使用CRT，Alice 将计算 $m_p\equiv{c^{d_P}}\pmod{p}$ 和 $m_q\equiv{c^{d_q}}\pmod{q}$ 。消息可以借助预先计算的值 $q_{inv}\equiv{q^{-1}}\pmod{p}$ 通过计算下式恢复：

这个式子被称为加纳公式（Garner’s formula）[Gar59]。

RSA密钥元素之间的关系。 为了密钥的恢复，我们通常假设攻击者知道公钥。

RSA 密钥具有许多数学结构，我们可以将公钥和私钥的不同组成部分联系在一起，用于密钥恢复算法。 RSA 公钥和私钥是相互关联的：

这个模等式可以通过引入新变量 $k$ ，来获得整数关系：

我们知道 $d<(p-1)(q-1)$ ，于是 $k<e$ 。虽然攻击者不知道 $k$ 的值，但是因为通常 $e\leq65537$ ，所以在实际上暴力枚举所有可能的 $k$ 值是有效的。

对于针对CRT系数的 $dp,dq$ 攻击，我们可以获得类似的关系：对于某些整数 $k_p<e,k_q<e$

暴力破解两个独立的 16 位值可能会很麻烦，但我们可以将 $k_p,k_q$ 关联如下：重新整理这两个关系，我们得到

相乘得到 (原paper这里几个式子的符号有误)

对上式模 $e$

因此，给定 $k_p$ 的值，我们可以求解 $k_q\pmod{e}$ 的唯一值，于是对于需要暴力破解 $k_p,k_q$ 值的应用程序，我们只需要暴力破解最多 $e$ 对。

乘数 k 也与这些值也有很好的关系。将等式 1 中的关系相乘，我们有

用 $(p-1)(q-1)=(ed-1)/k$ 进行替换，同时对式子模 $e$ ，我们就可以将系数表示成：

当公钥 $(N, e)$ 已知时，任何密钥值 $p、q、d、d_p、d_q、q_{inv}$ 都足以计算所有其他值。

从 $p$ 或 $q$ 计算其他值很简单。对于小的 $e$ ， $N$ 可以从 $d$ 计算得到分解：

乘数 $k$ 可以通过 $[(ed-1)/N]$ 舍入来恢复。一旦 $k$ 已知，等式 3 就可以变形用于求解 $s=p+q$ 。 $s$ 知道后，我们就有 $(p+q)^2=s^2=p^2+2N+q^2,\ \ s^2-4N=p^2-2N+q^2=(p-q)^2$ ，于是 $N$ 就可以通过计算 $\gcd{((p+q)-(p-q),N)}$ 分解。

当 $e$ 很小时， $p$ 可以从 $d_p$ 计算得到（其中 $k_p$ 可以从 1 到 $e$ 枚举得到）

当 $k_p$ 未知且太大而无法枚举，那么对于任意的 $a$ ，有

通过 $q_{inv}$ 分解更为复杂。如 [HS09] 中所述， $q_{inv}$ 满足 $q_{inv}q^2 − q ≡ 0 \pmod N$ ，并且可以使用 Coppersmith 方法恢复 $q$ ，如下所述。

4.2 已知连续位的 RSA 密钥恢复

本节将介绍在已知密钥的大部分连续位时恢复 RSA 私钥的方法。在这种情况下使用的主要方法是格基规约。

对于本节中的密钥恢复问题，我们通常可以恢复未知密钥值（ $p,d \pmod{p − 1}$ 或 $d$ ）的一大块未知位。我们通常假设攻击者知道公钥 $(N, e)$ 但没有任何其他辅助信息（例如， $q$ 或 $d \pmod {q - 1}$ 。

在涉及噪声测量的侧信道中，不太可能出现密钥的大量连续部分信息。但在从内存中读取密钥，并在可识别区域损坏的情况下，可能会出现这类情况。如果为恢复已知位付出了巨大代价，它们还可以帮助提高攻击效率。

4.2.1 热身：对具有不良填充的低指数 RSA 的格攻击

用于连续位 RSA 密钥恢复的主要算法是通过找到整数模多项式的小根来描述问题，然后使用格基规约来解决这个问题。

为了介绍使用格基规约来求多项式根的主要工具，我们将从一个说明性示例开始，以说明使用已知填充攻击小指数 RSA 的具体应用。在后面的部分中，我们将说明如何优化这种方法，以涵盖不同的 RSA 密钥恢复场景。

这个问题的最初表述是由 Coppersmith [Cop96] 提出的。 Howgrave-Graham [HG97] 给出了一种我们发现更容易阐释并更容易实现的方法。 May 的研究 [May10] 包含了对 Coppersmith/Howgrave-Graham 算法的详细描述。

为了解决这个问题，我们假设有一个整数 $N$ 和一个 $k$ 次多项式 $f(x)$ ，其有根 $r$ 模 $N$ ，即 $f(r) ≡ 0 \pmod{N}$ 。我们希望找到这样的 $r$ 。找到多项式的根就可以有效地模素数 [LLL82]，所以如果 $N$ 是素数或 $N$ 的素数分解已知，这个问题很容易解决。当 N 的素数分解未知时，Coppersmith/Howgrave-Graham 方法很有趣：它提供了一种有效的算法来寻找未知分解的模数 $N$ 的所有小根（如果它们存在）。

问题设定。 对于我们的简单示例，我们将使用96位RSA模数

令 $e=3$ 。考虑一个损坏的 PKCS#1v1.5-esque RSA 加密填充方案，它将消息 m 填充为

现在假设我们得到了一个密文

我们希望恢复未知消息 $m$

图1：低指数 RSA 消息恢复攻击条件的图示。攻击者在加密之前知道模数 $N$ 、密文 $c$ 和填充在未知消息 $m$ 之前的填充 $a$ 。攻击者希望恢复 $m$ 。

将问题转换为找到多项式的根。 令

为已知的填充字符串（偏移到正确的字节位置）。我们也知道消息的长度；在这种情况下， $m < 2^{16}$ 。因此我们对于某个未知的 $m$ ，有 $c\equiv(a+m)^3\pmod{N}$ 。令 $f(x)=(a+x)^3-c$ ；由于我们已经设定了系数，所以我们希望找到一个多项式小根满足 $f(m)\equiv{0}\pmod{N}$ ，多项式化简如下

（这里已经对所有系数模 $N$ ）

构造格。 令 $f$ 的系数为 $f(x) = x^3+f_2x^2+f_1x+f_0$ 。设 $M = 2^{16}$ 是根 $m$ 大小的上限。我们构造矩阵

然后我们将 LLL 算法应用于矩阵。规约基的最短向量是

从格中提取多项式并找到它的根。 然后我们构造多项式

多项式 $g$ 有一个整数根 0x42，这就是 $m$ 的解。

这种特定的 4 × 4 格结构可以找到最大为 $N^{1/6}$ 的根。对于我们在示例中使用的小密钥，它仅为16位，但由于求解值直接与模数大小成比例，相同的格结构足以用1024位RSA模数得到170比特的消息，或者用2048位RSA模数得到341比特的消息。当然，4×4格基上的格基规约是非常快的。

更详细的阐释。 为什么能解出结果？该矩阵的行对应于多项式的系数向量 $f(x),Nx^2,Nx$ 和 $N$ 。我们知道，在 $x = m$ 处计算的这些多项式中的每一个都将模 $N$ 余0。每一列都按 $M$ 的幂进行缩放，因此该格中任何向量的1 - 范数都是在 $r$ 处计算的相应（未缩放）多项式值的上界。对于格中向量 $v=(v_3M^3,v_2M^2,v_1M,v_0)$ ，对任意 $|m|\leq{M}$ 有

我们已经构造了格子，因此我们从中提取的每个多项式 $g$ 都具有 $g(m) ≡ 0 \pmod N$ 的性质。我们还构造了格子，使得在约简基中的最短向量的长度将小于 $N$ 。能让 $N$ 小于 $N$ 的唯一整数倍数是 0，因此通过构造，对应于这个短向量的多项式在整数上满足 $g(m) = 0$ ，而不仅仅是模 $N$ 。由于找到多项式的根（整数，有理数，实数和复数）可以在多项式时间内完成，我们可以计算这个多项式的根，并检查其中哪一个是我们想要的解。

如果格子构造正确，此方法始终有效。也就是说，我们需要确保简化的基将包含一个长度小于 $N$ 的向量。对于这个例子， $\det B = M^6N^3$ 。于是，LLL算法将会找到一个向量，其 2 - 范数为 $|v|_2\leq{1.02^n(\det{B})^{1/\dim{B}}}$ 。我们赞数忽略 $1.02^n$ 这个因数，以及 2 - 范数和 1 - 范数之间的差异。那么我们希望满足的条件就是

例如，我们有 $\det{B}^{1/\dim{L}}=(M^6N^3)^{1/4}<N$ 。不等式对 $M$ 求解，我们得到 $M<N^{1/6}$ 。在上面的例子中， $N$ 为96比特， $m$ 为16比特，因此条件满足。

这个条件可以被扩展为 $N^{1/e}$ ，其中 $e$ 是在使用更高维的格后多项式 $f$ 的指数。Howgrave-Graham 的论文 [HG] 和 May 的研究 [May10] 对这种方法进行了详细的阐释和改进。

4.2.2 已知 $p$ 的连续位进行因式分解。

在本节中，我们将说明：如果已知一个因数的大部分连续位（不失一般性 $p$ ），如何使用格来分解 RSA 模数 $N$ 。

图 2：已知 $p$ 的连续高位，对 $N = pq$ 进行因式分解。

Coppersmith 在 [Cop96] 中解决了这个问题，但我们发现 Howgrave-Graham 将其重新表述为“近似整数公约数”[HG01]后，更易于应用，我们将在此处给出构造。

问题设定。 令 $N = pq$ 是具有相同比特的 $p$ 和 $q$ 的 RSA 模数。为了适合页面显示，选择一个足够小数字，我们有一个 240 位 RSA 模数

假设 $N$ 已知，假设我们知道 $p$ 的大量连续 $b$ 比特高位，因此 $p=a+r$ ，其中 $r$ 未知，但是我们知道 $a=2^lb$ 。这里我们令 $l=30$ 是未知比特，或者等价于已知位的左移量。

我们知道 $r$ 很小，并且特别的，对于某个已知界 $R$ ，有 $|r|<R$ ，这里 $R=30$ 。

构造格。 我们可以构造格基如下

然后对格基 $B$ 使用LLL算法。令 $v=(v_2R^2,v_1R.v_0)$ 是规约基的最短向量。在我们的例子中，我们得到向量

从格中提取多项式并找到它的根。 我们构造多项式 $f(x)=v_2x^2+v_1x+v_0$ 。在我们的例子中

我们可以计算 $f$ 的根，在此例子中，它有一个整数根 $r={\rm0x873209}$ ，然后我们可以重写 $a+r$ 并验证 $\gcd(a+r, N)$ 是 $N$ 的因数。

这个 3 × 3 格子适用于任何 $|r|<p^{1/3}$ ，并随着 $p$ 的增加直接减小。在我们的例子中，我们选择120位的 $p$ 和 $q$ ，而 $r$ 有 30 位。但是，同样的格可以从 1024 位 RSA 模数的 512 位因数中恢复 170 位，或从 2048 位 RSA 模数的 1024 位因数中恢复 341 位。

更详细的阐释。 该矩阵的行对应于多项式的系数向量 $x(x+a)$ 、 $x+a$ 和 $N$ 。我们知道当 $x = r$ 时计算这些多项式的值都是模 $p$ 余0，因此每个多项式对应的向量都有这个性质。与前面的例子一样，每一列都按 $R$ 的幂进行缩放，因此该格中任何向量的 1 - 范数都是在 $r$ 处计算的相应（未缩放）多项式的值的上限。

如果我们可以在格中找到一个长度小于 $p$ 的向量，那么它对应的多项式 $g$ ，必须满足 $g(r) < p$ 。因为通过构造，我们有 $g(r) = 0 \pmod p$ ，于是 $g(r) = 0$ 是整数解。

我们计算格的行列式，来验证它是否包含这样小的向量。对于本例， $\det B=R^3N$ ，这就说明我们需要 $(\det{B})^{1/\dim{L}}=(R^3N)^{1/3}<p$ 。对 $R$ qiujie ，得到条件 $R<p^{1/3}$ 。对于一个RSA模数我们有 $p\approx{N^{1/2}}$ ，所以有 $R<N^{1/6}$ 。

该方法通过增加格的维度，在极限处达到 $R < p^{1/2}$ 。这是通过取 $f$ 和 $N$ 的更高倍数来实现的。有关如何操作的详细信息，请参阅 Howgrave-Graham 的论文 [HG] 和 May 的研究 [May10]。

4.2.3 从 $p$ 的最低有效位恢复 RSA 密钥

采用上面的方法，来处理 $p$ 的最低有效位中的未知位块也很简单：如果块从第 $l$ 位开始，则输入多项式为 $f(x) = 2^lx+a$ 。多项式可以乘以 $2^{-l}$ ，然后完全按照上面的方法求解。

图3：已知 $p$ 的最低有效位，对 $N = pq$ 进行因式分解。

4.2.4 从 $p$ 的中间位恢复 RSA 密钥

从 $p$ 的中间位恢复 RSA 密钥比前面的例子复杂一些，因为在 $p$ 的最高和最低有效位中有两个未知的位块。

图4：已知 $p$ 的中间连续位，对 $N = pq$ 进行因式分解。

问题设定。 假设我们知道 $p$ 的大量中间连续位，于是我们有 $p=a+r_l+2^tr_m$ ，其中 $a$ 表示 $p$ 的已知位， $r_l,r_m$ 分别表示我们希望解出的最低有效位和最高有效位， $t$ 是未知最高有效位的起始位位置。我们知道对于某个界 $R$ ，有 $|r_l|<R,|r_m|<R$ 。

具体例子，令

是一个326位的RSA模数，令

是因数 $p$ 的中间已知位，于是有分别有16未知比特的最高有效位和最低有效位，因此我们知道 $R=2^{16}$ ，我们希望恢复 $p$ 。

将问题转换为寻找多项式的解。 在之前的例子中，我们只需要求解一个变量，现在我们有两个变量，所以我们需要使用一个二元多项式。写出如下多项式 $f(x,y)=x+2^ty+a$ ，于是 $f(r_l,r_m)=p$ 。

在我们具体的例子里， $p$ 有164比特，所以有 $f(x,y)=x+2^{148}y+a$ 。我们希望构造两个在整数上的多项式 $g_1(x,y),g_2(x,y)$ 满足 $g_1(r_l,r_m)=0,g_2(r_l,r_m)=0$ ，然后我们就可以求出方程组的根。

构造格。 和前面一样，我们将使用输入多项式 $f$ 和 RSA 的模数 $N$ 来构造一个格。不幸的是，尽管我们的例子很简单，最小的，可以保证在我们所需根的解大小上有一个非平凡的界，这样的多项式阶数为3，但我们还需要一个10维的格。

如前所述，每列对应于多项式中出现的一个单项式，每行对应于一个多项式，该多项式在我们的解中计算为 $0 \pmod p$ 。在我们的例子中，我们将使用多项式 $f^3,f^2y,fy^2,y^3N,f^2,fy,y^2N,f,yN$ 和 $N$ ；列中的单项式为 $x^3,x^2y,xy^2,y^3,x^2,xy,y^2,x,y$ 和 1 。每列按R的幂进行适当缩放。

我们使用 LLL 算法对这个矩阵进行规约，并重写与规约基的每一行相对应的二元多项式。不幸的是，它们太庞大而无法写页面上~~(作者偷懒)~~。

求解多项式组以找到公共根。 我们希望只需要两个足够短的向量，然后计算相应多项式的结果或使用 Gröbner 基来找到公共根，但在我们的例子中，两个最短向量不是代数独立的。在这种情况下，使用前三个向量就足够了。具体而言，我们在具有整数系数的二元多项式环上构造一个理想，其基是与上述 $L(B)$ 的规约基中的三个最短向量对应的多项式，然后对它使用Gröbner基算法。对于这个例子，Gröbner基是多项式 $(x−{\rm0x339b}, y − {\rm0x5a94})$ ，这就是 $x=r_l,y=r_m$ 的所需解。

在这个例子中，九个最短向量都在所需的解中为0，因此我们可以从这些短向量的其他子集，构建我们的 Gröbner 基。

更详细的阐释。 我们构造的格的行列式为 $\det{B}=R^{20}N^4$ ，格维数为10.我们希望能找到两个向量 $v_1,v_2$ ，其长度约为 $\det{B^{1/\dim{B}}}$ ；这并不能保证是可能的，但对于随机格，我们希望向量的长度在缩减的基础上接近相同的长度。向量 $v_1,v_2$ 的 1 - 范数是在期望根 $r_l,r_m$ 处计算的相应多项式 $f_{v_1}(x,y),f_{v_2}(x,y)$ 的大小的上界。为了保证这些向量为0，我们希望如下不等式成立：

因此，成功的理想条件是

对于我们的例子， $N$ 为326比特，我们选择的 $R$ 为16比特。

[BCC 13] 中应用了这种攻击，来恢复由错误的随机数生成器生成的 RSA 密钥，该生成器生成具有可预测位序列的素数。

4.2.5 从 $p$ 的多个位块中恢复 RSA 密钥

上面的想法可以扩展到处理更多 $p$ 的位块，但代价是增加格的维数。每个未知的“块”位都会在线性方程中引入一个新变量，该变量将求解 $p$ 。在极限情况下，该算法需要将 $p$ 的 70% 的位划分为最多 $\log{(\log{N})}$ 个块 [HM08]。

图5：已知 $p$ 的多个位块，对 $N = pq$ 进行因式分解。

4.2.6 开放问题：从 $p$ 的许多不连续位中恢复 RSA 密钥

上述方法随着已知位块的数量而难以扩展。如果只知道（比如） $N$ 的一个因子 $p$ 的不连续位，那么找到一种次指数时间方法来恢复 RSA 密钥或者使用超过 $\log{(\log{N})}$ 的未知位块来分解 RSA 模数 N 是一个开放问题。如果已知关于RSA私钥的p和q或其他字段的信息，则第4.3.1节中的方法可能适用。

图 6：给定许多 $p$ 的位块且没有关于 $p$ 的其他信息的情况下，分解 $N = pq$ 是一个开放问题。

4.2.7 RSA $d_p$ 的部分恢复

可以使用 4.2.2、4.2.3 和 4.2.4 节中给出的方法从大量连续位恢复 CRT 系数 $d_p \equiv{d} \pmod{p - 1}$ 。我们在已知最高有效位的情况下说明该方法。

给定 $d_p$ 大量连续位恢复 RSA 系数 $d_p \equiv{d} \pmod{p - 1}$ 。

问题设定。 令

是240比特的RSA模数，我们使用公钥指数 $e=65537$ 。

在这个问题中，我们有 $d_p$ 的 $b$ 位最高有效位，我们希望恢复剩余的比特。和之前类似，令 $l$ 是我们需要恢复的 $d_p$ 的最低有效位的比特数，因此对某个 $r<2^l$ ，我们有 $a=2^lb,a+r=d_p$ 。具体例子，我们令

将问题转换为寻找多项式的解。 我们从等式 $ed_p\equiv{1}\pmod{p-1}$ 开始，我们引入一个新变量 $k_p$ ，将等式重写为一个整数关系：

整数 $k_p$ 是未知的，但是由于 $d_p<p-1$ ，于是我们知道 $k_p<e$ 。在我们的例子里，我们有 $e=65537$ ，因此我们将对 $1≤ kp < 65537$ 范围内所有可能值进行攻击。有了正确的参数，我们可以保证找到 $kp$ 正确值。对于 $kp$ 的其他错误猜测，在实际中，攻击不太可能找到任何其他解，出现的任何虚假解都可以舍去，因为它们最终不能分解 $N$ 。

我们将等式 4 重写，计算 $e^{-1}\pmod{N}$ 的值后：

记 $A=a+e^{-1}(k_p-1)$ 。我们希望找到多项式 $f(x)=A+x\pmod{p}$ 的小根 $r$ ， $|r|<R$ 。

对于我们的例子来说， $R=2^{30},k_p=23592$ ，于是

构造格。 由于问题的形式与上一节相同，我们使用相同的格构造：

对这组基应用 LLL 算法，并且取规约基的最短向量，对于我们的例子，其为

得到其对应多项式

计算多项式 $f$ 的根，我们发现有 $r=\rm 0x39d9b141$ 满足条件，于是计算 $\gcd(A+r,N)=p$ 。

在极限情况下，通过增加具有更高次多项式和更高根重数的格的维数，该方法可以使用到 $R<p^{1/2}$ [BM03]。

4.2.8 从最高有效位部分恢复 RSA 的 $d$ 是不可能的

$d$ 的部分恢复在一定程度上取决于已知位和 $e$ 的大小。由于 $e$ 在实践中很小，我们将在这里重点讨论这种情况。

图 7：对于小指数 $e$ ， $d$ 的最高有效位不允许完整密钥恢复。

$d$ 的最高有效位。当 $e$ 足够小，足以使用暴力破解时， $d$ 的最高有效位的一半可以很容易地恢复，而无需额外的信息。这意味着，如果只可能从 $d$ 的最高有效位的一半进行完整密钥恢复，那么低公钥指数 RSA 将被完全破坏。由于通常认为低公钥指数 RSA 是安全的，不幸的是，这意味着这种情况下不可能有这样的密钥恢复方法。

考虑 RSA 等式，一步步对其变形

由于 $p+q\approx{\sqrt{N}}$ ，第二项仅影响 $d$ 的最低有效位的一半，因此 $kN/e$ 的值与 $d$ 共享其最高有效位的一半。

从积极的方面来看，如果攻击者真的知道 $d$ 的任何最高有效位，则此结论允许攻击者缩小 $k$ 的可能值。有关详细信息，请参阅 Boneh、Durfee 和 Frankel [Bon98]。

4.2.9 从最低有效位部分恢复 RSA 的 $d$

对于低指数RSA，如果攻击者知道 $d$ 的最低有效 $t$ 位，则可以将其转换为 $p$ 的最低有效 $t$ 位，然后可以应用第4.2.3节的方法。该算法由Boneh、Durfee和Frankel [Bon98]提出。

图 8：在给定 $d$ 的连续最低有效位的情况下恢复 RSA 的 $p$ 。

假设攻击者知道 $d$ 的最低 $t$ 位有效位，设为 $d_0$ ，于是

设 $s=p+q$ ，攻击者遍历 $1<k<e$ 中的所有值，从而得到 $s$ 的最低 $t$ 个有效位的 $e$ 个候选值。

然后对于每个 $s$ 的候选值， $p$ 的最低有效位是方程

的解。

令 $a$ 是 $p$ 的最低有效位候选解，将其带入4.2.3节的内容，攻击者想要求出 $f(x)=a+2^tx\equiv 0\pmod{p}$ 的解，我们可以两边乘上 $2^{-t}\pmod{N}$ ，然后用4.2.3节的方法恢复 $p$ ，由于在极限情况下，4.2.3节的方法可以恢复 $p$ 的 $N^{1/4}$ 位，所以当 $d$ 的 $N^{1/4}$ 位已知时，这里的方法可以适用。

当然，存在涉及不同的权衡的、更复杂的格算法，但对于非常小的 $e$ （这在实践中是典型的情况），它们需要知道 $d$ 的几乎所有最低有效位[BM03]。

4.3 已知冗余的非连续位

本节介绍，在已知或需要恢复许多非连续位密钥的情况下的密钥恢复。上一节中介绍的格方法可以用于恢复未知关键位的多个块，但代价很高：格维数会随着块的数量增加而增加，并且当要恢复大量位时，运行时间是块数量的指数倍。

在本节中，我们将探讨一种允许不同权衡的方法。在这种情况下，攻击者知道许多不连续的密钥值位，并且知道密钥的多个值。例如，攻击者可能已经知道了 $p$ 和 $q$ 的一部分，或者 $d \pmod{p - 1}, d \pmod{q - 1}$ 。

4.3.1 已知 $p$ 和 $q$ 的随机位

图9：已知 $p$ 和 $q$ 的随机位，分解 $N=pq$ 。

我们先从一个现实中不太可能发生的情况开始分析，即擦除 $p$ 和 $q$ 的随机位的情况，以此从最简单的情况给出算法背后的主要思想。

这些情况主要采用的方法是剪枝算法。剪枝算法背后的思想是写下密钥和公钥中元素之间的整数关系，并从最低有效位开始逐步求解密钥的未知位。这会产生一棵解的树：每个分支对应特定解的一个或多个未知位的猜想，如果猜想导致它与公钥的关系不正确，则修剪分支。

该算法在 [HS09] 中有介绍和分析。

问题设定。 令 $N=899$ ，假设我们已知 $p$ 和 $q$ 的一些比特，在擦除模型中：对于每个位，我们要么知道位的值，要么不知道。例如：

确定整数关系。 在这个例子中，我们使用的整数关系是 $N = pq$ 。

迭代求解每一位。 该算法的主要思想是，从最低有效位开始，迭代求解未知量 $p$ 和 $q$ 的每一位。然后对照已知的 $N$ 检查这些值。

对于最低有效位，对于 $p$ 是已知的，对于 $q$ 是未知的。 $q$ 有两种选择，但只有值 1 满足条件 $pq \equiv N \pmod 2$ 的。然后算法进行下一步，其中第二位的值对于 $q$ 是已知的，但对于 $p$ 是未知的。只有值 1 满足条件 $pq \equiv N \pmod {2^2}$ ，所以算法继续进行这个分支。由于这会生成一棵树，因此可以按深度优先或广度优先的顺序遍历树；深度优先将更节省内存。如图 10 所示。

图10：例子的剪枝树。该算法表示：从最低有效位的右侧节点开始，向最高有效位移动，迭代地对连续位进行剪枝和猜测。

该算法之所以有效，是因为对任意正整数 $i$ ，有 $N=pq\pmod{2^i}$ 。此外，我们希望确保对特定位的值的错误猜测，可以让该分支被修剪。所以，当 $p$ 和 $q$ 的第 $i$ 位都未知时，树会分支；当第 $i$ 位只有一个知道时，那么就只有一个特解；当 $p$ 和 $q$ 的第 $i$ 位都已知时，大约有50%的概率删减一个不正确的解。因此，只要没有长时间运行同时未知比特，该算法就有可能有效。我们假设 $p$ 和 $q$ 的长度是已知的，一旦算法遍历完所有比特，就可以在没有模的情况下对比等式 $N = pq$ 。

当获知 $p$ 和 $q$ 中随机位，[HS09] 的研究表明，当已知 $p$ 和 $q$ 57% 的随机位时，生成的解树具有多项式大小。如果已知位的分布不是随机的，只要它能有效地修剪树，算法仍然可以有效。如 [YGH16] 中：已知 $p$ 和 $q$ 的每 5 位中的 3 位。

Paterson、Polychroniadou和Sibborn[PPS12]对不同场景下所需的信息进行了分析，并观察到深度优先搜索比广度优先搜索在内存上更高效。

4.3.2 已知中国剩余定理系数 $d\pmod{p-1},d\pmod{q-1}$ 的随机比特

可以用于 4.3.1 节中相同的方法，对 4.3.1 节中的描述进行扩充，就可以恢复中国剩余定理的指数 $d_p\equiv{d}\pmod{p-1},d_q\equiv{d}\pmod{q-1}$ 。这是 RSA 侧信道攻击中最常见的情况。

给定 $d_p,d_q$ 的非连续位，分解 $N=pq$ 。

问题设定。 令 $N=899$ ， $e=17$ 。假设攻击者知道 $d_p,d_q$ 的部分非连续位，

我们希望通过恢复 $d_p,d_q$ 的未知位，来恢复密钥。

确定整数关系。 我们知道 $ed_p\equiv1\pmod{p-1},ed_q\equiv1\pmod{q-1}$ ，将其变形为整数关系

我们没有关于 $p$ 和 $q$ 值的信息，但它们的值是可以通过猜测 $d_p$ 或 $d_q$ 唯一确定。

我们还知道 $pq=N$ 。由于我们不知道 $k_p,k_q$ ，所以我们不惜通过遍历所有可能值爆破它们。我们希望舍去错误值，保留唯一正确的值。4.1 节中的等式 $(2)$ 说明，对于一个给定 $k_p$ 有一个唯一 $k_q$ 与之对应。因为 $k_p<e$ ，我们最多只需要尝试 $e$ 组可能的 $k_p,k_q$ 值。

在我们的例子中，我们有 $k_p=13$ 和 $k_q=3$ （尽管在找到解之前，这不会被确定为正确的猜测）。

迭代求解每一位。 有了整数关系，我们就可以从最低有效位开始，使用它们，迭代求解未知数 $d_p,d_q,p$ 和 $q$ 的每一位。根据三个整数关系检验每个猜测的值，并且在第 $i$ 位修剪那些不满足整数关系模 $2^i$ 的值。因为我们有三个关系和四个未知数，所以我们在每位上最多生成两个新分支。

由于到第 i 位的 $p$ 和 $q$ 的值是由我们对 $d_p$ 和 $d_q$ 的猜测唯一确定，因此算法基于等式 $pq≡N \pmod{2^i}$ 对解剪枝。随后，这种情况的分析与已知 $p$ 和 $q$ 随机比特的情况相同。

对于 $k_p,k_q$ 值的错误猜测，我们希望方程像随机约束一样，很快无法成立。一旦树中不再有可能的解，已知 $k_p,k_q$ 的猜测就是不正确的。如图11所示。

图11：从树右侧的最低有效位开始，我们给出一个样本分支并修剪树来从已知位恢复 $d_p$ 和 $d_q$ 。对于每个位， $p$ 到第 $i$ 位的值，由 $dp$ 到第 $i$ 位的猜测唯一确定；而 $q$ 到第 $i$ 位的值，由 $dq$ 到第 $i$ 位的猜测唯一确定。红色 X 标记通过验证等式 $pq≡N \pmod{2^i}$ 修剪分支。

4.3.3 从间接信息中恢复 RSA 密钥

对于这种类型的密钥恢复算法，并不总是需要直接知道密钥值的比特值。即使只知道关于秘密值的“隐含”信息，仍然可以应用剪枝算法来恢复密钥（只要该隐含信息可以从最低有效位开始猜测，通过检验来选择或修剪候选值）。文献中的例子包括 [BBG 17]，它计算猜测的候选值的部分滑动窗口快速幂序列，并将它们与实际值进行比较；还有 [MVH 20]，它将二进制GCD算法实现中的程序分支序列与实际值进行比较。

4.3.4 开放问题：无冗余的随机已知位

如第4.2.6节所述，当需要恢复许多非连续的比特块时，恢复RSA密钥是一个开放问题（已知的比特只来自一个密钥字段，没有来自其他值的额外信息）。将本节中讨论的剪枝方法应用于单个密钥值，例如已知 $p$ 的随机比特，除非有额外信息可用于修剪树，否则将产生一个具有指数多个解的树。

5 DSA 和 ECDSA 的密钥恢复方法

5.1 DSA 和 ECDSA 初步

从部分密钥恢复的角度来看，DSA 和 ECDSA 非常相似，所以我们将一起介绍。我们将使用稍微不标准的符号来描述每个签名方案，使它们尽可能接近，以便我们可以使用相同的符号同时描述攻击。

5.1.1 DSA

数字签名算法 [NIS13] (DSA) 是对 ElGamal 签名方案 [EG85] 的改进，它通过使用 Schnorr 群 [Sch90] 减少了所需的计算量和生成的签名大小。

参数生成。 DSA 的公钥包括几个全局参数：给定定义一个在 $p$ 上的群，一个阶为 $n$ 的子群（ $n$ 满足 $n|(p-1)$ ）和一个生成元 $g$ ，其生成一个阶为 $n\pmod{p}$ 的子群（ $n$ 远远小于 $p$ ，比如对于2048比特的 $p$ ，选择256比特的 $n$ ）。一组群的参数可以在多个公钥之间共享，也可以为特定公钥单独生成。

为了生成一个长期的私有签名密钥，首先选择一个密钥 $0<d<n$ ，并计算 $y\equiv{g^d}\pmod{p}$ 。公钥组是 $(y,g,p,n)$ ，私钥组是 $(d,g,p,n)$ 。

签名生成。 为了对消息 $m$ 进行签名，需要用抗碰撞哈希函数 $H$ 对 $m$ 进行哈希，得到 $h=H(m)$ 。为了生成签名，需要生成一个随机参数 $0<k<n$ ，并计算 $r=({g^k}\pmod{p})\pmod{n}$ 和 $s=k^{-1}(h+dr)\pmod{n}$ 。签名对为 $(r,s)$ 。

5.1.2 ECDSA

椭圆曲线数字签名算法 (ECDSA) 是对 DSA 的改编，使用椭圆曲线而不是 Schnorr 群。

参数生成。 ECDSA公钥包括指定有限域上椭圆曲线 $E$ 的全局参数，以及 $E$ 上 $n$ 阶子群的生成元 $g$ 。

为了生成长期私钥，首先选择一个密钥 $0<d<n$ ，并计算 $E$ 上的椭圆曲线点 $y=dg$ 。公钥是椭圆曲线点 $y$ 以及全局参数 $E$ 、 $g$ 和 $n$ 。私钥是整数 $d$ 以及这些全局参数。

签名生成。 为了对消息 $m$ 进行签名，需要用抗碰撞哈希函数 $H$ 对 $m$ 进行哈希，得到 $h=H(m)$ 。为了生成签名，需要生成一个随机参数 $0<k<n$ ，计算椭圆曲线上的点 $kg$ ，并令 $r$ 为 $kg$ 的 $x$ 坐标值。然后计算整数 $s=k^{-1}(h+dr)\pmod{n}$ 。签名对为 $(r,s)$ 。

5.1.3 随机参数恢复和 (EC)DSA 的安全性

(EC)DSA 的安全性极其依赖于签名随机数 $k$ 的安全生成、均匀分布和每个签名的唯一性。如果一个或多个签名的随机数以易受攻击的方式生成，那么攻击者可能有效地恢复长期签名密钥。由于这一特性，针对 (EC)DSA 的侧信道攻击几乎普遍针对随机数生成。

从签名随机数中恢复密钥。 对于 DSA 或 ECDSA 密钥，如果用于单个签名的随机数 $k$ 已知，则计算长期私钥很简单。对 $s$ 的表达式变形，密钥 $d$ 可以恢复为

5.2 从随机数 $k$ 的最高有效位恢复 (EC)DSA 密钥

从随机数 k 的最高有效位恢复 (EC)DSA 密钥主要有两种方法。两种方法都需要知道来自同一密钥的多个签名中，使用的随机数的信息。我们假设攻击者知道长期签名验证公钥，并且可以使用相应的签名密钥生成的多个签名。攻击者还需要知道签名对应的消息的哈希值。

图 12：已知随机数的最高有效位，恢复 (EC)DSA 密钥。

第一种方法是通过格。通常认为其更容易实现，并且当我们知道更多的随机数位，且来自更少签名的信息可用时，其效果很好：我们需要从几十到数百个签名的随机数中，至少知道两个最高位。我们将在下面介绍这种方法。

第二种方法是通过傅立叶分析。这种方法可以处理签名随机数中至少已知一个最高有效位的情况，但从经验上看，它似乎需要比格的方法，多一个数量级甚至更多的签名。最近的研究里有使用 $2^{23}$ 个[ANT 20]、 $2^{35}$ 个[ANT 20] 和 $2^{26}$ 个[TTA18] 签名进行记录和计算。我们把对该方法更详细的讨论，留给本文的未来版本。读者可以在 [DHMP13, TTA18] 中找到对该算法的详细描述。

5.2.1 格攻击

(EC)DSA 密钥恢复的格攻击背后的主要思想：是将 (EC)DSA 密钥恢复问题转化为 HNP（隐藏数问题），然后计算一个经特殊构造的格的最短向量，最终求解。

下面我们给出一个简单的例子，说明当随机数的许多最高有效位为零时，如何从少量签名中恢复密钥。然后我们将说明如何将攻击扩展到使用更多签名，而每个随机数的已知位更少，并涵盖已知随机数的任意位的情况。

问题设定。 令 $p={\rm 0xffffffffffffd21f}$ 是一个64比特素数，令 $E$ ： $y^2=x^3+3$ 是定义在 $F_p$ 上的椭圆曲线。令 $g=(1,2)$ 是椭圆曲线 $E$ 的生成元，其阶为 $n={\rm 0xfffffffefa23f437}$ 。

我们有如下两个签名：

对于明文哈希值 $h_1={\rm 0xae0f1d8cd0fd6dd1}$
对于明文哈希值 $h_2={\rm 0x8927e246fe4f3941}$

这些签名都使用 32 位随机数 $k$ ；也就是说，我们知道它们的 32 个最高有效位是 0。

将问题转换为方程组。 我们上面的签名满足等价于

$k_1,k_2,d$ 的值是未知的，其他是已知的。我们把 $d$ 消去后，整理式子

令 $t=-s_1^{-1}s_2r_1r_2^{-1},\ u=s_1^{-1}r_1h_2r_2^{-1}-s_1^{-1}h_1$ ，上式就化为

我们希望解出 $k_1,k_2$ ，我们知道它们都很小，所以有 $|k_1|,|k_2|<K$ ，在我们的例子中 $K=2^{32}$ 。

构造格。 我们构造出如下的格

向量 $v=(k_1,k_2,K)$ 在我们构造的格中，我们希望它是格中的最短向量。

通过在 $B$ 上运行 BKZ 算法，我们得到规约基中第三个短向量为

我们可以验证例子中的 $r_1$ 是否与 $k_1g$ 的 x 坐标相等，我们可以使用公式 5 来计算私钥 $d$ 。

更详细的阐释。 在我们的例子中，我们构造了一个包含目标向量的格。为了让这个方法起作用，我们希望它是最短向量，或者接近格子中的最短向量，我们通过解格中的最短向量问题来找到它。

构造的向量 $v=(k_1,k_2,K)$ 长度为 $|v|_2\leq{\sqrt{3}K}$ 。构造的格的行列式为 $\det{B}=nK$ 。暂时忽略常数，如果我们的格是真随机的，我们希望最短向量的长度 $\approx \det{B^{1/\dim{B}}}$ 。因此如果 $|v|_2\leq{\det{B^{1/\dim{B}}}}$ ，我们预计它就是格中的最短向量，并通过 SVP 找到一个好的近似。

在我们的例子中，当 $K<(nK)^{1/3}$ 或 $K<\sqrt{n}$ 时，条件满足。

这里采用的方法可能会让读者想起 4.2.1 节中的方法。这里使用的特定格的构造是 4.2.1 节中构造的一种“对偶”，因为目标向量是我们方程组的所需解。然而，与第 4.2.1 节相比，虽然我们找到短向量，但不能保证找到我们想要的解，因为与预期的最短向量长度相比，我们的目标向量 $d$ 越短，这种方法成功的概率越小。

HNP (The Hidden Number Problem) 我们用于解决这些问题的格算法，是基于 Boneh 和 Venkatesan [BV96] 提出的 HNP (隐数问题) 。他们通过这种方法说明 Diffie-Hellman 共享密钥中的最高有效位十分重要。 Nguyen 和 Shparlinski 说明了在已知随机数相关信息的条件下，如何使用这种方法攻击 DSA 和 ECDSA [NS02, NS03]。这种方法的延申可以解决已知每个签名的不同比特 [BvSY14] 或者错误 [DDME+18] 。

还有一种使用傅里叶分析 [Ble98, DHMP13] 的算法可以解决这个问题，它最初由 Bleichenbacher 提出；它需要更多的样本，但可以处理更少的已知位。

扩展到更多签名，减少已知比特。 为了减少每个签名所需的位数，我们可以将更多签名放入格中。如果我们已知对面明文的哈希值 $h_1,\dots,h_m$ 有对应签名 $(r_1,s_1),\dots,(r_m,s_m)$ ，我们用同样的方法写出等式 $s_i\equiv{k_i^{-1}(h_i+dr_i)}\pmod{n}$ ，然后像上面一样消去 $d$ 整理式子：

然后构造出格：

为了解决 SVP ，我们必须运行像块大小为 $\dim{L(B)}=m+1$ 的 BKZ 算法。使用 BKZ 算法解决 SVP 问题，目前可以有效地完成约100维的格；当维数更大时，其花费就越来越多。实际上，对于固定参数，通常可以使用更多样本来构建更高维的格，并且用更小的块的 BKZ 来找到目标向量，从而提高运行效率。这种方法可以在已知最高 4 位的 nonce 的条件下，使用大约 70 个样本（ 256 位的 ECDSA ）；已知最高 3 位的 nonce 的条件下，使用大约 95 个样本。而对于已知比特更少的情况，需要傅里叶分析，或者需要这些格技术的更强大的应用，以及更强大的计算能力。

已知最高非零有效位。 如果 $k_i$ 的最高有效位已知且非零，我们把它写成 $k_i=a_i+b_i$ ，其中 $a_i$ 已知，而 $b_i$ 很小，所以有 $|b_i|<K$ 。然后把式子带入等式 $(6)$ ，有

令 $u_i'=u_i+a_i+t_ia_m$ ，然后在上面构造的格里用 $u_i'$ 替换 $u_i$ 。

随机数再平衡。 签名随机数 $k_i$ 的范围是 $0<k_i<n$ ，而格结构限制绝对值 $|k_i|$ 。因此如果我们知道对于某个界 $K$ ， $0<k_i<K$ ，我们可以通过重新规范化签名来实现更严格的约束。令 $k_i'=k_i-K/2$ ，于是 $|k_i'|<K/2$ 。我们就可以把等式 $(7)$ 写成

于是我们有了一个关于 $t_i'=t_i,u_i'=(t_i+1)K/2,K'=K/2$ 的等价问题，我们用之前的方法可以对其求解。这种优化减少了所需样本的数量，在实际中有重要作用。

5.2.2 从随机数 $k$ 的最低有效位恢复 (EC)DSA 密钥

上一节中描述的攻击，同样适用于 (EC)DSA 中已知随机数的最低有效位的情况。

图 13：已知随机数的最低有效位，恢复(EC)DSA 的签名密钥。

问题设定。 我们对明文的哈希值 $h_i$ 进行 (EC)DSA 签名得到 $(r_i,s_i)$ 。对于每个签名，我们知道随机数 $k_i$ 的最低有效位，于是

其中 $a_i$ 已知， $b_i$ 未知但满足 $|b_i|<B$ 。

将上面的式子带入等式 $(7)$

对于这个问题我们有等价关系 $t_i'=t_i,u_i'=2^{-l}(a_i+t_ia_m+u_i),B'=B$ ，然后用上面的方法求解即可。

5.2.3 从随机数 $k$ 的中间位恢复 (EC)DSA 密钥

图 13：已知随机数的中间位，恢复(EC)DSA 的签名密钥。

从随机数 $k$ 的中间位恢复 ECDSA 密钥，比上面讨论的方法稍微复杂一些，因为对于每个签名有两个未知的随机数“块”要恢复。幸运的是，我们可以将方法扩展到对每个签名的多个变量来处理这些问题。我们在这里使用的方法类似于第 4.2.4 节中的多变量扩展，但这里的情况更简单。

问题设定。 我们将使用与上面相同的椭圆曲线参数。令 $p={\rm 0xffffffffffffd21f}$ 是一个64比特素数，令 $E$ ： $y^2=x^3+3$ 是定义在 $F_p$ 上的椭圆曲线。令 $g=(1,2)$ 是椭圆曲线 $E$ 的生成元，其阶为 $n={\rm 0xfffffffefa23f437}$ 。

我们有如下两个签名：

对于明文哈希值 $h_1={\rm 0x608932fcfaa7785d}$
对于明文哈希值 $h_2={\rm 0x4de972930ab4a534}$

我们知道相应随机数的一些中间位。令

是第一个签名使用的随机数 $k_1$ 的中间 34 位，其前后 15 位未知。令

是第二个签名使用的随机数 $k_2$ 的中间 34 位，其前后 15 位未知。

将问题转换为方程组。 同上， $k_1,k_2$ 满足等式

其中 $t=-s_1^{-1}s_2r_1r_2^{-1},\ u=s_1^{-1}r_1h_2r_2^{-1}-s_1^{-1}h_1$ 。

因为我们知道 $k_1,k_2$ 的中间位 $a_1,a_2$ ，所以有

其中 $b_1,c_1,b_2,c_2$ 未知但很小，小于界 $K$ 。在我们的例子里，有 $|b_1|,|c_1|,|b_2|,|c_2|\leq{2^{15}}$ ， $l=64-15=49$ 。

对等式 $(8)$ 进行替换和整理

令 $u'=a_1+ta_2+u$ 。我们希望对下面的线性等式找到小根 $x_1=b_1,y_1=c_1,x_2=b_2,y_2=c_2$

构造格。 构造如下格基

对上面的的格 $B$ 使用 BKZ 算法，我们得到的规约基中有如下向量：

其对应线性等式

对基中接下来的三个短向量做同样的事情，最终对四个未知数，我们有四个线性多项式。解方程组，我们得到解

更详细的阐释。 格的行向量对应等式 $(9)$ 中的线性多项式 $f$ 的加权系数向量 $nx_1、ny_1、nx_2$ 和 $ny_2$ 。当在所需解 $x_1=b_1,y_1=c_1,x_2=b_2,y_2=c_2$ 处求值时，每一个线性多项式都在构造中模 $n$ 为0，因此和格中的向量对应的任何线性多项式都是这样。如果我们能找到一个 1 - 范数小于 $n$ 的格向量，那么当在所需解处求值时，对应的线性方程在整数上为0。由于我们有四个未知数，如果我们能找到对应四个线性独立方程的四个短格向量，我们就可以解出我们想要的未知数。

我们例子中格的行列式为 $\det{B}=K^4n^4$ ，格的维度是5.因此忽略近似因数和常数，我们希望找到一个长为 $\det{B^{1/\dim{B}}}=(Kn)^{4/5}$ 的向量。当 $K^4<n$ 时，它比 $n$ 小；由于我们选择了15比特的 $K$ 和64比特的 $n$ ，例子是满足条件的。

行列式的界能保证我们找到一个短向量，但不能保证找到四个短向量。为此，我们需要能让随机格的规约向量接近相同长度的启发式方法。

5.2.4 从随机数的许多位块中恢复 (EC)DSA 密钥

上述方法可以扩展到任意数量的变量的情况。

从已知随机数的多个位块中恢复 (EC)DSA 签名密钥。

这种扩展叫 Ex HNP（Extended Hidden Number problem）（扩展隐数问题），它可以解决已知随机数的多个位块时恢复 (EC)DSA 签名密钥的问题。每个签名的随机数的每个未知“块”都会引入一个新变量，因此生成的格的维数将比未知数的总数大一；如果有 $m$ 个签名，每个签名随机数有 $n$ 个未知“块”，格的维数就是 $mh+1$ 。当参数使得方程组具有唯一解时，我们希望这种方法可以找到解。如果每个块的大小为 $K$ ，那么找到解的条件就是 $K^{mh}<n^{m-1}$ 。这种方法已在 [FWC16] 中用于实践，并在 [DPP20] 中进一步探索。

6 Diffie-Hellman 密钥交换的密钥恢复方法

6.1 有限域和椭圆曲线 Diffie-Hellman 初步

Diffie-Hellman (DH) 密钥交换协议 [DH76] 允许两方以安全的方式创建一个公共密钥。我们在有限域和椭圆曲线的背景下总结了协议。

有限域 Diffie-Hellman。 有限域 Diffie-Hellman 的参数由素数 $p$ 和生成元 $g$ 确定。常见实现是选择一个安全素数 $p$ ，即 $q = (p − 1)$ 是素数，在这种情况下 g 通常等于 2、3 或 4 ；或者选择素数 $p$ ，使得 $p-1$ 有160、224或256位的素因子 $q$ ，并且 $g$ 生成一个 $q$ 阶 $F_p^*$ 的子群。密钥交换过程如下：

Alice 选择一个随机私钥 $a$ ，满足 $1\leq a<q$ ，计算一个公钥 $A=g^a\pmod{p}$
Bob 选择一个随机私钥 $b$ ，满足 $1\leq b<q$ ，计算一个公钥 $B=g^b\pmod{p}$
Alice 和 Bob 交换公钥
Alice 计算 $s_A=B^a\pmod{p}$
Bob 计算 $s_B=A^b\pmod{p}$

因为 $B^a=(g^b)^a=(g^a)^b=A^b\pmod{p}$ ，所以 $s_A=s_B$ 。后者是 Alice 和 Bob 共享的密钥。

椭圆曲线 Diffie-Hellman。 椭圆曲线 Diffie-Hellman (ECDH) 协议是 Diffie-Hellman 密钥交换协议的椭圆曲线对应。在 ECDH 中，Alice 和 Bob 共享有限域上的椭圆曲线 $E$ 和 $q$ 阶生成元 $G$ 。

Alice 选择一个随机私钥 $a$ ，满足 $1\leq a<q$ ，计算一个公钥 $A=aG$
Bob 选择一个随机私钥 $b$ ，满足 $1\leq b<q$ ，计算一个公钥 $B=bG$
Alice 和 Bob 交换公钥
Alice 计算 $s_A=aB$
Bob 计算 $s_B=bA$

共享密钥为 $s_A=aB=a(bG)=b(aG)=bA=s_B$ 。

6.2 已知有限域 Diffie-Hellman 共享密钥的最高有效位

我们在上一节中，从关于 nonce 的信息中恢复 ECDSA 或 DSA 密钥，使用的 HNP 方法，也可以用于从最高有效位恢复 Diffie-Hellman 共享密钥。

从 $s$ 的最高有效位恢复 Diffie-Hellman 共享密钥。

问题设定。 令 $p={\rm0xffffffffffffffffffffffffffffc3a7}$ 是用于有限域 Diffie-Hellman 的 128 位素数，令 $g=2$ 是模 $p$ 的乘法群生成元。

令 $s$ 是 Diffie-Hellman 的共享私钥，有

我们已知 $s$ 的前65位：

因此 $s=r_1+k_1$ ，其中 $k_1<K=2^{63}$ 。

令 $c = 0x56e112dac14f4a4cc02951414aa43a38$ ，同样我们知道 $AC=g^{a+c}=g^ag^c\pmod{p}$ 和 $B$ 之间的共享私钥的前65位：

我们知道 $g^{(a+c)b}=g^{ab}g^{bc}=sB^c\pmod{p}$ 。令 $t=B^c$ ，于是 $st=r_2+k_2\pmod{p}$ ，其中 $k_2<K=2^{63}$ 。

将问题转换为方程组。 我们有两个等式

其中 $s,k_1,k_2$ 是很小的未知数， $r_1,r_2,t$ 已知。我们将变量 $s$ 消去，得到线性等式

我们现在有一个与我们在上一节中解决的 HNP 相同形式的线性方程。

构造格。 我们构造格基：

我们对 $M$ 使用 LLL 算法得到的规约基包含下面的向量

这与我们期望的解 $(k_1，k_2，K)$ 相对应。但是就算Diffie-Hellman假设为真，我们还是无法验证其正确性。

更详细的阐释。 这种方法由 Boneh 和 Venkatesan [BV96] 提出，这种方法也是他们提出 HNP 的最初动机。Raccoon 攻击最近展示了在 TLS [MBA 20] 中使用这种方法的攻击场景。

该方法可以适用于多个样本，其所需的位数与对 ECDSA 的攻击所需位数相同。我们也不需要知道 $s$ 的最高有效位；我们只需要知道 $s$ 的倍数 $t_i$ 的最高有效位。

6.3 已知 Diffie-Hellma 密钥指数连续位的离散对数攻击

本节讨论当已知部分信息是秘密指数的一部分或另一部分时，Diffie-Hellman密钥恢复的问题。我们在本节使用的方法是 Pollard’s kangaroo （也叫 lambda）算法。与前几节的方法不同，本节算法以指数时间运行：区间大小的平方根；前几节中的方法通常在攻击者对密钥的了解高于某个阈值时有效，而在攻击者对密钥的了解低于该阈值时无效或不可行。因此，与暴力破解相比，它有显著的优势，但在实际中，密钥恢复可能仅限于 80 位或更少，除非有相当大量的计算资源。

Pollard kangaroo 算法是一种通用的离散对数算法，旨在：当结果位于已知的小区间内时，计算离散对数。它适用于椭圆曲线和有限域的离散对数。我们将在示例中使用有限域离散对数，但算法在椭圆曲线中是相同的。

6.3.1 已知 Diffie-Hellman 密钥指数的最高有效位

问题设定。 使用与 6.1 节中相同的有限域表示法，令 $A$ 为 Diffie-Hellman 公钥， $p$ 为素数模， $g$ 为模 $p$ 的 $q$ 阶乘法群生成元。这些值都是公开的，因此我们假设它们是已知的。假设我们已经获得了密钥指数 $a$ 的最高有效位的连续分数，我们希望恢复 $a$ 的未知位来获得密钥。

图 15：已知密钥指数的最高有效位，恢复 Diffie-Hellman 共享密钥。

换句话说，令 $a=m+r$ ，其中：对于某些已知整数 $m',l$ 有 $m=2^lm'$ ，并且 $0\leq{r}<2$ 未知。令 $w$ 为包含 $r$ 的区间的宽度：这里我们有 $w = 2^l$ 。

具体例子，令 $p=\rm0xfef3$ 是16位的素数， $g=3$ 是模 $p$ 的阶为 $q=(p-1)/2={\rm0x7f79}$ 的乘法群生成元。Diffie-Hellman 的一个公钥为 $A={\rm0xa163}$ ，我们知道密钥指数 $a$ 的最高有效位，但它的最低8位未知，记作 $m={\rm0x1400},l=8,r<2^8$ 。

进行伪随机过程。 我们定义一个在模 $p$ 的乘法群下，通过在 $[0,\sqrt{w}]$ 中的指数选择一组随机步长，遍历 $s_0,s_1,\dots,s_i,\dots$ （及其相关的已知指数）的伪随机过程。在我们的例子中，伪随机步长为 $(1,3,7,10)$ 。

这是为运行我们的简单示例计算，而生成的小样本伪随机过程。伪随机过程中的每一步都由前一个值 $0\leq{s_i}<p$ 确定。

我们运行两次随机过程，第一次叫“the tame kangaroo”，从要搜索的指数区间的中间开始，即 $s_0=g^{m+[\frac{w}{2}]}\pmod{p}$ 。在示例中，我们有 $m={\rm0x1400},w=2^8=256$ ，因此 the tame kangaroo 从 $s_0=g^{\rm0x1480}\pmod{p={\rm0x9581}}$ 开始。我们沿着这条确定的伪随机路线走 $\sqrt{w}$ 步，并将 $s_i$ 和指数 $x_i$ 的值一起存储，用于得到 $g^{x_i}\equiv{s_i}\pmod{p}$ 。

第二次随机过程叫 “wild kangaroo”。它从目标 $s_0'=A={\rm0xa163}$ 开始，并沿着和上面一样的路线进行计算。我们并不知道私钥指数 $a$ 但是对于每一步过程，我们知道 $s_i'=Ag^{x_i'}=g^{a+x_i'}\pmod{p}$ 。我们沿着这条确定路线至多走 $\sqrt{w}$ 步。

如果某个时刻，“wild kangaroo” 和 “the tame kangaroo” 的路径相交，那么我们就完成了计算并且可以得到结果了。

计算离散对数。 我们知道对于 “the tame kangaroo” 的路径上的 $s_i$ 和对于 “wild kangaroo” 的路径上的 $s_j'$ ，有 $s_i=s_j'$ 。因此

在实例中，两条路线交汇于 $g^{\rm0x1497}$ 和 $g^{a+{\rm0x36}}$ ，因此计算得到 $a={\rm0x1461}$ 并验证 $g^{\rm0x1461}\equiv{\rm0xa163}\pmod{p}$ 。

更详细的阐述。 Pollard 在 [Pol78] 中给出了该算法的原始版本。 Teske 在 [Tes00] 中给出了另一种随机过程，理论上更有优势，但在实际中，似乎并没有表现出明显的优势。

我们希望算法在 $O(\sqrt{w})$ 步内完成碰撞；因此，该算法需要 $O(\sqrt{w})$ 的时间，计算宽度为 $w$ 的区间中的离散对数。因此原则上来说，普通的密码分析员应该能计算 64 到 80 位之间的离散对数，而有更多资源的人可以计算比这略多一点的离散对数。

为了将其扩展到更多位，需要进行一些修改。首先，使用具有更多细分的随机过程：32 是常用值。其次，van Oorschot 和 Wiener [OW99] 说明了如何使用区分点的方法，并行化 kangaroo 算法。这种方法背后的思想是：存储所有 “the tame kangaroo” 的路径需要太多内存。相反，存储某些具有特殊性质（例如以一定数量的零开头）的值的子集，效果更好。于是算法会运行许多 “the tame kangaroo” 和 “wild kangaroo” 的过程，将特殊点存储在数据库中。当“the tame kangaroo” 和 “wild kangaroo” 到达同一特殊点时，算法结束。

椭圆曲线。 该算法同样适用于 ECDLP 。椭圆曲线的反转性让算法复杂度提高 $\sqrt2$ 。由于点 $P$ 和 $-P$ 的 x 坐标相同，因此可以对关系 $P ∼ ±P$ 的等价类运行伪随机过程。

6.3.2 未知 Diffie-Hellman 密钥指数的最高有效位

图 16：已知密钥指数的最低有效位，恢复 Diffie-Hellman 共享密钥

扩展 kangaroo 方法来求解指数的未知最高有效位很简单。和之前一样，我们已知 $A=g^a\pmod{p}$ ，希望求出未知的 $a$ 。在最高有效位未知的情况下，有 $m$ 使得对于满足 $0\leq{r}<w$ 的未知量 $r$ ，有等式 $a=m+2^lr$ 。偏移量 $l$ 已知。我么可以在 $A'=g^{2^{-l}}A=g^{2^{-l}+m+2^lr}\pmod{p}$ 上运行 kangaroo 算法，来对之前的问题归化。

6.3.3 开放问题：未知 Diffie-Hellman 密钥指数的多个块

图 17：使用密钥指数的多个未知位块，恢复 Diffie-Hellman 共享密钥。

在实际中，使用多个未知块恢复 Diffie-Hellman 密钥，仍然是一个开放问题。理论上，在这种特殊情况下，可以使用离散对数问题的多维变体寻找密钥。后者将一个区间中的离散对数问题推广到多个区间的情况，更多细节参见 [Rup10, Chapter 6]。在 [Rup10] 中，Ruprai 分析了小维度的多维离散对数问题。当维度大于 5 时，这种方法似乎会遇到多维伪随机过程的边界问题，这说明这种方法可能不会扩展到恢复 Diffie-Hellman 指数的多个未知块的情况。

7 总结

这篇文章总结了流行的公钥密码算法已知其部分信息的密钥恢复方法。我们重点研究了使用最广泛的非对称算法：RSA、(EC)DSA 和 Diffie-Hellman。这些算法来自于各种侧信道攻击。

虽然在某些情况下，密钥恢复算法的存在可能会导致某个特定漏洞被利用，但是需要注意的是，不应该把这些利用密钥恢复攻击的有效方法，应用于指导对策。相反，实现应该努力为所有加密步骤，提供完全恒定的时间，以防止侧信道攻击。

译者总结

这篇文章的大部分精力都放在了通过格来恢复密钥的方法，格构造基本都是 Coppersmith 方法及它的多元扩展，也详细介绍了通过两种算法恢复密钥的方法。文章涵盖内容可以说是相当全面了，基本总结了当下常见的格攻击方式，不论是对于CTF中密码学的进阶学习，还是单纯的密码研究，都有很大的启发性，我本人也从这篇文章学到了许多知识，获取了一些做题、出题的灵感。

8 致谢

Pierrick Gaudry、Daniel Genkin 和 Yuval Yarom 对这项工作的早期版本做出了重大贡献。同时我们感谢 Akira Takahashi 的帮助。这项工作由美国国家科学基金会资助，资助号为：1513671 ，1651344。

参考文献


[ANT+20]	Diego F. Aranha, Felipe Rodrigues Novaes, Akira Takahashi, Mehdi Tibouchi, and Yuval Yarom. LadderLeak: Breaking ECDSA with less than one bit of nonce leakage. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 20, pages 225–242. ACM Press, November 2020.
[AS08]	Onur Acii¸cmez and Werner Schindler. A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on OpenSSL. In Tal Malkin, editor, CT-RSA 2008, volume 4964 of LNCS, pages 256–273. Springer, Heidelberg, April 2008.
[ASK07]	Onur Acii¸cmez, Werner Schindler, and C¸ etin Kaya Ko¸c. Cache based remote timing attack on the AES. In Masayuki Abe, editor, CT-RSA 2007, volume 4377 of LNCS, pages 271–286. Springer, Heidelberg, February 2007.
[BBG+17]	Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal, and Yuval Yarom. Sliding right into disaster: Leftto-right sliding windows leak. In Wieland Fischer and Naofumi Homma, editors, CHES 2017, volume 10529 of LNCS, pages 555– 576. Springer, Heidelberg, September 2017.
[BCC+13]	Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange, and Nicko van Someren. Factoring RSA keys from certified smart cards: Coppersmith in the wild. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, pages 341–360. Springer, Heidelberg, December 2013.
[Ber05]	Daniel J. Bernstein. Cache-timing attacks on AES, 2005.
[Ble98]	Daniel Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In Hugo Krawczyk, editor, CRYPTO’98, volume 1462 of LNCS, pages 1– 12. Springer, Heidelberg, August 1998.
[BM03]	Johannes Bl¨omer and Alexander May. New partial key exposure attacks on RSA. In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, pages 27–43. Springer, Heidelberg, August 2003.
[Bon98]	Dan Boneh. The decision Diffie-Hellman problem. In Third Algorithmic Number Theory Symposium (ANTS), volume 1423 of LNCS. Springer, Heidelberg, 1998. Invited paper.
[Boo51]	Andrew D. Booth. A signed binary mutiplication technique. Q. J. Mech. Appl. Math., 4(2):236–240, January 1951.
[BR95]	Mihir Bellare and Phillip Rogaway. Optimal asymmetric encryption. In Alfredo De Santis, editor, EUROCRYPT’94, volume 950 of LNCS, pages 92–111. Springer, Heidelberg, May 1995.
[BV96]	Dan Boneh and Ramarathnam Venkatesan. Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In Neal Koblitz, editor, CRYPTO’96, volume 1109 of LNCS, pages 129–142. Springer, Heidelberg, August 1996.
[BvSY14]	Naomi Benger, Joop van de Pol, Nigel P. Smart, and Yuval Yarom. “ooh aah... just a little bit”: A small amount of side channel can go a long way. In Lejla Batina and Matthew Robshaw, editors, CHES 2014, volume 8731 of LNCS, pages 75–92. Springer, Heidelberg, September 2014.
[Cop96]	Don Coppersmith. Finding a small root of a bivariate integer equation; factoring with high bits known. In Ueli M. Maurer, editor, EUROCRYPT’96, volume 1070 of LNCS, pages 178–189. Springer, Heidelberg, May 1996.
[DDME+18]	Fergus Dall, Gabrielle De Micheli, Thomas Eisenbarth, Daniel Genkin, Nadia Heninger, Ahmad Moghimi, and Yuval Yarom. Cachequote: Efficiently recovering long-term secrets of sgx epid via cache attacks. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(2):171–191, May 2018.
[DH76]	Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Trans. Information Theory, 22(6):644–654, 1976.
[DHMP13]	Elke De Mulder, Michael Hutter, Mark E. Marson, and Peter Pearson. Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA. In Guido Bertoni and Jean-S´ebastien Coron, editors, CHES 2013, volume 8086 of LNCS, pages 435–452. Springer, Heidelberg, August 2013.
[DPP20]	Gabrielle De Micheli, R´emi Piau, and C´ecile Pierrot. A tale of three signatures: Practical attack of ECDSA with wNAF. In Abderrahmane Nitaj and Amr M. Youssef, editors, AFRICACRYPT 20, volume 12174 of LNCS, pages 361–381. Springer, Heidelberg, July 2020.
[EG85]	Taher El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Information Theory, 31(4):469–472, 1985.
[EL85]	Wim Van Eck and Neher Laborato. Electromagnetic radiation from video display units: An eavesdropping risk? Computers and Security, 4:269–286, 1985.
[FH08]	J. Ferrigno and M. Hlavac. When AES blinks: Introducing optical side channel. Information Security, IET, 2:94 – 98, 10 2008.
[FWC16]	Shuqin Fan, Wenbo Wang, and Qingfeng Cheng. Attacking OpenSSL implementation of ECDSA with a few signatures. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 1505–1515. ACM Press, October 2016.
[Gar59]	Harvey L. Garner. The residue number system. IRE Trans. Electron. Computers, EC-8(2):140–147, Jun 1959.
[Gor98]	Daniel M. Gordon. A survey of fast exponentiation methods. J. Algorithms, 27(1):129–146, April 1998.
[GST14]	Daniel Genkin, Adi Shamir, and Eran Tromer. RSA key extraction via low-bandwidth acoustic cryptanalysis. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 444–461. Springer, Heidelberg, August 2014.
[HG]	Nicholas A Howgrave-Graham. Computational Mathematics Inspired by RSA. PhD thesis
[HG97]	Nicholas Howgrave-Graham. Finding small roots of univariate modular equations revisited. In Michael Darnell, editor, Crytography and Coding, pages 131–142, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg.
[HG01]	Nick Howgrave-Graham. Approximate integer common divisors. pages 51–66, 2001.
[HM08]	Mathias Herrmann and Alexander May. Solving linear equations modulo divisors: On factoring given any bits. In Josef Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS, pages 406–424. Springer, Heidelberg, December 2008.
[HR07]	Martin Hlav´ac and Tom´as Rosa. Extended hidden number problem and its cryptanalytic applications. In Eli Biham and Amr M. Youssef, editors, SAC 2006, volume 4356 of LNCS, pages 114–133. Springer, Heidelberg, August 2007.
[HS09]	Nadia Heninger and Hovav Shacham. Reconstructing RSA private keys from random key bits. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 1–17. Springer, Heidelberg, August 2009.
[HS14]	Michael Hutter and J¨orn-Marc Schmidt. The temperature side channel and heating fault attacks. Cryptology ePrint Archive, Report 2014/190, 2014.
[HSH+08]	J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W. Felten. Lest we remember: Cold boot attacks on encryption keys. In Paul C. van Oorschot, editor, USENIX Security 2008, pages 45–60. USENIX Association, July / August 2008.
[IGA+15]	Mehmet Sinan Inci, Berk G¨ulmezoglu, Gorka Irazoqui Apecechea, Thomas Eisenbarth, and Berk Sunar. Seriously, get off my cloud! cross-vm rsa key recovery in a public cloud. IACR Cryptology ePrint Archive, 2015:898, 2015.
[KHF+19]	Paul Kocher, Jann Horn, Anders Fogh, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, Michael Schwarz, and Yuval Yarom. Spectre attacks: Exploiting speculative execution. In 2019 IEEE Symposium on Security and Privacy, pages 1–19. IEEE Computer Society Press, May 2019.
[KJJ99]	Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In Michael J. Wiener, editor, CRYPTO’99, volume 1666 of LNCS, pages 388–397. Springer, Heidelberg, August 1999.
[KJJR11]	Paul Kocher, Joshua Jaffe, Benjamin Jun, and Pankaj Rohatgi. Introduction to differential power analysis. Journal of Cryptographic Engineering, 1(1):5–27, Apr 2011.
[Koc96]	Paul C. Kocher. Timing attacks on implementations of DiffieHellman, RSA, DSS, and other systems. In Neal Koblitz, editor, CRYPTO’96, volume 1109 of LNCS, pages 104–113. Springer, Heidelberg, August 1996.
[LLL82]	Arjen Klaas Lenstra, Hendrik Willem Lenstra, and L´aszl´o Lov´asz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
[LSG+18]	Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Anders Fogh, Jann Horn, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. Meltdown: Reading kernel memory from user space. In William Enck and Adrienne Porter Felt, editors, USENIX Security 2018, pages 973–990. USENIX Association, August 2018.
[May10]	Alexander May. Using LLL-reduction for solving RSA and factorization problems. ISC, pages 315–348. Springer, Heidelberg, 2010.
[MBA+20]	Robert Merget, Marcus Brinkmann, Nimrod Aviram, Juraj Somorovsky, Johannes Mittmann, and J org Schwenk. Raccoon attack: Finding and exploiting most-significant-bit-oracles in tlsdh(e). 2020.
[Möl03]	Bodo Möller. Improved techniques for fast exponentiation. In Pil Joong Lee and Chae Hoon Lim, editors, ICISC 02, volume 2587 of LNCS, pages 298–312. Springer, Heidelberg, November 2003.
[MVH+20]	Daniel Moghimi, Jo Van Bulck, Nadia Heninger, Frank Piessens, and Berk Sunar. CopyCat: Controlled instruction-level attacks on enclaves. In Srdjan Capkun and Franziska Roesner, editors, USENIX Security 2020, pages 469–486. USENIX Association, August 2020.
[NIS13]	National Institute of Standards and Technology. Digital Signature Standard (DSS), 2013.
[NS02]	Phong Q. Nguyen and Igor E. Shparlinski. The insecurity of the Digital Signature Algorithm with partially known nonces. J. Cryptology, 15(3):151–176, 2002.
[NS03]	Phong Q. Nguyen and Igor E. Shparlinski. The insecurity of the Elliptic Curve Digital Signature Algorithm with partially known nonces. Des. Codes Cryptography, 30(2):201–217, 2003.
[NS06]	Phong Nguyen and Damien Stehl´e. LLL on the average. In Proceedings of the 7th International Conference on Algorithmic Number Theory, ANTS’06, pages 238–256, Berlin, Heidelberg, 2006. Springer-Verlag.
[OST06]	Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks and countermeasures: The case of AES. In David Pointcheval, editor, CT-RSA 2006, volume 3860 of LNCS, pages 1–20. Springer, Heidelberg, February 2006.
[OW99]	Paul C. Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications. J. Cryptol., 12(1):1–28, January 1999.
[Pag02]	D. Page. Theoretical use of cache memory as a cryptanalytic sidechannel. Cryptology ePrint Archive, Report 2002/169, 2002.
[Per05]	Colin Percival. Cache missing for fun and profit. In BSDCon 2005, Ottawa, CA, 2005.
[Pol78]	John M. Pollard. Monte Carlo methods for index computation mod p. Mathematics of Computation, 32:918–924, 1978.
[PPS12]	Kenneth G. Paterson, Antigoni Polychroniadou, and Dale L. Sibborn. A coding-theoretic approach to recovering noisy RSA keys. In Xiaoyun Wang and Kazue Sako, editors, ASIACRYPT 2012, volume 7658 of LNCS, pages 386–403. Springer, Heidelberg, December 2012.
[QS01]	Jean-Jacques Quisquater and David Samyde. Electromagnetic analysis (ema): Measures and counter-measures for smart cards. In Proceedings of the International Conference on Research in Smart Cards: Smart Card Programming and Security, E-SMART ’01, pages 200–210, London, UK, UK, 2001. Springer-Verlag.
[Rup10]	Raminder Singh Ruprai. Improvements to the Gaudry-Schost Algorithm for Multidimensional discrete logarithm problems and Applications. PhD thesis, 2010.
[Sch87]	Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53(2-3):201– 224, 1987.
[Sch90]	Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Gilles Brassard, editor, CRYPTO’89, volume 435 of LNCS, pages 239–252. Springer, Heidelberg, August 1990.
[SE94]	Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming, 66(2):181–199, 1994.
[Tes00]	Edlyn Teske. On random walks for pollard’s rho method. Mathematics of Computation, 70:809–825, 2000.
[TSS+03]	Yukiyasu Tsunoo, Teruo Saito, Tomoyasu Suzaki, Maki Shigeri, and Hiroshi Miyauchi. Cryptanalysis of DES implemented on computers with cache. In Colin D. Walter, C¸ etin Kaya Ko¸c, and Christof Paar, editors, CHES 2003, volume 2779 of LNCS, pages 62–76. Springer, Heidelberg, September 2003.
[TTA18]	Akira Takahashi, Mehdi Tibouchi, and Masayuki Abe. New Bleichenbacher records: Fault attacks on qDSA signatures. IACR TCHES, 2018(3):331–371, 2018.
[TTMH02]	Yukiyasu Tsunoo, Etsuko Tsujihara, Kazuhiko Minematsu, and Hiroshi Hiyauchi. Cryptanalysis of block ciphers implemented on computers with cache. In International Symposium on Information Theory and Its Applications, Xi’an, CN, October 2002.
[YGH16]	Yuval Yarom, Daniel Genkin, and Nadia Heninger. CacheBleed: A timing attack on OpenSSL constant time RSA. In Benedikt Gierlichs and Axel Y. Poschmann, editors, CHES 2016, volume 9813 of LNCS, pages 346–367. Springer, Heidelberg, August 2016.