[SICTF Round4] Crypto

SignBase

交给厨子，一点魔术棒

next_prime

给了gift = n * next_prime(p) * next_prime(q) 直接来分解

#gift = p*nextp*q*nextq 
def factor(n):
    list = []
    a = iroot(n, 2)[0]
    while True:
        B2 = pow(a, 2) - n
        if is_square(B2):
            b = iroot(B2, 2)[0]
            pq = a - b
            p1q1 = a + b
            list.append([pq, p1q1])
            print(pq)
            print(p1q1)
            if len(list) == 2:
                break
        a += 1
    return list

list = factor(gift)
p = gcd(n,list[0][0])
long_to_bytes(pow(c,invert(65537,p-1),p))
#b'SICTF{f2a3af27-ad07-4fc2-9b69-a91304eee6a3}'

Smooth

从名字上看p的生成函数是用小素数生成的，最后+1，所以p-1是光滑的

def getT1ngPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(sieve_base)
        if isPrime(n + 1):
            return n + 1

n = ...
e = ...
c = ...
a = 2
k = 2
while True:
    a = powmod(a, k, n)
    res = gcd(a-1, n)
    if res != 1 and res != n:
        q = n // res
        p = res
        print(p)
        print(q)
        break
    k += 1

long_to_bytes(pow(c,invert(e,p1-1),p1))
b'SICTF{d8af7f58-49f7-490d-be49-386b8ff16361}'

Math Cocktail

给了一个算式 k = x + pow(x,-1,M)，两边乘x就得到kx=x^2+1 mod M 也就可以直接解2次方程了，出来一堆解，不过都能算出flag来

# k = x+pow(x,-1,M) => kx = x^2 + 1 mod M 
P.<x> = PolynomialRing(Zmod(M))
f = x^2 + 1 - k*x 
res = f.monic().roots(multiplicities=False)

for x in res:
    x = int(x)
    result = pow(x,n,M) + pow(x,-n,M)
    print("SICTF{"+str(result)+"}")

#SICTF{83812289150322223053501552731270409032921}