首页 > 其他分享 >NSSCTF--Crypto--[CISCN 2023 初赛]badkey

NSSCTF--Crypto--[CISCN 2023 初赛]badkey

时间:2024-12-24 19:21:29浏览次数:7  
标签:hash CISCN temp -- 初赛 assert time print import

[CISCN 2023 初赛]badkey

task:

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from hashlib import sha256
import random, os, signal, string

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
    _hexdigest = sha256(proof.encode()).hexdigest()
    print(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}")
    print('Give me XXXX: ')
    x = input()
    if len(x) != 4 or sha256(x.encode()+proof[4:].encode()).hexdigest() != _hexdigest:
        print('Wrong PoW')
        return False
    return True

if not proof_of_work():
    exit(1)
    
signal.alarm(10)
print("Give me a bad RSA keypair.")

try:
    p = int(input('p = '))
    q = int(input('q = '))
    assert p > 0
    assert q > 0
    assert p != q
    assert p.bit_length() == 512
    assert q.bit_length() == 512
    assert isPrime(p)
    assert isPrime(q)
    n = p * q
    e = 65537
    assert p % e != 1
    assert q % e != 1
    d = inverse(e, (p-1)*(q-1))
except:
    print("Invalid params")
    exit(2)

try:
    key = RSA.construct([n,e,d,p,q])
    print("This is not a bad RSA keypair.")
    exit(3)
except KeyboardInterrupt:
    print("Hacker detected.")
    exit(4)
except ValueError:
    print("How could this happen?")
    from secret import flag
    print(flag)

analysis:

首先我们连接靶机之后,我们需要输入四位正常可显示字符,这四位字符与剩下的16位字符的hash值已经给定,所以第一步进行爆破即可.

第二部需要我们输入一组RSA加密的p,q并且有assert的限制条件,采用key = RSA.construct([n,e,d,p,q])后需要发生ValueError错误才能获取flag.通过搜索该函数:

排除调用 RSA.construct 前已进行的检查,最有可能导致失败的检查是

if Integer(n).gcd(d) != 1:
    raise ValueError("RSA private exponent is not coprime to modulus")

\[\begin{flalign} &n=pq\quad and\quad gcd(n,d)!=1\Longrightarrow gcd(n,d)=p\\ &设d=k_1p,ed=ek_1p=ek_1+ek_1(p-1)\equiv1(mod\ (p-1)*(q-1))\Longrightarrow ek_1\equiv1(mod\ p-1).\\ &k_1=e^{-1}(mod\ p-1).ed = k_2(p-1)*(q-1),k_2(q-1)={ek_1p\over p-1}\Longrightarrow q={ek_1p\over k_2(p-1)}+1.\\ &k_2是整数,且q.bit\_length()=512,则在range(1,2^{{ek_1p\over p-1}.bit\_lehnth()-512})的范围进行爆破寻找能让RSA.construct产生ValueError错误的p,q即可.& \end{flalign} \]

exp:

# -*- coding: utf-8 -*-
# @Author  : chen_xing
# @Time    : 2024/12/24 下午4:35
# @File    : badkey.py
# @Software: PyCharm
from pwn import *
import temp
# getpq
p,q = temp.getpq()
# hash_pop
io = remote('node4.anna.nssctf.cn',28788)
data = io.recvline().decode().strip().split(') == ')
result = data[1]
known = data[0][-16:]
io.sendline(temp.hash_pop(result,known))
io.sendlineafter(b'p = ', str(p))
io.sendlineafter(b'q = ', str(q))
io.interactive()
"""
-------------------------------getpq-begin-------------------------------
--------------------------------getpq-end--------------------------------
getpq time is: 16.541666269302368
-------------------------------hash_pop-begin-------------------------------
--------------------------------hash_pop-end---------------------------------
hash_pop time is: 44.73846364021301
How could this happen?
NSSCTF{971a423e-8f97-4f98-b7ee-e2d5eff4c2fb}
"""
"""
temp.py
import hashlib
from Crypto.Util.number import *
from time import *
def hash_pop(result,known):
    print("-------------------------------hash_pop-begin-------------------------------")
    start_time = time()
    for i in range(32,127):
        for j in range(32,127):
            for p in range(32,127):
                for q in range(32,127):
                    temp = str(chr(i)) + str(chr(j)) + str(chr(p)) + str(chr(q)) + known
                    if hashlib.sha256(temp.encode('utf-8')).hexdigest() == result:
                        end_time = time()
                        print("--------------------------------hash_pop-end---------------------------------")
                        print(f"hash_pop time is: {end_time - start_time}")
                        return temp[:4:]
def getpq():
    print("-------------------------------getpq-begin-------------------------------")
    e = 65537
    start_time = time()
    while True:
        p = getPrime(512)
        d = inverse(e,p - 1)
        temp = (e * d * p - 1) // (p - 1)
        for k in range(1,2**(temp.bit_length() - 512)):
            if temp % k == 0:
                q = temp // k + 1
                if isPrime(q) and q.bit_length() == 512:
                    end_time = time()
                    print("--------------------------------getpq-end--------------------------------")
                    print(f"getpq time is: {end_time - start_time}")
                    return p,q
"""

