Prayan CTF 2019 Crypto Write up

Decode This

문제에서 주어진 코드와 암호문은 다음과 같다.

암호문

vuqxyugfyzfjgoccjkxlqvguczymjhpmjkyzoilsxlwtmccclwizqbetwthkkvilkruufwuu

source.py

import random

file = open("secret.txt","r")

secret = file.read()

flag = ""

for i in secret:

    if i.isalpha():

        flag += i

l = len(flag)

key = [[int(random.random()*10000) for e in range(2)] for e in range(2)]

# [[7156, 9059], [9366, 2474]]

i = 0

ciphertext = ""

while i <= (l-2):

    x = ord(flag[i]) - 97

    y = ord(flag[i+1]) - 97

    z = (x*key[0][0] + y*key[0][1])%26 + 97

    w = (x*key[1][0] + y*key[1][1])%26 + 97

    ciphertext = ciphertext + chr(z) + chr(w)

    i = i+2

cipherfile = open('ciphertext.txt','w')

cipherfile.write(ciphertext)

암호화 과정에서 0~10000 범위의 랜덤 키 4가지가 사용된다.

간단히 생각하면 10000**4의 경우의 수를 브포해서 유의미한 문자열을 찾으면 될 것 같긴한데 범위가 크기도하고 이런걸 의도한 문제는 아닌 것 같아서 다른 방향으로 생각해봤다.

암호화 코드를 좀 더 보니 코드에 나온 수식이 아래와 같이 변경 가능했고 이를 통해 실질적으로 키 값의 범위가 0~10000가 아닌 0~26인 것을 알 수 있었다.

z = (x*key[0][0] + y*key[0][1])%26 + 97

z = ((x%26)*(key[0][0]%26))%26+((y%26)*(key[0][1]%26))%26+97

이를 통해 키 범위를 26**4=456976으로 줄일 수 있었고 추가로 문자열 복호화 시 플래그 포멧인 pctf 문자열을 생성하는 키들을 따로 추출해 복호화 하는식으로 키 범위를 더 줄여서 플래그를 구했다.

solve.py

def get_key(enc_flag):

    flag_format = "pctf"

    for j in range(0,26):

        for k in range(0,26):

                x = ord(flag_format[0]) - 97

                y = ord(flag_format[1]) - 97

                p = ord(flag_format[2]) - 97

                q = ord(flag_format[3]) - 97

                z = (x * j + y * k) % 26 + 97

                w = (x * j + y * k) % 26 + 97

                r = (p * j + q * k) % 26 + 97

                u = (p * j + q * k) % 26 + 97

                if z==ord(enc_flag[0]) and r==ord(enc_flag[2]):

                    k1=[j,k]

                if w==ord(enc_flag[1]) and u==ord(enc_flag[3]):

                    k2=[j,k]

    return [k1,k2]

def decrypt_flag(key,enc_flag):

    flag = ""

    for i in range(0, len(enc_flag), 2):

        for j in range(ord('a'), ord('z') + 1):

            for k in range(ord('a'), ord('z') + 1):

                x = j - 97

                y = k - 97

                z = (x * key[0][0] + y * key[0][1]) % 26 + 97

                w = (x * key[1][0] + y * key[1][1]) % 26 + 97

                if z == ord(enc_flag[i]) and w == ord(enc_flag[i + 1]):

                    flag += chr(j) + chr(k)

    if "pctf" in flag:

        print flag

enc_flag = "vuqxyugfyzfjgoccjkxlqvguczymjhpmjkyzoilsxlwtmccclwizqbetwthkkvilkruufwuu"

for i in range(0,len(enc_flag)-4,2):

    key = get_key(enc_flag[i:i+4])

    decrypt_flag(key,enc_flag)

result

pctfaqnrrfqhcscypuqthzmkxpesklxcpurfeubkqtrvekcyzwtrrrdprvzclxnbnlugduug

bkidyqgrkvbtmaigpctfybqggdkinztqpckvakbotfilyaigvsapchabilryepibklcibgci

utndygtvjbxesmoyidpctfagxbworgkbidjbmsevpchhkyoysrfbbzjhhhodlfvpxjkgkrkg

vxknqmedeldsyweunrpouduagfeypctfnrelggnppouxwseutjwjqhyluxzhezoryfosdfos

telpiepbtfyhoieqpcexrzwenfgsyrnspctfumboexbjcqeqpurfzvpjbjfcnzhxztoeluoe

ramhasalittlesecretforyourighthereitispctfilikeclimbinghillswhataboutyou

rsjxwczhlpsvausytecddxsujlyckrjytelpemdccdhraosypctfvxdjhrhgtddfhdygfiyg

bvdiawnmpgiloeowbxivxegqfqcgsrfdbxpgcmhfivpcciowtndspqvwpctfzcnqnukmvlkm

lkltouxfffuhmeosrayjzzwmjbssmjjoraffkopayjtzyiosnopvjhbrtzpctfjlvrkyhuky

위 결과 중 의미있는 문장이 딱 하나 나온다.

