InCTF参加記:PolyRSA

本記事は旧ブログから移行しました

感想

  • なんか惜しいところまで行ったような気がするんだけど、そうでもなかったりする…

  • お久しぶりの方々にお会いできたのは嬉しかった。

  • 解けた人々によるwriteupはこちら

    • https://ctftime.org/event/981/tasks/
    • これを見ながら、自分でも再現できる手順を書きます。

PolyRSA

  • 「これ、研究で某暗号をやった人間として、できなきゃあかんやつ…」と思いつつトライ。大体の方針は立つのに細かいところで動けないのはやはり理解していないのでは?という話はさておき。

自分がたどり着いたところ

  • まずはじめに、作問者からpとnとm^eとeが与えられている。

    • RSAのの性質の式をこねってmを出す典型問題というストーリーはわかる。
  • ちょっとRSAについて復習

[人物]
公開鍵(n, e)
秘密鍵 d
メッセージ m
暗号文 c = m^e
作成途中で出てくる機密情報的なもの p, q

[性質]
n = p * q (ただしpとqは素数, p!= q)
e*d = 1 % (p-1)(q-1)
m = (m^e)^ d % n

与えられたものを見る
p = 2470567871
n = めっちゃ長い多項式
q = 不明
=> この時点で、RSA暗号の特徴よりn = p * qのため計算できるはずだが、多項式でだるくされている

e = 65537
c = m^e = めっちゃ長い多項式
d = 秘密鍵、知りたい。

[引用]

元ネタは、学位論文(何…だと!!)の Polynomial based RSA http://www.diva-portal.se/smash/get/diva2:823505/FULLTEXT01.pdf

  • 元ネタの論文を読む。多項式でもRSAの性質満たすねーというざっくりとした理解をした。

  • 多項式の計算にはSageMathというライブラリが使えそうなので、ubuntuにインストールする。

  • おや、ところで問題文にも"sage"の文字列がありますね、核心っぽい。

  • SageMathは多項式の計算をやってくれるライブラリ。時間かかるのかなと思ったけれど、全然そんなことはなかった。すごい。有能。というか大学の試験でこれ使ったら一瞬で終わりそう。

  • 試しに使ってみる

sage: P = PolynomialRing(GF(2), 'x')
sage: d = P(x^203 + x^202 + x^201 + x^200 + x^199 + x^196 + x^194 + x^193 + x^
....: 192 + x^191 + x^190 + x^188 + x^187 + x^186 + x^185 + x^184 + x^183 + x^
....: 181 + x^180 + x^178 + x^177 + x^173 + x^171 + x^170 + x^167 + x^165 + x^
....: 164 + x^163 + x^160 + x^159 + x^156 + x^155 + x^154 + x^153 + x^152 + x^
....: 150 + x^148 + x^146 + x^144 + x^143 + x^141 + x^139 + x^138 + x^137 + x^
....: 135 + x^134 + x^133 + x^130 + x^129 + x^126 + x^125 + x^123 + x^121 + x^
....: 119 + x^117 + x^116 + x^115 + x^114 + x^113 + x^108 + x^107 + x^104 + x^
....: 101 + x^99 + x^98 + x^96 + x^95 + x^89 + x^88 + x^84 + x^78 + x^74 + x^7
....: 3 + x^72 + x^71 + x^67 + x^65 + x^63 + x^61 + x^58 + x^57 + x^54 + x^53
....: + x^51 + x^50 + x^49 + x^47 + x^46 + x^44 + x^42 + x^40 + x^38 + x^37 +
....: x^36 + x^35 + x^34 + x^33 + x^31 + x^29 + x^28 + x^27 + x^23 + x^22 + x^
....: 21 + x^19 + x^17 + x^15 + x^12 + x^11 + x^10 + x^6 + x^5 + x^3 + x)
sage: print(d.factor())
x * (x + 1) * (x^2 + x + 1)^2 * (x^23 + x^21 + x^18 + x^17 + x^14 + x^11 + x^10 + x^9 + x^8 + x^5 + x^4 + x^3 + 1) * (x^57 + x^55 + x^53 + x^51 + x^47 + x^46 + x^42 + x^41 + x^39 + x^38 + x^36 + x^35 + x^33 + x^32 + x^30 + x^29 + x^28 + x^26 + x^25 + x^24 + x^21 + x^15 + x^13 + x^10 + x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1) * (x^117 + x^109 + x^108 + x^104 + x^102 + x^100 + x^99 + x^95 + x^91 + x^90 + x^88 + x^80 + x^73 + x^72 + x^71 + x^69 + x^68 + x^67 + x^60 + x^58 + x^57 + x^56 + x^50 + x^49 + x^48 + x^47 + x^43 + x^40 + x^35 + x^34 + x^33 + x^32 + x^31 + x^27 + x^25 + x^23 + x^20 + x^19 + x^18 + x^14 + x^13 + x^12 + x^10 + x^8 + x^3 + x + 1)
  • わーいわーい。よくわからないけどでき…でき…次…何しよう…
  • とりあえず適当に因数分解をしようと思ったが、ここでGFってあれだよね…有限体…2でいいのか?pかな…?と、ごちゃごちゃ古い記憶を取り出したりしていたら終了した。