LOADING

加载过慢请开启缓存 浏览器默认开启

题目杂记

2024/11/28

之前打过的比赛一直没更，有些懒，这次全更了。
ps：星盟安全团队密码招新

巅峰极客-Crypto

task.py

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

def inverse_mod(a, m):
    if a == 0:
        return 0
    return gmpy2.powmod(a, -1, m)

def bit_length(x):
    return x.bit_length()

def get_malicious_key():
    a = getRandomNBitInteger(20)
    b = getRandomNBitInteger(21)
    w = getRandomNBitInteger(30)
    X = getRandomNBitInteger(25)
    return a, b, w, X

class RSZeroError(RuntimeError):
    pass


class InvalidPointError(RuntimeError):
    pass


class Signature(object):
    """ECDSA signature."""

    def __init__(self, r, s):
        self.r = r
        self.s = s


class Public_key(object):
    """Public key for ECDSA."""

    def __init__(self, generator, point, verify=True):

        self.curve = generator.curve()
        self.generator = generator
        self.point = point
        n = generator.order()
        p = self.curve.p()
        if not (0 <= point.x() < p) or not (0 <= point.y() < p):
            raise InvalidPointError(
                "The public point has x or y out of range."
            )
        if verify and not self.curve.contains_point(point.x(), point.y()):
            raise InvalidPointError("Point does not lay on the curve")
        if not n:
            raise InvalidPointError("Generator point must have order.")

        if (
            verify
            and self.curve.cofactor() != 1
            and not n * point == ellipticcurve.INFINITY
        ):
            raise InvalidPointError("Generator point order is bad.")


class Private_key(object):
    """Private key for ECDSA."""

    def __init__(self, public_key, secret_multiplier):

        self.public_key = public_key
        self.secret_multiplier = secret_multiplier

    def sign(self, hash, random_k):

        G = self.public_key.generator
        n = G.order()
        k = random_k % n
        p1 = k * G
        r = p1.x() % n
        if r == 0:
            raise RSZeroError("amazingly unlucky random number r")
        s = (
            inverse_mod(k, n)
            * (hash + (self.secret_multiplier * r) % n)
        ) % n
        if s == 0:
            raise RSZeroError("amazingly unlucky random number s")
        return Signature(r, s)

    def malicious_sign(self,hash, random_k, a, b, w, X):
        # t = random.randint(0,1)
        t = 1
        G = self.public_key.generator
        Y = X * G
        n = G.order()
        k1 = random_k
        z = (k1 - w * t) * G + (-a * k1 - b) * Y
        zx = z.x() % n
        k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
        #print(f'k2 = {k2}')
        p1 = k2 * G
        r = p1.x() % n
        if r == 0:
            raise RSZeroError("amazingly unlucky random number r")
        s = (
                    inverse_mod(k2, n)
                    * (hash + (self.secret_multiplier * r) % n)
            ) % n
        if s == 0:
            raise RSZeroError("amazingly unlucky random number s")
        return (Signature(r, s),k2)

if __name__ == '__main__':
    a,b,w,X = get_malicious_key()

    message1 = b'It sounds as though you were lamenting,'
    message2 = b'a butterfly cooing like a dove.'
    hash_message1 = int(hashlib.sha1(message1).hexdigest(), 16)
    hash_message2 = int(hashlib.sha1(message2).hexdigest(), 16)
    private = getRandomNBitInteger(50)
    rand = getRandomNBitInteger(49)
    public_key = Public_key(generator_192, generator_192 * private)
    private_key = Private_key(public_key, private)
    sig = private_key.sign(hash_message1, rand)
    malicious_sig,k2 = private_key.malicious_sign(hash_message2, rand, a,b,w,X)
    
    print(a,b,w,X)
    print(sig.r)
    print(malicious_sig.r)

    '''
    751818 1155982 908970521 20391992
    6052579169727414254054653383715281797417510994285530927615
    3839784391338849056467977882403235863760503590134852141664
    '''
    
    # flag为flag{uuid}格式
    flag = b''
    m = bytes_to_long(flag)
    p = k2
    for i in range(99):
        p = gmpy2.next_prime(p)
    q = gmpy2.next_prime(p)
    e = 65537
    c = pow(m,e,p*q)
    print(c)
    # 1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943

分析题目

首先可以很明显地看到题目是ECDSA，那么就先讲一下ECDSA呢

ECDSA

椭圆曲线数字签名算法英语：Elliptic Curve Digital Signature Algorithm，缩写：ECDSA）是一种基于椭圆曲线密码学的公开密钥的加密算法，在之前的对于DSA知识点的文章介绍里面提到过ECDSA，ECDSA就是他的一个变种，Alice和Bob仍然使用同样的曲线，ECDSA需要使用明文的哈希结果，而不是明文本身。哈希函数的选择取决于使用者，但是需要明确的是必须选择加密安全的哈希函数。

因为ECDSA是签名算法，所以下面是签名和验签的过程

签名

1、需要选择一条椭圆曲线Ep(a,b)

2、选取一个随机数k，使 其范围满足1<k<=n-1,n则是椭圆曲线的阶

