shibak333333n

移転しました→　https://shibaken28.github.io/my-blog-4/

今年解いたCrypto問題を振り返る(2021年)

これはなに

こっそりいくつかのctfに参加したりあとから問題を覗いたりして，Crypto問題だけ解いてました．
今後似た問題と遭遇したときのために備忘録として書きます．

そして公開日が12/26のくせになんとアドベントカレンダー24日目の記事です．
qiita.com

全部で4問あります．

K3RN3LCTF - Pascal RSA

問題概要
triangle =[[1]]
flag = open('flag.txt','rb').read()

from Crypto.Util.number import getPrime,bytes_to_long
from math import gcd
p = getPrime(20)
while len(triangle[-1]) <= p:
    r = [1]
    for i in range(len(triangle[-1]) - 1):
        r.append(triangle[-1][i] + triangle[-1][i+1])
    r.append(1)
    triangle.append(r)
code = ''
for x in triangle[-1]:
    code+=str(x%2)
d = int(code,2)
while True:
    P = getPrime(512)
    Q = getPrime(512)
    if gcd(d, (P-1)*(Q-1)) == 1:
        N = P*Q
        e = pow(d,-1,(P-1)*(Q-1))
        break
enc = pow(bytes_to_long(flag), e, N)
file = open('challenge.txt','w')
file.write(f'p = {p}\nenc = {enc}\nN = {N}')

p = 751921
enc = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
N = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447
考えたこと

プログラムは，

  1. 素数$p$を元にtriangle二次元配列を作る
  2. それを使って$d$を作成
  3. 素数$P,Q$が生成され$N=PQ$，$e=d^{-1} \bmod N$として$enc = (flag)^{e} \bmod N$が計算される
  4. $p,enc,N$が出力

を行っていて，$(enc)^d= (flag)^ed =(flag)^1 \bmod N$を計算すれば$flag$が求まるので$d$が欲しい．

$d$は$triangle$配列の各数にパリティによって決定され，$triangle$はパスカルの三角形．
詳しくは，パスカルの三角形を$p+1$段作り，最下段の数のうち奇数を1,偶数を0として横に並べたものを左から2進数とみて，それを$d$としている．

ここで，$p=751921$がわかっているので，実際にパスカルの三角形を作って$d$が求められるが，$O(p^2)$かかるため非常に時間がかかる．
どうにかして$p+1$段目のみを直接計算する必要がありそう．
パスカルの三角形の意味を考えると，各数は二項係数になっているため，最下段は$_pC_i$を表している．
二項係数の偶奇，すなわち$2$で割ったあまりはルーカスの定理を使用すれば高速に求められる！

プログラム

ルーカスの定理の$\bmod 2$の場合はビット演算で$O(1)$で求められます．

p = 751921
enc = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
N = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447


def is_nCk_odd( n,k):
    return n&k == k

code=''
for i in range(0,p+1):
    ch=is_nCk_odd(p,i)
    if ch:
        code+='1'
    else:
        code+='0'

d=int(code,2)

print(hex(pow(enc,d,N)))

idek - Destroyed RSA

問題概要

RSA暗号で，各パラメータがわかります．

