ふるつき

v(*'='*)v かに

LINE CTF 2021 babycrypto4 writeup

LINE CTF は cryptoに関しては満足行くクオリティの問題はありませんでした……。

overview

secp160r1上のECDSAに関する次の20 x 4個のパラメータが与えられます*1。左からr, s, kの上位16bit, hash(m) です。このときにいわゆる秘密鍵dを求めよ、という問題です。

0x92acb929727872bc1c7a5f69c1c3c97ae1c333e2 0xe060459440ebc11a7cd811a66a341f095f5909e5 0xef2b0000 0x68e548ef4984f6e7d05cbcea4fc7c83393806bbf
0xb0f5df566a323de9c9449b925d29b84a607c6b5d 0x84e39e417e47b4fcaf344255103c61ecaaec4129 0xc1c00000 0x1a79e7b0308805508d79f2600a01e70d4f56559e
0xc90081698382f98c817a137db22f11a846d699fe 0x2f8fbb7e74b789cd762b30930ef21862a5fd68ee 0x841b0000 0x95e3302e197be4d8335cf0d17cc70860ea5317f7
0x9d84669314b014bc83f3ac53ddcf3c9536c940b1 0x8b1a69d6e9d75f1698144badc7b93f9a2347839d 0xa1c90000 0xc7af08154a154ac8c58eb14380955834093b3863
0x96d5439a01f47e92be9ff40bee1fecb033b70d3f 0x1c23660695d16bf03ef40e5ef53bdc92a5d348e7 0x816e0000 0x9d3f0dc80e962b9377ed22de66d6421457bcaf5d
0x3ea39f6c446918690b395ba181f6d5d08444897a 0x4478e239338ec6652815d03b8decb2d4f58beaba 0x9d050000 0x478e00e6191477e6cdd17a29719d96d02e5e8960
0xbd1cbcd26fb6cb41878ec155fb2506534e803c97 0xd732fbda187222d85e9a14243b007cc25e1b6b7c 0x445a0000 0x2493379cf90246fe7316963c65f28cd9b0a6ecd4
0x727f7f05a9096beb6d5f65acce6fe42ec3a07dc9 0x8511715efb01ff83b04fe82fb7535dc7de40abef 0x91d0000 0x6ce034dddd5470034068c5146fae4dd039aacaf6
0x513ed0e15f8f3405bf0083a2186926fe60ccb65e 0x28892ebcc428f2a566b39a2dbe03ec436641c948 0x879d0000 0xfe4e2564369a23e07efbf82d01c5ae7e72cd8105
0xebf3e23fbe73c5f50032c8e4a3d8359fef203a03 0xa5b79ae6f8ed237a05b4325c02b8dfe7b9ff5aa7 0x98950000 0x762309f98ebac533fece5321736fc6ba95d8382b
0xc49cdbf6ec3b73188238291fa960675a099b74a0 0xeabb1e7dcd20115a47b94ecfe8780f676e237437 0x287a0000 0x523ea75c4310ac1ac64fa28cc5047b7223e8da0b
0x9e8a731a26f509793e2b8778cd75b518549ab9c8 0x27be029029db9d62cdb729bc592cb0a4e6168bf3 0xebc80000 0x9f0e9e95661f5e93c90b72af0dce38c673c7ef16
0xa74159f377749ad36efc28f9c7608a6758009af 0xa3ce2671944b01f633265a6458ce2cca8b72eda6 0x574c0000 0x16e12f9dece23681927be002d24a0e4e6ed3ae7e
0xcb0a427a05b3e3dcb18a1bb66f9340d2a0c721ab 0x4a242cca295c6018f4a65d1fadbdb45731cccd7a 0x23f40000 0xd7e0a09d8aed604bc1fda1f1965c4a8bf6b58621
0x5dc440585c88e75da002f941520867add07f93ef 0x3612124de46659ef7d79d46f1eb05707e313b84d 0x65850000 0xca6547a9e3f08bd36f700b7282a36033250971ad
0x6e009a8f5138a5b94d4e81b5f2a07ee29b413b39 0x8b3c33c15dca93248f840324d540b7956251d1e0 0xb4f80000 0xe916da678253ff7b31453ba1ec709eb909b37c5d
0x5091314db6155d7a96c1b19098ca235cf86d1f77 0x2c62bf21452a2b326e8db27fb3345e10c63b2821 0x452c0000 0x31dd06dcf95fb04a734149eed64b7b99a575d56e
0x2f6eed036a46ca6e309d8d7292bd3b0796607fcc 0x63b4524f47dcde603426c48bbb2f308bc474e5ce 0x63780000 0xe108d036a12b4f15cc9af89688d26634c5dfc32a
0x247ca1d3450a85612e6176ea5dfec4aeb90e2a3f 0x66b1f9f04e284e28f44402f1ca7803c90786d9c2 0x48a0000 0xd58c608cc4d3adfc131c73cccff952c1d310a1e0
0xab04fc0c4981b047622c786662091f7efbbbd807 0xa2853851df0aaed34dc972bcf7d7d5ffbbc2b401 0x9d040000 0x5bdd98b548b8b0f48a56fb4c41e6d09bf8bd1b0e

