[Week1] sieve#

题目#

# sage
from Crypto.Util.number import bytes_to_long
from sympy import nextprime

FLAG = b'hgame{xxxxxxxxxxxxxxxxxxxxxx}'
m = bytes_to_long(FLAG)

def trick(k):
    if k > 1:
        mul = prod(range(1,k)) 
        if k - mul % k - 1 == 0:
            return euler_phi(k) + trick(k-1) + 1
        else:
            return euler_phi(k) + trick(k-1)
    else:
        return 1

e = 65537
p = q = nextprime(trick(e^2//6)<<128)
n = p * q
enc = pow(m,e,n)
print(f'{enc=}')
#enc=2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546

解题#

稍微分析的话，会发现素数p和q是同一个由nextprime(trick(e^2//6)<<128)生成的素数。

而这个函数跟之前YCB的decode差不多，都是素数的情况下会有个+1（因为判断条件是威尔逊定理，不懂的可以自行搜索了解一下），这里就直接给出结论：

trick(k)=sum([euler_phi(kk) for kk in range(1, k+1)])+prime_pi(e^2//6)

其中 prime_pi(k) 是一个函数，可以统计出**[1,k]**这个范围内的素数个数。

所以我们只需要算出sum([euler_phi(kk) for kk in range(1, k+1)])即可，我采取的方法是多线程（这数字就那么大，多线程下还是挺快就算出来的，我大概花了7~8min）

最后就直接按RSA解密的方式来解即可。

exp#

# sage-10.5
from Crypto.Util.number import *
from gmpy2 import *
from sage.parallel.multiprocessing_sage import parallel_iter
from multiprocessing import cpu_count

# get sum of phi
# res: 155763335410704472

def sum_euler_phi(start, end):
    return sum(euler_phi(i) for i in range(start, end + 1))

n = 65537^2 // 6
segment_size = n // cpu_count()

results = parallel_iter(cpu_count(), sum_euler_phi, [((k * segment_size + 1, (k + 1) * segment_size), {}) for k in range(cpu_count())])
total_sum = sum([val[1] for val in list(results)])
# print(total_sum)

ff = total_sum + prime_pi(65537**2//6)
p = q = next_prime(ff<<128)
phi = p*(p-1)
enc = 2449294097474714136530140099784592732766444481665278038069484466665506153967851063209402336025065476172617376546
d = invert(65537, phi)
print(long_to_bytes(pow(enc, d, p*q)))
# b'hgame{sieve_is_n0t_that_HArd}'

[Week1] ezBag#

题目#

from Crypto.Util.number import *
import random
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
from secrets import flag

list = []
bag = []
p=random.getrandbits(64)
assert len(bin(p)[2:])==64
for i in range(4):
    t = p
    a=[getPrime(32) for _ in range(64)]
    b=0
    for i in a:
        temp=t%2
        b+=temp*i
        t=t>>1
    list.append(a)
    bag.append(b)
print(f'list={list}')
print(f'bag={bag}')

key = hashlib.sha256(str(p).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")


"""
list=[[2826962231, 3385780583, 3492076631, 3387360133, 2955228863, 2289302839, 2243420737, 4129435549, 4249730059, 3553886213, 3506411549, 3658342997, 3701237861, 4279828309, 2791229339, 4234587439, 3870221273, 2989000187, 2638446521, 3589355327, 3480013811, 3581260537, 2347978027, 3160283047, 2416622491, 2349924443, 3505689469, 2641360481, 3832581799, 2977968451, 4014818999, 3989322037, 4129732829, 2339590901, 2342044303, 3001936603, 2280479471, 3957883273, 3883572877, 3337404269, 2665725899, 3705443933, 2588458577, 4003429009, 2251498177, 2781146657, 2654566039, 2426941147, 2266273523, 3210546259, 4225393481, 2304357101, 2707182253, 2552285221, 2337482071, 3096745679, 2391352387, 2437693507, 3004289807, 3857153537, 3278380013, 3953239151, 3486836107, 4053147071], [2241199309, 3658417261, 3032816659, 3069112363, 4279647403, 3244237531, 2683855087, 2980525657, 3519354793, 3290544091, 2939387147, 3669562427, 2985644621, 2961261073, 2403815549, 3737348917, 2672190887, 2363609431, 3342906361, 3298900981, 3874372373, 4287595129, 2154181787, 3475235893, 2223142793, 2871366073, 3443274743, 3162062369, 2260958543, 3814269959, 2429223151, 3363270901, 2623150861, 2424081661, 2533866931, 4087230569, 2937330469, 3846105271, 3805499729, 4188683131, 2804029297, 2707569353, 4099160981, 3491097719, 3917272979, 2888646377, 3277908071, 2892072971, 2817846821, 2453222423, 3023690689, 3533440091, 3737441353, 3941979749, 2903000761, 3845768239, 2986446259, 3630291517, 3494430073, 2199813137, 2199875113, 3794307871, 2249222681, 2797072793], [4263404657, 3176466407, 3364259291, 4201329877, 3092993861, 2771210963, 3662055773, 3124386037, 2719229677, 3049601453, 2441740487, 3404893109, 3327463897, 3742132553, 2833749769, 2661740833, 3676735241, 2612560213, 3863890813, 3792138377, 3317100499, 2967600989, 2256580343, 2471417173, 2855972923, 2335151887, 3942865523, 2521523309, 3183574087, 2956241693, 2969535607, 2867142053, 2792698229, 3058509043, 3359416111, 3375802039, 2859136043, 3453019013, 3817650721, 2357302273, 3522135839, 2997389687, 3344465713, 2223415097, 2327459153, 3383532121, 3960285331, 3287780827, 4227379109, 3679756219, 2501304959, 4184540251, 3918238627, 3253307467, 3543627671, 3975361669, 3910013423, 3283337633, 2796578957, 2724872291, 2876476727, 4095420767, 3011805113, 2620098961], [2844773681, 3852689429, 4187117513, 3608448149, 2782221329, 4100198897, 3705084667, 2753126641, 3477472717, 3202664393, 3422548799, 3078632299, 3685474021, 3707208223, 2626532549, 3444664807, 4207188437, 3422586733, 2573008943, 2992551343, 3465105079, 4260210347, 3108329821, 3488033819, 4092543859, 4184505881, 3742701763, 3957436129, 4275123371, 3307261673, 2871806527, 3307283633, 2813167853, 2319911773, 3454612333, 4199830417, 3309047869, 2506520867, 3260706133, 2969837513, 4056392609, 3819612583, 3520501211, 2949984967, 4234928149, 2690359687, 3052841873, 4196264491, 3493099081, 3774594497, 4283835373, 2753384371, 2215041107, 4054564757, 4074850229, 2936529709, 2399732833, 3078232933, 2922467927, 3832061581, 3871240591, 3526620683, 2304071411, 3679560821]]
bag=[123342809734, 118191282440, 119799979406, 128273451872]
ciphertext=b'\x1d6\xcc}\x07\xfa7G\xbd\x01\xf0P4^Q"\x85\x9f\xac\x98\x8f#\xb2\x12\xf4+\x05`\x80\x1a\xfa !\x9b\xa5\xc7g\xa8b\x89\x93\x1e\xedz\xd2M;\xa2'
"""

解题#

这题还是比较清晰的——先随机生成一个64bit的数p，然后根据其二进制形式进行如下计算（设——数p的二进制列表为P、题目给的素数列表为L、得到的结果列表为b）：

\begin{pmatrix}P_0,P_1,P_2,\cdots,P_{64}\end{pmatrix} * \begin{pmatrix}L_{0,0}&L_{0,1}&L_{0,2}&L_{0,3}\\L_{1,0}&L_{1,1}&L_{1,2}&L_{1,3}\\\vdots&\vdots&\vdots&\vdots\\L_{63,0}&L_{63,1}&L_{63,2}&L_{63,3}\end{pmatrix} = \begin{pmatrix}b_0,b_1,b_2,b_3\end{pmatrix}

而题目提到了bag，因此比较熟悉格的Crypto手们应该还是能反应过来——这题类似于背包密码。

于是我们直接构造一个如下的背包格即可：

M=\begin{pmatrix} 1&&&&&L_{0,0}&L_{0,1}&L_{0,2}&L_{0,3}\\ &1&&&&L_{1,0}&L_{1,1}&L_{1,2}&L_{1,3}\\ &&1&&&L_{2,0}&L_{2,1}&L_{2,2}&L_{2,3}\\ &&&\ddots&&\vdots&\vdots&\vdots&\vdots\\ &&&&1&L_{63,0}&L_{63,1}&L_{63,2}&L_{63,3}\\ &&&&&-b_0&&&\\ &&&&&&-b_1&&\\ &&&&&&&-b_2&\\ &&&&&&&&-b_3\\ \end{pmatrix}

这个格满足的等式如下：

\begin{pmatrix}P_0,P_1,P_2,\cdots,P_{64},1,1,1,1\end{pmatrix}*M=\begin{pmatrix}P_0,P_1,P_2,\cdots,P_{64},0,0,0,0\end{pmatrix}

此时我们只需要对格基规约后的结果进行筛选即可（参考exp），但是做题的时候发现直接用LLL对M进行规约不太行，所以就采用了BKZ。

最后筛出来后，直接AES解密即可。

exp#

# sage-10.5
from Crypto.Cipher import AES
import hashlib
List = [[2826962231, 3385780583, 3492076631, 3387360133, 2955228863, 2289302839, 2243420737, 4129435549, 4249730059, 3553886213, 3506411549, 3658342997, 3701237861, 4279828309, 2791229339, 4234587439, 3870221273, 2989000187, 2638446521, 3589355327, 3480013811, 3581260537, 2347978027, 3160283047, 2416622491, 2349924443, 3505689469, 2641360481, 3832581799, 2977968451, 4014818999, 3989322037, 4129732829, 2339590901, 2342044303, 3001936603, 2280479471, 3957883273, 3883572877, 3337404269, 2665725899, 3705443933, 2588458577, 4003429009, 2251498177, 2781146657, 2654566039, 2426941147, 2266273523, 3210546259, 4225393481, 2304357101, 2707182253, 2552285221, 2337482071, 3096745679, 2391352387, 2437693507, 3004289807, 3857153537, 3278380013, 3953239151, 3486836107, 4053147071], [2241199309, 3658417261, 3032816659, 3069112363, 4279647403, 3244237531, 2683855087, 2980525657, 3519354793, 3290544091, 2939387147, 3669562427, 2985644621, 2961261073, 2403815549, 3737348917, 2672190887, 2363609431, 3342906361, 3298900981, 3874372373, 4287595129, 2154181787, 3475235893, 2223142793, 2871366073, 3443274743, 3162062369, 2260958543, 3814269959, 2429223151, 3363270901, 2623150861, 2424081661, 2533866931, 4087230569, 2937330469, 3846105271, 3805499729, 4188683131, 2804029297, 2707569353, 4099160981, 3491097719, 3917272979, 2888646377, 3277908071, 2892072971, 2817846821, 2453222423, 3023690689, 3533440091, 3737441353, 3941979749, 2903000761, 3845768239, 2986446259, 3630291517, 3494430073, 2199813137, 2199875113, 3794307871, 2249222681, 2797072793], [4263404657, 3176466407, 3364259291, 4201329877, 3092993861, 2771210963, 3662055773, 3124386037, 2719229677, 3049601453, 2441740487, 3404893109, 3327463897, 3742132553, 2833749769, 2661740833, 3676735241, 2612560213, 3863890813, 3792138377, 3317100499, 2967600989, 2256580343, 2471417173, 2855972923, 2335151887, 3942865523, 2521523309, 3183574087, 2956241693, 2969535607, 2867142053, 2792698229, 3058509043, 3359416111, 3375802039, 2859136043, 3453019013, 3817650721, 2357302273, 3522135839, 2997389687, 3344465713, 2223415097, 2327459153, 3383532121, 3960285331, 3287780827, 4227379109, 3679756219, 2501304959, 4184540251, 3918238627, 3253307467, 3543627671, 3975361669, 3910013423, 3283337633, 2796578957, 2724872291, 2876476727, 4095420767, 3011805113, 2620098961], [2844773681, 3852689429, 4187117513, 3608448149, 2782221329, 4100198897, 3705084667, 2753126641, 3477472717, 3202664393, 3422548799, 3078632299, 3685474021, 3707208223, 2626532549, 3444664807, 4207188437, 3422586733, 2573008943, 2992551343, 3465105079, 4260210347, 3108329821, 3488033819, 4092543859, 4184505881, 3742701763, 3957436129, 4275123371, 3307261673, 2871806527, 3307283633, 2813167853, 2319911773, 3454612333, 4199830417, 3309047869, 2506520867, 3260706133, 2969837513, 4056392609, 3819612583, 3520501211, 2949984967, 4234928149, 2690359687, 3052841873, 4196264491, 3493099081, 3774594497, 4283835373, 2753384371, 2215041107, 4054564757, 4074850229, 2936529709, 2399732833, 3078232933, 2922467927, 3832061581, 3871240591, 3526620683, 2304071411, 3679560821]]
bag = [123342809734, 118191282440, 119799979406, 128273451872]
ciphertext = b'\x1d6\xcc}\x07\xfa7G\xbd\x01\xf0P4^Q"\x85\x9f\xac\x98\x8f#\xb2\x12\xf4+\x05`\x80\x1a\xfa !\x9b\xa5\xc7g\xa8b\x89\x93\x1e\xedz\xd2M;\xa2'
M = Matrix(ZZ, 68, 68)
for k in range(64):
    M[k, k] = 1
    M[k, -4] = List[0][k]
    M[k, -3] = List[1][k]
    M[k, -2] = List[2][k]
    M[k, -1] = List[3][k]
for k in range(-4, 0, 1):
    M[k, k] = -bag[4+k]
res = M.BKZ()
for k in range(68):
    if all(kk==0 for kk in res[k][-4:]):
        kk = res[k][:-4]
        if all(abs(kkk) in [0, 1] for kkk in kk):
            print(f"res: {res[k]}")
            print("".join(map(str, map(abs, kk)))[::-1])
            p = int("".join(map(str, map(abs, kk)))[::-1], 2)
            print(k, p)
            key = hashlib.sha256(str(p).encode()).digest()
            cipher = AES.new(key, AES.MODE_ECB)
            print(cipher.decrypt(ciphertext))
print("over")
'''
res: (1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0)
64 17739748707559623655
b'hgame{A_S1mple_Modul@r_Subset_Sum_Problem}\x06\x06\x06\x06\x06\x06'
over
'''

[Week1] suprimeRSA#

因为这题的n有问题，所以出题人中途有换了一组数据；因此我这里也分别说一下思路。

a, 第一版数据（非预期）#

题目#

from Crypto.Util.number import *
import random

FLAG=b'hgame{xxxxxxxxxxxxxxxxx}'
e=0x10001

#trick
def factorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= i
    return result
a=?
b=?
assert factorial(a)+factorial(b)==a**b
M=(a+b)<<128

def gen_key():
    while True:
        k = getPrime(29)
        a = getPrime(random.randint(20,62))
        p = k * M + pow(e, a, M)
        if isPrime(p):
            return p

p,q=gen_key(),gen_key()
n=p*q
m=bytes_to_long(FLAG)
enc=pow(m,e,n)

print(f'{n=}')
print(f'{enc=}')

"""
n=669040758304155675570167824759691921106935750270765997139446851830489844731373721233290816258049
enc=487207283176018824965268172307888245763817583875071008869370172565777230514379236733742846575849
"""

解题#

这版数据的问题是：因为M取得过于小了，使得n的bit长度也很少（）

所以直接yafu分解n，然后RSA解密即可XD

exp#

from Crypto.Util.number import *
from gmpy2 import *
n = 669040758304155675570167824759691921106935750270765997139446851830489844731373721233290816258049
c = 487207283176018824965268172307888245763817583875071008869370172565777230514379236733742846575849
p = 839777194079410698093279448382785381699926556673
q = 796688410951167236263039235508020180383351898113
e = 65537
d = invert(e, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))
# b'hgame{ROCA_ROCK_and_ROll!}'

b, 第二版数据（预期）#

题目#

from Crypto.Util.number import *
import random
from sympy import prime

FLAG=b'hgame{xxxxxxxxxxxxxxxxxx}'
e=0x10001

def primorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= prime(i)
    return result
M=primorial(random.choice([39,71,126]))

def gen_key():
    while True:
        k = getPrime(random.randint(20,40))
        a = getPrime(random.randint(20,60))
        p = k * M + pow(e, a, M)
        if isPrime(p):
            return p

p,q=gen_key(),gen_key()
n=p*q
m=bytes_to_long(FLAG)
enc=pow(m,e,n)

print(f'{n=}')
print(f'{enc=}')

"""
n=787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
enc=365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
"""

解题#

这版数据修复了M过于小的情况，所以就不太可能直接yafu了。

而这里的素数生成是这样的：

e=0x10001

def primorial(num):
    result = 1
    for i in range(1, num + 1):
        result *= prime(i)
    return result
M=primorial(random.choice([39,71,126]))

def gen_key():
    while True:
        k = getPrime(random.randint(20,40))
        a = getPrime(random.randint(20,60))
        p = k * M + pow(e, a, M)
        if isPrime(p):
            return p

p,q=gen_key(),gen_key()

这个是一种弱素数生成的形式，而这也有对应的一种攻击，叫ROCA（还是一个CVE）；因此网上能找到对应的攻击脚本，最后直接套着用即可。

算法的基本流程如下：
具体的原理可以参考The Return of Coppersmith’s AttackFactorization of Widely Used RSA Moduli这篇论文或是Analysis of the ROCA vulnerability · Bitsdeep这篇博客文章，里边讲得还是较详细的。

exp#

# sage-10.5
# code index: https://github.com/FlorianPicca/ROCA/blob/master/roca_attack.py
from sage.all import *
from Crypto.Util.number import *
from gmpy2 import *

def solve(M, n, a, m):
    # I need to import it in the function otherwise multiprocessing doesn't find it in its context
    def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
        """
        Taken from https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
        Coppersmith revisited by Howgrave-Graham
    
        finds a solution if:
        * b|modulus, b >= modulus^beta , 0 < beta <= 1
        * |x| < XX
        More tunable than sage's builtin coppersmith method, pol.small_roots()
        """
        #
        # init
        #
        dd = pol.degree()
        nn = dd * mm + tt
    
        #
        # checks
        #
        if not 0 < beta <= 1:
            raise ValueError("beta should belongs in [0, 1]")
    
        if not pol.is_monic():
            raise ArithmeticError("Polynomial must be monic.")
    
        #
        # calculate bounds and display them
        #
        """
        * we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
    
        * we know LLL will give us a short vector v such that:
        ||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
    
        * we will use that vector as a coefficient vector for our g(x)
    
        * so we want to satisfy:
        2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
    
        so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
        (it's important to use N because we might not know b)
        """
        #
        # Coppersmith revisited algo for univariate
        #
    
        # change ring of pol and x
        polZ = pol.change_ring(ZZ)
        x = polZ.parent().gen()
    
        # compute polynomials
        gg = []
        for ii in range(mm):
            for jj in range(dd):
                gg.append((x * XX) ** jj * modulus ** (mm - ii) * polZ(x * XX) ** ii)
        for ii in range(tt):
            gg.append((x * XX) ** ii * polZ(x * XX) ** mm)
    
        # construct lattice B
        BB = Matrix(ZZ, nn)
    
        for ii in range(nn):
            for jj in range(ii + 1):
                BB[ii, jj] = gg[ii][jj]
    
        BB = BB.LLL()
    
        # transform shortest vector in polynomial
        new_pol = 0
        for ii in range(nn):
            new_pol += x ** ii * BB[0, ii] / XX ** ii
    
        # factor polynomial
        potential_roots = new_pol.roots()
    
        # test roots
        roots = []
        for root in potential_roots:
            if root[0].is_integer():
                result = polZ(ZZ(root[0]))
                if gcd(modulus, result) >= modulus ** beta:
                    roots.append(ZZ(root[0]))
        return roots

    base = int(65537)
    # the known part of p: 65537^a * M^-1 (mod N)
    known = int(pow(base, a, M) * inverse_mod(M, n))
    # Create the polynom f(x)
    F = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
    (x,) = F._first_ngens(1)
    pol = x + known
    beta = 0.1
    t = m+1
    # Upper bound for the small root x0
    XX = floor(2 * n**0.5 / M)
    # Find a small root (x0 = k) using Coppersmith's algorithm
    roots = coppersmith_howgrave_univariate(pol, n, beta, m, t, XX)
    # There will be no roots for an incorrect guess of a.
    for k in roots:
        # reconstruct p from the recovered k
        p = int(k*M + pow(base, a, M))
        if n%p == 0:
            return p, n//p

def roca(n):

    keySize = n.bit_length()

    if keySize <= 960:
        M_prime = 0x1b3e6c9433a7735fa5fc479ffe4027e13bea
        m = 5

    elif 992 <= keySize <= 1952:
        M_prime = 0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
        m = 4
        print("Have you several days/months to spend on this ?")

    elif 1984 <= keySize <= 3936:
        M_prime = 0x16928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
        m = 7
        print("You'll change computer before this scripts ends...")

    elif 3968 <= keySize <= 4096:
        print("Just no.")
        return None

    else:
        print("Invalid key size: {}".format(keySize))
        return None

    a3 = Zmod(M_prime)(n).log(65537)
    order = Zmod(M_prime)(65537).multiplicative_order()
    inf = a3 // 2
    sup = (a3 + order) // 2

    # Search 10 000 values at a time, using multiprocess
    # too big chunks is slower, too small chunks also
    chunk_size = 10000
    for inf_a in range(inf, sup, chunk_size):
        # create an array with the parameter for the solve function
        inputs = [((M_prime, n, a, m), {}) for a in range(inf_a, inf_a+chunk_size)]
        # the sage builtin multiprocessing stuff
        from sage.parallel.multiprocessing_sage import parallel_iter
        from multiprocessing import cpu_count

        for k, val in parallel_iter(cpu_count(), solve, inputs):
            if val:
                p = int(val[0])
                q = int(val[1])
                print("found factorization:\np={}\nq={}".format(p, q))
                return (p, q)

if __name__ == "__main__":
    # Normal values
    # p = 88311034938730298582578660387891056695070863074513276159180199367175300923113
    # q = 122706669547814628745942441166902931145718723658826773278715872626636030375109
    # a = 551658, interval = [475706, 1076306]
    # won't find if beta=0.5
    '''
    p = 80688738291820833650844741016523373313635060001251156496219948915457811770063
    q = 69288134094572876629045028069371975574660226148748274586674507084213286357069
    '''
    # a = 176170, interval = [171312, 771912]
    n = 787190064146025392337631797277972559696758830083248285626115725258876808514690830730702705056550628756290183000265129340257928314614351263713241
    c = 365164788284364079752299551355267634718233656769290285760796137651769990253028664857272749598268110892426683253579840758552222893644373690398408
    # For the test values chosen, a is quite close to the minimal value so the search is not too long
    p, q = roca(n)
    e = 65537
    d = invert(e, (p-1)*(q-1))
    print(long_to_bytes(pow(c, d, n)))
# b'hgame{ROCA_ROCK_and_ROll!}'

[Week2] Ancient Recall#

题目#

import random

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana
reversals = [0,-1]

Value = []
cards = []
YOUR_initial_FATE = []
while len(YOUR_initial_FATE)<5:
    card = random.choice(tarot)
    if card not in cards:
        cards.append(card)
        if card in Major_Arcana:
            k = random.choice(reversals)
            Value.append(tarot.index(card)^k)
            if k == -1:
                YOUR_initial_FATE.append("re-"+card)
            else:
                YOUR_initial_FATE.append(card)
        else:
            Value.append(tarot.index(card))
            YOUR_initial_FATE.append(card)
    else:
        continue
print("Oops!lets reverse 1T!")

FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")

YOUR_final_Value = Value
def Fortune_wheel(FATE):
    FATEd = [FATE[i]+FATE[(i+1)%5] for i in range(len(FATE))]
    return FATEd

for i in range(250):
    YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)
YOUR_final_FATE = []
for i in YOUR_final_Value:
    YOUR_final_FATE.append(tarot[i%78])
print("Your destiny changed!\n",",".join(YOUR_final_FATE))
print("oh,now you GET th3 GOOd lU>k,^^")
"""
Oops!lets reverse 1T!
[2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
Your destiny changed!
 Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords
oh,now you GET th3 GOOd lU>k,^^
"""

解题#

首先，题目说了flag是这样的：

FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")

给我们的数据如下：

# 长度为5
YOUR_final_Value = [2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]

# 这个其实没啥用，可以不用管
YOUR_final_FATE = "Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords".split(",")

而我们如果只看与上述部分有关的内容的话，整道题的关键部分有如下两处：

1，随机选出YOUR_initial_FATE以及对应的Value
2，对Value进行250次Fortune_wheel()，得到YOUR_final_Value

而且题目也说了lets reverse 1T!

因此，这题只是考我们对代码的审计，所以我们就reverse一下。

1，求Value

先来看这段代码：

YOUR_final_Value = Value
def Fortune_wheel(FATE):
    FATEd = [FATE[i]+FATE[(i+1)%5] for i in range(len(FATE))]
    return FATEd

for i in range(250):
    YOUR_final_Value = Fortune_wheel(YOUR_final_Value)
print(YOUR_final_Value)

这个函数的功能是：输出FATE列表相邻两数（最后一个数与第一个数相邻）相加的和，也就是下面这个公式：

FATEd[i]=FATE[i]+FATE[(i+1)\ mod\ 5]

因为这里就5个数，所以就是下面这样：

FATEd[0]=FATE[0]+FATE[1]\\ FATEd[1]=FATE[1]+FATE[2]\\ FATEd[2]=FATE[2]+FATE[3]\\ FATEd[3]=FATE[3]+FATE[4]\\ FATEd[4]=FATE[4]+FATE[0]

这样一列出来就很容易知道，FATEd列表与FATE列表的关系如下：

\sum^{4}_{i=0}FATEd[i]=2\sum^{4}_{i=0}FATE[i]

所以这里我们就能知道——FATE列表的元素总和=0.5*FATEd列表的元素总和

假设FATE列表的元素总和为S，此时我们把这个与前面的对照着看，就可以发现FATE列表的元素与FATEd列表有着下列关系：

\begin{split} FATE[0]&=S-FATEd[1]-FATEd[3]\\ FATE[1]&=S-FATEd[2]-FATEd[4]\\ FATE[2]&=S-FATEd[3]-FATEd[0]\\ FATE[3]&=S-FATEd[4]-FATEd[1]\\ FATE[4]&=S-FATEd[0]-FATEd[2]\end{split}

也就是下列公式：

FATE[i]=S-FATEd[(i+1)\ mod\ 5]-FATEd[(i+3)\ mod\ 5]

于是Value就能逆出来了。

def re_Fortune_wheel(FATE):
    ss = sum(FATE)//2
    FATEd = [ss-FATE[(i+1)%5]-FATE[(i+3)%5] for i in range(len(FATE))]
    return FATEd


YOUR_final_Value = [2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
YOUR_final_FATE = "Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords".split(",")
for i in range(250):
    YOUR_final_Value = re_Fortune_wheel(YOUR_final_Value)
Value = YOUR_final_Value
# [-19, -20, 20, -15, 41]

2，求YOUR_initial_FATE

这个就涉及到这段代码了：

Value = []
cards = []
YOUR_initial_FATE = []
while len(YOUR_initial_FATE)<5:
    card = random.choice(tarot)
    if card not in cards:
        cards.append(card)
        if card in Major_Arcana:
            k = random.choice(reversals)
            Value.append(tarot.index(card)^k)
            if k == -1:
                YOUR_initial_FATE.append("re-"+card)
            else:
                YOUR_initial_FATE.append(card)
        else:
            Value.append(tarot.index(card))
            YOUR_initial_FATE.append(card)
    else:
        continue

简单来说，是这样的：：

如果k=-1，则YOUR_initial_FATE添加的是"re-"+card，Value添加的是tarot.index(card)^(-1)
否则，就是直接分别添加card和tarot.index(card)

所以就很简单了——负数就是有re-，否则就是没有（我感觉没啥好解释的，具体可以看代码）

exp#

Major_Arcana = ["The Fool", "The Magician", "The High Priestess","The Empress", "The Emperor", "The Hierophant","The Lovers", "The Chariot", "Strength","The Hermit", "Wheel of Fortune", "Justice","The Hanged Man", "Death", "Temperance","The Devil", "The Tower", "The Star","The Moon", "The Sun", "Judgement","The World"]
wands = ["Ace of Wands", "Two of Wands", "Three of Wands", "Four of Wands", "Five of Wands", "Six of Wands", "Seven of Wands", "Eight of Wands", "Nine of Wands", "Ten of Wands", "Page of Wands", "Knight of Wands", "Queen of Wands", "King of Wands"]
cups = ["Ace of Cups", "Two of Cups", "Three of Cups", "Four of Cups", "Five of Cups", "Six of Cups", "Seven of Cups", "Eight of Cups", "Nine of Cups", "Ten of Cups", "Page of Cups", "Knight of Cups", "Queen of Cups", "King of Cups"]
swords = ["Ace of Swords", "Two of Swords", "Three of Swords", "Four of Swords", "Five of Swords", "Six of Swords", "Seven of Swords", "Eight of Swords", "Nine of Swords", "Ten of Swords", "Page of Swords", "Knight of Swords", "Queen of Swords", "King of Swords"]
pentacles = ["Ace of Pentacles", "Two of Pentacles", "Three of Pentacles", "Four of Pentacles", "Five of Pentacles", "Six of Pentacles", "Seven of Pentacles", "Eight of Pentacles", "Nine of Pentacles", "Ten of Pentacles", "Page of Pentacles", "Knight of Pentacles", "Queen of Pentacles", "King of Pentacles"]
Minor_Arcana = wands + cups + swords + pentacles
tarot = Major_Arcana + Minor_Arcana


def re_Fortune_wheel(FATE):
    ss = sum(FATE)//2
    FATEd = [ss-FATE[(i+1)%5]-FATE[(i+3)%5] for i in range(len(FATE))]
    return FATEd


YOUR_final_Value = [2532951952066291774890498369114195917240794704918210520571067085311474675019, 2532951952066291774890327666074100357898023013105443178881294700381509795270, 2532951952066291774890554459287276604903130315859258544173068376967072335730, 2532951952066291774890865328241532885391510162611534514014409174284299139015, 2532951952066291774890830662608134156017946376309989934175833913921142609334]
YOUR_final_FATE = "Eight of Cups,Ace of Cups,Strength,The Chariot,Five of Swords".split(",")
for i in range(250):
    YOUR_final_Value = re_Fortune_wheel(YOUR_final_Value)
Value = YOUR_final_Value
print(Value)
YOUR_initial_FATE = []
for k in Value:
    if k < 0:
        YOUR_initial_FATE.append("re-"+tarot[(-1)^k])
    else:
        YOUR_initial_FATE.append(tarot[k])
FLAG=("hgame{"+"&".join(YOUR_initial_FATE)+"}").replace(" ","_")
print(FLAG)
# b'hgame{re-King_of_Pentacles&re-The_Magician&Judgement&re-King_of_Pentacles&Six_of_Cups}'

[Week2] Intergalactic Bound#

题目#

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randint
import hashlib
from secrets import flag

def add_THCurve(P, Q):
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 - y1 ** 2 * x2 * y2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    y3 = (y1 * y2 ** 2 - a * x1 ** 2 * x2) * pow(a * x1 * y1 * x2 ** 2 - y2, -1, p) % p
    return x3, y3


def mul_THCurve(n, P):
    R = (0, 0)
    while n > 0:
        if n % 2 == 1:
            R = add_THCurve(R, P)
        P = add_THCurve(P, P)
        n = n // 2
    return R


p = getPrime(96)
a = randint(1, p)
print(f"{a = }")
G = (randint(1,p), randint(1,p))
d = (a*G[0]^3+G[1]^3+1)%p*inverse(G[0]*G[1],p)%p
x = randint(1, p)
Q = mul_THCurve(x, G)
print(f"p = {p}")
print(f"G = {G}")
print(f"Q = {Q}")

key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = pad(flag,16)
ciphertext = cipher.encrypt(flag)
print(f"ciphertext={ciphertext}")

"""
p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
Q = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"
"""

解题#

其实没啥好说的，这个在之前的SICTF Round3有出现过，就是考察Twisted Hessian Curves映射成Weierstrass Curves；这个在鸡块师傅的博客里有介绍以及计算代码：2024-羊城杯-wp-crypto，不过我们这里还需要算出a的值

而我们知道这条曲线的一般方程在代入d后长这样：

ax^{3}+y^{3}+1=\frac{xy(a{G_x}^{3}+{G_y}^{3}+1)}{G_xG_y}\ mod\ p

稍微整理一下就有：

a=\frac{xy({G_x}^{3}+1)-G_xG_y({y}^3+1)}{x^3G_xG_y-{G_x}^{3}xy}\ mod\ p

之后就跟鸡块师傅的计算代码一致了

exp#

# sage-10.5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from gmpy2 import *
import hashlib


p = 55099055368053948610276786301
G = (19663446762962927633037926740, 35074412430915656071777015320)
P = (26805137673536635825884330180, 26376833112609309475951186883)
ciphertext=b"k\xe8\xbe\x94\x9e\xfc\xe2\x9e\x97\xe5\xf3\x04'\x8f\xb2\x01T\x06\x88\x04\xeb3Jl\xdd Pk$\x00:\xf5"

########################################################### part1 get a and d
a = ((P[1]*P[0]*(G[1]**3+1)-G[1]*G[0]*(P[1]**3+1))*invert(G[1]*G[0]*P[0]**3-P[1]*P[0]*G[0]**3, p))%p
Q = P
P = G
d = (a*P[0]^3 + P[1]^3 + 1) * inverse(P[0]*P[1], p) % p

########################################################### part2 dlp
R.<x,y,z> = Zmod(p)[]
cubic = a*x^3 + y^3 + z^3 - d*x*y*z
E = EllipticCurve_from_cubic(cubic,morphism=True)
P = E(P)
Q = E(Q)
x = int(Q.log(P))

########################################################### part3 get flag
key = hashlib.sha256(str(x).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.decrypt(ciphertext)
print(f"{ciphertext}")
# b'hgame{N0th1ng_bu7_up_Up_UP!}'

[Week2] SPiCa#

题目#

from Crypto.Util.number import getPrime, long_to_bytes,bytes_to_long
from secrets import flag
from sage.all import *

def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)

m = bytes_to_long(flag).bit_length()
n = 70
p = derive_M(n)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, list(bin(bytes_to_long(flag))[2:]))
h = x*A

with open("data.txt", "w") as file:
    file.write(str(m) + "\n")
    file.write(str(p) + "\n")
    for item in h:
        file.write(str(item) + "\n")

数据有点长，我就不放出来了。

解题#

因为A矩阵是一个01矩阵，而p的生成也比较特殊：

def derive_M(n):
    iota=0.035
    Mbits=int(2 * iota * n^2 + n * log(n,2))
    M = random_prime(2^Mbits, proof = False, lbound = 2^(Mbits - 1))
    return Integer(M)

所以就在网上查了下，发现是隐子集和问题（HSSP / Hidden Subset Sum Problem）；于是我们用对应的攻击脚本来打就行

exp#

# sage-10.5
# index: https://lazzzaro.github.io/2020/11/07/crypto-%E6%A0%BC%E5%AF%86%E7%A0%81/index.html#%E9%9A%90%E5%AD%90%E9%9B%86%E5%92%8C%E9%97%AE%E9%A2%98%EF%BC%88HSSP-Hidden-Subset-Sum-Problem%EF%BC%89
from Crypto.Util.number import *

n = 70
m = 247
p = 
w = 


def allpmones(v):
    return len([vj for vj in v if vj in [-1, 0, 1]]) == len(v)

# We generate the lattice of vectors orthogonal to b modulo x0
def orthoLattice(b, x0):
    m = b.length()
    M = Matrix(ZZ, m, m)

    for i in range(1, m):
        M[i, i] = 1
    M[1:m, 0] = -b[1:m] * inverse_mod(b[0], x0)
    M[0, 0] = x0

    for i in range(1, m):
        M[i, 0] = mod(M[i, 0], x0)

    return M

def allones(v):
    if len([vj for vj in v if vj in [0, 1]]) == len(v):
        return v
    if len([vj for vj in v if vj in [0, -1]]) == len(v):
        return -v
    return None

def recoverBinary(M5):
    lv = [allones(vi) for vi in M5 if allones(vi)]
    n = M5.nrows()
    for v in lv:
        for i in range(n):
            nv = allones(M5[i] - v)
            if nv and nv not in lv:
                lv.append(nv)
            nv = allones(M5[i] + v)
            if nv and nv not in lv:
                lv.append(nv)
    return Matrix(lv)

def kernelLLL(M):
    n = M.nrows()
    m = M.ncols()
    if m < 2 * n:
        return M.right_kernel().matrix()
    K = 2 ^ (m // 2) * M.height()

    MB = Matrix(ZZ, m + n, m)
    MB[:n] = K * M
    MB[n:] = identity_matrix(m)

    MB2 = MB.T.LLL().T

    assert MB2[:n, : m - n] == 0
    Ke = MB2[n:, : m - n].T

    return Ke

def attack(m, n, p, h):
    # This is the Nguyen-Stern attack, based on BKZ in the second step
    print("n =", n, "m =", m)

    iota = 0.035
    nx0 = int(2 * iota * n ^ 2 + n * (2).log(n))
    print("nx0 =", nx0)

    x0 = p
    b = vector(h)

    # only information we get
    M = orthoLattice(b, x0)

    t = cputime()
    M2 = M.LLL()
    print("LLL step1: %.1f" % cputime(t))

    # assert sum([vi == 0 and 1 or 0 for vi in M2 * X]) == m - n
    MOrtho = M2[: m - n]

    print("  log(Height, 2) = ", int((2).log(MOrtho.height())))

    t2 = cputime()
    ke = kernelLLL(MOrtho)

    print("  Kernel: %.1f" % cputime(t2))
    print("  Total step1: %.1f" % cputime(t))

    if n > 170:
        return

    beta = 2
    tbk = cputime()
    while beta < n:
        if beta == 2:
            M5 = ke.LLL()
        else:
            M5 = M5.BKZ(block_size=beta)

        # we break when we only get vectors with {-1,0,1} components
        if len([True for v in M5 if allpmones(v)]) == n:
            break

        if beta == 2:
            beta = 10
        else:
            beta += 10

    print("BKZ beta=%d: %.1f" % (beta, cputime(tbk)))
    t2 = cputime()
    MB = recoverBinary(M5)
    print("  Recovery: %.1f" % cputime(t2))
    print("  Number of recovered vector = ", MB.nrows())
    print("  Number of recovered vector.T = ", MB.ncols())
    return MB

res = attack(m, n, p, w)
for k in res:
    flag = long_to_bytes(int("".join(map(str, list(k))), 2))
    if b"hgame" in flag:
        print(flag)
'''
n = 70 m = 247
nx0 = 354
LLL step1: 12.9
  log(Height, 2) =  0
  Kernel: 6.1
  Total step1: 18.9
BKZ beta=10: 0.6
  Recovery: 1.5
  Number of recovered vector =  70
  Number of recovered vector.T =  247
b'hgame{U_f0und_3he_5pec14l_0n3!}'
'''