n=1107089530865291005792928480548189885479977703442107533313356742591951667125087535826010797157037462511849114045516095117408586807231706532861043400760247491545435256670371588020835746662537074526723641129179212527096161455117334264697975671817050553066298766943783138197527420889207777538892682506714149210612017224796083819420558023833783052917520724666512823601961316820680461331809092698744718706733677296285030329390980535993866209005527261307419128592439300515586162373258781346476786339580690681056167085317745381659204404735103663112312693895151699459534695810700103198736323229849182269856798173444808702578924983265251814786149856862410628895786620259450924651662102926294106305830166586486290823127164862167085238586221495862582249250498351063486438791642573599997108715545357001141390463446119948917429169048381714872075664706511363903028841832059662969788526342879432038294204060254076089346916015904423832151508649589004393115281760187305175538986217342069866841444503926477979016789070563231454129660241269241703644048193901022392096029852555194381071481792694321652042639278577632914177886450520371875549477493674646527815335341293227066407822982856815277497965140254717599437693337147736442753971955722420621907486011
p=36984002748507170891753731406126456416455992571790181677355704906806965226019238824877042494690893998579858694111411376511253440817505962720769835375650471685769471414118510774533150115499644554157393860475762756716310600646166773019267339855093152750395193553746652677602677776044436793635218677785744671419934810989547208990895631879209745428788589809123973606636033943819211438418326058364282178941980077621277854916308671126967906285068857212366779324466914715729553717164382649849824461928856952183975506817514230213608208371112629129318318247510911612301933407885682758975715426046251265646994864308390350130597
q=29934281002344392584917041715572452186213480993633769076547996710425134248100828277592343431170595254088836916660834689235026786084921641309257834412549082271979733777849147751813839475093849198230955115891279535391278974673199880605616268135363608516171875844412554370669853436778763238712799066154529158577804567624075485413272553162482452019391457208428519791195318467405021196329420684098999738549035239634242441609101096054948406319959608539620961927531536528883122477541022179797553950933620777436215821991811508533829734240459263426901285492628622233303498344386289944426215246507874026244979669057103099687263
e = 6551
c=1058973149865164549817155137780815812623456388672543624635614085499244505987561039674767711743995552767627702752408380616883846211075499731545623651849875151404363710832001498313789374024771997636035858261588415813326816005995068929381352608925142940988357078368871961040798086164564448858106053108740194519944625550651430368864502736439474454098320996590422347650921528404245531928248700516748854749201075928521539792773428322450795957658901093109369813686410937987553062385702498313602204488073904351501964183374202465473380985602391885101503608627656341003137115517005592591746184951205036757837506166599417314523057848473058411480339477693062957272869601856015496182168433136199994935250109784152100245527161736252507193119985157036229139371883973535111593404077185046749750799222687057579590699112612517984739574870394435873979331373499970168615775526148858445852147161884965435806142797327740412603655959161046424598064190354357612721920648035385092037901968197029138094288551013982417040611621259974923351358663093743109476722870043782424356300204605852351738436494837101112320000689343206094235482366575795725469918145189121430260345459865260920783660140849521053205162497433393126952425091234633490186637000777737106192645410
考えたこと

$\phi = (p-1)(q-1)$として$e^{-1} \bmod \phi$を求めようとするが，$\phi$と$e$が互いに素でないので$e$の逆元が存在しない．
けれども，いつものRSA暗号よりも$p$と$q$が大きく感じる．これより，$p,q$よりも平文が小さいと推測し，$\bmod p$の世界で考える．

プログラム

オイラーの$\phi$関数より$\phi=p(p-1)$です．

import binascii

phi =(p-1)*p
d=pow(e,-1,phi)
m=pow(c,d,p)
print(binascii.a2b_hex(hex(m)[2:]))
# idek{A_mashup_of_2_interesting_papers?_4p-1_and_coprime_e-phi}

idekCTF - Polyphenol

問題概要
import random
from secret import flag

assert flag[: 5] == b"idek{"
assert flag[-1:] == b"}"

