CB backpack

源码：

from random import shuffle

def gen_e():
    e = []
    for i in range(8):
        ee = [0]*3+[1]*3
        shuffle(ee)
        e += ee
    return e
    
e = gen_e()
nbit = len(e)
flag = 'DASCTF{'+sha256(''.join([str(i) for i in e]).encode()).hexdigest()+'}'

a = [randint(1,2^nbit) for i in range(nbit)]

re = 0
for i in range(nbit):
    re += e[i]*a[i]

print(a)
print(re)

很明显这是一个背包问题，但是跟普通的背包又不一样，这里就要提到Schroeppel_Shamir算法。Schroeppel_Shamir的算法是解决背包问题的一个经典方法，它主要利用生日悖论和排序来降低时间复杂度。

Schroeppel_Shamir算法基本步骤：

将背包问题划分为两个较小的子问题。
解决两个子问题以得到所有可能的部分和。
使用排序和二分查找技术找到合适的部分和，使其总和满足背包问题的目标。

则按照上述的方式即可求解$e$。

exp

这边就写一个求e的过程，大概1分多钟就能跑出来。

import time

def schroeppel_shamir_solution(weights, target):
    n = len(weights)

    half_n = n // 2
    A, B = weights[:half_n], weights[half_n:]

    def generate_partial_sums(subset):
        sums = {0: []}
        for weight in subset:
            new_sums = {}
            for s, combination in sums.items():
                new_sum = s + weight
                new_combination = combination + [weight]
                if new_sum not in sums:
                    new_sums[new_sum] = new_combination
            sums.update(new_sums)
        return sums

    partial_sums_A = generate_partial_sums(A)
    partial_sums_B = generate_partial_sums(B)

    keys_A = sorted(list(partial_sums_A.keys()))
    keys_B = sorted(list(partial_sums_B.keys()))

    i, j = 0, len(keys_B) - 1
    while i < len(keys_A) and j >= 0:
        current_sum = keys_A[i] + keys_B[j]
        if current_sum == target:
            return partial_sums_A[keys_A[i]] + partial_sums_B[keys_B[j]]
        elif current_sum < target:
            i += 1
        else:
            j -= 1

    return []

start_time=time.time()

weights=[65651991706497, 247831871690373, 120247087605020, 236854536567393, 38795708921144, 256334857906663, 120089773523233, 165349388120302, 123968326805899, 79638234559694, 259559389823590, 256776519514651, 107733244474073, 216508566448440, 39327578905012, 118682486932022, 263357223061004, 132872609024098, 44605761726563, 24908360451602, 237906955893793, 204469770496199, 7055254513808, 221802659519968, 169686619990988, 23128789035141, 208847144870760, 272339624469135, 269511404473473, 112830627321371, 73203551744776, 42843503010671, 118193938825623, 49625220390324, 230439888723036, 241486656550572, 107149406378865, 233503862264755, 269502011971514, 181805192674559, 152612003195556, 184127512098087, 165959151027513, 188723045133473, 241615906682300, 216101484550038, 81190147709444, 124498742419309]
target=4051501228761632

solution = schroeppel_shamir_solution(weights, target)
print(solution)
ee=[0]*48
for i in range(48):
    if weights[i] in solution:
        ee[i]=1
print(ee)
end_time=time.time()
print(end_time-start_time)

EzRSA

源码

from Crypto.Util.number import *
import random
from gmpy2 import *
from libnum import *
from flag import flag

def padding(f):
    random_chars = bytes([random.randint(0, 255) for _ in range(32)])
    f = f + random_chars
    return f

def guess_p(p):
    e = 65537
    
    P = p
    n1 = getPrime(512)*getPrime(512)
    with open('enc.txt', 'w+') as f:
        while jacobi(2,n1) == 1:
            n1 = getPrime(512)*getPrime(512)
        while P:
            pad = random.randint(0, 2**2023)**2 
            message = pad << 1 + P % 2
            cipher = pow(message, e, n1)
            f.write(str(cipher)+'n')
            P //= 2
    print("n1 = "+ str(n1) )    
    
def guess_q(q):
    
    def encrypt(q, n):
        e = random.randint(1000,2000)
        noise = random.randint(0, n - 1)
        c = pow(q+noise,e,n)
        return e, noise,c 
    
    n2 = getPrime(512)*getPrime(512)
    e1, noise1, c1 = encrypt(q, n2)
    e2, noise2, c2 = encrypt(q, n2)
    print("n2 = "+ str(n2) ) 
    print('(e1, noise1, c1) =', (e1,noise1,c1))
    print('(e2, noise2, c2) =', (e2,noise2,c2))
