2024-CISCN-wp-crypto

还是更个wp吧。

day1

hash

题目描述：

你能仅仅通过一个Python2.7自带的hash函数的输出，计算出它的原象的sha384哈希值吗？

题目：

#!/usr/bin/python2
# Python 2.7 (64-bit version)
from secret import flag
import os, binascii, hashlib
key = os.urandom(7)
print hash(key)
print int(hashlib.sha384(binascii.hexlify(key)).hexdigest(), 16) ^ int(binascii.hexlify(flag), 16)

可以看到密文其实就是flag和key的sha384做异或而已，所以关键就是找到key，而题目给出了以下几个关于key的信息：

• 长度为7字节
• hash(key)在Python 2.7 (64-bit version)下的值

由于key仅有7字节，实在是太像mitm了，所以自然的思路是hash的过程是可以逐步逆回去的，从而构造一个3.5-3.5的mitm，复杂度就可以接受。

所以是先要找到hash的具体实现，搜2.7的release发现其实有个可以在python3实现的py2.7的hash，可以比较轻松的看到源码如下：

"""
Compatibility methods to support Python 2.7 style hashing in Python 3.X+

This is designed for compatibility not performance.
"""

import ctypes
import math

def hash27(value):
    """
    Wrapper call to Hash.hash()

    Args:
        value: input value

    Returns:
        Python 2.7 hash
    """

    return Hash.hash(value)

class Hash(object):
    """
    Various hashing methods using Python 2.7's algorithms
    """

    @staticmethod
    def hash(value):
        """
        Returns a Python 2.7 hash for a value.

        Args:
            value: input value

        Returns:
            Python 2.7 hash
        """

        if isinstance(value, tuple):
            return Hash.thash(value)
        if isinstance(value, float):
            return Hash.fhash(value)
        if isinstance(value, int):
            return hash(value)
        if isinstance(value, ("".__class__, u"".__class__, bytes)) or type(value).__name__ == "buffer":
            return Hash.shash(value)

        raise TypeError("unhashable type: '%s'" % (type(value).__name__))

    @staticmethod
    def thash(value):
        """
        Returns a Python 2.7 hash for a tuple.

        Logic ported from the 2.7 Python branch: cpython/Objects/tupleobject.c
        Method: static long tuplehash(PyTupleObject *v)

        Args:
            value: input tuple

        Returns:
            Python 2.7 hash
        """

        length = len(value)

        mult = 1000003

        x = 0x345678
        for y in value:
            length -= 1

            y = Hash.hash(y)
            x = (x ^ y) * mult
            mult += 82520 + length + length

        x += 97531

        # Convert to C type
        x = ctypes.c_long(x).value

        if x == -1:
            x = -2

        return x

    @staticmethod
    def fhash(value):
        """
        Returns a Python 2.7 hash for a float.

        Logic ported from the 2.7 Python branch: cpython/Objects/object.c
        Method: long _Py_HashDouble(double v)

        Args:
            value: input float

        Returns:
            Python 2.7 hash
        """

        fpart = math.modf(value)
        if fpart[0] == 0.0:
            return hash(int(fpart[1]))

        v, e = math.frexp(value)

        # 2**31
        v *= 2147483648.0

        # Top 32 bits
        hipart = int(v)

        # Next 32 bits
        v = (v - float(hipart)) * 2147483648.0

        x = hipart + int(v) + (e << 15)

        # Convert to C long type
        x = ctypes.c_long(x).value

        if x == -1:
            x = -2

        return x

    @staticmethod
    def shash(value):
        """
        Returns a Python 2.7 hash for a string.

        Logic ported from the 2.7 Python branch: cpython/Objects/stringobject.c
        Method: static long string_hash(PyStringObject *a)

        Args:
            value: input string

        Returns:
            Python 2.7 hash
        """

        length = len(value)

        if length == 0:
            return 0

        mask = 0xffffffffffffffff
        x = (Hash.ordinal(value[0]) << 7) & mask
        for c in value:
            x = (1000003 * x) & mask ^ Hash.ordinal(c)

        x ^= length & mask

        # Convert to C long type
        x = ctypes.c_long(x).value

        if x == -1:
            x = -2

        return x

    @staticmethod
    def ordinal(value):
        """
        Converts value to an ordinal or returns the input value if it's an int.

        Args:
            value: input

        Returns:
            ordinal for value
        """

        return value if isinstance(value, int) else ord(value)

