TL;DR

  • 公開鍵$N=pq$の$p$が$d$となっているRSA
  • 暗号文を$N$乗することで、$q$を法としてフラグと合同になる
  • というわけで法の約数を更に法として解を求めるタイプのCoppersmith's Attackを使う

Prerequisite

  • フェルマーの小定理
  • Coppersmith's Attack

Writeup

次のスクリプトとその実行結果が与えられる

from Crypto.Util.number import *

N = 1024
P = 211
p = getPrime(P)
q = getPrime(N-P)
n = p*q
print(n.bit_length())
d = p
e = inverse(d, (p-1)*(q-1))
flag = bytes_to_long(open('flag','rb').read())

print(n)
print(e)
print(pow(flag, e, n))

$N = pq$となる$p,q$に対して、$d = q$となっている。

フラグを$m$とおくと、$c \equiv m^e \mod N$であるから、両辺$N$乗すると$c^N \equiv m^{epq} \equiv m^q \mod N$となる。

ここで、$q$は$N$の約数なので法を$q$として、フェルマーの小定理を用いると$c^N \equiv m^q \equiv m \mod q$も成り立つ。

というわけで$N$の約数を法とした合同方程式の解を求めるCoppersmith's Attackによって$f(x) = c^N - x \mod q$の解を求めるとフラグが$q$以下であるなら求めることが出来る。small_roots()のパラメータとして、$q \approx 2^{813} \gt N^{3/4}$であるから、beta=0.75を設定した。

Code

n = 73105772487291349396254686006336120330504972930577005514215080357374112681944087577351379895224746578654018931799727417401425288595445982938270373091627341969888521509691373957711162258987876168607165960620322264335724067238920761042033944418867358083783317156429326797580005138985469248465425537931352359757
e = 4537482391838140758438394964043410950504913123892269886065999941390882950665896428937682918187777255481111874006714423664290939580653075257588603498124366669194458116324464062487897262881136123858890202346251370203490050314565294751740805575602781718282190046613532413038947173662685728922451632009556797931
c = 14558936777299241791239306943800914301296723857812043136710252309211457210786844069103093229876701608756952780774067174377636161903673229776614350695222134040119114881027349864098519027057618922872932074441000483969146246381640236171500856974180238934543370727793393492372475990330143750179123498797867932379

PR.<x> = PolynomialRing(Zmod(n))

f = pow(c, n, n) - x
f = f.monic()

res = f.small_roots(beta=0.75, epsilon=1/20)
print(res)

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(res[0]))

Flag

hitcon{~~so_triviAl_coPper5mitH~~}

Resources