姜姜酱 |

Crypto CTF 2022刷题记录（二）—— medium easy部分

2023-02-20

SOTS

He who abides far away from his home, is ever longing for the day he shall return.

└─# nc 05.cr.yp.toc.tf 37331
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hey math experts, in this challenge we will deal with the numbers   |
|  those are the sum of two perfect square, now try hard to find them! |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generating the `n', please wait...
| Options: 
|       [G]et the n 
|       [S]olve the challenge! 
|       [Q]uit
G
| n = 3987875173593025625528614308277076676618568147483435653130190320646040337
| Options: 
|       [G]et the n 
|       [S]olve the challenge! 
|       [Q]uit
S
| Send your pair x, y here:

将$n$分解成3个素数$n=p_1p_2p_3$，发现$p_1,p_2,p_3$都是$4k+1$型素数，而根据论文[1]中Theorem 3.8可知，这样的素数可以表示为两个整数的平方和：$p=x^2+y^2$，并证明了其存在性。而这里需要对这样的$x,y$求解，我们将这一求解过程看作是对$4k+1$型高斯素数的唯一分解过程。一个高斯整数$\mathbb{Z}[i]=\left\{a+bi|a,b\in \mathbb{Z},i^2=-1\right\}$，它的范数是它与其共轭的乘积：

$N(a+bi)=(a+bi)(a-bi)=a^{2}+b^{2}$

分解高斯整数参考链接，主要分为两步：

找到一个$z\in \mathbb{Z}$，满足$z^2\equiv -1(\bmod p)$，目的利用$z$构造高斯整数，使得范数$p^2=z^2+1$.
在环上进行分解计算$x$和$y$.

对于第一步，具体方法是首先找到一个模$p$的二次非剩余$a$，$a^{(p-1)/2}\equiv -1(\bmod p)$，这样令$z\equiv a^{(p-1)/4}(\bmod p)$就可以找到符合条件的$z$。而要想找到$a$，二次非剩余和二次剩余各占一半，最坏情况下$(p-1)/2$次后找到$a$。

对于第二步，计算$gcd(p,z+i)=x+yi$，而$p$作为素数，$x+yi$整除$p$，与共轭$x-yi$组成了$p$唯一分解。

然后把$p_1,p_2,p_3$作为其范数，分解得到$(x_i,y_i),i=1,2,3$。由[1]中Lemma 3.10再次组合：

$\begin{aligned} n&=p_1p_2p_3\\ &=\left(x_1^2+y_1^2\right)\left(x_2^2+y_2^2\right)\left(x_3^2+y_3^2\right)\\ &=\left(\left(x_1x_2-y_1y_2\right)^2+\left(x_1y_2+y_1x_2\right)^2\right)\left(x_3^2+y_3^2\right)\\ &=\left(x_1x_2x_3-y_1y_2x_3-x_1y_2y_3-y_1x_2y_3\right)^2+\left(x_1x_2y_3-y_1y_2y_3+x_1y_2x_3+y_1x_2x_3\right)^2 \end{aligned}$

Lemma 3.10 Let $a, b$ be positive integers such that both $a$ and $b$ can be written as a sum of squares. Then the product $ab$ can be written as a sum of squares in two ways.

Proof. Let $a=x^2+y^2$ and $b=z^2+t^2$ where $x, y, z, t \in \mathbb{Z}$. Then we have the following:
$\begin{aligned} a b & =\left(x^2+y^2\right)\left(z^2+t^2\right) \\ & =x^2 z^2+x^2 t^2+y^2 z^2+y^2 t^2 \\ & =\left(x^2 z^2+2 x y z t+y^2 t^2\right)+\left(x^2 t^2-2 x y z t+y^2 z^2\right) \\ a b & =(x z+y t)^2+(x t-y z)^2 \\ a b & =(x z-y t)^2+(x t+y z)^2 \end{aligned}$

mods = lambda a, p: (a % p) - p if (a % p) > (p // 2) else a % p
quos = lambda a, p: (a - mods(a, p)) // p

def grem(a, b):
    (x1, y1) = a
    (x2, y2) = b
    norm_b = x2*x2 + y2*y2
    u = quos(x1*x2 + y1*y2, norm_b)
    v = quos(x2*y1 - x1*y2, norm_b)
    return (x1 - x2*u + y2*v, y1 - x2*v - y2*u)

def sq2(p):
    k = (p - 1) // 4
    for i in range(2, (p - 1) // 2):
        z = pow(i, k, p)
        if mods(z**2, p) == -1:
            break
    a = (p, 0)
    b = (z, 1)
    while b != (0, 0):
        a, b = b, grem(a, b)
    return a

n = 1981722672302581189082901915288506374526880879886288891112359421465804017
p1 = 1551467770836394791909197
p2 = 1195018123585596996022289
p3 = 1068871821419604191282149
x1, y1 = sq2(p1)
x2, y2 = sq2(p2)
x3, y3 = sq2(p3)
x = x1*x2*x3 - y1*y2*x3 - x1*y2*y3 - y1*x2*y3
y = x1*x2*y3 - y1*y2*y3 + x1*y2*x3 + y1*x2*x3
assert x**2 + y**2 == n
print(f'{x}, {y}')
# | Congratz! the flag is CCTF{3Xpr3sS_4z_Th3_sUm_oF_7w0_Squ4rE5!}

注：sage的factor()可以直接分解。

polyRSA

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def keygen(nbit = 64):
	while True:
		k = getRandomNBitInteger(nbit)
		p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
		q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
		if isPrime(p) and isPrime(q):
			return p, q

def encrypt(msg, n, e = 31337):
	m = bytes_to_long(msg)
	return pow(m, e, n)

p, q = keygen()
n = p * q
enc = encrypt(flag, n)
print(f'n = {n}')
print(f'enc = {enc}')

# n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
# enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532

多项式求根再求值解RSA。

from Crypto.Util.number import *

k = PolynomialRing(RationalField(), 'k').gen()
fp = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
fq = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011

n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
e = 31337
f = fp * fq - n
k = f.roots()[0][0]
p = fp(k)
q = fq(k)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(enc, d, n)
print(long_to_bytes(m))
# b'CCTF{F4C70r!N9_tRIcK5_aR3_fUN_iN_RSA?!!!}'

Infinity castle

#!/usr/bin/env python3

from Crypto.Util.number import *
from os import urandom

class TaylorSeries():

	def __init__(self, order):
		self.order = order
		
	def coefficient(self, n):
		i = 0
		coef = 1
		while i < n:
			i += 1
			coef *= (coef * (1/2-i+1)) / i
		return coef

	def find(self, center):
		sum = 0
		center -= 1
		i = 0
		while i < self.order:
			sum += (center**(1/2-i) * self.coefficient(i))
			i += 1
		return sum

def xor(cip, key):
	repeation = 1 + (len(cip) // len(key))
	key = key * repeation
	key = key[:len(cip)]
	
	msg = bytes([c ^ k for c, k in zip(cip, key)])
	return msg

# If you run these 3 functions (diamond, triage, summarize) with big numbers, they will never end
# You need to optimize them first

def diamond(num):
	output = 0
	for i in range(num):
		output += i*2 + 1
	return output

def triage(num):
	output = 0
	index = 0
	for i in range(num):
		output += (i+index)*6 + 1
		index += i
	return output

def summarize(b):
	order = getRandomRange(1000, 2000)
	t = TaylorSeries(order)
	output = 0
	
	i = 2
	while i < b:
		b1 = t.find(i)
		b2 = t.find(i+1)
		output += (b1+b2) / 2
		i += 1
	return output

KEY_SIZE = 2048
p, q = [getPrime(KEY_SIZE) for _ in '01']

e, n = 0x10001, p*q

f = open ('./message.txt', 'rb')
message = f.read()
f.close()
msg_length = len(message)
padded_msg = message + urandom(len(long_to_bytes(n)) - msg_length)
padded_msg_length = len(padded_msg)

xor_key = long_to_bytes(int(summarize(n)))[:padded_msg_length]
assert(len(xor_key) == 512)

enc0 = xor(padded_msg, xor_key)
assert(bytes_to_long(enc0) < n)

c0 =  abs(diamond(p) - diamond(q))
c1 =  triage(p)
c1 += 3*n*(p+q)
c1 += triage(q)

m = bytes_to_long(enc0)
enc1 = pow(m, e, n)

print(f"c0 = {c0}")
print(f"c1 = {c1}")
print(f"enc = {enc1}")

diamond函数化简：

$\begin{aligned} \sum_{i=0}^{n-1} (2i+1)&=2\sum_{i=0}^{n-1} i+n \\ &= (n-1)n+n \\ &=n^2 \end{aligned}$

triage函数化简：

$\begin{aligned} \sum_{i=0}^{n-1}\left(6\left(i+\sum_{j=0}^{i-1}j\right)+1\right)&=3(n-1)n+3\sum_{i=0}^{n-1}(i-1)i+n\\ &=3n^2-3n+3\sum_{i=0}^{n-1}i^2-3\frac{n(n-1)}{2}+n \\ &=3n^2-2n+\frac{(n-1)n(2n-1)}{2}-3\frac{n(n-1)}{2} \\ &=3n^2-2n+\frac{2n^3-6n^2+4n}{2}\\ &=n^3 \end{aligned}$

已知$c_0,c_1$，化简联立即可求$p$和$q$的值，解密enc得到enc0：

$\begin{aligned} c_0&=p^2-q^2\\ c_1&=p^3+q^3+3pq(p+q)=(p+q)^3 \end{aligned}$

find化简：

$\begin{aligned} find(x)&=\sum_{i=0}^{n-1}\left(\prod_{j=1}^{i}\frac{1/2-j+1}{j}\cdot (x-1)^{1/2-i}\right)\\ &=\sum_{i=0}^{n-1}\left(\frac{\prod_{j=1}^{i} \left(1/2-j+1\right)}{j!}\cdot (x-1)^{1/2-i}\right) \end{aligned}$

前一部分是coefficient()，后一部分在find()内循环。写出$find(x)$的前几项：

$\begin{aligned} i&=0,find(x)=1\cdot(x-1)^{\frac{1}{2}}\\ i&=1,find(x)=1\cdot(x-1)^{\frac{1}{2}}+\frac{1}{2}\cdot(x-1)^{-\frac{1}{2}}\\ i&=2,find(x)=1\cdot(x-1)^{\frac{1}{2}}+\frac{1}{2}\cdot(x-1)^{-\frac{1}{2}}+\frac{1/2\cdot (-1/2)}{2!}\cdot(x-1)^{-\frac{3}{2}}\\ i&=3,find(x)=1\cdot(x-1)^{\frac{1}{2}}+\frac{1}{2}\cdot(x-1)^{-\frac{1}{2}}+\frac{1/2\cdot (-1/2)}{2!}\cdot(x-1)^{-\frac{3}{2}}+\frac{1/2\cdot (-1/2)\cdot (-2/3)}{3!}\cdot(x-1)^{-\frac{5}{2}}\\ \end{aligned}$

可以看到，实际上$find(x)$是函数$f(x)=\sqrt{x}$在$x=x-1$处的泰勒级数。

一个函数$f(x)$在$x=a$处的泰勒展开公式如下。$R_n(x)$是泰勒公式中的余项，表示用$n$项泰勒级数来近似原函数时产生的误差。一般来说，当$n$越大时，$R_n(x)$越小，说明泰勒级数越接近原函数。
$f(x) = f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n + R_n(x)$

summarize化简：

$\begin{aligned} \sum_{i=2}^{n-1}\frac{\sqrt{i}+\sqrt{i+1}}{2}&=\frac{\sqrt{2}}{2}+\sqrt{3}+\cdots+\sqrt{n-1}+\frac{\sqrt{n}}{2}\\ &=\sum_{i=2}^{n}\sqrt{i}-\frac{\sqrt{2}}{2}-\frac{\sqrt{n}}{2} \end{aligned}$

对平方根求近似和的方法有很多，参考链接。论文[2]中Theorem 0.1给出了前$n$个自然数的$r$次根和的公式，代入：

$\sum_{i=2}^{n}\sqrt{i}=\frac{2}{3}(n+1)^{\frac{3}{2}}-\frac{1}{2}(n+1)^\frac{1}{2}-\phi-1$

Theorem 0.1. Let $r$ be a real number with $r \geq 1$ and $n$ be a positive integer. Then
$\sum_{x=1}^{x=n} x^{\frac{1}{r}}=\frac{r}{r+1}(n+1)^{\frac{1+r}{r}}-\frac{1}{2}(n+1)^{\frac{1}{r}}-\phi_n(r)$
where $\phi_n$ is a function of $r$ with $n$ as a parameter. This function is bounded between 0 and $\frac{1}{2}$.

import gmpy2
from Crypto.Util.number import *

def xor(cip, key):
    repeation = 1 + (len(cip) // len(key))
    key = key * repeation
    key = key[:len(cip)]
    
    msg = bytes([c ^^ k for c, k in zip(cip, key)])
    return msg

c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045

eq0 = gmpy2.iroot(c1, 3)[0]
eq1 = c0 // eq0
p = (eq0 + eq1) // 2
q = eq0 - p
assert abs(p**2 - q**2) == c0
assert (p + q)**3 == c1
e, n = 0x10001, p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
enc0 = long_to_bytes(pow(enc, d, n))

ring = RealField(3072)
key = int(2/3*(ring(n)+1)^(3/2)-1/2*(ring(n)+1)^(1/2)-1)
key = long_to_bytes(int(key))[:512]
print(xor(enc0, key))

# b"Never heard of using taylor series and integral beside RSA?!\nBut there are always ways to make things complicated\n\nCCTF{Mix1ng_c4lcUluS_w17h_Numb3r_The0Rry_S33ms_s7r0ng_cRyp70_Sch3m4!!}\n\nWe compute integrals ...'

Keydream

#!/usr/bin/env python3

from Crypto.Util.number import *
import string
from flag import flag

def randstr(l):
	rstr = [(string.printable[:62] + '_')[getRandomRange(0, 62)] for _ in range(l)]
	return ''.join(rstr)


def encrypt(msg, l):
	while True:
		rstr = 'CCTF{it_is_fake_flag_' + randstr(l) + '_90OD_luCk___!!}'
		p = bytes_to_long(rstr.encode('utf-8'))
		q = bytes_to_long(rstr[::-1].encode('utf-8'))
		if isPrime(p) and isPrime(q):
			n = p * q
			e, m = 65537, bytes_to_long(msg.encode('utf-8'))
			c = pow(m, e, n)
			return n, c

n, c = encrypt(flag, 27)

print(f'n = {n}')
print(f'c = {c}')

'''
n = 23087202318856030774680571525957068827041569782431397956837104908189620961469336659300387982516148407611623358654041246574100274275974799587138270853364165853708786079644741407579091918180874935364024818882648063256767259283714592098555858095373381673229188828791636142379379969143042636324982275996627729079
c = 3621516728616736303019716820373078604485184090642291670706733720518953475684497936351864366709813094154736213978864841551795776449242009307288704109630747654430068522939150168228783644831299534766861590666590062361030323441362406214182358585821009335369275098938212859113101297279381840308568293108965668609
'''

RSA关于$p,q$中位未知的Coppersmith，注意rstr是以字符的形式存在，计算比特位时乘8。

from Crypto.Util.number import *
n = 23087202318856030774680571525957068827041569782431397956837104908189620961469336659300387982516148407611623358654041246574100274275974799587138270853364165853708786079644741407579091918180874935364024818882648063256767259283714592098555858095373381673229188828791636142379379969143042636324982275996627729079
c = 3621516728616736303019716820373078604485184090642291670706733720518953475684497936351864366709813094154736213978864841551795776449242009307288704109630747654430068522939150168228783644831299534766861590666590062361030323441362406214182358585821009335369275098938212859113101297279381840308568293108965668609
e = 65537

PR.<x> = PolynomialRing(Zmod(n))
kbits = 27 * 8
leak = bytes_to_long(b'CCTF{it_is_fake_flag_' + b'\x00' * 27 + b'_90OD_luCk___!!}')
f = x * 2^127 + leak
x0 = f.monic().small_roots(2^kbits, beta=0.4)[0]
# p = int(x0) * 2^127 + leak
p = int(f(x0))
q = n // p
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
# b'Congratz, the flag is: CCTF{h0M3_m4dE_k3Y_Dr1vEn_CrYp7O_5ySTeM!}'

Jeksign

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import gensol, nbit_gensol
from flag import flag

m = bytes_to_long(flag.encode('utf-8'))
print(m)

a = 1337
b = 31337

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.readline().strip()

def main():
	border = "|"
	pr(border*72)
	pr(border, "Welcome crypto guys! Here we are looking for the solution of special", border)
	pr(border, "Diophantine equation: 1337(z^4 - x^2) = 31337(y^2 - z^4) in natural ", border)
	pr(border, "numbers, in each stage solve the equation in mentioned interval :)  ", border)
	pr(border*72)

	STEP, level = 0, 19

	while True:
		p, q = nbit_gensol(1337, 31337, STEP + 30)
		x, y, z = gensol(a, b, p, q)
		pr(border, f"Send a solution like `x, y, z' such that the `z' is {STEP + 30}-bit: ")
		ans = sc()
		try:
			X, Y, Z = [int(_) for _ in ans.split(',')]
			NBIT = Z.bit_length()'
		except:
			die(border, 'Your input is not valid, Bye!')
		if 1337*(Z**4 - X**2) == 31337*(Y**2 - Z**4) and NBIT == STEP + 30:
			if STEP == level - 1:
				die(border, f'Congrats, you got the flag: {flag}')
			else:
				pr('| good job, try to solve the next challenge :P')
				STEP += 1
		else:
			die(border, 'your answer is not correct, Bye!!')

