squarectf2018 writeup

なかなか時間が確保できない今日この頃だが、脳死で解けそうなcrypto問があったので一応解いておいた。

C2: flipping bits

以下問題文。

Disabling C2 requires cracking a RSA message. You have two ciphertexts. The public key is (e1, n).

Fortunately (this time), space rabiation caused some bit flibs and the second ciphertext was encrypted with a faulty public key (e2, n). Can you recover the plaintexts?

ダウンロードしたjarを展開すると以下の内容のテキストファイルが出てくる。

ct1:  13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
ct2:  79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065
e1:  13
e2:  15
modulus:  103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627

You have two captured ciphertexts. The public key is (e1, n). But,
due to a transient bit flip, the second ciphertext was encrypted with a faulty
public key: (e2, n). Recover the plaintexts.

(The algorithm is RSA.)

bit flipとか書いてあってめんどくさそうな気がめちゃくちゃしたが、とりあえずRSA問ということで、いつもどおり使える攻撃が何かないか探してみる。 elliptic-shiho.hatenablog.com 今回はm（平文）とnが共通でeが異なるc（暗号文）の組みがあるので、Common Modulus Attackが利用できそう。
適当にコードを書く。（勢い余ってpython2で書いてしまった）

import sys
import gmpy
import binascii

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    m = (v * w) % n
    return m


if __name__ == '__main__':
    n = 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627

    e1 = 13
    e2 = 15

    c1 = 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654

    c2 = 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065

    print binascii.unhexlify(hex(common_modulus_attack(c1, c2, e1, e2, n))[2:])

解けた。FLAGはflag-54d3db5c1efcd7afa579c37bcb560ae0。

所感

スコアリングの方式は謎だったが、問題の難易度的にはクソ雑魚の自分でも楽しめるくらいだったようだ。（そろそろ難しい問題にも挑戦していけ！？）
来年もできれば参加したい。