Mystery of Scattered Key

時間内には解ききれなかったのですが、かなり惜しい所まで行った問題についてのメモ書きです。

目次

問題
 試したこと
 解答

問題

与えられた問題ファイルの内容は以下です。

ソースコード

challenge.py

from Crypto.Util.number import getStrongPrime
from random import shuffle

flag = b'FAKE{THIS_IS_FAKE_FLAG}'


p = getStrongPrime(1024)
q = getStrongPrime(1024)

#p=98472054987205546789087654
#q=19857394857209546789087666

N = p * q
e = 0x10001
m = int.from_bytes(flag, 'big')
c = pow(m, e, N)


# "Aaaaargh!" -- A sharp, piercing scream shattered the silence.

p_bytes = p.to_bytes(128, 'big')
q_bytes = q.to_bytes(128, 'big')
print(p_bytes)
print(q_bytes)

fraction_size = 2
p_splitted = [int.from_bytes(p_bytes[i:i+fraction_size], 'big') for i in range(0, len(p_bytes), fraction_size)]
q_splitted = [int.from_bytes(q_bytes[i:i+fraction_size], 'big') for i in range(0, len(q_bytes), fraction_size)]

shuffle(p_splitted)
shuffle(q_splitted)


print(f'N = {N}')
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')
print(f'p_splitted = {p_splitted}')
print(f'q_splitted = {q_splitted}')

output.py

N = 20258342755030699342765611614877226774887411463378181451840683524015047892651973850627359327237027774356720466793903228878105456871700095061940512708020098618057571729943083434709826167248620306311075548853347901271259447873417249634361203320669711383057513256692645763182907367630873827308387269636636289231405813338687900835089134983309705316926805886077666050520726687030034195743282451467528496315178642323807316904673350899061558504836111406826196935670026969650853021793806021689762347770412960223358347923518483267323592429810806182091459339480461991545802571444958728299104188325433443437138511489545219679697
c = 7123414739023542748810203483709689015408917851116023820618517477707107834968496358236168325897320226453721626392832959216652528045703210750125701176032827942299755718368878395927764432908785593372611140758024558283573960529417102003625606595077755879081211049268879243499173403440059239858308427266558935817943602623773418104985260309484175243613311427707700872120183486969325635776183186398996045018265812500716946531309303922788481972201938026485853049867490332841823037660486595790337519475108241096821738281828388702502632013367441754603384687444518555226345985885414563346111755133096794599057161802602344386709
p_splitted = [1648, 26443, 23758, 59540, 54722, 64595, 54876, 56461, 37559, 58038, 62190, 48794, 3685, 15347, 37807, 65456, 27238, 43839, 27847, 38403, 26704, 6902, 13361, 48888, 40733, 30039, 2759, 31739, 10053, 15206, 32185, 8727, 53066, 51903, 33778, 57075, 7384, 34279, 55988, 26971, 15381, 10770, 14264, 30253, 11971, 50652, 14420, 7242, 54046, 21582, 26535, 42340, 43335, 52478, 60716, 21061, 2633, 24288, 44532, 50813, 49308, 30582, 3906, 4989]
q_splitted = [17900, 40783, 35173, 58646, 30439, 8839, 14895, 33243, 40515, 60827, 39626, 23436, 11739, 48698, 26830, 44120, 9651, 38993, 3295, 4606, 57793, 57260, 63312, 38766, 33916, 15401, 37856, 21410, 23082, 4751, 12279, 60843, 26791, 61740, 8570, 31666, 55249, 23535, 64786, 26597, 3997, 60330, 28810, 21136, 20487, 55594, 10618, 34867, 55177, 33728, 60147, 62991, 36041, 50205, 44371, 40864, 36657, 32481, 5885, 12358, 6736, 8984, 5618, 27045]

ごく普通のRSA暗号なのですが秘密鍵生成に用いるp,qを2byteずつ分割してシャッフルしたものがC,Nと同時に出力されています。
配列の要素が60を越えるためp*q=Nとなるp,qを総当たりで見つけるのは厳しそうですが、まずp_splitted[i]*q_splitted[j]の下位2byteがNの下位2byteと一致する(i,j)の組み合わせを見つけ、次に3～4byte目のp_splitted[i]とq_splitted[j]の組み合わせについて、最初に見つけた下位2byteと組み合わせて作った数の積における下位4byteがNの下位4byteと一致するものを探す、といった手順を繰り返すことで下位桁から順に2byteずつ確定していくことができそうです。

試したこと

分割前のpとqを求めようと作成したソースコードが以下です。

solve.py

N=[省略]
p_splitted=[省略]
q_splitted=[省略]
flag=0
p_answer=0
q_answer=0
for k in range(len(p_splitted)):
    flag=0
    print(k)
    for i in p_splitted:  
        for j in q_splitted:   
            if (((i*(65536**k)+p_answer)*(j*(65536**k)+q_answer)))%(65536**(k+1))==N%(65536**(k+1)):
                print(hex(i),hex(j))
                p_answer+=i*(65536**k)
                q_answer+=j*(65536**k)
                print(f"p={hex(p_answer)}")
                print(f"q={hex(q_answer)}")
                flag=1
                break
        if flag==1:
            break

実行結果

