2023ACTF——Crypto题目复现

2023-11-02

未分类

2.3k 词

EasyRSA

源码：

from secret import flag
from Crypto.Util.number import *


def genKey(nbits, dbits):
    bbits = (nbits // 2 - dbits) // 2

    while True:
        a = getRandomNBitInteger(dbits)
        b = getRandomNBitInteger(bbits)
        c = getRandomNBitInteger(bbits)
        p1 = a * b * c + 1
        if isPrime(p1):
            # print("p1 =", p1)
            break

    while True:
        d = getRandomNBitInteger(dbits)
        p2 = b * c * d + 1
        if isPrime(p2):
            # print("p2 =", p2)
            break

    while True:
        e = getRandomNBitInteger(bbits)
        f = getRandomNBitInteger(bbits)
        q1 = e * d * f + 1
        p3 = a * e * f + 1
        if isPrime(q1) and isPrime(p3):
            # print("p3 =", p3)
            # print("q1 =", q1)
            break

    while True:
        d_ = getRandomNBitInteger(dbits)
        if GCD(a * b * c * d * e * f, d_) != 1:
            continue
        e_ = inverse(d_, a * b * c * d * e * f)
        k1 = (e_ * d_ - 1) // (a * b * c * d * e * f)
        assert e_ * d_ == (a * b * c * d * e * f) * k1 + 1
        q2 = k1 * e * f + 1
        q3 = k1 * b * c + 1
        if isPrime(q2) and isPrime(q3):
            # print("q2 =", q2)
            # print("q3 =", q3)
            # print("e =", e_)
            # print("d =", d_)
            break

    n1 = p1 * q1
    n2 = p2 * q2
    n3 = p3 * q3
    
    assert pow(pow(0xdeadbeef, e_, n1), d_, n1) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n2), d_, n2) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n3), d_, n3) == 0xdeadbeef

    return(e_, n1, n2, n3)


nbits = 0x600
dbits = 0x210

m = bytes_to_long(flag)
e, n1, n2, n3 = genKey(nbits, dbits)
c = pow(m, e, n1)

print("c =", c)
print("e =", e)
print("n1 =", n1)
print("n2 =", n2)
print("n3 =", n3)

# c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644
# e = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227
# n1 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201
# n2 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181
# n3 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421

解法一：

自家解法，还就那个非预期，当时找到了dual RSA，发现生成方式很类似，后来队友找到个破解dual RSA的脚本，调参数梭了20分钟出来的。https://github.com/xalanq/jarvisoj-solutions/blob/master/crypto/%5B61dctf%5Drsa.md

解法二：

目前看到了个格的解法(来自无趣的浅，又是这位大哥)，比较像预期解。

对于题目的分析:

进一步展开有：

再进一步构造：

记上3式等号右结果为A,B,C，即：

分析各个数的大小有：

-1533bit;-1534bit;-528bit;-528bit;

$，，$ -1296(528+768)bit；

有：

实操跑了一下t取都可以，在此情况下，相对于1534位的格基，基本在1296位的向量确实是格上最短。

t下界的相关证明（队友问了L的大哥，说是用高斯启发式）：

忘记咋求行列式了，唐突补习：

转换为比特位即：

$位$

|w|（目标向量长度） $位$

可得若目标向量为格上最短向量，则tbit约位

实测为589，差别不大。

t上界证明暂无。

脚本：

from Crypto.Util.number import *
c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644
e = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227
n1 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201
n2 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181
n3 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421
M = Matrix(ZZ,[[e,e,e,2^768],
               [n1,0,0,0],
               [0,n2,0,0],
               [0,0,n3,0]])
