20210828 WMCrypto方向部分复现

发表于 2021-10-08 分类于树哥让我天天写之Crypto 阅读次数：本文字数： 30k 阅读时长 ≈ 27 分钟

woc，这也太难了吧，简直是神仙在打架，看着解出人数就没有什么信心做下去了

全a了，大师傅的博客，然后发WP的那一刻环境也关了

四道题，一道考格在背包，一道考格在RSA的AGCD，一道考AES.OCB，最后一道不清楚考点

WM

Crypto-checkin（recuring）

众所周知，L1near是一个著名大黑客，他为W&M编写了一个全自动的水群机器人，我们偷到了L1near在开发时的简易版本，并且获得了交互的接口，你能帮我们找到L1near偷偷藏起来的flag吗？

Link

第二天上了update

请提交合法的secret中最小的那个，题目没有说清楚，给各位师傅添麻烦了～

<title>W&M exclusive robot</title>

<style>
    h1 {text-align:center}
    p {text-align:center}
    form {text-align:center}
</style>

<head>
    <body>
        <h1>Fully automatic rp system</h1>
        <p>Come and get your rp value today!</p>
        <hr></hr>
        <form action="show.php" method="post">
        <input type="hidden" id="rp" name="rp" value="rp">
        <input type="submit" value="Get today's rp!">
        </form>
    </body>
</head>

<script>
    function ran(){
        var rp = Math.floor( Math.random() * 100);
        document.getElementById("rp").setAttribute('value',rp);
    }
    ran();
</script>

<!--
-------------------------------------------------------
Maybe there are some Easter eggs?
So where are them?
-->

rp是0到99的整数，但是post100会得到

<title>W&M exclusive robot</title>

<style>
    h1 {text-align:center}
    p {text-align:center}
</style>

<h1>Fully automatic rp system</h1>
<p>Come and get your rp value today!</p>
<hr></hr>

<p>Your rp value:100</p>
<p>Wow! Golden legend!<!-- so why not try to post 'flag' as rp? --></p>

没有分析出什么东西，稍微梳理一下

0~19

Ah-ha! There is a idiot!
20~39

Gee, this is too miserable.
40~59

Oh, you almost passed it!
60~79

Fortunately, you passed 60.
80~99

You are Koi! Congratulations!
100

Wow! Golden legend!

flag

Your rp value:1620418829165478

What happend to my bot?????

Let me find something in my backpack which can fix this bug!

第一次写post脚本，祭奠一下

from Crypto.Util.number import *
import requests


def exDigit(String):
    d = 0
    for j in String:
        if '0' <= j <= '9':
            d = d * 10 + int(j)
    return d

x = 999999999999999999999999999999999
url = "http://47.104.243.99:10000/show.php"
r = requests.post(url, {"rp": 2017515922459700})
for i in range(65537):
    if 'flag' in r.text or 'WMCTF' in r.text or 'wmctf' in r.text or '1620418829165478' in r.text:
        print(r.text)
        print(x)
    line = r.text[205:][:37]
    t = exDigit(line)
    if t < x:
        x = t
    print(t)
    payload = {
        "rp": t
    }
    r = requests.post(url, payload)

然而看了WP后发现，这些搜集的信息都没什么用，我直接原地爆炸

考的是背包，CTF Wiki上这篇背包挺通俗易懂的，主要掌握以下这些概念吧：超递增，Merkle–Hellman背包加密，构造01格破解

不过是看了WP还不懂系列。首先想知道是怎么看出这机器背后是背包加密的，然后为什么post 2^i+a就可以得到背包每一项的值，i和a分别是什么

目前的理解是，post flag得到的1620418829165478就是密文，然后破解得到私钥，解密

但目前还有很多疑点以及不懂的地方，太难了，后续补充吧

来了，这是这几天来的第三次复现，看了Striving师傅的博客终于或多或少有点理解了。好吧，原来菜鸡是我自己

看到backpack想到的背包，当时一直以为是备份的意思

简单介绍下背包加密，又是从la佬这里学习而来

首先背包问题就是我们熟知的背包问题，下面这段话也许能重拾记忆

私钥生成

选择一个超递增集${s_1, s_2, \cdots, s_n}$