由于传入的是7个字符的字节流，所以定位到：

def shash(value):
        """
        Returns a Python 2.7 hash for a string.

        Logic ported from the 2.7 Python branch: cpython/Objects/stringobject.c
        Method: static long string_hash(PyStringObject *a)

        Args:
            value: input string

        Returns:
            Python 2.7 hash
        """

        length = len(value)

        if length == 0:
            return 0

        mask = 0xffffffffffffffff
        x = (Hash.ordinal(value[0]) << 7) & mask
        for c in value:
            x = (1000003 * x) & mask ^ Hash.ordinal(c)

        x ^= length & mask

        # Convert to C long type
        x = ctypes.c_long(x).value

        if x == -1:
            x = -2

        return x

可以看出这个hash函数是逐字符的，所以完全可以从密文逆这个过程，然而这样就只能拆成3+4或者4+3，因为建2^32数量级的字典不太现实，所以我选择爆第一个字符，然后用3+3去mitm，自己手动多进程，大概需要半个多小时可以出来。具体怎么实现的可以参考solver。

之所以这个过程可以逆，是因为与mask做与运算其实完全等价于模2^64，所以乘1000003也就可以变成对应求逆元

exp：

from itertools import *
from tqdm import *
from Crypto.Util.number import *
from gmpy2 import *

c = 7457312583301101235

#mitm
length = 7
mask = 0xffffffffffffffff
T = invert(1000003 , mask + 1)

for i in trange(256):
    dic = {}

    for a in product([i for i in range(256)] , repeat=3):
        x = (i << 7) & mask
        x = (1000003 * x) & mask ^ i
        tt = list(a)
        for char in tt:
            x = (1000003 * x) & mask ^ char       
        dic[x] = tt
    
    for b in product([i for i in range(256)] , repeat=3):
        tt = list(b)
        cc = c ^ (length & mask)
        for char in tt:
            cc = cc ^ char
            cc = cc * T & mask  
        if(cc in dic.keys()):
            print(i , dic[cc] , tt)
            exit()

得到结果：

#from py27hash.hash import hash27
from Crypto.Util.number import *

cipher = 13903983817893117249931704406959869971132956255130487015289848690577655239262013033618370827749581909492660806312017
key = bytes([93,140, 240, 63,90, 8, 82])
import os, binascii, hashlib
print(long_to_bytes(int(hashlib.sha384(binascii.hexlify(key)).hexdigest(), 16) ^ cipher))

#flag{bdb537aa-87ef-4e95-bea4-2f79259bdd07}

还有个比较有趣的思路是使用LLL，不过不在这里展开了

what mouth

题目描述：

Here is running a key exchange system, but there are someone who has an access to the whole process.

题目：

#! /usr/bin/env python3

import os
import binascii
from random import random

from flask import request
import json
from libnum import n2s, s2n
from secret import flag, K_as, K_bs
from flask import Flask
from hashlib import md5
import time
from Crypto.Cipher import AES
from os import urandom

# from rpc.restful_service import TodoList, Todo, Datatype_es, Datatype_byte, Datatype_classify
# from rpc.rpc_service import *

app = Flask(__name__)

flag += '\x00' * (- len(flag) % 16)

# from gevent.pywsgi import WSGIServer
A = md5(b'A').hexdigest()[:16]
B = md5(b'B').hexdigest()[:16]
S = md5(b'S').hexdigest()[:16]
K_sc = {A: K_as, B: K_bs}
name2hex = {"A": A, "B": B, "S": S}
# tokens = json.loads(open('token.txt', 'r').read())
hex_chars = set(list('0123456789abcdefg'))

last_time = time.time()

history = {}
keys = {}
if os.path.exists('keys.txt'):
    try:
        keys = json.loads(open('keys.txt', 'r').read())
    except Exception as e:
        keys = {}
        print(e)

if os.path.exists('K_sc.txt'):
    tag = 0
    cur_sc = {}
    try:
        cur_sc = json.loads(open("K_sc.txt", 'r').read())
        tag = 1
    except Exception as e:
        tag = 0
        print(e)
    if tag:
        K_sc.update(cur_sc)