solution

いわゆるnonceであるkの上位16bitがわかっているのでこれを利用するのかな、と思うところですが、そもそも32bitのkでは小さすぎるので、半分が与えられていようがいまいが変わらず解けます。

(EC)DSAでは s \equiv (h + rd)k^{-1} \mod n ですから、これを展開して変形すると k - s^{-1}rd - s^{-1}h \equiv 0 \mod n になります。いくつかのインスタンスを考えて、インスタンスごとに異なる値に添え字をつけると

k_i - s_u^{-1}r_id - s_i^{-1}h_i \equiv 0 \mod n

となります。このとき、 k_i, d がそれぞれ未知数で、 r_i, s_i, h_iはそれぞれ既知です。

一方、Hidden Number Problemは以下の式で t_i, a_i既知、 x_i, y未知に未知数を求める問題で、 x_iの最大値がある程度小さい時には、CVPを解いて x_i, yがそれぞれ求めることができます。

x_i - t_iy + a_i \equiv 0 \mod p

2つの式を見比べてみると、 k_i \leftrightarrow x_i, s_i^{-1}r_i \leftrightarrow t_i, d \leftrightarrow y, a_i \leftrightarrow -s_i^{-1}h_i という対応づけができそうです。そして、 x_iに対応する k_iは最大でも 2^{33} - 1 と小さいですから、CVPを解くことで k_i, xを求められそうです。今回は埋め込み法(embedded technique)と呼ばれる形のSVPを解くことでCVPを解いています。

from hashlib import sha1
import random

# https://neuromancer.sk/std/secg/secp160r1
p = 0xffffffffffffffffffffffffffffffff7fffffff
K = GF(p)
a = K(0xffffffffffffffffffffffffffffffff7ffffffc)
b = K(0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45)
E = EllipticCurve(K, (a, b))
G = E(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32)
E.set_order(0x0100000000000000000001f4c8f927aed3ca752257 * 0x01)

n = int(E.order())

dataset = []
with open("output.txt") as f:
    lines = f.read().strip().split("\n")
    for l in lines:
        # r_, s_, k_, h_ = [int(x, 16) for x in l.split(" ")]
        dataset.append( [int(x, 16) for x in l.split(" ")] )


r, s, k, h = zip(*dataset)
N = 20 # randint(2, 20) # len(h)
print("N = {}".format(N))
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [(h[i] * inverse_mod(-s[i], n) % n) % n for i in range(N)]

nonce_max = 2**32

B = matrix(QQ, N + 2, N + 2)
B.set_block(0, 0, matrix.identity(N) * n)
B.set_block(N, 0, matrix(QQ, 1, N, t))
B.set_block(N+1, 0, matrix(QQ, 1, N, u))
B[N,N] = nonce_max / n
B[N+1,N+1] = nonce_max

