'Crypto & Network & Etc'에 해당되는 글 40건

문제에서 제공하는 파일은 클라이언트용 파이썬 코드와 pcap 파일 두가지이다.

먼저 클라이언트 파이썬 코드를 보면 아래와 같다.

client.py

from socket import *

from ssl import *

import time

def recv_until(s, string):

    result = ''

    while string not in result:

        result += s.recv(1)

    return result

client_socket=socket(AF_INET, SOCK_STREAM)

tls_client = wrap_socket(client_socket, ssl_version=PROTOCOL_TLSv1_2, cert_reqs=CERT_NONE)

print "[+] Connecting with server.."

tls_client.connect(('ch41l3ng3s.codegate.kr',443))

print "[+] Connect OK"

while 1:

    data = recv_until(tls_client, "Input : ")

    print data

    #message

    user_input = raw_input()

    if user_input == "u":

        print "Sorry.. Not support function.."

        exit()

    elif user_input == "d": 

        tls_client.send("6423e47152f145ee5bd1c014fc916e1746d66e8f5796606fd85b9b22ad333101\n")

    elif user_input == "r":

        tls_client.send("34660cfdd38bb91960d799d90e89abe49c1978bad73c16c6ce239bc6e3714796\n")

    elif user_input == "l":

        print "Sorry.. Not support function.."

        exit()

    else:

        print "Invalid input!"

        exit()    

client_socket.shutdown(SHUT_RDWR)

client_socket.close()

예전 문제라 현재 서버가 존재하지 않지만 코드를 보면 방향키 입력 시 해당 방향과 매칭되는 해쉬값을 서버에 보내 실제 방향 이동을 하는 것 같았다.

근데 이 때 4가지 방향 중 2가지 방향에 대한 해쉬 값이 없어 방향 이동 제한이 존재하는 것 같았고 실제 문제 출제가 어떻게 되었었는지 확인해보니 게임을 통해 플래그 위치까지 가려면 4가지 방향에 대해 모두 이동을 해야만 하는 상황이었었다.

해당 코드만 가지고 뭔가 할만한건 없으니 pcap 파일을 보면 통신이 TLS로 이루어져 패킷 내용을 확인할 수 없는 상황이었다.

여기서 뭘 해야할지 감이 안왔는데 크립토 문제였기 때문에 일단 와이어샤크를 통해 TLS 통신 시 사용된 인증서를 추출한 뒤 공개키가 소인수분해가 되거나, factor db를 통해 p,q를 구할 수 있는지 확인해보는식으로 진행해봤다.

인증서 추출은 아래 글을 참고

https://5kyc1ad.tistory.com/57

추출한 인증서에서 n 값을 확인

openssl x509 -inform der -in test.crt -pubkey -noout > pub.key

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

[*] n: 316033277426326097045474758505704980910037958719395560565571239100878192955228495343184968305477308460190076404967552110644822298179716669689426595435572597197633507818204621591917460417859294285475630901332588545477552125047019022149746524843545923758425353103063134585375275638257720039414711534847429265419

[*] e: 65537

factordb에서 p,q 값 확인

p = 17777324810733646969488445787976391269105128850805128551409042425916175469168770593916088768472336728042727873643069063316671869732507795155086000807594027

q = 17777324810733646969488445787976391269105128850805128551409042425916175469483806303918279424710789334026260880628723893508382860291986009694703181381742497

인증서에 사용된 공개키를 통해 d를 구할 수 있는 상황이기 때문에 RsactfTool을 이용해 private key를 생성한 뒤 wireshark에 생성한 private key를 적용해줬다.

python RsaCtfTool.py --publickey pub.key --private > pri.key

아래 게시글을 참조하여 생성한 개인키 와이어 샤크에 적용

https://hiseon.me/network/decrypt-ssl-traffic/

위 과정들을 통해 pcap 파일에 존재하는 패킷 내용을 복호화 할 수 있었고, 통신 내용을 확인해보니 아래와 같이 나머지 두 방향키에 대한 해쉬 값을 확인할 수 있었다.

이제 모든 방향 이동이 가능하기 때문에 게임 클리어가 가능하고 이를 통해 플래그를 구해주면 된다.

source.py

import multiprocessing

from Crypto.Cipher import AES

from secret import key, flag

counter = 0

aes = AES.new(key, AES.MODE_ECB)

def chunk(input_data, size):

    return [input_data[i:i + size] for i in range(0, len(input_data), size)]

def xor(*t):

    from functools import reduce

    from operator import xor

    return [reduce(xor, x, 0) for x in zip(*t)]

def xor_string(t1, t2):

    t1 = map(ord, t1)

    t2 = map(ord, t2)

    return "".join(map(chr, xor(t1, t2)))

def pad(data):

    pad_byte = 16 - len(data) % 16

    return data + (chr(pad_byte) * pad_byte)

def worker_function(block):

    global counter

    key_stream = aes.encrypt(pad(str(counter)))

    result = xor_string(block, key_stream)

    counter += 1

    return result

def distribute_work(worker, data_list, processes=8):

    pool = multiprocessing.Pool(processes=processes)

    result = pool.map(worker, data_list)

    pool.close()

    return result

def encrypt_parallel(plaintext, workers_number):

    chunks = chunk(pad(plaintext), 16)

    results = distribute_work(worker_function, chunks, workers_number)

    return "".join(results)

def main():

    plaintext = """The Song of the Count

You know that I am called the Count

Because I really love to count

I could sit and count all day

Sometimes I get carried away

I count slowly, slowly, slowly getting faster

Once I've started counting it's really hard to stop

Faster, faster. It is so exciting!

I could count forever, count until I drop

1! 2! 3! 4!

1-2-3-4, 1-2-3-4,

1-2, i love couning whatever the ammount haha!

1-2-3-4, heyyayayay heyayayay that's the sound of the count

I count the spiders on the wall...

I count the cobwebs in the hall...

I count the candles on the shelf...

When I'm alone, I count myself!

I count slowly, slowly, slowly getting faster

Once I've started counting it's really hard to stop

Faster, faster. It is so exciting!

I could count forever, count until I drop

1! 2! 3! 4!

1-2-3-4, 1-2-3-4, 1,

2 I love counting whatever the

ammount! 1-2-3-4 heyayayay heayayay 1-2-3-4

That's the song of the Count!

""" + flag

    encrypted = encrypt_parallel(plaintext, 32)

    print(encrypted.encode("hex"))

if __name__ == '__main__':

    multiprocessing.freeze_support()

    main()

solve.py

from Crypto.Util.strxor import strxor

def pad(data):

    pad_byte = 16 - len(data) % 16

    return data + (chr(pad_byte) * pad_byte)

def unpad(data):

    last_char = data[-1]

    if ord(last_char) < 16:

        return data.rstrip(last_char)

    else:

        return data

def chunk(input_data, size):

    return [input_data[i:i + size] for i in range(0, len(input_data), size)]

def xor(*t):

    from functools import reduce

    from operator import xor

    return [reduce(xor, x, 0) for x in zip(*t)]

