首页 比赛

# Klamkin

# 题目

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hello, now we are finding the integer solution of two divisibility  |
|  relation. In each stage send the requested solution. Have fun :)    |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| We know (ax + by) % q = 0 for any (a, b) such that (ar + bs) % q = 0
| and (q, r, s) are given!
| Options: 
|	[G]et the parameters 
|	[S]end solution 
|	[Q]uit
S
| please send requested solution like x, y such that y is 12-bit:

先求出 10 个 a，b

然后看他要求几位的 x 或 y

在 check 一下

# exp

import random
from Crypto.Util.number import *
q = 187664899777679218903377367769149423927
r = 62883771665086813542392383956133061422
s = 42242585173255963334352283606980757549
ass=[]
bs=[]
for i in range(10):
    a = random.randint(0, q - 1)
    b = (- a * r) * inverse(s, q) % q
    ass.append(a)
    bs.append(b)
while True:
    y = getPrime(17)
    x = (- bs[0] * y) * inverse(ass[0], q) % q
    #x=getPrime(12)
    #y=(-ass[0]*a)*inverse(bs[0],q)%q
    flag=1
    for i in range(1,10):
        if(ass[i]*x+bs[i]*y)%q!=0:
            flag=0
            break
    if(flag==1):
        print(x,y)
        break
