# Nhập môn lập trình - IT001.P11.CTTN
Tuần vừa rồi lớp CTF NMLT, thầy mình có tổ chức kiểm tra cuối kì bằng các bài tập CTF. Sau đây là WU của mình cho các câu giải được trong quá trình thi.
[TOC]
## substitution

Chall cho mình một file python như sau

KEY = {
    'A': 'Q', 'B': 'W', 'C': 'E', 'D': 'R', 'E': 'T', 'F': 'Y', 'G': 'U', 'H': 'I', 'I': 'O',
    'J': 'P', 'K': 'A', 'L': 'S', 'M': 'D', 'N': 'F', 'O': 'G', 'P': 'H', 'Q': 'J', 'R': 'K',
    'S': 'L', 'T': 'Z', 'U': 'X', 'V': 'C', 'W': 'V', 'X': 'B', 'Y': 'N', 'Z': 'M',
    'a': 'q', 'b': 'w', 'c': 'e', 'd': 'r', 'e': 't', 'f': 'y', 'g': 'u', 'h': 'i', 'i': 'o',
    'j': 'p', 'k': 'a', 'l': 's', 'm': 'd', 'n': 'f', 'o': 'g', 'p': 'h', 'q': 'j', 'r': 'k',
    's': 'l', 't': 'z', 'u': 'x', 'v': 'c', 'w': 'v', 'x': 'b', 'y': 'n', 'z': 'm',
}

def hehe(data, key):
    return ''.join(key.get(char, char) for char in data)

def encrypt(plaintext):
    substituted = hehe(plaintext, KEY)
    return substituted

if __name__ == "__main__":
    plaintext = "W1{???????????????}"
    encrypted = encrypt(plaintext)
    with open("encrypted.txt", "w") as f:
        f.write(encrypted)

Mã hóa bằng một hàm $\displaystyle f:KEY\rightarrow KEY$. Ta dựa vào các phép thế được đưa ra ở trên để giải mã lại flag trong file encrypted.txt

V1{lxwlzozxzogf}
V->W, l->s,x->u,.... 

Ngồi viết tay một hồi thì cuối cùng ta được flag là `W1{substitution}` :)))

## 4ES


Chall cho ta một file python như sau :

#!/usr/bin/env python3

from hashlib import sha256
from random import choices

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


FLAG = b'W1{???????????????????????}'

chars = b'AoThuatGiaDP'
L = 3

w, x, y, z = (
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
)

k1 = sha256(w).digest()
k2 = sha256(x).digest()
k3 = sha256(y).digest()
k4 = sha256(z).digest()

pt = b'AES_AES_AES_AES!'
ct = AES.new(k4, AES.MODE_ECB).encrypt(
        AES.new(k3, AES.MODE_ECB).encrypt(
            AES.new(k2, AES.MODE_ECB).encrypt(
                AES.new(k1, AES.MODE_ECB).encrypt(
                    pt
                )
            )
        )
    )

key = sha256(w + x + y + z).digest()
enc_flag = AES.new(key, AES.MODE_ECB).encrypt(pad(FLAG, AES.block_size))

with open('output.txt', 'w') as f:
    f.write(f'pt = {pt.hex()}\nct = {ct.hex()}\nenc_flag = {enc_flag.hex()}')

Và một file output.txt

pt = 4145535f4145535f4145535f41455321
ct = a5d45cdb322abe38b9da6df19f997696
enc_flag = ecd0486b5c1c5a2b9af4e42abc8891445a97337cf1857e366bff6063bdbeaa7f

Dùng kĩ thuật MITM để Attack: Mục tiêu của ta là tìm lại 4 khóa $\displaystyle k_{1} ,k_{2} ,k_{3} ,k_{4}$. Để tìm lại 4 khóa này thì ta cần tìm lại 4 kí tự $\displaystyle w,x,y,z$ được tạo ngẫu nhiên bằng cách lấy 3 kí tự trong chars. Ta đã biết cả pt và ct thì việc cần làm là ta sẽ đi encrypt pt bằng 2 khóa bất kì rồi lưu lại trong bảng, tiếp đó ta sẽ decrypt ct bằng 2 khóa bất kì rồi sau đó sẽ tìm collision.
Code em lấy ở một bài có ý tưởng giống : https://7rocky.github.io/en/ctf/other/crewctf/4es/

#!/usr/bin/env python3

from hashlib import sha256
from itertools import product

from Cryptodome.Cipher import AES
from Cryptodome.Util.Padding import unpad


pt = bytes.fromhex("4145535f4145535f4145535f41455321") 
ct = bytes.fromhex("a5d45cdb322abe38b9da6df19f997696") 
enc_flag = bytes.fromhex("ecd0486b5c1c5a2b9af4e42abc8891445a97337cf1857e366bff6063bdbeaa7f") 
L = 3
chars = b'AoThuatGiaDP'
char_keys = list(map(bytes, product(chars, repeat=L)))


def encrypt_aes(key, plaintext):
    return AES.new(key, AES.MODE_ECB).encrypt(plaintext)


def decrypt_aes(key, ciphertext):
    return AES.new(key, AES.MODE_ECB).decrypt(ciphertext)


def mitm():
    middle = {}

    for w in char_keys:
        k1 = sha256(w).digest()

        for x in char_keys:
            k2 = sha256(x).digest()
            enc = encrypt_aes(k2, encrypt_aes(k1, pt))
            middle[enc] = (w, x)

    for z in char_keys:
        k4 = sha256(z).digest()

        for y in char_keys:
            k3 = sha256(y).digest()
            dec = decrypt_aes(k3, decrypt_aes(k4, ct))

            if dec in middle:
                return middle[dec] + (y, z)


wxyz = mitm()
assert wxyz is not None, 'failed'

w, x, y, z = wxyz

k1 = sha256(w).digest()
k2 = sha256(x).digest()
k3 = sha256(y).digest()
k4 = sha256(z).digest()

assert ct == encrypt_aes(k4, encrypt_aes(k3, encrypt_aes(k2, encrypt_aes(k1, pt)))), 'Wrong keys found'

key = sha256(b''.join(wxyz)).digest()
FLAG = unpad(decrypt_aes(key, enc_flag), AES.block_size)
print(FLAG.decode())

## hix
Chall cho ta một file python

import hashlib
import random

methods = ['md5', 'sha256', 'sha3_256', 'sha3_512', 'sha3_384', 'sha1', 'sha384', 'sha3_224', 'sha512', 'sha224']