所谓的超递增集就是满足第i个数大于前面所有数的和
公钥生成
1. 选取模数m，确保$m>\sum\limits_{i=1}^n s_i$
2. 选取乘数w，确保$(w,\ m)=1$，这里又说w也是私钥
3. 生成公钥集$t_i$，$t_i\equiv ws_i\ (mod\ m)$
加密

明文b的每一位的二进制为$b_i$
$$
c=\sum\limits_{i=1}^nt_ib_i\ (mod\ m)
$$
解密

先求$w^{-1}$，则
$$
b=\sum\limits_{i=1}^nw^{-1}t_ib_i\ (mod\ m)=\sum\limits_{i=1}^ns_ib_i\ (mod\ m)
$$

该密码系统有一个密度，为$d=\frac{n}{log_2(max{t_i})}$

然后就是看不懂的地方说，Striving师傅说春哥师傅说每次post$2^i$，会发现周期是32，得到的值也就公钥集里面的值。借下数据，相当于知道公钥集和密文，要求明文

1
2

t = [97005071980911, 32652300906411, 73356817713575, 108707065719744, 103728503304990, 49534310783118, 53330718889073, 2121345207564, 46184783396167, 115771983454147, 64261597617025, 2311575715655, 56368973049223, 84737125416797, 24316288533033, 82963866264519, 101019837363048, 25996629336722, 41785472478854, 68598110798404, 40392871001665, 94404798756171, 54290928637774, 112742212150946, 91051110026378, 124542182410773, 40388473698647, 22059564851978, 57353373067776, 80692115733908, 84559172686971, 28186390895657]
c = 1620418829165478

有了这个可以求出密度

from math import log

d = len(t) / log(max(t), 2)
# d = 0.6834156494834176

说是低密度可以直接搞，不太懂原理，抄个脚本，也是用到格

抄自论文

t = [97005071980911, 32652300906411, 73356817713575, 108707065719744, 103728503304990, 49534310783118, 53330718889073, 2121345207564, 46184783396167, 115771983454147, 64261597617025, 2311575715655, 56368973049223, 84737125416797, 24316288533033, 82963866264519, 101019837363048, 25996629336722, 41785472478854, 68598110798404, 40392871001665, 94404798756171, 54290928637774, 112742212150946, 91051110026378, 124542182410773, 40388473698647, 22059564851978, 57353373067776, 80692115733908, 84559172686971, 28186390895657]
ct = 1620418829165478
n = len(t)
M = Matrix.identity(n)

last_row = [0 for x in t]
M_last_row = Matrix(ZZ, 1, len(last_row), last_row)

last_col = t[:]
last_col.append(ct)
M_last_col = Matrix(ZZ, len(last_col), 1, last_col)

M = M.stack(M_last_row)
M = M.augment(M_last_col)

X = M.LLL()
target = X[-1][:-1]
ans = [abs(k) for k in target]
flag = int(''.join([str(i) for i in ans])[::-1], 2)
# 4159506287

魔改la佬的脚本

然后听说把解密得到的flag这串数字post过去就得到flag了，你得到了吗

Crypto-ocb（unsolved）

L1near已经疲倦了AK比赛的生活了，他想趁此机会学习一下AES.OCB，这是他最新实现的一个加密系统，你来帮他看看有什么问题吧。

from ocb.aes import AES # https://github.com/kravietz/pyOCB
from base64 import b64encode, b64decode
from Crypto.Util.number import *
from hashlib import sha256
from secret import flag
from ocb import OCB
import socketserver
import signal
import string
import random
import os

xor = lambda s1 , s2 : bytes([x1^x2 for x1,x2 in zip(s1,s2)])
def check(data):
    try:
        if(len(data) % 16 != 0):
            return False
        for i in range(data[-1]):
            if(data[-1] != data[-1-i]):
                return False
        return True
    except:
        return False
def pad(data):
    if check(data):
        return data
    padlen = 16 - len(data) % 16
    return data + padlen * bytes([padlen])
def unpad(data):
    if not check(data):
        return data
    return data[:-data[-1]]