标签:hash,CISCN,temp,--,初赛,assert,time,print,import
From: https://www.cnblogs.com/chen-xing-zzu/p/18628553

相关文章

  • oss文件上传。
    昨天我们把文件已经上传到本地服务器下。为什么今天要讲上传到oss服务器下。第一个原因:服务器重启后服务器下上传的文件就会丢失。第二个原因:服务器是一个集群模式---集群文件无法共享。我们可以使用oss作为共享的文件服务器。1申请oss服务器。阿里云的服务器。---需......
  • Socat 命令总结
    事以密成,语以泄败。导航介绍基本语法用法示例回显输入回显输入overTCP/UDP正向连接shell反向连接shell端口转发网络服务文件传输管道传输加密传输TUN网络杂项介绍Socat是一个功能强大的网络工具(相当于是增强版netcat),它可以在两个数据流之间建立......
  • C#中使用gRPC(二)
    这一节,我们实际操作和体验一下再C#中使用gPrc我用的开发环境是VS2022和.Net6的版本。创建好项目以后,ASP.NETCore会自动帮我们创建一个greet.proto的文件和一个服务调整一下greet.proto文件,假设我们的sayHello方法传入一个对象,有年龄,姓名,住址和电话这四个字段,其中电话是一个字......
  • 近期学习安排
    首先啊,感谢学校放的一周假期(外教都回去过圣诞了。然后大概理一下还有哪些算法和数据结构是我在**近期可以学(了解)的。Manacher权值线段树Splay树Tarjan求LCA莫队算法IDA*双向广搜近期博客计划:每周一篇题解对于每学的一种新算法都在博客上整理记录近期刷题计划:......
  • 快手MARM 文章理解
    阅读了快手的论文MARM,论文中的算法符号看起来不容易理解。对照图自己研究了下,理解了。需要知道为什么(b)和(c)中的中间结果是相同的。需要知道masked-self-attention缓存是怎么处理,看箭头快手MARM:UnlockingtheFutureofRecommendationSystemsthroughM......
  • C#中使用gRPC(一)
    在使用gRpc之前,需要先了解一点基础知识。1.ProtocolBuffers具体参考https://protobuf.dev/:简答来说就是Google开发的一种数据描述的格式。和具体的开发语言无关,根据这个东西,你能定义你方法的参数,返回值类型。首先创建一个xxx.proto文件.例如sayHello.protosyntax=......
  • 返回json数据。
    1什么场景下需要返回json数据。ajax异步请求时,要求服务器返回json数据。借助jquery.$.get(url,data,function(result){},"json")之前服务器怎样返回json数据。需要借助阿里巴巴的fastjson的jar包。out=response.getWriter();StringjsonStr=JSON.toJSONString(java对象);......
  • 匈牙利算法
    匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,并推动了后来的原始对偶方法。——————百度百科咳咳,匈牙利算法是一种常用于求二分图最大匹配的高效算法,将暴力的指数级算法进化到多项式复杂度,如果用邻接表存图,最坏时间复杂度为O(nm)。二分图又称作二部图,是图......
  • 全局异常处理
    当controller层出现异常后,统一由全局异常处理器来处理。创建一个全局异常处理类@ControllerAdvice//标记该类为全局异常处理类。publicclassMyExceptionHandler{@ExceptionHandler(ArithmeticException.class)//该方法处理的为ArithmeticException异常类型publi......
  • deque容器/构造函数/赋值操作/大小操作/插入和删除/数据存取/排序
    deque容器基本概念功能:双端数组,可以对头端进行插入删除操作deque与vector区别:vector对于头部的插入删除效率低,数据量越大,效率越低deque相对而言,对头部的插入删除速度会比vector块vector访问元素时的速度会比deque快,这和两者内部实现有关deque内部工作原理:deque内部有个中......