SSS

sorunun aciklamasini tam hatirlayamasam da lagrange’ dan bahsediliyordu.
ayrica ekte asagidaki grafik de vardi.
lagrange.

gayet duzgun aciklanmis duz bir soru aslinda. grafikte bize x’lere karsilik gelen y’ler verilmis.
fonksiyonun x=0 noktasinda degerini bulmamiz isteniyor. bunun icin lagrange interpolasyonu kullanicam.

(lagrange interpolasyonu referans icin:
http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html)

  1. resimde hex olarak verilen degerleri integere cevir
  2. lagrange polinomu olustur
  3. aradigimiz x degerini polinoma uygula (x=0)
  4. ciktidaki integer degeri asciiye cevir.

soru icin yazdigim python scripti: (sadece 3 nokta ile ugrasacagimiz icin lagrange fonksiyonunu yazmaya ugrasmadim.)

#!/usr/bin/python
import binascii

y0hex = "4612c90f5d8cd5d616193257336d92af1f66df92443b4ee69f5c885f0173ad80113844e393d194e3"
y1hex = "8c25921e46b03e48b7cbe94c3267f41adf618abd16422f660b59df6fae81e8aff2242852be33db49"
y2hex = "d2385b2d2fd3a6bb597ea041316255869f5c35e7e8490fe5775736805b9023dfd3100bc1e89621af"

y0 = int(y0hex, 16)
y1 = int(y1hex, 16)
y2 = int(y2hex, 16)
x0=1
x1=2
x2=3
x=0
p=y0*(((x-x1)*(x-x2))/((x0-x1)*(x0-x2)))+y1*(((x-x0)*(x-x2))/((x1-x0)*(x1-x2)))\
+y2*(((x-x0)*(x-x1))/((x2-x0)*(x2-x1)))

print binascii.unhexlify('%x' % p)
./solver.py
    timctf{b4s1C_l4gr4ng3_1NTerP0LatioN}

Those Are Rookie Numbers

klasik bir rsa problemi, soruda bize n e ve c sayilari verilmis.

n: 58900433780152059829684181006276669633073820320761216330291745734792546625247
e: 65537
c: 56191946659070299323432594589209132754159316947267240359739328886944131258862

n sayisi, iki asal sayinin carpimindan olusan public keyimizin parcasi. rsade guvenlik icin bu iki asal sayinin (p ve q olarak gecer cogunlukla) olabildigince buyuk olmasi gerekmektedir ki elimizdeki n sayisi geri dondurulebilir olmasin.
e sayisi, public exponent(us), cogunlukla 65537 olarak secilir, bu da public keyimizin diger parcasi.
c sayisi, cipherimiz.
mesaja m dersek cipheri su sekilde hesaplariz : (m^e) % n = c
cipher c iken de mesaji su sekilde hesaplariz : (c^d) % n = m
elimizde olmayan, d sayisi var ve buna ulastigimizda da soruyu cozmus oluyoruz.
fakat d sayisina ulasmak icin euler totient fonksiyonundan ve oklid algoritmasindan yararlanmamiz gerekir
ben ise once p ve q’ yu hesaplayarak basliyorum, bunun icin msieve adli programi kullaniyorum.
msieve verdigim sayiyi faktorlere ayiracak.

~/msieve/msieve 58900433780152059829684181006276669633073820320761216330291745734792546625247

p:176773485669509339371361332756951225661
q:333197218785800427026869958933009188427

p ve q’yu elde ettikten sonra euler totient fonksiyonu(φ)’ nun sonucunu bulmamiz gerekiyor.euler totient fonksiyonu bir sayinin, kendisinden kucuk, pozitif ve kendisi ile arasinda asal olan tam sayilarin sayisidir.
kisaca φ(n)=(p-1)(q-1)=(pq-p-q+1) seklinde ifade edilebilir.
son olarak d sayisina ihtiyacimiz var.
peki bu d sayisina nasil ulasilir?
bilmemiz gereken sey e*d % φ(n) = 1 esitligi. bu esitlikten d = (e^-1) % φ(n) sonucunu cikarabiliriz.
bu noktadan sonra d sayisini hesaplayabilmek icin genisletilmis oklid algoritmasi kullanilabilir.

soru icin yazdigim python scripti :

#!/usr/bin/python2
import gmpy2
import binascii

p =  333197218785800427026869958933009188427
q =  176773485669509339371361332756951225661
e =  65537
c =  56191946659070299323432594589209132754159316947267240359739328886944131258862
t = (p-1)*(q-1)
n = p*q

# d hesabi icin gmpy kutuphanesinden invert fonksiyonunu cagiriyoruz
# e * d == 1 % t esitliginden yararlanarak d sayisini donduruyor.
d = gmpy2.invert(e,t)
m = pow(c,d,n)

print binascii.unhexlify('%x' % m)
./solver.py
    timctf{th0sE_rOoKIe_numB3rz}

Not Your Average RSA

