BaseCTF2024-Crypto-naby

官方wp:https://j0zr0js7k7j.feishu.cn/docx/MS06dyLGRoHBfzxGPF1cz0VhnGh

复现平台: https://gz.imxbt.cn/games/13

Crypto

week1

babypack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
import random
flag=b'BaseCTF{}'
m=bytes_to_long(flag)
bin_m=bin(m)[2:]
length=len(bin_m)

a=[1]
sum=1
for i in range(length-1):
    temp=random.randint(2*sum+1,4*sum)
    sum=sum+temp
    a.append(temp)

a=a[::-1]
c=0
for i in range(length):
    if bin_m[i]=='1':
        c=c+a[i]
print("a=",a)
print("c=",c)

简单的超递增序列（不懂的可以简单了解一下背包密码）

从尾开始遍历列表a，大于c就为0，小于等于c就为1，并且c要减去这个值

(数据太多我就不贴了)

1
2
3
4
5
6
7
8
9
10
11
12
13
#BaseCTF{2c4b0c15-3bee-4e4a-be6e-0f21e44bd4c9}
from Crypto.Util.number import *
a=
c=2488656295807929935404316556194747314175977860755594014838879551525915558042003735363919054632036359039039831854134957725034750353847782168033537523854288427613513938991943920607437000388885418821419115067060003426834
bin_m=""
for i in a:
    if c>=i:
        bin_m+="1"
        c=c-i
    else:
        bin_m+="0"
m=int(bin_m,2)
print(long_to_bytes(m))

babyrsa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

flag=b'BaseCTF{}'
m=bytes_to_long(flag)

n=getPrime(1024)
e=65537
c=pow(m,e,n)

print("n =",n)
print("e =",e)
print("c =",c)
"""
n = 104183228088542215832586853960545770129432455017084922666863784677429101830081296092160577385504119992684465370064078111180392569428724567004127219404823572026223436862745730173139986492602477713885542326870467400963852118869315846751389455454901156056052615838896369328997848311481063843872424140860836988323
e = 65537
c = 82196463059676486575535008370915456813185183463924294571176174789532397479953946434034716719910791511862636560490018194366403813871056990901867869218620209108897605739690399997114809024111921392073218916312505618204406951839504667533298180440796183056408632017397568390899568498216649685642586091862054119832
"""

单素数RSA

ϕ(n)\phi(n)表示从1到n之间，有多少个数与n互素。

计算方法：排除掉不与n互素的数。

ϕ(pq)=pq−p−q+1=(p−1)(q−1)\phi(pq)=pq-p-q+1 = (p-1)(q-1)

这题n已经是素数了，1到n-1都与n互素，ϕ(n)=n−1\phi(n)=n-1

求到ϕ\phi之后就正常做就行

（理解RSA最重要的一点是搞懂e*d=1 mod(φ(n)），要理解为什么这里为什么是取φ(n)）

（很难绷，为什么那么多人问我n怎么分解，n=getPrime(1024)已经是素数了，不需要分解了。）

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
import gmpy2
n = 104183228088542215832586853960545770129432455017084922666863784677429101830081296092160577385504119992684465370064078111180392569428724567004127219404823572026223436862745730173139986492602477713885542326870467400963852118869315846751389455454901156056052615838896369328997848311481063843872424140860836988323
e = 65537
c = 82196463059676486575535008370915456813185183463924294571176174789532397479953946434034716719910791511862636560490018194366403813871056990901867869218620209108897605739690399997114809024111921392073218916312505618204406951839504667533298180440796183056408632017397568390899568498216649685642586091862054119832

phin=n-1
d=gmpy2.invert(e,phin)
m=pow(c,d,n)
print(long_to_bytes(m))
#b'BaseCTF{7d7c90ae-1127-4170-9e0d-d796efcd305b}'

hellpCrypto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import random

flag=b'BaseCTF{}'

key=random.randbytes(16)
print(bytes_to_long(key))

my_aes=AES.new(key=key,mode=AES.MODE_ECB)
print(my_aes.encrypt(pad(flag,AES.block_size)))

# key1 = 208797759953288399620324890930572736628
# c = b'U\xcd\xf3\xb1 r\xa1\x8e\x88\x92Sf\x8a`Sk],\xa3(i\xcd\x11\xd0D\x1edd\x16[&\x92@^\xfc\xa9(\xee\xfd\xfb\x07\x7f:\x9b\x88\xfe{\xae'

直接AES解密即可

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
from Crypto.Cipher import AES


key1 = 208797759953288399620324890930572736628
c = b'U\xcd\xf3\xb1 r\xa1\x8e\x88\x92Sf\x8a`Sk],\xa3(i\xcd\x11\xd0D\x1edd\x16[&\x92@^\xfc\xa9(\xee\xfd\xfb\x07\x7f:\x9b\x88\xfe{\xae'
my_aes1=AES.new(key=long_to_bytes(key1),mode=AES.MODE_ECB)
print(my_aes1.decrypt(c))

#b'BaseCTF{b80bf679-1869-4fde-b3f9-d51b872d31fb}\x03\x03\x03'

你会算md5吗

1
2
3
4
5
6
7
8
9
10
11
12
13
import hashlib

flag='BaseCTF{}'

output=[]
for i in flag:
    my_md5=hashlib.md5()
    my_md5.update(i.encode())
    output.append(my_md5.hexdigest())
print("output =",output)
'''
output = ['9d5ed678fe57bcca610140957afab571', '0cc175b9c0f1b6a831c399e269772661', '03c7c0ace395d80182db07ae2c30f034', 'e1671797c52e15f763380b45e841ec32', '0d61f8370cad1d412f80b84d143e1257', 'b9ece18c950afbfa6b0fdbfa4ff731d3', '800618943025315f869e4e1f09471012', 'f95b70fdc3088560732a5ac135644506', '0cc175b9c0f1b6a831c399e269772661', 'a87ff679a2f3e71d9181a67b7542122c', '92eb5ffee6ae2fec3ad71c777531578f', '8fa14cdd754f91cc6554c9e71929cce7', 'a87ff679a2f3e71d9181a67b7542122c', 'eccbc87e4b5ce2fe28308fd9f2a7baf3', '0cc175b9c0f1b6a831c399e269772661', 'e4da3b7fbbce2345d7772b0674a318d5', '336d5ebc5436534e61d16e63ddfca327', 'eccbc87e4b5ce2fe28308fd9f2a7baf3', '8fa14cdd754f91cc6554c9e71929cce7', '8fa14cdd754f91cc6554c9e71929cce7', '45c48cce2e2d7fbdea1afc51c7c6ad26', '336d5ebc5436534e61d16e63ddfca327', 'a87ff679a2f3e71d9181a67b7542122c', '8f14e45fceea167a5a36dedd4bea2543', '1679091c5a880faf6fb5e6087eb1b2dc', 'a87ff679a2f3e71d9181a67b7542122c', '336d5ebc5436534e61d16e63ddfca327', '92eb5ffee6ae2fec3ad71c777531578f', '8277e0910d750195b448797616e091ad', '0cc175b9c0f1b6a831c399e269772661', 'c81e728d9d4c2f636f067f89cc14862c', '336d5ebc5436534e61d16e63ddfca327', '0cc175b9c0f1b6a831c399e269772661', '8fa14cdd754f91cc6554c9e71929cce7', 'c9f0f895fb98ab9159f51fd0297e236d', 'e1671797c52e15f763380b45e841ec32', 'e1671797c52e15f763380b45e841ec32', 'a87ff679a2f3e71d9181a67b7542122c', '8277e0910d750195b448797616e091ad', '92eb5ffee6ae2fec3ad71c777531578f', '45c48cce2e2d7fbdea1afc51c7c6ad26', '0cc175b9c0f1b6a831c399e269772661', 'c9f0f895fb98ab9159f51fd0297e236d', '0cc175b9c0f1b6a831c399e269772661', 'cbb184dd8e05c9709e5dcaedaa0495cf']
'''

单字符md5，可以理解为单字节加密，没有行列转换混淆的话，一般都可以直接爆破

（如果答案不对一般就是字符集的问题，整数32-126就是可见字符范围）

1
2
3
4
5
6
7
8
9
10
11
12
import hashlib


output = ['9d5ed678fe57bcca610140957afab571', '0cc175b9c0f1b6a831c399e269772661', '03c7c0ace395d80182db07ae2c30f034', 'e1671797c52e15f763380b45e841ec32', '0d61f8370cad1d412f80b84d143e1257', 'b9ece18c950afbfa6b0fdbfa4ff731d3', '800618943025315f869e4e1f09471012', 'f95b70fdc3088560732a5ac135644506', '0cc175b9c0f1b6a831c399e269772661', 'a87ff679a2f3e71d9181a67b7542122c', '92eb5ffee6ae2fec3ad71c777531578f', '8fa14cdd754f91cc6554c9e71929cce7', 'a87ff679a2f3e71d9181a67b7542122c', 'eccbc87e4b5ce2fe28308fd9f2a7baf3', '0cc175b9c0f1b6a831c399e269772661', 'e4da3b7fbbce2345d7772b0674a318d5', '336d5ebc5436534e61d16e63ddfca327', 'eccbc87e4b5ce2fe28308fd9f2a7baf3', '8fa14cdd754f91cc6554c9e71929cce7', '8fa14cdd754f91cc6554c9e71929cce7', '45c48cce2e2d7fbdea1afc51c7c6ad26', '336d5ebc5436534e61d16e63ddfca327', 'a87ff679a2f3e71d9181a67b7542122c', '8f14e45fceea167a5a36dedd4bea2543', '1679091c5a880faf6fb5e6087eb1b2dc', 'a87ff679a2f3e71d9181a67b7542122c', '336d5ebc5436534e61d16e63ddfca327', '92eb5ffee6ae2fec3ad71c777531578f', '8277e0910d750195b448797616e091ad', '0cc175b9c0f1b6a831c399e269772661', 'c81e728d9d4c2f636f067f89cc14862c', '336d5ebc5436534e61d16e63ddfca327', '0cc175b9c0f1b6a831c399e269772661', '8fa14cdd754f91cc6554c9e71929cce7', 'c9f0f895fb98ab9159f51fd0297e236d', 'e1671797c52e15f763380b45e841ec32', 'e1671797c52e15f763380b45e841ec32', 'a87ff679a2f3e71d9181a67b7542122c', '8277e0910d750195b448797616e091ad', '92eb5ffee6ae2fec3ad71c777531578f', '45c48cce2e2d7fbdea1afc51c7c6ad26', '0cc175b9c0f1b6a831c399e269772661', 'c9f0f895fb98ab9159f51fd0297e236d', '0cc175b9c0f1b6a831c399e269772661', 'cbb184dd8e05c9709e5dcaedaa0495cf']
for i in output:
    for j in range(33,128):
        my_md5=hashlib.md5()
        my_md5.update(chr(j).encode())
        if  my_md5.hexdigest() == i:
            print(chr(j),end="")
            break
#BaseCTF{a4bf43a5-3ff9-4764-bda2-af8ee4db9a8a}

week2

two_squares

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
flag=b'BaseCTF{}'
m=bytes_to_long(flag)
p=getPrime(128)
q=getPrime(128)
n=p*q
e=65537
c=pow(m,e,n)
x=p^2+q^2
print("e =",e)
print("c =",c)
print("x =",x)

"""
e = 65537
c = 42330675787206041757903427737108553993012805007294570657461042152628982126538
x = 209479773119142584969854470862023704936857416491817498021871883305658177375498
"""

利用sage中的two_squares()可以很方便的进行求解
（此题本意就是一道环境题，导致很多新手误解，再次道个歉）

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import gmpy2
e = 65537
c = 42330675787206041757903427737108553993012805007294570657461042152628982126538
x = 209479773119142584969854470862023704936857416491817498021871883305658177375498
p,q=two_squares(x)
p,q=int(p),int(q)
n=p*q
phin=(p-1)*(q-1)
d=gmpy2.invert(e,phin)
a=long_to_bytes(int(pow(c,d,n)))
print(a)
# b'BaseCTF{0760becd-cefaab0b094d}'

random_primes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
import random
def gen_n():
    primes=[getPrime(128) for _ in range(256)]
    n = 1
    for i in range(100):
        n *= primes[random.randint(0,127)]
    return primes,n

flag=b'BaseCTF{}'
m=bytes_to_long(flag)

assert len(flag)==45

primes,n = gen_n()
e = 0x010001

c=pow(m,e,n)

print("n =",n)
print("e =",e)
print("c =",c)
print("primes =",primes)

n很大很大，给了flag范围，可以得出flag为359位

素数都是128，利用3个素数（大约384位）即可比flag大

可以直接爆破

（数据太多就不贴了）

（好多师傅来问我最后为什么求出来是0，一看他们都是找出了所有素数，而且过程中都除以了n，导致最后n=1，这点需要注意）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from gmpy2 import *
# n =
# e = 
# c = 
# primes =
for i in primes:
    for j in primes:
        for k in primes:
            tn=i*j*k
            phi=(i-1)*(j-1)*(k-1)
            m=long_to_bytes(pow(c,invert(e,phi),tn))
            if b'BaseCTF' in m:
                print(m)
                exit()

basic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from Crypto.Util.number import *
import socketserver
import os
import random
import base64
import string

flag = os.getenv('GZCTF_FLAG').encode()


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):
        return self._recvall()
    
    def handle(self):
        printable_chars = string.ascii_letters + string.digits + string.punctuation
        optional=[b'A',b'B',b'C',b'D']
        for _ in range(100):
            secret= ''.join(random.choices(printable_chars, k=16)).encode()
            select=random.choice(optional)
            self.send(select)
            enc=b''
            if select==b'A':
                enc=base64.b64encode(secret)
            elif select==b'B':
                enc=secret.hex().encode()
            elif select==b'C':
                enc=bytes_to_long(secret)
                enc=str(enc).encode()
            elif select==b'D':
                enc=[i for i in secret]
                enc=str(enc).encode()
            self.send(enc)
            client_send=self.recv()
            if client_send!=secret:
                self.send("\nYou wrong!!!!!")
                exit()

        self.send(flag)
        self.send(b"\nConnection has been closed  =.=  ")
        self.request.close()


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


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


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

