CTF - Alice doesn't know algebra - Cryptography - Codeby.games

2023-11-25 2024-11-18 854 слов 4 минут

CTF задача "Alice doesn't know algebra" на платформе Codeby.games

Содержание

1 Исходные данные

Ссылка на задачу
Alice doesn’t know algebra

Описание
Alice took a long time to decide which exponent to choose when encrypting the key. In the end, she decided to use both…

Сложность
Medium

Сервер
62.173.***.***:11***

Файлы
Alice_doesnt_know_algebra.zip

2 Решение

2.1 Анализ исходных данных

Распаковываем архив task.zip. В нем только файл cipher.py. Смотрим содержимое cipher.py

cipher.py

#!/usr/bin/ python3

from binascii import unhexlify
from Crypto.Util.number import bytes_to_long, getPrime , long_to_bytes

intro = ("""   

          !GPPPPPPPP?                                                                   
          P@@@@@@@@@#                                                                   
       @@@7      ^!~J@@@@@@P                                                            
   .!!7PGG~      :^:!###GPGY!!!                                                         
   J@@@   .^:::::::::^^^   ~@@@.                                                        
G##J^^^::::^:!#&&7:^^~~~:..:^^^G###########BB#########BBB##########BB###!               
@@@J   ^^^~7!?&&&Y!7!~~~^:^.   #@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&&&&@Y...            
&@@J   :::G@@&   G@@&~~~^::::::^~~^::^^~^~~~~~~~^:^^^^^^~~^::::^^.      ?@@&            
&@@5 ..:::G@@#   G@@&~~~^:::^^^^^^^^^^^~~^^^^^^^^^^:::::^:!P55^:::......5@@@            
&@@P::::::G@@#   G@@&~~~^::^^^^^~^~!!!!!!^::::::^~~^::::::?@@@!::^~^~!!~G@@@            
@@@G:^^:::^!~7&&&J~!~^^^:::^~~~&@@@@@@@@@@&@@@@@&&@#777#&&G...B&@P:::777B@@@            
G##P???^:::::~&&&7::::::^^^~YJJB################@@@&7?7&@@B   &@@B^^^7?7B@@@            
   J@@@~^^::::::::::::::^~~5@@@.                G@@&777&@@B   &@@#77777!B@@@            
   .!!7B##?^^^^^^^^^7BBB###P!!!                 :!!?#&&J!!^   ^!!Y&&&&&&5!!~            
       &@@P!7777777!Y@@@@@@5                       .@@@:         !@@@@@@?               
          P@@@@@@@@@#                                                                   
          !GPPPPPPPP?                                                                   
          
          """)

print(intro)

FLAG = open("SuperSecretflag.txt" , "rb").read()
KEY = open("SuperSecretkey.txt" , "rb").read()

class Cipher():
    def __init__(self):
        self.p = getPrime(256)
        self.q = getPrime(256)
        self.e_1 = getPrime(256)
        self.e_2 = getPrime(256)
        self.N = self.p * self.q
        print(f"N: {self.N}")
        print()

    def encrypt(self, pt):
        if len(pt) == 0:
            return 0
        ct_1 = b""
        ct_2 = b""
        pt_num = bytes_to_long(pt)
        
        ct_1 = long_to_bytes(pow(pt_num , self.e_1 , self.N))
        ct_2 = long_to_bytes(pow(pt_num , self.e_2 , self.N))

        return ct_1, ct_2
 
    def decrypt(self,ct):
        return self.encrypt(ct)
    
def check_input(phrase):
    while True:
        try:
            your_input = int(input(phrase))
            break
        except:
            print("Invalid int format")
    return your_input

def check_input_hex(phrase):
    while True:
        try:
            your_input = unhexlify(input(phrase))
            break
        except:
            print("Invalid hex format")
    return your_input.hex()

cipher = Cipher()

while True:

    print()
    print("[1] - Зашифровать текст")
    print("[2] - Расшифровать текст")
    print("[3] - Получить флаг")
    print("[4] - Получить зашифрованный ключ")
    print("[0] - Выход")
    print()

    your_input = check_input("Выберите действие: ", )
    print()

    if your_input == 1:

        pt = check_input_hex("Введите исходный текст в hex-формате: ")

        ct_1, ct_2 = cipher.encrypt(bytes.fromhex(pt))
        print(f"Шифротекст первый: {ct_1.hex()}") 
        print(f"Шифротекст второй: {ct_2.hex()}")  

    elif your_input == 2:

        ct = check_input_hex("Введите зашифрованный текст в hex-формате: ")
        pt_1, pt_2 = cipher.decrypt(bytes.fromhex(ct))
        print(f"Исходный текст: {pt_1.hex()}")

    elif your_input == 3:
        input_password = input("Введите ключ: ")

        if input_password.encode() == KEY:
            print(FLAG)
        else:
            print("Ключ неверный!")    

    elif your_input == 4:
        print("Ключ:")
        enc_key_1, enc_key_2 = cipher.encrypt(KEY)
        print(enc_key_1.hex())
        print("Ну или...")
        print(enc_key_2.hex())

    elif your_input == 0:
        print("Игра окончена . . .")
        exit()