aslinda bir onceki soruyla neredeyse ayni soru.
yine bize n,e,c sayilari verildi.
fakat onceki sorudan farki biz onceki soruda p ve q dedigimiz iki farkli asal kullanarak sifrelememizi gerceklestirmistik. bu soruda standart rsa degil de multi prime rsa var, 2den fazla asal sayi kullanilarak elde edilmis bir key var diyebiliriz.
bizim icin degisen sey, n sayisindan cok sayida prime cikaricaz ve euler totient fonksiyonunun cok girdi alacak. geri kalan yontemler ayni.
elimizdeki sayilar
c: 2031862365927713378443686340515935099445788767434303946421766259516954715525216270775786037390459155888
0102908865139317161642898188843552485749556428171374190436116308993843078746618097974105761149153341729931
060530612128761115767471801348290177493316532913006382242873832659641556157675014368433683567068217
n: 1349075082402621379465020743607391030591109390231180556745683396752749787082164655502393951857976334959
7478804788032856041095660589589449780379729471563196393954647293905451269376232956364223073163592866593754
2607055460883018173012233396950213422702996807273870440698007181387418977498579818700406673368084937
e: 65537
n sayisini asal carpanlarina ayirmak icin yine msieve kullaniyorum

~/msieve/msieve 134907508240262137946502074360739103059110939023118055674568339675274978708216465550239395  
1857976334959747880478803285604109566058958944978037972947156319639395464729390545126937623295636422307316  
3592866593754260705546088301817301223339695021342270299680727387044069800718138741897749857981870040667336  
8084937

msieve’nin urettigi carpanlari asagidaki formata aliyorum ve devam ediyorum

cat factors.txt
42125267
49833439
58693039
61513877
39347927
39752197
40912577
41726467
43841219
48967511
50211853
55280663
56437529
56476139
56763647
59049911
60435281
60924557
61330141
64954529
66976769
34863589
35558351
39792197
40186049
41546803
41606921
42060289
42776633
43820687
46715131
49267469
49542749
52120109
59268661
61304303
64529057
65171647
65436601
66385931

elimde 40 adet asal carpan bulunmakta.
φ(n)=(p1-1)(p2-1)(p3-1)… esitligini kullanarak φ(n) sayisina ulasabilirim.
φ(n)=1349074978389125669289993857479598254415480913911217034383410027057358075700177182786696343063928106446381
853154933095007858301809954149259314577538428403767506327612959009949203559860516180569354834269977007244193779
05082592826930684594917646612003870921648344367047496409731018992994301773359753726010108672
buradan sonra degisen bir sey yok.
d’ye e
d % φ(n) = 1 esitliginden ulasip,
decryption icin (c^d) % n = m esitligini uygulayacagiz.

soru icin yazdigim python scripti :

#!/usr/bin/python2
import gmpy2
import binascii

e = 65537
c = 20318623659277133784436863405159350994457887674343039464217662595169547155252162707757860373904591558880102  
908865139317161642898188843552485749556428171374190436116308993843078746618097974105761149153341729931060530612  
128761115767471801348290177493316532913006382242873832659641556157675014368433683567068217  
n = 13490750824026213794650207436073910305911093902311805567456833967527497870821646555023939518579763349597478  
804788032856041095660589589449780379729471563196393954647293905451269376232956364223073163592866593754260705546  
0883018173012233396950213422702996807273870440698007181387418977498579818700406673368084937  
t = 1 

with open('factors.txt', 'r') as file:
    for line in file:
        temp=int(line)-1
        t*=temp

d = gmpy2.invert(e,t)
m = pow(c,d,n)
print binascii.unhexlify('%x' % m)
./solver.py 
    timctf{mUlt1_PriM3_rS4_1t_iS}

Hush Hush

info: nc 89.38.210.129 6665

verilen servise baglanip collision bulmamiz istenmis.
ekte bir python kodu var, bu kod infoda belirtilen serverda calisan bir servis.
kullanicidan 2 ayri girdi bekleniyor, girdiler asagidaki fonksiyona sokuluyor:

def my_hash(x):
    global n
    x += "piper"
    x = int(x.encode('hex'), 16)
    for i in range(32):
        x = pow(x, x, n)
        x +=1
    m = md5.new()
    m.update(hex(x))
    return m.hexdigest()

asagidaki kod blogunda da kontrolu saglaniyor:

input1 = self.receive("First input: ")
input2 = self.receive("Second input: "

hash1 = my_hash(input1)
hash2 = my_hash(input2)

if hash1 == hash2  and input1 != input2:
    print "flag"
    self.send("Thix will never be printed anyway, " + FLAG)
else:
    self.send("Told ya!")

girdiler farkli oldugu halde md5 hashlenmis halleri ayni olacak, kisaca md5 collision yaratin demis.
sorudaki numara hash fonksiyonundaki girdinin kontrol edilmemesinde yatiyordu.
gonderecegimiz stringin basina null byte ( \x00 ) ekleyip gonderdigimizde, hashler esit ancak inputlar farkli olacakti.

(printf ""; cat - ; printf "\x00") | nc 89.38.210.129 6665
Hello stranger!
Nobody can break my hash but you are free to try.
First input: Second input: Thix will never be printed anyway, timctf{d0UbT_3verYTH1nG}