kurenaif Valentine Problems - redundant_rsa

kurenaifさんがCryptoの問題をプレゼントしてくれました。ちょっと忙しかったので今から解きます。一応既に公式writeupが出ているはずですので、そちらを見た方が分かりやすい説も。

問題概要

問題リンク

problem.py

from Crypto.Util.number import *
from flag import *
import secrets


leftDummy = secrets.token_bytes((500 - bytes_to_long(flag).bit_length()) // 8 // 2)
rightDummy = secrets.token_bytes((500 - bytes_to_long(flag).bit_length()) // 8 // 2)

# format: RANDOM_DATAkurenaifCTF{*}RANDOM_DATA
# please Extract kurenaifCTF{*} by manual work :)
m = bytes_to_long(leftDummy + flag + rightDummy)


p = getPrime(256)
q = getPrime(256)
N = p*q

# guarantee and hint 
assert GCD(m*m % N, N) == 1
assert GCD(m*m*m % N, N) == 1

# In CTF, 3 is sometimes used, but in general RSA, 65537 is used.
print("N =", N)
print("c3 =", pow(m, 3, N))
print("c65537 =", pow(m, 65537, N))

問題解説

RSAの解説についてはp_p_rsaの方で済ませたので、問題の方に早速行きます。

着眼点

プログラム自体はシンプルで、$\gcd(m^2\%N, N) = \gcd(m^3\%N, N) = 1$が保証された状態で$m^3$と$m^{65537}$が与えられます。気にすべきは後者の「$c$が複数与えられている」という点です。

ところで、$65537 = 3 * 21845 + 2$です。ということは$c_{65535}={c_{3}}^{21845}$として$c_2=c_{65537}\times {c_{65535}}^{-1}$であると考えられます。同様の考え方で$m=c_3\times{c_2}^{-1}$ですね。

これだけなんですが、実際に計算する際においては$\mod N$で計算する必要があります。$c_65535$や$c_2$が逆元を持つことを証明するために上の前提条件があります。というのも、逆元は拡張ユークリッドの互除法を用いて求めるのですが、$\gcd$が1以外になると逆元が求まりません。

solve.py

from math import gcd
N = 8208175638972200577186038102634114258848486365767463332763957381946985480397227219800325703361508208728778216773973313756762762324416016301819271949512427
c3 = 510199524103978915755062119293765889950938959100085136114101960072728304594090942964306874023123457091885387418124063977610496306587745044542739034336862
c65537 = 4673531855283872496727093452348048121242854682829577660566947295656149440028839210065857595110277181842297946378296819272562912619683355333762343087859186

# c3 ^ 21845 = c65535
# c2 * c65535 = c65537 => c2 = c65537 * inv(c65535)
# m = c1 = c3 * inv(c2)

def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a % b)
        y -= (a // b)*x
        return d, x, y
    return a, 1, 0

def inv(x):
    assert gcd(x, N) == 1
    _, res, _ = extgcd(x, N)
    return (res + N) % N

c65535 = pow(c3, 65537 // 3, N)
c2 = (c65537 * inv(c65535)) % N
m = (c3 * inv(c2)) % N
print(m.to_bytes(96, "big"))