BANNER =br'''
 __      __          ___                                           __                                               __       ___  
/\ \  __/\ \        /\_ \                                         /\ \__                                           /\ \__  /'___\ 
\ \ \/\ \ \ \     __\//\ \     ___    ___     ___ ___      __     \ \ ,_\   ___       __  __  __    ___ ___     ___\ \ ,_\/\ \__/ 
 \ \ \ \ \ \ \  /'__`\\ \ \   /'___\ / __`\ /' __` __`\  /'__`\    \ \ \/  / __`\    /\ \/\ \/\ \ /' __` __`\  /'___\ \ \/\ \ ,__\
  \ \ \_/ \_\ \/\  __/ \_\ \_/\ \__//\ \L\ \/\ \/\ \/\ \/\  __/     \ \ \_/\ \L\ \   \ \ \_/ \_/ \/\ \/\ \/\ \/\ \__/\ \ \_\ \ \_/
   \ `\___x___/\ \____\/\____\ \____\ \____/\ \_\ \_\ \_\ \____\     \ \__\ \____/    \ \___x___/'\ \_\ \_\ \_\ \____\\ \__\\ \_\ 
    '\/__//__/  \/____/\/____/\/____/\/___/  \/_/\/_/\/_/\/____/      \/__/\/___/      \/__//__/   \/_/\/_/\/_/\/____/ \/__/ \/_/ 
'''

MENU = br'''[+] 1.Encrypt
[+] 2.Decrypt
[+] 3.Get flag
[+] 4.Exit
'''

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

    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 encrypt(self, nonce, message, associate_data=b''):
        assert nonce not in self.NONCEs
        self.NONCEs.append(nonce)
        self.ocb.setNonce(nonce)
        message = pad(message)
        tag, cipher = self.ocb.encrypt(bytearray(message), bytearray(associate_data))
        return (bytes(cipher), bytes(tag))
    
    def decrypt(self, nonce, cipher, tag, associate_data=b''):
        self.ocb.setNonce(nonce)
        authenticated, message = self.ocb.decrypt(*map(bytearray, (associate_data, cipher, tag)))
        message = unpad(message)
        if not authenticated:
            self.send(b"[!] Who are you???")
            return b''
        return message

    def handle(self):
        signal.alarm(60)
        self.send(BANNER)
        if not self.proof_of_work():
            self.send(b'[!] Wrong!')
            return
        
        self.send(b'[+] Welcome my friend!')
        self.send(b'[+] Can you find the secret through the easy encryption system?')

        aes = AES(128)
        self.ocb = OCB(aes)
        KEY = os.urandom(16)
        self.ocb.setKey(KEY)
        self.NONCEs = []

        while True:
            self.send(MENU, newline=False)
            choice = self.recv()
            if(choice == b'1'):
                try:
                    self.send(b'[+] Please input your nonce')
                    nonce = b64decode(self.recv())
                    self.send(b'[+] Please input your message')
                    message = b64decode(self.recv())
                    associate_data = b'from baby'
                    ciphertext, tag = self.encrypt(nonce, message, associate_data)
                    self.send(b"[+] ciphertext: " + b64encode(ciphertext))
                    self.send(b"[+] tag: " + b64encode(tag))
                except:
                    self.send(b"[!] ERROR!")
            elif(choice == b'2'):
                try:
                    self.send(b'[+] Please input your nonce')
                    nonce = b64decode(self.recv())
                    self.send(b'[+] Please input your ciphertext')
                    ciphertext = b64decode(self.recv())
                    self.send(b'[+] Please input your tag')
                    tag = b64decode(self.recv())
                    self.send(b'[+] Please input your associate data')
                    associate_data = b64decode(self.recv())
                    if associate_data == b'from admin':
                        self.send(b'[!] You are not admin!')
                        break
                    message = self.decrypt(nonce, ciphertext, tag, associate_data)
                    self.send(b'[+] plaintext: ' + b64encode(message))
                except:
                    self.send(b"[!] ERROR!")
            elif(choice == b'3'):
                try:
                    nonce = b'\x00'*16
                    message = flag
                    associate_data = b'from admin'
                    ciphertext, tag = self.encrypt(nonce, message, associate_data)
                    self.send(b"[+] ciphertext: " + b64encode(ciphertext))
                    self.send(b"[+] tag: " + b64encode(tag))
                except:
                    self.send(b"[!] ERROR!")
            elif(choice == b'4'):
                self.send(b'[+] Bye~')
                self.send(b'[+] See you next time!')
                break
            else:
                self.send(b'[!] What are you doing???')
                self.send(b'[!] Go away!')
                break

        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', 10001
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    print(HOST, PORT)
    server.serve_forever()