L = B.LLL()
for row in list(L):
    k1 = int(abs(row[0]))
    if k1 != 0 and k1 != nonce_max and k1 < nonce_max:
        x = (k1*s[0] - h[0]) * inverse_mod(r[0], n) % n
        kk = (k1 >> 16) << 16
        print(k1, x, kk in k)
        print(int(x)*G)

この問題では k_iがかなり小さいので、3インスタンス程度あればHNPが解けます。

*1:もともと問題文ではsecp160k1となっていましたが、正しくはsecp160r1のようでした。この間違いのアナウンスなしに解いたThe Duckはすごい

CTF crypto 逆引き

theoremoon/ctf-crypto-dict へのコントリビュートお待ちしております。こういう内容についても書いてほしいみたいな場合もissueとか建ててくれるとそのうちやるかも

RSA

黙って Twenty Years of Attacks on the RSA Cryptosystem や Recovering cryptographic keys from partial information, by example を読んでおけば大体なんとかなる

e が 3など (Low Public Exponent)

例えば、 m^e \lt n であればe乗根を取ることで mが手に入る

出題例

nが多くの素因数に分解される

いわゆるMulti-Prime RSA。 nがどう素因数分解されようともオイラーのφ関数は定義できて、 \mod nでの位数がわかるので逆元 d \equiv e^{-1} \mod \phi(n)が求められる。

出題例

nがある素数と別の合成数までは素因数分解できる

実際には n = p*q*r だが、 p \lt q,r でnを素因数分解した結果 n = p*c （ここで c=q*r）までは得られたが、 cの素因数分解は難しそう、というとき。このとき m \lt pであれば、 \mod pの世界で考えることで mを得られる。

出題例

nが同じでeが異なる複数の暗号文 (Common Modulus)

Common Modulus Attackが適用できる。複数の eが互いに素ではない場合には、それぞれの eの最大公約数を公開鍵とした暗号文が手に入ることになる

出題例 募集中

e, dがわかっているときにnを素因数分解する

def factorize(N, e, d):
    from math import gcd
    import gmpy2

    k = d*e - 1
    t = k
    while t % 2 == 0:
        t //= 2

    g = 3
    while True:
        x = pow(g, t, N)
        if x > 1:
            y = gcd(x - 1, N)
            if y > 1:
                return y, N//y
        g = gmpy2.next_prime(g)

出題例 募集中

φ(n)がわかっているときのnの素因数分解

そもそも \phi(n)がわかっているならsecret exponentが求められるのでわざわざ nを素因数分解する必要はない。それでも素因数分解したい場合は n = pq, \phi(n) = pq - p - q + 1より、 b = n - phi + 1 = p + q としておくと、2次方程式の解と係数の関係から p,q = \frac{b \pm \sqrt(b^2 - 4n)}{2}として素因数が求まる

出題例 募集中

何度でも任意の暗号文を復号でき、復号結果のうち一部が手に入る (LSB Leak)

LSB Leak Attackが適用できる。一度に手に入る平文のbit数が多い代わりに、復号の試行回数に制限がある場合もある。LSB Leak Attackには2種類のアプローチがあると思っている。

一つはよく説明されるもので、次の通り。

(2^eC)^d \equiv 2m \mod nについて考える。 2m \lt n であれば 2mは2倍されているので偶数、すなわちLSBは0となる。一方で 2m \gt nでれば、復号結果は 2m - n となるから（ 2n \gt 2m \gt n ）偶数と奇数の減算で奇数になる*1。すなわちLSBは1となる。ということは、 2^eCの復号結果のLSBが0ならば 0 \lt m \le \frac{n}{2}が、LSBが1ならば \frac{n}{2} \lt m \lt nがわかる。次に 4^eC についても同様に考えて、次々と mの範囲を2分探索的に縮めていき、 mの値を求める。

もう一つの方法は、次のようなもの。

C \mod nの復号によって得られるLSB Oracleは mの最下位bitである。では 2^{-e}C \mod nの復号結果から得られるLSB Oracleはどうか。 m = 2^{k}a_{k} + \cdots + 2^1a_1 + a_0 と書くと m2^{-1} \equiv a_1 + 2^{-1}a_0 \mod 2となる。ここで、 a_0は先程明らかになったため、簡単な計算で a_1を算出できる。同様に a_2, a_3, \dots と復元して a_{k}まで復元することで、 m全体を求めることができる。