def xor_string(t1, t2):

    t1 = map(ord, t1)

    t2 = map(ord, t2)

    return "".join(map(chr, xor(t1, t2)))

def is_printable(data):

    for i in data:

        if ord(i)<32 or ord(i)>127:

            return False

    return True

plaintext = """The Song of the Count

You know that I am called the Count

Because I really love to count

I could sit and count all day

Sometimes I get carried away

I count slowly, slowly, slowly getting faster

Once I've started counting it's really hard to stop

Faster, faster. It is so exciting!

I could count forever, count until I drop

1! 2! 3! 4!

1-2-3-4, 1-2-3-4,

1-2, i love couning whatever the ammount haha!

1-2-3-4, heyyayayay heyayayay that's the sound of the count

I count the spiders on the wall...

I count the cobwebs in the hall...

I count the candles on the shelf...

When I'm alone, I count myself!

I count slowly, slowly, slowly getting faster

Once I've started counting it's really hard to stop

Faster, faster. It is so exciting!

I could count forever, count until I drop

1! 2! 3! 4!

1-2-3-4, 1-2-3-4, 1,

2 I love counting whatever the

ammount! 1-2-3-4 heyayayay heayayay 1-2-3-4

That's the song of the Count!

"""

output = "9d5c66e65fae92af9c8a55d9d3bf640e8a5b76a878cbf691d3901392c9b8760ebd5c62b22c88dca9d1c55098cbbb644ae9406ba32c8293bdd29139bbc2b4605bba51238f2cb399a9d0894ad9cbb8774be9406ce66fae89a6c8ef7ad9c4b87442ad1470af78e19da6d8c55096d2b9750ea8586fe668a085c2ef8a5e9cd3be6c4bba144ae66ba488e8df84418bceb2650ea84362bf0688dcabd3905d8d87a46d414626be04a58215b84263a620de3203fa4626be08e2940da35c61b82c98201ce15438cd67eb921cf77c28a969de321bf4433ea24ca59216a25b7bb662996106e11639e75ae09015bb4c2fb76d8c254fe15e6ab45cea817391547cab698c6d4ff35039b34df7df599e412fb67fde3200b55432a441f19817b01405962c9d2e1af9556aa447f09f0df75360ad6988241db91129a85deb8559a25b7bb660de084ff1cc3a0e8041bc71d71fb29883931d9d3e8f784ca743b065c91ea386909e1a9100925f4fa742b1718c1efec4d4d609df5bcb3b17e417bd268d5fe6ced4d65b9c40d6305eeb1df03e9050e68bcad241dd15b46453b85dae7cd112b2c3c7ca50dd4ddf2c1ff350f5349c5febcadbd2509c40d6340aad03bd258d5bb2d8cdc647d814d1335efe18f8718651e7c5d6b9609c57d12010fe50e939801ee1dbcbd74cce4739c1eeceba8ef87360b629ed82a6eb9d508ee381bb88e97363bf20a1cfe7a7e07cccf3cea788bd277fb265e9cde4a9b937808aa7ee85f22679a365f5c4ede5f478c0e482ab95bd3c79f731e9c9a8b6ff7cc2e6c0e0c897047fb22ba1e5afa8b778c2ef80abcabd1a37b42af4c2fce5fa60dde582a8c7971a37b42af4c2fce5e475c1f782b7cabd207bb832edd5a4e5e4130a976ad4a2fe86ac99c18491f9f6c86adae59cc4a9f33072f70ca6daede5e40b049272c8e6b980b798c69e9fb7f7891611c7758df0fc82b481d1ca9eb8e2cd5f118f26def6f693d2abc99982bce2855f038175d9e7ebcdf8a4dcca9faab0da1045857eceebed8ab68a89e0bff9f3c60a098426ceedec8daccdce8584bce6cc0d49c065c2f7f797f898c69e9fb5b0e05f019269dd88a8c2f8df89cac5f8b09d00ad16dc760ead7c3518baed47603c5b5251cc269cae93d1f8a4888699aff58942c8529f304af0362143f2bd1e37670d538753992129ff3c6c5befb21e7331590c950ac26917be39644dfba50b2b70117fcbccba57b209ae95721a1c9d36073d934b75014109102be14fb6a044a7cf9e468748976457f6342177f5a9042630622f97d2ba5a8c04a7890d4e5fcb445b7600d7c1be71b711b6b32b4444f078557ef82e4f0559225437b455aa9a0bbaff89c834531a45115125c933d6cd6cdca8f8".decode("hex")

chunks = chunk(pad(plaintext), 16)

keyStream_list = []

for i in range(0,len(chunks)-1):

    keyStream_list.append(strxor(chunks[i],output[i*16:(i*16)+16]).encode("hex"))

keyStream_list = list(set(keyStream_list))

for i in range(len(chunks)-1,len(output)/16):

    print "------------------------"

    for j in range(0,len(keyStream_list)):

        result = unpad(strxor(keyStream_list[j].decode("hex"), output[i * 16:(i * 16) + 16]))

        if is_printable(result):

            print result

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

-.-

주어진 암호문은 다음과 같다.