Подключаемся к удаленному серверу

output.go

[amyasnikov@ubuntu:~]$ nc 62.173.***.*** 11***


          !GPPPPPPPP?
          P@@@@@@@@@#
       @@@7      ^!~J@@@@@@P
   .!!7PGG~      :^:!###GPGY!!!
   J@@@   .^:::::::::^^^   ~@@@.
G##J^^^::::^:!#&&7:^^~~~:..:^^^G###########BB#########BBB##########BB###!
@@@J   ^^^~7!?&&&Y!7!~~~^:^.   #@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&&&&@Y...
&@@J   :::G@@&   G@@&~~~^::::::^~~^::^^~^~~~~~~~^:^^^^^^~~^::::^^.      ?@@&
&@@5 ..:::G@@#   G@@&~~~^:::^^^^^^^^^^^~~^^^^^^^^^^:::::^:!P55^:::......5@@@
&@@P::::::G@@#   G@@&~~~^::^^^^^~^~!!!!!!^::::::^~~^::::::?@@@!::^~^~!!~G@@@
@@@G:^^:::^!~7&&&J~!~^^^:::^~~~&@@@@@@@@@@&@@@@@&&@#777#&&G...B&@P:::777B@@@
G##P???^:::::~&&&7::::::^^^~YJJB################@@@&7?7&@@B   &@@B^^^7?7B@@@
   J@@@~^^::::::::::::::^~~5@@@.                G@@&777&@@B   &@@#77777!B@@@
   .!!7B##?^^^^^^^^^7BBB###P!!!                 :!!?#&&J!!^   ^!!Y&&&&&&5!!~
       &@@P!7777777!Y@@@@@@5                       .@@@:         !@@@@@@?
          P@@@@@@@@@#
          !GPPPPPPPP?


N: 5528421003787152797780905532338533644132966573280985037688431655042011332476181014684652947059175828063517292266175422491347923201331594191535914968309911
e_1: 69711700699061079421281917335076487671413484781984251661406882503217129427749
e_2: 104216655613664737083708985163582773085116384037288226397753589821256726375927


[1] - Зашифровать текст
[2] - Расшифровать текст
[3] - Получить флаг
[4] - Получить зашифрованный ключ
[0] - Выход

Выберите действие: 4

Ключ:
0b28b5908bcd409b69bd63e664149de5776428c6ac567b27f5b21f6dcb16c0d54338cb92688654687a67381720f7808dcbd68da00f0e97566e60b1c960b13f62
Ну или...
094a5fee3aec8f4b508238e311f6ae07e3a41a1111bd989673d38dec767bd0509e3f4d04bd2c645a2d4f266cd0b6bc8eaaa5a13fd5c33236d20c531476e32365

[1] - Зашифровать текст
[2] - Расшифровать текст
[3] - Получить флаг
[4] - Получить зашифрованный ключ
[0] - Выход

Выберите действие: 0

Игра окончена . . .

2.2 Размышления

Известнo:
N - модуль
e1 - первая экспонента
e2 - вторая экспонента
c1 = F ^ e1 mod N - первое зашифрованное сообщение
c2 = F ^ e2 mod N - второе зашифрованное сообщение

Неизвестно:
F - флаг

Перемножим c1, c2 со степенями p, q и получим:
(c1 ^ p) * (c2 ^ q) = F ^ (p * e1 + q * e2) mod N

F == (c1 ^ p) * (c2 ^ q), если p * e1 + q * e2 == 1

Воспользуемся свойством:
d ^ s = d ^ (s * (N ^ k)) mod N при любых d, s, N, k

Т.е. p * e1 + q * e2 = N ^ k
Т.е. gdc(&p, &q, e1, e2) = 1

Находим p, q из уравнения выше, а и затем F:
F = (c1 ^ p) * (c2 ^ q)

2.3 Скрипт solve.py

Напишем скрипт для нахождению ключа в соответствии с размышлениями выше

solve.py

#!/usr/bin/ python3

from Crypto.Util.number import long_to_bytes

