p - 1 ≡ 0 (mod e) のときの RSA 復号方法

Mon Oct 26 2020

    昨日参加した Hack.lu CTF 2020 で解けなかった暗号問題 Bad Primes の復習となります。CTFtime に載っている writeup を参考にしました。この writeup を見ると Stack Exchange を引用しています。

    問題設定

    基本的には普通の RSA と一緒です。ただし公開鍵 n(=pq)n (=pq) を計算するための素数 p,qp, q は既知とします。また、 e=65537e = 65537 です。 このとき、ある平文 mm を暗号化した cmemodnc \equiv m^e \mod n が与えられており、それらを使って mm を復号するという問題です。

    従来の RSA と異なるのは、本来ですと gcd(e,ϕ)=1\gcd(e, \phi) = 1 となるような素数 p,qp, q を用いるのですが、この問題では p10modep-1 \equiv 0 \mod e となっており、 gcd(e,ϕ)=e\gcd(e, \phi) = e です。すると ed1modϕed \equiv 1 \mod \phi となる dd が存在せず、 RSA での復号方法 mcdmodnm \equiv c^d \mod n は成立しません。これを復号するにはどうすればいいでしょうか。

    実は次のことが成立しているとき、 mm の候補を ee 個に絞ることができます。

    • ee は素数
    • p10modep-1 \equiv 0 \mod e かつ p1≢0mode2p - 1 \not\equiv 0 \mod e^2
    • q1≢0modeq-1 \not\equiv 0 \mod e

    復号方法

    • λ=(p1)(q1)/gcd(p1,q1)=lcm(p1,q1)\lambda = (p-1)(q-1)/\gcd(p-1, q-1) = \mathrm{lcm}(p-1, q-1)
    • Lkλ/emodnL \equiv k^{\lambda/e} \mod n (kk は位数が λ\lambda となる任意の整数)
    • de1modλ/ed \equiv e^{-1} \mod \lambda/e

    としたとき、 cdLimodnc^d L^i \mod n (0i<e0\le i < e) が mm の候補となります。

    証明

    まず、 mcdLimodnm' \equiv c^d L^i \mod n で計算される mm'(m)ec(m')^e \equiv c を満たすことを示します。 証明には カーマイケルの定理 を使います。カーマイケルの定理より、 λ(n)=lcm(λ(p),λ(q))=lcm(p1,q1)\lambda(n) = \mathrm{lcm}(\lambda(p), \lambda(q)) = \mathrm{lcm}(p-1, q-1) となる λ(n)\lambda(n) を用いて、 aλ(n)1modna^{\lambda(n)} \equiv 1 \mod n (gcd(a,n)=1\gcd(a, n) = 1) となります。この λ(n)\lambda(n) が「復号方法」で定義した λ\lambda となります。 dd は法を λ/e\lambda/e としたときの ee の逆元という定義ですが、これは lcm(p1,q1)\mathrm{lcm}(p-1, q-1)ee でちょうど1回しか割り切れないことから存在が示せます。 実際に cdLic^d L^i で求まる値を mm' として計算すると、

    m=cdLimedk(λ/e)imodn=m(λ/e)x+1k(λ/e)i=m×(mxki)λ/e\begin{aligned} m' &= c^d L^i \\ &\equiv m^{ed} k^{(\lambda/e)i} \mod n\\ &= m^{(\lambda/e)x + 1} k^{(\lambda/e)i} \\ &= m \times (m^x k^i)^{\lambda/e} \end{aligned}

    となります。これを ee 乗すると、 (m)eme(mxki)λme(m')^e \equiv m^e (m^x k^i)^{\lambda} \equiv m^e となるため、このようにして求まる mm'(m)ec(m')^e \equiv c を満たします。

    次に iji \ne j のとき LiLjL^i \ne L^j であることと、 Le1L^e \equiv 1を示します。 これ の命題9.11 (1) を使います。再掲すると、mm を2以上の自然数、aamm と互いに素な整数、 ss を法 mm に関する aa の位数としたとき、 s=uvs = uv ならば法 mm に関する aua^u の位数は vv となります。 ke(λ/e)k^{e(\lambda/e)} に上記命題を適用すると、 kλ/e=Lk^{\lambda/e} = L の位数は ee となります。位数の定義により、示せました。

    以上をもって mcdLimodnm' \equiv c^d L^i \mod n について 0i<e0\le i < e をそれぞれ計算すれば、 ee 通りの解が求まります。今 me=cm^e = c となる mm はたかだかee個しかないため、この方法で計算される mm' のどれかが mm となります。

    実装

    Hack.lu CTF 2020 の Bad Primes について解いてみました。

    from Crypto.Util.number import long_to_bytes, inverse, GCD
    
    n = 3283820208958447696987943374117448908009765357285654693385347327161990683145362435055078968569512096812028089118865534433123727617331619214412173257331161
    p = 34387544593670505224894952205499074005031928791959611454481093888481277920639
    q = 95494466027181231798633086231116363926111790946014452380632032637864163116199
    e = 65537
    c = 2152534604028570372634288477962037445130495144236447333908131330331177601915631781056255815304219841064038378099612028528380520661613873180982330559507116
    assert p * q == n
    
    _lambda = (p - 1) * (q - 1) // GCD(p - 1, q - 1)
    assert _lambda % e == 0
    assert _lambda // e % e != 0
    L = pow(2, _lambda // e, n)
    assert L > 1
    d = inverse(e, _lambda // e)
    assert e * d % (_lambda // e) == 1
    
    for i in range(e):
        tmp_flag = long_to_bytes(pow(c, d, n) * pow(L, i, n) % n)
        if b"flag" in tmp_flag:
            print(tmp_flag)

    flag{thanks_so_much_for_helping_me_with_these_primitive_primes}