当前位置：首页 > news >正文

[CPCTF 2025] Crypto

news 2025/5/1 15:10:17

上上周的比赛，有事没写，补上一部分。最近都是每周3个，难度感觉越来越大。

Heroic code

Caeser爆下即可

'''
Xubbe qdt jxqda oek veh zeydydw jxu SFSJV! Jxu vbqw yi SFSJV{qbuq_zqsjq_uij}.
Hello and thank you for joining the CPCTF! The flag is CPCTF{alea_jacta_est}.
'''

add-and-multiple

plaintext = input()
a = [ord(i) for i in plaintext]
cipher = 0
for i,chr in enumerate(a,1000):cipher += chrcipher *= i
f = open('cipher.txt', 'w')
f.write(str(cipher))
f.close()

这个for i,chr in enumerate(a,1000)式子不常见，测试一下是说i从1000开始，那么这个式子就是：

c = a0*1000*1001... + a1*1001*... + an*1029

第个的参数是1000*....*1029，第2个参数是1001*...*1029这样显然第1个因子最大，所以从大到小除一下就得到flag

c = 103200264548574214569124695908951019136986646123214535931636006688814109904122192900997137101
base = prod(range(1000,1030))
flag = ''
i = 1000
while c>1000:k = c//basec -= k*baseflag+=chr(k)print(flag)base//=ii+=1#CPCTF{C14ssic4l_Ciph3r_15_fun}

Anomaly

from Crypto.Util.number import getPrime, bytes_to_longflag = "CPCTF{fake_flag}"p = getPrime(512)
e = getPrime(512)
q = 0x10001
n = p * q
c = pow(bytes_to_long(flag.encode()), e, n)with open("output.py", "w") as f:f.write(f"e = {e}\n")f.write(f"n = {n}\n")f.write(f"c = {c}\n")

这个就比较简单了，n的一个小因子已经，去掉后拿另一个就能直接求解

p = n//0x10001
m = pow(c,inverse_mod(e,p-1),p)
long_to_bytes(int(m))#CPCTF{You_h4v3_escap3d!_8fa245b1007bc564}

One More PPC Problem

from secrets import randbelowm = 80701148760020250419  # prime
a = 20250418
b = 240240240240MAX_N = 10**5
MAX_Q = 100class myRand:def __init__(self):self.v = randbelow(m)def random(self):self.v = (a*self.v+b) % mreturn self.vdef genCase(h, w, rd):A = [[rd.random() % MAX_N+1 for _ in range(w)] for _ in range(h)]A[rd.random() % h][rd.random() % w] = 0return (A, h, w)def judge(case):A, H, W = casecnt = 0x, y = 0, 0print(f"{H} {W}")while cnt < MAX_Q:cnt += 1op = input()if op == '>':y += 1elif op == '<':y -= 1elif op == '^':x -= 1elif op == 'v':x += 1else:print("Invalid Input")return Falseif x >= 0 and x < H and y >= 0 and y < W:print(A[x][y])if A[x][y] == 0:return Trueelse:print("Out of Stage")return Falseprint("Query Over")return Falsedef main():r = myRand()caseHW = [(5, 5), (10, 10), (50, 50), (50, 50), (50, 50),(50, 50), (50, 50), (50, 50), (50, 50), (50, 50), (50, 50)]for i in range(len(caseHW)):h, w = caseHW[i]case = genCase(h, w, r)if not judge(case):print(f"WA on Case {i}")exit(0)print("AC!")with open("flag.txt") as f:print(f.read())exit(0)if __name__ == '__main__':try:main()except:print("Judge Error")exit()

这个没弄成，后来感觉刚开始方法有点问题。

这是一个lcg模式（a,b,m已知）的伪随机数，给出后5位10进制数。

每关当除放置w*w个随机数外会随机生成一个坐标，在坐标对应格内填0，当移动到为0的格（小于100步）时过关。

一开始发现用第1关25格里的10个完成不了就没接着作。其实可以先路过第1关，（只有5*5个格动一遍不会到100）用第2关的20个格来求应该是可以的。回头试好了再补上

#from pwn import remote,context as ctx
#ctx.log_level = 'debug'
#from sage.all import *m = 80701148760020250419  # prime
a = 20250418
b = 240240240240MAX_N = 10**5
MAX_Q = 100class myRand:def __init__(self,seed):self.v = seeddef random(self):self.v = (a*self.v+b) % mreturn self.vdef genCase(h, w, rd):A = [[rd.random() % MAX_N+1 for _ in range(w)] for _ in range(h)]A[rd.random() % h][rd.random() % w] = 0return (A, h, w)def get_seed(k3):dim = len(k3)-1k3 = [i-1 for i in k3]A = [1]B = [0]for i in range(1, dim):A.append(a*A[i-1] % m)B.append((a*B[i-1]+(a*k3[i]+b-k3[i+1])*inverse_mod(100000,m)) % m)A = A[1:]B = B[1:]M = matrix(ZZ, dim, dim)for i in range(dim-2):M[i, i] = mM[-2, i] = A[i]M[-1, i] = B[i]M[i, -2] = M[i, -1] = 0M[-2,-2] =  1M[-1,-1] = m//100000  #高位的规模ll = M.LLL()[0]l1 = ll[-2]h1 = k3[1]s1 = l1*100000+h1seed = ((s1-b)*inverse_mod(a,m))%mseed = ((seed-b)*inverse_mod(a,m))%mprint(seed)return seed#test
seed = 61998074543891883238
rd = myRand(seed)
A,h,w = genCase(10,10,rd)#用10*10来求seed 当前20个值为含0时
k3 = A[0]+A[1]
seed2 = get_seed(k3)assert seed == seed2