一道交互题，四种加密方式

主要实现四种加密方式

A：base64

B：直接转成十六进制

C：转成整型

D：每个字符转成ascii码

主要考察pwntools的使用

（本人抽象代码，请谅解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from pwn import *
import ast
import base64
from Crypto.Util.number import *

rem=remote("",)


for _ in range(100):
    a=rem.recvline().decode().strip()
    print(a,end=" ")
    b=rem.recvline()
    if a=='A':
        b=base64.b64decode(b)
    elif a=='B':
        b=bytes.fromhex(b.decode().strip())
    elif a=='C':
        b=int(b.decode().strip())
        b=long_to_bytes(b)
    elif a=='D':
        b=ast.literal_eval(b.decode().strip())
        c=b''
        for i in b:
            c+=long_to_bytes(i)
        b=c
    print(b)
    rem.send(b)
print(rem.recvall())
rem.interactive()

try_to_factor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import *
import random

flag=b'BaseCTF{}'+random.randbytes(64)
m=bytes_to_long(flag)

p,q,r,s,t=[getStrongPrime(512) for _ in range(5)]
N=p*q*r*s*t

n=p*q
e=65537
c=pow(m,e,n)


gift=random.randint(2,n)*(p-1)*(q-1)*(r-1)*(s-1)*(t-1)
while gift%2==0:
    gift//=2

print("N =",N)
print("c =",c)
print("gift =",gift)

"""
N = 162692163428762295773992659007654377270271126313772302197255271375236131917158614424426498628778734679898165422129699410934825650141972454562350664161510689489443251515884304101827584411577749250383438126881931889798597627663578045519256806107514170414321556291545302688028088470848270636776466672843710163017531472049823632822203461654253767303314505996071453898533003519236112138591066133289040889933161978131399309340741554076140734156174295730180874473301361701867633594222054688204666518058106672165786417002466165926062199279674267145233283545524775943767021416906072142236079753359492846480515376121887507681663761713445807717270089017438999615422884163666812016989696908657065537508715229685120221307021151610089917537155165897740417480127289719971512938348936259
c = 113962118676826667648935023618252851875440854724310328843964819392166304653581141146631375503931008732348730639629174670963727399860571217264854300057305570824097216782800531930906801885967717639795643406206813677461127762087560021634738167845077869308515223303820469892552545806179267969169748886980836435095
gift = 863514692222931709925579242743251211976114217396765747601042357918763818732391790491059528595917786523674732369068315533549380754409535403506339052401422249684188032949680148055803474336983973622610403448963752802490806614810077181934627694570685722842963961551889267501616799757825675192653489096007790143775773378495299981666657347802233798206597104474595281241837323214457344961462510183726339545608046357281265026013496037522835659867389206279894057481600882665189079672009577651494435000349624334685832217586703242422260870866432379257259316411280539845741932725104662417642890238587876489774492067722351467773093391502588019563488688309892102039611978767690653206664257400163618467825666105966072942726011447079204869750153256054140924951306811971422635104088608275908232688385437145325481792836532453258784103533536292492138405929815964841772656055397705840797739586953744563989819811944946916720655079908564653686456283647030055622241840292127096994325415897266379446446435164189216562921252341705747891518007710533906231225283309180960546212899099652226954393826875
"""

（此题算是临时加的，因为我做不出moectf第二周的题，想着增加点难度？所以我一开始就是准备给论文的，如果你能够认真静下心来看完论文，应该就可以解决这个问题了。论文中给出了算法流程，并不需要搞懂原理就可以出，很多师傅找的模板也是可以用的，将gift每次乘2爆破就行，我这里只是稍微改了一下希望不是拿到模板能直接出的那种。最后如果让你感到了不好的体验，我在这道个歉。

关于N和ϕ(n)\phi(n)进行分解的脚本，当然可以直接用，可以直接进行爆破x倍的2，然后套脚本也是可以的。我这里只是稍稍微魔改了一点。这里面也有很多脚本，感兴趣可以多看看

https://github.com/jvdsn/crypto-attacks/blob/master/attacks/factorization/known_phi.py）

先贴一下论文3-540-36492-7_25.pdf (springer.com)，主要是其中的第三部分

当然看不懂论文也没事，不过可以适当看一下2-Prime和3-Prime的部分，能够按算法流程实现就可以得到flag，主要是思想。

先从后往前看，最后对flag进行了2个素数的rsa加密，给了一个gift为k倍的ϕ(n)\phi(n)除去x倍的2。

从这里我们就可以看出来，要根据给的这个gift和之前的N来分解出p和q。

（分解出来是5个数，爆破一下就可以了）

算法流程：