def update_keys(cur_token, left, right, cur_key):
    global keys
    if cur_token not in keys:
        keys[cur_token] = {left: {right: cur_key}}
    else:
        cur_dict = keys[cur_token]
        if left not in cur_dict:
            cur_dict[left] = {right: cur_key}
        else:
            cur_dict[left][right] = cur_key
    cur_time = time.time()
    global last_time
    if cur_time - last_time > 666:
        open('keys.txt', 'w').write(json.dumps(keys))
        last_time = cur_time
    return True


def check_fresh(t):
    cur = time.time()
    # if t > cur:
    #     return False
    if cur - t > 24:
        return False
    return True


def get_token(args):
    cur_token = args.get('token', None)
    if cur_token is None:
        return False, {"message": "Add your Token"}
    cur_token = cur_token.ljust(16, '0')[:16]
    for char in cur_token:
        if char not in hex_chars:
            return False, {"message": "Your token should be made of hex"}
    return True, cur_token


def add_to_history(cur_log, cur_token):
    global history
    if cur_token in history:
        history[cur_token].append(cur_log)
    else:
        history[cur_token] = [cur_log]


def dec_and_split_message(cli, message, need_hex=False):
    message = binascii.unhexlify(message)
    scheme = AES.new(binascii.unhexlify(K_sc[cli]), AES.MODE_ECB)
    message = scheme.decrypt(message)
    if need_hex:
        t, target, cur_key = int(message[:16].hex(), 16), message[16: 24].hex(), message[32: 48].hex()
    else:
        t, target, cur_key = int(message[:16].hex(), 16), message[16: 24], message[32: 48]
    return t, target, cur_key


def send_to_client(cur_token, target, message):  # all of the inputs are hex
    if not len(message) == 16 * 3 * 2:
        return "Your message is not valid"
    cur_log = f'{time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())}: S -> {target}: {message}'
    add_to_history(cur_log, cur_token)
    t, friend, cur_key = dec_and_split_message(target, message, need_hex=True)
    if not check_fresh(t):
        return "This is an old message, get out"
    return update_keys(cur_token, target, friend, cur_key)


def send_to_server(cur_token, orig_message):
    if not len(orig_message) == 16 * 3 * 2 + 16:
        return "Your message is not valid"
    sender, message = orig_message[0: 16], orig_message[16:]
    t, target, cur_key = dec_and_split_message(sender, message)
    if not check_fresh(t):
        return "This is an old message, get out"

    cur_log = f'{time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())}: {sender} -> S: {orig_message}'
    add_to_history(cur_log, cur_token)
    suffix = os.urandom(8)
    wait_to_send_m = n2s(int(time.time())).rjust(16, b'0') + binascii.unhexlify(sender) + suffix + cur_key
    target = target.hex()
    scheme = AES.new(binascii.unhexlify(K_sc[target]), AES.MODE_ECB)
    cipher = scheme.encrypt(wait_to_send_m).hex()
    send_to_client(cur_token, target, cipher)
    return True


def send_message(cur_token, target, message):
    if target == S:
        return send_to_server(cur_token, message)
    else:
        return send_to_client(cur_token, target, message)


def exchange_key(cur_token):
    k_ab = os.urandom(16)
    if random() > 0.5:
        sender = A
        target = B
    else:
        sender = B
        target = A
    suffix = os.urandom(8)
    message = n2s(int(time.time())).rjust(16, b'0') + binascii.unhexlify(target) + suffix + k_ab
    scheme = AES.new(binascii.unhexlify(K_sc[sender]), AES.MODE_ECB)
    cipher = scheme.encrypt(message).hex()
    message = sender + cipher
    ans = send_message(cur_token, S, message)
    if ans is not True:
        return ans
    update_keys(cur_token, sender, target, k_ab.hex())
    return {'message': 'A and B have completed key exchange!'}


@app.route('/A_and_B', methods=['GET'])
def index():
    # predict_impl = predict.predict(rows_limit=10000, version=0.02, debug=1)
    # predict_impl.get_data()
    # predict_impl.read_origin_table(0)
    bol, message = get_token(request.args)
    if not bol:
        return {"message": message}
    cur_token = message
    return exchange_key(cur_token)


@app.route('/register', methods=['GET'])  # get token and
def register():
    # cur_token = os.urandom(16).hex()
    bol, message = get_token(request.args)
    if not bol:
        return {"message": message}
    cur_token = message
    if cur_token in K_sc:
        cur_key = binascii.unhexlify(K_sc[cur_token])
    else:
        cur_key = os.urandom(16)
        K_sc[cur_token] = cur_key.hex()
    cur_time = time.time()
    global last_time
    if cur_time - last_time > 666:
        open("K_sc.txt", 'w').write(json.dumps(K_sc))
        last_time = cur_time
    return {'token': cur_token, 'key_to_server': cur_key.hex()}


