CTF - wysi-prime - cryptography - osugaming.lol

Alexander Myasnikov

2024-04-12 2024-11-18 394 слов 2 минут

CTF задача crypto/wysi-prime на платформе osugaming.lol

Содержание

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

Ссылка на задачу
crypto/wysi-prime

Файлы
wysi-prime.zip

2 Решение

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

Смотрим что содержит файл server.py

script.py

from Crypto.Util.number import isPrime, bytes_to_long
import random
import os

def getWYSIprime():
    while True:
        digits = [random.choice("727") for _ in range(272)]
        prime = int("".join(digits))
        if isPrime(prime):
            return prime

# RSA encryption using the WYSI primes
p = getWYSIprime()
q = getWYSIprime()
n = p * q
e = 65537
flag = bytes_to_long(os.getenv("FLAG", b"osu{fake_flag_for_testing}"))
ciphertext = pow(flag, e, n)
print(f"{n = }")
print(f"{e = }")
print(f"{ciphertext = }")

Содержимое файла output.txt

output.txt

n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
e = 65537
ciphertext = 2087465275374927411696643073934443161977332564784688452208874207586196343901447373283939960111955963073429256266959192725814591103495590654238320816453299972810032321690243148092328690893438620034168359613530005646388116690482999620292746246472545500537029353066218068261278475470490922381998208396008297649151265515949490058859271855915806534872788601506545082508028917211992107642670108678400276555889198472686479168292281830557272701569298806067439923555717602352224216701010790924698838402522493324695403237985441044135894549709670322380450

Нужно найти два простых числа p, q, состоящие из цифр 2 и 7

2.2 Скрипт solve.py

Очевидно, что если p*q == n, то (p*q) % k == n % k для любых k
Используем алгоритм поиска в ширину для нахождения чисел p и q
Начнем с чисел p=0 и q=0 и будем увеличивать числа, прибавляя цифру 2 или 7 внaчало, пока не найдем числа, произведение которых равно n

Найдя p и q, вычислим секретную экспоненту и рашифруем сообщение

Напишем код

solve.py

#!/usr/bin/python3

import binascii
from typing import List, Tuple

n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
e = 65537
ciphertext = 2087465275374927411696643073934443161977332564784688452208874207586196343901447373283939960111955963073429256266959192725814591103495590654238320816453299972810032321690243148092328690893438620034168359613530005646388116690482999620292746246472545500537029353066218068261278475470490922381998208396008297649151265515949490058859271855915806534872788601506545082508028917211992107642670108678400276555889198472686479168292281830557272701569298806067439923555717602352224216701010790924698838402522493324695403237985441044135894549709670322380450


def find_pq(n: int, digits: List[int]) -> List[Tuple[int, int]]:
    ret = []

    nums = [(0, 0, 0)]

    while len(nums) != 0:
        nums_next = []
        for p, q, i in nums:
            if p * q == n:
                ret.append((p, q))
                continue

            if p * q > n:
                continue

            if (n - p * q) % (10**i) != 0:
                continue

            for pd in digits:
                for qd in digits:
                    nums_next.append(((pd * 10**i) + p, (qd * 10**i) + q, i + 1))

        nums = nums_next

    return ret


numbers = find_pq(n, [2, 7])
assert len(numbers) > 0

(p, q) = numbers[0]

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

d = pow(e, -1, phi)

msg = pow(ciphertext, d, n)
msg = hex(msg)[2:]
msg = binascii.unhexlify(msg).decode("utf-8")

print(f"n = {n}")
print(f"p = {p}")
print(f"q = {q}")
print(f"phi = {phi}")
print(f"e = {e}")
print(f"d = {d}")
print(f"msg = {msg}")

Запустим скрипт

output

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

n = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591415828107248775449619403563269856991145789325659736854030396401772371148983463743700921913930643887223704115714270634525795771407138067936125866995910432010323584269926871467482064993332990516534083898654487467161183876470821163254662352951613205371404232685831299594035879
p = 77777772777772222722727222227777272777772777772277727772722777777777227277727272772727277277272772727227272772772222277777772727727772722772777272727777272722772777277777277777277777727777277277777277777272772772777777727772727277727777772772777772272772272222227777777227
q = 27777727727777722777277277777272772727772722777777277777277772227772772772227272727777772772772727227772777277727777777222777777277727772272272777772722727722777727277727727777777772772777772777277772222727227777777222727777772772272727777222777777277777727272772272272277
phi = 2160489795493918825870689458820648828073650907916827108594219132976202835249425984494778310568338106260399032800745421512005980632641226298431130513637640125399673697368934008374907832728004469350033174207285393191694692228748281256956917290437627249889472471749973975591310272606743225504119399063264806945640243825109681848480395851766821148933509198200416863880598387268704065663770634470795220902132567441080816945409932009878033765371366461927009442832435466479028848654487466610628876015270663204661847401617649821853682686336299543986376
e = 65537
d = 1821929437227251960715250840298469548211643266060992779814100566431112228141813416620731997042591850690350082332099382191800578781820691423705590583902397986030238891503866149516395794610351755612375962264278832194415224306975163041155956908168154557267520257201364293589955976565251351815557117781245038458652354478879667771182172475694598538811789567068105632178601874806284504890971690118519912013033257621896234342767760385582637168481610544445428244762808961745220064674726624916758870420311636836169588482005625108021231991481884536940889
msg = osu{h4v3_y0u_3v3r_n0t1c3d_th4t_727_1s_pr1m3?}