Low Public-Exponent Attack

0. Low Public-Exponent Attackとは

こんにちは。普段競技プログラミングや数学をしている中学3年生のもちもちです。最近CTFをはじめたので新しい攻撃手法を知った際にこれからメモもかねて記事にしていこうかなと思っています。早速本題に入ります
Low Public-Exponent Attackとはその名の通りRSA暗号の公開鍵eが十分小さいときに使える攻撃手法です。RSA暗号の定義より$C≡M^e mod N$なので$M<\sqrt[e]{N}$のとき$M^e<N$より先ほどの$C≡M^e mod N$の式は$mod N$の影響を受けることがなくなり、$C=M^e$となるので$M=\sqrt[e]{C}$となり、高速に復号ができるようになりました。

1. 環境

• Windows10
• Windows Subsystem for Linux 2(WSL2)

まだWLS2を導入してないのであれば以下のサイトが参考になると思います。
Windows 10でLinuxを使う(WSL2)

2. gmpy2のインストール

現在$M=\sqrt[e]{C}$を求めたいのでgmpy2という非常に大きな数を計算するのに役に立つライブラリであるGNU Multi-Precision Library（GMP)のPython用のラッパーです。以下のコマンドを打つだけでインストールできます。

$ sudo apt-get update
$ sudo apt install python3-pip
$ pip install pycrypto
$ sudo apt-get install python3-gmpy2

今回使う関数は以下を使用します

a,b=gmpy2.iroot(c,e)
#aにはcのe乗根号が整数で返されてbにはcのe乗根号が整数であったかがbool型で返される

3. 実装

ここでは初心者向けのCTFの問題がまとめられたPICOCTFというサイトののMini RSAという問題を解いていこうと思います。

問題文

What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let's decrypt this:
ようするにeが十分に小さいときに復号してねって問題です。注意しなければいけないところは$M^e$がわずかに$N$よりも大きいということです。つまりはじめに紹介した方法だけではこの暗号を解けないことになります。そこで生きてくるのが先ほどの

a,b=gmpy2.iroot(c,e)

で返されるbool型のbの値です。"わずかに大きい"ので$C+εN=M^e$と置くことができます。これらよりこの問題は$b$が$true$になるまで$C$に$N$を足しながら$M=\sqrt[e]{C+εN}$をし続けることで解けることがわかりました。

解答例

import gmpy2


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


def LPA(c, e, n):
    while(True):
        m, b = gmpy2.iroot(c, e)
        if b:
            break
        else:
            c += n
    return int(m)


def main():
    n = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
    e = 3
    c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808154521995312832362835648711819155169679435239286935784452613518014043549023137530689967601174246864606495200453313556091158637122956278811935858649498244722557014003601909465057421728834883411992999408157828996722087360414577252630186866387785481057649036414986099181831292644783916873710123009473008639825720434282893177856511819939659625989092206115515005188455003918918879483234969164887705505900695379846159901322053253156096586139847768297521166448931631916220211254417971683366167719596219422776768895460908015773369743067718890024592505393221967098308653507944367482969331133726958321767736855857529350486000867434567743580745186277999637935034821461543527421831665171525793988229518569050
    # decode()に合わせるためにmをバイト列に直す
    m = LPA(c, e, n)
    # 整数mをバイト列に変換した後でコードして文字間をつめる
    flag = int_to_bytes(m).decode().strip()
    print(flag)


if __name__ == '__main__':
    main()

実行結果

$ python3 LPA.py
picoCTF{e_sh0u1d_b3_lArg3r_a166c1e3}

参考文献
https://security-blog-it.com/6815/
https://tsalvia.hatenablog.com/entry/2021/04/08/110000#Mini-RSA---70-points
(Pythonの実装力はまだまだ弱いので参考にさせていただきました。ありがとうございます)