menu badmonkey's blog
more_vert
chevron_right 首页 » CTF,Crypto » 正文
2020安恒六月赛crypto部分wp
2020-06-26 | CTF,Crypto | 暂无评论 | 614 次阅读 | 502字

DASCTF 2020 六月团体赛

crypto

Gemini_Man

最狗血的一道题,感觉不是很好。。。

from gmpy2 import *
n='*******'
c='*******'
p = iroot(n,2)[0]
q=p+2
print(p*q == n)
phi = (p-1)*(q-1)
e = 65537

print("d.....")
d = invert(e,phi)
print("m.....")

m = int(powmod(c,d,n))
print("flag....")
flag = bytes.fromhex(hex(m).strip("0xL"))
print(flag)
# b'Nep{e540b1fd7d4459619eecd244c12ae5c4}'

HardKnapsack1

常规的背包,直接LLL就出了,背包密度为0.8左右。这里直接上脚本:

from hashlib import *
from sage.all import *
a = [780007910488861179164293870887, 644757781267431438527370588084, 886344987910700007796700699622, 67037192443258799119898868140, 315956500273241342245431683326, 351211073412604835884630475291, 335995606663513190145190482978, 297359033781432237886700807123, 830856741522978372146275766502, 66237663505632806581378309121, 215381734735218549313962033405, 901490788983193928886516147592, 499548714837069155558450537001, 224630055332830997824601426897, 919172894051797483753355195026, 1245440331898780823251731300504, 298263995223321209902868895182, 736591430769582414355553278342, 1217976030016671115168136964102, 980399099884318297365025522271, 726084355132965753252062504988, 951277826840378766945561669930, 7492442200302555390486229208, 769018513342604618159516970070, 968152198590814209754881322238, 1175154665753017160833066426121, 451952196471082603080565175017, 1221094023689255701171287330816, 617456087916724185254283878151, 226112898226641715564773252737, 494810212661607333752928148148, 1244821663551343141356670958981, 679214190369761834097630749359, 745058412645059179660418453044, 1178229830813633913730449092984, 145802775498878544007250617349, 1120246265160574187528207432153, 879947206559082641568587869322, 694829766294593284811782637743, 27254432667363032997310672464, 659494232598071549477042457760, 246528894190618505904569471972, 678865008088637501445062252585, 338808883115188328216917974008]
s = 7435339872422467409289909942435
def decrypt(enc,publickey):
    # 维数
    n = len(publickey)
    # 构造格
    d = 2*identity_matrix(ZZ,n,n)
    col = publickey+[enc]
    col = matrix(col).transpose()
    last = matrix(ZZ,[[1]*n])
    tmp = block_matrix(ZZ,[[d],[last]])
    grid = block_matrix(ZZ,[[tmp,col]])
    # 格基规约 使用LLL算法,找到最短向量
    M = grid.LLL()
    # 利用最短向量还原信息,注意又两种可能,这里仅考虑第一种,reverse 函数将当前结果转换为第二种可能
    m = ''
    for i in M[0]:
        if i== -1:
#             m += '0'
            m += '1'
        elif i == 1:
#             m += '1'
            m += '0'
    return m

m = decrypt(s,a)
# m = '01100101000000000100010010000010000100100111'
flag = md5(m.encode()).hexdigest()
print(flag)
# a5c7fcd8423c696562ae7a2ce302cb15

HardKnapsack2

