N1CTF 2019 Crypto Writeup(+1) Crypto道場四[6/100]

どうも。duckです。
N1CTFも解いてました。

Cryptoが2題あったなか1題だけ解けた(悔しい)のでWriteup書きます。

Part3-BabyRSA
なんでPart3なんだとかツッコミはいろいろあるけど解いていきましょう。
配られたファイルはこちら。

暗号化
Dropbox - BabyRSA.py - Simplify your life
暗号文
Dropbox - flag.enc - Simplify your life

短いので暗号化のpythonファイルははっちゃいます。

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
from Crypto.Util import number
import random
from secret import flag
N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
m = number.bytes_to_long(flag)
with open('flag.enc', 'w') as f:
    while m:
        padding = random.randint(0, 2**1000) ** 2
        message = padding << 1 + m % 2
        cipher = pow(message, e, N)
        f.write(hex(cipher)+'\n')
        m /= 2

平文bitを下から順に1bitずつパディング入れながら暗号化してるだけですね。
Nがめちゃでかいのと、パディングもめちゃでかいのでこれどーすんのって感じです。

Crypto問題は困ったら(というかいつもだいたい)紙に起こしてみるようにしてます。
ということで数式になおしちゃうぞ☆。

padding:p,random.randint...:r,message:M,cipher:cとおく。

p=r^2
M=2p+m
なので結局
c=(2r^2+m)^e {\rm mod}Nです。
重要なのがmは0or1ということです。

んんん?
mが0の時は大変なことが起きますね。
(2^e)^{-1}c= (r^e)^2{\rm mod}N
はい。平方剰余です。
平方剰余の相互法則がありますから
x^2=a {\rm mod} b
を満たすxが存在するかはすぐに判定できます。

つまり今回は(2^e)^{-1}cが平方剰余であるかどうかを調べるとmが0か1か判定できます。
計算にはSagemathを使いました。
コードはどっかに消えてしまったので見つかれば載せます。
すべてのchipherに対して平方剰余だったら0平方剰余でなかったら1を出力する用にfor文回すとかだったと思います。
下位ビットから求まっていくことに注意すれば解けました。

flag:N1CTF{You_can_leak_the_jacobi_symbol_from_RSA}

フラッグのjacobiはヤコビ記号のことです。平方剰余の時に出てきます。
ついでにいうとヤコビ記号の拡張としてルジャンドル記号もいます。たしか。