d=abs(M.LLL()[0][3]//2^768)
long_to_bytes(ZZ(pow(c,d,n1)))

MDH

我自己看的时候感觉涉及矩阵交换律的验证的事情，因为太久没用过线性代数甚至都忘记怎么证明了。

总之队友贴了验证跑的代码，有pk_alice.T * pk_bob == sharded。

from Crypto.Util.number import *
r = 128
c = 96
p = 308955606868885551120230861462612873078105583047156930179459717798715109629
Fp = GF(p)
with open('output.txt', 'r') as f:
    ct = Integer(f.readline())
    pk_alice_data = f.readline().strip()
    pk_bob_data = f.readline().strip()
ct = int(ct)
pk_alice = Matrix(Fp,r,r,eval(pk_alice_data))
pk_bob = Matrix(Fp,r,r,eval(pk_bob_data))
shared=(pk_alice.T * pk_bob).trace()
flag = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^^ ct
print(long_to_bytes(flag))

Claw crane

伪随机生成了一个 128bit 的整数 r, 并根据我们的两个小于64bit 的输入 p, q 计算 delta = abs(r\*q - p\*pow(2,BITS))delta中0占比越低，越容易抓到娃娃，一共256次要求222次成功。

解法一：

当时没有细推导，简单尝试了几次之后因为过于非酋分数较低就淘汰掉了，没想到在wp中看到了，十分后悔。

令q=2**63, p为r的高63位。这样最终的 delta 高 63 位和低 63 位均为 0，剩下的 66位有一半为 0，即 0 所占比例 82.8%，比222/256略低，但也差不太多，运气好就行。

记录里翻出来的代码：

from Crypto.Util.number import *

context.log_level = 'debug'

problem = remote('120.46.65.156', 19991)
BITS = 128
import math
for _ in range(256):
    problem.recvuntil(b'[')
    col = int(problem.recvuntil(b',')[:-1])
    row = int(problem.recvuntil(b']')[:-1])
    move = b'D' * col + b'W' * row
    problem.sendlineafter(b'Your moves: ', move)
    problem.recvuntil(b'choas: ')
    choas = int(problem.recvline()[:-1])
    q=2**63
    p=choas//(2**65)
    #t=abs(q*choas-p*2**BITS)
    p=str(p).encode()
    q=str(q).encode()
    problem.sendlineafter(b"give me your claw using p,q and p,q in [0, 18446744073709551615] (e.g.: 1,1): ",q+b','+p)

problem.recvline()
problem.recvline()
problem.interactive()

解法二：

构造

LLL算法求出最短向量后解XA=B

核心代码（参考：https://blog.csdn.net/shshss64/article/details/134169323）：

def solve_pq(chaos):
    K = matrix(ZZ, [[2 ^ 128, 0], [chaos, 1]])
    KK = K.LLL()
    v = K.solve_left(KK[0])
    p, q = v[0], v[1]
    return abs(p), abs(q)

midRSA

源码：

from secret import flag
from Crypto.Util.number import *


def genKey(nbits, dbits):
    bbits = (nbits // 2 - dbits) // 2

    while True:
        a = getRandomNBitInteger(dbits)
        b = getRandomNBitInteger(bbits)
        c = getRandomNBitInteger(bbits)
        p1 = a * b * c + 1
        if isPrime(p1):
            # print("p1 =", p1)
            break

    while True:
        d = getRandomNBitInteger(dbits)
        p2 = b * c * d + 1
        if isPrime(p2):
            # print("p2 =", p2)
            break

    while True:
        e = getRandomNBitInteger(bbits)
        f = getRandomNBitInteger(bbits)
        q1 = e * d * f + 1
        p3 = a * e * f + 1
        if isPrime(q1) and isPrime(p3):
            # print("p3 =", p3)
            # print("q1 =", q1)
            break

    while True:
        d_ = getRandomNBitInteger(dbits)
        if GCD(a * b * c * d * e * f, d_) != 1:
            continue
        e_ = inverse(d_, a * b * c * d * e * f)
        k1 = (e_ * d_ - 1) // (a * b * c * d * e * f)
        assert e_ * d_ == (a * b * c * d * e * f) * k1 + 1
        q2 = k1 * e * f + 1
        q3 = k1 * b * c + 1
        if isPrime(q2) and isPrime(q3):
            # print("q2 =", q2)
            # print("q3 =", q3)
            # print("e =", e_)
            print("d =", d_)
            break

    n1 = p1 * q1
    n2 = p2 * q2
    n3 = p3 * q3
    
    assert pow(pow(0xdeadbeef, e_, n1), d_, n1) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n2), d_, n2) == 0xdeadbeef
    assert pow(pow(0xdeadbeef, e_, n3), d_, n3) == 0xdeadbeef

    return(e_, n1, n2, n3)


nbits = 0x600
dbits = 0x240

m = bytes_to_long(flag)
e, n1, n2, n3 = genKey(nbits, dbits)
c = pow(m, e, n1)

print("c =", c)
print("e =", e)
print("n1 =", n1)
print("n2 =", n2)
print("n3 =", n3)


# c = 598823083137858565473505718525815255620672892612784824187302545127574115000325539999824374357957135208478070797113625659118825530731575573239221853507638809719397849963861367352055486212696958923800593172417262351719477530809870735637329898331854130533160020420263724619225174940214193740379571953951059401685115164634005411478583529751890781498407518739069969017597521632392997743956791839564573371955246955738575593780508817401390102856295102225132502636316844
# e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
# n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
# n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
# n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451

分析：

调整dbits = 0x240，使得原本easyRSA的脚本无论如何调整t的大小都无法获得结果。

同样的等式

各个数的大小有

-1534bit;-1534bit;-576bit;-576bit;

$，，$ -1344(576+768)bit；

复现的时候对于卡了t的界的问题自己提了个比较粗浅地推导==：

对于easyRSA里的这个格，同样利用高斯启发式考虑。

期望最短向量长度为,转换为比特位即：

$位$

|w| $位$

为满足需求有 $位$

但此时再次计算目标向量中的D*t，可以发现其位数为，即此时目标向量长度改变，tbit不再能满足需求，也就推出矛盾了。

时间线稍后，队友复盘提到了格攻击之小未知数方程求解入门——原理与例子 | Tover’ Blog，里面提到了配平技巧。