def random_encrypt(x) :
    method = random.choice(methods)
    hash_obj = hashlib.new(method)
    hash_obj.update(x.encode())
    return hash_obj.hexdigest()

def main() :
    message = open("./../private/flag.txt", "r").read()
    enc = []

    for char in message :
        x = (ord(char) + 20) % 130
        x = hashlib.sha512(str(x).encode()).hexdigest()
        x = random_encrypt(x)
        enc.append(x)

    with open('encrypted_memory.txt', 'w') as f :
        f.write("ct = " + str(enc))

if __name__ == "__main__" :
    main()

và một file txt:

ct = ['f189636f8eef640b55d03387864fd17efd324453cc9276be5ff6bd4da88b13fca72438daaab00830a6d14330d37c0f7bee1e7c32d5dda0541a171f66a2343dc1', '1388cafa58065fa0c04372ce57f303cc4ec9fe62', 'f6266e2849bf8b8575701814cc3f3eb5369e887db54b34e85b1e4608b4fbf5e5', '31f33ac191e818db784cf8321d70f84763db2b2e599f90cf65868eec85a10f20ae0e23aa1cd48c2f13eec355b2975089490761a291ac2a1bcf33f5fbecead431', '981e4bce5dede3faa51a936f650e2c1d64169493860c67d68a1ffbbfa32f58598e7869f3f11aefc1620ee8d3ebe4e5f5', 'f06ffaaa6290bf47d26ba2c09c28dddd8f5bcad6ac464ec17fea48040acf1214d10bc109b7c47cffddb6bccd6b61b61a9e629a8f47ab26b80593f29c8c297489', 'a7d95b3bbde885b4eaa76afc6572e18e4483351005f637fe1f5a7bc0b000fe1f', '85245de371c327440a5f343f27d6df361225806e679950bab3a5a336', 'ea1923e909de3c3c3384ad9ae7696d73', '21df20aab35967470aada32375f535d4a735789bf0789fd421f85163c4d75c6e', 'b9491ae1a9de40d30a86c00139bd7d6f496f5bf4ce013bc2d5a43a97', '03f061f60f3527b15ff31d31dcce0761', '981e4bce5dede3faa51a936f650e2c1d64169493860c67d68a1ffbbfa32f58598e7869f3f11aefc1620ee8d3ebe4e5f5', 'f2a1a7e9dd5e6363050b0cdb0579ebfebdc5e348ab538bdcf47616139351cf2b9f92cb4d14446b3ad8bf182875b81e75', '24aaafc58a2b897aed5829b2e96d73b1de7cd680d76a1143cdc8baef', '6d80d11e5f1161ef86619dcdb186852b5218d6ac224b81b63555fe73741631c36ae0bcb5b3228fbed796c22dedeed587c9d65ddb825aee4fae92b6619e7ffd8f', '6f8b39550106044625102ee0cabf9fe1393f0013388633d5742fcc7e8df7708793a96885b9d18b795a2b0d9014704b9f', 'ddf3c543be9cac44f3af078583fe5fddb64104d93308c146c23f52ff25b2a6e23606c42dc0060a4dd9b11b446759cb5de1844471eb3d6d25c43c6fcc0d8d60c4', '95f2739053cf64555b0c0662b5e2d63822433f7fcac6960de6d57efda427461a58c6e2ffac6da6f4caa9407df10cc0be', 'a1bd4e0efc7ce8bd1d63433a0baa87e3a486fbfe2729d73d1dbf7d2822d201ee8726c6d94da1f09f1a53554e440ad6041ecab545b2085dc28c6f6849f0fcea23', 'a7d95b3bbde885b4eaa76afc6572e18e4483351005f637fe1f5a7bc0b000fe1f', '2b4561a521a82af6a26dfb76078ca97ba53a720f7ee67d923a6d3a13', 'b21ed1f3d501a8a842ef1b26ed3863cf10cf8231ee23a079f749cfa322702c8e', 'd798a32b52384219f8779dccf8b2173f4b73f075cbeb4507ee83c94e', 'b863fa3492fb87edcdef766f38a508ed', '9f876db4b58c1b7e499f35cdbd533a810060a0c8250bfc5421e0f42b2715b027', '4b14748ba0f3da581ddd7ec49dac41d34ea1ee6dae90818333b11501', '85153b2a5f8dea7f5488906cb65d61e9ac0666057636ff6b356dd4d8d0fc5d20', '6b91d6259827176bcb3f312a8faca297e56c7e627235b930cf8163b3e7a5328b', 'b21ed1f3d501a8a842ef1b26ed3863cf10cf8231ee23a079f749cfa322702c8e', '4c8740f90af1055f194a4c8e1b69522da228812465eb72b82b35c927bc48bf9d', 'b248b6b2f2c9365aa9a0e9b37a8057effd29bb2f34c79ec0b40124d08986832b5d227db95cb97b176541589985762d9a', '7260f9b5d1c58d0609523114ed324f396335d940f852dba558461b34c5a53630', 'a1bd4e0efc7ce8bd1d63433a0baa87e3a486fbfe2729d73d1dbf7d2822d201ee8726c6d94da1f09f1a53554e440ad6041ecab545b2085dc28c6f6849f0fcea23', '1077caf3ed754ed8fbd49c76134906e8', 'f3565219d115ec74a85056997cc25e98e3e4912a31c858c1e45b841047698e93', '83315b8fa07a35b12e3f47ebb365268b4a4a8ef2', '64c008d6460c2b98aba616b1d0d11a06b9df564b87d3aeedda83b36aacd3d0c160465109eb06c62e86e360cf026faa27a616dbbf2bec269be9ad128af96073bb', '60bbd94b3ac3ea7149fc6cd850d72d4f1750601275832815dd9a23d4c3757d84aca29d716da5dd72a0045f15ff969925', '94327e8c8321421e72f52cd726336e824630ec7dda31b07ce83f11b8234aea7a', 'a69ef62254280226cc4223a2341c727afcd7ce4e3ffd3f2f1c57d9d3cd30659b52b1c2b56f911a7157041b5f0ff8176f', '3c904622c8d8d79c6704d50ae0175b049b3a5708705ecdce932fe426b9f46f1bd6585b8288c1d38f6301c31af5feac02', 'a3939bf491ffd9824056e249d6e355d8423855f0']

