はじめに

zer0pts CTFにKUDoSというチームで参加して、951チーム中23位でした。

チーム全体では1633ptで、自分はcryptoの4問を解いて570pt入れました。

今年度初めて得点を入れた(というか本格的に何時間も割いた)CTFです。

zer0ptsのチームメンバーもTwitterで何人か把握¹していて、その方々が開催するとなれば参加必至です。

本当に久々に参加したので実力が落ちているか心配でした²が、それ以上に解けた時の快感を思い出しました。

シンプルかつ解きごたえのある問題ばかりで、土日を溶かしてよかったと思います。この場を借りて問題、サーバ提供に感謝します。

~~いつか勝ちます。~~

自分のwriteupのスタイルとして、いきなり答えに直結するものだけでなく色々試行錯誤した跡も残すので、結構冗長です。すみません。

war(sa)mup (crypto, 102pt, 95solves)

Do you know RSA? I know.

from Crypto.Util.number import getStrongPrime, GCD
from random import randint
from flag import flag
import os

def pad(m: int, n: int):
  # PKCS#1 v1.5 maybe
  ms = m.to_bytes((m.bit_length() + 7) // 8, "big")
  ns = n.to_bytes((n.bit_length() + 7) // 8, "big")
  assert len(ms) <= len(ns) - 11

  ps = b""
  while len(ps) < len(ns) - len(ms) - 3:
    p = os.urandom(1)
    if p != b"\x00":
      ps += p
  return int.from_bytes(b"\x00\x02" + ps + b"\x00" + ms, "big")


while True:
  p = getStrongPrime(512)
  q = getStrongPrime(512)
  n = p * q
  phi = (p-1)*(q-1)
  e = 1337
  if GCD(phi, e) == 1:
    break

m = pad(int.from_bytes(flag, "big"), n)
c1 = pow(m, e, n)
c2 = pow(m // 2, e, n)

print("n =", n)
print("e =", e)
print("c1=", c1)
print("c2=", c2)

# n = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
# e = 1337
# c1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
# c2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

要約すると

flagを m=b'\x00\x02' + ('\x00'を含まないrandom) + b'\x00' + flagの形にパディング。mの長さは128 byte
公開鍵を $(N, E)$ , 秘密鍵を $(p, q)$ とするRSA暗号に対し、 $m$ および $\lfloor m/2\rfloor$ に対応する暗号文 $C_1, C_2$ が与えられる。ここで、 $\lfloor m/2\rfloor$ は床関数(あるいはGauss記号)。つまり

$C_1 = m^ E$ mod $N$

$C_2 = \left(\lfloor\frac{m}{2}\rfloor\right)^ E$ mod $N$

大文字で示した $C_1, C_2, N, E$ は既知で、 $m$ は未知です。

1番目は実は関係なくて、 $m$ さえ分かればパディングは簡単に外せます。なので実質2番目だけです。

アプローチ1

割と典型的な問題ですが、まずはじめに、RSA暗号には乗法準同型性があります。簡単に言うと、

「 $m$ に対応する暗号文 $C$ がわかれば、 $m, 2m$ を知らなくとも $2m$ に対応する暗号文 $C'$ を作成可能」

です。もちろん $2m$ じゃなく何倍でもOKです。

$C' = (2m)^ E = 2^ E \cdot m^ E = 2^ E \cdot C$

これで終わりです。 $C$ と公開鍵 $E$ だけで計算可能です。

さて、これがどう生きるかというと、一般にCTFのflagはzer0pts{hoge}のように、最後の1文字が}、ASCIIコード表でいう\x7c=125であることが多いため、高確率で $m$ は奇数であることが分かります。

不安な人のために、 $m$ が偶数である場合に矛盾することを示しておきます³。

$m$ が偶数なら、 $m/2$ は整数になるのでGauss記号は不要で、

$C_2 = \left(\frac{m}{2}\right)^ E$ mod $N$

つまり、 $C_2$ に $2^ E$ mod $N$ を乗算すると

$C_2 \cdot 2^ E = \left(\frac{m}{2}\right)^ E \cdot 2^ E = m^ E = C_1$

になるはずです。

# odd_or_even.py

N = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
E = 1337
C1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
C2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762

if C2 * pow(2, E, N) % N == C1:
  print('m is even')
else:
  print('m is odd')

結果は自分でご確認ください(当然奇数です)。

本題に戻ります。 $m$ が奇数なので、 $\lfloor m/2\rfloor = (m-1)/2$ です。これは $m=7$ など適当な奇数を代入したらわかると思います。

そのため、先ほどと同様に $C_2$ に $2^ E$ mod $N$ を乗算すると(これを $C_3$ とします)

$C_3 = C_2 \cdot 2^ E = \left(\frac{m-1}{2}\right)^ E \cdot 2^ E = (m-1)^ E$ mod $N$

です。つまり、 $m, m-1$ に対する暗号文が計算できるわけです。

ここからは、RSA暗号に対するだいたいの攻撃方法が載っているRSA暗号運用でやってはいけない n のことを参照します。

その11「上位ビットが共通する二つの平文に対する暗号文を知られてはいけない」がもろ該当します。

Franklin-Reiter Related Message Attackが適用可能

二つの平文 $m_1, m_2 = a\cdot m_1 + b$ と、それぞれの暗号文が得られるとき、 $m_1$ を導出可能

今回は $a=1, b=-1$ ですね。

アプローチ0(脱線)

さて、ここまでは似たような問題もちらほらあり、Coppersmith(上記その14参照)とかそのあたりを使うんだろうと思い、"coppersmith's attack"で検索しました(まずこの時点で雲行きが怪しい)。

すると、ももいろテクノロジーの記事がヒット。

下にスクロールすると、「Coppersmith’s Short Pad Attack & Franklin-Reiter Related Message Attack」の文字が。Franklin Reiterの文字もあります。

実は過去にこのCoppersmith + Franklin Reiterのコードをそのまま適用することで解ける問題があった⁴ので、今回もコピペでいけると思っていました。

ここで定義されている2関数short_pad_attack, related_message_attackを拝借します。

print まわりがPython2仕様になっているので少し修正してあります。

# cannot_solve.sage

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

N = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
E = 1337
C1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
C2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
C3 = (pow(2, E, N) * C2) % N

diff = short_pad_attack(C1, C3, E, N)
print("difference of two messages is %d" % diff)

m1 = related_message_attack(C1, C3, diff, E, N)
print(m1)

…全然終わらない。 $C_1, C_3$ を逆にしたりしてみましたが全く終わりません。

原因は記事内のこの部分です。

二つの暗号文について平文の上位bitが $n$ のbit数の $(1-1/e^ 2)$ 程度共通する場合、これらからそれぞれの平文を求めることができる。

本問題は $e=1337$ です。ざっくり1000と見積もっても、100万bitのうち999999bitは共通しているくらいの精度が必要です。

しかし、今回 $m$ は128byte(=1024bit)なので、 $m, m-1$ の誤差は上に比べたらめちゃくちゃ大きいです。

この方法は(記事内の例でもわかる通り) $e=3$ くらいじゃないと厳しいです。

今回の教訓ですが、

(本問の $m-1$ のように) $m_1, m_2$ の関係性が分かっている場合はFranklin Reiter (精度は $(1-1/e)$ 程度)
(記事にあるように) $m_1, m_2$ の関係性は分からないが、より一致する精度が高い場合はCoppersmith + Franklin Reiter (精度は $(1-1/e^ 2)$ 程度)

アプローチ1(再開)

脱線終わりです。あらためて、'franklin reiter'でググってみます⁵。こちらのブログがヒット。

この2関数gcd, franklinreiterを拝借します。

# solver.sage

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()

def franklinreiter(c_1, c_2, e_1, e_2, N, a, b):
    P.<X> = PolynomialRing(Zmod(N))
    g_1 = X^e_1 - c_1
    g_2 = (a*X + b)^e_2 - c_2
    # get constant term
    result = -gcd(g_1, g_2).coefficients()[0]

    return result

N = 113135121314210337963205879392132245927891839184264376753001919135175107917692925687745642532400388405294058068119159052072165971868084999879938794441059047830758789602416617241611903275905693635535414333219575299357763227902178212895661490423647330568988131820052060534245914478223222846644042189866538583089
E = 1337
C1= 89077537464844217317838714274752275745737299140754457809311043026310485657525465380612019060271624958745477080123105341040804682893638929826256518881725504468857309066477953222053834586118046524148078925441309323863670353080908506037906892365564379678072687516738199061826782744188465569562164042809701387515
C2= 18316499600532548540200088385321489533551929653850367414045951501351666430044325649693237350325761799191454032916563398349042002392547617043109953849020374952672554986583214658990393359680155263435896743098100256476711085394564818470798155739552647869415576747325109152123993105242982918456613831667423815762
C3 = (pow(2, E, N) * C2) % N

flag = franklinreiter(C1, C3, E, E, N, 1, -1)
print(int(flag).to_bytes((int(flag).bit_length() + 7) // 8, "big"))

franklinreiterの引数について少し補足しておきます。本問では $m, m-1$ の暗号化に両方 $E=1337$ を使っていましたが、Franklin Reiterは $m_1, m_2$ の関係性(つまり $a, b$ )さえ分かれば

$C_1 = m_1^ {E_1}$

$C_2 = m_2^ {E_2}$

と異なる $E$ を使っていても問題ありません。

NOT Mordell primes (crypto, 209pt, 19solves)

I found one integral point on an elliptic curve, so there's finite number of integral solutions.

This means You can pick from an finite number of primes... right?

special thanks: https://ctf.cr0wn.uk/challenges#Mordell%20primes-11

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG


p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177

E = EllipticCurve(GF(p),[a,b])

P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
Q = k*P
R = (k+1)*P

p = int(Q[0])
q = int(R[0])

assert is_prime(p)
assert is_prime(q)

e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

# N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
# c = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987

要約すると

$y^ 2=x^ 3+Ax+B$ mod $p$ 上の点 $P(X_0, Y_0)$ が与えられる
$Q=kP=(x_1, y_1), R=(k+1)P=(x_2, y_2)$ とする。ただし $(x_1, x_2)$ は素数である
$N=x_1x_2$ を計算する
公開鍵を $(N, E)$ , 秘密鍵を $(x_1, x_2)$ とするRSA暗号でflagを暗号化する

です。大文字で示した $A, B, X_0, Y_0, N, E$ および $p$ は⁶既知で、 $x_1, x_2, y_1, y_2, k$ は未知です。

アプローチ1

RSA暗号を破るには、基本的に秘密鍵を計算しないと話にならないので、どうにかして $k, x_1$ あたりを求めることになります。

最初の方針はいたって簡単です。 $k$ が小さいことに賭けて総当たりします。

# approach1.sage

p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
E = EllipticCurve(GF(p),[A,B])
X0 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980
Y0 = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991
P = E(X0, Y0)

for i in range(50000):
    x1 = int((i*P)[0])
    x2 = int(((i+1)*P)[0])
    if is_prime(x1) and is_prime(x2):
        print(i)

これで50000以下で $k$ で見つかれば…

まあ見つからないんですけどね。基本的にbrute-forceでうまくいく問題はそうありません。

アプローチ2

問題文のspecial thanksが気になります。何かしらのインスピレーションを受けた問題であるので、オリジナルの問題を見てみます。

サーバにはアクセスできなかったので、"mordell primes ctf"などでググってwriteupを検索すると、rkm0959氏の記事がヒット⁷。

オリジナルでは

mod $p$ がないので、 $k$ を大きくすればするほど爆発的に $x$ 座標が大きくなり、あっという間に $N = x_1x_2$ をオーバーしてしまう

なので、brute-forceで $k$ を求める

という方針です。

…うーん、アプローチ1で総当たりは試しているのでこれも参考にはならなさそうです。

オリジナルの問題の解法が使えたら、わざわざspecial thanksなんて書きませんからね。

アプローチ3

一般に楕円曲線の離散対数問題は解けないですが、楕円曲線の位数が小さい素数の積で表せる場合、Pohlig-Hellman attackが可能です。(類題: picoCTF 2017 ECC2)

# approach3.sage

p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
E = EllipticCurve(GF(p),[A,B])

print(E.order())
# 13046889097521646369087469608188552207167764240347195472002158820809408567609977087077882412569118765147021946659023117215407788432751798068268647045531505

結構時間がかかります。Sage Math Cellだと多分タイムアウトします。

さて、これを素因数分解するわけですが、msieveを使ってもfactordbを使ってもいい結果は得られません。

150桁くらいの合成数が残ってしまうので、この方法も失敗です。

アプローチ4

最初の要約のところに

$Q=kP=(x_1, y_1), R=(k+1)P=(x_2, y_2)$ とする。

とあります。ということは、 $x_1, x_2$ に依存関係があります。

具体的には、 $P+Q=R$ なので、Wikipediaをもと⁸に

$x_2 = \left(\frac{y_1-Y_0}{x_1-X_0}\right)^ 2 - x_1 - X_0$

が成立します。これと $x_1x_2 = N$ を連立する方針でいきます。

以下、式変形が続きます。当然ですが、 $y_1^ 2=x_1^ 3+Ax_1+B$ です。

まず分数を除去します。

$x_1 \left(\left(\frac{y_1-Y_0}{x_1-X_0}\right)^ 2 - x_1 - X_0\right) = N$

$x_1 \left(\frac{y_1-Y_0}{x_1-X_0}\right)^ 2 - x_1^ 2 - X_0x_1 = N$

$x_1 \left(\frac{y_1-Y_0}{x_1-X_0}\right)^ 2 = x_1^ 2 + X_0x_1 + N$

$x_1 (y_1-Y_0)^ 2 = (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N)$ ...(＊)

しかし、このままだと $y_1$ が残っているので、なんとかして $y_1^ 2$ の項を作ろうと式変形しています。

イメージとしては、

$\sqrt{x^ 2+1}+x=5$

に対して $\sqrt{x^ 2+1}=5-x$ としてから2乗してルートを消す感覚です。

$x_1 (y_1^ 2- 2Y_0y_1 + Y_0^ 2) = (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N)$

$x_1 (x_1^ 3+Ax_1+B - 2Y_0y_1 + Y_0^ 2) = (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N)$

$x_1 (x_1^ 3+Ax_1+B + Y_0^ 2) - 2x_1Y_0y_1= (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N)$

$x_1 (x_1^ 3+Ax_1+B + Y_0^ 2) - (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N) = 2x_1Y_0y_1$

$\left(x_1 (x_1^ 3+Ax_1+B + Y_0^ 2) - (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N)\right)^ 2 = 4x_1^ 2Y_0^ 2y_1^ 2$

$\left(x_1 (x_1^ 3+Ax_1+B + Y_0^ 2) - (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N)\right)^ 2 = 4x_1^ 2Y_0^ 2(x_1^ 3+Ax_1+B)$

$\left(x_1 (x_1^ 3+Ax_1+B + Y_0^ 2) - (x_1-X_0)^ 2(x_1^ 2 + X_0x_1 + N)\right)^ 2 - 4x_1^ 2Y_0^ 2(x_1^ 3+Ax_1+B) = 0$

お疲れ様でした。これで $x_1$ だけの多項式で、係数は全て既知の状態になりました。

これをSageに解いてもらいましょう。

# approach4.sage

p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
E = EllipticCurve(GF(p),[A,B])

X0 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980
Y0 = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991
P = E(X0, Y0)

N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387

# xがx_1に相当します
x = PolynomialRing(GF(p), 'x').gen()
f = (x*(x**3+A*x+B+Y0**2)-((x-X0)**2)*(x**2+x*X0+N))**2 - 4*(x**2)*(Y0**2)*(x**3+A*x+B)
ans = f.roots()
print(ans)
# [(5266647903652352665309561331835186152327627163271331811555419978564191000470060566535428497675116887002541568904535904345037425011015457585262022604897451, 1), (4292528248136861387890911319917455946841411872473250675409509735620572311636407361858881556677385609500178629430025710517411214702704597103005396234440737, 1), (11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 2)]

print(f)みたいなことをしたらわかりますが、上記は $x$ の6次式ですがいとも簡単に解いてくれます。コンピュータさまさまです⁹。

ちなみに、(5266...7451, 1)のようになっていますが、この1の部分は解の重複度です。最後の1128...9980は2重解ということです¹⁰。

これで $x_1$ の候補が見つかりました。

あとは $N$ / $x_1$ が割り切れれば確定です。

以上をもとに、ソルバは次のようになります。

# solver.sage

# 与えられたパラメータ
p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
A = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
B = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177
E = EllipticCurve(GF(p),[A,B])
X0 = 11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980
Y0 = 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991
P = E(X0, Y0)

N = 22607234899418506929126001268361871457071114354768385952661316782742548112938224795906631400222949082488044126564531809419277303594848211922000498018284382244900831520857366772119155202621331079644609558409672584261968029536525583401488106146231216232578818115404806474812984250682928141729397248414221861387
E = 0x10001
C = 15850849981973267982600456876579257471708532525108633915715902825196241000151529259632177065183069032967782114646012018721535909022877307131272587379284451827627191021621449090672315265556221217089055578013603281682705976215360078119427612168005716370941190233189775697324558168779779919848728188151630185987

# 多項式ソルバ
x = PolynomialRing(GF(p), 'x').gen()
f = (x*(x**3+A*x+B+Y0**2)-((x-X0)**2)*(x**2+x*X0+N))**2 - 4*(x**2)*(Y0**2)*(x**3+A*x+B)
ans = f.roots()

# x_1の特定
for c in ans:
    if N % int(c[0]) == 0:
        x1 = int(c[0])
        break

# RSA解読部分
import codecs

x2 = N // x1
phi = (x1-1)*(x2-1)
d = pow(E, -1, phi)
m = pow(C, d, N)
print(codecs.decode(('%x' % m), 'hex_codec'))

感想ですが、コーディングで2乗と2倍を間違えたりしていて、式変形はあっているのかや $k=4$ など答えが分かっている状態でちゃんと動作するのかなどのデバッグに手間取りました。

上でも記しているように、 $x$ の6次式(デバッグ段階では8次式になったりしていた)を解かせることになるので、まさかこのアプローチでうまくいくと思っていませんでした。何事もやってみるのが良しです。

あとで他の問題もwriteupを作成します。→ こちら

ありがたいことに相互FFの方もいます。↩
最低限貢献はしたものの、間違いなく落ちています。ちゃんと復習します。↩
この記事を読んでいる人でそんな心配性の方はいないと思いますが…↩
出典忘れました。すみません。↩
ちなみに、上記のももいろテクノロジーの記事内のコードもほぼ同じ内容ですが、 $m_2=am_1+b$ で $a=1$ の場合に限定しています。自分の後学のため、一般化している別の記事を取り上げます。↩
$p$ を大文字にすると点Pと混同するので小文字にしました。↩
余談ですが、rkm0959氏はcryptoのエキスパートです。よくwriteupの参考にしています。↩
厳密にはWikipediaに載っているのは $-R$ の計算ですが、-1倍しても $y$ 座標の正負が入れ替わるだけなので今回は関係ありません。↩
記事では冷静に書いてますが、当時めちゃくちゃガッツポーズしてました。↩
この1128…9980という値、実は $X_0$ そのものです。(＊)で $x=X_0$ が重解を持つのは明らかですね。↩