新生赛wp

1.ezfactor

N为1024bit，几乎不可能直接分解，一定有其他信息泄露或者参数生成不当

1	q = next_prime(p)

注意到q是p的下一个素数，所以q十分接近p

根据这个有很多思路，

解法1.直接枚举素数

我们发现q>p

那么 \[ p^2 < N <q^2 \\ p < \sqrt{N} < q \]

p，q既然是相邻素数，那么，中间隔得数应该是比较少的，于是我们直接枚举$\sqrt{N}$之后的素数就行了

exp：

from Crypto.Util.number import *
import gmpy2
N=76054928615390642027267557721898606104435347689858137357839292028005606199646260254335983379549076728600128701160658648775791285669662746597218527060446604461201763384425245933884293633398664617814840172770170474161815207215980122891433996225544102325164066480808143986384191942898062253112909454093416472009
c=62062456777910256575514210934984740421121264105858854882925023869828419630803830871607829312998780773576941511717725735799343767638696056960219462684570499043418495771755735700746113071057918634489911794403743980485105589796802402638825739840675064980625622577129872334550019181602368250342431549928922419379
temp = gmpy2.iroot(N,2)[0] #或者用其他库/自己写的算法开根都行
q = gmpy2.next_prime(temp)
while(N%q != 0):
    q = gmpy2.next_prime(q) #直到q整除N,即N除以q的余数为0
p = N // q
phi = (p-1)*(q-1)
e= 65537
d = inverse(e,phi)
m = pow(c,d,N)
print(long_to_bytes(m))
#运行时间为：0.8010999990801793毫秒

由于素数定理 \[ \pi(x) \sim \frac{x}{\ln x} \\ \frac{x}{\pi(x)}\sim \ln(x) \\ \pi(x) 是不大于x的素数个数 \] 所以数量级为2的512次方的素数平均间距接近512ln2 也就是354左右

因此间距不是很大，上面的exp可以在很短的时间内跑出来，实际上这里p和q的间距只有8

解法2.费马分解

实际上寻找下一个素数是比较耗时的，我们可以不枚举素数

更快的方法是利用均值不等式 \[ p+q \geq 2\sqrt{pq}= 2\sqrt{N} \\ 当p接近q时，\frac{p+q}{2}非常接近\sqrt{N},略大于\sqrt{N} \\ \frac{(p+q)^2}{4} - N = \frac{(p-q)^2}{4}\\ \frac{p+q}{2}减去N是一个平方数，我们以\frac{p+q}{2}=[\sqrt{N}]作为起点，不断加1，直到差为完全平方数，就能求出\frac{p+q}{2} \\ 然后差开根号就是\frac{p-q}{2}\\ p=\frac{p+q}{2}+\frac{p-q}{2},q=\frac{p+q}{2}-\frac{p-q}{2} \]

temp = gmpy2.iroot(N,2)[0] #sqrt(N)
while(1):
    if(gmpy2.is_square(temp*temp - N)):  
        x = temp 
        y = gmpy2.iroot(temp*temp-N,2)[0]
        p = x+y
        q = x-y
        break
    else:
        temp+=1
#运行时间为：0.06690000009257346毫秒

2.ezbag

(实际上是一道算法题)

背包密码，利用的是子集和问题的困难性 \[ 给定一个正整数集合 (M_1,M_2,..M_n) 以及整数S \\ 求子集的和使得 S = \sum_{i=1}^nx_iM_i ,其中x\in\{0,1\} \] 显然直接求解的时间复杂度是$O(2^{n})$

即使使用MIMT攻击，也只能降到$O(2^{\frac{n}{2}})$

这道题中n=232,直接枚举攻击是几乎不可能

但如果定义在超级递增序列上，也就是满足 $$ M_{i+1} 2M_i,1i n-1

的序列，那么有\

M_{i+1} -M_i M_i\

左边是一个跌进，求和得到\

M_{i+1}-M_1 _{i=1}^nM_i

于是有\

M_{k} > _{i=1}^{k-1}M_i \那这个性质就可以帮助解决背包问题了\ 从M_n开始枚举 S>M_n,说明S里肯定有M_n,否则前面的和肯定小于M_n,然后扣掉M_n，继续往下 $$ 小于自然就是没有了