津门杯和红明谷有类似的题目，ocb模式的AES提供了身份验证，还没有仔细研究过该模式下的流程，光看代码，没有什么方法可以绕过那个associate_data == b'from admin'

Crypto-easylsb（recuring）

#!/usr/bin/python3
# encoding: utf-8
import random
import string
import sys
import os
from hashlib import sha256
import uuid
from Crypto.Util.number import *

password = # Hidden
flag = ('flag{' + str(uuid.uuid4()) + '}').encode()

def proof_of_work():
    random.seed(os.urandom(8))
    proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)]).encode()
    digest = sha256(proof).hexdigest()
    printf("sha256(XXXX+%s) == %s" % (proof[4:].decode(),digest))
    printf('Give me XXXX:')
    x = read_str()
    if len(x) != 4 or sha256(x.encode()+proof[4:]).hexdigest() != digest: 
        return False
    return True

def printf(message):
    sys.stdout.write('{0}\n'.format(message))
    sys.stdout.flush()
    sys.stderr.flush()

def read_str():
    return sys.stdin.readline().strip()

def read_int():
    return int(sys.stdin.readline().strip())

def next_prime(a):
    while not isPrime(a):
        a += 2
    return a

def get_prime(a):
    suffix = getPrime(368)
    return next_prime(a ** 2 + suffix + 1)

def generate_pubkey(key):
    p, q = get_prime(getPrime(512)), get_prime(key)
    n = p * q
    return n

def airdrop(a):
    n = generate_pubkey(a)
    printf('gift: {}'.format(n))
    return

def hint(n, e, c):
    printf('n = {}'.format(n))
    printf('e = {}'.format(e))
    printf('c = {}'.format(c))
    return

def leak():
    p = get_prime(getPrime(512))
    e = 0x1000
    c = pow(bytes_to_long(flag), e, p)
    
    hint(p, e, c)
    return

def backdoor():
    printf('Input your password:')
    user_input = read_str()
    if user_input.encode() == password:
        leak()
    else:
        printf('Wrong')
        exit(0)

if __name__ == '__main__':
    if not proof_of_work():
        exit(0)
    
    a = getPrime(512)
    p = get_prime(a)
    q = get_prime(getPrime(512))
    n = p * q
    e = 0x10001
    max_time = 5
    password_enc = pow(bytes_to_long(password), e, n)
    
    printf('====================================',)
    printf('1. Airdrop                          ',)
    printf('2. Backdoor                         ',)
    printf('3. Hint                             ',)
    printf('4. Exit                             ',)
    printf('====================================',)
    
    try:
        while True:
            printf('Your choice:')
            choice = read_int()
            if choice == 1:
                if max_time > 1:
                    airdrop(a)
                    max_time -= 1
                    printf('Done!')
                else:
                    printf('Greed will destroy you!')
                continue
            elif choice == 2:
                backdoor()
                printf('Done!')
                continue
            elif choice == 3:
                hint(n, e, password_enc)
                printf('Done!')
                continue
            elif choice == 4:
                printf('bye~')
                exit(0)
                continue
            else:
                printf('Invalid!')
                continue
    except:
        exit(-1)

流程比较简单，虽然不会，但是思路比较清晰，通过4组gift和1个n求得a和p$\rightarrow$解密password$\rightarrow$在e=4096，模数是素数下解密flag

一开始通过尚师傅提醒，尝试之后发现，q开根后取整的结果是和a一样的
$$
\lfloor \sqrt{q} \rfloor=a
$$
然后假设$q=next_prime(a^2+suffix_1+1),\ p=next_prime(b^2+suffix_2+1)$

那么n=pq，给n开根号可以得到ab的高位，但也不知道拿来怎么用

保存了一组数据下来，以后有机会研究

# nc 47.104.243.99 9999
import random
import string
import sys
import os
from hashlib import sha256
import uuid
from Crypto.Util.number import *
from pwn import *
from itertools import product


# flag = ('flag{' + str(uuid.uuid4()) + '}').encode()
# print(flag)
# flag{cb8365b5-a825-4c65-9251-b6827f0792ad}