我们可以知道：kϕ(n)=2x∗gift每一次分解时：随机取一个数w∈[2,N−2]计算数a1=w2s∗giftmod  Nfors=0,1...untila1≡1mod  N当结束后如果s=0则说明算法失效，一般为重新选取w。计算a2≡w2s−1∗giftmod  N保证a2≢±1，则gcd(N,a2+1)就是N的一个分解。由于一开始N不止有两个素数，所以这里需要判断一下分解出来的是不是素数。我们可以知道：k\phi(n)=2^x*gift\\ 每一次分解时： 随机取一个数w\in[2,N-2]\\ 计算数a_1=w^{2^s*gift}\mod N\quad for\quad s=0,1... until\quad a_1\equiv1\mod N\\ 当结束后如果s=0则说明算法失效，一般为重新选取w。\\ 计算a_2\equiv w^{2^{s-1}*gift}\mod N\\ 保证a_2\not\equiv\pm1，则gcd(N,a_2+1)就是N的一个分解。\\ 由于一开始N不止有两个素数，所以这里需要判断一下分解出来的是不是素数。

个人理解：

当a1≡1mod  时，a1就是模N下的平凡平方根通过计算我们知道a1≡a22≡1mod  N因为N是合数，只要a2≢±1mod  N，则a2称为模N下的非平凡平方根（这里只需要判断a2≢1mod  N,因为出计算a1时已经计算过一遍a2不等于1了)得a22−1≡(a2+1)∗(a2−1)≡0mod  N得(a2+1)∗(a2−1)=kN，因为N为合数得a2+1=x或者a2−1=x，这里x指kN中的一个因数那么我们通过求解gcd(N,a2+1)或者gcd(N,a2−1)就可以得到N的分解了（所以算法中gcd中的a2+1改成a2−1也是可行的）当a_1\equiv1\mod 时，a_1就是模N下的平凡平方根\\ 通过计算我们知道a_1\equiv a_2^2\equiv1\mod N\\ 因为N是合数，只要a_2\not\equiv\pm1\mod N，则a_2称为模N下的非平凡平方根\\ （这里只需要判断a_2\not\equiv1\mod N,因为出计算a_1时已经计算过一遍a_2不等于1了)\\ 得a_2^2-1\equiv(a_2+1)*(a_2-1)\equiv0\mod N\\ 得(a_2+1)*(a_2-1)=kN，因为N为合数\\ 得a_2+1=x或者a_2-1=x，这里x指kN中的一个因数\\ 那么我们通过求解gcd(N,a_2+1)或者gcd(N,a_2-1)就可以得到N的分解了\\ （所以算法中gcd中的a_2+1改成a_2-1也是可行的） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from random import randrange
from gmpy2 import *
from Crypto.Util.number import *
import itertools
def my_factors(N, gift):
    ans=[]
    factors=[N]
    while len(factors)>0:
        N=factors[0]
        w = randrange(2, N - 1)

        s = 0
        a_1 = pow(w, gift * pow(2,s), N)
        while a_1!=1:
            s=s+1
            a_1 = pow(w, gift * pow(2,s), N)
        
        if s!=0:
            a_2 = pow(w, gift * pow(2,s-1), N)
            if a_2!=N-1:
                p = gcd(N, a_2 + 1)
                if p!=1:
                    q=N//p
                    factors=factors[1:]
                    if isPrime(p):
                        ans.append(p)
                    else:
                        factors.append(p)
                    if isPrime(q):
                        ans.append(q)
                    else:
                        factors.append(q)
    return ans
N = 162692163428762295773992659007654377270271126313772302197255271375236131917158614424426498628778734679898165422129699410934825650141972454562350664161510689489443251515884304101827584411577749250383438126881931889798597627663578045519256806107514170414321556291545302688028088470848270636776466672843710163017531472049823632822203461654253767303314505996071453898533003519236112138591066133289040889933161978131399309340741554076140734156174295730180874473301361701867633594222054688204666518058106672165786417002466165926062199279674267145233283545524775943767021416906072142236079753359492846480515376121887507681663761713445807717270089017438999615422884163666812016989696908657065537508715229685120221307021151610089917537155165897740417480127289719971512938348936259
c = 113962118676826667648935023618252851875440854724310328843964819392166304653581141146631375503931008732348730639629174670963727399860571217264854300057305570824097216782800531930906801885967717639795643406206813677461127762087560021634738167845077869308515223303820469892552545806179267969169748886980836435095
gift = 863514692222931709925579242743251211976114217396765747601042357918763818732391790491059528595917786523674732369068315533549380754409535403506339052401422249684188032949680148055803474336983973622610403448963752802490806614810077181934627694570685722842963961551889267501616799757825675192653489096007790143775773378495299981666657347802233798206597104474595281241837323214457344961462510183726339545608046357281265026013496037522835659867389206279894057481600882665189079672009577651494435000349624334685832217586703242422260870866432379257259316411280539845741932725104662417642890238587876489774492067722351467773093391502588019563488688309892102039611978767690653206664257400163618467825666105966072942726011447079204869750153256054140924951306811971422635104088608275908232688385437145325481792836532453258784103533536292492138405929815964841772656055397705840797739586953744563989819811944946916720655079908564653686456283647030055622241840292127096994325415897266379446446435164189216562921252341705747891518007710533906231225283309180960546212899099652226954393826875


primes=my_factors(N,gift)
print(primes)
permutation=itertools.combinations(primes,2)
for i in permutation:
    p,q=i
    p,q=int(p),int(q)
    flag=long_to_bytes(pow(c,inverse(65537,(p-1)*(q-1)),p*q))
    if b'BaseCTF' in flag:
        print(flag)
        break
#b'BaseCTF{ed4bff90-d1f4-4f0f-a3bd-999c54d9eeb7};\xef\xd7"X\xceglz\xc2l\xc3\xf0\x04\n$I\x00\xda\rT\xc5\xef\xc9t]\x0c\xae@\xdcO5\x02\xa8\xd6/{5\xacD5\xda\x11{\x80\x80\xa3\t#\x97\x871L\x10\r\x122z\xe1\x89%\x85\xdb\x94'

week3

没有n啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import *
import gmpy2

flag=b'BaseCTF{}'
m=bytes_to_long(flag)

p=getPrime(512)
q=getPrime(512)

n=p*q
e=65537

phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)

c=pow(m,e,n)
x=pow(n,e,c)
print("c =",c)
print("e =",e)
print("d =",d)
print("x =",x)
'''
c = 52453423663797600504896811946820841317615798875871627840172711423749946998217916744135290476795328543876098295227017753117609268701786914053599060330837226980969490439739651088710549890669593587642238827462108900683237797139569260570711611781514337884756698142193277516649805710242748531658979160170193283558
e = 65537
d = 54297831548863701092644190086258072883163378307246681513317422545902442650340916001357605211715836911877651782099787873046987096258918495734824011752504203578982947618784736181975847356304742402103468329660346526185908618978851982007496096394151821403282347897417590596861323293706611997134962231129075032641
x = 40635864473997460751766935373772107585133301579524000836637683731949939348171187931595274511243052505604832873086269554842194695737052043633079044688826020656068356561856848814530947955429343483847291398607359454851926470168457852479044154798114087493843073091985855839008222762224952503563764527380033064437
'''

n=c+ax=nemod(c)二项式定理：x=aemod(c)e∗dc=1mod(ϕ(c))xdc=ae∗dc=amod(c)n=c+a\\ x=n^e\quad mod(c)\\ 二项式定理：x=a^e\quad mod(c)\\ e*d_c=1\quad mod(\phi(c))\\ x^{d_c}=a^{e*d_c}=a\quad mod(c)

ϕ(c)\phi(c)可以通过网站在线分解

也可以直接利用sage中euler_phi()求解，就是时间有点久

factordb.com

之后给了d就正常解了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2

c = 52453423663797600504896811946820841317615798875871627840172711423749946998217916744135290476795328543876098295227017753117609268701786914053599060330837226980969490439739651088710549890669593587642238827462108900683237797139569260570711611781514337884756698142193277516649805710242748531658979160170193283558
e = 65537
d = 54297831548863701092644190086258072883163378307246681513317422545902442650340916001357605211715836911877651782099787873046987096258918495734824011752504203578982947618784736181975847356304742402103468329660346526185908618978851982007496096394151821403282347897417590596861323293706611997134962231129075032641
x = 40635864473997460751766935373772107585133301579524000836637683731949939348171187931595274511243052505604832873086269554842194695737052043633079044688826020656068356561856848814530947955429343483847291398607359454851926470168457852479044154798114087493843073091985855839008222762224952503563764527380033064437

phic=(2-1)*(3-1)*(73-1)*(3967-1)*(6373-1)*(95592293-1)*(216465863-1)*(4744823012787277141-1)*(48245998253859255581546561942142167304434549996919484957120717763726325509833409296170471619434291990255044694414983821250538266717293535917534918221352198192885071310932646412147737114561229291373456448363184353049796801297876664512630305475226391199481032049429-1)
#phic=euler_phi(c)
dc=gmpy2.invert(e,phic)
a=pow(x,dc,c)

print(long_to_bytes(pow(c,d,a+c)))

exgcd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from Crypto.Util.number import *

flag=b'BaseCTF{}'
m=bytes_to_long(flag)

p=getPrime(1024)
q=getPrime(1024)

n=p*q
e1=3747
e2=2991

c1=pow(m,e1,n)
c2=pow(m,e2,n)

print("n =",n)
print("e1 =",e1)
print("e2 =",e2)
print("c1 =",c1)
print("c2 =",c2)

