BuckeyeCTF crypto

補之前打BuckeyeCTF的wp，雖然拿到第41名，但是是靠caleb把web破台才那麼高的，crypto的部分只有解出四題。

megaxord/beginner

題目

Some pesky wizard stole the article I was writing. I got it back, but it’s all messed up now 😦

Hint: the wizard used the same magic on every character…

附件

因為太長了，而且是沒意義的字符，就放下載連結。

megaxord.txt

解題思路

題目有說是用同一種方式去xor的，所以就以xor的角度去爆，到0x58的時候可以看到明文，直接找到。但賽中是淺羽幫我解的，我只是晚幾個小時打QQ，太快了啦。

解答

data = open('megaxord.txt', 'rb').read()

for i in range(0, 0x59):
    c = bytes([v ^ i for v in data])
    print(i, c)

buckeye{m1gh7y_m0rph1n_w1k1p3d14_p4g3}

Twin prime RSA/easy

題目

Real winners use twin primes

附件

import Crypto.Util.number as cun

while True:
    p = cun.getPrime(1024)
    q = p + 2
    if cun.isPrime(q):
        break

n = p * q
e = 0x10001

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

FLAG = cun.bytes_to_long(b"buckeye{?????????????????????????????????????????????????????????????}")
c = pow(FLAG, e, n)
assert pow(c, d, n) == FLAG

print(f"n = {n}")
print(f"c = {c}")

"""
Output:
n = 20533399299284046407152274475522745923283591903629216665466681244661861027880216166964852978814704027358924774069979198482663918558879261797088553574047636844159464121768608175714873124295229878522675023466237857225661926774702979798551750309684476976554834230347142759081215035149669103794924363457550850440361924025082209825719098354441551136155027595133340008342692528728873735431246211817473149248612211855694673577982306745037500773163685214470693140137016315200758901157509673924502424670615994172505880392905070519517106559166983348001234935249845356370668287645995124995860261320985775368962065090997084944099
c = 786123694350217613420313407294137121273953981175658824882888687283151735932871244753555819887540529041840742886520261787648142436608167319514110333719357956484673762064620994173170215240263058130922197851796707601800496856305685009993213962693756446220993902080712028435244942470308340720456376316275003977039668016451819131782632341820581015325003092492069871323355309000284063294110529153447327709512977864276348652515295180247259350909773087471373364843420431252702944732151752621175150127680750965262717903714333291284769504539327086686569274889570781333862369765692348049615663405291481875379224057249719713021
"""

解題思路

$q = p + 2$，那就可以直接分解，有了p, q，接下來就RSA正常解密流程，本來以為是水題，沒想到是接下來難題的開胃菜。

解答

from Crypto.Util.number import long_to_bytes
from gmpy2 import gmpy2, iroot
from gmpy2 import mpz

n = mpz(20533399299284046407152274475522745923283591903629216665466681244661861027880216166964852978814704027358924774069979198482663918558879261797088553574047636844159464121768608175714873124295229878522675023466237857225661926774702979798551750309684476976554834230347142759081215035149669103794924363457550850440361924025082209825719098354441551136155027595133340008342692528728873735431246211817473149248612211855694673577982306745037500773163685214470693140137016315200758901157509673924502424670615994172505880392905070519517106559166983348001234935249845356370668287645995124995860261320985775368962065090997084944099)
c = mpz(786123694350217613420313407294137121273953981175658824882888687283151735932871244753555819887540529041840742886520261787648142436608167319514110333719357956484673762064620994173170215240263058130922197851796707601800496856305685009993213962693756446220993902080712028435244942470308340720456376316275003977039668016451819131782632341820581015325003092492069871323355309000284063294110529153447327709512977864276348652515295180247259350909773087471373364843420431252702944732151752621175150127680750965262717903714333291284769504539327086686569274889570781333862369765692348049615663405291481875379224057249719713021)
e = 0x10001

p = iroot(n, 2)[0]
q = p + 2

fn = (p - 1) * (q - 1)
d = gmpy2.invert(e, fn)
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))

buckeye{B3_TH3R3_OR_B3_SQU4R3__abcdefghijklmonpqrstuvwxyz__0123456789}

fastfor/medium

題目

Make the image different yet same!

https://fastfor.chall.pwnoh.io

附件

from PIL import Image
import numpy