Đầu tiên ta để ý hàm sau:

def random_encrypt(x) :
    method = random.choice(methods)
    hash_obj = hashlib.new(method)
    hash_obj.update(x.encode())
    return hash_obj.hexdigest()

Khi ta gọi hàm này thì nó sẽ chọn ngẫu nhiên một hàm băm sau đó trả về giá trị $x$ đã được băm dưới dạng hexadecimal. Còn về flag sẽ được mã hóa từng kí tự như sau:

  for char in message :
        x = (ord(char) + 20) % 130
        x = hashlib.sha512(str(x).encode()).hexdigest()
        x = random_encrypt(x)
        enc.append(x)

Nhìn thì có vẻ ngẫu nhiên nhưng ta có thể lợi dụng tính chất cố định của hàm băm để bruteforce lại kí tự ban đầu.

Cụ thể mỗi hàm băm H tạo đầu ra có độ dài cố định cho nên ta có thể dựa vào độ dài của các char sau khi băm để xác định ngược lại thuật toán băm và brute force:

import hashlib

hash_lengths = {
    32: 'md5',
    40: 'sha1',
    56: ['sha224', 'sha3_224'],
    64: ['sha256', 'sha3_256'],
    96: ['sha384', 'sha3_384'],
    128: ['sha512', 'sha3_512']
}

def identify_hash_algorithm(hash_value):
    length = len(hash_value)
    return hash_lengths.get(length, "Unknown")

def hash_attempt(method, data):
    try:
        hash_obj = hashlib.new(method)
        hash_obj.update(data.encode())
        return hash_obj.hexdigest()
    except ValueError:
        return None

def reverse_character(hash_value):
    algorithms = identify_hash_algorithm(hash_value)
    if algorithms == "Unknown":
        return None
    if not isinstance(algorithms, list):
        algorithms = [algorithms]
    for method in algorithms:
        for i in range(130):
            intermediate_hash = hashlib.sha512(str(i).encode()).hexdigest()
            if hash_attempt(method, intermediate_hash) == hash_value:
                original_char = chr((i - 20) % 130)
                return original_char
    return None

encrypted_values = ['f189636f8eef640b55d03387864fd17efd324453cc9276be5ff6bd4da88b13fca72438daaab00830a6d14330d37c0f7bee1e7c32d5dda0541a171f66a2343dc1', '1388cafa58065fa0c04372ce57f303cc4ec9fe62', 'f6266e2849bf8b8575701814cc3f3eb5369e887db54b34e85b1e4608b4fbf5e5', '31f33ac191e818db784cf8321d70f84763db2b2e599f90cf65868eec85a10f20ae0e23aa1cd48c2f13eec355b2975089490761a291ac2a1bcf33f5fbecead431', '981e4bce5dede3faa51a936f650e2c1d64169493860c67d68a1ffbbfa32f58598e7869f3f11aefc1620ee8d3ebe4e5f5', 'f06ffaaa6290bf47d26ba2c09c28dddd8f5bcad6ac464ec17fea48040acf1214d10bc109b7c47cffddb6bccd6b61b61a9e629a8f47ab26b80593f29c8c297489', 'a7d95b3bbde885b4eaa76afc6572e18e4483351005f637fe1f5a7bc0b000fe1f', '85245de371c327440a5f343f27d6df361225806e679950bab3a5a336', 'ea1923e909de3c3c3384ad9ae7696d73', '21df20aab35967470aada32375f535d4a735789bf0789fd421f85163c4d75c6e', 'b9491ae1a9de40d30a86c00139bd7d6f496f5bf4ce013bc2d5a43a97', '03f061f60f3527b15ff31d31dcce0761', '981e4bce5dede3faa51a936f650e2c1d64169493860c67d68a1ffbbfa32f58598e7869f3f11aefc1620ee8d3ebe4e5f5', 'f2a1a7e9dd5e6363050b0cdb0579ebfebdc5e348ab538bdcf47616139351cf2b9f92cb4d14446b3ad8bf182875b81e75', '24aaafc58a2b897aed5829b2e96d73b1de7cd680d76a1143cdc8baef', '6d80d11e5f1161ef86619dcdb186852b5218d6ac224b81b63555fe73741631c36ae0bcb5b3228fbed796c22dedeed587c9d65ddb825aee4fae92b6619e7ffd8f', '6f8b39550106044625102ee0cabf9fe1393f0013388633d5742fcc7e8df7708793a96885b9d18b795a2b0d9014704b9f', 'ddf3c543be9cac44f3af078583fe5fddb64104d93308c146c23f52ff25b2a6e23606c42dc0060a4dd9b11b446759cb5de1844471eb3d6d25c43c6fcc0d8d60c4', '95f2739053cf64555b0c0662b5e2d63822433f7fcac6960de6d57efda427461a58c6e2ffac6da6f4caa9407df10cc0be', 'a1bd4e0efc7ce8bd1d63433a0baa87e3a486fbfe2729d73d1dbf7d2822d201ee8726c6d94da1f09f1a53554e440ad6041ecab545b2085dc28c6f6849f0fcea23', 'a7d95b3bbde885b4eaa76afc6572e18e4483351005f637fe1f5a7bc0b000fe1f', '2b4561a521a82af6a26dfb76078ca97ba53a720f7ee67d923a6d3a13', 'b21ed1f3d501a8a842ef1b26ed3863cf10cf8231ee23a079f749cfa322702c8e', 'd798a32b52384219f8779dccf8b2173f4b73f075cbeb4507ee83c94e', 'b863fa3492fb87edcdef766f38a508ed', '9f876db4b58c1b7e499f35cdbd533a810060a0c8250bfc5421e0f42b2715b027', '4b14748ba0f3da581ddd7ec49dac41d34ea1ee6dae90818333b11501', '85153b2a5f8dea7f5488906cb65d61e9ac0666057636ff6b356dd4d8d0fc5d20', '6b91d6259827176bcb3f312a8faca297e56c7e627235b930cf8163b3e7a5328b', 'b21ed1f3d501a8a842ef1b26ed3863cf10cf8231ee23a079f749cfa322702c8e', '4c8740f90af1055f194a4c8e1b69522da228812465eb72b82b35c927bc48bf9d', 'b248b6b2f2c9365aa9a0e9b37a8057effd29bb2f34c79ec0b40124d08986832b5d227db95cb97b176541589985762d9a', '7260f9b5d1c58d0609523114ed324f396335d940f852dba558461b34c5a53630', 'a1bd4e0efc7ce8bd1d63433a0baa87e3a486fbfe2729d73d1dbf7d2822d201ee8726c6d94da1f09f1a53554e440ad6041ecab545b2085dc28c6f6849f0fcea23', '1077caf3ed754ed8fbd49c76134906e8', 'f3565219d115ec74a85056997cc25e98e3e4912a31c858c1e45b841047698e93', '83315b8fa07a35b12e3f47ebb365268b4a4a8ef2', '64c008d6460c2b98aba616b1d0d11a06b9df564b87d3aeedda83b36aacd3d0c160465109eb06c62e86e360cf026faa27a616dbbf2bec269be9ad128af96073bb', '60bbd94b3ac3ea7149fc6cd850d72d4f1750601275832815dd9a23d4c3757d84aca29d716da5dd72a0045f15ff969925', '94327e8c8321421e72f52cd726336e824630ec7dda31b07ce83f11b8234aea7a', 'a69ef62254280226cc4223a2341c727afcd7ce4e3ffd3f2f1c57d9d3cd30659b52b1c2b56f911a7157041b5f0ff8176f', '3c904622c8d8d79c6704d50ae0175b049b3a5708705ecdce932fe426b9f46f1bd6585b8288c1d38f6301c31af5feac02', 'a3939bf491ffd9824056e249d6e355d8423855f0']

