CTF日本語サイト : BCTF 2016

Special RSA Score: 200
crypto

While studying and learning RSA, I knew a new form of encryption/decryption with the same safety as RSA.

I encrypted msg.txt and got msg.enc as an example for you.
$ python special_rsa.py enc msg.txt msg.enc
Can you recover flag.txt from flag.enc?

special_rsa.zip.f6e85b8922b0016d64b1d006529819de

ファイルを解凍すると次のファイルができます。

flag.enc
msg.enc
msg.txt
special_rsa.py

special_rsa.pyのencrypt処理より、mを平文、cを暗号文とすると、次のとおり表せます。

k ^ r * m ≡ c (mod N)

また、msg.txtよりm、msg.encよりr,cを取得することができます。実際に取得すると、2組の(m1, c1, r1)と(m2, c2, r2)を得ることができます。

c1 = 14548997380897265239778884825381301109965518989661808090688952232381091726761464959572943383024428028270717629953894592890859128818839328499002950828491521254480795364789013196240119403187073307558598496713832435709741997056117831860370227155633169019665564392649528306986826960829410120348913586592199732730933259880469229724149887380005627321752843489564984358708013300524640545437703771424168108213045567568595093421366224818609501318783680497763353618110184078118456368631056649526433730408976988014678391205055298782061128568056163894010397245301425676232126267874656710256838457728944370612289985071385621160886
m1 = 8246074182642091125578311828374843698994233243811347691229334829218700728624047916518503687366611595562099039411430662968666847086659721231623198995017758424796091810259884653332576136128144958751327844746991264667007359518181363522934430676655236880489550093852524801304612322373542296281962196795304499711006801211783005857297362930338978872451934860435597545642219213551685973208209873623909629278321181485010964460652298690058747090298312365230671723790850998541956664376820820570709272500330966205578898690396706695024001970727864091436518202414166919020415892764617055978488996164642229582717493375419993187360
r1 = 12900676191620430360427117641859547516838813596331616166760756921115466932766990479475373384324634210232168544745677888398849094363202992662466063289599443
c2 = 12793942795110038319724531875568693507469327176085954164034728727511164833335101755153514030256152878364664079056565385331901196541015393609751624971554016671160730478932343949538202167508319292084519621768851878526657022981883304260886841513342396524869530063372782511380879783246034751883691295368172069170967975561364277514063320691930900258017293871754252209727301719207692321798229276732198521711602080244950295889575423383308099786298184477668302842952215665734671829249323604032320696267130330613134368640401070775927197554082071807605399448960911234829590548855031180158567578928333030631307816223152118126597
m2 = 15575051453858521753108462063723750986386093067763948316612157946190835527332641201837062951012227815568418309166473080588354562426066694924364886916408150576082667797274000661726279871971377438362829402529682825471299861814829463510659258586020732228351258291527965822977048954720558973840956731377322516168809373640494227129998871167089589689796024458501705704779109152762373660542684880052489213039920383757930855300338529058000330103359636123251274293258
r2 = 7718975159402389617924543100113967512280131630286624078102368166185443466262861344357647019797762407935675150925250503475336639811981984126529557679881059

従って、これらの値からkを求めることができれば、flag.encを復号することができます。
さて、ここで、中国の剰余定理、整数の合同による性質を利用しkを求めます。整数の合同については、下記のサイトが分かりやすいです。
http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Cong.html

2組の(m1, c1, r1)と(m2, c2, r2)について、次の式が成り立ちます。

k ^ r1 * m1 ≡ c1 (mod N)
k ^ r2 * m2 ≡ c2 (mod N)

m1とNの最大公約数が1、m2とNの最大公約数が1であるため、次のように変形できます。

k ^ r1 ≡ c1 / m1 (mod N)
k ^ r2 ≡ c2 / m2 (mod N)

合同による乗算により、次のようになります。

(k ^ r1) * (r ^ r2) ≡ (c1 / m1) * (c2 / m2) (mod N) ・・・①

ここで、factordbでr1、r2について調べると、共に素数であることが分かります。
従って、r1とr2は互いに素なので、適当な整数(a,b)が存在し、

a * r1 + b * r2 = 1

が成り立ちます。式を変形して、

r2 = (1 - a * r) / b ・・・②

②を①に代入して、いろいろ変形すると、

k ≡ (c1 / m1) ^ a * (c2 / m2) ^ b (mod N)

となります。
ここまできたら、Pythonを基盤とした数式処理システムSageMathCloudで、下記のコードにより求めます。

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