L = len(flag[5: -1])
print(f"L = {L}")
coeff = list(flag[5: -1])
points = random.sample(range(L), L // 2)
evaluations = []

for p in points:
	evaluations += [sum(c * p ** i for i, c in enumerate(coeff))]

print(f"points = {points}")
print(f"evaluations = {evaluations}")

L = 34
points = [4, 26, 22, 30, 1, 0, 2, 28, 23, 6, 25, 15, 5, 17, 14, 3, 13]
evaluations = [6218619148819094267912, 3239660278168289094170378865781537878483145039862, 13167423991006904868698304825721530103488567362, 362300164581366743933077318596814390341728710066538, 2912, 68, 1115908868222, 37269531510352347514290324712333731253807861642016, 56973337294691266392513915302684316231304471586, 3613524058959314538010460402, 889396341293302641051808753025749133146757798168, 43685960244566626421146033917835089685178, 9183044381254551882537188, 2694648608589552169772471076958756166751152, 4505915953382938147124977926390455694362, 529597204775372366, 392892826701163426612412172019222254476]
考えたこと

プログラムが次のことをしている．

  1. フラグの長さ$L=34$
  2. 長さ$L/2$の配列$p$がランダムに生成される
  3. 各$p$について$\sum_i c_i\cdot p^i$が計算され，それがevaluations配列(以下要素を$e_j$とする)として出力される．$c_i$はflagの$i$文字目(0-indexed)

$i=0$のことを考えると，$c_i\cdot p^0$すなわち$c_i$がそのまま出力されている．
もし，$c_0$が確定したのなら，各$j$について，$e_j-c_0$は$p$で割り切れるはず．
よって$c_0$を全探索して，$e_j-c_0\bmod p=0$となる$c_0$を探せばいい．

これで$c_0$が判明すると，$e_j-c_0$は，
$$\cdots c_4\cdot p^4+c_3\cdot p^3+c_2\cdot p^2+c_1\cdot p^1$$
であるから，これを$p$で割って
$$\cdots c_4\cdot p^3+c_3\cdot p^2+c_2\cdot p^1+c_1\cdot p^0$$
となる．さっきと同じく$c_1$を引き算した値は$p$で割り切れればいいので，同じく$c_1$を全探索すればよい．
これを繰り返していけば全ての$c_i$が判明する．

プログラム
L = 34
points = [4, 26, 22, 30, 1, 0, 2, 28, 23, 6, 25, 15, 5, 17, 14, 3, 13]
evaluations = [6218619148819094267912, 3239660278168289094170378865781537878483145039862, 13167423991006904868698304825721530103488567362, 362300164581366743933077318596814390341728710066538, 2912, 68, 1115908868222, 37269531510352347514290324712333731253807861642016, 56973337294691266392513915302684316231304471586, 3613524058959314538010460402, 889396341293302641051808753025749133146757798168, 43685960244566626421146033917835089685178, 9183044381254551882537188, 2694648608589552169772471076958756166751152, 4505915953382938147124977926390455694362, 529597204775372366, 392892826701163426612412172019222254476]

flag=b''

for i in range(L):
    print(i)
    
    for c in range(128):
        ok = True
        for j,p in enumerate(points):
            if p==0:
                continue
            if (evaluations[j]-c)%p!=0:
                ok=False
        if ok:
            flag=flag+bytes([c])
            break
    
    print(flag)
    if len(flag)<=i:
        break
    
    for j,p in enumerate(points):
        if p==0:
            continue
        evaluations[j]=(evaluations[j]-flag[i]) // p

print(flag)

ASIS CTF Finals - stair

問題概要

インタラクティブ問題で，整数$ m $を与えると，
$(m+f)^5 + m+f \bmod N$の値が得られる．ただし，$N$は与えられていて，$f$が$flag$をエンコードした整数．

考えたこと

$m=0$をツッコめば$f^5+f \bmod N$がもらえるが，これだけでは$f$がわからない．
いろんな$ m $に対する値を求めて，差分を使えば$f$が求められそうに見える．
せいぜい5乗だから5個くらい連立すれば求められそう．
sagemathに連立合同方程式の解を求める機能があると嬉しいが，検索しても情報が見つからないので自力でやることにした(知っている方がいれば教えていただきたいです)．
$m=0,1,2,3,4$のときの値を使うと$120f +240 \bmod N$の値がわかるので，$240$を引いて$120$の逆元を掛け算すれば$f$が得られる．

プログラム

配列fは$m=0,1,2,3,4$にしたときの値です．

#R, t = QQ['t'].objgen()
#f=[]
#
#for i in range(5):
#    f.append( (t+i)**5 + t+i )
N=26988480498549621160245719900903773232840133632092297127594267334625529876976567682696748909369604307829651367885173095648610898772155393424116881932377221727862169668643423945930632234830754314591119837812803280535627188168965771909142681188203416675060421505442173186401565213575135378512462997278191411587241912090506266759586550889109151809874920511159366347810063459052745819442622154442058802011002148677617743211040695825214353014636602312764287004302711193427903045229183477950620693238823860006014265413878884235271462570833448784828338773641090407644755768854808432704391895324251672027902608709822270571071

f=[7678362696224158956701891820260394322994444797134797509334898256237146486825801472927211891948373682506250939990802637395815706180623415855149741953776176055751156241260147038974404936634988564631047217184263400661620152919050573840562356351476554657104647343763809819409861741939562400931934650138514735572988980993806819120866951461870234494460541725144896871734651790217891303509247078749652558277274167508705770696323811414745227700584203806687715766468950519359927358705878416874611802144155422995089769048614986692238802133901914397516042752676004147573266403361112062581792833558029226248737403199527438101506,
14788325360699107531306883919556661064144694519471445922375722388450018317715071448645425976259873338645456550465992743602233105598367448123297061726949072210596288375462294436390394768943351588656958020779127908522908375145662787356823775692477212852561741562973843495730657757120104974270301648537189578177935723642798567001071035939064945165499393719867511733557712586650030399158140495127084644514974254698883657787832456262952225317851149173187482987991183508960271215005204373037324993641153123036288642461886338701109931921696160086233560207701523685353360356073766738874059155880544426943413197189649763340469,
21898288025174056105911876018852927805294944241808094335416546520662890148604341424363640120308705001328139799218998060015220942233233701538823483287890909370769140314557114171968074199480696460085493743859515498285671834353430141248665625350519376847518062995201731923444520473050821056431972562163140276496932676822592113294620726369076656350511158871574580444106607129983841062022948596916098177172143748496868607261996723630121751958059224066318699169970404234748180746499874149125182858370225434592223825067602214818918707522969362030582810133458711106275622375979468758972194206769242862002115016442569191670002,
2019770191099383520271148217245421313605060332052445620863103318250232102517043717385105414725264362724649318364645490986168317313066782677612124704224465808407542389901182299776810993416268864325534548612622889414283342373386863606945224137399629966913190135005314360201431489751672235765133723328700215283026889601838380167605348282189309021862550825208429644683376091750387313918390873545491852150335373967558575026248766078766442683294484810240993392208645810520091041566321843792752435210298734407372786599215959432578668401548719075249453389171411072742265840059681198511185651880203553468467815910403957235784,
9129732855574332094876140316541688054755310054389094033903927450463103933406313693103319678248760038494287843673281227812297028382177478387896749840704184979235833938781346711677869620411577430559320110664056642979997275543464498249947934429524805560867965993268949622856068047968026236155360456180777014050991147320707090064873879876014299581545044759189485020020250520638970634987053277770240771384108302208704746621142823647041991599554522837644776555616935109506734178564089606937235925590812881349191169371998982998804490076888309687538840639371530995031780991087826941206924626040375611741008453199170472273187
]

f2=[]

for i in range(4):
    f2.append(f[i+1]-f[i])

f3=[]
for i in range(3):
    f3.append(f2[i+1]-f2[i])

f4=[]
for i in range(2):
    f4.append(f3[i+1]-f3[i])

f5=[]
for i in range(1):
    f5.append(f4[i+1]-f4[i])

# f5[0] = 120f +240

m=((f5[0] -240)*pow(120,-1,N))%N
print(hex(m))

あとがき

RSA暗号系はちょっとだけ慣れてきましたが，楕円曲線暗号やブロック暗号の問題はさっぱりです．来年はここらへんも理解できるようになりたい......