def check_hash(fi):
    image = numpy.asarray(Image.open('static/IMG.png'))
    submission = numpy.asarray(Image.open(fi))
    if image.shape != submission.shape:
        return False
    same = numpy.bitwise_xor(image, submission)
    if (numpy.sum(same) == 0):
        return False
    im_alt = numpy.fft.fftn(image)
    in_alt = numpy.fft.fftn(submission)
    im_hash = numpy.std(im_alt)
    in_hash = numpy.std(in_alt)
    if im_hash - in_hash < 1 and im_hash - in_hash > -1:
        return True
    return False

解題思路

題目給了一張圖片，要求上傳的圖做傅立葉變換後再求出來的標準差與原圖相同，看起來就需要同一張圖，我直接把原圖轉180度丟上去就解掉了。

bonce/easy

題目

nonce without a cipher

附件

import random

with open('sample.txt') as file:
    line = file.read()

with open('flag.txt') as file:
    flag = file.read()

samples = [line[i:i+28] for i in range(0, len(line) - 1 - 28, 28)]

samples.insert(random.randint(0, len(samples) - 1), flag)

i = 0
while len(samples) < 40:
    samples.append(samples[len(samples) - i - 2])
    i = random.randint(0, len(samples) - 1)

encrypted = []
for i in range(len(samples)):
    x = samples[i]
    if i < 10:
        nonce = str(i) * 28
    else:
        nonce = str(i) * 14
    encrypted.append(''.join(str(ord(a) ^ ord(b)) + ' ' for a,b in zip(x, nonce)))

with open('output.txt', 'w') as file:
    for i in range(0, 4):
        file.write('input: ' + samples[i] + '\noutput: ' + encrypted[i] + '\n')
    file.write('\n')
    for i in range(4, len(samples)):
        file.write('\ninput: ???\n' + 'output: ' + encrypted[i])

加密後檔案前面大概是這樣，給了input和output。

input: Look in thy glass, and tell 
output: 124 95 95 91 16 89 94 16 68 88 73 16 87 92 81 67 67 28 16 81 94 84 16 68 85 92 92 16 
input: the face thou viewestNow is 
output: 69 89 84 17 87 80 82 84 17 69 89 94 68 17 71 88 84 70 84 66 69 127 94 70 17 88 66 17 
input: the time that face should fo
output: 70 90 87 18 70 91 95 87 18 70 90 83 70 18 84 83 81 87 18 65 90 93 71 94 86 18 84 93 
input: rm another;Whose fresh repai
output: 65 94 19 82 93 92 71 91 86 65 8 100 91 92 64 86 19 85 65 86 64 91 19 65 86 67 82 90 


input: ???
output: 70 20 93 82 20 90 91 67 20 64 92 91 65 20 90 91 64 20 70 81 90 81 67 81 71 64 24 96 
input: ???
output: 93 90 64 21 81 90 70 65 21 87 80 82 64 92 89 80 21 65 93 80 21 66 90 71 89 81 25 21 
input: ???
output: 67 88 84 90 83 69 69 22 69 89 91 83 22 91 89 66 94 83 68 24 112 89 68 22 65 94 83 68 
input: ???
output: 82 23 94 68 23 68 95 82 23 68 88 23 81 86 94 69 23 64 95 88 68 82 23 66 89 82 86 69 
input: ???
output: 218 8340 8474 92 24 79 87 85 90 124 81 75 92 89 81 86 75 24 76 80 93 24 76 81 84 84 89 95 

解題思路

與其說是加密，不如說更像逆向，但因為我很爛還是被卡很久。

解答

把每一題的下面都刪掉之後進行還原。

input: ???
output: 

with open('output.txt') as file:
    samples = file.read()

samples = samples.split('\n')
# print(samples)
encrypted = []
for i in range(4,20):
    x = samples[i-4].split(' ')
    if i < 10:
        nonce = str(i) * 28
    else:
        nonce = str(i) * 14

    # print(x)
    # print(nonce)
    print(''.join(chr(int(a) ^ ord(b)) + '' for a,b in zip(x, nonce)))

拿到以下內容。

r if now thou not renewest,T
hou dost beguile the world, 
unbless some mother.For wher
e is she so fair whose unear
â€:tm:d wombDisdains the tillag
e of thy husbandry?Or who is
 he so fond will be the tomb
Of his self-love, to stop po
sterity?Thou art thy motherâ
€:tm:s glass, and she in theeCa
lls back the lovely April of
 her prime:So thou through w