ramhasalittlesecretforyourighthereitispctfilikeclimbinghillswhataboutyou

Flag = pctf{ilikeclimbinghillswhataboutyou}

Easy RSA

주어진 정보는 아래와 같다.

e=217356749319385698521929657544628507680950813122965981036139317973675569442588326220293299168756490163223201593446006249622787212268918299733683908813777695992195006830244088685311059537057855442978678020950265617092637544349098729925492477391076560770615398034890984685084288600014953201593750327846808762513
n=413514550275673527863957027545525175432824699510881864021105557583918890022061739148026915990124447164572528944722263717357237476264481036272236727160588284145055425035045871562541038353702292714978768468806464985590036061328334595717970895975121788928626837881214128786266719801269965024179019247618967408217
c=337907824405966440030495671003069758278111764297629248609638912154235544001123799434176915113308593275372838266739188034566867280295804636556069233774555055521212823481663542294565892061947925909547184805760988117713501561339405677394457210062631040728412334490054091265643226842490973415231820626551757008360

e 값이 엄청 커서 위너 어택 코드를 돌려보면 개인키를 구할 수 있고 이걸로 그냥 복호화하면 된다.

solve.py

from gmpy2 import *

  

d = 12978409760901509356642421072925801006324287746872153539187221529835976408177

n = 413514550275673527863957027545525175432824699510881864021105557583918890022061739148026915990124447164572528944722263717357237476264481036272236727160588284145055425035045871562541038353702292714978768468806464985590036061328334595717970895975121788928626837881214128786266719801269965024179019247618967408217

c = 337907824405966440030495671003069758278111764297629248609638912154235544001123799434176915113308593275372838266739188034566867280295804636556069233774555055521212823481663542294565892061947925909547184805760988117713501561339405677394457210062631040728412334490054091265643226842490973415231820626551757008360

print("%x"%pow(c,d,n)).decode("hex")

Help Rabin

문제에서 주어진 정보는 다음과 같다.

- public pem file

- 암호문

- 암호화 시 사용한 코드

먼저 암호화 시 사용된 코드를 보면 다음과 같다.

encrypt.py

from Crypto.Util.number import *

import random

def nextPrime(prim):

    if isPrime(prim):

        return prim

    else:

        return nextPrime(prim+1)

p = getPrime(512)

q = nextPrime(p+1)

while p%4 != 3 or q%4 !=3:

    p = getPrime(512)

    q = nextPrime(p+1)

n = p*q

m = open('secret.txt').read()

m = bytes_to_long(m)

m = m**e

c = (m*m)%n

c = long_to_bytes(c)

c = c.encode('hex')

cipherfile = open('ciphertext.txt','w')

cipherfile.write(c)

암호화 코드를 보면 p,q 값이 거의 차이가 나지 않기 때문에 n 값만 알아도 p,q를 구할 수 있다. n 값은 pem 파일을 통해 확인했고, 추가로 조금 특이한게 암호화 코드를 잘 보면 결국 수행하는 행위가 c=(m**2)%n 이다. e가 2라는 건데 이런 경우에는 d가 생성이 안된다. rsa라고 생각했는데 rsa가 아닌거 같았고 e가 2인경우에 대해 찾아보니 rabin이라는 암호화가 존재하는 걸 알 수 있었다. 문제이름도 마침 rabin이었고 실제로 찾아보니 암호화 과정이 동일해서 해당 암호를 복호화하는 python 코드를 통해 플래그를 찾았다. 

solve.py

from Crypto.Util.number import *

from gmpy2 import *

def egcd(a, b):

    if a == 0:

        return b, 0, 1

    else:

        gcd, y, x = egcd(b % a, a)

        return gcd, x - (b // a) * y, y

# python RsaCtfTool.py --dumpkey --key pub.key

n = 68367741643352408657735068643514841659753216083862769094847066695306696933618090026602354837201210914348646470450259642887798188510482019698636160200778870456236361521880907328722252080005877088416283896813311117096542977573101128888124000494645965045855288082328139311932783360168599377647677632122110245577

p = isqrt(n)

while True:

    q, r = t_divmod(n, p)

    if r == 0:

        break

    p += 1

c = 0x4f741fe93dd7e383ff527caa9a2f27d27fd74b53b62123837b74a2b024d0fbbe052f3b330ce5208ba989fc68e2f5235ac4e9dd9e091e7cb80c02745d9b2aad10cab9431590ae63117ce539ebf747b4bc81f2a293aea52f0b1fee746158dc45d0c8d60769a8a8e671fb049b52669a010a1ca6f5de851d715bf1821d8771bbeb47

r = pow(c, long((p+1)/4), long(p))

s = pow(c, long((q+1)/4), long(q))

gcd, c, d = egcd(p, q)

x = (r * d * q + s * c * p) % n

y = (r * d * q - s * c * p) % n

plain_list = [x, n - x, y, n - y]

for plain in plain_list:

    flag = long_to_bytes(plain)

    print flag