3、选取椭圆曲线上任意点G，计算K=k*G,坐标为K=(x,y)(注意这里的x,y为点K的x,y)

4、计算数字r=xK mod n

5、如果r=0，那么签名失败重新选择k直到其不等于0

6、获取要加密的明文m的哈希值Hex(m)，计算根据，sk=(Hex(m)+rd)mod n(此处为Alice的私钥d)

7、如果s=0，那么重新选择k，重新计算

8、输出签名(r,s)

验签

1、计算u1=s**(-1)*z mod n

2、就算u2=s**(-1)*r mod n

3、计算P=u1G+u2H(A)= (s**(-1)zG+s**(-1)rH(A)) mod n =s**(-1)G(z+rd)mod n (此处d为Alice的私钥)

4、当r=xP mod n的时候，验签成功

分析代码

主代码

那我们了解完签名与验签的过程可以来分析题目，先看主函数程序运行

if __name__ == '__main__':
    a,b,w,X = get_malicious_key()

    message1 = b'It sounds as though you were lamenting,'
    message2 = b'a butterfly cooing like a dove.'
    hash_message1 = int(hashlib.sha1(message1).hexdigest(), 16)
    hash_message2 = int(hashlib.sha1(message2).hexdigest(), 16)
    private = getRandomNBitInteger(50)
    rand = getRandomNBitInteger(49)
    public_key = Public_key(generator_192, generator_192 * private)
    private_key = Private_key(public_key, private)
    sig = private_key.sign(hash_message1, rand)
    malicious_sig,k2 = private_key.malicious_sign(hash_message2, rand, a,b,w,X)
    
    print(a,b,w,X)
    print(sig.r)
    print(malicious_sig.r)

    '''
    751818 1155982 908970521 20391992
    6052579169727414254054653383715281797417510994285530927615
    3839784391338849056467977882403235863760503590134852141664
    '''
    
    # flag为flag{uuid}格式
    flag = b''
    m = bytes_to_long(flag)
    p = k2
    for i in range(99):
        p = gmpy2.next_prime(p)
    q = gmpy2.next_prime(p)
    e = 65537
    c = pow(m,e,p*q)
    print(c)
    # 1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943

在这里面我们可以看到首先给定了Alice和Bob传递的明文，然后生成两个签名，并且用第二个签名生成p与q然后生成一个rsa

接下来逐步分析两个签名

签名一

def sign(self, hash, random_k):

    G = self.public_key.generator
    n = G.order()
    k = random_k % n
    p1 = k * G
    r = p1.x() % n
    if r == 0:
        raise RSZeroError("amazingly unlucky random number r")
    s = (
        inverse_mod(k, n)
        * (hash + (self.secret_multiplier * r) % n)
    ) % n
    if s == 0:
        raise RSZeroError("amazingly unlucky random number s")
    return Signature(r, s)

在这个签名，就是正常流程，不多做赘述

签名二

def malicious_sign(self,hash, random_k, a, b, w, X):
    # t = random.randint(0,1)
    t = 1
    G = self.public_key.generator
    Y = X * G
    n = G.order()
    k1 = random_k
    z = (k1 - w * t) * G + (-a * k1 - b) * Y
    zx = z.x() % n
    k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
    #print(f'k2 = {k2}')
    p1 = k2 * G
    r = p1.x() % n
    if r == 0:
        raise RSZeroError("amazingly unlucky random number r")
    s = (
                inverse_mod(k2, n)
                * (hash + (self.secret_multiplier * r) % n)
        ) % n
    if s == 0:
        raise RSZeroError("amazingly unlucky random number s")
    return (Signature(r, s),k2)

这个签名相比签名一多了一个生成z与k2的过程，我们可以知道k2就是z点的x坐标，那么我们去找到z点就可以

后门分析

然后根据整体代码或者自己测一下数据就可以发现，我们两个签名用的k和G是一样的，这个其实就是这道题目所说的后门了，所以我们在签名1得到的r其实就是k1*G的x坐标，但是因为这个是椭圆曲线上的点，点的相乘和正常的相乘是不一样的，所以我们就可以将式子转换为，z = p1+( - w * t) * G + (-a * k1 - b) * Y + (-a * p1)X+ (-b * XG),在这里需要注意的是椭圆曲线上的点不支持减法所以需要转化为+上负数倍的，然后我们将式子带入签名一然后直接解码就好了

完整exp：

from ecdsa.ecdsa import *
from Cryptodome.Util.number import *
import hashlib
import gmpy2
from tqdm import *
import sympy
def inverse_mod(a, m):
    if a == 0:
        return 0
    return gmpy2.powmod(a, -1, m)

def bit_length(x):
    return x.bit_length()

def get_malicious_key():
    a = getRandomNBitInteger(20)
    b = getRandomNBitInteger(21)
    w = getRandomNBitInteger(30)
    X = getRandomNBitInteger(25)
    return a, b, w, X

class RSZeroError(RuntimeError):
    pass


class InvalidPointError(RuntimeError):
    pass