dah-dah-dah-dah-dah dah-di-di-dah di-di-di-di-dit dah-dah-di-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-dah-dah-dah di-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-di-dit dah-dah-dah-di-dit dah-dah-di-di-dit di-di-di-di-dah di-di-di-di-dah dah-dah-di-di-dit di-di-di-di-dit di-dah-dah-dah-dah di-di-di-dah-dah dah-dah-dah-di-dit dah-di-di-di-dit di-di-di-di-dit di-di-di-dah-dah dah-dah-dah-di-dit dah-dah-di-di-dit di-dah-dah-dah-dah dah-di-di-di-dit dit dah-di-di-di-dit dah-di-dit di-di-di-di-dah dah-di-dit di-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dit di-di-di-di-dit di-di-dah-dah-dah di-dah dah-dah-di-di-dit di-di-di-dah-dah dah-dah-di-di-dit dah-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit di-di-di-di-dah dah-dah-dah-di-dit dah-di-di-di-dit dah-di-di-dit dah-di-di-di-dit di-dah di-di-di-di-dah dah-dah-dah-dah-dit dah-dah-di-di-dit di-di-di-di-dah di-di-dah-dah-dah di-dah di-di-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-dah-dah-dah-dah di-di-dah-dah-dah dah-di-di-di-dit di-di-di-di-dah di-dah dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-di-di-dit di-dah dah-dah-di-di-dit dah-di-di-di-dit dah-di-di-di-dit di-dah dah-di-di-di-dit dah-di-dit di-di-dah-dah-dah di-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-dit di-di-di-di-dah di-di-di-di-dah dah-di-di-di-dit dah-di-di-dit dah-di-di-di-dit dah-di-di-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-di-dit dit di-di-di-di-dah dit di-di-di-dah-dah dah-dah-dah-dah-dit dah-di-di-di-dit dah-di-di-di-dit dah-di-di-di-dit dah-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-di-di-di-dit di-di-di-di-dah di-di-di-di-dit di-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-di-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-dah-dah dah-dah-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit di-di-dah-dit di-di-di-di-dit di-di-di-di-dah di-di-di-dah-dah dah-dah-dah-dah-dah di-di-di-di-dit dah-dah-dah-dah-dah di-di-di-di-dit di-dah di-di-di-di-dit di-dah-dah-dah-dah dah-di-di-di-dit dah-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-dit di-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-di-dah di-di-di-di-dit di-dah di-di-di-di-dah dah-di-dit dah-dah-di-di-dit dah-di-di-di-dit di-di-dah-dah-dah di-dah di-di-dah-dah-dah di-dah-dah-dah-dah di-di-di-di-dah dah-di-di-di-dit dah-di-di-di-dit dah-di-di-dit di-di-di-dah-dah dah-dah-dah-di-dit dah-di-di-di-dit dah-di-dah-dit di-di-dah-dah-dah di-di-di-di-dit dah-di-di-di-dit di-di-dah-dah-dah dah-di-di-di-dit di-dah dah-dah-di-di-dit di-dah-dah-dah-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-di-dit dah-dah-dah-dah-dah di-di-di-di-dah dah-di-dit dah-di-di-di-dit dah-di-di-di-dit di-di-di-di-dah dah-dah-dah-dah-dit di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit dah-di-dit dah-di-di-di-dit di-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit dah-dah-di-di-dit di-dah di-di-di-di-dah dah-dah-di-di-dit di-di-dah-dah-dah dah-dah-dah-dah-dah dah-di-di-di-dit dah-dah-di-di-dit dah-di-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit dah-dah-di-di-dit dah-di-di-di-dit di-di-di-di-dit dah-di-di-di-dit dah-di-dit dah-dah-di-di-dit dah-di-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-di-dah-dah di-dah-dah-dah-dah dah-di-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-di-di-dit di-di-di-di-dit di-di-dah-dit dah-di-di-di-dit di-di-di-dah-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-dah-dah di-dah-dah-dah-dah di-di-di-di-dah di-di-di-dah-dah di-di-di-di-dah dah-di-di-dit di-di-dah-dah-dah dah-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dit di-di-di-dah-dah dah-dah-dah-dah-dah dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dit di-di-dah-dit dah-di-di-di-dit dah-dah-dah-di-dit di-di-di-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-dah-dah di-di-di-di-dit di-di-dah-dit dah-di-di-di-dit dah-di-dit di-di-di-dah-dah di-di-di-di-dah di-di-di-di-dah dah-dah-dah-dah-dit di-di-di-dah-dah di-dah-dah-dah-dah dah-dah-di-di-dit dah-di-dit di-di-dah-dah-dah dah-dah-dah-dah-dah dah-dah-di-di-dit di-di-di-di-dit dah-dah-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit dah-dah-di-di-dit di-dah di-di-di-di-dah dah-di-di-dit di-di-di-di-dit di-dah dah-dah-di-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit di-di-dah-dit dah-di-di-di-dit dah-di-dit dah-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dah di-di-di-di-dah di-di-di-di-dit di-di-di-dah-dah dah-di-di-di-dit dah-dah-dah-di-dit di-di-di-di-dah dah-di-dah-dit dah-di-di-di-dit dah-di-dit di-di-di-dah-dah dah-dah-dah-di-dit di-di-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit dah-di-di-di-dit dit di-di-di-di-dit di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dah dah-dah-di-di-dit dah-dah-di-di-dit di-di-di-di-dah di-dah di-di-di-di-dah dah-dah-dah-dah-dah di-di-di-di-dah dit dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dah di-di-dah-dit di-di-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit dah-di-di-di-dit di-di-di-di-dit dah-dah-dah-di-dit di-di-dah-dah-dah dah-di-di-di-dit di-di-di-dah-dah dah-dah-dah-di-dit dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dah dah-dah-dah-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit dit di-di-dah-dah-dah di-dah-dah-dah-dah di-di-di-dah-dah di-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dit di-di-di-di-dah dah-dah-di-di-dit di-dah-dah-dah-dah dah-dah-di-di-dit dah-di-di-di-dit di-di-di-dah-dah dah-dah-dah-dah-dah di-di-di-di-dit dah-di-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dit di-di-dah-dah-dah dah-dah-di-di-dit di-dah di-di-di-di-dit dah-di-di-di-dit di-di-dah-dah-dah di-dah-dah-dah-dah dah-di-di-di-dit di-dah di-di-dah-dah-dah di-dah-dah-dah-dah dah-dah-di-di-dit dah-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-di-dah-dah dah-dah-dah-di-dit di-di-di-di-dah di-di-dah-dah-dah dah-di-di-di-dit di-dah dah-di-di-di-dit di-di-di-di-dah di-di-di-di-dah dit di-di-di-di-dah dah-dah-dah-dah-dit dah-dah-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-dah-dah di-di-di-di-dit dah-dah-di-di-dit dah-dah-di-di-dit di-di-dah-dah-dah di-di-di-dah-dah di-di-dah-dah-dah di-di-di-di-dah di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-di-dit di-di-di-di-dit di-dah di-di-di-di-dah di-di-dah-dit di-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dit di-dah di-di-di-dah-dah di-di-dah-dah-dah dah-dah-di-di-dit di-dah di-di-di-dah-dah dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dah di-di-di-dah-dah dah-dah-di-di-dit di-di-dah-dah-dah dah-di-di-di-dit dah-dah-di-di-dit dah-dah-dah-di-dit di-di-di-di-dah dah-di-dah-dit di-di-di-di-dah dah-dah-dah-dah-dah di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dah di-di-dah-dit di-di-di-dah-dah dah-dah-di-di-dit di-di-di-dah-dah di-di-di-di-dah di-di-di-dah-dah di-dah-dah-dah-dah di-di-di-dah-dah dah-dah-dah-dah-dah di-di-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah dah-dah-dah-dah-dit

-,공백은 구분자이고 실질적으로는 di,dah,dit로 이루어져있다. 구성 요소가 3개라 3진수인가 싶었는데 아니었고, 문제이름이 딱봐도 morse code였는데 구성 요소가 3개라

아닌가 싶었다. 여기서 좀 헤매다 결국 morse code 같아서 morse code 테이블이랑 하나씩 비교하면서보니 di,dit를 그냥 둘다 .으로 치환해버리면 구조가 딱 들어맞는것 같길래 싹다 치환해서 온라인 디코더로 돌려보니 hex값이 나왔고 이거 디코딩하니 플래그가 나왔다.

solve.py

