X-MAS CTF 2018の復習をします。crypto全然解けなかったので自分への戒めも込めて別枠で復習。

Hanukkah

以下問題文。

Most of the old religions celebrate Christmas in one way or another!

hannukah.zip

とりあえずzipを展開すると、Hanukkah.py、pubkey.docx、flag.encという３つのファイルが入っていた。中身はそれぞれ以下のとおり。

Hanukkah.py

from Crypto.Util.number import isPrime
from random import getrandbits

def genKey(k):

    while True:
        r=getrandbits(k)
        while(r%2):
            r=getrandbits(k)

        p =  3 * r**2 +  2 * r + 7331
        q = 17 * r**2 + 18 * r + 1339
        n = p * q

        if(isPrime(p) and isPrime(q)):
            return (p,q) , n

def encrypt(m,pubkey):

    c=m**2 % pubkey
    return c

privkey,pubkey = genKey(256)

flag = open('flag.txt').read().strip()
while(len(flag)<125):
    flag+='X'
flag = int(flag.encode('hex'),16)

ct=encrypt(flag,pubkey)

with open('flag.enc','w') as f:
    f.write('ct = ' + str(ct))

with open('pubkey.txt','w') as f:
    f.write('pubkey = ' + str(pubkey))

with open('privkey.txt','w') as f:
    f.write('privkey = ' + str(privkey))

flag.enc

ct = 66888784942083126019153811303159234927089875142104191133776750131159613684832139811204509826271372659492496969532819836891353636503721323922652625216288408158698171649305982910480306402937468863367546112783793370786163668258764837887181566893024918981141432949849964495587061024927468880779183895047695332465

pubkey.docx

pubkey = 577080346122592746450960451960811644036616146551114466727848435471345510503600476295033089858879506008659314011731832530327234404538741244932419600335200164601269385608667547863884257092161720382751699219503255979447796158029804610763137212345011761551677964560842758022253563721669200186956359020683979540809

flag.encとpubkey.docxはそれぞれ、暗号文、公開鍵に相当する値なので、一旦放置して、Hanukkah.pyを見ていく。（特別短い値というわけでもなさそうなので。。。
Hanukkah.pyの中には、暗号化の処理と、鍵生成の処理の関数が存在していた。（復号用の関数は特になさそう）
encrypt()を見てみると、暗号化は $m^{2}\ (mod\ pubkey)$ となっているようだ。一見、RSAの公開鍵であるeを2にしたような処理かと思っていたが、 Rabin暗号であるという解釈が正しいらしい。

def encrypt(m,pubkey):
    c=m**2 % pubkey
    return c

genKey()を見ていく。genKey()のざっくりとした処理は、乱数 $r$ から素数 $p$ と素数 $q$ を生成し、素数 $p$ 、 $q$ を乗算した結果 $n$ を公開鍵として出力している。こちらも一見RSAにあるような処理だが、素数 $p$ 、 $q$ の生成の仕方が特徴的である。

def genKey(k):
    while True:
        r=getrandbits(k)
        while(r%2):
            r=getrandbits(k)
        p =  3 * r**2 +  2 * r + 7331
        q = 17 * r**2 + 18 * r + 1339
        n = p * q
        if(isPrime(p) and isPrime(q)):
            return (p,q) , n

とりあえず、乱数 $r$ を復元し、 $p$ 、 $q$ を求められるか試す。 $p$ と $q$ はそれぞれ以下のような二次方程式である。
　　 $p=3r^{2}+2r+7331$
　　 $q=17r^{2}+18r+1339$
また、Nは以下のような四次方程式になる。
　　 $N = p \times q = (3r^{2}+2r+7331) + (17r^{2}+18r+1339) = 51r^{4}+88r^{3}+128680r^{2}+134636r+9816209$
どうやらこのくらいの四次方程式ならsagemathで簡単に解けるらしい。

r = var('r')
p =  3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339
n = 577080346122592746450960451960811644036616146551114466727848435471345510503600476295033089858879506008659314011731832530327234404538741244932419600335200164601269385608667547863884257092161720382751699219503255979447796158029804610763137212345011761551677964560842758022253563721669200186956359020683979540809
print(solve([p*q == n], r))

実行結果は以下のようになった。