N = 23927411014020695772934916764953661641310148480977056645255098192491740356525240675906285700516357578929940114553700976167969964364149615226568689224228028461686617293534115788779955597877965044570493457567420874741357186596425753667455266870402154552439899664446413632716747644854897551940777512522044907132864905644212655387223302410896871080751768224091760934209917984213585513510597619708797688705876805464880105797829380326559399723048092175492203894468752718008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131
c1 = 14548997380897265239778884825381301109965518989661808090688952232381091726761464959572943383024428028270717629953894592890859128818839328499002950828491521254480795364789013196240119403187073307558598496713832435709741997056117831860370227155633169019665564392649528306986826960829410120348913586592199732730933259880469229724149887380005627321752843489564984358708013300524640545437703771424168108213045567568595093421366224818609501318783680497763353618110184078118456368631056649526433730408976988014678391205055298782061128568056163894010397245301425676232126267874656710256838457728944370612289985071385621160886
m1 = 8246074182642091125578311828374843698994233243811347691229334829218700728624047916518503687366611595562099039411430662968666847086659721231623198995017758424796091810259884653332576136128144958751327844746991264667007359518181363522934430676655236880489550093852524801304612322373542296281962196795304499711006801211783005857297362930338978872451934860435597545642219213551685973208209873623909629278321181485010964460652298690058747090298312365230671723790850998541956664376820820570709272500330966205578898690396706695024001970727864091436518202414166919020415892764617055978488996164642229582717493375419993187360
r1 = 12900676191620430360427117641859547516838813596331616166760756921115466932766990479475373384324634210232168544745677888398849094363202992662466063289599443
c2 = 12793942795110038319724531875568693507469327176085954164034728727511164833335101755153514030256152878364664079056565385331901196541015393609751624971554016671160730478932343949538202167508319292084519621768851878526657022981883304260886841513342396524869530063372782511380879783246034751883691295368172069170967975561364277514063320691930900258017293871754252209727301719207692321798229276732198521711602080244950295889575423383308099786298184477668302842952215665734671829249323604032320696267130330613134368640401070775927197554082071807605399448960911234829590548855031180158567578928333030631307816223152118126597
m2 = 15575051453858521753108462063723750986386093067763948316612157946190835527332641201837062951012227815568418309166473080588354562426066694924364886916408150576082667797274000661726279871971377438362829402529682825471299861814829463510659258586020732228351258291527965822977048954720558973840956731377322516168809373640494227129998871167089589689796024458501705704779109152762373660542684880052489213039920383757930855300338529058000330103359636123251274293258
r2 = 7718975159402389617924543100113967512280131630286624078102368166185443466262861344357647019797762407935675150925250503475336639811981984126529557679881059

g, a, b = egcd(r1, r2)
k = pow((c1 / m1) % N, a, N) * pow((c2 / m2) % N, b, N)
print k

実行すると、kが求まります。

k = 175971776542095822590595405274258668271271366360140578776612582276966567082080372980811310146217399585938214712928761559525614866113821551467842221588432676885027725038849513527080849158072296957428701767142294778752742980766436072183367444762212399986777124093501619273513421803177347181063254421492621011961

kがわかりましたので、次のPythonプログラムによりflag.encより平文を求めます。

import msgpack

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    assert g == 1
    return x % m

def pad_even(x):
    return ('', '0')[len(x)%2] + x

def decrypt(c, k):
    out = ''
    for r_s, c_s in msgpack.unpackb(c):
        r = int(r_s.encode('hex'), 16)
        c = int(c_s.encode('hex'), 16)
        k_inv = modinv(k, N)
        out += pad_even(format(pow(k_inv, r, N) * c % N, 'x')).decode('hex')
    return out

N = 23927411014020695772934916764953661641310148480977056645255098192491740356525240675906285700516357578929940114553700976167969964364149615226568689224228028461686617293534115788779955597877965044570493457567420874741357186596425753667455266870402154552439899664446413632716747644854897551940777512522044907132864905644212655387223302410896871080751768224091760934209917984213585513510597619708797688705876805464880105797829380326559399723048092175492203894468752718008631464599810632513162129223356467602508095356584405555329096159917957389834381018137378015593755767450675441331998683799788355179363368220408879117131
k = 175971776542095822590595405274258668271271366360140578776612582276966567082080372980811310146217399585938214712928761559525614866113821551467842221588432676885027725038849513527080849158072296957428701767142294778752742980766436072183367444762212399986777124093501619273513421803177347181063254421492621011961
print decrypt(open("flag.enc").read(), k)

実行すると、フラグが表示されます。
フラグは、

BCTF{q0000000000b3333333333-ju57-w0n-pwn20wn!!!!!!!!!!!!}

です。

数学ガール/フェルマーの最終定理 (数学ガールシリーズ 2) [単行本]

結城浩

SBクリエイティブ

2008-07-30

catvideo Score: 150
forensic

cat_video.mp4

ダウンロードした動画を再生すると、砂嵐様の画面が表示されます。

よく見ると微妙な動きがあるので、フレームごとの画像イメージをファイルに抽出して、フレーム間の差分を取ってみます。動画から画像イメージを抽出するのにFree Video to JPG Converterを使います。
http://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm

イメージを抽出したところ1922フレームありました。それでは、フレーム間の差分をとります。ImageJを使い、対象となる画像ファイルを2つ開いて「Process」→「Image Calculator」でOperationにXORを指定します。