"""
n = 27855350163093443890983002241607629119744539643165776358993469078731521668677421483556132628708836721737685936980427467856642738196111748018522018598646125626995613169001111504706363742194664774823604738939411512861441742683157275818500991834651769368178320088982759626122029956515159435424882855075032400667120376075618896752694718491438251810609878021717559466498493103257912108879328270813061231904227056671621363669388496383136964549879459562004569059185078204867346250733489663015417879915436157806942021693920206071715538430633494012923651469196048546309592946901609803631751035364478773126967010589504275776307
e1 = 3747
e2 = 2991
c1 = 24426579024062518665031958216110619832653602343205488454298659533869220501923184793828421371206493659949730138867555889074137026401207985428160803910695088081370233571905915349589146504374710444468715701305061060934519410886010929009297226496448218819742287990364436349188987723637449590579092391100714056589967894609950537021838172987840638735592599678186555961654312442380755963257875487240962193060914793587712733601168204859917001269928487633954556221987632934190217367502677285906521385169669644977192556145782303526375491484736352799180747403161343130663661867413380222714012960607473395828938694285120527085083
c2 = 6932145147126610816836065944280934160173362059462927112752295077225965836502881335565881607385328990881865436690904056577675885697508058289570333933837515526915707121125766720407153139160751343352211421901876051228566093038929625042619250168565502734932197817082848506826847112949495527533238122893297049985517280574646627011986403578166952789317461581409161873814203023736604394085875778774834314777046086921852377348590998381648241629124408514875110073073851913857329679268519229436092660959841766848676678740851087184214283196544821779336090434587905158006710112461778939184327386306992082433561460542130441825293
"""

共模攻击，但$$e_1和e_2不互素$$

c1=me1mod  nc2=me2mod  n通过扩展欧几里得计算：s1∗e1+s2∗e2=sc1s1∗c2s2=ms1∗e1+s2∗e2=msc_1=m^{e1}\mod n\\ c_2=m^{e2}\mod n\\ 通过扩展欧几里得计算：s_1*e_1+s_2*e_2=s\\ c_1^{s_1}*c_2^{s_2}=m^{s_1*e_1+s_2*e_2}=m^s

最后得到的是mgcd(e1,e2)m^{gcd(e1,e2)}，最后开个根即可

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from gmpy2 import *
n = 27855350163093443890983002241607629119744539643165776358993469078731521668677421483556132628708836721737685936980427467856642738196111748018522018598646125626995613169001111504706363742194664774823604738939411512861441742683157275818500991834651769368178320088982759626122029956515159435424882855075032400667120376075618896752694718491438251810609878021717559466498493103257912108879328270813061231904227056671621363669388496383136964549879459562004569059185078204867346250733489663015417879915436157806942021693920206071715538430633494012923651469196048546309592946901609803631751035364478773126967010589504275776307
e1 = 3747
e2 = 2991
c1 = 24426579024062518665031958216110619832653602343205488454298659533869220501923184793828421371206493659949730138867555889074137026401207985428160803910695088081370233571905915349589146504374710444468715701305061060934519410886010929009297226496448218819742287990364436349188987723637449590579092391100714056589967894609950537021838172987840638735592599678186555961654312442380755963257875487240962193060914793587712733601168204859917001269928487633954556221987632934190217367502677285906521385169669644977192556145782303526375491484736352799180747403161343130663661867413380222714012960607473395828938694285120527085083
c2 = 6932145147126610816836065944280934160173362059462927112752295077225965836502881335565881607385328990881865436690904056577675885697508058289570333933837515526915707121125766720407153139160751343352211421901876051228566093038929625042619250168565502734932197817082848506826847112949495527533238122893297049985517280574646627011986403578166952789317461581409161873814203023736604394085875778774834314777046086921852377348590998381648241629124408514875110073073851913857329679268519229436092660959841766848676678740851087184214283196544821779336090434587905158006710112461778939184327386306992082433561460542130441825293
s,s1,s2=gcdext(e1,e2)

m=(pow(c1,s1,n)*pow(c2,s2,n))%n

print(long_to_bytes(iroot(m,s)[0]))
#b'BaseCTF{feb7e1ae-a8f7-4fc4-8d6d-945a45cc3f6d}'

wiener?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from Crypto.Util.number import *
import decimal
flag=b"BaseCTF{}"
m = bytes_to_long(flag)


p = getPrime(1024)
q = getPrime(1024)
n=p*q

e=65537
c=pow(m,e,n)

print("e =",e)
print("c =",c)

decimal.getcontext().prec = 648
P=decimal.Decimal(p)
Q=decimal.Decimal(q)
leak=decimal.Decimal((3*P*Q-1)/(3*Q*Q))
print("leak =",leak)

"""
e = 65537
c = 11032748573623426359632659657114807044712138586316710250985606809252700461490504487308849626514319062562557448839550994242999334882617031487618174168038491566640081840111747765753878087564318833273878755416584962921669911444225959335274753391800995531023212276838665202257007640354237043291129197348884914956663597240094662207929658519596987351984403258345205873566463643624175318315064440456858013874962784792564480286904620663695194689839431808082976248378509181327101557380978849545906691903896662095520288964101796965095129861467059775556110616007889846240936219381379219605528051627402300580239311202137582442057
leak = 0.829374344780877053838760251345359097311540811993463349625630085472892814959843248358036249898871908548743719153319438638517170060651237635838827482534816419091949205584951292517303330452910012749674475329235689229498752425379611083979518257734473992186831474208400813283887045691145481237726578827559198828469462343342343287720369159899636816373592067698883361360269728719786071024354151682314608072902347335691012713629816579496252896260869382806838857194293618332286500427694077400072428506897829689703872985954772105672992293334668485358785863779749153981721900135318166811250762946069962348114491411585418993494561587403918162681937152503739843
"""

直接摘抄的wiener攻击的思想，连分数定理：

∣a−cd∣<12∗d2可得cd就是a的一个连分数近似\left|a-\frac{c}{d}\right|<\frac{1}{2*d^2}\\ 可得\frac{c}{d}就是a的一个连分数近似

（至于定理证明我也不会，不好意思喵）

推导：

leak=3∗P∗Q−13∗Q∗Qleak=PQ−13∗Q2∣leak−PQ∣=13∗Q2<12∗Q2之后计算leak的连分数，即可得到p和qleak=\frac{3*P*Q-1}{3*Q*Q}\\ leak=\frac{P}{Q}-\frac{1}{3*Q^2}\\ \left|leak-\frac{P}{Q}\right|=\frac{1}{3*Q^2}<\frac{1}{2*Q^2}\\ 之后计算leak的连分数，即可得到p和q 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
e = 65537
c = 11032748573623426359632659657114807044712138586316710250985606809252700461490504487308849626514319062562557448839550994242999334882617031487618174168038491566640081840111747765753878087564318833273878755416584962921669911444225959335274753391800995531023212276838665202257007640354237043291129197348884914956663597240094662207929658519596987351984403258345205873566463643624175318315064440456858013874962784792564480286904620663695194689839431808082976248378509181327101557380978849545906691903896662095520288964101796965095129861467059775556110616007889846240936219381379219605528051627402300580239311202137582442057
leak = 0.829374344780877053838760251345359097311540811993463349625630085472892814959843248358036249898871908548743719153319438638517170060651237635838827482534816419091949205584951292517303330452910012749674475329235689229498752425379611083979518257734473992186831474208400813283887045691145481237726578827559198828469462343342343287720369159899636816373592067698883361360269728719786071024354151682314608072902347335691012713629816579496252896260869382806838857194293618332286500427694077400072428506897829689703872985954772105672992293334668485358785863779749153981721900135318166811250762946069962348114491411585418993494561587403918162681937152503739843
from Crypto.Util.number import *
cf = continued_fraction(leak)
convers = cf.convergents()
for pkd in convers:
    # possible k, d
    pp, pq = pkd.as_integer_ratio()
    pp=int(pp)
    if pp.bit_length()==1024 and isPrime(pp):
        flag=long_to_bytes(int(pow(c,inverse(e,pp-1),pp)))
        if b'Base' in flag:
            print(flag)
            break
#b'BaseCTF{9431ee53-5d5c-4b0b-956f-1eafff6c9e87}'

没有n啊_pro

前言：

在之前西瓜杯的比赛中我出一次这个题，然后在前几天sigenzhe师傅在我博客低下说了另一种不用给x的解法，所以我重新生成了一下数据搬了过来，感谢sigenzhe师傅。

当时博客里的sigenzhe师傅的原话：

《给你d又怎样》 这道题可以不要 hint 也能做出来。
n为256位，那phi(n)的位数在256、255、254这个区间内。有了e和d，ed=k * phi(n) + 1 。且 k < e 可以通过爆破k的方法 得到几十个可能的 phi(n) 。而且最重要是 phi(n)的位数小于256，是可以分解的，phi(n) = (p-1) * (q-1) ，那我们通过组合phi(n)的因子，就有可以得到（p-1) 。
最终检测退出的条件是，因子组合排列相乘，只要位数是128 且 + 1后是素数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
import gmpy2

flag=b'BaseCTF{}'
m=bytes_to_long(flag)
p=getPrime(128)
q=getPrime(128)

n=p*q
e=65537

phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)

assert d<phi

c=pow(m,e,n)
print("c =",c)
print("e =",e)
print("d =",d)