if __name__ == '__main__':
	main()

求满足Diophantine等式$1337(z^4 - x^2) = 31337(y^2 - z^4)$的$x,y,z$，其中$z$的长度按挑战依次从30bit到48bit。化简一下：

$(1337+31337)z^4=ax^2+by^2$

当$x=y=z^2$时恒成立。

Diophantine Equation：形如$x^2+y^2=z^4$，等式有无穷多个整数解，构造解的方法如下：

令$u=z^2$，$x^2+y^2=u^2$。对于任意$m,n\in Z$，有：
$(m^2+n^2)^2=(m^2-n^2)^2+4m^2n^2$
成立。令$u=m^2+n^2,x=m^2-n^2,y=2mn$，这样转化成找$u=z^2=m^2+n^2$的一组解，同理。

from pwn import *

context.log_level = 'DEBUG'
conn = remote('02.cr.yp.toc.tf', 17113)

for i in range(30, 49):
    z = 1 << (i - 1)
    x = y = z ** 2
    conn.recvuntil(b'Send a solution like')
    conn.sendline(f'{x},{y},{z}')

conn.interactive()
# b'| Congrats, you got the flag: CCTF{4_diOpH4nT1nE_3Qua7i0n__8Y__Jekuthiel_Ginsbur!!}\n'