def proof_of_work():
    # sha256(XXXX+cgDUNjezTPNSj91D) == 30fc93b19ef81e8755f3ee0e3df72722f66556b7636b5037f34d1beb981235b0
    proof = sh.recvline()
    tail = proof[12:28].decode()
    HASH = proof[23:97]
    for i in product(string.ascii_letters + string.digits, repeat=4):
        head = ''.join(i)
        t = hashlib.sha256((head + tail).encode()).hexdigest()
        if t == HASH:
            sh.sendline(head.encode())
            break


def proof_of_work2():
    # sha256(XXXX+cgDUNjezTPNSj91D) == 30fc93b19ef81e8755f3ee0e3df72722f66556b7636b5037f34d1beb981235b0
    proof = sh.recvline()
    tail = 'eqbj8j6Z9xvz3YiV'
    HASH = 'b5808aff39327c9ac49d209d10fe3e27c898d49faffc956bbf1d73523c44ce77'
    for i in product(string.ascii_letters + string.digits, repeat=4):
        head = ''.join(i)
        t = hashlib.sha256((head + tail).encode()).hexdigest()
        if t == HASH:
            sh.sendline(head.encode())
            break


context.log_level = 'debug'
sh = remote("47.104.243.99", 9999)
proof_of_work2()

e = 0x10001
n = 124478026101165354098037876421627662624056206605515177686194103211430464934743129994417330643128683345849733014275487857184516763016301408033382676283620282332485581507315430690690813831282519976585364463744017296315372258981215919387679949709396064987889800074036410663927631478105899096723790945928412829187822284593750473740315866322998068351563015099367643886154042581191841533888375305195743073059105310700318861167337672659772641786687582718180589854118978820530842381081568922213227168617789474006973152602334271699398178963791154954792676067153150646411025449463253194489657095241613282942586704728903727611399
c = 90647155870804971113806442051901226002120015769259333554192477899450971338831255790857101662710560234954831825416787459228033373486077151217415092360097814474283515220281223555587026056325099266316005605716929634353603643319859645167427538563242884591102004934790399528462112789803351851769047685792159647390050985871679243422993775721776244067168064933786611606433105514418429089777322132633028815660525070271128628044386434106685643657668695364607215033856398608992051550288297119711825866170869469834444973857013360900452988222767960318998636640763573797297203544581343736625672669946528644260077687270041162148579
gift1 = 430643544402084432319325961880416327356872029175895120742910502784460696485981655831364057771978842374920289740546998744096646780935886278222230684528731470188637076148307527311922452490801045278988434801896164340653915198079023711297016090027381126073802620204314765869166624636941907534206046998568042400815444697126334029985946496452932477337335924863188276040631646131204436116708742280199903183210826719901897273260766069768314579353548171372586771188839003301749872795307598319516051259672117483195538538878148292313730887085591272354625175614366936749367007177827223031514498275753340915542939818624965339274541
gift2 = 279643881521430665779764628210196159031443254319916096260435206316116655701344325784134050728686231352816394212502789612947929220430466611004330150352137570405484127780364316335386736272544877793446702006665399064591475517610575894857804921152265901610537191780251376268112843688812459951190257679817490601282013470378644045696567456486059374094892490322848884260103728441765221196492288890565220765116737467020984854284776188063793107604665880577892150257025900438921323929874583349697921571156857890185078774883450481945134786456867498237937223992977125106207044050316201931335150865420643200300919950666792333800421
gift3 = 237902069859826089956710602458488697197969935460375469157966706791637991891038954423106099106663742928616105443683571279895168734280020803510641968762322744746722455831059684745613465616901995570874116303439549541932451281441959514629564655972962203744852006794160278105621063202850402448076034174743227230202591123961117876362833492478366233652816443873213201410433457033307944305406209168085355438156499669719905462067847881209129983251184647052314353242784174374088582263983943733709287614092898665984536781786084591414804290805713181580225096207601673326693693442261927044483426965621699507399608913104482509541829
gift4 = 131184496439376311814751172869309509301398236134030748081290782986296909958428702969677021306310259793511587606469385852829507392096577310273567455635233040499932518933927338330158300947934921792366825549482737059128276134653805578959896357503546949681198843822945160611138388841031519307824760189249466171835761078895545203381195921789823129815826662876576368032722825159838976137103324588326186884693453137115752294499574361951327089081432442184727065530788376603390307277709197418051468405219378610308912749832078805547917787498228816440083434077213552664217150489211767711038795362880479839885325109115335568243823