class Signature(object):
    """ECDSA signature."""

    def __init__(self, r, s):
        self.r = r
        self.s = s


class Public_key(object):
    """Public key for ECDSA."""

    def __init__(self, generator, point, verify=True):

        self.curve = generator.curve()
        self.generator = generator
        self.point = point
        n = generator.order()
        p = self.curve.p()
        if not (0 <= point.x() < p) or not (0 <= point.y() < p):
            raise InvalidPointError(
                "The public point has x or y out of range."
            )
        if verify and not self.curve.contains_point(point.x(), point.y()):
            raise InvalidPointError("Point does not lay on the curve")
        if not n:
            raise InvalidPointError("Generator point must have order.")

        if (
            verify
            and self.curve.cofactor() != 1
            and not n * point == ellipticcurve.INFINITY
        ):
            raise InvalidPointError("Generator point order is bad.")


class Private_key(object):
    """Private key for ECDSA."""

    def __init__(self, public_key, secret_multiplier):

        self.public_key = public_key
        self.secret_multiplier = secret_multiplier
    def change_generator(self, o):
        # 假设 new_generator 是一个包含新生成元的元组
        self.public_key.generator = o

    def sign(self, hash, random_k):

        G = self.public_key.generator
        print(G)

        n = G.order()
        print('-------')
        print('G',G.x())
        k = 432179965122662 % n
        p1 = k * G
        print(k)
        print('random_k',random_k)
        print('o',p1.x())
        print(p1)
        print(p1.y())
        print('n',n)
        r = p1.x() % n
        print(n)
        print('-----------------')
        a = 751818
        b = 1155982
        w = 908970521
        X = 20391992
        t=1
        z = p1+(-w * t) * G + (-a * p1)*X+ (-b * X*G)
        print(z)
        print('z', z.x())
        print('z', z.y())
        zx = z.x() % n
        print('zx', zx)
        k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
        print('k2', k2)
        print("k2", k2, k2.bit_length(), hashlib.sha1(str(zx).encode()).hexdigest(),
            len(hashlib.sha1(str(zx).encode()).hexdigest()))
        # print(f'k2 = {k2}')

        print('=========================================================')
        #     k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
        p = k2
        for i in range(99):
            p = sympy.nextprime(p)
        q = sympy.nextprime(p)
        e = 65537
        d = inverse(e, (p - 1) * (q - 1))
        c = 1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943
        n = p * q
        m = int(pow(c, d, n))
        for i in range(2 ** 16):
            m += n
            flag = long_to_bytes(int(m))
            if b"flag" in flag:
                print(i)
                print(flag)
                break

        print('-----')

        if r == 0:
            raise RSZeroError("amazingly unlucky random number r")
        s = (
            inverse_mod(k, n)
            * (hash + (self.secret_multiplier * r) % n)
        ) % n
        if s == 0:
            raise RSZeroError("amazingly unlucky random number s")
        return Signature(r, s)

    def malicious_sign(self,hash, random_k, a, b, w, X):
        # t = random.randint(0,1)
        t = 1
        G = self.public_key.generator
        print(G.x())
        print(G.y())
        print('random_k', random_k)
        print('G',G.x())
        Y = X * G
        print('Y',Y.x())
        print('Y', Y.y())
        n = G.order()
        print('n',n)
        k1 = random_k
        z = (k1 - w * t) * G + (-a * k1 - b) * Y
        print(z)
        print('z',z.x())
        print('z',z.y())
        zx = z.x() % n
        print('zx',zx)
        k2 = int(hashlib.sha1(str(zx).encode()).hexdigest(), 16)
        print('k2',k2)
        print("k2",k2,k2.bit_length(),hashlib.sha1(str(zx).encode()).hexdigest(),len(hashlib.sha1(str(zx).encode()).hexdigest()))
        #print(f'k2 = {k2}')
        p1 = k2 * G
        r = p1.x() % n
        if r == 0:
            raise RSZeroError("amazingly unlucky random number r")
        s = (
                    inverse_mod(k2, n)
                    * (hash + (self.secret_multiplier * r) % n)
            ) % n
        if s == 0:
            raise RSZeroError("amazingly unlucky random number s")
        return (Signature(r, s),k2)

if __name__ == '__main__':


    message1 = b'It sounds as though you were lamenting,'
    message2 = b'a butterfly cooing like a dove.'
    hash_message1 = int(hashlib.sha1(message1).hexdigest(), 16)
    print('hash_message1',hash_message1)
    hash_message2 = int(hashlib.sha1(message2).hexdigest(), 16)
    print('hash_message2', hash_message2)
    private = getRandomNBitInteger(50)
    print('private',private)
    rand = getRandomNBitInteger(49)
    print('rand',rand)
    public_key = Public_key(generator_192, generator_192 * private)
    private_key = Private_key(public_key, private)
    sig = private_key.sign(hash_message1, rand)
    a=751818
    b=1155982
    w=908970521
    X=20391992
    malicious_sig,k2 = private_key.malicious_sign(hash_message2, rand, a,b,w,X)
    print('malicious_sig',malicious_sig.s)
    print(k2)
    
    print(a,b,w,X)
    print(sig.r)
    print(malicious_sig.r)

    '''
    751818 1155982 908970521 20391992
    6052579169727414254054653383715281797417510994285530927615
    3839784391338849056467977882403235863760503590134852141664
    '''
    
    # flag为flag{uuid}格式
    flag = b'aaa'
    m = bytes_to_long(flag)
    p = k2
    for i in range(99):
        p = gmpy2.next_prime(p)
    print(p)
    q = gmpy2.next_prime(p)
    e = 65537
    c = pow(m,e,p*q)
    print(c)
    print(long_to_bytes(1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943))
    # 1294716523385880392710224476578009870292343123062352402869702505110652244504101007338338248714943
    print('----------------------------------------------------------')