$ sage solve.sage
[
r == -1/306*2^(1/3)*(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3)*(I*sqrt(3) + 1) - 4374650985893276104010003272325976898933572037179781744103021230488477995911375200505744036399526360125671364924951827208525285830472388678182701342414992024/153*2^(2/3)*(I*sqrt(3) - 1)/(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 2957921900893691988152446008625867048893493730601028771719173070390091206938194/153,
r == -1/306*2^(1/3)*(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3)*(-I*sqrt(3) + 1) + 4374650985893276104010003272325976898933572037179781744103021230488477995911375200505744036399526360125671364924951827208525285830472388678182701342414992024/153*2^(2/3)*(I*sqrt(3) + 1)/(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 2957921900893691988152446008625867048893493730601028771719173070390091206938194/153,
r == 1/153*2^(1/3)*(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 8749301971786552208020006544651953797867144074359563488206042460976955991822750401011488072799052720251342729849903654417050571660944777356365402684829984048/153*2^(2/3)/(153*sqrt(15147150630629000233804099452906101530934498191519647372356855149628789898185342413449836545900924662176230915294233370033963114644930012543565154246564399307994638439115638993183241400679583377149678122807648637577134435844295862489220640130051235448412196666616140954176530088660572814324543526976182025566317867574806379719140477173890301822047212775915209877434199260588836314486598090996510297680974690331976003346468620814300052353074520740824643178183803211195)*sqrt(51) - 129398759599399029878538864574409097631593624315136752522578442202900377311534041642773374695881782587166702224211678308439051036481714875871713370811022131963402610901118373474257540602240876772216885599860605597381607467985074933522361)^(1/3) - 2957921900893691988152446008625867048893493730601028771719173070390091206938194/153,
r == 57998468644974352708871490365213079390068504521588799445473981772354729547806
]

これで $r$ が57998468644974352708871490365213079390068504521588799445473981772354729547806であることがわかったので、 $p$ 、 $q$ がそれぞれ以下のように求められる。

r = 57998468644974352708871490365213079390068504521588799445473981772354729547806
p =  3 * r**2 +  2 * r + 7331
q = 17 * r**2 + 18 * r + 1339

Rabin暗号の復号は次のように行われるらしい。
暗号文を $y$ とし、次の2つの連立方程式の解 $x$ が求める平文になる。このとき、暗号文は単射ではないため、復号の際に一意に平文を求めることができないそうだ。
　　 $x^{2}+Bx-y=0\ (mod\ p)$
　　 $x^{2}+Bx-y=0\ (mod\ q)$
上記の方程式には4つの解が求まるが、4個の解から正しい平文を特定することはできない。正しい平文が求められるには、平文に十分な冗長度を持たせるなどの条件が必要となるそうな。具体的には、
　　 $x_{p}=(y+\frac{B^{2}}{4})^{(p+1/4)}-\frac{B}{2}\ mod\ p$
　　 $x_{p}=(y+\frac{B^{2}}{4})^{(q+1/4)}-\frac{B}{2}\ mod\ q$
とすると、求める解 $x$ は、
$(a,b)\ in\$ { $(x_{p}, x_{q}),\ (p-B-x_{p},x_{q}),(x_{p}, q-B-x_{q}),(p-B-x_{p},q-B-x_{q})$ }
の4組を中国の剰余定理により、 $x=a\ mod\ p,\ x=b\ mod\ q$ として求めるらしい。
ここでRabin暗号の暗号化について再度確認する。暗号化は次の通りである。
　　 $e(x)=x(x+B)\ mod\ n$ (ただし、 $p\equiv q\equiv 3$ ( $n$ をブラム数)、 $\leq B \leq n-1$ とする)
Hanukkah.pyのencrypt()による処理はc=m**2 % pubkeyであった。つまり今回は $B$ が0であるということがわかる。（ $B$ は単純に0とすることもできるため、Bを省略する場合もある）
よって、今回は $x_{p}$ 、 $x_{q}$ はそれぞれ以下のように求めることができる。

x_p = pow(ct, (p + 1) // 4, p)
x_q = pow(ct, (q + 1) // 4, q)

ここで、mの候補が４つになる。
$(a,b)\ in\$ { $(x_{p}, x_{q}),\ (p-B-x_{p},x_{q}),(x_{p}, q-B-x_{q}),(p-B-x_{p},q-B-x_{q})$ } の4組を中国の剰余定理により、 $x=a\ mod\ p,\ x=b\ mod\ q$ として求め、FLAGとして読めるものを選ぶ。以下をsageで実行する。

p = 10091467095486219386412925657038008994079750950818412327803970543226016138203830244281982855685318564926478052110051579561412412195187526673196657177343851
q =  57184980207755243189673245389882050966451922054637669857555833078280758116488758040722202677901531011185810382486226074211480927769032477693263422201893659
x_p = 5984384930362230902622118946606281088100185956715787357946688873976535748331735942467243660980295803795793201525873387182929644912620353687562775589288159
x_q =  9829161971938290069494314061938280901130884226712253442619690608876562799446658151136035886370379982653275907790319650566077618427448116797862433732627431
p_x_p = 4107082165123988483790806710431727905979564994102624969857281669249480389872094301814739194705022761130684850584178192378482767282567172985633881588055692
q_x_q =  47355818235816953120178931327943770065321037827925416414936142469404195317042099889586166791531151028532534474695906423645403309341584360895400988469266228

print(crt(x_p, x_q, p, q))
print(crt(p_x_p, x_q, p, q))
print(crt(x_p, q_x_q, p, q))
print(crt(p_x_p, q_x_q, p, q))

実行結果は以下のようになった。

$ sage solver.sage
546904478187754617970476928307782831327662789934115652310999639566732839911154963774037436727833744857683073603504302262536438011729853379642182939993673573801255216023647104887795195253938148646971787123118542563618966430816768768434049464197145400517827633353737734261878904557678614372825691067991025965824
577080342431875103050291541129748237695113048455522768672372116789787568249258449241136894862701032937391075692141058011928319000460264136464333583431446340765331120449009860869563031779240441024465326440106737207865005885016572835407784127138753408938519915029770041431424636487675561808249848130301475549425
3690717643400668910831063406341503098095591698055476318681557942254342027053896194996178473071268238319590774518398915404078477108468086016903753823835938265159657686994321225312921279358286372779396518771582790273013231775355353085206258352613158049531072716590828927233993638378706510890382503991384
30175867934838128480483523653028812708953356616998814416848795904612670592445512520995653131045761150976240408227530267790796392808887865290236660341526590800014169585020442976089061838223571735779912096384713415828829727213035842329087748147866361033850331207105023760374659163990585814130667952692953574985

$(a,b)in(x_{p}, q-B-x_{q})$ による $x=a\ mod\ p,\ x=b\ mod\ q$ を読める形に直しておわり。

$ python3
>>> s = 3690717643400668910831063406341503098095591698055476318681557942254342027053896194996178473071268238319590774518398915404078477108468086016903753823835938265159657686994321225312921279358286372779396518771582790273013231775355353085206258352613158049531072716590828927233993638378706510890382503991384
>>> bytes.fromhex(hex(s)[2:]).decode().rstrip('X')
'X-MAS{H4nukk4h_Rabb1_and_Rab1n_l0ok_4nd_s0und_v3ry_much_alik3_H4nukk4h}'

FLAGはX-MAS{H4nukk4h_Rabb1_and_Rab1n_l0ok_4nd_s0und_v3ry_much_alik3_H4nukk4h}。

所感

Rabin暗号を少し理解することができた。
sagemath便利なのでもっといい感じに使っていきたい。
他のcryptoも復習する予定で別枠で記事にしたのだが疲れたので気が向いたら更新するかも。

Special Christmas Wishlist (Crypto)

以下問題文。

While Santa was looking through the wishlists of the childern all around the world he came across a very strange looking one. Help Santa decode the letter in order to fulfill the wishes of this child.

(Flag is Non-Standard)

wishlist.png

UPDATE: flag is lowercase!

wishlist.pngは以下のような画像である。
f:id:kent056-n:20181225212142p:plain
時々でる換字式暗号の類であると推測できる。この手の問題は頻度分析をしなければならない印象があり、敬遠しがちだったが今回は他の人の解き方を見ながら復習してみる。
とりあえず、以下の画像の上から6行分のみをアルファベットに順に対応させていく。 f:id:kent056-n:20181225212639p:plain すると、このような具合になる。

ABCDCEFG AHIJDCEFG KHELG LDJI
JDMBNNG NBODAP QHHRGIFL
KCOA QGGM JABLLGL LGC HN CSH
QBF FHJ SDLFHO CEOQAGML
BFTGICEMGM OEACDCHHA UADV SBCUK
CSDJ OBMLKOBAAHS LRGSGM

ここまでできたら、quipqiupというツール？に入れてみる。実行結果はこんな感じ。 f:id:kent056-n:20181225213111p:plain 一番上の出力をいい感じに整形すると、以下のようになる。これで、謎の記号に適当にアルファベットを割り当てた状態から、いい感じにアルファベットを割り当てた状態になった。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO 
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIX WATCH 
TWIG MARSHMALLOW SKEWER

これより、NABJがFLAGに対応することがわかるので、その近辺のみを復号してFLAGを読み取れば終了。

LATITUDE LONGITUDE HOUSE SIGN
GIRAFFE FAMILY BOOKENDS
HTML BEER GLASSES SET OF TWO
BAD DOG WISDOM TUMBLERS
ADVENTURER MULTITOOL CLIP WATCH
TWIG MARSHMALLOW SKEWER
            :
THE FLAG IS
XMASYOUARESOGOODATSUBSTITUTIONCIPHERS

FLAGはX-MAS{xmasyouaresogoodatsubstitutionciphers}。