flag = ''
for hash_val in encrypted_values:
    char = reverse_character(hash_val)
    if char:
        flag += char
    else:
        flag += '?'

print("Flag:", flag)

Flag: ```W1{are_you_trying_to_predict_randomness@_@}```

## gcdpoly

Chall cho ta một file python:

from Crypto.Util.number import getPrime, GCD, bytes_to_long, getRandomNBitInteger, long_to_bytes

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    e = 0x101
    if GCD((p - 1) * (q - 1), e) == 1:
        break
N = p * q

flag = b'W1{??????????????????????????????}'

assert len(flag) == 34

flag = bytes_to_long(flag)
x = getRandomNBitInteger(flag.bit_length())

hint = x * flag
more_hint = long_to_bytes(hint) + long_to_bytes(x)

x_enc = pow(x, e, N)
hint_enc = pow(hint, e, N)
more_hint = pow(bytes_to_long(more_hint), e, N)

print(f"{N = }")
print(f"{e = }")
print(f"{x_enc = }")
print(f"{hint_enc = }")
print(f"{more_hint = }")

Và một file encrypted.txt:

N = 17455402175437176532762011936605374319510514858668809934283527533793019636085567941340428251796332874658887034973125379656976787899948739462792044779394617697923593713865571947480575715808220681702040571713834962591162896883126625987542697405715758837886980695935599886296833761332668492586517301554181926290501066261415348762218737641025568994218666972555733452415715789836479580743518759606518560790216074668160062318077354838559692467462868744895402199050233183880016075435689438118159209700791215305127872319962224886262950782267716759134051276573034748789032249652527725069033671937172082733885413797270594046659
e = 257
x_enc = 9996223492945930307599847149030142323594733002172616721058190037475290836989969789254053717666020951921459176187704524599282156785134867888383301434607072014358468217885735213022405058511843363872636247404379439558338700149306005415828454372965267435748808512594750475657894932556732283868780381727090987803428282860149481730335955039459503864265070695125410078101017244023029264699216041534759532946007673595164569006924131708811385328137810260255820693022452407318872511604340046032703603689226966698963947140903268751317131092280784353673781583886340493103149941363175123086894375292235376263422464299937964242529
hint_enc = 14789408518282984435806404374838863944620574135335751718371470938725019307943299519996110191146342336694298360945290481279154411743070024294186906891227799217417210874041187513533095475177536407329059640170945862144612697751930832068191380343375683600799846751305650713478329200992580277004206060405550671431501911580994159286609366370084466999243157644437677404006488711305765810155959071167712372903081938159711179919854865680181098099964158600115467907298067836087274873276020158780106022394580520866275356696118835744838635778222876212312712636991385848611744174549177416655001397274793228678792857731056729401479
more_hint = 11029946941431959428525282661954512235928562456214126818506773711111719425190566952451999044331493580332064561323097236705681748867775061691143721439117904810714121197594096628261432006374462970213237363365127870527463436083313806638082369213886645623998873849163617775630517410918551847474235496220816340531322685920512036201318038335403616434596578979491681508214839604410062184542042494994435105891585296125095470899377721478810921246711310813490006032578790263495042565529710594969722185609497948277910670140174206535208998036166377688284289995920516604924956793172587315806815116854231045587846108456607501836645

Từ đề bài mình đoán được phần nào ý của tác giả là lấy gcd của 2 đa thức với các hệ số thuộc trường hữu hạn $\displaystyle \mathbb{Z} /n\mathbb{Z}$
Trước hết ta cần xử lí giá trị của more_hint để sử dụng các tính chất số học. Ta để ý more_hint ban đầu được tính bởi: `more_hint = long_to_bytes(hint) + long_to_bytes(x)`.

Em có thử ngồi nghịch một chút với python và phát hiện ra tính chất sau:

Phép cộng 2 xâu bytes khác với phép cộng số học thông thường, cụ thể ta sẽ có công thức như dưới đây:

$$\displaystyle more\_hint=hint\times 2^{34\times 8} +x=hint\times 2^{272} +x$$

Trong đó 34 chính là số bytes của $x$. Ta nhân 8 lên sẽ được số bit cần tính của $x$ vì ban đầu khi khai báo $x$ ta sử dụng các dòng lệnh sau :

assert len(flag) == 34
flag = bytes_to_long(flag)
x = getRandomNBitInteger(flag.bit_length())

Như vậy dựa vào đây ta sẽ xây dựng 2 đa thức $f(x)$ và $g(x)$ có nghiệm trên $\displaystyle \mathbb{Z} /n\mathbb{Z}$ sẽ là $flag$ như sau: $\displaystyle f( x) =x\_enc\times x^{e} -hint\_enc$ và $\displaystyle g( x) =x\_enc\times \left( x\times 2^{272} +1\right)^{e} -more\_hint$ vì ta có $\displaystyle ( more\_hint)^{e} =\left( hint\times 2^{272} +x\right)^{e} =x^{e}\left( flag\times 2^{272} +1\right)^{e}$, nếu đưa về mod $\displaystyle n$ thì ta chuyển $\displaystyle x^{e}$ thành $\displaystyle x\_enc$