indows of thine age shall se
eDespite of wrinkles this th
y golden time.But if thou li
buckeye{some_say_somefish:)}

powerball/easy

這題開始補題，賽中沒做出來。

題目

What could go wrong using a Linear Congruential Generator to get some random numbers?

https://powerball.chall.pwnoh.io

附件

const socket = io() // eslint-disable-line no-undef
let seenFlag = false

function seedToBalls (n) {
  const balls = []
  for (let i = 0; i < 10; i++) {
    balls.push(Number(n % 100n))
    n = n / 100n
  }
  return balls
}

function handleUpdate (update) {
  console.log(update)

  if (update.flag && !seenFlag) {
    alert(update.flag)
    seenFlag = true
  }

  const balls = seedToBalls(BigInt(update.last_winning_seed))
  for (let i = 0; i < 10; i++) {
    document.getElementById(`ball${i}`).innerText = balls[i]
  }
}

function initSocket () {
  socket.on('update', handleUpdate)
  socket.emit('updateRequest')

  setInterval(() => {
    console.log(Date.now() / 1000)
    socket.emit('updateRequest')
  }, 5000)
}

function sendBallsIfAvailable () {
  const balls = []
  for (let i = 0; i < 10; i++) {
    const a = parseInt(document.getElementById(`input-ball${i}`).value)
    if (isNaN(a) || a < 0 || a >= 100) return
    balls.push(a)
  }
  console.log(`Submitting balls ${balls}`)
  socket.emit('submitBalls', balls)
}

function initInput () {
  for (let i = 0; i < 10; i++) {
    document.getElementById(`input-ball${i}`).onkeypress = (event) => {
      const n = parseInt(event.key)
      if (isNaN(n)) return false
      setTimeout(sendBallsIfAvailable, 100)
    }
    document.getElementById(`input-ball${i}`).onpaste = (event) => {
      const n = event.clipboardData.getData('Text')
      if (isNaN(n)) return false
      setTimeout(sendBallsIfAvailable, 100)
    }
  }
}

initSocket()
initInput()

解題思路

看出來是LCG，但就沒有然後了。(X)

https://en.wikipedia.org/wiki/Linear_congruential_generator

題目會給出前十個生成的數，然後讓你去推後十個數。

賽中一直沒有太好的思路，後來才知道他是簡化的LGC，然後求出p就好。

不過網站關了沒辦法補題，有點遺憾。

Quad prime RSA/medium

賽後補題，賽中沒想法輸光。

題目

Ok I learned from my mistake! I’ll just put my twin primes into separate RSA keys…

附件

import Crypto.Util.number as cun

p = cun.getPrime(500)

while True:
    q = cun.getPrime(1024)
    r = q + 2
    if cun.isPrime(r):
        break

s = cun.getPrime(500)

n_1 = p * q
n_2 = r * s

e = 0x10001
d_1 = pow(e, -1, (p - 1) * (q - 1))
d_2 = pow(e, -1, (r - 1) * (s - 1))

FLAG = cun.bytes_to_long(b"buckeye{??????????????????????????????????????????????????????????????????????}")
c_1 = pow(FLAG, e, n_1)
c_2 = pow(FLAG, e, n_2)

assert pow(c_1, d_1, n_1) == FLAG
assert pow(c_2, d_2, n_2) == FLAG

print(f"n_1 = {n_1}")
print(f"n_2 = {n_2}")
print(f"c_1 = {c_1}")
print(f"c_2 = {c_2}")

"""
Output:
n_1 = 266809852588733960459210318535250490646048889879697803536547660295087424359820779393976863451605416209176605481092531427192244973818234584061601217275078124718647321303964372896579957241113145579972808278278954608305998030194591242728217565848616966569801983277471847623203839020048073235167290935033271661610383018423844098359553953309688771947405287750041234094613661142637202385185625562764531598181575409886288022595766239130646497218870729009410265665829
n_2 = 162770846172885672505993228924251587431051775841565579480252122266243384175644690129464185536426728823192871786769211412433986353757591946187394062238803937937524976383127543836820456373694506989663214797187169128841031021336535634504223477214378608536361140638630991101913240067113567904312920613401666068950970122803021942481265722772361891864873983041773234556100403992691699285653231918785862716655788924038111988473048448673976046224094362806858968008487
c_1 = 90243321527163164575722946503445690135626837887766380005026598963525611082629588259043528354383070032618085575636289795060005774441837004810039660583249401985643699988528916121171012387628009911281488352017086413266142218347595202655520785983898726521147649511514605526530453492704620682385035589372309167596680748613367540630010472990992841612002290955856795391675078590923226942740904916328445733366136324856838559878439853270981280663438572276140821766675
c_2 = 111865944388540159344684580970835443272640009631057414995719169861041593608923140554694111747472197286678983843168454212069104647887527000991524146682409315180715780457557700493081056739716146976966937495267984697028049475057119331806957301969226229338060723647914756122358633650004303172354762801649731430086958723739208772319851985827240696923727433786288252812973287292760047908273858438900952295134716468135711755633215412069818249559715918812691433192840
"""