a = """dah-dah-dah-dah-dah dah-di-di-dah di-di-di-di-dit dah-dah-di-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-dah-dah-dah di-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-di-dit dah-dah-dah-di-dit dah-dah-di-di-dit di-di-di-di-dah di-di-di-di-dah dah-dah-di-di-dit di-di-di-di-dit di-dah-dah-dah-dah di-di-di-dah-dah dah-dah-dah-di-dit dah-di-di-di-dit di-di-di-di-dit di-di-di-dah-dah dah-dah-dah-di-dit dah-dah-di-di-dit di-dah-dah-dah-dah dah-di-di-di-dit dit dah-di-di-di-dit dah-di-dit di-di-di-di-dah dah-di-dit di-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dit di-di-di-di-dit di-di-dah-dah-dah di-dah dah-dah-di-di-dit di-di-di-dah-dah dah-dah-di-di-dit dah-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit di-di-di-di-dah dah-dah-dah-di-dit dah-di-di-di-dit dah-di-di-dit dah-di-di-di-dit di-dah di-di-di-di-dah dah-dah-dah-dah-dit dah-dah-di-di-dit di-di-di-di-dah di-di-dah-dah-dah di-dah di-di-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-dah-dah-dah-dah di-di-dah-dah-dah dah-di-di-di-dit di-di-di-di-dah di-dah dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-di-di-dit di-dah dah-dah-di-di-dit dah-di-di-di-dit dah-di-di-di-dit di-dah dah-di-di-di-dit dah-di-dit di-di-dah-dah-dah di-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-dit di-di-di-di-dah di-di-di-di-dah dah-di-di-di-dit dah-di-di-dit dah-di-di-di-dit dah-di-di-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-di-dit dit di-di-di-di-dah dit di-di-di-dah-dah dah-dah-dah-dah-dit dah-di-di-di-dit dah-di-di-di-dit dah-di-di-di-dit dah-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-di-di-di-dit di-di-di-di-dah di-di-di-di-dit di-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-di-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-dah-dah dah-dah-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit di-di-dah-dit di-di-di-di-dit di-di-di-di-dah di-di-di-dah-dah dah-dah-dah-dah-dah di-di-di-di-dit dah-dah-dah-dah-dah di-di-di-di-dit di-dah di-di-di-di-dit di-dah-dah-dah-dah dah-di-di-di-dit dah-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-dit di-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-di-dah di-di-di-di-dit di-dah di-di-di-di-dah dah-di-dit dah-dah-di-di-dit dah-di-di-di-dit di-di-dah-dah-dah di-dah di-di-dah-dah-dah di-dah-dah-dah-dah di-di-di-di-dah dah-di-di-di-dit dah-di-di-di-dit dah-di-di-dit di-di-di-dah-dah dah-dah-dah-di-dit dah-di-di-di-dit dah-di-dah-dit di-di-dah-dah-dah di-di-di-di-dit dah-di-di-di-dit di-di-dah-dah-dah dah-di-di-di-dit di-dah dah-dah-di-di-dit di-dah-dah-dah-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-di-dit dah-dah-dah-dah-dah di-di-di-di-dah dah-di-dit dah-di-di-di-dit dah-di-di-di-dit di-di-di-di-dah dah-dah-dah-dah-dit di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit dah-di-dit dah-di-di-di-dit di-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-di-dit di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit dah-dah-di-di-dit di-dah di-di-di-di-dah dah-dah-di-di-dit di-di-dah-dah-dah dah-dah-dah-dah-dah dah-di-di-di-dit dah-dah-di-di-dit dah-di-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit dah-dah-di-di-dit dah-di-di-di-dit di-di-di-di-dit dah-di-di-di-dit dah-di-dit dah-dah-di-di-dit dah-di-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-di-dah-dah di-dah-dah-dah-dah dah-di-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-di-di-dit di-di-di-di-dit di-di-dah-dit dah-di-di-di-dit di-di-di-dah-dah dah-di-di-di-dit dah-di-dah-dit di-di-di-dah-dah di-dah-dah-dah-dah di-di-di-di-dah di-di-di-dah-dah di-di-di-di-dah dah-di-di-dit di-di-dah-dah-dah dah-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dit di-di-di-dah-dah dah-dah-dah-dah-dah dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dit di-di-dah-dit dah-di-di-di-dit dah-dah-dah-di-dit di-di-di-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-dah-dah di-di-di-di-dit di-di-dah-dit dah-di-di-di-dit dah-di-dit di-di-di-dah-dah di-di-di-di-dah di-di-di-di-dah dah-dah-dah-dah-dit di-di-di-dah-dah di-dah-dah-dah-dah dah-dah-di-di-dit dah-di-dit di-di-dah-dah-dah dah-dah-dah-dah-dah dah-dah-di-di-dit di-di-di-di-dit dah-dah-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit dah-dah-di-di-dit di-dah di-di-di-di-dah dah-di-di-dit di-di-di-di-dit di-dah dah-dah-di-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit di-di-dah-dit dah-di-di-di-dit dah-di-dit dah-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dah di-di-di-di-dah di-di-di-di-dit di-di-di-dah-dah dah-di-di-di-dit dah-dah-dah-di-dit di-di-di-di-dah dah-di-dah-dit dah-di-di-di-dit dah-di-dit di-di-di-dah-dah dah-dah-dah-di-dit di-di-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-di-dah dah-di-di-di-dit dah-di-di-di-dit dit di-di-di-di-dit di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dah dah-dah-di-di-dit dah-dah-di-di-dit di-di-di-di-dah di-dah di-di-di-di-dah dah-dah-dah-dah-dah di-di-di-di-dah dit dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dah di-di-dah-dit di-di-di-di-dit dah-dah-dah-dah-dit dah-di-di-di-dit dah-di-di-di-dit di-di-di-di-dit dah-dah-dah-di-dit di-di-dah-dah-dah dah-di-di-di-dit di-di-di-dah-dah dah-dah-dah-di-dit dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dah dah-dah-dah-dah-dah di-di-di-di-dah dah-dah-di-di-dit dah-di-di-di-dit dit di-di-dah-dah-dah di-dah-dah-dah-dah di-di-di-dah-dah di-dah-dah-dah-dah di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dit di-di-di-di-dah dah-dah-di-di-dit di-dah-dah-dah-dah dah-dah-di-di-dit dah-di-di-di-dit di-di-di-dah-dah dah-dah-dah-dah-dah di-di-di-di-dit dah-di-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dit di-di-dah-dah-dah dah-dah-di-di-dit di-dah di-di-di-di-dit dah-di-di-di-dit di-di-dah-dah-dah di-dah-dah-dah-dah dah-di-di-di-dit di-dah di-di-dah-dah-dah di-dah-dah-dah-dah dah-dah-di-di-dit dah-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dit dah-dah-di-di-dit dah-dah-dah-dah-dah di-di-di-dah-dah dah-dah-dah-di-dit di-di-di-di-dah di-di-dah-dah-dah dah-di-di-di-dit di-dah dah-di-di-di-dit di-di-di-di-dah di-di-di-di-dah dit di-di-di-di-dah dah-dah-dah-dah-dit dah-dah-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-dah-dah di-di-di-di-dit dah-dah-di-di-dit dah-dah-di-di-dit di-di-dah-dah-dah di-di-di-dah-dah di-di-dah-dah-dah di-di-di-di-dah di-di-dah-dah-dah di-di-di-di-dit di-di-di-di-dit dah-di-di-di-dit di-di-di-dah-dah di-di-di-di-dah di-di-di-di-dit di-di-di-di-dit di-di-di-di-dit di-dah di-di-di-di-dah di-di-dah-dit di-di-di-di-dit dah-dah-dah-dah-dit di-di-di-di-dit di-dah di-di-di-dah-dah di-di-dah-dah-dah dah-dah-di-di-dit di-dah di-di-di-dah-dah dah-dah-di-di-dit di-di-di-di-dit di-di-di-di-dah di-di-di-dah-dah di-di-dah-dah-dah di-di-di-dah-dah di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dah di-di-di-dah-dah dah-dah-di-di-dit di-di-dah-dah-dah dah-di-di-di-dit dah-dah-di-di-dit dah-dah-dah-di-dit di-di-di-di-dah dah-di-dah-dit di-di-di-di-dah dah-dah-dah-dah-dah di-di-di-di-dit dah-dah-di-di-dit di-di-di-di-dah di-di-dah-dit di-di-di-dah-dah dah-dah-di-di-dit di-di-di-dah-dah di-di-di-di-dah di-di-di-dah-dah di-dah-dah-dah-dah di-di-di-dah-dah dah-dah-dah-dah-dah di-di-di-di-dit di-dah-dah-dah-dah di-di-di-di-dah dah-dah-dah-dah-dit"""