SEKAICTF-Crypto

import random
from secrets import randbelow, randbits
from flag import FLAG

CIPHER_SUITE = randbelow(2**256)
print(f"oPUN_SASS_SASS_l version 4.0.{CIPHER_SUITE}")
random.seed(CIPHER_SUITE)

GSIZE = 8209
GNUM = 79

LIM = GSIZE**GNUM


def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)


def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res


def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod


def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res


G = [gen(GSIZE) for i in range(GNUM)]


FLAG = int.from_bytes(FLAG, 'big')
left_pad = randbits(randbelow(LIM.bit_length() - FLAG.bit_length()))
FLAG = (FLAG << left_pad.bit_length()) + left_pad
FLAG = (randbits(randbelow(LIM.bit_length() - FLAG.bit_length()))
        << FLAG.bit_length()) + FLAG

bob_key = randbelow(LIM)
bob_encr = enc(FLAG, bob_key, G)
print("bob says", bob_encr)
alice_key = randbelow(LIM)
alice_encr = enc(bob_encr, alice_key, G)
print("alice says", alice_encr)
bob_decr = enc(alice_encr, bob_key, [inverse(i) for i in G])
print("bob says", bob_decr)

分析代码，先看主体干了什么，发现FLAG被填充前后都被填充了，然后可以很快的发现生成了三段密文，分别是bob_enc,alice_enc,bob_decr,可以看到三段密文都是enc函数生成的，我们去看一下enc函数

def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod

观察enc函数，你可以很快的发现首先它是一个递归函数，很明显有一个判断条件，就是当不在G的时候程序停止返回输出，否则他会递归，每次递归的变化如下：
gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod
在这里面可以看到有一个gexp函数，我们去看一下这个函数

def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res

显而易见你不用管这个函数，首先没随机数，根据你输入的g,e规定，这两个你都知道，所以这个就是对逆输入的G进行变换成为一个新的G，其实这个G就是一个排列，也就是S盒

def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)

然后回到前面的函数你会发现，每次递归需要找到S盒的首行某个值的索引，这里面这个值就是key mod 8209，然后每次递归得到的数据需要乘一下8209在加上S盒索引所对应的值也是就在G中所对应的值，所以我们得到的密文最后会是((((((x*8209)+y)*8209)+y)*8209)+y)……….)*8209+y，所以我们的可以根据这个把每次去到的G里面的值都得到，我们要求的就是他的索引，这个索引在enc函数是key mod 8209得到的，所以我们可以反推回去得到key，这里面有个比较关键的地方我们传入的第一个数据必须要是已知明文这样我们才能找key因为明文限制了S盒的生成
使用G值的脚本

def key_mod_8029(res):
    s=[]
    while (res):
        s.append(res%8209)
        res//=8209
    return s

这时候我们只需要稍微修改一下enc脚本使其变成最后加起来的东西只有这些索引就好了，不过要注意的是不要让索引值＋在递归函数前面要不然根据运算规则会先从左到右＋导致数据加多了去寻找索引就出现问题，数据就有问题了