def egcd(p, q):
    if p == 0:
        return (q, 0, 1)
    else:
        (gcd, u, v) = egcd(q % p, p)
        return (gcd, v - (q // p) * u, u)

n = 5528421003787152797780905532338533644132966573280985037688431655042011332476181014684652947059175828063517292266175422491347923201331594191535914968309911
e_1 = 69711700699061079421281917335076487671413484781984251661406882503217129427749
e_2 = 104216655613664737083708985163582773085116384037288226397753589821256726375927
enc_key_1 = 0x0B28B5908BCD409B69BD63E664149DE5776428C6AC567B27F5B21F6DCB16C0D54338CB92688654687A67381720F7808DCBD68DA00F0E97566E60B1C960B13F62
enc_key_2 = 0x094A5FEE3AEC8F4B508238E311F6AE07E3A41A1111BD989673D38DEC767BD0509E3F4D04BD2C645A2D4F266CD0B6BC8EAAA5A13FD5C33236D20C531476E32365

g, p, q = egcd(e_1, e_2)
ct_1 = pow(enc_key_1, p, n)
ct_2 = pow(enc_key_2, q, n)

t = (ct_1 * ct_2) % n
t = long_to_bytes(t).decode()

print(f"g={g}")
print(f"p={p}")
print(f"q={q}")
print(f"t={t}")

Запускаем скрипт solve.py

output

[amyasnikov@ubuntu:~]$ python3 ./solve.py

g=1
p=50876718808717398630833481663924268106628133421247601105153259371288643274534
q=-34032013148563943495646408603594819163516768429468729511646574596529289866795
t=it'5_v3ry_*****************

2.4 Получение флага

Подключаемся к серверу, вводим найденный ключ

server_output_2.txt

[amyasnikov@ubuntu:~]$ nc 62.173.***.*** 11***


          !GPPPPPPPP?
          P@@@@@@@@@#
       @@@7      ^!~J@@@@@@P
   .!!7PGG~      :^:!###GPGY!!!
   J@@@   .^:::::::::^^^   ~@@@.
G##J^^^::::^:!#&&7:^^~~~:..:^^^G###########BB#########BBB##########BB###!
@@@J   ^^^~7!?&&&Y!7!~~~^:^.   #@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&&&&@Y...
&@@J   :::G@@&   G@@&~~~^::::::^~~^::^^~^~~~~~~~^:^^^^^^~~^::::^^.      ?@@&
&@@5 ..:::G@@#   G@@&~~~^:::^^^^^^^^^^^~~^^^^^^^^^^:::::^:!P55^:::......5@@@
&@@P::::::G@@#   G@@&~~~^::^^^^^~^~!!!!!!^::::::^~~^::::::?@@@!::^~^~!!~G@@@
@@@G:^^:::^!~7&&&J~!~^^^:::^~~~&@@@@@@@@@@&@@@@@&&@#777#&&G...B&@P:::777B@@@
G##P???^:::::~&&&7::::::^^^~YJJB################@@@&7?7&@@B   &@@B^^^7?7B@@@
   J@@@~^^::::::::::::::^~~5@@@.                G@@&777&@@B   &@@#77777!B@@@
   .!!7B##?^^^^^^^^^7BBB###P!!!                 :!!?#&&J!!^   ^!!Y&&&&&&5!!~
       &@@P!7777777!Y@@@@@@5                       .@@@:         !@@@@@@?
          P@@@@@@@@@#
          !GPPPPPPPP?


N: 5528421003787152797780905532338533644132966573280985037688431655042011332476181014684652947059175828063517292266175422491347923201331594191535914968309911
e_1: 69711700699061079421281917335076487671413484781984251661406882503217129427749
e_2: 104216655613664737083708985163582773085116384037288226397753589821256726375927


[1] - Зашифровать текст
[2] - Расшифровать текст
[3] - Получить флаг
[4] - Получить зашифрованный ключ
[0] - Выход

Выберите действие: 4

Ключ:
0b28b5908bcd409b69bd63e664149de5776428c6ac567b27f5b21f6dcb16c0d54338cb92688654687a67381720f7808dcbd68da00f0e97566e60b1c960b13f62
Ну или...
094a5fee3aec8f4b508238e311f6ae07e3a41a1111bd989673d38dec767bd0509e3f4d04bd2c645a2d4f266cd0b6bc8eaaa5a13fd5c33236d20c531476e32365

[1] - Зашифровать текст
[2] - Расшифровать текст
[3] - Получить флаг
[4] - Получить зашифрованный ключ
[0] - Выход

Выберите действие: 3

Введите ключ: it'5_v3ry_*****************
b'CODEBY{RSA_*************}'

[1] - Зашифровать текст
[2] - Расшифровать текст
[3] - Получить флаг
[4] - Получить зашифрованный ключ
[0] - Выход

Выберите действие: 0

Игра окончена . . .

И видим флаг CODEBY{RSA_*************}

3 Вывод

Легкая задача, немного математики нужно вспомнить

P.S. Часть данных заменена на звездочки