چالش دوم شترگاوپلنگ - جری

به ما یک آدرس و یک پرونده‌ی پایتون داده است. پرونده‌ی پایتون همان چیزی است که درون سرور اجرا می‌شود و بنابراین، بایستی آن را بررسی کنیم.

چالش PoW

در ابتدای حل سوال با چالش PoW مواجه می‌شویم. برای حل این چالش، می‌توانیم از این متد موجود در pwntools استفاده کنیم و به راحتی bruteforce با parse کردن پیام نمایش داده شده، قابل انجام است.

اصل! سوال

اکنون به بررسی تابع main و newjary می‌پردازیم. تابع main بدین صورت است که با یک مشخص، یک حلقه را آغاز می‌کند و در هر بار از اجرای حلقه، یک عدد تصادفی با نام انتخاب می‌کند و از ما عدد را می‌پرسد. عدد بایستی به شکلی انتخاب شود که دو رابطه‌ی و برقرار باشد. در پایان حلقه، c یک واحد افزایش می‌یابد و حلقه به دور بعد می‌رود. پس بایستی تابع newjary را بررسی کنیم.

تابع newjary

این تابع ورودی را می‌گیرد و دنبال نزدیکترین عدد مرکب با فقط دو عامل اول در حوالی عدد می‌گردد و فاصله‌ی آن عدد تا را به وسیله‌ی متغیر برمی‌گرداند.

خب، چطور حل می‌شود؟

برای حل کاملا اتوماتیک سوال، نیاز به استفاده از مثلا pwntools داریم. اما قصد نداریم پیچیدگی‌های آن را وارد این توضیحات کنیم. بنابراین، فرض می‌کنیم که می‌خواهیم یک برنامه بنویسیم که به طور دستی، خودمان به آن ورودی می‌دهیم و خروجی می‌گیریم. خروجی آن را به عنوان پاسخ هر مرحله، برای nc می‌فرستیم. این اسکریپت را در ادامه توضیح می‌دهیم. اسکریپت مورد نظر، این است:

from Crypto.Util.number import getPrime
import math, sys, primefac

def newjary(n):
	c = (n % 2) ^ 1
	while True:
		FU = list(primefac.primefac(n + c))
		FD = list(primefac.primefac(n - c))
		if len(FU) == 2:
			return c
		elif len(FD) == 2:
			return c
		else:
			c += 2
			
def sc():
    return sys.stdin.readline().strip()

for i in range(4,40):
	print('-'*80)
	print('Step: ' + str(i))
	r = int(sc())

	Nb = math.ceil((math.log(10**i) / math.log(2)) / 2) + 1
	n1 = getPrime(Nb)
	n2 = getPrime(Nb)
	n = n1 * n2 - r
	while r != newjary(n) or n >= 10**(i+1):
		n1 = getPrime(Nb)
		n2 = getPrime(Nb)
		n = n1 * n2 - r
	print(n)

ما به دنبال اعدادی با دو عامل اول می‌گردیم. یک راه ساده‌ی آن، این است که خودمان آن‌ها را بسازیم! اگر عددی مرکب بین ۱۰۰۰۰ تا ۱۰۰۰۰۰ می‌خواهیم، کافی است که دو عدد اول به صورت تصادفی بین ۱۰۰ تا ۳۱۶ (یعنی جذر این دو عدد) پیدا کنیم، آن دو عدد اول را در یک دیگر ضرب کنیم. اکنون یکعدد مرکب با شرط خواسته شده داریم و باید فاصله‌ی خواسته شده را از حاصل‌ضرب کم کنیم. ممکن است حاصل‌ضرب نزدیکترین عدد به نتیجه نباشد، بنابراین خودمان با فراخوانی تابع newjary از این شرط اطمینان می‌یابیم و این قدر این تولید اعداد اول را ادامه می‌دهیم، تا زمانی که به شرط مورد نظر سوال برسیم. این کار به سرعت انجام می‌شود، زیرا تعداد اعداد اول در این بازه‌ها خیلی زیاد است و می‌توان با آزمون دستی هم متوجه شد که سرعت بسیار خوبی برای این کار وجود دارد.
برای تولید اعداد اول از بسته‌ی Crypto.Util درون pycryptodome کمک می‌گیریم. مستندات آن در اینجا قابل مشاهده است.
لازم است که برای تولید اعداد اول با استفاده از getPrime موجود در این بسته، تعداد بیت مورد نظر را به عنوان ورودی بدهیم. به همین دلیل، از در مبنای ۲ لگاریتم می‌گیریم و حاصل را تقسیم بر ۲ می‌کنیم (این کار معادل با گرفتن لگاریتم از جذر است) تا تعداد بیت‌های مورد نیاز برای هر دو عدد اول مشخص شود.
به همین ترتیب، پرچم به دست می‌آید:

parcham{dO_Y0u_l0v3_PPC_1N_CTFs!!!? }