sign1n

题目

from secret import r, t
from Crypto.Util.number import *

flag = b'xxx'
flag = bytes_to_long(flag)
e = 0x10001

def gen_keys():
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p-1)*(q-1)
    d = inverse(e,phi)
    n = p*q
    print(f'n = {n}')
    WHATF = (d ** 3 + 3) % phi
    print(f'WHATF= {WHATF}')
    return d, n, WHATF

def easy_sign(n,d):
    m = flag * pow(r,e**2+d**2,n) % n
    s = pow(m,d,n)
    return s

def gift():
    assert t > 0
    gift = pow(r,t) - 1
    #print(t)
    print(isPrime(gift))

d,n,WHATF = gen_keys()
gift()
sign = easy_sign(n,d)
print(f'sign = {sign}')

# n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
# WHATF= 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
# 1
# sign = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815

题目给了WHATF等式，等式两边同乘e³即可求出kphi，尝试用kphi和n分解n；其次在gift函数中容易得到r=2，若r不为2则输出结果必为合数。后面就是常规的RSA...

我的解答

from Crypto.Util.number import *


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)

n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
WHATF= 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
sign = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815
e=0x10001
r=2
kphi=e**3*WHATF-3*e**3-1

p,q=factorize_multi_prime(n,kphi)
phi=(p-1)*(q-1)
d=int(inverse_mod(e,phi))
m=pow(sign,e,n)
flag=(m*int(inverse_mod(int(pow(r,e**2+d**2,n)),n)))%n
print(long_to_bytes(int(flag)))
#b'DASCTF{RSA_Bl1nd_Signatur3_With_M4th}'

babyhash_revenge

题目

import socketserver
import signal
from Crypto.Util.number import *
from random import randint
from gmpy2 import next_prime

banner = br'''
 _____     ______     ______     ______     ______   ______  
/\  __-.  /\  __ \   /\  ___\   /\  ___\   /\__  _\ /\  ___\ 
\ \ \/\ \ \ \  __ \  \ \___  \  \ \ \____  \/_/\ \/ \ \  __\ 
 \ \____-  \ \_\ \_\  \/\_____\  \ \_____\    \ \_\  \ \_\   
  \/____/   \/_/\/_/   \/_____/   \/_____/     \/_/   \/_/   
'''

flag = b'xxx'
n0 = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
g = 91289086035117540959154051117940771730039965839291520308840839624996039016929

class LCG():
    def __init__(self) -> None:
        self.n = next_prime(2**240)
        self.a = getRandomNBitInteger(85)
        self.seed = randint(1, self.n-1)

    def next(self):
        self.seed = (self.seed ** 3 * self.a + randint(-2**230, 2**230) + randint(1,100)) % self.n
        return self.seed

def gift():
    lcg = LCG()
    outputs = []
    for i in range(30):
        outputs.append(int(lcg.next()))
    return outputs, lcg.a

gift, a = gift()

def check(str1,str2):
    key = bin(a)[2:]
    test = []
    for i in range(len(key)):
        if key[i] == '0':
            test.append(str1[i] == str2[i])
    return all(test)

def hash(msg):
    key = bin(a)[2:]
    n = n0
    msg = list(map(ord,msg))
    for i in range(len(msg)):
        if key[i] == '1':
            n = g * (2 * n + msg[i])
        else:
            continue
        n = n & ((1 << 383) - 1)
    return (n - 0xdeedbeef114514) % (1 << 100)

MENU = br'''
<OPTION>
'''

class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'SERVER <INPUT>: '):
        self.send(prompt, newline=False)
        return self._recvall()

    def proof_of_work(self):
        rounds = 1000
        pseudo_prime = int(self.recv(prompt=b'[+] Plz Tell Me your number: '))
        if isPrime(pseudo_prime):
            self.send(b"\nNo! it's a prime, go away!")
            self.request.close()
        for i in range(rounds):
            if pow(randint(2, pseudo_prime), pseudo_prime - 1, pseudo_prime) != 1:
                self.send(b"\nYou failed in round " + str(i + 1).encode() + b', bye~~')
                self.request.close()
        self.send(b"\nCongratulations, you have passed the proof_of_work!\n")
        return True

    def handle(self):
        signal.alarm(300)
        step1 = self.proof_of_work()
        if not step1:
            self.request.close()
        self.send(banner)
        self.send(b"\nNew challenge now! Please give me 2 diff strings whose hashes are the same~~")
        self.send(b'Here is my gift for you: \n' + str(gift).encode())
        string1 = self.recv().decode()
        string2 = self.recv().decode()
        if len(string1) < 70 or len(string2) < 70:
            self.send(b"\nNo! Too short!")
            self.request.close()
        if not check(string1,string2):
            self.send(b"\nNo! I do not like!")
            self.request.close()
        if string1 == string2:
            self.send(b"\nNo! They are the same one!")
            self.request.close()
        if hash(string1) == hash(string2):
            self.send(b'\nGood job~ Here you are!')
            self.send(flag)
        self.send(b"\nConnection has been closed.")
        self.request.close()

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 9999
    print("HOST:POST " + HOST+":" + str(PORT))
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

