2023-0xGame-week4-wp-crypto

比赛记录

[Week 4] Orac1e

题目描述：

2011年被Pwnie Rewards被评为“最具有价值的服务器漏洞”。是时候挑战一下real hacking了！

Hint 1: 强烈建议在本地进行测试，通过之后再来霍霍管理员的小水管！服务器的时间大抵是管够的

题目：

Serve.py：

import os
import string
from hashlib import sha256
from string import ascii_uppercase
from random import shuffle,choice,randint
import socketserver
import signal
import random

class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    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'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

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

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

task.py：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from base64 import *
from Serve import *
from secret import flag


def pad(text):
    tmp = len(text)%16
    pad_num = 16 - tmp
    text += (pad_num)*bytes([pad_num])
    return text

def unpad(text):
    num = int(text[-1])
    if num == 0:return b'False'
    for i in range(1,num+1):
        if int(text[-i]) != num:
            return b'False'
    else:
        tmp = text[:-num]
        return b'Data update'

def encrypt(plain_text, key):
    cipher = AES.new(key, AES.MODE_CBC, iv)
    cipher_text = cipher.encrypt(pad(plain_text))
    return iv + cipher_text

def decrypt(cipher_text, key):
    iv = cipher_text[:AES.block_size]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    tmp = cipher.decrypt(cipher_text[AES.block_size:])
    result = unpad(tmp)
    return result

iv = get_random_bytes(AES.block_size)
key = get_random_bytes(16)

class test(Task):
    def handle(self):
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        enc = encrypt(flag,key)
        self.send(b'Here are the secert:')
        self.send(b64encode(enc))
        self.send(b'May be you can send something to decrypt it?')
        while True:
            data = self.recv()
            try:
                self.send(decrypt(b64decode(data),key))
            except:
                self.send(b'invaild input')

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10005
    server = ForkedServer((HOST, PORT), test)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

一个经典的CBC预言填充攻击，详细原理请见我另一篇博客：

2023-NewStarCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

而本题中，由于有300s限时，因此需要一组一组来恢复明文。

exp：