感觉很像今年大学生密码竞赛的第三题,后来听V神说是原题连数据都一样。(懒狗实锤了。于是捡起看到一半的论文开始啃。

Knapsack系统的密度为$d = \frac{n}{log_2(max\{a_i\})}$

基于子集和问题,最开始出现的是一种密度比较低的Knapsack密码系统(MH密码系统),很快shamir等人提出了一系列的攻击方式,包括丢番图逼近,LLL等方法。虽然这个密码系统被攻破了,但是由于密码学家们很喜欢这种小巧的系统??,新的Knapsack系统诞生了,这种密码系统的密度变高了,$a_i$值变小了。而且加密的明文的二进制位中1的数量也很小。

haiming weight :加密的明文的二进制位中1的数量

新的密码系统更加难以破解,也称之为HardKnapsack系统,不过后来密码学家们还是发现了攻击方法,我们称之为low-weight attack。

Schroeppel-Shamir Algorithm

时间复杂度,空间复杂度均为$O(n/2)$

The Howgrave-Graham–Joux Algorithm

时间复杂度$O(0.337n)$,空间复杂度$O(0.256n)$

原论文比较难,笔者也只是理解了一部分,欢迎各位师傅指点。

总体来说,这两种算法是基于分治和mitm的思想进行攻击的。参考论文Improved Generic Algorithms for Hard Knapsacks

非预期解

我们知道m中有12个1,其中左右两边各6个1的概率约为0.24。幸运的是此题恰好满足此条件,于是可以爆破左右两边的所有可能情况,利用mitm攻击还原m。exp如下:

#!/usr/bin/python3
# @Time    : 2020-06-26 13:53:47
# @Author  : badmonkey
# @FileName: exp.py
# @Software: PyCharm

from hashlib import md5

a=[132512289947606266688, 2414795396463926269118, 4431032274086306311038, 438409060232570923534, 4081842379559820847930, 3692926635897108774236, 2321233718723287079203, 2906518304492591303432, 16329871656862994748, 955444090786656773324, 3899236180323276022119, 3007518555157518129362, 199825369329115989579, 1892203519839647552731, 1663367093510654645615, 2818239607219638890476, 1609653993011886150031, 876177649679238314392, 64638488345439455658, 702091777537314818127, 2924135376313926286260, 1513945888509335587618, 945145651183067313209, 3980711473391297194399, 532587388734221515102, 850082115913851677926, 1341869583757324217413, 3907913016252282691693, 1659084558674822543062, 3146940273421315888497, 447678727192767667534, 3073661656530784633718, 1412209678918380868590, 3768627013375110863559, 4260476107811246443867, 569430811137646528556, 534304982838037694029, 171539063676303640233, 876380098043872683778, 1379079964748964855735, 4502263359279147194141, 3871467895851428124873, 1874045705839170731546, 4078014252760893322853, 2417284838875457207038, 3909477741902431070824, 2987652175894271732201, 1848744068276145862519, 2724985743527003977076, 2070852918438712853532, 1285272495716088648507, 2674287484603241609950, 4138133212901657663775, 710058052066041315713, 2777863325085117868077, 2010235840999174953954, 4570873502224619249353, 2819009959943938633903, 1517003993374574562683, 805800309809619272650, 459286691389244854557, 4179050550215838827249, 1255285121486530023485, 1118525043806432513453, 3859455943156125426205, 89289626203320452817, 4643684829186959131820, 226322390044812305284, 3059305091059169430907, 2121289926471736948693, 1940197436140021987593, 350197708619902358746, 3922342070491939933106, 4245282549916363769747, 2706993416933981315294, 4387316124919887443598, 1166190476683313167410, 4647377080883871673239, 2417285158341492119434, 3496941124891656512050]
s = 30611285231583357754266

# 解决子背包问题
def findC(a,c):
    for i in range(40):
        for j in range(i+1,40):
            for k in range(j+1,40):
                for m in range(k+1,40):
                    for n in range(m+1,40):
                        for o in range(n+1,40):
                            if a[i]+a[j]+a[k]+a[m]+a[n]+a[o] == c:
                                tmp = (i,j,k,m,n,o)
                                print(tmp)
                                return tmp
    return 0

# 收集所有可能解
def collectValue(a):
    res = []
    for i in range(40):
        for j in range(i+1,40):
            for k in range(j+1,40):
                for m in range(k+1,40):
                    for n in range(m+1,40):
                        for o in range(n+1,40):
                            if a[i]+a[j]+a[k]+a[m]+a[n]+a[o] < s:
                                tmp = (i,j,k,m,n,o,a[i]+a[j]+a[k]+a[m]+a[n]+a[o])
                                res.append(tmp[-1])
    return res


def findSolution(a,c):
    La = collectValue(a[:40])
    La.sort()
    print("Left Part done possible numbers %d"%len(La))
    Lb = collectValue(a[40:])
    Lb.sort()
    print("Right part done possible numbers %d"%len(Lb))
    i = 0
    j = len(Lb)-1
    while i<len(La) and j>=0:
        tot = La[i]+Lb[j]
        if tot<c:
            i+=1
        elif tot>c:
            j -= 1
        else:
            tmp = (La[i],Lb[j])
            print("Left subset sum is %d "%La[i])
            print("Right subset sum is %d "%Lb[j])
            return tmp
    print("no solution return (0,0)")
    return (0,0)

solution = findSolution(a,s)
print(solution)


L = findC(a[:40],solution[0])
R = findC(a[40:],solution[1])

def connect(L,R):
    res = ['0']*80
    for i in L:
        res[i] = '1'
    for i in R:
        res[i+40] = '1'
    return res
m = connect(L,R)

message = ''.join(m)
# message = '00000000001001000000001001000100000000010001000100000001000000000000000000000111'

flag = md5(message.encode()).hexdigest()
print(flag)
# fb3a16cf748160f232b839b40a8eb029

预期解

待补充,求大师傅指点

None
发表评论
暂无评论
textsms
account_circle
email
link
arrow_back 上一篇
arrow_forward 下一篇