def dec(k, res, G):
    if not G:
        return [0]
    mod = len(G[0])
    return dec(k // mod, res[1:], G[1:])+[gexp(G[0], k % mod).index(res[0])]

然后就是恢复key，根据前面所说的规则生成

def key_replay(res):
    a=0
    for i in res:
        a=a*8209+i
    return a

然后我们就能找到alice_key,然后我们去看bob_key,前面也说了需要知道前面的已知明文所以只能用bob_decr去解密
然后就知道两个key，那我们去恢复明文，这下子我们知道了key，那我们传入bob_key的话因为整体不是很大8209，我们就可以爆破一下匹配传入每次在gen函数取余传入的明文是多少

def dec1(res,key,G):
    a=[]
    if not G:
        return [0]
    for i in range(8209):
        if gexp(G[0],i)[key%8209]==res[0]:
            print(i)
            a.append(i)
    return dec1(res[1:],key//8209 ,G[1:])

然后用key_replay函数恢复一下就好了，不过注意下这边得到的数组需要逆向相加，因为我没递归直接返回值，而是生成一个数组，因为知道FLAG是前后有随机数中间可能会有flag在然后爆破一下找低位看到了很像flag的玩意

27887110439548179837945284065479407005671984418227744307030297585766676421518051725820730881303094307602205264926431534545591400990734997978646260585798939930398586856703150064008768662739131299115425991133646456082485455073198522787353032367591607142340524576787860298767828999348122114
b"\xbb\x89\x8b\x18\xc9\x7f\xff\xab8\xe7^V\x93MXO\xf6M\xb5;\xf7h\x11\xbd\x9ah\xa9h)/f\xecf&F\x8cf,FL,\xacL\xcc\x87,\xa6\x86g,l&,f\xe6\x86L\x86F\xccG&\xa6\xe6\xe7&F\x8cF\xac&'\x06Fff\xe7\x06\x06G\x0cfl\xac\x86\xa7,\x86\xec,\x87&L\x86/\xb7\xea\x98\x08T\xbf\xa5\xb4\x8b\xeft\xa8\xde\xdf\x00\xf2\xe9o\xce\xf3\xd1Kr\x02"
b"\xbb\x89\x8b\x18\xc9\x7f\xff\xab8\xe7^V\x93MXO\xf6M\xb5;\xf7h\x11\xbd\x9ah\xa9h)/f\xecf&F\x8cf,FL,\xacL\xcc\x87,\xa6\x86g,l&,f\xe6\x86L\x86F\xccG&\xa6\xe6\xe7&F\x8cF\xac&'\x06Fff\xe7\x06\x06G\x0cfl\xac\x86\xa7,\x86\xec,\x87&L\x86/\xb7\xea\x98\x08T\xbf\xa5\xb4\x8b\xeft\xa8\xde\xdf\x00\xf2\xe9o\xce\xf3\xd1Kr\x02"
b"]\xc4\xc5\x8cd\xbf\xff\xd5\x9cs\xaf+I\xa6\xac'\xfb&\xda\x9d\xfb\xb4\x08\xde\xcd4T\xb4\x14\x97\xb3v3\x13#F3\x16#&\x16V&fC\x96SC3\x966\x13\x163sC&C#f#\x93Sss\x93#F#V\x13\x13\x83#33s\x83\x03#\x8636VCS\x96Cv\x16C\x93&C\x17\xdb\xf5L\x04*_\xd2\xdaE\xf7\xbaToo\x80yt\xb7\xe7y\xe8\xa5\xb9\x01"
b'.\xe2b\xc62_\xff\xea\xce9\xd7\x95\xa4\xd3V\x13\xfd\x93mN\xfd\xda\x04of\x9a*Z\nK\xd9\xbb\x19\x89\x91\xa3\x19\x8b\x11\x93\x0b+\x133!\xcb)\xa1\x99\xcb\x1b\t\x8b\x19\xb9\xa1\x93!\x91\xb3\x11\xc9\xa9\xb9\xb9\xc9\x91\xa3\x11\xab\t\x89\xc1\x91\x99\x99\xb9\xc1\x81\x91\xc3\x19\x9b+!\xa9\xcb!\xbb\x0b!\xc9\x93!\x8b\xed\xfa\xa6\x02\x15/\xe9m"\xfb\xdd*7\xb7\xc0<\xba[\xf3\xbc\xf4R\xdc\x80'
b'\x17q1c\x19/\xff\xf5g\x1c\xeb\xca\xd2i\xab\t\xfe\xc9\xb6\xa7~\xed\x027\xb3M\x15-\x05%\xec\xdd\x8c\xc4\xc8\xd1\x8c\xc5\x88\xc9\x85\x95\x89\x99\x90\xe5\x94\xd0\xcc\xe5\x8d\x84\xc5\x8c\xdc\xd0\xc9\x90\xc8\xd9\x88\xe4\xd4\xdc\xdc\xe4\xc8\xd1\x88\xd5\x84\xc4\xe0\xc8\xcc\xcc\xdc\xe0\xc0\xc8\xe1\x8c\xcd\x95\x90\xd4\xe5\x90\xdd\x85\x90\xe4\xc9\x90\xc5\xf6\xfdS\x01\n\x97\xf4\xb6\x91}\xee\x95\x1b\xdb\xe0\x1e]-\xf9\xdez)n@'
b'\x0b\xb8\x98\xb1\x8c\x97\xff\xfa\xb3\x8eu\xe5i4\xd5\x84\xffd\xdbS\xbfv\x81\x1b\xd9\xa6\x8a\x96\x82\x92\xf6n\xc6bdh\xc6b\xc4d\xc2\xca\xc4\xcc\xc8r\xcahfr\xc6\xc2b\xc6nhd\xc8dl\xc4rjnnrdh\xc4j\xc2bpdffnp`dp\xc6f\xca\xc8jr\xc8n\xc2\xc8rd\xc8b\xfb~\xa9\x80\x85K\xfa[H\xbe\xf7J\x8d\xed\xf0\x0f.\x96\xfc\xef=\x14\xb7 '
b'\x05\xdcLX\xc6K\xff\xfdY\xc7:\xf2\xb4\x9aj\xc2\x7f\xb2m\xa9\xdf\xbb@\x8d\xec\xd3EKAI{7c124c1b2aebfd9e439ca1c742d26b9577924b5a1823378028c3ed59d7ad92d1}\xbfT\xc0B\xa5\xfd-\xa4_{\xa5F\xf6\xf8\x07\x97K~w\x9e\x8a[\x90'
b'\x02\xee&,c%\xff\xfe\xac\xe3\x9dyZM5a?\xd96\xd4\xef\xdd\xa0F\xf6i\xa2\xa5\xa0\xa4\xbd\x9b\xb1\x98\x99\x1a1\x98\xb1\x190\xb2\xb132\x1c\xb2\x9a\x19\x9c\xb1\xb0\x98\xb1\x9b\x9a\x192\x19\x1b1\x1c\x9a\x9b\x9b\x9c\x99\x1a1\x1a\xb0\x98\x9c\x19\x19\x99\x9b\x9c\x18\x19\x1c1\x99\xb2\xb2\x1a\x9c\xb2\x1b\xb0\xb2\x1c\x992\x18\xbe\xdf\xaa`!R\xfe\x96\xd2/\xbd\xd2\xa3{|\x03\xcb\xa5\xbf;\xcfE-\xc8'
b'\x01w\x13\x161\x92\xff\xffVq\xce\xbc\xad&\x9a\xb0\x9f\xec\x9bjw\xee\xd0#{4\xd1R\xd0R^\xcd\xd8\xccL\x8d\x18\xccX\x8c\x98YX\x99\x99\x0eYM\x0c\xceX\xd8LX\xcd\xcd\x0c\x99\x0c\x8d\x98\x8eMM\xcd\xceL\x8d\x18\x8dXLN\x0c\x8c\xcc\xcd\xce\x0c\x0c\x8e\x18\xcc\xd9Y\rNY\r\xd8Y\x0eL\x99\x0c_o\xd50\x10\xa9\x7fKi\x17\xde\xe9Q\xbd\xbe\x01\xe5\xd2\xdf\x9d\xe7\xa2\x96\xe4'
b"\xbb\x89\x8b\x18\xc9\x7f\xff\xab8\xe7^V\x93MXO\xf6M\xb5;\xf7h\x11\xbd\x9ah\xa9h)/f\xecf&F\x8cf,FL,\xacL\xcc\x87,\xa6\x86g,l&,f\xe6\x86L\x86F\xccG&\xa6\xe6\xe7&F\x8cF\xac&'\x06Fff\xe7\x06\x06G\x0cfl\xac\x86\xa7,\x86\xec,\x87&L\x86/\xb7\xea\x98\x08T\xbf\xa5\xb4\x8b\xeft\xa8\xde\xdf\x00\xf2\xe9o\xce\xf3\xd1Kr"
b"]\xc4\xc5\x8cd\xbf\xff\xd5\x9cs\xaf+I\xa6\xac'\xfb&\xda\x9d\xfb\xb4\x08\xde\xcd4T\xb4\x14\x97\xb3v3\x13#F3\x16#&\x16V&fC\x96SC3\x966\x13\x163sC&C#f#\x93Sss\x93#F#V\x13\x13\x83#33s\x83\x03#\x8636VCS\x96Cv\x16C\x93&C\x17\xdb\xf5L\x04*_\xd2\xdaE\xf7\xbaToo\x80yt\xb7\xe7y\xe8\xa5\xb9"
b'.\xe2b\xc62_\xff\xea\xce9\xd7\x95\xa4\xd3V\x13\xfd\x93mN\xfd\xda\x04of\x9a*Z\nK\xd9\xbb\x19\x89\x91\xa3\x19\x8b\x11\x93\x0b+\x133!\xcb)\xa1\x99\xcb\x1b\t\x8b\x19\xb9\xa1\x93!\x91\xb3\x11\xc9\xa9\xb9\xb9\xc9\x91\xa3\x11\xab\t\x89\xc1\x91\x99\x99\xb9\xc1\x81\x91\xc3\x19\x9b+!\xa9\xcb!\xbb\x0b!\xc9\x93!\x8b\xed\xfa\xa6\x02\x15/\xe9m"\xfb\xdd*7\xb7\xc0<\xba[\xf3\xbc\xf4R\xdc'
b'\x17q1c\x19/\xff\xf5g\x1c\xeb\xca\xd2i\xab\t\xfe\xc9\xb6\xa7~\xed\x027\xb3M\x15-\x05%\xec\xdd\x8c\xc4\xc8\xd1\x8c\xc5\x88\xc9\x85\x95\x89\x99\x90\xe5\x94\xd0\xcc\xe5\x8d\x84\xc5\x8c\xdc\xd0\xc9\x90\xc8\xd9\x88\xe4\xd4\xdc\xdc\xe4\xc8\xd1\x88\xd5\x84\xc4\xe0\xc8\xcc\xcc\xdc\xe0\xc0\xc8\xe1\x8c\xcd\x95\x90\xd4\xe5\x90\xdd\x85\x90\xe4\xc9\x90\xc5\xf6\xfdS\x01\n\x97\xf4\xb6\x91}\xee\x95\x1b\xdb\xe0\x1e]-\xf9\xdez)n'
b'\x0b\xb8\x98\xb1\x8c\x97\xff\xfa\xb3\x8eu\xe5i4\xd5\x84\xffd\xdbS\xbfv\x81\x1b\xd9\xa6\x8a\x96\x82\x92\xf6n\xc6bdh\xc6b\xc4d\xc2\xca\xc4\xcc\xc8r\xcahfr\xc6\xc2b\xc6nhd\xc8dl\xc4rjnnrdh\xc4j\xc2bpdffnp`dp\xc6f\xca\xc8jr\xc8n\xc2\xc8rd\xc8b\xfb~\xa9\x80\x85K\xfa[H\xbe\xf7J\x8d\xed\xf0\x0f.\x96\xfc\xef=\x14\xb7'
b'\x05\xdcLX\xc6K\xff\xfdY\xc7:\xf2\xb4\x9aj\xc2\x7f\xb2m\xa9\xdf\xbb@\x8d\xec\xd3EKAI{7c124c1b2aebfd9e439ca1c742d26b9577924b5a1823378028c3ed59d7ad92d1}\xbfT\xc0B\xa5\xfd-\xa4_{\xa5F\xf6\xf8\x07\x97K~w\x9e\x8a['
b'\x02\xee&,c%\xff\xfe\xac\xe3\x9dyZM5a?\xd96\xd4\xef\xdd\xa0F\xf6i\xa2\xa5\xa0\xa4\xbd\x9b\xb1\x98\x99\x1a1\x98\xb1\x190\xb2\xb132\x1c\xb2\x9a\x19\x9c\xb1\xb0\x98\xb1\x9b\x9a\x192\x19\x1b1\x1c\x9a\x9b\x9b\x9c\x99\x1a1\x1a\xb0\x98\x9c\x19\x19\x99\x9b\x9c\x18\x19\x1c1\x99\xb2\xb2\x1a\x9c\xb2\x1b\xb0\xb2\x1c\x992\x18\xbe\xdf\xaa`!R\xfe\x96\xd2/\xbd\xd2\xa3{|\x03\xcb\xa5\xbf;\xcfE-'
b'\x01w\x13\x161\x92\xff\xffVq\xce\xbc\xad&\x9a\xb0\x9f\xec\x9bjw\xee\xd0#{4\xd1R\xd0R^\xcd\xd8\xccL\x8d\x18\xccX\x8c\x98YX\x99\x99\x0eYM\x0c\xceX\xd8LX\xcd\xcd\x0c\x99\x0c\x8d\x98\x8eMM\xcd\xceL\x8d\x18\x8dXLN\x0c\x8c\xcc\xcd\xce\x0c\x0c\x8e\x18\xcc\xd9Y\rNY\r\xd8Y\x0eL\x99\x0c_o\xd50\x10\xa9\x7fKi\x17\xde\xe9Q\xbd\xbe\x01\xe5\xd2\xdf\x9d\xe7\xa2\x96'
b"\xbb\x89\x8b\x18\xc9\x7f\xff\xab8\xe7^V\x93MXO\xf6M\xb5;\xf7h\x11\xbd\x9ah\xa9h)/f\xecf&F\x8cf,FL,\xacL\xcc\x87,\xa6\x86g,l&,f\xe6\x86L\x86F\xccG&\xa6\xe6\xe7&F\x8cF\xac&'\x06Fff\xe7\x06\x06G\x0cfl\xac\x86\xa7,\x86\xec,\x87&L\x86/\xb7\xea\x98\x08T\xbf\xa5\xb4\x8b\xeft\xa8\xde\xdf\x00\xf2\xe9o\xce\xf3\xd1K"
b"]\xc4\xc5\x8cd\xbf\xff\xd5\x9cs\xaf+I\xa6\xac'\xfb&\xda\x9d\xfb\xb4\x08\xde\xcd4T\xb4\x14\x97\xb3v3\x13#F3\x16#&\x16V&fC\x96SC3\x966\x13\x163sC&C#f#\x93Sss\x93#F#V\x13\x13\x83#33s\x83\x03#\x8636VCS\x96Cv\x16C\x93&C\x17\xdb\xf5L\x04*_\xd2\xdaE\xf7\xbaToo\x80yt\xb7\xe7y\xe8\xa5"
b'.\xe2b\xc62_\xff\xea\xce9\xd7\x95\xa4\xd3V\x13\xfd\x93mN\xfd\xda\x04of\x9a*Z\nK\xd9\xbb\x19\x89\x91\xa3\x19\x8b\x11\x93\x0b+\x133!\xcb)\xa1\x99\xcb\x1b\t\x8b\x19\xb9\xa1\x93!\x91\xb3\x11\xc9\xa9\xb9\xb9\xc9\x91\xa3\x11\xab\t\x89\xc1\x91\x99\x99\xb9\xc1\x81\x91\xc3\x19\x9b+!\xa9\xcb!\xbb\x0b!\xc9\x93!\x8b\xed\xfa\xa6\x02\x15/\xe9m"\xfb\xdd*7\xb7\xc0<\xba[\xf3\xbc\xf4R'
b'\x17q1c\x19/\xff\xf5g\x1c\xeb\xca\xd2i\xab\t\xfe\xc9\xb6\xa7~\xed\x027\xb3M\x15-\x05%\xec\xdd\x8c\xc4\xc8\xd1\x8c\xc5\x88\xc9\x85\x95\x89\x99\x90\xe5\x94\xd0\xcc\xe5\x8d\x84\xc5\x8c\xdc\xd0\xc9\x90\xc8\xd9\x88\xe4\xd4\xdc\xdc\xe4\xc8\xd1\x88\xd5\x84\xc4\xe0\xc8\xcc\xcc\xdc\xe0\xc0\xc8\xe1\x8c\xcd\x95\x90\xd4\xe5\x90\xdd\x85\x90\xe4\xc9\x90\xc5\xf6\xfdS\x01\n\x97\xf4\xb6\x91}\xee\x95\x1b\xdb\xe0\x1e]-\xf9\xdez)'

进程已结束,退出代码0

完整exp

import random
from secrets import randbelow, randbits
from Cryptodome.Util.number import *

CIPHER_SUITE =5856735718192672966225212630546045665679020834917236661169743409360745081692
b1 =934535015385784972098018441829301227888268300482554572889937663972835689477317906590269550483816058279675056740632836110427165342116825918458562882459952965524045087097428340305468008069307089535207656651490741013829130388943184449967876591696491662942908809195857190028729699667883172408778919813286215678587

a1 =1200023343219513263382590595000530709398044680494887232151068706332454900457993992785528158990834544878450058108341045830600802696148032561205251770283666006973167393948548197072049425715808993347674584378538883200268601390915839644385525216204736891481357328537881870321049952052453132654798693784947466776387

b2 =1272441200473454987001701625665347128998267676768270586334850447786321082063417203439895347670890554611411858488237562330644466912578982684875984076535384996939506416271097344882332314135242565253987938022938597663163369675849841691494448925864719322424546037485802787986584090093449519504693373904532207187504

'''
bob says 934535015385784972098018441829301227888268300482554572889937663972835689477317906590269550483816058279675056740632836110427165342116825918458562882459952965524045087097428340305468008069307089535207656651490741013829130388943184449967876591696491662942908809195857190028729699667883172408778919813286215678587
alice says 1200023343219513263382590595000530709398044680494887232151068706332454900457993992785528158990834544878450058108341045830600802696148032561205251770283666006973167393948548197072049425715808993347674584378538883200268601390915839644385525216204736891481357328537881870321049952052453132654798693784947466776387
bob says 1272441200473454987001701625665347128998267676768270586334850447786321082063417203439895347670890554611411858488237562330644466912578982684875984076535384996939506416271097344882332314135242565253987938022938597663163369675849841691494448925864719322424546037485802787986584090093449519504693373904532207187504
'''
random.seed(CIPHER_SUITE)
GSIZE = 8209
GNUM = 79
LIM = GSIZE ** GNUM


def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)


def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res


def dec(k, res, G):
    if not G:
        return [0]
    mod = len(G[0])
    return dec(k // mod, res[1:], G[1:])+[gexp(G[0], k % mod).index(res[0])]


def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res


G = [gen(GSIZE) for i in range(GNUM)]


def key_mod_8029(res):
    a=[]
    while (res):
        a.append(res%8209)
        res//=8209
    return a


def key_replay(res):
    a=0
    for i in res:
        a=a*8209+i
    return a

def dec1(res,key,G):
    a=[]
    if not G:
        return [0]
    for i in range(8209):
        if gexp(G[0],i)[key%8209]==res[0]:
            print(i)
            a.append(i)
    return dec1(res[1:],key//8209 ,G[1:])

res = key_mod_8029(a1)
alice_key = key_replay(dec(b1, res, G))
res = key_mod_8029(b2)
bob_key = key_replay(dec(a1, res, [inverse(i) for i in G]))
res = key_mod_8029(b1)
dec1(res, bob_key, G)
a=(1936,
714,
7902,
2862,
958,
7,
4555,
5113,
5926,
3030,
2805,
6103,
3321,
7057,
2739,
2296,
6778,
5992,
2412,
5540,
7484,
5352,
6431,
2590,
6637,
4527,
4162,
5863,
1497,
2802,
4281,
4730,
7675,
1481,
6999,
6708,
1748,
3712,
126,
8111,
8071,
3535,
6725,
6717,
2231,
3087,
6844,
2080,
7716,
3681,
5834,
5903,
5666,
7767,
1112,
4696,
4728,
4675,
4655,
3456,
5558,
3019,
908,
7959,
5845,
2384,
4362,
2173,
5657,
604,
7247,
6713,
307,
5,
0,
0,
0,
0,
0)
FLAG = key_replay(reversed(a))
print(FLAG)
print(long_to_bytes(FLAG))
for i in range(20):
    print(long_to_bytes(FLAG>>i))

SEKAI{7c124c1b2aebfd9e439ca1c742d26b9577924b5a1823378028c3ed59d7ad92d1}