from Crypto.Util.number import *
from pwn import *
from tqdm import *
from hashlib import sha256
from base64 import b64decode,b64encode

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("43.139.107.237", 10005)
proof_of_work()
r.recvuntil(b"secert:")
r.recvline()
c = b64decode(r.recvline().strip())
blocks = [c[i*16:i*16+16] for i in range(len(c)//16)]


#group3
if(0):
    message = [0 for i in range(16)]
    change_block = [0 for i in range(16)]
    dec_list = [0 for i in range(16)]
    block = blocks
    for j in range(16):
        for i in trange(256):
            r.recvuntil(b"> ")
            change_byte = long_to_bytes(i)
            temp = block[2][:15-j] + long_to_bytes(i)
            for k in range(15-j+1,16):
                temp += long_to_bytes(change_block[k])
            msg = b64encode(block[0] + block[1] + temp + block[3])
            r.sendline(msg)
            res = r.recvline()
            if(b"False" not in res):
                if(j < 2):
                    if(i != block[2][-j-1]):
                        dec_list[15-j] = i ^ (j+1)
                        message[15-j] = (dec_list[15-j] ^ block[2][-j-1])
                        for k in range(j+1):
                            change_block[15-k] = dec_list[15-k] ^ (j+2)
                        break
                else:
                    dec_list[15-j] = i ^ (j+1)
                    message[15-j] = (dec_list[15-j] ^ block[2][-j-1])
                    for k in range(j+1):
                        change_block[15-k] = dec_list[15-k] ^ (j+2)
                    break 
        print(message)
#[99, 48, 50, 102, 52, 53, 57, 125, 8, 8, 8, 8, 8, 8, 8, 8]
#c02f459}


#group2
if(0):
    message = [0 for i in range(16)]
    change_block = [0 for i in range(16)]
    dec_list = [0 for i in range(16)]
    block = blocks
    for j in range(16):
        for i in trange(256):
            r.recvuntil(b"> ")
            change_byte = long_to_bytes(i)
            temp = block[1][:15-j] + long_to_bytes(i)
            for k in range(15-j+1,16):
                temp += long_to_bytes(change_block[k])
            msg = b64encode(block[0] + temp + block[1])
            r.sendline(msg)
            res = r.recvline()
            if(b"False" not in res):
                if(j < 2):
                    if(i != block[1][-j-1]):
                        dec_list[15-j] = i ^ (j+1)
                        message[15-j] = (dec_list[15-j] ^ block[1][-j-1])
                        for k in range(j+1):
                            change_block[15-k] = dec_list[15-k] ^ (j+2)
                        break
                else:
                    dec_list[15-j] = i ^ (j+1)
                    message[15-j] = (dec_list[15-j] ^ block[1][-j-1])
                    for k in range(j+1):
                        change_block[15-k] = dec_list[15-k] ^ (j+2)
                    break 
        print(message)
#[48, 51, 49, 49, 99, 52, 102, 50, 49, 100, 54, 55, 54, 100, 50, 98]
#0311c4f21d676d2b

#group1
if(1):
    message = [0 for i in range(16)]
    change_block = [0 for i in range(16)]
    dec_list = [0 for i in range(16)]
    block = blocks
    for j in range(16):
        for i in trange(256):
            r.recvuntil(b"> ")
            change_byte = long_to_bytes(i)
            temp = block[0][:15-j] + long_to_bytes(i)
            for k in range(15-j+1,16):
                temp += long_to_bytes(change_block[k])
            msg = b64encode(temp + block[1])
            r.sendline(msg)
            res = r.recvline()
            if(b"False" not in res):
                if(j < 2):
                    if(i != block[0][-j-1]):
                        dec_list[15-j] = i ^ (j+1)
                        message[15-j] = (dec_list[15-j] ^ block[0][-j-1])
                        for k in range(j+1):
                            change_block[15-k] = dec_list[15-k] ^ (j+2)
                        break
                else:
                    dec_list[15-j] = i ^ (j+1)
                    message[15-j] = (dec_list[15-j] ^ block[0][-j-1])
                    for k in range(j+1):
                        change_block[15-k] = dec_list[15-k] ^ (j+2)
                    break 
        print(message)
#[0, 0, 0, 0, 0, 0, 123, 52, 55, 53, 98, 49, 97, 55, 99, 52]
#{475b1a7c4
    

#0xGame{475b1a7c40311c4f21d676d2bc02f459}

[Week 4] LLL-Third Blood

题目描述：

第三滴血，一样的味道，一样的构造，陌生的题目，管理员岂能如此粗心大意！

Hint 1: 找到数学等式，构造矩阵，LLL启动（枯燥无味的密码学.jpg）

Hint 2: DSA

Hint 3: HNP——在0xGame结束之际再签个名呗

题目：

DSA.py：

from Crypto.Util.number import *
from random import getrandbits,randint
from hashlib import sha1
from secret import pri_key

class DSA:
    def __init__(self):
        self.q = getPrime(160)
        while True:
            tmp = self.q*getrandbits(864)
            if isPrime(tmp+1):
                self.p = tmp+1
                break
        self.x = pri_key
        assert self.p%self.q == 1
        h = randint(1,self.p-1)
        self.g = pow(h,(self.p-1)//self.q,self.p)
        self.y = pow(self.g,self.x,self.p)

    def sign(self,m):
        H = bytes_to_long(sha1(m).digest())
        k = getrandbits(128)
        r = pow(self.g,k,self.p)%self.q
        s = (inverse(k,self.q)*(H+r*self.x))%self.q
        return (s,r)

    def verify(self,m,s_,r_):
        H = bytes_to_long(sha1(m).digest())
        u1 = (inverse(s_,self.q)*H)%self.q
        u2 = (inverse(s_,self.q)*r_)%self.q
        r = (pow(self.g,u1,self.p)*pow(self.y,u2,self.p))%self.p%self.q
        if r == r_:
            return True
        else:
            return False

task.py：

import os
import string
import random
from hashlib import sha256
from string import ascii_uppercase
from random import shuffle,choice,randint
import socketserver
import signal
from DSA import *
from secret import flag
GAME = DSA()

MENU = """
  Welcome_to_Final_Chanllange!
/----------------------------\\
|          options           |
| [S]ign                     |
| [V]erify                   |
| [C]heck answer             |
\\---------------------------/
"""

class Task(socketserver.BaseRequestHandler):
    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            return False
        return True

    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'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def timeout_handler(self, signum, frame):
        raise TimeoutError

    def handle(self):
        signal.signal(signal.SIGALRM, self.timeout_handler)
        signal.alarm(300)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return
        self.send(MENU.encode())
        self.send(b'Here are your public key:')
        self.send(f'q={GAME.q}\np={GAME.p}\ng={GAME.g}\ny={GAME.y}'.encode())
        while True:
            self.send(b'What you want to choice?')
            code = self.recv()
            
            if code == b'S':
                self.send(b'What you want to sign?')
                msg = self.recv()
                if msg == b'admin':
                    self.send(b'Permission denied!')
                    self.send(b'Are you trying hack me?No way!')
                    quit()
                self.send(b'Here are your signature:')
                s,r = GAME.sign(msg)
                self.send(f's = {s}'.encode())
                self.send(f'r = {r}'.encode())

            elif code == b'V':
                self.send(b"Let's check your signature.")
                self.send(b'Tell me your message:')
                msg = self.recv()
                self.send(b'Tell me the signature (s,r):')
                s = int(self.recv())
                r = int(self.recv())
                if GAME.verify(msg,s,r):
                    self.send(b'OK,it work')
                else:
                    self.send(b'Something wrong?')

            elif code == b'C':
                self.send(b"Tell me the signature of 'admin'")
                s = int(self.recv())
                r = int(self.recv())
                if GAME.verify(b'admin',s,r):
                    self.send(b'Congratulations!You are Master of Cryptography!')
                    self.send(b'Here are your flag:')
                    self.send(flag)
                    quit()
                else:
                    self.send(b'It seems Something wrong?')
            else:
                self.send(b'invaild input')

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

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

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

本题中DSA是标准实现，没有改动过的地方。因此主要分析一下题目任务：

• 连接上靶机后，开始限时300s
• 通过proof后，靶机下发DSA的公钥(p,q,g,y)，然后开始交互
• 选择”S”，可以对除了”admin”的任何消息进行签名，并获得签名值(s,r)
• 选择”V”，可以对消息和签名值进行验签
• 选择”C”，可以提交一组签名值。如果该签名值与”admin”验签正确，则得到flag

而我们不能对”admin”直接签名，因此这道题的主要目的就是还原DSA的私钥x，从而自己构造出符合要求的”admin”的签名并传回靶机。而在时间限定范围内，我们可以申请多组不同签名，因此我们有机会构造出HNP结构来还原私钥。在此之前，还是先介绍一下DSA作为预备知识。

DSA

首先要了解一下DSA的具体签名流程：

• 选取一个素数q，并以q为基础生成一个素数p，满足q整除p-1
• 生成一个模p下的q阶元素g
• 选取一个(0,q)的数x作为私钥，并生成y=g^x % p
• 此时所有密钥生成完毕，公钥为(p、q、g、y)，私钥为x

然后是签名与验签过程。

签名：

• 首先生成一个(0,q)的随机数k，k即为本次签名的临时密钥
• 计算待签名消息m的哈希值H(m)
• 计算签名值(r,s)如下：

$$r = (g^k \quad (mod\;p)) \quad(mod\;q)$$ $$s =(H(m) + xr)k^{-1} \quad (mod\;q)$$

验签：

• 计算待验签消息m的哈希值H(m)，并计算s^(-1) %q
• 进行如下操作来验证签名是否正确：

$$r = g^{H(m)*s^{-1}}y^{r*s^{-1}} \quad (mod\;p) \quad(mod\;q)$$

如果相等则验签正确。

之所以正确，其原理主要是：

$$k =(H(m) + xr)s^{-1} \quad (mod\;q)$$

而由于g是q阶元素，所以有：

$$g^{a} \equiv g^{a\; modq} \quad (mod\;p)$$

因此验签正确性得以证明。

HNP

那么显然，由DSA的签名流程，我们可以发现一个式子：

$$s =(H(m) + xr)k^{-1} \quad (mod\;q)$$

将其变形为：

$$k =(H(m) + xr)s^{-1} \quad (mod\;q)$$

然后将模等式转化为等式，并展开：

$$k =(H(m) + xr)s^{-1} + tq$$ $$k =H(m)s^{-1} + xrs^{-1} + tq$$

发现可以写成如下形式：

$$k =(rs^{-1})x + s^{-1}H(m) + tq$$

而由于我们可以申请多组签名，而只有临时密钥k改变，私钥x不变，因此有多组如下等式：

$$k_i =(r_is_i^{-1})x + s_i^{-1}H(m_i) + t_iq$$

以这样的多组等式为基础，我们可以构造如下格：

$$\left( \begin{matrix} q & & & & & & \\ &q & & & & & \\ & &... & & & & \\ & & &q & & & \\ & & & &q & & \\ r_1s_1^{-1} &r_2s_2^{-1} & &r_{i-1}s_{i-1}^{-1} &r_is_i^{-1} &1 & \\ s_1^{-1}H(m_1) & s_2^{-1}H(m_2) & & s_{i-1}^{-1}H(m_{i-1}) & s_i^{-1}H(m_i) & &1 \\ \end{matrix} \right)$$

这个格具有如下线性关系：

$$(t_1,t_2,...t_{i-1},t_i,x,1)* \left( \begin{matrix} q & & & & & & \\ &q & & & & & \\ & &... & & & & \\ & & &q & & & \\ & & & &q & & \\ r_1s_1^{-1} &r_2s_2^{-1} & &r_{i-1}s_{i-1}^{-1} &r_is_i^{-1} &1 & \\ s_1^{-1}H(m_1) & s_2^{-1}H(m_2) & & s_{i-1}^{-1}H(m_{i-1}) & s_i^{-1}H(m_i) & &1 \\ \end{matrix} \right) = (k_1,k_2,...k_{i-1},k_i,x,1)$$

因此LLL就能得到含有x的向量，得到x后就可以自行生成一组正确的对”admin”的签名了。

exp：

from Crypto.Util.number import *
from Pwn4Sage.pwn import *
from tqdm import *
from hashlib import sha256,sha1
import string

#context.log_level = 'debug'

def proof_of_work():
	table = string.digits + string.ascii_letters
	temp = r.recvuntil(b"sha256(XXXX+")
	temp = r.recvline()
	suffix = temp[:16].decode()
	hex1 = temp[20:].strip().decode()
	for i in tqdm(table):
		for j in table:
			for k in table:
				for m in table:
					temp1 = i+j+k+m
					if(sha256((temp1+suffix).encode()).hexdigest() == hex1):
						r.sendline(temp1.encode())
						return

r = remote("43.139.107.237", 10004)
proof_of_work()

r.recvuntil(b"public key:")
r.recvline()
q = int(r.recvline().strip().decode()[2:])
p = int(r.recvline().strip().decode()[2:])
g = int(r.recvline().strip().decode()[2:])
y = int(r.recvline().strip().decode()[2:])


# HNP
A = []
B = []
for i in trange(100):
    r.recvuntil(b"> ")
    r.sendline(b"S")
    r.recvuntil(b"> ")
    m = str(i).encode()
    r.sendline(m)
    r.recvuntil(b"signature:")
    r.recvline()

    S = int(r.recvline().strip().decode()[4:])
    R = int(r.recvline().strip().decode()[4:])
    A.append(inverse(S,q)*R % q)
    B.append(inverse(S,q)*bytes_to_long(sha1(m).digest()) % q)
#print(A)
#print(B)

K = 2^128
length = 100
L = Matrix(ZZ, length+2,length+2)

for i in range(length):
    L[i,i] = q
    L[length,i] = A[i]
    L[length+1,i] = B[i]
L[length,length] = 1
L[-1,-1] = 1
res = L.LLL()
x = int(res[0][-2])
#print(x)


# Sign
msg = b"admin"
R = g % p % q
S = bytes_to_long(sha1(msg).digest()) + x*R % q
r.recvuntil(b"> ")
r.sendline(b"C")
r.recvuntil(b"> ")
r.sendline(str(S).encode())
r.recvuntil(b"> ")
r.sendline(str(R).encode())
r.recvline()
r.recvline()
print(r.recvline().strip().decode())

#0xGame{31260c7522632a69031d07133aedebfe}

[Week 4] Danger Leak

题目描述：

时间紧任务重，我们的嗨客情急之下偷到了一部分密钥的信息，但没完全偷完——泪如雨下。幸运的是，我们找到了其中的部分数学关系。

题目：

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

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
while True:
    M = getrandbits(954)
    d0 = getrandbits(70)
    d1 = getrandbits(60)
    d = M * d1 + d0
    e = inverse(d, (p - 1) * (q - 1))
    if GCD(d,phi) == 1:
    	break


c = pow(m,e,n)
print(f'n = {n}')
print(f'e = {e}', )
print(f'c = {c}')
print(f'leak={M}')

'''
n = 20890649807098098590988367504589884104169882461137822700915421138825243082401073285651688396365119177048314378342335630003758801918471770067256781032441408755600222443136442802834673033726750262792591713729454359321085776245901507024843351032181392621160709321235730377105858928038429561563451212831555362084799868396816620900530821649927143675042508754145300235707164480595867159183020730488244523890377494200551982732673420463610420046405496222143863293721127847196315699011480407859245602878759192763358027712666490436877309958694930300881154144262012786388678170041827603485103596258722151867033618346180314221757
e = 18495624691004329345494739768139119654869294781001439503228375675656780205533832088551925603457913375965236666248560110824522816405784593622489392063569693980307711273262046178522155150057918004670062638133229511441378857067441808814663979656329118576174389773223672078570346056569568769586136333878585184495900769610485682523713035338815180355226296627023856218662677851691200400870086661825318662718172322697239597148304400050201201957491047654347222946693457784950694119128957010938708457194638164370689969395914866589468077447411160531995194740413950928085824985317114393591961698215667749937880023984967171867149
c = 7268748311489430996649583334296342239120976535969890151640528281264037345919563247744198340847622671332165540273927079037288463501586895675652397791211130033797562320858177249657627485568147343368981852295435358970875375601525013288259717232106253656041724174637307915021524904526849025976062174351360431089505898256673035060020871892556020429754849084448428394307414301376699983203262072041951835713075509402291301281337658567437075609144913905526625759374465018684092236818174282777215336979886495053619105951835282087487201593981164477120073864259644978940192351781270609702595767362731320959397657161384681459323
leak=136607909840146555806361156873618892240715868885574369629522914036807393164542930308166609104735002945881388216362007941213298888307579692272865700211608126496105057113506756857793463197250909161173116422723246662094695586716106972298428164926993995948528941241037242367190042120886133717
'''

并且给出了一篇对应论文。在论文中可以定位到：

可以看到，其构造了一个模leak*e下的多项式，并用三元coppersmith求对应小根，求出的小根中，由于z=p+q-1，因此可以分解n。

那么也就是调用一下多元copper的small_root，但是需要将上界稍微设置的松散一点。

exp：

import itertools
from gmpy2 import iroot
from Crypto.Util.number import *
 
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
 
    R = f.base_ring()
    N = R.cardinality()
 
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
 
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
 
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
 
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
 
    B = B.dense_matrix().LLL()
 
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
 
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 20890649807098098590988367504589884104169882461137822700915421138825243082401073285651688396365119177048314378342335630003758801918471770067256781032441408755600222443136442802834673033726750262792591713729454359321085776245901507024843351032181392621160709321235730377105858928038429561563451212831555362084799868396816620900530821649927143675042508754145300235707164480595867159183020730488244523890377494200551982732673420463610420046405496222143863293721127847196315699011480407859245602878759192763358027712666490436877309958694930300881154144262012786388678170041827603485103596258722151867033618346180314221757
e = 18495624691004329345494739768139119654869294781001439503228375675656780205533832088551925603457913375965236666248560110824522816405784593622489392063569693980307711273262046178522155150057918004670062638133229511441378857067441808814663979656329118576174389773223672078570346056569568769586136333878585184495900769610485682523713035338815180355226296627023856218662677851691200400870086661825318662718172322697239597148304400050201201957491047654347222946693457784950694119128957010938708457194638164370689969395914866589468077447411160531995194740413950928085824985317114393591961698215667749937880023984967171867149
c = 7268748311489430996649583334296342239120976535969890151640528281264037345919563247744198340847622671332165540273927079037288463501586895675652397791211130033797562320858177249657627485568147343368981852295435358970875375601525013288259717232106253656041724174637307915021524904526849025976062174351360431089505898256673035060020871892556020429754849084448428394307414301376699983203262072041951835713075509402291301281337658567437075609144913905526625759374465018684092236818174282777215336979886495053619105951835282087487201593981164477120073864259644978940192351781270609702595767362731320959397657161384681459323
leak=136607909840146555806361156873618892240715868885574369629522914036807393164542930308166609104735002945881388216362007941213298888307579692272865700211608126496105057113506756857793463197250909161173116422723246662094695586716106972298428164926993995948528941241037242367190042120886133717

PR.<x,y,z> = PolynomialRing(Zmod(leak*e))
f = e*x - n*y + y*z - 1
bound = (2^71, 2^1020, 2^1026)
solves = small_roots(f, bound, m=3,d=3)

pplusq = int(solves[0][2])+1
pminusq = iroot(pplusq**2-4*n,2)[0]
p = (pplusq + pminusq)//2
q = n//p
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(int(pow(c,d,n))))

#0xGame{a9e1f260f845be84f56ff06b165deb80}

其实这道题我自己调参数一直出不了结果，然后询问了出题人，出题人告诉我他的bound设置的是：

(2^100, 2^1024, 2^1024)

这样确实能出，但是实际上求出的z是大于这个2^1024这个上界的，确实有点奇怪。

[Week 4] Normal ECC

题目描述：

青春Bob梦得到他的电子Alice吗？

Hint 1: assert E.order() == p

题目：

from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from random import getrandbits
from hashlib import md5
from secret import flag,M

def MD5(m):return md5(str(m).encode()).hexdigest()
assert '0xGame{'+MD5(M[0])+'}' == flag
p = 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a = 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b = 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
assert p>a
assert p>b
E = EllipticCurve(GF(p),[a,b])
assert E.order() == p
M = E(M)

G = E.random_point()
k = getPrime(int(128))
K = k*G
r = getrandbits(64)

C1 = M + r*K
C2 = r*G

print(f'p={p}\na={a}\nb={b}')
print(f'G={G.xy()}')
print(f'K={K.xy()}')
print(f'C1={C1.xy()}')
print(f'C2={C2.xy()}')

'''
p=11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a=490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b=7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
G=(4045939664332192284605924284905750194599514115248885617006435833400516258314135019849306107002566248677228498859069119557284134574413164612914441502516162, 2847794627838984866808853730797794758944159239755903652092146137932959816137006954045318821531984715562135134681256836794735388745354065994745661832926404)
K=(9857925495630886472871072848615069766635115253576843197716242339068269151167072057478472997523547299286363591371734837904400286993818976404285783613138603, 9981865329938877904579306200429599690480093951555010258809210740458120586507638100468722807717390033784290215217185921690103757911870933497240578867679716)
C1=(4349662787973529188741615503085571493571434812105745603868205005885464592782536198234863020839759214118594741734453731681116610298272107088387481605173124, 10835708302355425798729392993451337162773253000440566333611610633234929294159743316615308778168947697567386109223430056006489876900001115634567822674333770)
C2=(5193866657417498376737132473732737330916570240569047910293144235752602489388092937375844109374780050061859498276712695321973801207620914447727053101524592, 684299154840371832195648774293174908478389728255128448106858267664482339440737099810868633906297465450436417091302739473407943955874648486647511119341978)
'''

题目提示就是说明是Smart attack，因此可以有两种思路：

• Smart attack求出私钥k，然后按正常椭圆曲线解密流程解密得到M
• Smart attack直接求出r，然后对应减去rK即可

这里我选择的是第一种，更符合椭圆曲线加解密的基本流程，不过区别不大。

exp：

from Crypto.Util.number import *
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()

p=11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a=490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b=7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
G=(4045939664332192284605924284905750194599514115248885617006435833400516258314135019849306107002566248677228498859069119557284134574413164612914441502516162, 2847794627838984866808853730797794758944159239755903652092146137932959816137006954045318821531984715562135134681256836794735388745354065994745661832926404)
K=(9857925495630886472871072848615069766635115253576843197716242339068269151167072057478472997523547299286363591371734837904400286993818976404285783613138603, 9981865329938877904579306200429599690480093951555010258809210740458120586507638100468722807717390033784290215217185921690103757911870933497240578867679716)
C1=(4349662787973529188741615503085571493571434812105745603868205005885464592782536198234863020839759214118594741734453731681116610298272107088387481605173124, 10835708302355425798729392993451337162773253000440566333611610633234929294159743316615308778168947697567386109223430056006489876900001115634567822674333770)
C2=(5193866657417498376737132473732737330916570240569047910293144235752602489388092937375844109374780050061859498276712695321973801207620914447727053101524592, 684299154840371832195648774293174908478389728255128448106858267664482339440737099810868633906297465450436417091302739473407943955874648486647511119341978)
E = EllipticCurve(GF(p),[a,b])

P = E(G)
Q = E(K)

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

k = int(SmartAttack(P, Q, p))

M = E(C1) - k*E(C2)
print('0xGame{'+MD5( M.xy()[0] )+'}')

#0xGame{6f2b3accf11a8cb7a9d3c7b159bc6c6c}