a = a.replace("-","")

a = a.replace("dit",".")

a = a.replace("di",".")

a = a.replace("dah","-")

print a

print "57702a6c58744751386538716e6d4d59552a737646486b6a49742a5251264a705a766a6d2125254b446b6670235e4e39666b346455346c423372546f5430505a516d4351454b5942345a4d762a21466b386c25626a716c504d6649476d612525467a4720676967656d7b433169634b5f636c31434b2d7930755f683476335f6d3449317d20757634767a4b5a7434796f6d694453684c6d385145466e5574774a404e754f59665826387540476e213125547176305663527a56216a217675757038426a644e49714535772324255634555a4f595a327a37543235743726784c40574f373431305149".decode("hex")

RSAaaay

문제는 다음과 같다.

(2531257, 43)

p = 509

q = 4973

My super secret message: 906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268

n 값이 엄청 작아서 그냥 소인수 분해가 된다. 주어진 암호문을 공백으로 split한 뒤 각각 복호화 해보면 아래와 같은 값이 나온다.

103

105103

101109

12383

97118

97103

10195

83105

12095

70108

121105

110103

9584

105103

101114

115125

그냥 hex디코딩해보면 첫번째 값만 디코딩이 된다. 뭐지 하다 유심히 복호화된 값을 보니 아스키 값을 2개씩 이어붙인 것 같았고 이를 토대로 복호화 해보니 제대로 값이 나왔다.

solve.py

from gmpy2 import *

p = 509

q = 4973

phi = (p-1)*(q-1)

n = p*q

e = 43

d = invert(e,phi)

c = "906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268".split(" ")

flag = ""

for i in c:

        result = str(pow(int(i),d,n))

        if len(result)>3:

                if result[0]=="1":

                        flag += chr(int(result[0:3]))

                        flag += chr(int(result[3:]))

                else:

                        flag += chr(int(result[0:2]))

                        flag += chr(int(result[2:]))

        else:

                flag += chr(int(result))

print flag

smile

문제에서 준 암호문은 다음과 같다.

XUBdTFdScw5XCVRGTglJXEpMSFpOQE5AVVxJBRpLT10aYBpIVwlbCVZATl1WTBpaTkBOQFVcSQdH

base64 디코딩 해보면 이상한 값이 나오는데, 디코딩된 각 문자들이 모두 아스키 범위였다. 그래서 아스키범위로 카이사르 돌려봤는데 아니었고, 플래그 포멧이 gigem이라 해당 값으로 카이사르 키 같은게 있나 찾아봤는데 이것도 아니었다. 그래서 혹시하고 gigem이랑 xor를 돌려봤더니 58 41이 계속 반복되는걸 볼 수 있었다. 이걸 key로 해서 base64 디코딩된 값을 xor해보니 플래그가 나왔다.

solve.py

a = "XUBdTFdScw5XCVRGTglJXEpMSFpOQE5AVVxJBRpLT10aYBpIVwlbCVZATl1WTBpaTkBOQFVcSQdH"

a =  a.decode("base64")

key = ":)"

flag = ""

for i in range(0,len(a)):

    flag += chr(ord(a[i])^ord(key[i%2]))

print flag

암호문과 pem 형식으로 된 두 개의 공개키를 제공해 준다. pem 파일에서 n을 각각 추출한 뒤 최대 공약수를 확인해보면 공개키 생성 과정에서  공통된 소수를 사용해 p 값을 구할 수 있다.

python RsaCtfTool.py --key ../rsa/seccon/pub1 --dumpkey

python RsaCtfTool.py --key ../rsa/seccon/pub2 --dumpkey

solve.py

from gmpy2 import *
from Crypto.PublicKey import RSA

n1 = 763718912475160487902804749669814117361530270298225094625871588939939773892509348006077810445741086683427253000695920011673348476297973798322806091336777405584801442639626925406721932533140226556519019440300864340670199686368307155860493615065198319490060598587202051942638792919648596288576294804549738135969737494734307362891313864027749187674251692407867312885251279302785352318725391842117065840058358065676707016006124478822206302825992616559261930620693061673348139416033418864269248381876692676529410115745518353146254670349865568255213560376368953292931958006941630719304442332912813624543600126197554727832190226632919876204677667384620275620336951964833888599634720101911051166398907898747710391394105753614253527704990658698844796442515669670816004761855554187277637871343595647487793209271354240148469085627742503649786300484610102224828274384484809539697728008552925590472129497180290668277790132130824141651399551803499770513576176720509094833332201946177880267399933460994496277590932311628302240154240967341858152145815276163397709272690500041597393678630136932574450837982593210399370333578887450410911663220219423601973078501237709613593311133945501455828164291429228495931943107997137587307522565029820756690578833

n2 = 847796795638781450678718708664542960446354226336422534142899480441478781747168340722544245493739168125415291376063352480076469305992008517388366298914970810765149321160596112226917023146371080685458239747986992197343482255681414590678694753885521068656675164266739274608505094927725285868801825144058835115051061857233824816176186349372737400492228548130718029270482313906040935333159681273527671359469173939861889228505791626525994180917670701909816457560622922219797109618405842358250940062127841301193206255543580550667149741357342408703680375118252445296600962244008043713708516004025217199954286478272550961283413053789743740774140439284662596273452124779590753836094450154459078034659421366584354005421566290862244000178569163732971816333961711759000171156293724203334889496589376907683142167883476184246287660764821622298961378903818077158234683927321823293466245584486980446609569799420950073036635602004293246754252079757527610246223280774592566063422181158810677919909523144033543195999214800559998598003329294711989868113423468536273984117507008756542731210465222475943122324672467669623079721727526348599823126409108190030551584092950358235465140166515452377475799157617227362838246912839086733412861436353117994501342653