@app.route('/send_message', methods=['GET'])
def execute_protocol():
    bol, message = get_token(request.args)
    if not bol:
        return {"message": message}
    cur_token = message
    target = request.args.get('to')
    message = request.args.get('message')
    send_message(cur_token, name2hex[target], message)
    return {"message": f"You have sent {message} to {target}"}


@app.route('/view_history', methods=['GET'])
def list_history():
    bol, message = get_token(request.args)
    if not bol:
        return {"message": message}
    cur_token = message
    if cur_token not in history:
        return {"message": "Invalid token or this token has not generated any histories."}
    cur_histories = history[cur_token]
    return_histories = cur_histories[0:]
    return_histories.reverse()

    return {"history": return_histories}


@app.route('/send_flag', methods=['GET'])
def send_flag():
    bol, message = get_token(request.args)
    if not bol:
        return {"message": message}
    cur_token = message
    if random() > 0.5:
        sender = A
        target = B
    else:
        sender = B
        target = A
    if keys[cur_token][sender][target] != keys[cur_token][target][sender]:
        exchange_key(cur_token)
        return {"message": "Keys between A and B are different! There must be something malicious in our system!"}
    cur_key = binascii.unhexlify(keys[cur_token][sender][target])
    scheme = AES.new(cur_key, AES.MODE_ECB)
    cipher = scheme.encrypt(flag.encode()).hex()
    cur_log = f'{time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())}: {sender} -> {target}: {cipher}'
    add_to_history(cur_log, cur_token)
    return {"message": f'{sender} has sent flag secretly to {target}!'}


if __name__ == '__main__':
    # app.run()
    # app.run(host='0.0.0.0', port=os.environ.get("PORT0"))
    app.run(host='0.0.0.0', port=12138, debug=True)

题目的难度完全在于耐着性子审代码，把所有接口能用的信息看完后，可以发现在register接口里会返回一个key值，而这个key值是：

cur_key = binascii.unhexlify(K_sc[cur_token])

也就是说，自己输入的一个token其实对应了这个key值，也就是一个token对应一个Ksc里面的一个key值。接着看这个Ksc，可以发现如果输入的token就是A或B的话，那么这个key在exchange被调用来了加密信息，并且存在了日志里面。

然后就是最后发送flag密文的过程，可以发现flag对应的AES是用这个密钥加密的：

cur_key = binascii.unhexlify(keys[cur_token][sender][target])

这其实就是共享密钥，而在exchange的过程里可以看到，共享密钥Kab其实是被附加在了消息最后面的，所以解题其实就是：

• 用A/B当作token
• 获取所有密文，用register的key去解密他们，中间对应明文的最后16字节就是Kab
• 用Kab解密掉sender给target的消息就可以得到flag了

调用接口虽然我并不熟悉，但是交给gpt-4o很快就好了，然后具体交互我也就直接手动来调。

exp：

import requests

#A : 7fc56270e7a70fa8
#B : 9d5ed678fe57bcca
#S : 5dbc98dcc983a707

# 设置服务器地址和端口
base_url = 'http://8.147.133.9:44180'

# 注册并获取token和key_to_server
def register(token):
    response = requests.get(f'{base_url}/register', params={'token': token})
    return response.json()

# 进行密钥交换
def exchange_keys(token):
    response = requests.get(f'{base_url}/A_and_B', params={'token': token})
    return response.json()

# 发送消息
def send_message(token, target, message):
    response = requests.get(f'{base_url}/send_message', params={'token': token, 'to': target, 'message': message})
    return response.json()

# 查看历史记录
def view_history(token):
    response = requests.get(f'{base_url}/view_history', params={'token': token})
    return response.json()

# 发送flag
def send_flag(token):
    response = requests.get(f'{base_url}/send_flag', params={'token': token})
    return response.json()

# 示例脚本
if __name__ == '__main__':

    token = "9d5ed678fe57bcca"
    #token = "7fc56270e7a70fa8"
    #token = "5dbc98dcc983a707"

    # 注册获取token和key_to_server
    registration_info = register(token)
    print('Registration Info:', registration_info)

    # 进行密钥交换
    key_exchange_info = exchange_keys(token)
    print('Key Exchange Info:', key_exchange_info)

    # 查看历史记录
    history_info = view_history(token)
    print('History Info:', history_info)

    # 发送flag
    flag_info = send_flag(token)
    print('Flag Info:', flag_info)