现在可以好好复现一下这道题了

先是补充，得到a之后，那么由上面的结论可知$a^2$就是q的高位，那这不就是RSA已知p的高位攻击吗

不懂WP里的格是由哪个方程组得到的

好了，第三波复现，还以为agcd是师傅打错了，原来是我菜了，是个论文Approximate GCD

看格式和题目是完全对应的

哈哈，看不太懂，拿了格就跑路

$x_i$显然就是五组$n_i$开根号得到的，这个上面也证实了；$\lambda$就是368，因为论文里的$r_i$就是题目中的$suffix_i+1$

这样对矩阵B进行LLL()得到的是$q_0\cdot 2^{\lambda +1}$，除以$2^{\lambda +1}$就是论文里的$q_0$了，也就是与$x_0$对应的那个

到此为止还少了一步，接着题目中的$n=pq$推导
$$
n=pq=(a^2+suffix_1+1)(b^2+suffix_2+1)
$$
设$\beta =\sqrt {b^2+suffix_2+1},\ \delta$为p开根后的低位，$r=\delta \beta$

给n开根
$$
\sqrt n=(a+\delta)\beta =a\beta +r
$$
这就和论文里给的形式一样了，而我们刚求出来的$q_0$就是这里的$\beta$，最后$\lfloor\sqrt n/\beta \rfloor =\lfloor (a\beta +r)/\beta\rfloor$，显然$r/\beta$已经是小数部分了，取整就完全舍去了，所以结果就是a

求出来的ans应该是上文的b，先用这位师傅的脚本得到a

from sympy import root

e = 0x10001
n = 124478026101165354098037876421627662624056206605515177686194103211430464934743129994417330643128683345849733014275487857184516763016301408033382676283620282332485581507315430690690813831282519976585364463744017296315372258981215919387679949709396064987889800074036410663927631478105899096723790945928412829187822284593750473740315866322998068351563015099367643886154042581191841533888375305195743073059105310700318861167337672659772641786687582718180589854118978820530842381081568922213227168617789474006973152602334271699398178963791154954792676067153150646411025449463253194489657095241613282942586704728903727611399
c = 90647155870804971113806442051901226002120015769259333554192477899450971338831255790857101662710560234954831825416787459228033373486077151217415092360097814474283515220281223555587026056325099266316005605716929634353603643319859645167427538563242884591102004934790399528462112789803351851769047685792159647390050985871679243422993775721776244067168064933786611606433105514418429089777322132633028815660525070271128628044386434106685643657668695364607215033856398608992051550288297119711825866170869469834444973857013360900452988222767960318998636640763573797297203544581343736625672669946528644260077687270041162148579
gift1 = 430643544402084432319325961880416327356872029175895120742910502784460696485981655831364057771978842374920289740546998744096646780935886278222230684528731470188637076148307527311922452490801045278988434801896164340653915198079023711297016090027381126073802620204314765869166624636941907534206046998568042400815444697126334029985946496452932477337335924863188276040631646131204436116708742280199903183210826719901897273260766069768314579353548171372586771188839003301749872795307598319516051259672117483195538538878148292313730887085591272354625175614366936749367007177827223031514498275753340915542939818624965339274541
gift2 = 279643881521430665779764628210196159031443254319916096260435206316116655701344325784134050728686231352816394212502789612947929220430466611004330150352137570405484127780364316335386736272544877793446702006665399064591475517610575894857804921152265901610537191780251376268112843688812459951190257679817490601282013470378644045696567456486059374094892490322848884260103728441765221196492288890565220765116737467020984854284776188063793107604665880577892150257025900438921323929874583349697921571156857890185078774883450481945134786456867498237937223992977125106207044050316201931335150865420643200300919950666792333800421
gift3 = 237902069859826089956710602458488697197969935460375469157966706791637991891038954423106099106663742928616105443683571279895168734280020803510641968762322744746722455831059684745613465616901995570874116303439549541932451281441959514629564655972962203744852006794160278105621063202850402448076034174743227230202591123961117876362833492478366233652816443873213201410433457033307944305406209168085355438156499669719905462067847881209129983251184647052314353242784174374088582263983943733709287614092898665984536781786084591414804290805713181580225096207601673326693693442261927044483426965621699507399608913104482509541829
gift4 = 131184496439376311814751172869309509301398236134030748081290782986296909958428702969677021306310259793511587606469385852829507392096577310273567455635233040499932518933927338330158300947934921792366825549482737059128276134653805578959896357503546949681198843822945160611138388841031519307824760189249466171835761078895545203381195921789823129815826662876576368032722825159838976137103324588326186884693453137115752294499574361951327089081432442184727065530788376603390307277709197418051468405219378610308912749832078805547917787498228816440083434077213552664217150489211767711038795362880479839885325109115335568243823