出題例

pやqに関連する値を暗号化している

うまく暗号文同士のgcdをとったり、 \mod pなどについて考えることによって秘密鍵を入手できる場合がある。

出題例

mやp, q, dの値が一部わかっている、近似できる

LLLやCoppersmith methodを使ってmやp, q, dを求めることができる。Coppersmithも内部ではそれっぽい格子を生成してLLLをしているのでどちらでも解ける。sageに実装されているCoppersmith methodは一変数多項式に対するものだが、多変数多項式に対してはdefundさんが実装しているものが出来がよく、これを使っておけばだいたいなんとかなる。

github.com

Coppersmith method適用のための典型的な立式

基本的には以下の2種類の式か、この式のmodを開いて（＝ a \equiv b \mod mを適当な整数 kを持ってきて a = b + kmと変形して）別の変数でmodを取り直した形の式で小さい根が求められないか考えることになります。

  • c \equiv m^e \mod n または c^d \equiv m \mod n
  • ed \equiv 1 \mod \phi

RSAの基本的な変数の他に特別な値が渡されている場合（ nや p, qの構成方法が特殊で、構成に用いる一部の値や式が公開されているなど）はその式やその式と上式、 n = pq, \phi = (p-1)(q-1) = N - (p+q) + 1などを組み合わせて立式します。

出題例

pやqに関連する値が追加で渡されている

r = f(p, q)や x = f(p, q)としてRSAのパラメータ n, e, cの他に p, qのヒントとなるような値を与えられているときは rや xについて \mod p, \mod qの式を立ててCoppersmith Methodをすると良いです。

出題例 - Leaky RSA - RTACTF upsolve - ふるつき

dが同じでnやeが異なる暗号文 (Small Common Private Exponent)

かつ、dがある程度小さければSmall Common Private Exponent Attackができる。

出題例

端的に言うと f_1, f_2という多項式があって、これらが同じ根を持つときに Franklin-Reiter's Related Message Attackが使える。典型的には c_1 = m^e \mod n, c_2 = (am + b)^e \mod nで a, bが明らかになっている場合には、未知数を xとおいて f_1 = c_1 - x^e, f_2 = c_2 - (ax + b)^eというような式を建てると2つの多項式が同じ根 mを共有します

出題例

ブロック暗号

ECBモードで、任意の平文+フラグが暗号化される

いわゆるChosen Plaintext Attackができる。

出題例

CBCモードで平文の先頭1ブロック程度を変更できれば良い (Bit Flipping)

Bit Flipping Attackで十分

出題例

CBCモードで復号の成否がわかる (Padding Oracle)

Padding Oracle (Encryption) Attackができる。

出題例

2段や3段の暗号化で、使われている鍵が短い (Meet in the Middle Attack)

Meet in the Middle Attackができる。

出題例

複数のラウンドで同じ鍵が使われている / 同じ鍵によって複数段の暗号化が行われている (slide attack)

平文と暗号のペアを十分な数得られる場合にはslide attackが適用可能かもしれません。詳しくは slide attack - Plaid CTF 2022 choreography upsolve - ふるつき をご参照ください

出題例

独自のS-BOXが使われている

Differential / Linear Cryptoanalysis だろうけど理解してないのでかけない

楕円曲線暗号

基本的な事項はだいたいすべて yoshi-gcc log - ふるつき にあります

位数が小さい素因数の積に分解できる (Pohlig-Hellman Attack)

楕円曲線に限った話ではなく一般の離散対数問題について言えることですが、位数が小さい素因数の積に分解できる時、元の群を小さい位数を持つ別の群に移してから離散対数問題を解き、CRTで元の群での離散対数問題を解くというPohlig-Hellman 攻撃が可能です。