p = gcd(n1,n2)

n = n2

q = n/p
e = 65537

phi = (p-1)*(q-1)

d = invert(e,phi)
f = open("./cipher","rb")
c = f.read()
c = int(c.encode("hex"),16)

print("%x"%pow(c,d,n))[1:].decode("hex")

문제 파일은 아래와 같다.

revolutional-secure-angou-de97106aa248a41a40fdd001fc5f7b4b4f28a39eb6bcabf8401b108b7a8961c5.7z

압축을 풀어보면 암호화된 flag, pem 형식의 공개키, 문제 소스가 존재한다.

generator.rb

require 'openssl'

e = 65537

while true

  p = OpenSSL::BN.generate_prime(1024, false)

  q = OpenSSL::BN.new(e).mod_inverse(p)

  next unless q.prime?

  key = OpenSSL::PKey::RSA.new

  key.set_key(p.to_i * q.to_i, e, nil)

  File.write('publickey.pem', key.to_pem)

  File.binwrite('flag.encrypted', key.public_encrypt(File.binread('flag')))

  break

end

소스는 루비를 통해 pem 형식의 공개키를 만들고 해당 공개키로 flag를 암호화하는 구조이다.

pem 파일에 존재하는 공개키를 구하기 위해 아래 툴을 사용하였다.

ssrinc@ssrinc-virtual-machine:~/RsaCtfTool$ ./RsaCtfTool.py --key ./publickey.pem --dumpkey

[*] n: 16809924442712290290403972268146404729136337398387543585587922385691232205208904952456166894756423463681417301476531768597525526095592145907599331332888256802856883222089636138597763209373618772218321592840374842334044137335907260797472710869521753591357268215122104298868917562185292900513866206744431640042086483729385911318269030906569639399362889194207326479627835332258695805485714124959985930862377523511276514446771151440627624648692470758438999548140726103882523526460632932758848850419784646449190855119546581907152400013892131830430363417922752725911748860326944837167427691071306540321213837143845664837111

[*] e: 65537

문제에서 제공해주는 파일은 아래와 같다.

captured_a4ff19205b4a6b0a221111296439b9c7

{N : e : c}

{0xfd2066554e7f2005082570ddf50e535f956679bf5611a11eb1734268ffe32eb0f2fc0f105dd117d9d739767f300918a67dd97f52a3985483aca8aa54998a5c475842a16f2a022a3f5c389a70faeaf0500fa2d906537802ee2088a83f068aba828cc24cc83acc74f04b59a0764de7b64c82f469db4fecd71876eb6021090c7981L : 0xa23ac312c144ce829c251457b81d60171161655744b2755af9b2bd6b70923456a02116b54136e848eb19756c89c4c46f229926a48d5ac030415ef40f3ea185446fa15b5b5f11f2ec2f0f971394e285054182d77490dc2e7352d7e9f72ce25793a154939721b6a2fa176087125ee4f0c3fb6ec7a9fdb15510c97bd3783e998719L : 0x593c561db9a04917e6992328d1ecadf22aefe0741e5d9abbbc12d5b6f9485a1f3f1bb7c010b19907fe7bdecb7dbc2d6f5e9b350270002e23bd7ae2b298e06ada5f4caa1f5233f33969075c5c2798a98dd2fd57646ad906797b9e1ce77194791d3d0b097de31f135ba2dc7323deb5c1adabcf625d97a7bd84cdf96417f05269f4L}

{0xcb26469a1b726d964cc0d3c8f2e486860b7252643b3c974857abc04cc93eca7167138e0cc5cbaa39b4c47daa6ccc5d546d6bfd4171f3ed3f1b0bfe30c22010e3376ec551ba46380cfa25495c7b1299ae7b02409523845fc1b3ccba46a19a4f58dd92c330a8a1ccb5f9000fd8d2b526be54528a237bfc34e24e3c59b2dffba473L : 0xb2a434913ffa775d4204165e30f875eecbdd1be46ef437ee4b93822ccd983a53a5860fd81b5c3f7aabe4c4a04c0ff9440729b50e5386db77c396b9f59a1eb8fb6986c1c4a4c3b2da75ae9c84fc589330f597442f526e2303a83ce75b58821a41238c0f2c30065cc44341d742b30605cc651ee57ed42255a34b173bdba31ee567L : 0x99f2c46f900977a329de45c070b8323ba4927a9d09ae28eb72b8d6741eb7929e88f3c619df2f73e7bcb540ca1e342b6644883834ade9e49cfa534a60e60259222ddf4b7465aa5519654aa576c7b27dbfd5d9b7f8ad68ce99373b4cde87fdde3f2209067d8774c8512e75e32a359a555c62e4ac95f9063a14cb15516a5b9121a3L}

..생략..

위와 같은 형태로 {N : e : c}에 해당하는 값들이 여러개 존재하는데 e 값을 상당히 크게 잡아서 winner Attack 공격 가능성이 존재한다.

위의 모든 N:e:c 쌍 중 winner Attack이 먹히는 값이 있는지 브포돌려서 개인키 구하고 복호화하면 된다.

https://github.com/pablocelayes/rsa-wiener-attack

위 소스를 다운받아서 RSAwienerHacker.py 파일을 조금 수정해서 돌려줬다.

solve.py

Created on Dec 14, 2011
  
