Partial Key Exposure Attack

Last updated Oct 23, 2022 Edit Source

# 説明

秘密鍵を部分的に知っていさえいれば、Coppersmith Method を用いて解けてしまう。 $n$ を $N$ のビット数とする。

# $p, q$ のどちらかを $n/4$ ビット程度知っているとき

$$ \begin{aligned} f(x) &= p_{upper} + x & \pmod p \\ f(x) &= 2^{k}x + p_{lower} & \pmod p \\ f(x,y) &= 2^kx + p_{mid} + y & \pmod p \\ \end{aligned} $$

# 平文 $m$ のビットを $(1-1/e)n$ 程度知っているとき

$$ \begin{aligned} f(x) &= (m_{upper} + x)^e - c & \pmod N \\ f(x) &= (2^kx + m_{lower})^e - c & \pmod N \\ f(x,y) &= (2^kx + m_{mid} + y)^e - c & \pmod N \\ \end{aligned} $$

# $d$ を $n/4$ ビット程度知っているとき

$e$ が総当り出来るくらい小さいときに $d$ を $n/4$ ビットだけ知っていれば元の $d$ を構成できる。大体の場合は $e = 65537$ であるから十分可能である。$d < \phi(N)$ より $0 < k \leq e$ となり、この $k$ に対して総当たりする。

上位ビットの場合 $d$ と $p, q$ の関係式を立てる。

$$ \begin{aligned} ed &= 1 & \pmod{\phi(N)} \\ ed &= 1 + k(N - p - q + 1) \\ d &= \frac{kN}{e} - \frac{k(p+q-1) -1}{e} \\ e(d_{upper} + x) &= - k (y - 1) + 1 & \pmod N \\ \end{aligned} $$

第三式について $p + q \approx \sqrt{N}$ より第二項は上位ビットに関連する情報を持たない。これより第一項の $k$ について総当りして上位ビットと一致する $k$ を見つければよい。すると第4式に対し Multivariate CopperSmith を用いて、$d$ がわかる。

下位ビットの場合 $d$ の下位ビットから $k$ について総当りして $p$ の下位ビットを求める。すると先程の問題に帰着できて $p$ がわかり $d$ がわかる。

$$ \begin{aligned} ed &= 1 + k\left(N - p - \frac{N}{p} + 1\right) \\ edp &= p + kp(N - p + 1) - kN & \pmod {2^{n/4}} \\ \end{aligned} $$

# CRTの秘密鍵 $d$ のビットを $n/4$ 程度知っているとき

上と同様にして解けます。

$$ \begin{aligned} ed_p &= 1 & \pmod{p-1} \\ ed_p &= 1 + k_p(p − 1) \\ \end{aligned} $$

# 実装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 3

beta = 0.5
epsilon = beta^2/7

pbits = p.nbits()
kbits = floor(n.nbits() * (beta^2 - epsilon))
# p upper
pbar = p & (2^pbits - 2^kbits)

print(f"upper {pbits - kbits} bits (of {pbits} bits) is given")

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar

print(p)
x0 = f.small_roots(X=2^kbits, beta=0.3)[0]
print(x0 + pbar)

# 使用例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

	# edx - kx(n-x+1) + kn = x mod 2^k
	# (ed - 1)x - kx(n-x+1) + kn = 0 mod 2^k
    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p


if __name__ == '__main__':
    n = 0x00bef498e6eb2cffe71312da47ab89d2c47db7438ea2cfa992ddddbc2a01978001fc51e286e6ebf028396cdb8b3323c60e6b9d50cd84187cf7f48e3875a2f0890f70b02333ad89db2923863ce146562286f63fb0a1d0198e3a6862ba5ac12e85a5c6d0d27cb1c81bdf69cc5bc95b8001a2f744517f9437b4ddd5a076fc0e9a5de1a7a268c40f31aa29e8dc27c0b3a182299ca7a9335b4bd4585452f6107c238e486c98dd73a5f9862e9e80b152f53381c72f897107551c281259ac3ee32c4b4f46cc03127d1bf699acd0266f3c6729253c70da0c69b1560fa172735709866b375b6eba294e1ce8b46fba798ba380080b4bf9603998cac199d9cd46e30ae8da9e7f
    e = 3
    d = 0x7f4dbb449cc8aa9a0cb73c2fc7b1372da924d7b46c8a710c93e9281c010faaabfd8bec59ef47f5702648925cccc284099d138b33ad65a8a54db425a3c1f5b0b4f5cac22273b13cc617aed340d98ec1af4ed5206be011097c459726e72b7459192f35e1a8768567ea46883d30e7aaabc1fa2d8baa62cfcde93915a4a809bc3e9547bb07e1ecca16e51078312e89f0561e31b55db8b0ea5bc87a6ca7464a3d7c28a68c60e2ba88fe6a7d2b300d723e549910a987da89fc0a1c0de197a3d62c501b1f0e819891b1c32a0d6c233f2a285df87bb9e5c6c72d983ff3e706696bba639f573f9c3646968f02f3a615a438e20bb7c38d53621079f2899547a95350f3abeb

    beta = 0.5
    epsilon = beta^2/7

    nbits = n.nbits()
    kbits = floor(nbits*(beta^2+epsilon))
    d0 = d & (2^kbits-1)
    print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    print d
    print inverse_mod(e, (p-1)*(q-1))

🪴 あやめHex