p = getPrime(512)
q = getPrime(512)

n = p*q
guess_p(p)
guess_q(q)
e = 0x10001
flag = padding(flag)
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c = " + str(c))
'''
n1 = 65634094430927080732256164808833233563732628654160389042977689628512527168256899310662239009610512772020503283842588142453533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554634493581962527475555869292091755676130810562421465063412235309
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802940810851806104430306195931179902098180199167945649526235613636163362672777298968943319216325949503045377100235181706964846408396946496139224344270391027205106691880999410424150216806861393
(e1, noise1, c1) = (1743, 44560588075773853612820227436439937514195680734214431948441190347878274184937952381785302837541202705212687700521129385632776241537669208088777729355349833215443048466316517110778502508209433792603420158786772339233397583637570006255153020675167597396958251208681121668808253767520416175569161674463861719776, 65643009354198075182587766550521107063140340983433852821580802983736094225036497335607400197479623208915379722646955329855681601551282788854644359967909570360251550766970054185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853621152905983)
(e2, noise2, c2) = (1325, 35282006599813744140721262875292395887558561517759721467291789696459426702600397172655624765281531167221787036009507833425145071265739486735993631460189629709591456017092661028839951392247601628468621576100035700437892164435424035004463142959219067199451575338270613300215815894328788753564798153516122567683, 50327632090778183759544755226710110702046850880299488259739672542025916422119065179822210884622225945376465802069464782311211031263046593145733701591371950349735709553105217501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773715759733714)
c = 124349762993424531697403299350944207725577290992189948388824124986066269514204313888980321088629462472088631052329128042837153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177197863522573410860341245613331398610013697803459403446614221369
'''

都是考过的知识点，雅可比符号还有RSA的Franklin攻击。前者的知识点具体可参考N1CTF2019这篇文章，讲的非常详细，后者可移步到我之前写的Franklin攻击。

exp

from Crypto.Util.number import *
from gmpy2 import *

def pdivmod(u, v):
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    x = u.parent().gen()
    if u.degree() < v.degree():
        u, v = v, u
    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])
    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)
    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)
    g0 = e // x^(m//2)
    g1 = f // x^(m//2)
    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    if u.degree() < v.degree():
        u, v = v, u
    if v == 0:
        return u
    if u % v == 0:
        return v
    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u
    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1
    return pgcd(b1, r)

(e1, noise1, c1) = (1743, 44560588075773853612820227436439937514195680734214431948441190347878274184937952381785302837541202705212687700521129385632776241537669208088777729355349833215443048466316517110778502508209433792603420158786772339233397583637570006255153020675167597396958251208681121668808253767520416175569161674463861719776, 65643009354198075182587766550521107063140340983433852821580802983736094225036497335607400197479623208915379722646955329855681601551282788854644359967909570360251550766970054185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853621152905983)
(e2, noise2, c2) = (1325, 35282006599813744140721262875292395887558561517759721467291789696459426702600397172655624765281531167221787036009507833425145071265739486735993631460189629709591456017092661028839951392247601628468621576100035700437892164435424035004463142959219067199451575338270613300215815894328788753564798153516122567683, 50327632090778183759544755226710110702046850880299488259739672542025916422119065179822210884622225945376465802069464782311211031263046593145733701591371950349735709553105217501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773715759733714)
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802940810851806104430306195931179902098180199167945649526235613636163362672777298968943319216325949503045377100235181706964846408396946496139224344270391027205106691880999410424150216806861393
PR.<q> = PolynomialRing(Zmod(n2))
g1=(q+noise1)**e1-c1
g2=(q+noise2)**e2-c2
r=pgcd(g1, g2)
q=int(-r.monic().constant_coefficient())


n1 = 65634094430927080732256164808833233563732628654160389042977689628512527168256899310662239009610512772020503283842588142453533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554634493581962527475555869292091755676130810562421465063412235309
data=open('enc.txt','r').read().split('n')[:-1]
cipher = [int(i,0) for i in data]

p = ""
for i in cipher:
    if jacobi(i,n1)==-1:
        p += '0'
    else:
        p += '1'
p=int(p[::-1],2)

phi=(p-1)*(q-1)
c = 124349762993424531697403299350944207725577290992189948388824124986066269514204313888980321088629462472088631052329128042837153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177197863522573410860341245613331398610013697803459403446614221369
m=pow(c,int(inverse_mod(65537,phi)),p*q)
print(long_to_bytes(int(m)))

还有两题下次补上，最近太忙了...