题目的第一步是要输入符合费马小定理但是不能是质数的数字，搜了一下pseudo_prime才知道这是伪素数。网上给出了卡迈克尔数构造方式：

pseudo_prime=(6*m+1)*(12*m+1)*(18*m+1)，其中这三个因子都为素数

这里只需要将m改大点就可以过了第一个验证。

第二步给出了lcg函数的输出以此来求a，很明显是一个HNP问题构造格即可求解。根据lcg输出的30组数据：

$$s_1≡a*{s_0}^3+e_0(mod \space n)$$

$$s_2≡a*{s_1}^3+e_1(mod \space n)$$

$$\vdots$$

$$s_{30}≡a*{s_{29}}^3+e_{29}(mod \space n)$$

则可以有递推公式：$e_i=A_i*e_1+B_i，i \in [2,29]$

即可构造如下格：

$$\begin{bmatrix}n & 0 & \dots &0& 0 \\0 & n & \dots &0& 0\\ \vdots & \vdots & \dots &\dots& \vdots \\A_0 & A_1 & \dots & 1 & 0\\B_0 & B_1 & \dots & 0 & 2^{230}\end{bmatrix}$$

即可求出a

第三步验证hash，其实就是构造两个字符串使得在0的位置上字符相同，1的位置上字符不同，使得最后得到的结果相同。假设构造S1，S2两个字符串。由于在1的时候n才会改变，那么只需要使得最后结果相同即可。经过迭代可得出只需满足$\sum_{i=1}^{k} (S1_i-S2_i)2^{k-i}g^{k-i+1}=0(mod2^{100})​​​$即可，及可构造格：

$$\begin{bmatrix} 1 & 0 & \cdots & 0 &g^{k-i+1}2^{k-i}\\0 & 1 & \cdots & 0 &g^{k-i}2^{k-i-1}\\\vdots & \vdots & \ddots & \vdots &\vdots\\0 &0 &0 &1 &g\\0 &0 & 0 & 0 & 2^{100}\end{bmatrix}$$

该格规约出来的结果就是两字符串在1处相差的数值。

我的解答

from pwn import *
from Crypto.Util.number import *

r=remote('node4.buuoj.cn',25097)
context(os='linux', arch='amd64', log_level='debug')
context.log_level = 'debug'

def pseudo_prime():
    for i in range(10**10,10**20):
        if isPrime(6*i+1) and isPrime(12*i+1) and isPrime(18*i+1):
            print((6*i+1)*(12*i+1)*(18*i+1))
            return (6*i+1)*(12*i+1)*(18*i+1)
            break

def hash(msg):
    key = bin(a)[2:]
    n = n0
    msg = list(map(ord,msg))
    for i in range(len(msg)):
        if key[i] == '1':
            n = g * (2 * n + msg[i])
        else:
            continue
        n = n & ((1 << 383) - 1)
    return (n - 0xdeedbeef114514) % (1 << 100)

n0 = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
g = 91289086035117540959154051117940771730039965839291520308840839624996039016929

r.recv()
r.send(str(pseudo_prime()).encode())
r.recvuntil(b'Here is my gift for you: \n')
lcg=eval(r.recvuntil(b']'))
A = []
B = []
n = next_prime(2 ** 240)

M = Matrix(ZZ, 30, 30)
for i in range(28):
    M[i, i] = n
for i in range(0, 28):
    M[28, i] = lcg[i + 1] ** 3
for i in range(0, 28):
    M[29, i] = lcg[i + 2]
M[28, 28] = 1
M[29, 29] = 2 ** 230
v = M.LLL()[0]
e1 = v[0]
a = (lcg[2] - e1) * inverse(lcg[1] ** 3, n) % n

a2 = bin(a)[2:]
length = len(a2)

max_1 = 0
for i in range(len(a2)):
    if a2[i] == '1':
        max_1 += 1

MM = Matrix(ZZ, max_1, max_1)
for i in range(max_1 - 1):
    MM[i, i] = 1
for i in range(max_1 - 1):
    MM[i, max_1 - 1] = 2 ** (max_1 - i) * g ** (max_1 - i + 1)
MM[max_1 - 1, max_1 - 1] = 2 ** 100
L = MM.LLL()
k=0
while 1:
    v = L[k]
    s = ''
    t = ''
    j = 0
    for i in range(len(a2)):
        if a2[i] == '0':
            s += 'a'
            t += 'a'
        else:
            s += 'b'
            t += chr(ord('b') + v[j])
            j += 1
    if hash(s) == hash(t):
        r.recvuntil(b'SERVER <INPUT>: ')
        r.send(s)
        r.recv()
        r.send(t)
        r.recv()
        break
    else:k+=1

其他

还有一题ECC打算之后学的时候再复现了，还是太菜了...