@author: pablocelayes
'''

import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator

def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)

    for (k,d) in convergents:

        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("Hacked!")
                    return d



if __name__ == "__main__":
    f = open("./capture","r")
    capture_list = f.read().split("\n")
    capture_list.pop(0)
    for i in capture_list:
        tmp = i.replace("{","").replace("}","").replace(" ","").replace("L","").split(":")
        n = int(tmp[0][2:],16)
        e = int(tmp[1][2:],16)
        c = int(tmp[2][2:],16)
        d = hack_RSA(e,n)
        if d!=None:
            print "d = " + str(d)
            print("%x"%pow(c,d,n)).decode("hex")

문제는 다음과 같다.

source.py

flag = 'TWCTF{CENSORED}'

# Public Parameters
N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
e = 65537

# Encrypt the flag!
for char in flag:
    print(pow(ord(char), e, N))

enc_flag

9073209977571176486825453267118351996016396235857623493182258724402523182425555398048461088180575997426276026776186441023571190870577545894667546140441145538176352391499376279774875943812941321565506013356240326235158415041323709138860753984228634160552040417002326854872319407516200542564071756611880349380322282130265915072405694912128104078505106072784722670288292878670301302909960910520529391182927036489958388823511447221117040898358990430312656065571576446469592472217394596577973531530126373565564994195530324540432367900449603179849204693929275999798234441199340509474634967526614647348655247823230784374
35639404627961781906461142088755137025298630410895631726441472610366623418342364917283665767957562174282457589855677069495230225819581200731431201665184892116733696486682454477915290834433777530535524437371339472350901843618705506005661289326664321691979577977602624815055003117998229419500683672655441419257356643852257251251761502995787965709527112696847071565558861604427364918548619913860926470431333287513742767137365798593418198144415567391257323940575314966786015734312154108604715446101475223727342693907796501114753375280182345362719422538419079170715967729017805398797931366993519156066479380119809407749
29970742560802286128437550167617662948565107399193467157016675822924072945425459560240723871886060997775695066335935643764351669954293612699598869470877609376021471072760517084396091286414268314025266921431195032977653702514792415001248075629193225762672546597247381460826494613102523960838451955661302078496325094813575402182208938085376338620166447700573430340174738180230002573129580484509212273973043579080949823666844684955818141112680250709742302040557969338361223048029382382856263109719029545309245888995127887228177601466240736947809755549463788679785044683353591671286918635707381665684957867916158256949
9073209977571176486825453267118351996016396235857623493182258724402523182425555398048461088180575997426276026776186441023571190870577545894667546140441145538176352391499376279774875943812941321565506013356240326235158415041323709138860753984228634160552040417002326854872319407516200542564071756611880349380322282130265915072405694912128104078505106072784722670288292878670301302909960910520529391182927036489958388823511447221117040898358990430312656065571576446469592472217394596577973531530126373565564994195530324540432367900449603179849204693929275999798234441199340509474634967526614647348655247823230784374
6505165269355349459207146663366047441688194958375318364558535173856663450712228704199777355430120346472437926308005168084164236777799358193673817242751350551129761039157690169023013004512588912294543463516411036479035366287351595535944141685254682636766525957625559957518566299296096642785180632298737381753096931371353732906806665505797027298156421929506483811881951997420752668734446176972811145325901107674607822548260986050552942913613453978790269275942433813911123981987320096944112043982171977835970320689551870847467672632789230490245769533853283172375637080945198548214252880070232242439832820376020827270
21183213341593498738516444880543177493922005619583805574621036610845469192010328280773548470111009986871538885425478935646973995507100891215474272395863721865526341059719628170496111172777431901923738040338575993679287205000994133882661468882632557617292897597173414257540085862308519556541967532509933234492153275218004343688362709977324491456249463253627826867702931115952768729397718933895218798741394694581409210667757016552534836181469227211377884483066055101186770442079773603153741831446549174996578414814900577286574676828436588641203924556681193171762756103136365796626495419220299745139504044747791030657
35281408092375952281726917090787142632733066563620991872002918692378166030610011447579042180082695834448370457076107980397712190086934090736939295047739108983311280069632388023724537185206135081640708416065752200674950158226541934310820828884784320648574385481184792432883840428832675118865022388604992184306433162856083501724629453140816907588357066877849638057796037811471382243339150192266945556056920084520661254644740550996346916309525106638714564549966779826545146543226245351244347767520267740976227220806375754780018194765576617703742034900612204265907753037602258832036675965585326987121730208904172636707
9101532610704319801229002627568606593118376880231363961793878928022682616808257607109430196313625958134631704058601693308284947736738665470244813934118299151452767791230856972131812540721505259138770769757869844334681886944409230647759469220912955547226599154678486454341028553818030097462570293871670067871193147146142698847930591071625262873141933952857468878191419947394293498446678303058453036476382121602756768748298356860355063204128785975756727271149328857774395653350883235189149487626224203793753774251337959040605167763646680641380742690050113762978662536767158651047697949489504622384197817837009805899
19727343590375254587632064140287699566563861529445468621638884818761861540961749277853179945255843397536566044480303263556254457161104941393645917691400698065333537334779814570503718249229475690196783419679830207498236110734650420609935794287945715103900372168348961901833772377802379479319644431008757815787334189780063235801416793468059424958573205997627164009534531784146324794250969016066689012860836352144213050795110337215547546732047516573017499097151983502940550806452813587410367538308128332213316272151085118366028973986023768617211377151718510089448930252336976332354607451783997638889985033237270143000
19727343590375254587632064140287699566563861529445468621638884818761861540961749277853179945255843397536566044480303263556254457161104941393645917691400698065333537334779814570503718249229475690196783419679830207498236110734650420609935794287945715103900372168348961901833772377802379479319644431008757815787334189780063235801416793468059424958573205997627164009534531784146324794250969016066689012860836352144213050795110337215547546732047516573017499097151983502940550806452813587410367538308128332213316272151085118366028973986023768617211377151718510089448930252336976332354607451783997638889985033237270143000
4445090445035309816967308047543919771789262531454517330433510565884369964378364605126226379819564829968488441058652506153262173239057050014566164621236559886897342588940445365608806667121789509027430166785283629129835559641423222470548437137085092267666689140100996007770120912463378323231522269978350165368055010106191244418791128640304446285109189459476433859526044671708676266353806769784954069238002071785082141503102486267921996976823912847921270611519062660030226965810630623647778242153341864677007897561440886995514761812023703358772010858242587672016375310824639504946900189098924010345259054082842462952
31489402022237845095713161555001836257530006471622299194679768644155916609549158574276114572220392183225055133158459214892388896393994816734758651928499631810524923518775717585896197183719011892736579692280180081227822350261519282412322947820015241944858673902001159393951757302936493328485381201812608014183954031226460217543105912866745071626776230347839783360708720981407649649955548220895829413187995263132828649329317684457074878797275638819579478233856655925392114867070177288400223153091926885999827210039281985405009690948796370190764595673615665288826527052161511322777467493975861282833820882856374851534
12162447081760673920818643554030757796301331887670032400173183950958372037923153779101114518800878662669193327234676755098501994856505925588938588147627222346418579875160828453373675031697330271241666811616528649626590785905375841865930581008555819760506462114408403893584247203331887414856156039545144175164912450208727932613202090824467408538115899554054403698251263868802055049783186220064659756518127744287353679560300160686602645213626430963599368771180591237896905830755596491910302237379297313673792354864377434884060559130006006741703356932449048458603684568158407356416615593652760086365317869765908887325
7614305733781939066447122348803189917373287147568651764965213030749807399485484322047897612051860731714216366150477837361431739543136904485219669180916405411738000788721017772411359501201129068067345416077041593698798902971482702218995094662687418603328550543751730581653237946791319838231000903206634501454848858633475328021270871124103263667264998568239850985283877083399747580436290629850807257257822672682275745341774055095177776018754664274959088627193403505950285396668902896974422056354568588387407148914323680129699728249546517637740465696761867411721105292606132614457797912681190579464754692178074288432
4445090445035309816967308047543919771789262531454517330433510565884369964378364605126226379819564829968488441058652506153262173239057050014566164621236559886897342588940445365608806667121789509027430166785283629129835559641423222470548437137085092267666689140100996007770120912463378323231522269978350165368055010106191244418791128640304446285109189459476433859526044671708676266353806769784954069238002071785082141503102486267921996976823912847921270611519062660030226965810630623647778242153341864677007897561440886995514761812023703358772010858242587672016375310824639504946900189098924010345259054082842462952
17123640712605486455710331503622149566381895546952371114127099144731126664255209549917555867405427059867732972283523645802981139955091908210987774319048157763180620099419426954198298442527633557343921414871801495924365946643742260302222329777691088689490433561268494614133918271392455570351732278861137935534144740792912463367825185307909549573973115626433511890886427014705525168084527676204902364574079608349328609735158096556056534370160007219534807220550313946711950618126886431458992114623708552088071858757603459331590270703529871979587852610846623171550166793798422077258772030354999760223188522132363046991
7614305733781939066447122348803189917373287147568651764965213030749807399485484322047897612051860731714216366150477837361431739543136904485219669180916405411738000788721017772411359501201129068067345416077041593698798902971482702218995094662687418603328550543751730581653237946791319838231000903206634501454848858633475328021270871124103263667264998568239850985283877083399747580436290629850807257257822672682275745341774055095177776018754664274959088627193403505950285396668902896974422056354568588387407148914323680129699728249546517637740465696761867411721105292606132614457797912681190579464754692178074288432
4445090445035309816967308047543919771789262531454517330433510565884369964378364605126226379819564829968488441058652506153262173239057050014566164621236559886897342588940445365608806667121789509027430166785283629129835559641423222470548437137085092267666689140100996007770120912463378323231522269978350165368055010106191244418791128640304446285109189459476433859526044671708676266353806769784954069238002071785082141503102486267921996976823912847921270611519062660030226965810630623647778242153341864677007897561440886995514761812023703358772010858242587672016375310824639504946900189098924010345259054082842462952
20363550882654656735712963147998538133764637873870133611050214874932713869759354432762182489154746956659530792748712009467706322316422789671158849556725585574743014878264003153724533655903940543399055564251373527306367498696880372355974158195209245652047044565961920636169427251288081831523847056680568954082761535975143622487783020431400018132089211820129843634233950617494095939185923688192584293665299930423599277271190380871612729583568891854409495233551826919062929941588416043949225548978630364031281835831744459011897180506462438324390682101572937023619706529875639300879007478466999609188887673123117209214
35281408092375952281726917090787142632733066563620991872002918692378166030610011447579042180082695834448370457076107980397712190086934090736939295047739108983311280069632388023724537185206135081640708416065752200674950158226541934310820828884784320648574385481184792432883840428832675118865022388604992184306433162856083501724629453140816907588357066877849638057796037811471382243339150192266945556056920084520661254644740550996346916309525106638714564549966779826545146543226245351244347767520267740976227220806375754780018194765576617703742034900612204265907753037602258832036675965585326987121730208904172636707
25661750150853878754481240488233682685517882929639728814204202272300466944029751885011417647185955996359405511812784463409308971670683299387591171281003655244009584382686676455602431966589035323543850991548183390364717650691625896510716018736326547862654140089659211608838212532579483772844608519496561750351067818473538036061228592093439093498669900206177604488003600893640301509323953394788450530568965046074374334569239897130350502591930457667645069637013800325558226517891334098213138664593715281493978250742348707920991717528287382299191564243044640233524841905412208103707160260558591951416676959307806215873
4737418197186592391586354472202635752008590916595183972465218893728984408576507219754756034257570062765539718361106275457290914012214818230187592078034620492127916852822584051869220339575175210112415729295137337534016600589496188204746588011191924526335111889982129997219996968394467426912082167640098296817533219415565903060917501772614737710895898803203456338300434543951124098288424726341437663499204600285075025297455076520034553966868158129943277982252596529840140662262808730320101013990956487314997739426728293826606488664708795806275867014436712077975555430580706595074184505085748631037695311359265814207
11240119660150979130437010834353812296017155111309439220183308849078858227855991580629935251160701236908831103145069249874891107420683432062612665536612579632424859570115647906861174185022272424579522026855349536403185750057864269381747030358151291562103266385870512025415554221071516346694005930799310152192570760986978549090327441829191065302181485759112788523209845375063401092061615955074279097798169788747371586081874107564321734493519543850720805645294745402722149032580939364203729403311298491779041445545543686221479651228590917901489455191288730608899488042870032701482338129174915458598330333698339237521
9101532610704319801229002627568606593118376880231363961793878928022682616808257607109430196313625958134631704058601693308284947736738665470244813934118299151452767791230856972131812540721505259138770769757869844334681886944409230647759469220912955547226599154678486454341028553818030097462570293871670067871193147146142698847930591071625262873141933952857468878191419947394293498446678303058453036476382121602756768748298356860355063204128785975756727271149328857774395653350883235189149487626224203793753774251337959040605167763646680641380742690050113762978662536767158651047697949489504622384197817837009805899
31489402022237845095713161555001836257530006471622299194679768644155916609549158574276114572220392183225055133158459214892388896393994816734758651928499631810524923518775717585896197183719011892736579692280180081227822350261519282412322947820015241944858673902001159393951757302936493328485381201812608014183954031226460217543105912866745071626776230347839783360708720981407649649955548220895829413187995263132828649329317684457074878797275638819579478233856655925392114867070177288400223153091926885999827210039281985405009690948796370190764595673615665288826527052161511322777467493975861282833820882856374851534
11240119660150979130437010834353812296017155111309439220183308849078858227855991580629935251160701236908831103145069249874891107420683432062612665536612579632424859570115647906861174185022272424579522026855349536403185750057864269381747030358151291562103266385870512025415554221071516346694005930799310152192570760986978549090327441829191065302181485759112788523209845375063401092061615955074279097798169788747371586081874107564321734493519543850720805645294745402722149032580939364203729403311298491779041445545543686221479651228590917901489455191288730608899488042870032701482338129174915458598330333698339237521
16720704891001160160511604046230034068017443633324944107643953041525029637475359045544222918596906514858175672077005030029646528275973947925424106660603416024101755629235987451663480919716815710453555727545586520911951104742920461376732853160755293429400576680667408992248991205547254368426122415960086723047971053279114784542893495494822477973438479488654683797880988580652670499899163395980039135520914163301462064745612533965959340971637913982554044048195794501437803019655664987668673582368766149289378623999422915164409242126795125100072233351736630846695814184161368800692814633567060875440309395003605294126

암호화를 한글자씩 하고있어서 그냥 브포 돌려주면 된다.

solve.py

#flag = 'TWCTF{CENSORED}'
f = open("C:\Python27\\flag_enc.txt")
flag_list = f.read().split("\n")
print int(flag_list[1])

# Public Parameters
N = 36239973541558932215768154398027510542999295460598793991863043974317503405132258743580804101986195705838099875086956063357178601077684772324064096356684008573295186622116931603804539480260180369510754948354952843990891989516977978839158915835381010468654190434058825525303974958222956513586121683284362090515808508044283236502801777575604829177236616682941566165356433922623572630453807517714014758581695760621278985339321003215237271785789328502527807304614754314937458797885837846005142762002103727753034387997014140695908371141458803486809615038309524628617159265412467046813293232560959236865127539835290549091
e = 65537
flag = ""
# Encrypt the flag!
for i in flag_list:
    for j in range(127):
        if pow(j, e, N)==int(i):
            flag += chr(j)
            print flag
            break