对密文解密(密文不多，所以我全部爆破比较简单，不用细分究竟是谁的密文)：

from Crypto.Cipher import AES
from Crypto.Util.number import *
import binascii
import time
from libnum import n2s, s2n

key = "8339eaaef837e5a463db5ad4f6fcecd1"
key = "5fa11352bb62df887404c4da9a8357c9"
#key = "ae787381739c370359f7b12bc6021cf1"

C = ["e8c3f1a327b5e67b8fc73eeb3a5d5d3f0267ce7f5b00633bebb1b1327b873afb690cbc9bfd1f862f1805772df16f05eb",
"c9be89b28aa4da445fbe8690e199d428257eb4f5be7b2835108087e8ef6d5f0c4dbc4118920a055f87e76abcfbf902f2",
"3deb6a1fe50b3ba49b7ce08e5ce33c7b2d22d0cee4d188a8b7fa9a997cd353409c71b7c7fa49ebe3fdf144119721b2a7",
"5e43646a84945c72233a5f7a51fcf8cf6a9f74e17f4c899d666d0c27f55f930913637ecbfa69cd97b5774c470c50e058",
"3b9d8cf65eeec7956660f9bac04e710fbef82065120926bae37041ad3460b11d4f81579434273ac9e49c308f5df991d9",
"5f2b46a3aa41433dc88de139f3a32eb462d15dfa750f7e5dfc7ae8e2d67966c18a783ff0ed3e241e6ccb4b37bdd38d29",
"09f03deb81a541443a5fb66e4b1c4ca24c673603217cc9eb2ad2d5307696694668a77fc9cab1ddf3d73053aec4185801",
"99261428bb61ed97550d73927d717ec109942925568aac53863173e4e53c9674f13bca553dad82392a3dd2c64490faca",
"61e22e0b5b4d2aab7eee244f6e8aa470b4210abcd841c01f0aea9bd0ec0b21897543fa61533606b3b4ea28d86f9eab1a",
"d93759236bbba7c5efa7b5fad686a5f6ba93f33e5ebb0324d909e0b3d8c7749fd117228e25e42d35d3941915d009e4d9",
"ce408bf6cc20856037caa1b451f6f978ef5169a428882628079d96452cf2534018a80d80c1324a59e5c8e5724fc00c19",
"70b49692ac62ec96b59beb0b8b4edba250c3577aa6269e61682d60618e5c543f0e93a10599d55218a2c18308207ddbfc",
"b3ce206d8a044792ad617ece3e9aea6d1a30904bfa7c2e93a5a9f11b94b3abc3cf8901decde3b94a3bf0be30a923549e",
"b3aa85658b5e5c45a1e81dde4694586c178dc8abe97ed43a74d979aa708a5185cb477278ab453d9b5731de6617365576",
"03d35cf155db4e3b0abb1983e36c0463ca466874f3bbe213066f3681754617dc6f62d0be3e14b5fb3a1eb8933b130999"]

scheme = AES.new(binascii.unhexlify(key), AES.MODE_ECB)

for c in C:
    tt = scheme.decrypt(long_to_bytes(int(c,16)))
    keytt = tt[-16:]
    
    for cc in C:
        schemett = AES.new(keytt, AES.MODE_ECB)
        flag = schemett.decrypt(long_to_bytes(int(cc,16)))
        if(b"flag" in flag):
            print(flag)


#flag{7aeeb90b-7cf3-4ade-9600-07a9a5f9ad0b}

其实这个题目还有个很奇怪的地方在于他的hexchar多了个g，不过没啥用：

hex_chars = set(list('0123456789abcdefg'))

这个题目其实是一个A、B、Server三方的密钥交换，初看是个Diffie-Hellman，实际上仔细看这个过程可以发现问题就在于A、B太信任Server了，交换密钥的过程其实是双方把私钥都给Server，然后Server用发送者的私钥解密后，再用接收者的私钥加密发给接收者。

这也就对应了题目描述，因为有个完全可信的第三方在密钥交换中间作用，所以一旦第三方出了什么问题整个系统就完了XD

day2

古典密码

题目：

AnU7NnR4NassOGp3BDJgAGonMaJayTwrBqZ3ODMoMWxgMnFdNqtdMTM9