已知：e∗d≡1mod  ϕ(n)那么e∗d=1+k∗ϕ(n)，k∗ϕ(n)=e∗d−1为了方便想我还给了一个条件d<ϕ(n)可以得到k<e，我们通过遍历e的范围即可得到多个kiϕ(n)ϕ(n)的范围可以推测为256之后可以求解ϕ(n)的全分解，对全分解进行排列组合即可得到已知：e*d\equiv1\mod\phi(n)\\ 那么e*d=1+k*\phi(n)，k*\phi(n)=e*d-1\\ 为了方便想我还给了一个条件d<\phi(n)\\ 可以得到k<e，我们通过遍历e的范围即可得到多个k_i\phi(n)\\ \phi(n)的范围可以推测为256\\ 之后可以求解\phi(n)的全分解，对全分解进行排列组合即可得到

当然也可以直接对e*d-1进行分解然后排列组合，但好像耗时比较长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#sage
from Crypto.Util.number import *
import itertools
c = 78919950899709764543039048006935881842075789773495004639436106636461009323420
e = 65537
d = 13002488326322253055272696035053386340217207134816593767440035447757509399233
p_bits=128
q_bits=128
def get_phi(e, d):
    k_phi = e*d -1
    result = []
    for k in range(e,2,-1):
        if k_phi % k == 0:
            tmp = k_phi // k
            if int(tmp).bit_length()==p_bits+q_bits:
                result.append(tmp)
    return result
def main():
    phi_list = get_phi(e,d)  #获得可能的phi_n列表
    count = len(phi_list)
    print(f'一共有{count}个可能的phi')
    count = 0
    for phi in phi_list:
        count += 1
        print(f'{count} 正在尝试爆破 {phi}')
        factors = factor(phi)  # 分解phi_n得到质因子列表
        result = []
        for i in factors:
            num, times = int(i[0]), i[1]
            result += [num] * times

        if len(factors)>1:
            s = set()
            for r in range(1, len(result) + 1):
                combination = list(itertools.combinations(result, r))
                for i in combination:
                    s.add(i)
            ans=[]
            for i in s:
                tmp=1
                for j in i:
                    tmp=tmp*j
                ans.append(tmp)
            for num in ans:
                if int(num+1).bit_length()==p_bits and is_prime(num+1):
                    p = num+1
                    q = phi // num + 1
                    if is_prime(q):
                        n = p * q
                        flag=long_to_bytes(int(pow(c,d,n)))
                        if b'BaseCTF' in flag:
                            print(flag)
                            return


if __name__ == '__main__':
    main()
#b'BaseCTF{3e226a94-babb27696416}'

week4

哎呀数据丢失了

具体分析我就不说了，最简单的证书分析，base64解码后前三个数据分别就是n,e,d。

贴一篇文章：https://tover.xyz/p/pem-by-hand/

说几句证书相关的关键点，一般来说手撕确实的证书分析就是把数据base64解密一下再转十六进制分析。

接下来就是找02开头的数据，然后看02后面的数据是不是跟着长度（一般根据n的bits来判断）

如果不对，那就从新开始，删去第一个字符在进行base64解密，依次反复知道正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from Crypto.Util.number import *
from gmpy2 import *


n=0x00bd278484122aef9a69ec647290219ded06edd2b7611721b326850b2f5060daeed7694356667c479ca9ccb6969f4fbe6dc7fa6759aca21d8a96a881a8e4a0217732757e649d503191511fa96da42ed1da2fa3bc8c9c65fbd9c0dd6f430359ac45e455d32c5b0ea29d21e647ff80e50abcbb80f76adb67007a04e85dbaeb4c8f1d
e=0x010001
d=0x2265e355593071ae3501062b4746b5bf7af918cebc5b46879bc3aa0b0aa4f26b68c4fdb7e29f4b2e943a6421f40abe689c6b4f0c21b6c184886d5056f46ca26908540ec07b82ad47e667971a01fac6162e93a7fc61aed5660f826aeba34d78accd18fc59e7921701f10ff51d52883706b864287cfdb34e309c93829d29d867c9

with open("out",'rb') as f:
    c=f.read()
    m=bytes_to_long(c)
    print(long_to_bytes(pow(m,d,n)))

"""30 
82 025c 
0201 00 
02 81 81 00bd278484122aef9a69ec647290219ded06edd2b7611721b326850b2f5060daeed7694356667c479ca9ccb6969f4fbe6dc7fa6759aca21d8a96a881a8e4a0217732757e649d503191511fa96da42ed1da2fa3bc8c9c65fbd9c0dd6f430359ac45e455d32c5b0ea29d21e647ff80e50abcbb80f76adb67007a04e85dbaeb4c8f1d
02 03 010001
02 81 80 2265e355593071ae3501062b4746b5bf7af918cebc5b46879bc3aa0b0aa4f26b68c4fdb7e29f4b2e943a6421f40abe689c6b4f0c21b6c184886d5056f46ca26908540ec07b82ad47e667971a01fac6162e93a7fc61aed5660f826aeba34d78accd18fc59e7921701f10ff51d52883706b864287cfdb34e309c93829d29d867c9
02 41 00c6e091a25cd8e75937af8370674f71ff000ce87a49a8374e654fe3b1877c63813c895c3cb83da4c3bc457aeedef78574bba69b1ac3a21d3fcd0b3a1ffa05aa93
02 41 00f37c0714f1d2e836e73a806ddb3509245539ceb363623d3e4f7887456580519cb513f6564508c8d5ea6b9ccb0b67b58168243bb96d61e8db6377413bbb95fd8f

02404e066d1cb630a3136db57e6beb1c5
02d2b67e50d953859fa77e50fffe697f6b20d7e16a1fbe6b36dd7bfaaab6ceecf7d2ce200984f889ad11d30fa6cf13aa7e1
024100a3c4583f0e27fd68703e3903aadd11390ed9c2dd858b1e063b0da66e56c6e81daeedae52783c60590143404291793febba5
0249ba3a6a72868ce5d61ffd9f2a1
0240369cfe9a217
02c39b0d07fdf8a4d82fe362177dd92fc82
02d699914b9a634016f6e30e270bde8c2d0068743a77d2fa8831cba75536e0f2f1578ddd4e4b5e7685"""

rabin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *


flag=b"BaseCTF{}"
m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
assert p%4==3 and q%4==3
n = p*q
e = 4

c = pow(m,e,n)
print("p=",p)
print("q=",q)
print("n=",n)
print("c=",c)
print("e=",e)
"""
p= 8531212975719216550108614256955774722172741885676113601617182716356239301381951899737237219659253655889636684200345109462928796329670321336864298557778843
q= 7443256287912111739335729314443559886458007838130371799255078565502662459436043455787869631999073617967343884377537828940738213460508765519478956421282871
n= 63500004625039456439237191267891267558404574431112995926594213383621331385226487443753506088788203040258384788149958095020759745138424276657604371402824844725005596890673468964961037168078105356669148960568974603581485045691990626520286184874115519591663033533771400334558853058140717812903874350138362098253
c= 51452608438757130697131508192775727191605112918772187364577097224326062184288501602000700342623122861398852536963355962672293705131887315354242193416090384360837672258861475017098419459125395949090523474744886423754439919504732741712693909507972791203801494594878447921609420574365853676576693694677914169353
e= 4
"""

高次rabin攻击

详见：文章列表 | NSSCTF

c≡m4≡x2mod  nc≡m4≡x2mod  p说明c是模p下的二次剩余可得这条结论cp−12≡1mod  p（详细证明看上面NSSCTF中xenny师傅的文章）x2≡c≡cp−12∗c≡cp+12mod  p由条件p≡3mod  4，可知cp+12可以进行开方得：x1≡cp+14mod  p和x2≡(p−cp+14)mod  p同理得：x3≡cq+14mod  q和x4≡(q−cq+14)mod  q之后对x1,x2,x3,x4都再进行一次rabin就可以得到16个mi进行筛选可得最终flagc\equiv m^4\equiv x^2\mod n\\ c\equiv m^4\equiv x^2\mod p\quad说明c是模p下的二次剩余\\ 可得这条结论c^{\frac{p-1}{2}}\equiv 1\mod p\\ （详细证明看上面NSSCTF中xenny师傅的文章）\\ x^2\equiv c\equiv c^{\frac{p-1}{2}}*c\equiv c^{\frac{p+1}{2}}\mod p\\ 由条件p\equiv3\mod4，可知c^{\frac{p+1}{2}}可以进行开方\\ 得：x_1\equiv c^{\frac{p+1}{4}}\mod p和x_2\equiv(p-c^{\frac{p+1}{4}})\mod p\\ 同理得：x_3\equiv c^{\frac{q+1}{4}}\mod q和x_4\equiv(q-c^{\frac{q+1}{4}})\mod q\\ 之后对x_1,x_2,x_3,x_4都再进行一次rabin就可以得到16个m_i\\ 进行筛选可得最终flag 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from Crypto.Util.number import *
import math

p= 7069399887135404147313451925856463790122288322955120353958439275669624760478622857767374372872346990136954266792268812402268519788981659317134531701377703
q= 7140401794925570651681210965995716787861669619864423417950517149172165700476247742598189428763096590450485848849559705021102255619953633260576326755189491
n= 50478355643148266354923007679620780526141911052216183219350733856301203909504117920782157926474133059342037694939720794471142298089233400685616528009799838411628460021560455031638939642439782783664643276781622313533393143794433785002028042268329216889290321025657400866309989050114906562764560145969527319173
c= 4087656016708624348430154736700209864616058176527780296412388210036556189223356217878476122554309456912053098904757651242467846016533157893713565869179648449607552843430116377433424175512165110689917185788645907642250661954679293286430479127383793220643392349769864898681882146542120386576626400193522553192
e= 16
  