雑に数式を持ってきて説明すると、ある曲線 Eがあって Q = xPなる P, Qが与えられて xを求めたいといういわゆる(EC)DLPを解きたいとします。このとき、 Eの位数 nが小さい素因数 p_1, p_2, \dotsの積に素因数分解できているとして、 n = \prod p_i ^ {e_i}と表しておきます*2。

このとき Q = xPのかわりに、ある素因数 p_iを持ってきて (n/p_i)Q = y_i(n/p_i)Pという式を考えるというのがPohlig-Hellman Attackのアイデアです。 (n/p_i)P, (n/p_i)Qは p_i倍すると p_i * (n / p_i)P = nP = G というふうに単位元と一致するので、点 (n/p_i)P, (n/p_i)Qの位数は p_iです*3。点の位数 p_iが十分小さければ、 (n/p_i)Q = y(n/p_i)Pとなるような yを求めることは容易く、 y_i \equiv x \mod p_iです。いろんな素因数 p_iについてかんたんな離散対数問題を解き、集めた y_i \equiv x \mod p_iの組から中国剰余定理を用いて xを求めることができます。

出題例 - PicoCTF 2017 - ECC2

位数と剰余の法が同じであるような楕円曲線である（SSSA Attack）

楕円曲線 y^2 \equiv x^3 + ax + b \mod pの剰余の法 pとその位数（ここでは nとします）が同じであるとき（つまり n = pであるとき）、その曲線はAnomalousであるといい、SSSA Attackと言われる手法を用いることで2点 P, Qから Q = xPとなるような xを求める(EC)DLPが簡単にとけます。この手法について簡潔に説明するのは難しいので私がめちゃくちゃ説明上手になるまではこのページには説明はかけません。ごめん

出題例

楕円曲線にcusp型の特異点が存在する（Singularな楕円曲線）

特異点が存在するような楕円曲線の場合、特殊な形式になっているため楕円曲線よりも簡単な演算を行う別の群への同型写像が定義できる場合があります。特にcusp型と呼ばれる楕円曲線は加法群への写像が定義できるため、離散対数問題が整数の除算と対応し簡単に解けます。 曲線がsingularか、またcusp型かどうか判別する手段についてはこのページでは解説を省きますが、Sagemathを使っている場合Singularな楕円曲線をEllipticCurveクラスを使用して定義しようとすると例外が発生することで気がつけると思います

実際にcusp型の楕円曲線に遭遇した場合には、特異点が原点になるように楕円曲線を平行移動すると y^2 = x^3 \mod pという非常に単純な式になります。曲線上の点 (x, y)は (x, y) \to x / y \mod pという写像によって \mathbb{F}_p上の値に写すことができ、また z \in \mathbb{F}_pは[z \mod p → (z^{-2} \mod p, z^{-3} \mod p)]という逆写像によって楕円曲線上の点に戻すことができます。

したがって、cusp型の楕円曲線上の離散対数問題 Q = dPは P, Qを平行移動して y^2 = x^3 \mod p上の点にしてから、 (x, y) \to x / y \mod pという写像で有限体上の値に移し、 \mod pの除算で dを求めることができます。

出題例

楕円曲線上に存在しない点の演算ができる（Invalid Curve Attack)

例えば楕円曲線 E: y^2 \equiv x^3 + ax + b \mod p上の点 Pをこちらが指定するとそれを x倍した点 Qを返してくれるので xを求めよという問題は楕円曲線のパラメータが安全であれば基本的に解くことは難しいです。

しかし、うっかりこちらが指定した点が楕円曲線上に存在するかどうかが判定されていない場合、別の楕円曲線 E': y^2 \equiv x^3 + ax + b' \mod p上の点 P'を指定することで Q' = xP'を計算させることができます。ここで上述されているような脆弱なパラメータの楕円曲線を指定しておけばそれらの手法を利用して xを求めることができます。

なぜ E上の乗算処理が行われるはずのロジックに対して E'上の点を渡して正しく x倍されるのかといえば、楕円曲線の加算（及びその繰り返し二乗法で実装されている乗算）では曲線のパラメータのうち bが使われていないからです。したがって、定数項 bの値のみが異なる Eと E'の２つの楕円曲線上の点の演算は同じロジックになります。