#CCTF{f1nDin9_In7Eg3R_50Lut1Ons_iZ_in73rEStIn9!}
# Baphomet
# 题目
#!/usr/bin/env python3
from base64 import b64encode
from flag import flag
def encrypt(msg):
	ba = b64encode(msg.encode('utf-8'))
	baph, key = '', ''
	for b in ba.decode('utf-8'):
		if b.islower():
			baph += b.upper()
			key += '0'
		else:
			baph += b.lower()
			key += '1'
	baph = baph.encode('utf-8')
	key = int(key, 2).to_bytes(len(key) // 8, 'big')
	enc = b''
	for i in range(len(baph)):
		enc += (baph[i] ^ key[i % len(key)]).to_bytes(1, 'big')
	return enc
enc = encrypt(flag)
f = open('flag.enc', 'wb')
f.write(enc)
f.close()
将 flag base64 加密之后大小写转换再与 key 异或
enc 是 48 位 所以 key 是 6 位
flag 以 CCTF{ 开头
base64 之后刚好 6 位固定
可以求出 key
即可得 base64 加密之后的密文
# exp
with open("flag.enc","rb") as f:
    a=f.read()
key=b'q0nurN'
k=b''
for i in range(6):
    k+=(a[i] ^ key[i % len(key)]).to_bytes(1, 'big')
print(k)
c=b''
for i in range(len(a)):
    c+=(a[i] ^ k[i % len(key)]).to_bytes(1, 'big')
print(c)
x=''
for i in c.decode():
    if i.islower():
        x+=i.upper()
    else:
        x+=i.lower()
from base64 import b64decode
print(b64decode(x.encode()))
# SOTS
# 题目
给出两个数的平方的和求这两个数
这个网站解一下
https://www.alpertron.com.ar/ECM.HTM
CCTF{3Xpr3sS_4z_Th3_sUm_oF_7w0_Squ4rE5!}
# 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}')
解方程就行
# exp
#sage
var('k')
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
n=44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
solve([p*q==n],[k])
#python
from Crypto.Util.number import *
n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
c = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
e = 31337
k = 9291098683758154336
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
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print(flag)
# 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}")
先看函数
def diamond(num):
	output = 0
	for i in range(num):
		output += i*2 + 1
	return output
diamond(num)=∑i=0n−12i+1=n2diamond(num)=\sum \limits_{i=0}^{n-1}2i+1=n^2
def triage(num):
	output = 0
	index = 0
	for i in range(num):
		output += (i+index)*6 + 1
		index += i
	return output
triage(num)=n3triage(num)=n^3
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
summarize(b)=\sum \limits^{n-1}_{i=2}\frac{f(i)+f(i+1)}
class TaylorSeries()
这个是泰勒级数
a0=1a_0=1
ai=1/2−i+1iai−12a_i=\frac{1/2-i+1}{i}a_{i-1}^2
在这基础上定义函数 f
f(x)=\sum \limits_{i=0}^{+ ∞ }a_i(x-1)^
我们得到
c0=∣d(p)−d(q)∣c_0=|d(p)-d(q)|
c1=t(p)+3∗n∗(p+1)+t(q)c_1=t(p)+3*n*(p+1)+t(q)
令 p>q
c0=∣d(p)−d(q)∣=p2−q2=(p+q)(p−q)c_0=|d(p)-d(q)|=p^2-q^2=(p+q)(p-q)
c1=t(p)+3∗n∗(p+1)+t(q)=(p+q)3c_1=t(p)+3*n*(p+1)+t(q)=(p+q)^3
可以求出 p，q
就可以求出 enc0 了
然后只要求得 key 就能求 flag
大佬的思路
[公式] 可以看成是对 f 的梯形法积分。也就是
[公式]
所以关键还是要分析出[公式] 是个啥玩意儿。主要就是弄清楚那个泰勒展开的系数是个啥。
经过一些尝试，发现[公式]（证明留在后面），所以
[公式]
所以也直接能求得[公式] 的值。
# exp
from Crypto.Util.number import *
c0 = 194487778980461745865921475300460852453586088781074246328543689440168930873549359227127363759885970436167330043371627413542337857082400024590112412164095470165662281502211335756288082198009158469871465280749846525326701136380764079685636158337203211609233704905784093776008350120607841177268965738426317288541638374141671346404729428158104872411498098187946543666987926130124245185069569476433120128275581891425551325847219504501925282012199947834686225770246801353666030075146469275695499044424390475398423700504158154044180028733800154044746648133536737830623670383925046006108348861714435567006327619892239876863209887013290251890513192375749866675256952802329688897844132157098061758362137357387787072005860610663777569670198971946904157425377235056152628515775755249828721767845990597859165193162537676147173896835503209596955703313430433124688537275895468076469102220355973904702901083642275544954262724054693167603475188412046722656788470695566949847884250306735314144182029335732280420629131990311054229665691517003924788583771265625694414774865289407885678238795596912006567817508035434074250123869676396153982762032750080222602796273083162627489526255501643913672882350236497429678928099868244687228703074267962827621792960
c1 = 102325064080381160170299055162846304227217463467232681115953623386548494169967745781550171804781503102663445039561476870208178139548389771866145006535051362059443515034504958703659546162037904784821960707630188600064568878674788077706711506213779443920430038560373854184526850365974450688458342413544179732143225845085164110594063440979455274250021370090572731855665413325275414458572412561502408983107820534723804225765540316307539962199024757378469001612921489902325166003841336027940632451584642359132723894801946906069322200784708303615779699081247051006259449466759863245508473429631466831174013498995506423210088549372249221415401309493511477847517923201080509933268996867995533386571564898914042844521373220497356837599443280354679778455765441375957556266205953496871475611269965949025704864246188576674107448587696941054123618319505271195780178776338475090463487960063464172195337956577785477587755181298859587398321270677790915227557908728226236404532915215698698185501562405374498053670694387354757252731874312411228777004316623425843477845333936913444143768519959591070492639650368662529749434618783626718975406802741753688956961837855306815380844030665696781685152837849982159679122660714556706669865596780528277684800454866433826417980212164051043504955615794706595412705883261111953152250227679858538249797999044336210905975316421254442221408945203647754303635775048438188044803368249944201671941949138202928389951227347433255867504906597772044398973241425387514239164853656233776024571606159378910745571588836981735827902305330330946219857271646498602227088657739442867033212012876837654750348578740516798444734534291467314881324902354425889448102902750077077381896216130734894767553834949561471219923459897244690006643798812989271282475503126962274052192342840870308710338336817452628324667507548265612892611100350882163205858101959976
'''
#sage
var('p q')
solve([p^2-q^2==c0,(p+q)^3==c1],[p,q])
'''
p=25465500595039564722385454268618341460440964303654692306893194812608651011894765148023201769023925823267446913594798724374078776058926548056279105656348138942211069695157129067986030357247987537066065195208337853580939616954961742954173270603234042184081995050125067398704045490448077961447418406856674045777724275017678698252609741079175784928310951915104807404003531834525200421059550762294584722178356010146438598799668537922242765662363844939035164178525445220653839693135494967926642943210917823981779895464411806829004306900926935124663285407830585204630912848783431051369106939431567473170247979142455819150893
q=21307368246113800130311098641506744510559988209047095448061577734947715969121645982743962584143752085867914325394457857827478912559095766977509129246922499990951138184298921892924074303356650532229644986118338361761354192554363128824141104808606558539422865199413633150757655174985683830034245659632460363700309887626934298289805670092066041542014924213128271705967504359900458092855272034197878632989626323553684162988741101770565319360726673172671459797955787997515498457867020749156835947018833861229200382521269341946614058721285386773372009177934062994798868703374266787876752211055631019633581263575312198649933
enc = 122235247669762131006183252122503937958296387791525458429403709404875223067116491817728568224832483391622109986550732469556761300197133827976956875865159629512476600711420561872409721582387803219651736262581445978042694384374119142613277808898398213602093802571586386354257378956087240174787723503606671543195193114158641301908622673736098768829071270132073818245595918660134745516367731595853832524328488074054536278197115937409643221809577554866060292157239061557708159310445977052686561229611117673473208278176118561352693319461471419694590218295911647368543698198762827636021268989705079848502749837879584394379300566277359149621932579222865430374652678738198451655509408564586496375811666876030847654260305392984710580761255795785508407844683687773983669843744274915862335181251050775093896006210092665809300090715190088851654138383362259256212093670748527819287681468901379286722214112321906917311154811516336259463356911326393701445497605365038857575515541024824906818473933597129846235905072394148879079996812146836910199111439031562946495046766063326815863624262541346543552652673629442370320109404700346028639853707278295255350982238521659924641921142615894039995513480511108116053798143154593343124822462519555715118822045
n=p*q
e=65537
enc0=long_to_bytes(pow(enc,inverse(e,(p-1)*(q-1)),n))
print(enc0)
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
key=floor(2/3*(n**(3/2)-2**(3/2)))#python 用不了
key=long_to_bytes(key)[:512]
m= xor(enc0, key)
print(m)
#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 with just measuring the area with a little fraction, forget about tough works!\nGood luck with the rest of CryptoCTF2022\x9a\x92W\xcf\xa2dl\x1a\x91\x96\'\x88\xec\xfez\xcd\xc2\xe7\x0bC\x90\xa3\xc7\xe7U\xb4F\xa535V\x19\x9b\x9e\xd4\xf7\xe7X\x02\x19Y\x86\xfa\x9f\x0b!\x9a\xc1\xd2\xcayG\x8af/\x14\xef\xf9\x1d\xc2\x9a\xcb\x9da}g8\xb8\\ 2~\xf3\xe3\xb6$\xb6i\x12\xd6\x82\xfac\x15\xeeVa[s\xa0S\x00y\x0c\x18\xc34\xbd\x96fd\xec\xcf\xb9\x02<Q\x8b\xb8\x9d\xd5\xefDu\xda\xd2\xf0\xc6g\x97\xf8\x952\x0c\rs=\x19.\x11"\x08\x81\xe7*\x87\xb8\xbd>\x82\n~\xf7l,\tu\x96}*\xab`\x17\xe7\xf4\xd7N^\xe3\xfe\xf3@\x1e\x1c\x15\xffC\xecVVr\xca\x8d\x03\xc5\xda\xd6\xbf=\xc6\x14+\xf2\x14N'
# 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
bytes_to_long 每一位是 2^8
a=97 aa=97*2^8+97
所以 p 和 q 的高位可以确定
# exp
#sage
from Crypto.Util.number import *
n = 23087202318856030774680571525957068827041569782431397956837104908189620961469336659300387982516148407611623358654041246574100274275974799587138270853364165853708786079644741407579091918180874935364024818882648063256767259283714592098555858095373381673229188828791636142379379969143042636324982275996627729079
c = 3621516728616736303019716820373078604485184090642291670706733720518953475684497936351864366709813094154736213978864841551795776449242009307288704109630747654430068522939150168228783644831299534766861590666590062361030323441362406214182358585821009335369275098938212859113101297279381840308568293108965668609
PR.<x> = PolynomialRing(Zmod(n))
e=65537
a=b'CCTF{it_is_fake_flag_'
b=b'0'*27
c=b'_90OD_luCk___!!}'
f=bytes_to_long(a)*2^(8*(len(b)+len(c)))+x*2^(8*len(c))+bytes_to_long(c)
f=f.monic()
root=f.small_roots(X=2^(8*(len(b))),beta=0.4)
p=gcd(ZZ(f(root[0])),n)
q=n//p
d=inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
#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()
求不定方程
a(z4−x2)=b(y2−z4)a(z^4-x^2)=b(y^2-z^4)
的正整数解，其中 a,b 已知。
给出的第 i 个解需要满足 z 为 i 比特整数。
首先把 z 都搬到一边
ax2+by2=(a+b)z4ax^2+by^2=(a+b)z^4
令x=y=z2x=y=z^2
# exp
from pwn import *
from Crypto.Util.number import *
re=remote("02.cr.yp.toc.tf",17113)
for i in range(19):
    re.recvuntil(b"| Send a solution like `x, y, z' such that the `z' is ")
    a=re.recvline().decode()[:2]
    z=getPrime(int(a))
    x=z**2
    y=x
    h=str(x)+', '+str(y)+', '+str(z)
    re.sendline(h.encode())
re.interactive()
# Volgo
# 题目
http://03.cr.yp.toc.tf:11117/
M-209 的加密机器
搜了一下发现是博福特密码类似于维吉尼亚
随便输几个数
发现收尾是固定的
只要输 A*155 得到 key 的值
然后博福特解密就行
YOU KNOW HOW TO FORMAT FLAG JUST PUT UPCOMING LETTERS WITHIN CURLY BRACES FOLLOWED BY CCTF OOJMPMDDIXCLNNWFTEJUMFXKBRVVMOPSLSSLUTXVDVNDMYYPHPWFJRNJBVBOMUYR
# Aniely
# 题目
#!/usr/bin/env python3
from struct import *
from os import *
from secret import passphrase, flag
def aniely_stream(passphrase):
	def mixer(u, v):
		return ((u << v) & 0xffffffff) | u >> (32 - v)
	def forge(w, a, b, c, d):
		for i in range(2):
			w[a] = (w[a] + w[b]) & 0xffffffff
			w[d] = mixer(w[a] ^ w[d], 16 // (i + 1))
			w[c] = (w[c] + w[d]) & 0xffffffff
			w[b] = mixer(w[b] ^ w[c], (12 + 2*i) // (i + 1))
	bring = [0] * 16
	bring[:4] = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
	bring[4:12] = unpack('<8L', passphrase)
	bring[12] = bring[13] = 0x0
	bring[14:] = [0] * 2
	while True:
		w = list(bring)
		for _ in range(10):
			forge(w, 0x0, 0x4, 0x8, 0xc)
			forge(w, 0x1, 0x5, 0x9, 0xd)
			forge(w, 0x2, 0x6, 0xa, 0xe)
			forge(w, 0x3, 0x7, 0xb, 0xf)
			forge(w, 0x0, 0x5, 0xa, 0xf)
			forge(w, 0x1, 0x6, 0xb, 0xc)
			forge(w, 0x2, 0x7, 0x8, 0xd)
			forge(w, 0x3, 0x4, 0x9, 0xe)
		for c in pack('<16L', *((w[_] + bring[_]) & 0xffffffff for _ in range(16))):
			yield c
		bring[12] = (bring[12] + 1) & 0xffffffff
		if bring[12] == 0:
			bring[13] = (bring[13] + 1) & 0xffffffff
def aniely_encrypt(msg, passphrase):
	if len(passphrase) < 32:
		passphrase = (passphrase * (32 // len(passphrase) + 1))[:32]
	rand = urandom(2) * 16
	return bytes(a ^ b ^ c for a, b, c in zip(msg, aniely_stream(passphrase), rand))
key = bytes(a ^ b for a, b in zip(passphrase, flag))
enc = aniely_encrypt(passphrase, key)
print(f'key = {key.hex()}')
print(f'enc = {enc.hex()}')
flag 和 passphrase 未知
key 和 enc 已知
key=passphrase⊕flagkey=passphrase⊕flag
要求 flag 就要求 passphrase
看加密函数
enc=passphrase⊕rand⊕stream(key)enc=passphrase⊕rand⊕stream(key)
stream (key) 已知
passphrase⊕rand=encsteam(key)passphrase⊕rand=enc^steam(key)
lll=key⊕passphrase⊕rand=passphrase⊕flag⊕passphrase⊕rand=flag⊕randlll=key⊕passphrase⊕rand=passphrase⊕flag⊕passphrase⊕rand=flag⊕rand
flag 以 CCTF{ 开头
而 rand 为 2 位重复 16 次
C ⊕lll[0], C ⊕lll [1] 即可求出 rand
# exp
key = 0x4dcceb8802ae3c45fe80ccb364c8de19f2d39aa8ebbfb0621623e67aba8ed5bc
enc = 0xe67a67efee3a80b66af0c33260f96b38e4142cd5d9426f6f156839f2e2a8efe8
from Crypto.Util.number import *
from struct import *
from os import *
def aniely_stream(passphrase):
    def mixer(u, v):
        return ((u << v) & 0xffffffff) | u >> (32 - v)
    def forge(w, a, b, c, d):
        for i in range(2):
            w[a] = (w[a] + w[b]) & 0xffffffff
            w[d] = mixer(w[a] ^ w[d], 16 // (i + 1))
            w[c] = (w[c] + w[d]) & 0xffffffff
            w[b] = mixer(w[b] ^ w[c], (12 + 2 * i) // (i + 1))
    bring = [0] * 16
    bring[:4] = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
    bring[4:12] = unpack('<8L', passphrase)
    bring[12] = bring[13] = 0x0
    bring[14:] = [0] * 2
    while True:
        w = list(bring)
        for _ in range(10):
            forge(w, 0x0, 0x4, 0x8, 0xc)
            forge(w, 0x1, 0x5, 0x9, 0xd)
            forge(w, 0x2, 0x6, 0xa, 0xe)
            forge(w, 0x3, 0x7, 0xb, 0xf)
            forge(w, 0x0, 0x5, 0xa, 0xf)
            forge(w, 0x1, 0x6, 0xb, 0xc)
            forge(w, 0x2, 0x7, 0x8, 0xd)
            forge(w, 0x3, 0x4, 0x9, 0xe)
        for c in pack('<16L', *((w[_] + bring[_]) & 0xffffffff for _ in range(16))):
            yield c
        bring[12] = (bring[12] + 1) & 0xffffffff
        if bring[12] == 0:
            bring[13] = (bring[13] + 1) & 0xffffffff
key = long_to_bytes(key)
enc=long_to_bytes(enc)
ll=bytes(a ^ b for a, b in zip(enc, aniely_stream(key)))
cc=bytes(a ^ b for a, b in zip(key, ll))
rand=long_to_bytes(cc[0]^ord('C'))+long_to_bytes(cc[1]^ord('C'))
rand=rand*16
print(bytes(a ^ b for a, b in zip(cc, rand)))
# Diploma
# 题目
在 GF (p) 上的 d 阶可逆矩阵群 GL (d,p) 中，抽一个元素 M。求 M 的阶。
sage 可以直接用
# exp
from pwn import *
from Crypto.Util.number import *
re=remote("08.cr.yp.toc.tf",37313)
for i in range(3,15):
    re.recvuntil(b'| Generating the parameters for p = ')
    p = re.recvuntil(b',').decode()[:-1]
    p = int(p)
    re.recvuntil(b'| M = \n')
    M = []
    for j in range(i):
        s = re.recvline().decode().strip()[1:-1]
        M.append([int(x) for x in s.split(' ') if x != ''])
    M = Matrix(GF(p), M)
    ans = M.multiplicative_order()
    re.sendline(str(ans).encode())
re.interactive()
# Oak land
# 题目
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576
x = bytes_to_long(flag.encode('utf-8'))
assert x < p
c = (110 * pow(e, x, p) + 313 * pow(f, x, p) + 114 * pow(g, x, p)) % p
print(f'c = {c}')
#c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356
c=110∗exmodp+313∗fxmodp+114∗gxmodpc=110*e^x\mod p+313*f^x\mod p+114*g^x\mod p
f,e,p,g,c 已知
求 x
看出
f=e−1modpf=e^{-1}\mod p
g=f2modpg=f^2\mod p
c=110∗exmodp+313∗e−xmodp+114∗e−2xmodpc=110*e^x\mod p+313*e^{-x}\mod p+114*e^{-2x}\mod p
c∗e2x=110∗e3xmodp+313∗exmodp+114modpc*e^{2x}=110*e^{3x}\mod p+313*e^{x}\mod p+114\mod p
在模 p 的意义下解出exe^x 为多少
# exp
from Crypro.Util.number import *
p = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
e = 31337
f = 7236042467316654159796543399639966340258093274047941788600980451877044636122969830708918356119442228154447395855689559447196348683125675305629837437591088260218138895919514078948650757100432223219969122629790
g = 1878626136321051642174045874618248475160620873585704351202865003185878331837410979441756843820270907300810543618813757245154196050399357659526631164136221434463496532263979506870318259276669412698827040743576
c = 871346503375040565701864845493751233877009611275883500035764036792906970084258238763963152627486758242101207127598485219754255161617890137664012548226251138485059295263306930653899766537171223837761341914356
F.<x> = PolynomialRing(Zmod(p))
f = (110 * x^3 + 313 * x + 114 - c * x^2)
ex=f.root()[0][0]
m=discrete_log(mod(ex,p),mod(e,p))
print(long_to_bytes(m))
#CCTF{V33333rY_eeeeZy_DLP_cH41L3n9E!}
# Cantilever
# 题目
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def gen_primes(nbit, imbalance):
	p = 2
	FACTORS = [p]
	while p.bit_length() < nbit - 2 * imbalance:
		factor = getPrime(imbalance)
		FACTORS.append(factor)
		p *= factor
	rbit = (nbit - p.bit_length()) // 2
	while True:
		r, s = [getPrime(rbit) for _ in '01']
		_p = p * r * s
		if _p.bit_length() < nbit: rbit += 1
		if _p.bit_length() > nbit: rbit -= 1
		if isPrime(_p + 1):
			FACTORS.extend((r, s))
			p = _p + 1
			break
	FACTORS.sort()
	return (p, FACTORS)
def genkey(nbit, imbalance, e):
	while True:
		p, FACTORS = gen_primes(nbit // 2, imbalance)
		if len(FACTORS) != len(set(FACTORS)):
			continue
		q, q_factors = gen_primes(nbit // 2, imbalance + 1)
		if len(q_factors) != len(set(q_factors)):
			continue
		factors = FACTORS + q_factors
		if e not in factors:
			break
	n = p * q
	return n, (p, q)
nbit = 2048
imbalance = 19
e = 0x10001
m_1 = bytes_to_long(flag[:len(flag) // 2])
m_2 = bytes_to_long(flag[len(flag) // 2:])
n, PRIMES = genkey(nbit, imbalance, e)
c_1 = pow(m_1, e, n)
c_2 = pow(e, m_2, n)
print(f'n = {n}')
print(f'c_1 = {c_1}')
print(f'c_2 = {c_2}')
n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
可以看到 p-1 光滑
可以分解 n
得到 m1
m2 没思路 看赵总的
求出分解后，由于 p-1 和 q-1 均光滑，可以先用 Pohlig-Hellman 分别求出 m2 模 p-1 和模 q-1 的值，进而用中国剩余定理求出明文 m2。
# exp
from gmpy2 import *
from Crypto.Util.number import *
a = 2
N=7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
n = 2
e=0x10001
c=488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
while True:
    a = powmod(a, n, N)
    res = gcd(a-1, N)
    if res != 1 and res != N:
        q = N // res
        d = invert(e, (res-1)*(q-1))
        m = powmod(c, d, N)
        print(q)
        print(long_to_bytes(m))
        break
    n += 1
    
    
q=84761154786085445040051273337185621770653977624442810400422736258693219544281946893222923335092616440575888204882883202879374137962201839964482318483860286412488851522612902055732831909496637360268825720155284438779235801463340052531340653630637729255285872455686692027630814695155220888112228977346697309127
p=n//q
Zp, Zq = Zmod(p), Zmod(q)
m_2p = discrete_log(Zp(c2), Zp(e))
m_2q = discrete_log(Zq(c2), Zq(e))
m_2 = crt([m_2p, m_2q], [p-1, q-1])
print(long_to_bytes(m_2))
#CCTF{5L3Ek_4s__s1lK__Ri9H7?!}
# Side step
# 题目
#!/usr/bin/env python3
from Crypto.Util.number import *
import random, sys
from flag import flag
def pow_d(g, e, n):
	t, r = 0, 1
	for _ in bin(e)[2:]:
		if r == 4: t += 1
		r = pow(r, 2, n)
		if _ == '1': r = r * g % n
	return t, r
def ts(m, p):
	m = m % p
	return pow(m, (p - 1) // 2, p) == 1
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, "Hi all cryptographers! Welcome to the Sidestep task, we do powing!!!", border)
	pr(border, "You should solve a DLP challenge in some special way to get the flag", border)
	p = 2 ** 1024 - 2 ** 234 - 2 ** 267 - 2 ** 291 - 2 ** 403 - 1
	s = random.randint(2, (p - 1) // 2)
	while True:
		pr("| Options: \n|\t[T]ry the magic machine \n|\t[Q]uit")
		ans = sc().lower()
		if ans == 't':
			pr(border, "please send your desired integer: ")
			g = sc()
			try:
				g = int(g)
			except:
				die(border, "The given input is not integer!")
			if ts(g, p):
				t, r = pow_d(g, s, p)
				if r == 4:
					die(border, f'Great! you got the flag: {flag}')
				else:
					pr(border, f"t, r = {t, r}")
			else:
				pr(border, "The given base is NOT valid!!!")
		elif ans == 'q':
			die(border, "Quitting ...")
		else:
			die(border, "Bye bye ...")
if __name__ == "__main__":
	main()
# Starter ECC
# 题目
#!/usr/bin/env sage
from Crypto.Util.number import *
from secret import n, a, b, x, flag
y = bytes_to_long(flag.encode('utf-8'))
assert y < n
E = EllipticCurve(Zmod(n), [a, b])
try:
	G = E(x, y)
	print(f'x = {x}')
	print(f'a = {a}')
	print(f'b = {b}')
	print(f'n = {n}')
	print('Find the flag :P')
except:
	print('Ooops, ERROR :-(')
y2=x3+ax+bmodny^2=x^3+ax+b\mod n
x,a,b,n 已知
求 y
其实是求模 n 下的二次剩余
分解 n
n=2^63 · 690712633549859897233^6 · 651132262883189171676209466993073^5
# exp
#sage
from Crypto.Util.number import *
import itertools
x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936
p = 2^63
q = 651132262883189171676209466993073^5
r = 690712633549859897233^6
ps = [p, q, r]
ys = []
RHS = (x^3 + a * x + b) % n
for p in ps:
    sol = Zmod(p)(RHS).nth_root(2, all=True)
    ys.append([ZZ(x) for x in sol])
for real_ys in itertools.product(*ys):
    y = crt(list(real_ys), ps)
    y = long_to_bytes(y)
    if (b'CCTF' in y):
        print(y)
 更新于   阅读次数  次