def rabin(c):
    m1 = pow(c, (p + 1) // 4, p)
    m2 = p-pow(c, (p + 1) // 4, p)
    m3 = pow(c, (q + 1) // 4, q)
    m4 = q-pow(c, (q + 1) // 4, q)

    return m1,m2,m3,m4

cs = [c]
lge=math.log(e,2)
for i in range(int(lge)):	#range里放log2e
    t = set()
    for c2 in cs:
        x = rabin(c2)
        for j in x:
            t.add(j)
    cs = list(t)
for i in cs:
    flag=long_to_bytes(i)
    if b'BaseCTF' in flag:
        print(flag)
#BaseCTF{01c28b9c-7924-4c04-b71d-1cca15342618}


extendmd5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from Crypto.Util.number import *
import hashlib
import socketserver
import signal
import os
import random 
flag = os.getenv('GZCTF_FLAG')


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):
        return self._recvall()

    def my_md5(self,text):
        mymd5=hashlib.md5()
        mymd5.update(text)
        return mymd5.hexdigest()
    def handle(self):
        signal.alarm(30)

        c=random.randint(1,64)
        want=random.randbytes(c)
        want_md5=self.my_md5(want)
        self.send(want_md5.encode())

        while True:
            self.send(b"\nPlease input the secret:")
            secret = self.recv()

            final=want+secret
            final_md5=self.my_md5(final)

            self.send(b"\nPlease input your md5:")
            your_md5=self.recv().decode()
            if  final_md5 == your_md5:
                self.send(flag.encode())
                break
        
            
        self.send(b"\nConnection has been closed  =.=  ")
        self.request.close()


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


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


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

（前言：循环100次单纯想检验一下写代码解决，而不是直接用别人的脚本生成一个结果就好了，所以可能会有点恶心，请见谅）

就是放在密码里得md5扩展攻击

原始内容长度是随机，爆破一下就可以了。

（以下原理讲的可能不是很清楚，可以看结合第二周web中的视频讲解观看）

原理：

首先需要从md5加密过程开始说起，md5加密是分组进行加密的，每组512bits。在一开始，需要对明文进行填充，如果最后分组不满512bits的需要填充到512bits；如果原始内容刚刚好可以分组，那也需要填充一个512bits的分组。md5扩展攻击最重要的就是理解填充规则。

填充规则：

首先添加一个固定字节b’\x80’，之后需要填充由原始明文长度计算得来的8个字节，这8个字节是一定需要填充的，所以如果这个时候明文已经到达了57bytes，再填充8字节就会不再是刚好的64bytes(512bits)，所以这时候我们要新添一个分组。最后八字节为原始明文长度，填充方式为小端序。

比如len=10，先填上个b’\x80’，这时候长度为11，可以填充8字节，那么再填充b’\x00’*(64-8-1-10)，64为一个分组的字节数，8为最后需要填充的数据，1是最开始填充的b’\x80’，最后填充八个字节为b’\x50\x00\x00\x00\x00\x00\x00\x00’。

比如len=33，先填上个b’\x80’，那么再填充b’\x00’*(64-8-1-33)，最后填充八个字节为b’\x08\x01\x00\x00\x00\x00\x00\x00’。原始数据为264bits，验证：0x108=264

比如len=56，先填上个b’\x80’，这时候有57字节，再填充8字节的话为65字节，那么不满足分组条件，所以这时候我们需要再填充b’\x00’*(64*2-8-1-56)，也就是63个0字节，最后填充八个字节为b’\xc0\x01\x00\x00\x00\x00\x00\x00。原始数据为448bits，验证：0x01c0=448

当我们填充完数据后，从第一个分组开始进行md5加密，加密过程可以不用在意，只需知道每次加密后得到32个16六进制，加密后的结果分成四组，当成下一个分组加密的IV，这是攻击的关键。

一开始，我们知道原始内容的md5值，并且原始内容长度小于64字节。这时候，服务器我们可以在原始内容后面添加自定义数据，那么最重要的就是，根据填充规则，我们只要知道原始内容长度，我们就可以自己进行填充，只要我们自己填充的数据与md5加密时一样，最后计算出的md5值也会一样，那么这个结果是作为下一组内容加密时的IV。

所以我们像服务器发送数据为：填充内容+任意内容

最后发送 任意内容的md5结果，当然这里需要根据服务器一开始传来的md5值作为IV来进行加密

这里我用GPT生成了一份md5加密代码，在加密时传送进去IV值，最重要的是，我这份源码是原始的md5加密代码，我们需要在”任意内容“前填上64bytes*分组数，而且在加密函数(my_md5)中，我们只要最后一个分组的结果，所以我们需要跳过前面几个分组（在代码中skip变量处体现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
from pwn import *

import struct
import math

# 定义MD5所需的常量
T = [int(4294967296 * abs(math.sin(i + 1))) & 0xFFFFFFFF for i in range(64)]


# 定义左旋转函数
def left_rotate(x, c):
    return (x << c) | (x >> (32 - c))


# 定义MD5主循环所需的四个基本函数
def F(x, y, z):
    return (x & y) | (~x & z)


def G(x, y, z):
    return (x & z) | (y & ~z)


def H(x, y, z):
    return x ^ y ^ z


def I(x, y, z):
    return y ^ (x | ~z)


# 定义MD5算法
def my_md5(message, A, B, C, D, skip):
    # 初始化变量
    a, b, c, d = A, B, C, D

    # 填充消息
    original_length = len(message) * 8
    message += b'\x80'
    while (len(message) * 8) % 512 != 448:
        message += b'\x00'
    message += struct.pack('<Q', original_length)

    # 处理每个512位（64字节）块
    # 跳过前几个分组
    for i in range(64 * skip, len(message), 64):
        block = message[i:i + 64]
        X = struct.unpack('<16I', block)

        # 备份当前的a, b, c, d值
        AA, BB, CC, DD = a, b, c, d
        # 进行四轮操作，每轮16步
        for i in range(64):
            if 0 <= i <= 15:
                k, s, func = i, [7, 12, 17, 22][i % 4], F(b, c, d)
            elif 16 <= i <= 31:
                k, s, func = (5 * i + 1) % 16, [5, 9, 14, 20][i % 4], G(b, c, d)
            elif 32 <= i <= 47:
                k, s, func = (3 * i + 5) % 16, [4, 11, 16, 23][i % 4], H(b, c, d)
            elif 48 <= i <= 63:
                k, s, func = (7 * i) % 16, [6, 10, 15, 21][i % 4], I(b, c, d)

            temp = b + left_rotate((a + func + X[k] + T[i]) & 0xFFFFFFFF, s)
            a, b, c, d = d, temp & 0xFFFFFFFF, b, c

        # 将结果加到当前的a, b, c, d
        a = (a + AA) & 0xFFFFFFFF
        b = (b + BB) & 0xFFFFFFFF
        c = (c + CC) & 0xFFFFFFFF
        d = (d + DD) & 0xFFFFFFFF
    # 返回哈希结果
    return struct.pack('<4I', a, b, c, d).hex()


rem = remote("challenge.basectf.fun", 33573)

for _ in range(100):
    want_md5 = rem.recv(32).decode()  # 接收原始数据的md5

    # 计算成iv
    iv = []
    for i in range(4):
        tmp = ""
        for j in range(4):
            tmp += want_md5[(i + 1) * 8 - (j + 1) * 2:(i + 1) * 8 - j * 2]
        iv.append(int(tmp, 16))

    # 爆破长度
    for i in range(32, 64):
        rem.recvuntil(b"Please input the secret:")

        # 填充消息
        payload = b''
        payload_length = i * 8
        payload += b'\x80'
        while ((i + len(payload)) * 8) % 512 != 448:
            payload += b'\x00'
        payload += struct.pack('<Q', payload_length)
        payload += b'naby'

        rem.sendline(payload)

        # 计算填充数据后的有几个分组，需要跳过计算
        skip = (i + len(payload) - 4) // 64
        A, B, C, D = iv
        message = b'a' * (64 * skip) + b'naby'
        res = my_md5(message, A, B, C, D, skip)
        rem.recvuntil(b"Please input your md5:")
        rem.sendline(res.encode())
        rem.recvline()
        m = rem.recvline()
        if b'correct' in m:
            print(_, want_md5, i, m)
            break

rem.interactive()

Fin

猜猜看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from Crypto.Util.number import *
import socketserver
import numpy as np
import random
import ast
import os
flag = os.getenv('GZCTF_FLAG').encode()
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):
        return self._recvall()
    
    def handle(self):
        assert len(flag)==45
        self.send(b"hello.")

        m=bytes_to_long(flag)
        m=bin(m)[2:]

        length=len(m)

        x=np.array([int(i) for i in m])
        T=np.array([[random.getrandbits(1) for _ in range(length)] for __ in range(length)])

        y=np.dot(x,T)
        self.send(str(list(y)).encode())

        while True:
            user_input=ast.literal_eval(self.recv().strip().decode('utf-8'))
            if isinstance(user_input,list):
                try:
                    mat=np.array(user_input)
                    res=list(np.dot(mat,T))
                    self.send(str(res).encode())
                except:
                    self.send(b'wrong!!')
            else:
                self.send(b'wrong!')
                break
        

        self.send(b"\nConnection has been closed  =.=  ")
        self.request.close()


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


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


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

灵感来自借nss3rd研究MT19937题目时想出来的点子。

参考：浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)

有提到一个黑盒测试，通过矩阵乘法的性质，利用左乘一个只有一个1，其他都位0的矩阵，可以得到右矩阵的某一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import numpy as np
from Crypto.Util.number import *
from pwn import *
p=remote()
p.recvline()
flag=eval(p.recvline())
length=45*8-1
T=[]
for i in range(length):
    x=[0]*i+[1]+[0]*(length-1-i)
    p.sendline(str(x).encode())
    T.append(eval(p.recvline()))
T=np.array(T)
t_ni=np.linalg.inv(T)

m=np.dot(flag,t_ni)
m=np.round(m)
flag=""
for i in m:
    if i==1:
        flag+='1'
    else:
        flag+='0'
print(long_to_bytes(int(flag,2)))

p.interactive()

ECB是不安全的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
import socketserver
import os
import base64
flag = os.getenv('GZCTF_FLAG').encode()
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):
        return self._recvall()
    
    def handle(self):

        self.send(b"the server will connect you entered to the front of flag.")
        self.send(b"then you will receive ciphertext(b64encode) encrypted by AES-ECB.")

        key=os.urandom(16)
        my_aes=AES.new(key=key,mode=AES.MODE_ECB)
        self.send(base64.b64encode(my_aes.encrypt(pad(flag,AES.block_size))))

        while True:
            self.send(b':')
            cin=self.recv()
            final=cin+flag
            self.send(base64.b64encode(my_aes.encrypt(pad(final,AES.block_size))))

            
        self.send(b"\nConnection has been closed  =.=  ")
        self.request.close()


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


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


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

