picoCTF Writeup picoGym Practice Challenges Dachshund Attacks (注意<spoiler>)

Description

What if d is too small? Connect with nc mercury.picoctf.net 36463.

netcat で接続すると、以下のように表示される。

nts/vscode$ nc mercury.picoctf.net 36463
Welcome to my RSA challenge!
e: 83077563702343554104974996434204739715645265602158673538690676471463336678613073880241775254228605106314353101710729653105703801639218664265081281431800464768751108207853871447670242797434974960441087184849197992674269375516588035103695638200385202471858474940467172884556768907433680138245599680626741810005
n: 121284873122734173170589805129141828295734462070736051160234618042523930722218189770628981423754078589956502455716817264371793634639863579905483351333596734771084564158158237582686931067049984902518851429985265857972394495978382581497493613778673575845608203816577795080850903131867388133380707501389132343227
c: 111706960717247640773070034560791401516861975925294183308134273305345496149225528086786540735265768015796964138975156865137538532095816868770852225744950925213608920146611723694488931500427074463572885488370631349565427800972434165100944213038448250274326828594322342022449855379423340174278552163361661239365

e が大きすぎる場合、Wiener attack で d を求めることができる。

import owiener

def long_to_bytes(x: int) -> bytes:
    return x.to_bytes((x.bit_length() + 7) // 8, 'big')

def main():

    e = 83077563702343554104974996434204739715645265602158673538690676471463336678613073880241775254228605106314353101710729653105703801639218664265081281431800464768751108207853871447670242797434974960441087184849197992674269375516588035103695638200385202471858474940467172884556768907433680138245599680626741810005
    n = 121284873122734173170589805129141828295734462070736051160234618042523930722218189770628981423754078589956502455716817264371793634639863579905483351333596734771084564158158237582686931067049984902518851429985265857972394495978382581497493613778673575845608203816577795080850903131867388133380707501389132343227
    c = 111706960717247640773070034560791401516861975925294183308134273305345496149225528086786540735265768015796964138975156865137538532095816868770852225744950925213608920146611723694488931500427074463572885488370631349565427800972434165100944213038448250274326828594322342022449855379423340174278552163361661239365

    d = owiener.attack(e, n)
    print('d =', d)

    m = pow(c, d, n)
    flag = long_to_bytes(m).decode()
    print(flag)

if __name__ == '__main__':
    main()

owienerをインストールしていなかったためpip install owienerをしたが動かなかった。

ここからcurl -O https://raw.githubusercontent.com/orisano/owiener/master/owiener.py
経由で取得するとowienerが使えるようになった。

picoCTF{proving_wiener_2635457}