1.XR4#
import base64
import random
from secret import flag
import numpy as np
def init_sbox(key):
s_box = list(range(256))
j = 0
for i in range(256):
j = (j + s_box[i] + ord(key[i % len(key)])) % 256
s_box[i], s_box[j] = s_box[j], s_box[i]
return s_box
def decrypt(cipher, box):
res = []
i = j = 0
cipher_bytes = base64.b64decode(cipher)
for s in cipher_bytes:
i = (i + 1) % 256
j = (j + box[i]) % 256
box[i], box[j] = box[j], box[i]
t = (box[i] + box[j]) % 256
k = box[t]
res.append(chr(s ^ k))
return (''.join(res))
def random_num(seed_num):
random.seed(seed_num)
for i in range(36):
print(chr(int(str(random.random()*10000)[0:2]) ^ (data[i])))
if __name__ == '__main__':
ciphertext = "MjM184anvdA="
key = "XR4"
box = init_sbox(key)
a=decrypt(ciphertext, box)
random_num(int(a))
# transposed_matrix=(data.reshape(6*6))^T
# transposed_matrix=[[ 1 111 38 110 95 44]
# [ 11 45 58 39 84 1]
# [116 19 113 60 91 118]
# [ 33 98 38 57 10 29]
# [ 68 52 119 56 43 125]
# [ 32 32 7 26 41 41]]类似RC4的流密码，解密思路是用密钥XR4解密密文MjM184anvdA=还原出随机数种子，用来重置随机数生成器，再恢复矩阵，最后生成随机数流逐位异或就能得到答案，exp
import base64
import random
import numpy as np
# RC4初始化函数
def init_sbox(key):
s_box = list(range(256))
j = 0
for i in range(256):
j = (j + s_box[i] + ord(key[i % len(key)])) % 256
s_box[i], s_box[j] = s_box[j], s_box[i]
return s_box
# RC4解密函数
def decrypt(cipher, box):
res = []
i = j = 0
cipher_bytes = base64.b64decode(cipher)
for s in cipher_bytes:
i = (i + 1) % 256
j = (j + box[i]) % 256
box[i], box[j] = box[j], box[i]
t = (box[i] + box[j]) % 256
k = box[t]
res.append(s ^ k)
return bytes(res)
if __name__ == '__main__':
# 已知参数
ciphertext = "MjM184anvdA="
key = "XR4"
transposed_matrix = np.array([
[1, 111, 38, 110, 95, 44],
[11, 45, 58, 39, 84, 1],
[116, 19, 113, 60, 91, 118],
[33, 98, 38, 57, 10, 29],
[68, 52, 119, 56, 43, 125],
[32, 32, 7, 26, 41, 41]
])
# Step 1: 解密RC4获取种子
box = init_sbox(key)
seed_bytes = decrypt(ciphertext, box.copy())
seed = int(seed_bytes.decode())
print(f"[+] 解密种子值: {seed}") # 78910112
# Step 2: 恢复原始矩阵
original_matrix = transposed_matrix.T.reshape(-1) # 转置恢复原始顺序
# Step 3: 生成随机数序列
random.seed(seed)
flag_chars = []
for num in original_matrix:
rand_val = int(str(random.random() * 10000)[:2]) # 生成前两位数字
flag_char = chr(rand_val ^ num)
flag_chars.append(flag_char)
# Step 4: 组合flag
flag = ''.join(flag_chars)
print(f"\n[+] 解密结果: {flag}") # c570ee41-8b09-11ef-ac4a-a4b1c1c5a2d2
flag{c570ee41-8b09-11ef-ac4a-a4b1c1c5a2d2}
2.essential#
from Crypto.Util.number import *
import sympy
from flag import flag
a=getPrime(512)
p=sympy.nextprime(13*a)
q=sympy.prevprime(25*a)
number2=p*q
def crypto01(number1, number2, number3):
number4 = 1
while number2 > 0:
if number2 % 2:
number4 = (number4 * number1) % number3
number1 = number1 ** 2 % number3
number2 //= 2
return number4
# n1^n2 mod n3
def crypto02(number1, number2):
number3 = number1
number4 = number2
giao = 1
giaogiao = 0
while number4 > 0:
number7 = number3 // number4
giao, giaogiao = giaogiao, giao - giaogiao*number7
number3, number4 = number4, number3 - number4*number7
while giao<0:
giao = giao + number2
return giao
#pow(n1,-1,n2)
def crypto03(number1, number2, number3):
number4 = crypto01(number3, number1, number2)
return number4
# n3^n1 mod n2
def crypto05(number1,number2):
return pow(number1,0xe18e,number2)
# n1^e mod n2
number2 = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947
number1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683
number3 = int.from_bytes(flag[0:19].encode("utf-8"), "big")
number4 = int.from_bytes(flag[19:39].encode("utf-8"), "big")
print(crypto03(number1, number2, number3))
print(crypto05(number4,number2))
#6624758244437183700228793390575387439910775985543869953485120951825790403986028668723069396276896827302706342862776605008038149721097476152863529945095435498809442643082504012461883786296234960634593997098236558840899107452647003306820097771301898479134315680273315445282673421302058215601162967617943836306076 p1
#204384474875628990804496315735508023717499220909413449050868658084284187670628949761107184746708810539920536825856744947995442111688188562682921193868294477052992835394998910706435735040133361347697720913541458302074252626700854595868437809272878960638744881154520946183933043843588964174947340240510756356766 p2
套层皮的RSA，crypto01计算的是
crypto02计算的是
crypto03计算的是
crypto05计算的是
这里给出了
,注意到a就512位，且考虑到质数分步在500多位下都很密集，p应该很接近13a，q很接近25a，那么就可以对n1除去13*25再开根，得到一个a的初步估计，再尝试搜索出p,q的值，脚本如下
def find_a(n):
a_approx = gmpy2.isqrt(n // 325)
for delta in range(-1000, 1000): # 搜索偏移范围
a_candidate = int(a_approx) + delta
p = sympy.nextprime(13 * a_candidate)
q = sympy.prevprime(25 * a_candidate)
if p * q == n:
return a_candidate, p, q
return None
a, p, q = find_a(n)
print(f"[+] Found a: {a}")
print(f"p = {p}\nq = {q}")
```
[+] Found a: 7876724580534791771835430594434627088013471560469412207736963203935537053220379418645369259714178145931522503674390087394035229717461111762112820042426110
p = 102397419546952293033860597727650152144175130286102358700580521651161981691864932442389800376284315897109792547767071136122457986326994452907466660551539601
q = 196918114513369794295885764860865677200336789011735305193424080098388426330509485466134231492854453648288062591859752184850880742936527794052820501060652747
```有了p,q之后就是很基础的RSA解明文了，注意到e与phi不互素，但是gcd很小，先试着用e//2算，实在不行再尝试有限域开根，所幸这里直接就算出来了,exp
p = 102397419546952293033860597727650152144175130286102358700580521651161981691864932442389800376284315897109792547767071136122457986326994452907466660551539601
q = 196918114513369794295885764860865677200336789011735305193424080098388426330509485466134231492854453648288062591859752184850880742936527794052820501060652747
number2 = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947
number1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683
c1 = 6624758244437183700228793390575387439910775985543869953485120951825790403986028668723069396276896827302706342862776605008038149721097476152863529945095435498809442643082504012461883786296234960634593997098236558840899107452647003306820097771301898479134315680273315445282673421302058215601162967617943836306076
c2 = 204384474875628990804496315735508023717499220909413449050868658084284187670628949761107184746708810539920536825856744947995442111688188562682921193868294477052992835394998910706435735040133361347697720913541458302074252626700854595868437809272878960638744881154520946183933043843588964174947340240510756356766
e=0xe18e
phi = (p-1)*(q-1)
print(GCD(number1,phi))
d1 = inverse(number1,phi)
m1 = pow(c1,d1,number2)
d2 = inverse(e//2,phi)
M2 = pow(c2,d2,number2)
m2 = int(gmpy2.iroot(M2,2)[0])
print(long_to_bytes(m1)+long_to_bytes(m2))
#b'flag{75811c6d95770d56092817b75f15df05}'flag{75811c6d95770d56092817b75f15df05}
3.EZ-calculate#
from Crypto.Util.number import *
from random import randint
from hashlib import md5
flag1 = b'xxx'
flag2 = b'xxx'
Flags = 'flag{' + md5(flag1+flag2).hexdigest()[::-1] + '}'
def backpack_encrypt_flag(flag_bytes, M, group_len):
bits = []
for byte in flag_bytes:
bits.extend([int(b) for b in format(byte, "08b")])
while len(bits) % group_len != 0:
bits.append(0)
S_list = []
for i in range(0, len(bits), group_len):
group = bits[i:i + group_len]
S = sum(bit * m for bit, m in zip(group, M))
S_list.append(S)
return S_list
def backpack(flag_bytes):
R = [10]
while len(R) < 8:
next_val = randint(2 * R[-1], 3 * R[-1])
R.append(next_val)
B = randint(2 * R[-1] + 1, 3 * R[-1])
A = getPrime(100)
M = [A * ri % B for ri in R]
S_list = backpack_encrypt_flag(flag_bytes, M, len(M))
return R, A, B, M, S_list
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 0x10000
m = bytes_to_long(flag1)
k = randint(1, 999)
problem1 = (pow(p,e,n)-pow(q,e,n)) % n
problem2 = pow(p-q,e,n)*pow(e,k,n)
c = pow(m,e,n)
R, A, B, M, S_list = backpack(flag2)
with open(r"C:\Users\Rebirth\Desktop\data.txt", "w") as f:
f.write(f"problem1 = {problem1}\n")
f.write(f"problem2 = {problem2}\n")
f.write(f"n = {n}\n")
f.write(f"c = {c}\n")
f.write("-------------------------\n")
f.write(f"R = {R}\n")
f.write(f"A = {A}\n")
f.write(f"B = {B}\n")
f.write(f"M = {M}\n")
f.write(f"S_list = {S_list}\n")
f.write("-------------------------\n")
f.write(f"What you need to submit is Flags!\n")part1
RSA,题目给出的是
这里我们的思路是枚举k的取值，计算出pow(e,k,n)之后用p2来除它，得到P，那么由二项式定理
上下相加，容易得到
同样的方法我们也能枚举出q，再用位数和正负号作为制约就能爆破出p,q的值，脚本如下
problem1 = 24819077530766367166035941051823834496451802693325219476153953490742162231345380863781267094224914358021972805811737102184859249919313532073566493054398702269142565372985584818560322911207851760003915310535736092154713396343146403645986926080307669092998175883480679019195392639696872929250699367519967334248
problem2 = 20047847761237831029338089120460407946040166929398007572321747488189673799484690384806832406317298893135216999267808940360773991216254295946086409441877930687132524014042802810607804699235064733393301861594858928571425025486900981252230771735969897010173299098677357738890813870488373321839371734457780977243838253195895485537023584305192701526016
n = 86262122894918669428795269753754618836562727502569381672630582848166228286806362453183099819771689423205156909662196526762880078792845161061353312693752568577607175166060900619163231849790003982326663277243409696279313372337685740601191870965951317590823292785776887874472943335746122798330609540525922467021
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776
e=65536
for i in range(1,1000):
k = pow(e,i,n)
Pr2 = problem2//k
# print(isinstance(Pr2,int))
sum = problem1+Pr2
sub = Pr2 - problem1
if sub>0 :
q = GCD(sub,n)
print(q)
# 爆破p q
#p = 9586253455468582613875015189854230646329578628731744411408644831684238720919107792959420247980417763684885397749546095133107188260274536708721056484419031
#q = 8998523072192453101232205847855618180700579235012899613083663121402246420191771909612939404791268078655630846054784775118256720627970477420936836352759291
然后这里e是65536，不和phi互素，gcd是4，就考虑有限域开根然后用crt算可能的解了，脚本如下
from Crypto.Util.number import *
from math import gcd
from sage.all import *
# 给定参数
p = 9586253455468582613875015189854230646329578628731744411408644831684238720919107792959420247980417763684885397749546095133107188260274536708721056484419031
q = 8998523072192453101232205847855618180700579235012899613083663121402246420191771909612939404791268078655630846054784775118256720627970477420936836352759291
n = p * q
e = 65536
c = 74962027356320017542746842438347279031419999636985213695851878703229715143667648659071242394028952959096683055640906478244974899784491598741415530787571499313545501736858104610426804890565497123850685161829628373760791083545457573498600656412030353579510452843445377415943924958414311373173951242344875240776
possible_m = []
def decrypt_rsa_with_coprime_e(p, q, e, c):
# 计算模p和模q的c值
c_p = c % p
c_q = c % q
# 处理模p下的解
s_p = (p - 1) // 2 # 因为p-1的2的指数为1
d_p = pow(e, -1, s_p)
m_p = pow(c_p, d_p, p)
solutions_p = [m_p, (-m_p) % p]
# 处理模q下的解
s_q = (q - 1) // 2 # q-1的2的指数为1
d_q = pow(e, -1, s_q)
m_q = pow(c_q, d_q, q)
solutions_q = [m_q, (-m_q) % q]
# 使用CRT组合所有可能的解
from itertools import product
possible_m = []
for mp, mq in product(solutions_p, solutions_q):
m = CRT([mp, mq], [p, q])
possible_m.append(m)
return possible_m
# 执行解密
possible_m = decrypt_rsa_with_coprime_e(p, q, e, c)
for m in possible_m:
print(long_to_bytes(m))
# b'CRYPTO_ALGORIT'不过跑出来b'CRYPTO_ALGORIT'就是第一个，有可能开根也能做呢
-
part2
背包加密，不过该给的都给了，按照加密过程反过来写很快就能搞出来
pythonfrom Crypto.Util.number import long_to_bytes import math # 已知参数 R = [10, 29, 83, 227, 506, 1372, 3042, 6163] A = 1253412688290469788410859162653 B = 16036 M = [10294, 12213, 10071, 4359, 1310, 4376, 7622, 14783] S_list = [13523, 32682, 38977, 44663, 43353, 31372, 17899, 17899, 44663, 16589, 40304, 25521, 31372] def backpack_decrypt(S_list, A, B, M): # 1. 验证A与B互质 assert math.gcd(A, B) == 1, "A and B must be coprime" # 2. 计算A的模逆元 inv_A = pow(A, -1, B) # 3. 恢复超递增序列R R_recovered = [(m * inv_A) % B for m in M] print("恢复的R:", R_recovered) # 应等于原始R # 4. 解密每个S值 bits = [] for S in S_list: # 将S转换为超递增背包问题 S_prime = (S * inv_A) % B # 贪心算法解背包 group = [] remaining = S_prime for r in reversed(R_recovered): if remaining >= r: group.append(1) remaining -= r else: group.append(0) bits.extend(group[::-1]) # 反转后加入 # 5. 转换二进制为字节 bytes_data = b'' for i in range(0, len(bits), 8): byte_bits = bits[i:i+8] if len(byte_bits) < 8: byte_bits += [0]*(8 - len(byte_bits)) byte = int(''.join(map(str, byte_bits)), 2) bytes_data += bytes([byte]) # 6. 去除填充的零 return bytes_data.rstrip(b'\x00') # 执行解密 flag2 = backpack_decrypt(S_list, A, B, M) print("解密结果:", flag2.decode()) # HMS_WELL_DONE最后对两个flag拼接之后取md5，
flag{64f67374264b7621650b1de4dbc5f924}
4.merge_ECC#
#t.sage
import random
from sympy import nextprime
def part1():
p = random_prime(2^512, 2^513)
a = random.randint(0, p-1)
b = random.randint(0, p-1)
while (4 * a**3 + 27 * b**2) % p == 0:
a = random.randint(0, p-1)
b = random.randint(0, p-1)
E = EllipticCurve(GF(p), [a, b])#构造一个模p环下的关于a,b的椭圆曲线
P=E.random_point()#曲线上的随机一个点
n = [random.randint(1, 2**20) for _ in range(3)] #随机的一个点
assert part1=''.join([hex(i)[2:] for i in n])
cipher = [n[i] * P for i in range(3)]
print(f"N = {p}")
print(f"a = {a}, b = {b}")
print(f"P = {P}")
for i in range(3):
print(f"cipher{i} = {cipher[i]}")
# CRT
def part2():
p = 839252355769732556552066312852886325703283133710701931092148932185749211043
a = 166868889451291853349533652847942310373752202024350091562181659031084638450
b = 168504858955716283284333002385667234985259576554000582655928538041193311381
P = E.random_point()
Q = key*P
print("p = ",p)
print("a = ",a)
print("b = ",b)
print("P = ",P)
print("Q = ",Q)
assert part2=key
part1()
print("-------------------------------------------")
part2()
assert flag="flag{"+str(part1)+"-"+str(part2)+"}"
考察的是有关ECC的两种特殊攻击方法
-
part1
攻击的思路是Pohlig-Hellman攻击，要求是曲线的阶有小因数，这里E.order计算出来是512位，丢yafu分解之后发现有7个因子，其中5个比较小，且全部乘起来之后是比要大的，因此我们就可以取小的5个因子来进行攻击，脚本如下
pythonfrom sage.all import * from Crypto.Util.number import * n = 8186762541745429544201163537921168767557829030115874801599552603320381728161178278432652391299286759969365150578265902315058515370390070500719061057476940 print(n.bit_length()) # 2*2*5*11*499*683*124696170958113532210068667*875618937758378886905025632349007870524674918888468835522805095350653442872611049093102429356717528012933133846029979343 # 椭圆曲线参数 p = 8186762541745429544201163537921168767557829030115874801599552603320381728161132002130533050721684554609459754424458805702284922582219134865036743485620797 a = 1495420997701481377470828570661032998514190598989197201754979317255564287604311958150666812378959018880028977121896929545639701195491870774156958755735447 b = 5991466901412408757938889677965118882508317970919705053385317474407117921506012065861844241307270755999163280442524251782766457119443496954015171881396147 E = EllipticCurve(GF(p), [a, b]) # 生成元和密文点 P = E( 6053058761132539206566092359337778642106843252217768817197593657660613775577674830119685211727923302909194735842939382758409841779476679807381619373546323, 7059796954840479182074296506322819844555365317950589431690683736872390418673951275875742138479119268529134101923865062199776716582160225918885119415223226 ) cipher0 = E( 4408587937721811766304285221308758024881057826193901720202053016482471785595442728924925855745045433966244594468163087104593409425316538804577603801023861, 5036207336371623412617556622231677184152618465739959524167001889273208946091746905245078901669335908442289383798546066844566618503786766455892065155724816 ) cipher1 = E( 2656427748146837510897512086140712942840881743356863380855689945832188909581954790770797146584513962618190767634822273749569907212145053676352384889228875, 4010263650619965046904980178893999473955022015118149348183137418914551275841596653682626506158128955577872592363930977349664669161585732323838763793957500 ) cipher2 = E( 1836350123050832793309451054411760401335561429787905037706697802971381859410503854213212757333551949694177845513529651742217132039482986693213175074097638, 1647556471109115097539227566131273446643532340029032358996281388864842086424490493200350147689138143951529796293632149050896423880108194903604646084656434 ) # 已知阶的分解（排除最后两个大因子） primes = [4, 5, 11, 499, 683] # 2^2, 5, 11, 499, 683 def pohlig_hellman(P, Q, primes): dlogs = [] for fac in primes: t = P.order() // fac PP = t * P QQ = t * Q dlog = PP.discrete_log(QQ) # 自动选择最佳算法 dlogs.append(dlog) print(f"Factor: {fac}, Discrete Log: {dlog}") return crt(dlogs, primes) # 计算三个离散对数 print("计算n0:") n0 = pohlig_hellman(P, cipher0, primes) print("\n计算n1:") n1 = pohlig_hellman(P, cipher1, primes) print("\n计算n2:") n2 = pohlig_hellman(P, cipher2, primes) # 验证结果 assert cipher0 == n0 * P assert cipher1 == n1 * P assert cipher2 == n2 * P # 拼接结果 part1 = hex(n0)[2:] + hex(n1)[2:] + hex(n2)[2:] print("\n解密结果:", part1) # f61bd9f152e65ac -
part2
smart攻击，这里曲线计算出来阶和模数相同，脚本如下
pythonfrom sage.all import * from Crypto.Util.number import * from gmpy2 import * p = 839252355769732556552066312852886325703283133710701931092148932185749211043 a = 166868889451291853349533652847942310373752202024350091562181659031084638450 b = 168504858955716283284333002385667234985259576554000582655928538041193311381 E = EllipticCurve(GF(p), [a, b]) r = E.order() # 839252355769732556552066312852886325703283133710701931092148932185749211043 print(r) P = E(547842233959736088159936218561804098153493246314301816190854370687622130932 , 259351987899983557442340376413545600148150183183773375317113786808135411950 ) Q = E(52509027983019069214323702207915994504051708473855890224511139305828303028 , 520507172059483331872189759719244369795616990414416040196069632909579234481 ) def SmartAttack(P,Q,p): E = P.curve() Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ]) P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True) for P_Qp in P_Qps: if GF(p)(P_Qp.xy()[1]) == P.xy()[1]: break Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True) for Q_Qp in Q_Qps: if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]: break p_times_P = p*P_Qp p_times_Q = p*Q_Qp x_P,y_P = p_times_P.xy() x_Q,y_Q = p_times_Q.xy() phi_P = -(x_P/y_P) phi_Q = -(x_Q/y_Q) k = phi_Q/phi_P return ZZ(k) r = SmartAttack(P, Q, p) print(r) # 7895892011flag{f61bd9f152e65ac-7895892011}
*5.logos#
2023赣政杯原题，这里是别的师傅写的博客2023赣政杯 --- Crypto_赣政杯2023-CSDN博客 ↗
还在被sagemath各种环境问题折磨，就暂时不细写了