灵感来源之前国外的一场，也没有给源码，甚至没有提示。

后面在cryptohack上也遇到了，就拿来出了一题。

这题我们可以在原始内容前面加上 任意内容。

通过测试AES加密的密文，我们可以知道flag的长度。

之后有两种方法，exp里都有写，但是从后往前爆破flag的也个点我没搞懂就先不讲了，只讲从前往后的。

先讲利用原理：ECB模式中，算法对每一个分组进行加密，与前后分组无关，当密钥固定之后，只要这一个分组的明文相同，那么加密之后的密文也相同。

这里直接举个例子。

比如flag是BaseCTF{0123456789}，长度为19.一开始服务器给我们发送密文（base64解密之后）为32字节，为两个AES-ECB分组。我们给服务器依次发送1-16字节的数据，发送一个1字节时，服务器加密20字节，最后密文还是32字节；当发送14字节时，服务器加密33字节，最后密文为48字节，发生了变化，在这时，我们就可以计算出flag长度为32-(14-1)=19。

之后利用刚刚讲的原理，我们发送flag长度填充到一个AES-ECB分组长度减一的内容，比如这里我们发送31字节的a，这时候服务器加密：

aaaaaaaaaaaaaaaa∣aaaaaaaaaaaaaaB∣aseCTF{0123456789}aaaaaaaaaaaaaaaa|aaaaaaaaaaaaaaB|aseCTF\{0123456789\}

之后我们爆破flag的第一个字节，少发送一个字节，这时候服务器加密：

aaaaaaaaaaaaaaaa∣aaaaaaaaaaaaaaa?∣BaseCTF{0123456789}aaaaaaaaaaaaaaaa|aaaaaaaaaaaaaaa?|BaseCTF\{0123456789\}

当我们爆破到这个字节为B时，服务器加密的第二个分组跟我们第一次发送的第二个分组相同，产生的密文也就相同，那么就可以推断出爆破成功，之后发送数据就要连带上爆破出来的flag。

这里在举爆破一个分组长度后的例子：

此时我们需要爆破flag的第17字节，我们已知flag的前16字节，我们发送(31-16)=15字节的a，得到：

aaaaaaaaaaaaaaaB∣aseCTF{012345678∣9}aaaaaaaaaaaaaaaB|aseCTF\{012345678|9\}