f = lambda a: int(root(a, 2))
x0, x1, x2, x3, x4 = f(n), f(gift1), f(gift2), f(gift3), f(gift4)

B = matrix(ZZ, [[2 ^ 368, x1, x2, x3, x4], [0, -x0, 0, 0, 0], [0, 0, -x0, 0, 0], [0, 0, 0, -x0, 0], [0, 0, 0, 0, -x0]])
L = B.LLL()
ans = L[0][0] // 2 ^ 368

p0 = abs(ans)
a = x0 // p0

print(a)
# a = 25582847577564670038612582668140373129129959651036453923605273284793860890291221263498753328353767798264241675861426056503889321642277844202986695039010291

然后是熟悉的节奏，但和一般的已知p的高位攻击不一样，显然$a^2$已经和p的位数差不多了，只是不知道368位的suffix是多少，所以本质一样，用CopperSmith求小根的算法求出suffix；这里取kbits为369，因为368出不来，往大一点的地方取

a = 25582847577564670038612582668140373129129959651036453923605273284793860890291221263498753328353767798264241675861426056503889321642277844202986695039010291
n = 124478026101165354098037876421627662624056206605515177686194103211430464934743129994417330643128683345849733014275487857184516763016301408033382676283620282332485581507315430690690813831282519976585364463744017296315372258981215919387679949709396064987889800074036410663927631478105899096723790945928412829187822284593750473740315866322998068351563015099367643886154042581191841533888375305195743073059105310700318861167337672659772641786687582718180589854118978820530842381081568922213227168617789474006973152602334271699398178963791154954792676067153150646411025449463253194489657095241613282942586704728903727611399
pbar = a ** 2
kbits = 369
PR.<x> = PolynomialRing(Zmod(n))
f = pbar + x
roots = f.small_roots(X=2^kbits, beta=0.4)
# 967901962469872165537856438801710756065070673694594801499396171114255660549746759504438698205658088002955084386

接下来RSA的常规步奏得到password

Cou1d_I_get_Th3_passw03d_then_captu7e_the_fla9?

因为比赛中没有获得flag的c，所以借这位师傅的一用

正如一开始所说的e是偶数，还是$2^{12}$，与$\varphi(p)=p-1$不互素，这个时候应该说PUTAOAO，你的台词说错了哟。报仇的时候可不能说兲蛋什么的。应该是这样：吾名尚师傅，为了抚平吾友4XWi11之憾恨，以及让吾左侧朋友Y1m0在天之灵得以安息，吾势必要汝以4谢罪!

平方根，有限域开方，Rabin一把梭

不过这里考虑到这里4096比较大，有限域开方会很慢吧，直接用nthroot_mod函数似乎并不行，传统的rabin是不行的因为模数是p；看了师傅的恍然大悟，为此特地去发了一篇关于rabin原理的博客

虽然不知道nthroot_mod为什么不行，由于p % 4 = 3符合rabin最基本的条件，之所以需要满足这个条件而这个条件也正是开方出来结果比较少的条件，所以直接开12次方没有压力