出題例

乱数

線形合同法を用いている

線形合同法は x_{i+1} \equiv Ax_{i} + B \mod Mという漸化式で表される単純な乱数生成器です。ある時点の出力が得られれば前後すべての出力を計算できるほか、 A, B, Mといったパラメータが未知の場合でも、複数の出力からこれらのパラメータを復元することもできます。

詳しくは kurenaif さんの動画で解説されているのでそちらを参照してください

出題例

LFSR

単純なLFSRならz3で殴ると解けます。それより難しい問題については魔女のお茶会 2022/春でy011d4さんが発表していたLFSRの超難問を解くというスライドを参照されてください

mersenne twisterで624個の連続した出力が得られる

mersenne twisterは624個の値からなる内部状態を持っており、複数の値に対してtwist処理を行って周期が長く予測が困難な乱数を生成しますが、出力をuntwistして内部状態を復元することができ、624個の連続した出力が得られれば内部状態を完全に復元できます。

内部状態の復元には kmyk/mersenne-twister-predictor が便利です。

また、出力の一部が欠落しているような場合にも十分な数の出力が得られるならば、z3などを用いて内部状態を探索可能であることも知られています。こちらは icemonster/symbolic_mersenne_cracker に実装があります。

出題例 - SECCON Beginners CTF 2022 Unpredictable Pad

その他の暗号

onetime pad

絶対にmany time padなので頻度解析をしながら鍵を当てていくとだんだん解けます。以前インタラクティブに解けるソルバを作ったので使い方を憶えると解きやすくなるはず

https://github.com/zer0pts/mtpsolver

出題例

(EC)DSA で同一のnonceが複数回用いられている (Nonce Reuse)

いわゆるnonce-reuse attack

出題例

平文がフラグと連結、圧縮されてから暗号化される（圧縮サイドチャネル攻撃 / compression oracle）

多くの圧縮手法では同一の平文が存在すると圧縮効率がよくなるため、もっとも圧縮効率がよくなる1文字を探索することでフラグに対するオラクルとすることができる。これはBEASTやCRIMEといった攻撃手法の原理（のはず）

出題例

*1:すなわち nが素因数に2を含んでいる時にはこの攻撃は成立しない、と思う

*2:どの素因数 p_iもある数 Bより小さい時 nはB-smoothであると言ったりします

*3:この説明だと位数は p_iの約数ですとまでしか言えないんですが、 p_iは素数なので1か p_i自身のみしか候補がありません

Fireshell CTF 2019 Biggars writeup

gist.github.com

とにかく長大なパラメータを持つRSA。nは大きいが小さい素因数からなっていて、簡単に素因数分解できる。

>>> list(factor(n))
[(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)]

3つ以上の素因数からなるRSAはMulti-prime RSAと言われる。この場合にもRSA暗号は成立する。オイラーのφ関数を一般化して、 N = \prod_i p_i^{k_i} と表されるとき、 \phi(N) = \prod_i(p_i^{k_i}-p_i^{k_i-1}) である。あとは dを計算して復号すれば良い

ただしこの問題の場合、 nが非常に大きいため、 c^d \mod nの計算はそのままでは非常に時間がかかる。そこでRSA-CRTの考え方を使い、中国剰余定理を用いてこの計算を高速化する。

import gmpy
from params import n, e, c

def chinese_remainder(ms, ns):
    assert(len(ms) == len(ns))

    n = 1
    for i in range(len(ms)):
        n = n * ns[i]

    r = 0
    for i in range(len(ms)):
        p = n / ns[i]
        r += ms[i] * gmpy.divm(1, p, ns[i]) * p
    try:
        return long(r % n)
    except:
        return int(r % n)

factors = [(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)]


ms = []
ns = []
for p, k in factors:
    n = pow(p, k)
    phi = pow(p, k) - pow(p, k - 1)
    d = gmpy.divm(1, e, phi)
    m = pow(c, d, n)
    ms.append(m)
    ns.append(n)

m = chinese_remainder(ms, ns)
print(bytes.fromhex(hex(m)[2:]))