之后爆破第17位，此时发送数据需要带上flag，这是我们发送的数据aaaaaaaaaaaaaaaB|aseCTF{01234567?，最后得到：

aaaaaaaaaaaaaaaaB∣aseCTF{01234567?∣BaseCTF{0123456789}aaaaaaaaaaaaaaaaB|aseCTF\{01234567?|BaseCTF\{0123456789\}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
from pwn import *
from Crypto.Util.number import *
import base64
p=remote()

print(p.recvline())
print(p.recvline())

c=p.recvline()[:-1]
c=base64.b64decode(c)

length1=0
for i in range(16):
    p.recvline()    # b":\n"
    payload=b'a'*i
    p.sendline(payload)
    d=p.recvline()[:-1]
    d=base64.b64decode(d)
    if len(d)!=len(c):
        length1=i
        break
length_flag=len(c)-length1
print(length_flag)

# 从前往后爆破flag
payload_length=len(c)+16     # 多一个分组保容错
flag=b''
for i in range(payload_length-1,payload_length-1-length_flag,-1):
    p.recvline()    # b":\n"
    payload=b'a'*i
    p.sendline(payload)
    d=p.recvline()[:-1]
    d=base64.b64decode(d)
    for j in range(33,128):
        p.recvline()    # b":\n"
        payload1=b'a'*i+flag+chr(j).encode()
        p.sendline(payload1)
        e=p.recvline()[:-1]
        e=base64.b64decode(e)
        e=e[payload_length-16:payload_length]
        if e in d:
            flag+=chr(j).encode()
            break
    print(flag)

"""# 从后往前爆破flag(此方法需要知道填充模式)
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES

# 在前面填充到满足AES加密的分组长度
dic='{}-BCTF0123456789abcdef'
flag=b''
for i in range(length_flag):
    p.recvline()    # b":\n"
    server_payload=b'a'*(length1+i+1)
    p.sendline(server_payload)
    server_flag=p.recvline()[:-1]
    server_flag=base64.b64decode(server_flag)
    
    for j in dic:
        p.recvline()    # b":\n"
        my_payload=j.encode()+flag
        my_payload=pad(my_payload,AES.block_size)
        my_payload=my_payload+b'a'  # 我也不知道这里为什么要多加一个字节,当i=2时不加这个字节就会出错
        p.sendline(my_payload)
        my_flag=p.recvline()[:-1]
        my_flag=base64.b64decode(my_flag)
        my_flag=my_flag[:16]
        
        if my_flag in server_flag:
            flag=j.encode()+flag
            
            break
    print(flag)"""

p.interactive()

の歪来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
from gmpy2 import *

flag=b''
assert len(flag)==28
m=bytes_to_long(flag)

n=getPrime(2048)
e=32

c=pow(m,e,n)


print("n =",n)
print("e =",e)
print("c =",c)

AMM开根

论文在这里：1111.4877 (arxiv.org)

我还没搞懂，所以直接套用了板子。

我出这题只是想着AMM的常规板子是两个素数求解然后求CRT，我就改成了一个素数，然后小m可以直接得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
from Crypto.Util.number import *
from gmpy2 import *
import random
import math


p = 17363249226879909675667629533972233798566313669420563155296918020175446973456428454735263489044575257132690882883587342817653451483222705760704890265900885255972067349104579938808591608382992680533327518070878297438339884996059309549300942570104747348751766711833983705979880714174709047335147739991850385244159235504375559144283494800573079055547597410783559965162216203307100248001158445665271438067670522510991047688414176659907164436539491205637933681658814267567385232097679554282863595183422504494357205180093828786415060565003183966959273253039416986816444073158723191290806413175478175738266995214965220231649
e = 32
c = 6840453756562205147103219479843999687625029691496635689045074720240615321966887831642035124198445485320265097191334720798522097422084141332044111764558336174743819347952914775206809737198058220362381349481027893609144697054465070779290329222696236671374412706789862193871687821041053566873553189148668599841084370137084893575567622972476409755187388121177923217208552049876944055745912987536390075417261016809335539362984984190264791744790640858201038207982043569204062714722892105134794280417020318408200038144689432974312283915592134911446185412636709207566063730723406969727969141426530341540330398465744403597273
def onemod(e, q):
    p = random.randint(1, q-1)
    while(powmod(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = powmod(p, r**(t-1)*s, q)
    b = powmod(o, r*a-1, q)
    c = powmod(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = powmod(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (powmod(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp


def calc(mp, mq, e, p, q):
    i = 1
    j = 1
    t1 = invert(q, p)
    t2 = invert(p, q)
    for mp1 in mp:
        for mq1 in mq:
            j += 1
            if j % 100000 == 0:
                print(j)
            ans = (mp1*t1*q+mq1*t2*p) % (p*q)
            if check(ans):
                return
    return


def check(m):
    try:
        a = long_to_bytes(m)
        if b'NSSCTF' in a:
            print(a)
            return True
        else:
            return False
    except:
        return False


def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = powmod(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

cp = c % p

mp = AMM_rth(cp, e, p)

rt1 = ALL_ROOT2(e, p) 
amp = ALL_Solution(mp, p, rt1, cp, e)

for i in amp:
    m=long_to_bytes(i)
    if b'BaseCTF' in m:
        print(m)
        break

老涩批了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
from Crypto.Util.number import *
import socketserver
import os
import uuid 
flag = os.getenv('GZCTF_FLAG').encode()

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):
        return self._recvall()

    def handle(self):
        
        p=getPrime(256)
        q=getPrime(256)
        n=p*q
        e=65537
        d=inverse(e,(p-1)*(q-1))

        text=b'BaseCTF{'+str(uuid.uuid4()).encode()+b'}'

        m1=bytes_to_long(text[:len(text)//2])
        c1=pow(m1,e,n)

        m2=bytes_to_long(text[len(text)//2:])
        c2=pow(m2,e,n)

        self.send(b'n = '+str(n).encode())
        self.send(b'e = '+str(e).encode())
        self.send(b'c1 = '+str(c1).encode())
        self.send(b'c2 = '+str(c2).encode())

        while True:
            select=self.recv().strip()
            if select==b'1':
                c=int(self.recv().decode().strip())
                m=pow(c,d,n)
                res=m&1
            elif select==b'2':
                c=int(self.recv().decode().strip())
                m=pow(c,d,n)
                res=long_to_bytes(m,64)[0]
            elif select==b'3':
                user_text=self.recv().strip()
                if user_text==text:
                    self.send(flag)
                    break
                else:
                    self.send(b'try again')
                    break
            else :
                self.send(b'wrong')
                break
            self.send(str(res).encode())
        self.send(b"\nConnection has been closed  =.=  ")
        self.request.close()


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


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


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

参考了La佬的博客：RSA | Lazzaro (lazzzaro.github.io)

说明一下出题：没点子了，就逛ctfwiki上看到了这个，然后搜了一圈只找到了LSB的代码，MSB没有，我就顺便结合起来了，然后由于GZ这里每个队伍开不同容器flag还是一样的，为了防止多次加密不安全，所以套了一下，先道个歉。

原理我就不献丑了，可以去看看佬们的博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from Crypto.Util.number import *
import decimal
from pwn import *
from time import *
rem=remote()
rem.recvuntil(b'n = ')
n=int(rem.recvline().decode().strip())

rem.recvuntil(b'e = ')
e=int(rem.recvline().decode().strip())

rem.recvuntil(b'c1 = ')
c1=int(rem.recvline().decode().strip())

rem.recvuntil(b'c2 = ')
c2=int(rem.recvline().decode().strip())
def server_decode1(c):
    rem.sendline(b'1')
    sleep(0.01)
    rem.sendline(str(c).encode())
    rec=rem.recvline().strip()
    return rec
kbits = n.bit_length()
decimal.getcontext().prec = kbits
L = decimal.Decimal(0)
R = decimal.Decimal(int(n))
for i in range(kbits):
    c1 = (c1 * pow(2, e, n)) % n
    recv = server_decode1(c1)
    if recv == b'1':
        L = (L + R) // 2
    else:
        R = (L + R) // 2
flag1=long_to_bytes(int((R)))
print(flag1)
sleep(0.01)
def server_decode2(c):
    rem.sendline(b'2')
    sleep(0.01)
    rem.sendline(str(c).encode())
    rec=rem.recvline().strip()
    return rec
k=1
while True:
    c22 = (c2 * pow(2, e*k, n)) % n
    res=server_decode2(c22)
    res=int(res)
    if res&1:
        break
    k=k+1
L=2**(k-1)
R=2**k

while True:
    if R-L==1:
        break
    x=(L+R)//2
    c22 = (c2 * pow(x, e, n)) % n
    res=server_decode2(c22)
    res=int(res)
    if res:
        R=x
    else :
        L=x
flag2=(2**(kbits-8)//L)
print(long_to_bytes(flag2))
user_text=flag1[:-1]+b'-'+long_to_bytes(flag2)
print(user_text)
rem.sendline(b'3')
sleep(0.01)
rem.sendline(user_text)


rem.interactive()

PDP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
from Crypto.Util.number import *
from gmpy2 import *
import hashlib
import hmac
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import *

def KeyGen():
    while True:
        pp=getPrime(512)
        p=2*pp+1
        while not isPrime(p):
            pp=getPrime(512)
            p=2*pp+1

        qq=getPrime(512)
        q=2*qq+1
        while not isPrime(q):
            qq=getPrime(512)
            q=2*qq+1
        
        if pp!=qq:
            break
    n=p*q
    phi=(p-1)*(q-1)

    e=getPrime(1024)
    d=invert(e,phi)

    v=getRandomNBitInteger(128)

    g=e**2%n

    return (n,g,e,d,v)

def TagBlock(n,g,d,v):
    f=open("ABigFile",'rb')
    F=f.read()
    f.close()
    b_size=64   # 64B

    block_count=len(F)//b_size + (0 if len(F)%b_size==0 else 1)

    W=[]
    tags=[]
    for i in range(block_count):
        Wi=str(v)+str(i)
        W.append(Wi)

        block=bytes_to_long(F[i*b_size:(i+1)*b_size])

        my_md5=hashlib.md5()
        my_md5.update(Wi.encode())
        tags.append(pow((int(my_md5.hexdigest(),16)*pow(g,block,n))%n,d,n))
    return (W,tags)

def GenProof(n,g):
    c=randint(400,500)
    k1=getRandomNBitInteger(256)
    k2=getRandomNBitInteger(160)
    s=getRandomNBitInteger(16)
    return (c,k1,k2,s,pow(g,s,n))

def gen_proof(n,tags,c,k1,k2,gs,judge=0):
    f=open("ABigFile",'rb')
    F=f.read()
    f.close()
    b_size=64   # 64B

    if judge:
        listF=list(F)
        X=[]
        for i in range(len(F)//100):
            x=randint(0,len(F)-1)
            while listF[x]==0:
                x=randint(0,len(F)-1)
            X.append(x)
            listF[x]=0
        F=b''
        for i in listF:
            F+=long_to_bytes(i)

    block_count=len(F)//b_size + (0 if len(F)%b_size==0 else 1)
    T=1
    temp=0
    for j in range(c):
        my_aes=AES.new(long_to_bytes(k1),mode=AES.MODE_ECB)
        i=my_aes.encrypt(pad(long_to_bytes(j),AES.block_size))
        i=bytes_to_long(i)%block_count

        my_sha256=hashlib.sha256
        my_hmac=hmac.new(long_to_bytes(k2),digestmod=my_sha256)
        my_hmac.update(long_to_bytes(j))
        a=int(my_hmac.hexdigest(),16)%n

        T=(T*(pow(tags[i],a,n)))%n

        block=bytes_to_long(F[i*b_size:(i+1)*b_size])%n

        temp=temp+block*a
    temp=pow(gs,temp,n)
    my_sha1=hashlib.sha1()
    my_sha1.update(str(temp).encode())
    rho=int(my_sha1.hexdigest(),16)
    return (T,rho)

n,g,e,d,v=KeyGen()
with open("./output/key.txt",'w') as file:
    file.write(str(n)+'\n')
    file.write(str(e)+'\n')

W,tags=TagBlock(n,g,d,v)
with open("./output/W.txt","w") as file:
    for i in W:
        file.write(str(i))
        file.write('\n')

c,k1,k2,s,gs=GenProof(n,g)
with open("./output/chal.txt",'w') as file:
    file.write(str(c)+'\n')
    file.write(str(k1)+'\n')
    file.write(str(k2)+'\n')
    file.write(str(s)+'\n')

T,rho=gen_proof(n,tags,c,k1,k2,gs)
with open("./output/result.txt",'w') as file:
        file.write(str(T)+'\n')

flag_md5=hashlib.md5()
flag_md5.update(str(rho).encode())
print(b'BaseCTF{'+flag_md5.hexdigest().encode()+b'}')

我的毕设课题，正好感觉能出成一题就出了，具体不多说，详了解的可以看：naby1/S-PDP (github.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from Crypto.Util.number import *
from gmpy2 import *
import hashlib
import hmac
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import *

def CheckProff(n,e,W,c,k1,k2,s,T):
    tau=pow(T,e,n)
    block_count=len(W)
    for j in range(c):
        my_aes=AES.new(long_to_bytes(k1),mode=AES.MODE_ECB)
        i=my_aes.encrypt(pad(long_to_bytes(j),AES.block_size))
        i=bytes_to_long(i)%block_count

        my_sha256=hashlib.sha256
        my_hmac=hmac.new(long_to_bytes(k2),digestmod=my_sha256)
        my_hmac.update(long_to_bytes(j))
        a=int(my_hmac.hexdigest(),16)%n

        Wi=str(W[i])
        my_md5=hashlib.md5()
        my_md5.update(Wi.encode())
        hw=pow(int(my_md5.hexdigest(),16),a,n)
        tau=(tau*invert(hw,n))%n
    tau=pow(tau,s,n)
    my_sha1=hashlib.sha1()
    my_sha1.update(str(tau).encode())
    tau=int(my_sha1.hexdigest(),16)
    flag_md5=hashlib.md5()
    flag_md5.update(str(tau).encode())
    print(b'BaseCTF{'+flag_md5.hexdigest().encode()+b'}')

with open("./output/key.txt",'r') as file:
    n=int(file.readline())
    e=int(file.readline())

W=[]
with open("./output/W.txt","r") as file:
    fl=file.readline()
    while fl:
        W.append(int(fl))
        fl=file.readline()

with open("./output/chal.txt",'r') as file:
    c=int(file.readline())
    k1=int(file.readline())
    k2=int(file.readline())
    s=int(file.readline())
T=234286400251524464112670458144913694525518333434039777508421611102466502545441606446799021254782625175811569624228349681696143431027926557585053651139957429856785510525021542033961575674601192776283321921860155347475439442726331189839563865687519551977156169783131926796425661730777079164446161030078497564104
CheckProff(n,e,W,c,k1,k2,s,T)

#BaseCTF{d198bce7a2f06ed24d3b043bddbd7512}
ctf > wp
#Crypto #BaseCTF2024
BaseCTF2024-Crypto-naby
http://example.com/2024/12/05/basectf2024/
作者
Naby
发布于
2024年12月5日
许可协议