RSA Trial

from Crypto.Util.number import getPrime, bytes_to_long
from sympy import nextprime
from secret import flagp = getPrime(512)
q = getPrime(512)
r = nextprime(p + q)n = p * q * r
hint = p**3 + q**3 + r**3
e = 0x10001
c = pow(bytes_to_long(flag.encode()), e, n)with open("output.py", "w") as f:f.write(f"e = {e}\n")f.write(f"n = {n}\n")f.write(f"c = {c}\n")f.write(f"hint = {hint}\n")

这个题给出的r=next_prime(p+q),给出的hint = p^3+q^3+r^3可以根据3次方展开公式得到：

2*(p+q)^3 = hint + 3*n

由于r只是略大于p+q可以直接开3次方得到p+q从面分解n

p_q = iroot((hint+3*n)//2,3)[0]
r = next_prime(p_q)
assert gcd(r,n) == r
#17758421139024913359737842854715476386497379733049987554858008465450704659866266822649115010114307927129443930502131087390672063301921117757614648780099317
m = pow(c,invert(65537,r-1),r)
#1995359735599891780688837994124480968965315009678458446439030574806791881327928957
long_to_bytes(m)
#b'CPCTF{tr1pl3_RSA_8011aed45d7c060f}'

Prime Tester

from math import gcddef is_prime(n):if n == 2: return Trueif n == 1 or n & 1 == 0: return Falsed = n - 1while d & 1 == 0:d >>= 1for a in range(500):if gcd(a, n) != 1:continuet = dy = pow(a, t, n)while t != n - 1 and y != 1 and y != n - 1:y = (y * y) % nt <<= 1if y != n - 1 and t & 1 == 0:return Falsereturn Trueif __name__ == '__main__':n = int(input("What is your favorite prime number?: "))if n <= 2 or 4096 <= n.bit_length():print("Hmm... I don't like this.")exit(0)if not is_prime(n):print(":(")exit(0)x = int(input("What is your favorite number?: "))if x <= 1 or x >= n - 1:print(":(")exit(0)if pow(x, 2, n) == x:print("Wow! How did you do that?")with open("flag.txt") as f:print(f.read())else:print("Nice!")exit(0)

要求输入一个n和一个x使得 x^2=x mod n并且n能通上边函数的伪素数测试。

感觉就是找一个500内base的伪素数就行，当n为素数里显然x^2==x只有0和1两个解达不到要求，当是合数里就有解，这个就模p,q分别得0，1

如果是300内的倒是有个存着的数

p = 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883
n = p *(313*(p - 1) + 1)*(353 * (p - 1) + 1)

500以内的搜了半天没搜着，放弃了。等哪天看着了再补上。

后来看他有3个hint，指向一篇论文，

但打开不知道论文内容是啥，不过搜到另外一个文章：

Constructing Miller–Rabin Pseudoprimes with SageMath

这里边有几个生成的例子，直接用541（>500）的那个即可

P = 7787732278755017824602699104690213508779614394369890477845377286825786597995065267843507802259844752423265555266243395693314487288078622041297083410934849005783165970061493954764862875292520625075354020623135144404282468700013671547
Q = 32529357728359709453365474160291021826172449325283032525960140927071310619825387623782332090039371530871980224347098663810974613402304404266497917407474864297156284256946860249052832230096858650939753744142835498176687871759957106047643
R = 16206270872089192092998216836860334311770377554683742084396230133884461910427730822382339736502736929792815620509052506437787448046491612467939230578155420781034768383697968919865679643483735420781811716916744235505311817364728450487227#n = P*Q*R
n = 4105533452433021765013837810250129497906776520439478762444757535787150166441808983131547549061042819241803677734684089387936615218512623246819260378395895806190969367738434747226833314918439125195560533069527626034315805252829069712946717489170662443699387652432168043013276992556383661463839991504034566570743939526431419627777024666651653328024067508705964704654262029757671485757644661464119465787544601305942781717049259725682702584999377699680541279376069665052863573819455144839742780771486371611198963915144096863366918510828427548413169928095028815881158255689153934576571383186599819333534474537810962373427256838686635300737173281200715737713827696261842481543872169300021385829998511793741667x = crt([0,0,1],[P,Q,R])
#1531366200181857377711253471591901546605387878653347058218367918899607190461573193774806122702526922633475207812515387104410225065505299232264145284679931809647250559662552357937882813391742908457819909520410271610494598873622898582376109230868035330321739604649879686263758296364934129304872988377327320975681824510252422811945467449312545894524670151200577073909395338222544281619489797225047347782037973971554822098059238445615511329358004762839987872520530558881754025345678961468010903818101033188743863511475142658563659779475437162133039943938077147640118449176233077231755249379875098399536038795818364620535923984824500857838465466897011059723446084866589594699779679030111619356355660402100543asset x^2%n == x

查看全文

http://www.mrgr.cn/news/100803.html