Volgo

模拟M-209密码机，已经获得加密oracle，要求对固定密文解密。M-209的参考文档TM 11-380，密码分析及实现参考链接，但这道题目不用这么复杂。M-209密码机加解密和维吉尼亚相似，对每个字符：

加密：$c_i\equiv k_i - m_i(\bmod 26)$
解密：$m_i\equiv k_i - c_i(\bmod 26)$

尝试加密：

A
{"cipher": "GGMCT NJOAA OXXXX GGMCT NJOAA"}
AA
{"cipher": "GGMCT NJOAA OOXXX GGMCT NJOAA"}
AAA
{"cipher": "GGMCT NJOAA OOYXX GGMCT NJOAA"}
B
{"cipher": "GGMCT NJOAA NXXXX GGMCT NJOAA"}
BB
{"cipher": "GGMCT NJOAA NNXXX GGMCT NJOAA"}

去掉头尾两组，只存在中间一组变化。如果已知一对明密文对$m_0,c_0$，以及待解密密文$c_1$，能恢复出密钥从而解密：

$m_1 \equiv (c_0+m_0)-c_1(\bmod 26)$

其中隐含了一个前提是$m_0$足够长，最好是和$c_1$等长，这样恢复出的密钥和$c_1$等长。因此加密155个’A’，得到的Oracle返回作为$c_0$。