Code sage giải bài này: Ta sẽ dùng thuật Half GCD để tăng tốc độ tính gcd của 2 đa thức

import sys

n = 17455402175437176532762011936605374319510514858668809934283527533793019636085567941340428251796332874658887034973125379656976787899948739462792044779394617697923593713865571947480575715808220681702040571713834962591162896883126625987542697405715758837886980695935599886296833761332668492586517301554181926290501066261415348762218737641025568994218666972555733452415715789836479580743518759606518560790216074668160062318077354838559692467462868744895402199050233183880016075435689438118159209700791215305127872319962224886262950782267716759134051276573034748789032249652527725069033671937172082733885413797270594046659
P.<x> = PolynomialRing(Zmod(n))

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11

def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)
e = 257
x_enc = 9996223492945930307599847149030142323594733002172616721058190037475290836989969789254053717666020951921459176187704524599282156785134867888383301434607072014358468217885735213022405058511843363872636247404379439558338700149306005415828454372965267435748808512594750475657894932556732283868780381727090987803428282860149481730335955039459503864265070695125410078101017244023029264699216041534759532946007673595164569006924131708811385328137810260255820693022452407318872511604340046032703603689226966698963947140903268751317131092280784353673781583886340493103149941363175123086894375292235376263422464299937964242529
hint_enc = 14789408518282984435806404374838863944620574135335751718371470938725019307943299519996110191146342336694298360945290481279154411743070024294186906891227799217417210874041187513533095475177536407329059640170945862144612697751930832068191380343375683600799846751305650713478329200992580277004206060405550671431501911580994159286609366370084466999243157644437677404006488711305765810155959071167712372903081938159711179919854865680181098099964158600115467907298067836087274873276020158780106022394580520866275356696118835744838635778222876212312712636991385848611744174549177416655001397274793228678792857731056729401479
more_hint = 11029946941431959428525282661954512235928562456214126818506773711111719425190566952451999044331493580332064561323097236705681748867775061691143721439117904810714121197594096628261432006374462970213237363365127870527463436083313806638082369213886645623998873849163617775630517410918551847474235496220816340531322685920512036201318038335403616434596578979491681508214839604410062184542042494994435105891585296125095470899377721478810921246711310813490006032578790263495042565529710594969722185609497948277910670140174206535208998036166377688284289995920516604924956793172587315806815116854231045587846108456607501836645

f=x_enc*x^e-hint_enc
g=x_enc*(x*2^272+1)^e-more_hint
print(GCD(f, g))

Sau khi chạy ta được một đa thức dạng $ax+b$ như sau:


Vì các hệ số được lấy theo modulo $n$ nên để khôi phục lại flag ta phải tính nghiệm của đa thức là $x=-b/a$, nếu viết theo ngôn ngữ số học thông thường sẽ là $(n-b) \times a^{-1} \mod n$.

Như vậy ta sẽ tìm được flag

from Cryptodome.Util.number import *
n=17455402175437176532762011936605374319510514858668809934283527533793019636085567941340428251796332874658887034973125379656976787899948739462792044779394617697923593713865571947480575715808220681702040571713834962591162896883126625987542697405715758837886980695935599886296833761332668492586517301554181926290501066261415348762218737641025568994218666972555733452415715789836479580743518759606518560790216074668160062318077354838559692467462868744895402199050233183880016075435689438118159209700791215305127872319962224886262950782267716759134051276573034748789032249652527725069033671937172082733885413797270594046659
a=9773221259870845390384818924439275392002320319354194062664469481906538648962533984193856566286726646549621893703410878200111498250592781252476398959962259814643582137359417983373155673348118323881888180481339981050792337421591386568963885268723828737013182590217759110103543677724987984290275930060782497628312542293026286318220951342121933270427041000128915820341861697214112686440657584246180841846516658949855303891393915680861967928721468562700586480922287501013135051379549802628887158314506259429804479176738033029076820721151360559878516632926877734775134865395004109545918323388019950517382238058253501658507
b=5357212906179756866715281890069471101230729984515492393746969161253055889321856843477372600935547086172508827384057895230497160502713414641618616945137818637240155063728755382396358659302086413212825145096220739713877265341187366255211704119424414138878404119457537474934520777352921220692584549517200469087399597743579923527176836836923022328356476427888546933649686694317099836309909270290836116559518044311984050115050973424402775001829379077243360179499178421927360804572434043005576157110890347548214244899458009827525995852187530858283237501761596156164759609769430221390571429877608824356245629296201289690916
d=inverse(a,n)
c=(n-b)*d % n 
print(long_to_bytes(c))

Ta được flag : ```W1{jus7_4dd_l1tt3_b1t_s3cr3t_hehe}```

Sau khi hết giải thì em có tìm hiểu được thêm một cách nữa sử dụng Groebner Basis. Tham khảo tại :
- https://www.youtube.com/watch?v=jxv7XnKIPMQ&t=1017s
- https://mystiz.hk/posts/2021/2021-02-15-dicectf-1/

Về cơ bản kĩ thuật này giúp biến đổi một hệ các đa thức đa biến về dạng đơn giản hơn rồi sau đó lấy gcd của chúng. Định nghĩa hình thức của cơ sở Groebner như sau:

Về cơ sở lý thuyết em tham khảo tại [đây](https://file.notion.so/f/f/2118b33f-6c63-4414-95b2-c6cd3258445d/dd15eb31-6169-41ab-bca6-c27209a219a0/(Graduate_Studies_in_Mathematics)_Joseph_J._Rotman_-_Advanced_Modern_Algebra_Part_1-American_Mathematical_Society_(2015).pdf?table=block&id=f7362dbb-d043-4dab-a756-d0644b8e23b2&spaceId=2118b33f-6c63-4414-95b2-c6cd3258445d&expirationTimestamp=1736157600000&signature=BnHoofZD1uVroJvde4XPG7UdUnGeURsJaPMGlvFjxRg&downloadName=%28Graduate+Studies+in+Mathematics%29+Joseph+J.+Rotman+-+Advanced+Modern+Algebra%2C+Part+1-American+Mathematical+Society+%282015%29.pdf) (trang 639)


Code sage cho bài này.

n = 17455402175437176532762011936605374319510514858668809934283527533793019636085567941340428251796332874658887034973125379656976787899948739462792044779394617697923593713865571947480575715808220681702040571713834962591162896883126625987542697405715758837886980695935599886296833761332668492586517301554181926290501066261415348762218737641025568994218666972555733452415715789836479580743518759606518560790216074668160062318077354838559692467462868744895402199050233183880016075435689438118159209700791215305127872319962224886262950782267716759134051276573034748789032249652527725069033671937172082733885413797270594046659
e = 257
x_enc = 9996223492945930307599847149030142323594733002172616721058190037475290836989969789254053717666020951921459176187704524599282156785134867888383301434607072014358468217885735213022405058511843363872636247404379439558338700149306005415828454372965267435748808512594750475657894932556732283868780381727090987803428282860149481730335955039459503864265070695125410078101017244023029264699216041534759532946007673595164569006924131708811385328137810260255820693022452407318872511604340046032703603689226966698963947140903268751317131092280784353673781583886340493103149941363175123086894375292235376263422464299937964242529
hint_enc = 14789408518282984435806404374838863944620574135335751718371470938725019307943299519996110191146342336694298360945290481279154411743070024294186906891227799217417210874041187513533095475177536407329059640170945862144612697751930832068191380343375683600799846751305650713478329200992580277004206060405550671431501911580994159286609366370084466999243157644437677404006488711305765810155959071167712372903081938159711179919854865680181098099964158600115467907298067836087274873276020158780106022394580520866275356696118835744838635778222876212312712636991385848611744174549177416655001397274793228678792857731056729401479
flag_enc = (pow(x_enc,-1,n)*hint_enc)%n
 
more_hint = 11029946941431959428525282661954512235928562456214126818506773711111719425190566952451999044331493580332064561323097236705681748867775061691143721439117904810714121197594096628261432006374462970213237363365127870527463436083313806638082369213886645623998873849163617775630517410918551847474235496220816340531322685920512036201318038335403616434596578979491681508214839604410062184542042494994435105891585296125095470899377721478810921246711310813490006032578790263495042565529710594969722185609497948277910670140174206535208998036166377688284289995920516604924956793172587315806815116854231045587846108456607501836645 
P.<x,y> = PolynomialRing(Zmod(n))

f1 = x^e - x_enc 
f2 = y^e - flag_enc
f3 = ((x*y)*2^(8*34) +x)^e -  more_hint
I = P.ideal([
   f1,f2,f3
])
for eq in I.groebner_basis():
    print(eq)


Cả 3 đa thức $f1,f2,f3$ đều có nghiệm chung là $x_{enc}$ và $flag_{enc}$. Sau khi có được $y+flag_{enc}$ thì em decrypt lại flag.

from Cryptodome.Util.number import * 
print(long_to_bytes(-17455402175437176532762011936605374319510514858668809934283527533793019636085567941340428251796332874658887034973125379656976787899948739462792044779394617697923593713865571947480575715808220681702040571713834962591162896883126625987542697405715758837886980695935599886296833761332668492586517301554181926290501066261415348762218737641025568994218666972555733452415715789836479580743518759606518560790216074668160062318077354838559692467462868744895402199050233183880016075435689438118159209700791215305127872319962224886262950782267714174483004833663080642567977831782538069781591097917792917559279142465967909791046%n))

## DH

Chall cho ta một file python:

from Crypto.Util.number import isPrime, long_to_bytes, getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
from hashlib import sha256


FLAG = b"W1{fake-flag}"

class DH:   

    def __init__(self):
        self.gen_params()

    def gen_params(self):
        self.r = getPrime(512)

        while True:
            self.q = getPrime(42)
            self.p = (2 * self.q * self.r) + 1
            if isPrime(self.p):
                break

        while True:
            self.h = getPrime(42)
            self.g = pow(self.h, 2 * self.r, self.p)
            if self.g != 1:
                break   

        self.a = randint(2, self.p - 2)
        self.b = randint(2, self.p - 2)

        self.A, self.B = pow(self.g, self.a, self.p), pow(self.g, self.b, self.p)
        self.ss = pow(self.A, self.b, self.p)

    def encrypt(self, flag_part):
        key = sha256(long_to_bytes(self.ss)).digest()[:16]
        cipher = AES.new(key, AES.MODE_ECB)
        ct = cipher.encrypt(pad(flag_part, 16)).hex()
        return f"encrypted = {ct}"

    def get_params(self):
        return f"p = {self.p}\ng = {self.g}\nA = {self.A}\nB = {self.B}"


def main():

    dh = DH()
    print(dh.get_params())
    print(dh.encrypt(FLAG))

if __name__ == "__main__":
    main()

p = 85013941328859365232686230728938372320812319905627686919070637645614632817039920673725615375841158719310596592903101914818137738460649589340349796188816568005092757847
g = 20033344683527080232439150682925185454003164954955126339094967675384779782733210350757021743656898625398860187361281262413493941502725149445995471514781822892886669776
A = 76548721461171533747911417838852759206858825205673491250696441734297318615226024320798706656529038703728631231084155790148283919370554345818139818854112841655270107839
B = 2103083080159597422706551446020625757109756570951674830166998494220734179439318911618156966499109201221652320384817270671579741987575328177442670242481963924501204498
encrypted = "240e7b7678aaaa0dcbe06de7c5598a1ca0be7e2ae584bc7dfd2388cdb1d4fb6a37ceb94556757afc293999cbe5a5a2dbb4071ebf6cfd4332088555f9b2de1922"

Cụ thể đây là DFKE - trao đổi khóa Diffie-Hellman


Như vậy ta có shared-secret được tính bằng cách lấy $\displaystyle ss=A^{b} \equiv B^{a}(\bmod p)$ và ta cần giải DLP để tính được $a,b$.
Để ý $p=2qr+1$ có cấu trúc khá đặc biệt nên ta có thể thử dùng thuật Pohlig Hellman để giải quyết.

Dùng tool để factor $p-1$:


Ta sẽ giải tìm $a$.

p = 85013941328859365232686230728938372320812319905627686919070637645614632817039920673725615375841158719310596592903101914818137738460649589340349796188816568005092757847
g = 20033344683527080232439150682925185454003164954955126339094967675384779782733210350757021743656898625398860187361281262413493941502725149445995471514781822892886669776
a = 76548721461171533747911417838852759206858825205673491250696441734297318615226024320798706656529038703728631231084155790148283919370554345818139818854112841655270107839
order1 = p - 1
factors =[2,3532729477811,12032331071885089636894466252658319251627277386273560255196257546850692960100677515370690305182105378105239739195632026290421584949679657929829280135767593]
from sage.all import *
K = GF(p)
res = []
for i in factors[:-1]:
    g_i = K(pow(g, order1 // i, p))
    a_i = K(pow(a, order1 // i, p))
    order = ZZ(i)
    x = discrete_log(a_i, g_i, ord=order)
    res.append(x)
b = crt(res, factors[:-1])
print(b)
B=2103083080159597422706551446020625757109756570951674830166998494220734179439318911618156966499109201221652320384817270671579741987575328177442670242481963924501204498
ss=pow(B,b,p)
print(ss)

Ở trong thuật ta bỏ qua thừa số nguyên tố cuối cùng vì thừa số này khá lớn, nếu chạy sẽ mất rất nhiều thời gian. Để kiểm tra xem kết quả khi giải CRT với 2 thừa số nguyên tố có đúng hay không thì ta có thể ```print(b)``` ra và check lại phương trình $\displaystyle g^{a} \equiv A(\bmod p)$. Trong trường hợp này thì may mắn khi $\displaystyle g=h^{2r}$ cho nên $\displaystyle g^{q} =h^{2rq} =1$. Điều này chứng tỏ $g$ thuộc vào một nhóm con có cấp là $q$ cho nên ta chỉ cần giải bài DLP với $2$ và $q$ là đủ.

exp = 5657118519872
ss = 66277002472717231027343343852936854583223697325634048850185463896894064552042232620221279686774192339783152904946258245343020845163004549305451198199889253864704673751

Sau khi có ss ta decrypt lại flag:

from Cryptodome.Cipher import AES
from Cryptodome.Util.Padding import unpad
from hashlib import sha256
from binascii import unhexlify

encrypted_hex = "240e7b7678aaaa0dcbe06de7c5598a1ca0be7e2ae584bc7dfd2388cdb1d4fb6a37ceb94556757afc293999cbe5a5a2dbb4071ebf6cfd4332088555f9b2de1922"
encrypted_bytes = unhexlify(encrypted_hex)

ss = 66277002472717231027343343852936854583223697325634048850185463896894064552042232620221279686774192339783152904946258245343020845163004549305451198199889253864704673751

key = sha256(ss.to_bytes((ss.bit_length() + 7) // 8, byteorder='big')).digest()[:16]

cipher = AES.new(key, AES.MODE_ECB)
decrypted_flag = unpad(cipher.decrypt(encrypted_bytes), 16)
print(decrypted_flag.decode())

Flag là : ```W1{so_you_know_about_the_Diffie-Hellman-key_exchange}```

## Smooth
Chall cho ta một file python:

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

FLAG = b'W1{???????????????????????????????}'

p = 29488186972994534670417457155366645471182192199548659526413766939622361834146838276946251349867903845037032661551684336383382344530884181161185642157078150688387732468939373900371006578051481214072847442197503071055434360628659838236532690198978142021175339546919178335298684316724700262657029112644393293166154034921906788597061578283700388736429770020977264432345664045738339856555098074820929368834732846308848389109185416718414806791898185843424928326488893410923833562473301321779917349894586830655477919639150483605307802684111768011681546150738863663345823398017514538698657196101072867671246153807653084849979

e = 0x10001

x = getRandomNBitInteger(1550)

hint = pow(e, x, p)

key = hashlib.sha512(long_to_bytes(x)).digest()[:16]

cipher = AES.new(key, AES.MODE_ECB)
print(hint)
print(cipher.encrypt(FLAG))
# 15565989507023520599989453473844888345738293883767540044682200387116098778726727092639584680030282924680754836996824347666944190568219259972559913371376230295642182212369433729563762217727277805412925981228881460051783217872389120277083233191144941820776264906459152636385581608797345048727329767042394346810437890763454382771288788698625345149261169962034579205221557431869735207318556427897861682927352582426356093597283783347686188442927706115209934983043745580341869373867823516184740079142532925105289504694660421450970265051590438438057830106683050024773068164385422394299956145634093724572089312716467972923242
# b'\x15\xa5(l\xa3\xaar\xcd\xf0cN\ti\x12\xb8\x9fB\x82\xd3N\x86\x05\xa1\xb1\x82\xc4\xe1\x17vf\x0e,'

Ta cần giải bài DLP để tìm lại $x$ thỏa mãn $e^x=hint \bmod p$
Từ đề bài ta được gợi ý rằng $p-1$ là một số nguyên trơn (smooth), tức là một số nguyên mà có thể dễ dàng phân tích về dưới dạng các thừa số nguyên tố nhỏ hơn.

Vậy ý tưởng của bài này tương tự như bài DH nhưng có vấn đề ở chỗ, nếu như ở bài DH ta có thể giải mà bỏ qua thừa số nguyên tố cuối cùng, thì ở bài này nếu như ta bỏ qua thừa số nguyên tố cuối cùng nghiệm sẽ không còn đúng nữa.

Ở bài DH ta có thể xử lí mà bó qua thừa số nguyên tố cuối cùng bởi vì cấu tạo của số $g$ khá đặc biệt. Cụ thể $\displaystyle g=h^{2r}$ cho nên $\displaystyle g^{q} =h^{2rq} =1$ cho nên ta có thể xác định được số $x$ thực chất thỏa mãn $0<a<q$. Còn ở bài này thì không như vậy:

Trước tiên ta sẽ giải bài toán Loga rời rạc cho các nhóm con nhỏ trước.

p = 29488186972994534670417457155366645471182192199548659526413766939622361834146838276946251349867903845037032661551684336383382344530884181161185642157078150688387732468939373900371006578051481214072847442197503071055434360628659838236532690198978142021175339546919178335298684316724700262657029112644393293166154034921906788597061578283700388736429770020977264432345664045738339856555098074820929368834732846308848389109185416718414806791898185843424928326488893410923833562473301321779917349894586830655477919639150483605307802684111768011681546150738863663345823398017514538698657196101072867671246153807653084849979
g = 0x10001
a = 15565989507023520599989453473844888345738293883767540044682200387116098778726727092639584680030282924680754836996824347666944190568219259972559913371376230295642182212369433729563762217727277805412925981228881460051783217872389120277083233191144941820776264906459152636385581608797345048727329767042394346810437890763454382771288788698625345149261169962034579205221557431869735207318556427897861682927352582426356093597283783347686188442927706115209934983043745580341869373867823516184740079142532925105289504694660421450970265051590438438057830106683050024773068164385422394299956145634093724572089312716467972923242
order1 = p - 1
factors=[2, 15739, 16193, 34146337, 34969303, 34996979, 35882111, 36235453, 36253411, 36425761, 36699737, 37482199, 38138383, 38335727, 38523971, 40124191, 41442881, 42039769, 43915397, 44131229, 44386523, 44601737, 44918989, 45234109, 47471797, 47549387, 47614939, 47685917, 48562117, 49424983, 49518451, 49592497, 51053143, 51603091, 51944203, 53274623, 53720993, 53812277, 53963431, 54074849, 54156757, 54161383, 54784601, 54825247, 55148501, 56594249, 58469773, 59463269, 60129947, 60522233, 60733993, 60796577, 61309427, 61975691, 62113789, 62556521, 62747701, 63628133, 64570157, 64974397, 65424053, 66279959, 7460499821685332157113516060069886564400427229472624761209683142140995510658080396491764993046100641019523524398412618076429841989075435122250235698035949]

from sage.all import *
K = GF(p)
res = []
for i in factors[:-1]:
    g_i = K(pow(g, order1 // i, p))
    a_i = K(pow(a, order1 // i, p))
    order = ZZ(i)
    x = discrete_log(a_i, g_i, ord=order)
    res.append(x)
b = crt(res, factors[:-1])
print(b)
# x=1855512073301756587756398232044694453287540787670792602075522813991081601061737651961714765303931127584794086388195063345643498845590200784521163870740676836865034348236672261500637967777776528654389569453659092664362103325055772843213798878968673741544455797271025007597011355845701322512387115527794386532917304746518282690374593080519689235943954434619469423490386939887715663575148853233409899365866194541445855735427925029943387649934084213322940603441421762

Nghiệm $x$ này vẫn chưa thỏa điều kiện ban đầu của bài. Để tìm ra chính xác $x$ ta thực hiện ý tưởng như sau: Ở bước cuối cùng của thuật Pohlig Hellman ta sử dụng CRT để tính nghiệm theo modulo các thừa số nguyên tố. Việc sử dụng CRT như vậy giúp ta sinh ra được một họ nghiệm (vô hạn nghiệm) gồm các số $x$ thỏa mãn hệ phương trình đồng dư.

Cụ thể là định lí như dưới đây:

Họ các nghiệm thỏa mãn sinh ra bởi phương trình đồng dư:

Như vậy, từ số $x$ tìm được ở trên, ta tiếp tục sinh ra thêm các nghiệm khác bằng cách cộng thêm vào $x$ modulo $m$ là tích của các thừa số nguyên tố, không tính thừa số nguyên tố cuối cùng. Bằng cách này ta có thể tìm được nghiệm chính xác của bài DLP mà không cần phải giải bài DLP cho thừa số nguyên tố lớn cuối cùng. Script sage cụ thể như sau:

from sage.all import *
p = 29488186972994534670417457155366645471182192199548659526413766939622361834146838276946251349867903845037032661551684336383382344530884181161185642157078150688387732468939373900371006578051481214072847442197503071055434360628659838236532690198978142021175339546919178335298684316724700262657029112644393293166154034921906788597061578283700388736429770020977264432345664045738339856555098074820929368834732846308848389109185416718414806791898185843424928326488893410923833562473301321779917349894586830655477919639150483605307802684111768011681546150738863663345823398017514538698657196101072867671246153807653084849979
e = 0x10001
hint = 15565989507023520599989453473844888345738293883767540044682200387116098778726727092639584680030282924680754836996824347666944190568219259972559913371376230295642182212369433729563762217727277805412925981228881460051783217872389120277083233191144941820776264906459152636385581608797345048727329767042394346810437890763454382771288788698625345149261169962034579205221557431869735207318556427897861682927352582426356093597283783347686188442927706115209934983043745580341869373867823516184740079142532925105289504694660421450970265051590438438057830106683050024773068164385422394299956145634093724572089312716467972923242
large_factor = 7460499821685332157113516060069886564400427229472624761209683142140995510658080396491764993046100641019523524398412618076429841989075435122250235698035949
FF = GF(p)
g = FF(e)
h = FF(hint)
x = 1855512073301756587756398232044694453287540787670792602075522813991081601061737651961714765303931127584794086388195063345643498845590200784521163870740676836865034348236672261500637967777776528654389569453659092664362103325055772843213798878968673741544455797271025007597011355845701322512387115527794386532917304746518282690374593080519689235943954434619469423490386939887715663575148853233409899365866194541445855735427925029943387649934084213322940603441421762
delta = p // large_factor

while True: 
    x+=delta
    if g^x == h:
        print(x)
        break
#x=39345789584158032512642763898941391995857388315308510231906758103602069400355492510675246179821522070796108546674823983368739227343617649698149723920009409085649862454006806441408416329515128156320837963767792617909364017501794254201478451853481782818746299820273100327214670628567515025254811562372652817330594388363763412836061592598885910564000993838864882287647394868600139277652449978683529171406785240992429298940751772312099536110532315909803441681024886529350    

Sau đó ta thay vào và giải ra flag:

from Cryptodome.Util.number import *
from Cryptodome.Cipher import AES
import hashlib

x=39345789584158032512642763898941391995857388315308510231906758103602069400355492510675246179821522070796108546674823983368739227343617649698149723920009409085649862454006806441408416329515128156320837963767792617909364017501794254201478451853481782818746299820273100327214670628567515025254811562372652817330594388363763412836061592598885910564000993838864882287647394868600139277652449978683529171406785240992429298940751772312099536110532315909803441681024886529350
ciphertext = b'\x15\xa5(l\xa3\xaar\xcd\xf0cN\ti\x12\xb8\x9fB\x82\xd3N\x86\x05\xa1\xb1\x82\xc4\xe1\x17vf\x0e,'
key=hashlib.sha512(long_to_bytes(x)).digest()[:16]
cipher=AES.new(key,AES.MODE_ECB)
flag=cipher.decrypt(ciphertext)
print(flag.decode())

Flag là : ```W1{1t_1s_sm00th_bu7_n07_3n0ugh!}```