题目一眼看上去就应该是基于base64编码做了某些加密，之所以会这样说是因为一个很重要的事实：密文长度为56，base64解码刚好长度为42，符合flag{uuid}的形式，所以一个比较自然的思路就是这可能是base64换表过后的结果。

然而转成bit流过后可以发现，他并不符合uuid的如下形式：

flag{********-****-****-****-************}

“不符合”的意思是，”-“没有出现在这几个固定的位置，也就表明这要么不是简单单表代换的码表，要么经过了置换。

但是无论如何肯定是要经过base64解码的，所以先考虑对密文进行一些凯撒之类的代换，然后发现用Atbash可以解出一个经历了某种置换后的flag，然后尝试栅栏就解掉了。

flag：

flag{b2bb0873-8cae-4977-a6de-0e298f0744c3}

OvO

题目描述：

I can only give you my partial e.

题目：

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

nbits = 512
p = getPrime(nbits)
q = getPrime(nbits)
n = p * q
phi = (p-1) * (q-1)
while True:
    kk = getPrime(128)
    rr = kk + 2
    e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1
    if gcd(e, phi) == 1:
        break
m = bytes_to_long(flag)
c = pow(m, e, n)

e = e >> 200 << 200
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

"""
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823
"""

题目e的生成过程是：

$$e = 65537 + ap + (a+2)(n+p+q+1) + 1$$

其中a就是题目的kk，这里方便看写成这样。

题目隐藏了e的低200位，然而从上面式子可以看出，e的主要大小来自于an，所以有：

$$e_h \approx (a+2)n$$

所以做个整除就可以得到a+2的值也就是rr，然后也就自然有了kk的值，然后代回e的式子有：

$$e_hq \approx 65537q + an + (a+2)(nq+n+q^2+q) + q$$

然后就可以在实数域上解出q的高位，之后copper就行。

exp：

from Crypto.Util.number import *

n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823
e1 = e

kk = e//n - 2
rr = kk + 2

PR.<q> = PolynomialRing(RealField(1000))
f = 65537*q + kk * n + rr*(n*q+q^2+n+q) + 1*q - e*q
res = f.roots()

qh = int(res[0][0])
PR.<x> = PolynomialRing(Zmod(n))
f = qh + x
res = f.small_roots(X=2^210,beta=0.499,epsilon = 0.03)

q = GCD(qh+int(res[0]),n)
p = n // q

kk = e1//n - 2
rr = kk + 2
e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1

print(long_to_bytes(int(pow(c,inverse(e,(p-1)*(q-1)),n))))


#flag{b5f771c6-18df-49a9-9d6d-ee7804f5416c}

ezrsa

题目描述：

这又是考了一万遍的RSA部分私钥泄露攻击，但这次可不太一样哦。

题目：

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

m = bytes_to_long(flag)
key = RSA.generate(1024)
passphrase = str(random.randint(0,999999)).zfill(6).encode()
output = key.export_key(passphrase=passphrase).split(b'\n')
for i in range(7, 15):
    output[i] = b'*' * 64
with open("priv.pem", 'wb') as f:
    for line in output:
        f.write(line + b'\n')
with open("enc.txt", 'w') as f:
    f.write(str(key._encrypt(m)))

pem：

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,435BF84C562FE793

9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlh
WiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdD
ig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSI
jLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg==
-----END RSA PRIVATE KEY-----

题目泄露了RSA部分私钥信息，对私钥文件熟悉一点的应该知道泄露的部分应该含有：

• n
• e
• qinvp

然而私钥文件是用3DES加密过的，不过密钥的范围很小，所以可以用私钥文件的标记符、长度类型等作为判断依据去解密，从而把密钥爆破出来是483584，这一部分细节用gpt就好了。

由于这个加密是CBC的，所以依次解密出来后，可以发现正确的值不仅有n、e、qinvp，还有dq的部分LSB，一个分组是8字节，去掉后面的长度标识0240后还剩48bit，所以相当于是要利用这些信息把n分解出来。

由于有：

$$ed_q = 1 + k_1(q-1)$$

把qinvp记为y，那么又有：

$$yq = 1 + k_2p$$

所以有：

$$yq^2 - q = k_2n$$

也就是：

$$yq^2 - q = 0 \quad(mod\;n)$$

然后把两个式子按如下推导过程联立起来