关键的代码m1 = pow(c, (p + 1) // 4, p)和m2 = p - m1

from Crypto.Util.number import long_to_bytes

p = 496584754781581997154645314415051021632937719346451955222548277806458479939882609131615548616817732786901123585586203791585231652481101508165523306207307511005218236201069837205145881515297396218450658339325435517394532697652694250302927324547950654199907918057947165277944713164863611463887879016367147027651
e = 4096
c = 202821697585498721190880385651888326819052363235092021514522019296117832067188656931773131985516119359273814956340533509702817980744398402155886334655033938474295749168241550740096583920405311629354495691732306096266636370938656838375279086916114964255411601403125984312042419408682006688199111243135798564394

mi = []

for i in range(12):
    mi.append(pow(c, (p + 1) // 4, p))
    mi.append(p - pow(c, (p + 1) // 4, p))
    c = pow(c, (p + 1) // 4, p)

for i in mi:
    t = long_to_bytes(i)
    if b'WMCTF' in t:
        print(t)
        break

然后看来Striving师傅的博客，原来有限域开方也是可以的，看来我并没有理解其中的精华，回顾之前的ctfshow unusualrsa系列的博客，其实有了sage一切就并不复杂

from Crypto.Util.number import *
p = 496584754781581997154645314415051021632937719346451955222548277806458479939882609131615548616817732786901123585586203791585231652481101508165523306207307511005218236201069837205145881515297396218450658339325435517394532697652694250302927324547950654199907918057947165277944713164863611463887879016367147027651
e = 4096
c = 202821697585498721190880385651888326819052363235092021514522019296117832067188656931773131985516119359273814956340533509702817980744398402155886334655033938474295749168241550740096583920405311629354495691732306096266636370938656838375279086916114964255411601403125984312042419408682006688199111243135798564394
R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
print(res1)
# res1 = [(496584754781581997154645314415051021632937719346451955222548277806458479939882609131615548616817732786901123585586203791585231652481101508165523306207307511005218236201069837205145881515297396218450658339313214656968189495352306293673615992017103882095004555948437432049586089024300970437646867574391499674950, 1), (12220860426343202300387956629311332530846772104903362109509733228358624140562641026241011441975647352701, 1)]
c = 12220860426343202300387956629311332530846772104903362109509733228358624140562641026241011441975647352701
print(long_to_bytes(c))

确实可以，跑的比预计的要快

Crypto-ezl1near（unsolved）

from Crypto.Util.number import long_to_bytes , bytes_to_long , getPrime , inverse
from Crypto.Cipher import AES
import socketserver , signal
import random
import string
from hashlib import sha256
import os
from secret import flag
q = 2**24

def getrandbits(n):
    return bytes_to_long(os.urandom(n // 8+1)) >> (8-n%8)

class server(socketserver.BaseRequestHandler):
    

    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg , bytes):
            msg += b'\n'
        else:
            msg += '\n'
            msg = msg.encode()
        self.request.sendall(msg)

    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())
        self._send(b'Give me XXXX: ')
        x = self._recv()
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            self.send('wrong')
            return False
        return True

    def genrsa(self):
        _p = getPrime(1024)
        _q = getPrime(1024)
        self.n = _p * _q
        self.e = 65537
        self.d = inverse(self.e , (_p-1)*(_q-1))

    def to_vec(self,num , length):
        vec = []
        while length > 0:
            vec = [num % q] + vec
            num //= q
            length -= 1
        return vec

    def to_mat(self,numlist):
        M =[]
        for i in numlist:
            M.append(self.to_vec(i , 40))
        return M

    def enc(self, key , m):
        key = self.to_mat(key)
        res = []
        for i in range(40):
            temp = 0
            for j in range(16):
                temp += m[j]* key[j][i]
                temp %= q
            res.append(temp)
        return res
    def handle(self):
        signal.alarm(120)
        self.proof_of_work()
        self.genrsa()
        self._send(str(self.n))
        self._send(str(self.e))
        secret = [1] + [2*getrandbits(23)-1 for _ in range(15)]
        self._send(b'Please generate key for me and I will give you my secret.But you have only two chances.')
        for i in range(2):
            key = []
            f0 = getrandbits(480)
            key.append(f0)
            self._send(str(pow(f0 , self.e , self.n)))
            f0 += f0 << 480
            for j in range(15):
                self._send('key'+str(i+1) + ':')
                c = int(self._recv())
                m = pow(c , self.d , self.n)
                f = m - f0
                f %= self.n
                key.append(f)
            c = self.enc(key , secret)
            self._send('Thanks, here is your cipher:' + str(c))
        self._send(b'do you know the secret?')
        guess = [int(i) for i in self._recv().split(b' ')]
        if len(guess) == 16:
            for j in range(16):
                if guess[j] != secret[j]:
                    break
            else:
            
                self._send(b'congratulations. here is your flag:')
                self._send(flag)
                return 0
        else:
            self._send(b'L1near don\'t care.')
        

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

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

没心情，看不下去了

可谓是重大失误，全程密码爆0，签到题搞心态，对不起web和misc的师傅