这样的背包密码很容易被破解，因此后来有了Merkle–Hellman加密方案 \[ 给一个超递增序列\{a_n\}，我们用一个私钥w来混淆 \\ b_n \equiv wa_n \mod p \\当w比较大的时候，由于取模，就会破坏原来的超递增序列，从而抵抗了贪心算法的攻击 \] 但是，这道题

def keygen(nbits):
    a = [randint(2**160, 2**200)]
    for x in range(nbits-1):
        a.append(randint(2*a[-1], 3*a[-1]))
    p = getPrime(1024)
    w = getPrime(30)
    b = [i*w % p for i in a]
    sk = [w]
    pk = [b,p]
    return sk,pk

w乘以a充其量是2的230次方，不可能超过p，因此b仍然是超递增序列，于是用贪心算法破解

def decrypt_attack(pk,c):
    b,p = pk
    m = ''
    for i in range(len(b)-1,-1,-1):
        if c >= b[i]: #大于说明背包里有，为1
            c-= b[i]
            m = "1" + m 
        else: #背包里没有
            m = "0" + m
    m = int(m,2)
    return long_to_bytes(m)
m = decrypt_attack(pk,c)
print(m)

注：这道题里，被加密的是m的二进制位，即将m转为01序列，和前面的x对应

且本题的w是可以求出来的，求出w还原a，再用贪心算法也可以

exp：

from functools import reduce
from Crypto.Util.number import *
b,p = pk
w = reduce(GCD,b)
a = [ bi*inverse(w,p) % p for bi in b]
m = ''
c = c*inverse(w,p) % p
for i in range(len(a)-1,-1,-1):
    if c >= a[i]:
        c-= a[i]
        m = "1" + m
    else:
        m = "0" + m
m = int(m,2)
print(long_to_bytes(m))

5.ez_bag_revenge

def encrypt(m,bags,module) -> int:
    m = bin(m)[2:].rjust(624, "0")
    res = 0
    for i in range(len(m)):
        res += bags[i] * int(m[i])  
    return res % module

相比ez_bag，多了个模运算，而且这个模就是我们要求的，然后bags也不知道，只能进行加密操作

预期

交互没有限制，可以选择明文攻击

求模常见的思路是利用同余定义,不妨设模为q \[ a\equiv b \mod q \\ c \equiv d \mod q \\ a-b =k_1q,c-d=k_2q \\ 如果(k_1,k_2)=1，那么q=(a-b,c-d)(最大公因数) \] 我们可以控制明文，所以找到几对同余的数就行了，我们记加密函数为E(x)

那么

如果m1，m2中1的位置不同，也就是说m1和m2用的背包不同，那m1和m2加起来，用的背包和分别用背包再合起来是一样的 \[ E(m_1)+E(m_2) \equiv E(m_1+ m_2) \mod q \] 多构造几个，要保证k不等于0 \[ E(m_1)+E(m_2) - E(m_1+m_2) = k_1q \\ E(m_3)+E(m_4) - E(m_3+m_4) = k_2q \\ \] 只要我们构造的够多，总有k1，k2是互素的，那么就求出了q

预期的构造方式是，预设一个 \[ m_1+m_2=11111111111111111111...(624个1)=2^{624}-1 \] 然后让m1从1开始增加，这样我们能构造非常多的m1，m2，确保能求出公因数

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from functools import *
p = remote("10.102.32.141",40286)
p.recvuntil(b"Input > ")
m = [i for i in range(100)]
p.send(str(2**624-1).encode())
p.recvuntil(b"= ")
cij = int(p.recvline().strip().decode())
kq = []
for i in trange(len(m)):
    p.send(str(i).encode())
    p.recvuntil(b"= ")
    ci = int(p.recvline().strip().decode())
    p.send(str(2**624-1-i).encode())
    p.recvuntil(b"= ")
    cj = int(p.recvline().strip().decode())
    if ci+cj-cij != 0:
        kq.append(ci+cj-cij)
mod = reduce(GCD,kq)
print(mod)
p.interactive()

非预期

由于出题的时候没充分考虑，模设的太小了，原意是想着需要用pwntools交互，但是这里手测几个构造就行了