$$(ed_q - 1+ k_1) = k_1q$$ $$yk_1^2q^2 - k_1^2q = 0 \quad(mod\;n)$$ $$y(ed_q - 1+ k_1)^2 - k_1(ed_q - 1+ k_1) = 0 \quad(mod\;n)$$

然后把dq拆成低位和高位表示就可以copper出dq了，由于是模n下的二次方程，所以beta取1，epsilon自己测一测发现0.09就可以出，比较宽松。

然后就开始爆破，得到n的分解后直接把加密的encrypt改成decrypt就行。

提数据：

from Crypto.Cipher import DES3
from Crypto.Protocol.KDF import PBKDF1
from Crypto.Hash import MD5
from Crypto.Util.number import *
import base64
from tqdm import *

# 读取被部分遮盖的私钥文件内容
with open(r"D:\CTF_challs\py\crypto\test\pri.txt", 'rb') as f:
    encrypted_key_data = f.read()

# 从文件内容中提取加密信息部分
def extract_encryption_info(encrypted_key_data):
    lines = encrypted_key_data.split(b'\n')
    proc_type = lines[1].decode()
    dek_info = lines[2].decode()
    iv_hex = dek_info.split(',')[1]
    iv = bytes.fromhex(iv_hex)
    encrypted_data = b'\n'.join(lines[4:-1])
    return iv, encrypted_data

iv, encrypted_data_base64 = extract_encryption_info(encrypted_key_data)
encrypted_data = base64.b64decode(encrypted_data_base64)

# 解密已知部分
def decrypt_known_part(encrypted_key_data, passphrase):
    salt = bytes.fromhex("435BF84C562FE793")

    # 派生密钥
    key = PBKDF1(passphrase, salt, 16, 1, MD5)
    key += PBKDF1(key + passphrase, salt, 8, 1, MD5)
    objenc = DES3.new(key, DES3.MODE_CBC, salt)
    
    # 解密数据
    decrypted_data = objenc.decrypt(encrypted_data)
    return decrypted_data

# 爆破出的密码
#i = 483584
for i in trange(1000000):
    passphrase = str(i).zfill(6).encode()

    decrypted_data = decrypt_known_part(encrypted_key_data, passphrase)

    # 输出解密后的数据
    tt = decrypted_data.hex()
    if(tt[:4] == "3082" and tt[8:12] == "0201"):
        print(i)
        print(tt)

爆破得到p、q、d：

from Crypto.Util.number import *
import gmpy2
from tqdm import tqdm
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from tqdm import *

n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 0x010001
dqlow = 0x8f2363b340e5
y = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989
T = 48

PR.<x> = PolynomialRing(Zmod(n))
dq = (2^T * x) + dqlow

#k = 47793
for k in trange(1,e):
    f = y * (e*(2^T*x+dqlow) - 1 + k)^2 - k * (e*(2^T*x+dqlow) - 1 + k)
    f = f.monic()
    root = f.small_roots(X=2^(512-T) , beta=1 , epsilon = 0.09)
    if len(root) > 0:
        dq = int(root[0]) * 2 ** T + dqlow
        q = int((e * dq - 1) // k + 1)
        p = n // q
        phi = (p - 1) * (q - 1)
        d = inverse(e,phi)
        print(p)
        print(q)
        print(d)
        break

解密：

from Crypto.Util.number import *
import gmpy2
from tqdm import tqdm
from Crypto.PublicKey import RSA
from tqdm import *

n = 0x00a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 0x10001
c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989

p = 10213829782024783545003297323361767013228142222661257002530956057551073950125450516695912589649595025698368560123447098557641941486430202994513499791955563
q = 11107519606798680785942597947927519480577762449720497374074609255590791207245332471170853195963310484826166823128414767323512303499706409040252972314205123
d = 32568689720517858814151927924698911469201163379749439724046356179518636186738524911873950449535627591530406776789440933434109620957137686406555998252715892086026220190607953957244199087250288903156876788032090718571241138221031510167062533558325992673659974554410983740088712469431483844336784080065875265881


key = RSA.construct((n,e,d,p,q))
flag = key._decrypt(c)
print(long_to_bytes(flag))


#flag{df4a4054-23eb-4ba4-be5e-15b247d7b819}

其实完全不给dq的泄露信息，这个题目也是可以做的。可以参考如下题目进行练习：

[tangcuxiaojkuai]easy_copper3 | NSSCTF