TL;DR

  • 公開鍵N=pqN=pqのppがddとなっているRSA
  • 暗号文をNN乗することで、qqを法としてフラグと合同になる
  • というわけで法の約数を更に法として解を求めるタイプの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=pqN = pqとなるp,qp,qに対して、d=qd = qとなっている。

フラグをmmとおくと、c≡memod  Nc \equiv m^e \mod Nであるから、両辺NN乗するとcN≡mepq≡mqmod  Nc^N \equiv m^{epq} \equiv m^q \mod Nとなる。

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

というわけでNNの約数を法とした合同方程式の解を求めるCoppersmith's Attackによってf(x)=cN−xmod  qf(x) = c^N - x \mod qの解を求めるとフラグがqq以下であるなら求めることが出来る。small_roots()のパラメータとして、q≈2813>N3/4q \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