0
0x5245 0xc41d
p=0x5245
q=0xc41d
1
0xa49 0x297a
p=0xa495245
q=0x297ac41d
2
0xa947 0xf750
p=0xa9470a495245
q=0xf750297ac41d
3
0xc5dc 0x9e43
p=0xc5dca9470a495245
q=0x9e43f750297ac41d

以下省略

pとqの配列要素の組み合わせを総当たりし、下位2biteの一致を剰余計算で確かめ、一致すればp_answerおよびq_answerの上位に追記していくというという作業を配列要素数分だけ繰り返すだけのコードですが、実行すると10回目の繰り返しのあたりで総当たりしても剰余が一致しなくなり、p_answerおよびq_answerの生成が止まってしまいました。

解答

競技終了後、他の方のソースコードで求めたp,qと比較して確認した所、どうやら9回目にたまたま別の組み合わせの剰余が一致してしまったことが原因で生成が止まったようです。上手くいかなければ戻ってやり直すというコードに変更することも考えましたが、配列の順序を直接変更した方が早そうだったので出力が止まった段階で最上位に追加されていた要素を手作業で配列の最後尾に移動させました。

配列要素の入れ替えを何回か行い、最後まで生成が行われることを確認しました。最終的なソースコードが以下になります。

ソースコード

solve.py

N = 20258342755030699342765611614877226774887411463378181451840683524015047892651973850627359327237027774356720466793903228878105456871700095061940512708020098618057571729943083434709826167248620306311075548853347901271259447873417249634361203320669711383057513256692645763182907367630873827308387269636636289231405813338687900835089134983309705316926805886077666050520726687030034195743282451467528496315178642323807316904673350899061558504836111406826196935670026969650853021793806021689762347770412960223358347923518483267323592429810806182091459339480461991545802571444958728299104188325433443437138511489545219679697
c = 7123414739023542748810203483709689015408917851116023820618517477707107834968496358236168325897320226453721626392832959216652528045703210750125701176032827942299755718368878395927764432908785593372611140758024558283573960529417102003625606595077755879081211049268879243499173403440059239858308427266558935817943602623773418104985260309484175243613311427707700872120183486969325635776183186398996045018265812500716946531309303922788481972201938026485853049867490332841823037660486595790337519475108241096821738281828388702502632013367441754603384687444518555226345985885414563346111755133096794599057161802602344386709
p_splitted = [1648, 26443, 23758, 59540, 54722, 64595, 54876, 56461, 37559, 58038, 62190, 48794, 3685, 3906, 37807, 65456, 27238, 43839, 27847, 38403, 26704, 6902, 13361, 48888, 40733, 30039, 2759, 31739, 10053, 15206, 32185, 8727, 53066, 51903, 30582, 57075, 7384, 34279, 55988, 26971, 15381, 10770, 14264, 30253, 11971, 50652, 4989, 7242, 54046, 21582, 26535, 42340, 43335, 52478, 60716, 21061, 2633, 24288, 44532, 50813, 49308,33778,15347 , 14420]
q_splitted = [17900, 40783, 35173, 58646, 30439, 8839, 14895, 33243, 40515, 60827, 39626, 23436, 11739, 48698, 26830, 44120, 9651, 38993, 3295, 4606, 57793, 57260, 63312, 38766, 33916, 15401, 37856, 21410, 23082, 4751, 12279, 60843, 26791, 61740, 8570, 31666, 27045, 23535, 64786, 26597, 3997, 60330, 28810, 21136, 20487, 55594, 10618, 34867, 55177, 33728, 60147, 62991, 36041, 50205, 44371, 40864, 36657, 32481, 5885, 12358, 6736, 8984, 5618,55249]
flag=0
p_answer=0
q_answer=0
for k in range(len(p_splitted)):
    flag=0
    print(k)
    for i in p_splitted:  
        for j in q_splitted:   
            if (((i*(65536**k)+p_answer)*(j*(65536**k)+q_answer)))%(65536**(k+1))==N%(65536**(k+1)):
                print(hex(i),hex(j))
                p_answer+=i*(65536**k)
                q_answer+=j*(65536**k)
                print(f"p={hex(p_answer)}")
                print(f"q={hex(q_answer)}")
                flag=1
                break
        if flag==1:
            break
p=p_answer
q=q_answer
d = pow(65537, -1, (p-1)*(q-1))
m = pow(c, d, N)
print(m.to_bytes((m.bit_length()-1)//8 + 1, 'big'))

出力

実行結果

~~省略~~
63
0xbe9a 0xd789
p=0xbe9a67a7674be894fc53ffb006706850d65c6cc738541c4acabfdab4bef834311af6137d27453b662a1296035ee03c1577769f1d93af7db9cf4a762d37b87557c67d1cd8ccfe2217d5c2e2b62ec3ed2c85e7c09c5cce83f23bf37bfbab3fd31e695bf2ee6a66dc8ddef392b70ac7adf40f42a564544e0e65c5dca9470a495245
q=0xd78993e02ddb5bef0f9d8cc95b8c3c297bb269a5e516217a25b3ed9bf60fac58e1c115f23a2f708a7ee183c016fd68a7976e5a2a128ffd129f4f228767e5d92aedabd7d11a50be3a81dbebaa53a2eaf345ec68ce9acaad532318dfac30469fa011fe0cdff12c88338965985152908f312ff776e7847c50079e43f750297ac41d
b'TSGCTF{Yasu_is_the_culprit_4977d14abf9a4fad90d87046d2ee7e7d}'