c0 = 'OOYXL SXVKW JGYMO CMWZS ROXLN RVPZH DAVGL RRXMO MPAWR YFVHZ OYPMT LZWAZ ORYSV GMLJS YINRM NYPYS SWYOP MHNRV JZWAO YHZOQ MUYOS KJYLL HPZSY DRWUO ZRLPF FXXLF SYYRO PPYSY NEUKH VTPGN RVUOR GGMCT'.replace(' ', '')
key = [chr(ord('A') + (ord(i) - ord('A')) % 26) for i in c0]
c1 = 'QAEYB FJZLP VKZTA DHIIG RVYGC RPQQN LHWRR YSDXM YDSJL ZUROG KHXNX DGPSM PPEBK INKSS WEVSH ZNEKW OTZNR NFLYQ KLIRC JVWLI PSNBF OEFHC NDUVO CABZC LCTEN NMDSI XVDEL DRADR YIPBQ IKOLM DJAQA'.replace(' ', '')
m1 = [chr(ord('A') + (ord(key[i % len(key)]) - ord(c1[i])) % 26) for i in range(len(c1))]
print(''.join(m1).replace('Z', ' '))

# YOU KNOW HOW TO FORMAT FLAG JUST PUT UPCOMING LETTERS WITHIN CURLY BRACES FOLLOWED BY CCTF OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR

参考文献

[1] Bhaskar J. Sum of two squares[J]. University of Chicago (REU 2008), 2008.

[2] Shekatkar S. The sum of the r’th roots of first n natural numbers and new formula for factorial[J]. arXiv preprint arXiv:1204.0877, 2012.

本文作者: 姜姜酱
本文链接: https://qsang.xin/2023/02/20/CCTF2022-2/
版权声明: 本网站所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明出处!