文章的大致意思指，一般情况下先配平，再去考虑高斯启发式，否则格可能会无法满足需求，配平即使目标向量中各个数的大小平衡。

对于midRSA这个题而言，就是令tbit=768，有|w|=1344

此时可求得α(L)=1342.5<1344不满足要求，这样就可以看到所谓的卡界了。

总而言之，以上是对于卡界的解释，接下来是解题部分。

解法一：

通过爆破部分位并构造新格来解决问题。

当我们爆破时，构造

令（错误警告）

则α(L)=1342.8变化不大，而|w|≈1345，依旧不满足条件。

//队友提醒上面格应该可以

这里重新推导，在令的部分应

此时重新计算

得为满足需求应有

因为算的比较粗略，需求可能要更大才能爆破出来，比如一起复现的队友算出来要爆破16位。

实测结果是10位

然后爆高位和低位没有影响，无非爆高位可以少爆一位

这里贴个改自队友爆高位的脚本：

from Crypto.Util.number import long_to_bytes
from tqdm import tqdm
c = 598823083137858565473505718525815255620672892612784824187302545127574115000325539999824374357957135208478070797113625659118825530731575573239221853507638809719397849963861367352055486212696958923800593172417262351719477530809870735637329898331854130533160020420263724619225174940214193740379571953951059401685115164634005411478583529751890781498407518739069969017597521632392997743956791839564573371955246955738575593780508817401390102856295102225132502636316844
e = 334726528702628887205076146544909357751287869200972341824248480332256143541098971600873722567713812425364296038771650383962046800505086167635487091757206238206029361844181642521606953049529231154613145553220809927001722518303114599682529196697410089598230645579658906203453435640824934159645602447676974027474924465177723434855318446073578465621382859962701578350462059764095163424218813852195709023435581237538699769359084386399099644884006684995755938605201771
n1 = 621786427956510577894657745225233425730501124908354697121702414978035232119311662357181409283130180887720760732555757426221953950475736078765267856308595870951635246720750862259255389006679454647170476427262240270915881126875224574474706572728931213060252787326765271752969318854360970801540289807965575654629288558728966771231501959974533484678236051025940684114262451777094234017210230731492336480895879764397821363102224085859281971513276968559080593778873231
n2 = 335133378611627373902246132362791381335635839627660359611198202073307340179794138179041524058800936207811546752188713855950891460382258433727589232119735602364790267515558352318957355100518427499530387075144776790492766973547088838586041648900788325902589777445641895775357091753360428198189998860317775077739054298868885308909495601041757108114540069950359802851809227248145281594107487276003206931533768902437356652676341735882783415106786497390475670647453821
n3 = 220290953009399899705676642623181513318918775662713704923101352853965768389363281894663344270979715555659079125651553079702318700200824118622766698792556506368153467944348604006011828780474050012010677204862020009069971864222175380878120025727369117819196954091417740367068284457817961773989542151049465711430065838517386380261817772422927774945414543880659243592749932727798690742051285364898081188510009069286094647222933710799481899960520270189522155672272451
dbit=9
tbit=1344-576+dbit+1
for Dh in tqdm(range(2^dbit)):
    Dh = int('1' + bin(Dh)[2:].zfill(dbit), 2) << (576-dbit-1)
    M = Matrix(ZZ,[[e, e, e, 2^tbit, 0],
                [n1, 0, 0, 0, 0],
                [0, n2, 0, 0, 0],
                [0, 0, n3, 0, 0],
                [e*Dh, e*Dh, e*Dh, 0, 2^1344]
                ])
    res = M.LLL()
    for i in res:
        if abs(i[-1])==2^1344:
            d = int(i[3]//2^tbit) + Dh
            flag = long_to_bytes(int(pow(c,d,n1)))
            if b'ACTF{' in flag:
                print(flag)
                break

解法二：

在解法一的错误计算中产生的想法（虽然不知道原博主是不是这样）

总之，为减小|w|，进而想到爆破ABC的部分位.

此时通过调整 $，$ 来调整

令，

则有,

则

满足需求

因为计算比较粗略，具体取值需要结合实际调试一下，不过这么算出来和博主（见参考资料第一条）的结果似乎是一样的，非常好。

博主写了个爆破高位的，优势是可以少爆一位，具体代码就不贴了。

接下来是个队友要求的优雅点的爆破低位代码。

CRCRC

参考资料

ACTF2023 Cypto-CSDN博客

2023 ACTF SU Write Up (qq.com)

微信公众平台 (qq.com)

ACTF 2023 Writeup By 0RAYS (qq.com)

格攻击之小未知数方程求解入门——原理与例子 | Tover’ Blog

[ACTF2023]复现-CSDN博客

标签

归档

最新文章

2023ACTF——Crypto题目复现

EasyRSA

源码：

解法一：

解法二：

t下界的相关证明（队友问了L的大哥，说是用高斯启发式）：

MDH

Claw crane

解法一：

解法二：

midRSA

源码：

解法一：

解法二：

CRCRC

参考资料