解題思路

因為這一題認識了連分數。

這題是四個質數的RSA，有以下性質。

$n1=p*q\\ n2=r*s\\ r=q+2$

可以做以下運算。

$\frac{n1}{n2} = \frac{p*q}{r*s} = \frac{p}{s} * \frac{q}{q+2}$

因為q很大，所以$\frac{n1}{n2}$近似於$\frac{p}{s}$。

賽中只想到這邊，後來才知道可以藉由連分數得到p，接下來就回歸RSA的正常解密步驟。

解答

from Crypto.Util.number import *
from gmpy2 import *

n1 = 266809852588733960459210318535250490646048889879697803536547660295087424359820779393976863451605416209176605481092531427192244973818234584061601217275078124718647321303964372896579957241113145579972808278278954608305998030194591242728217565848616966569801983277471847623203839020048073235167290935033271661610383018423844098359553953309688771947405287750041234094613661142637202385185625562764531598181575409886288022595766239130646497218870729009410265665829
n2 = 162770846172885672505993228924251587431051775841565579480252122266243384175644690129464185536426728823192871786769211412433986353757591946187394062238803937937524976383127543836820456373694506989663214797187169128841031021336535634504223477214378608536361140638630991101913240067113567904312920613401666068950970122803021942481265722772361891864873983041773234556100403992691699285653231918785862716655788924038111988473048448673976046224094362806858968008487
c1 = 90243321527163164575722946503445690135626837887766380005026598963525611082629588259043528354383070032618085575636289795060005774441837004810039660583249401985643699988528916121171012387628009911281488352017086413266142218347595202655520785983898726521147649511514605526530453492704620682385035589372309167596680748613367540630010472990992841612002290955856795391675078590923226942740904916328445733366136324856838559878439853270981280663438572276140821766675
c2 = 111865944388540159344684580970835443272640009631057414995719169861041593608923140554694111747472197286678983843168454212069104647887527000991524146682409315180715780457557700493081056739716146976966937495267984697028049475057119331806957301969226229338060723647914756122358633650004303172354762801649731430086958723739208772319851985827240696923727433786288252812973287292760047908273858438900952295134716468135711755633215412069818249559715918812691433192840
e = 0x10001


# from https://github.com/pablocelayes/rsa-wiener-attack/blob/master/ContinuedFractions.py


def rational_to_contfrac(x, y):
    '''
    Converts a rational x/y fraction into
    a list of partial quotients [a0, ..., an]
    '''
    a = x // y
    pquotients = [a]
    while a * y != x:
        x, y = y, x - a * y
        a = x // y
        pquotients.append(a)
    return pquotients


def contfrac_to_rational(frac):
    '''Converts a finite continued fraction [a0, ..., an]
     to an x/y rational.
     '''
    if len(frac) == 0:
        return (0, 1)
    num = frac[-1]
    denom = 1
    for _ in range(-2, -len(frac) - 1, -1):
        num, denom = frac[_] * num + denom, num
    return (num, denom)


def convergents_from_contfrac(frac):
    '''
    computes the list of convergents
    using the list of partial quotients
    '''
    convs = [];
    for i in range(len(frac)):
        convs.append(contfrac_to_rational(frac[0:i]))
    return convs


frac = rational_to_contfrac(n1, n2)
convergents = convergents_from_contfrac(frac)
for q1, q2 in convergents:
    # print(q1, q2)
    try:
        if n1 % q1 == 0:
            p1 = n1 // q1
            phi1 = (p1 - 1) * (q1 - 1)
            d1 = invert(e, phi1)
            m = pow(c1, d1, n1)
            print(long_to_bytes(m))
    except:
        pass