This game is very unsatisfactory, and I will not do anything.
I took WP and read a few questions, record it
random_RSA
This question will not be a normal situation, I think. For the thesis topic, if you don’t know it, you don’t know it. It is basically impossible to complete the thesis by yourself.
The topic is not long, there are only two menus, and you can interact 8 times in total. When you input 1, random numbers will be generated p, q, d (the generated random number will be shifted to the left by 32 bits and then take next_prime) and then e will be given (the phi corresponding to e is ( p^2-1)*(q^2-1)), when 2 is input, p will be generated again, and q will generate c with e=0x10001
from gmpy2 import next_prime, invert as inverse_mod
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from random import getrandbits
from math import lcm
from sys import exit
global_bits = 1024
BANNER = rb"""
.--------.--------.--------.--------.--------.---- ----.--------.--------.--------.--------.--------.
| N.--. | E.--. | P.--. | C.--. .--. | P.--. | Y.--. |
| :/\: | (\/) | :(): | :/\: | :/\: | :/\: | (\/) | :(): | :/\: | :/\: | (\/) |
| :\/: | :\/: | ()() | (__) | :\/: | (__) | :\/: | ()() | :\/: | :\/: | : \/: |
| '--'n | '--'e | '--'p | '--'c | '--'t | '--'f | '--'h | --'p | '--'p | '--'y|
`--------`--------`--------`--------'-------`---- ----`--------`--------`-------`-------`-------`
"""
def generate_prime(bits: int):
p = (getrandbits(bits - 32) << 32)
return next_prime(p)
def generate_private_key(bits: int):
p, q = generate_prime(bits), generate_prime(bits)
n, phi = p * q, lcm(p-1, q - 1)
d = inverse_mod(0x10001, phi)
privateKey = RSA. construct((int(n), int(0x10001), int(d), int(p), int(q)))
return privateKey, p > q
if __name__ == "__main__":
print(BANNER. decode())
print("Welcome to the world of random RSA.")
print("Please make your choice.")
for _ in range(8):
choice = input()
if choice == '1':
p, q = generate_prime(global_bits), generate_prime(global_bits)
N = p*q
d = generate_prime(global_bits-32)
e = inverse_mod(d, (p * p - 1) * (q * q - 1))
print(f"{int(N)}")
print(f"{int(e)}")
elif choice == '2':
privateKey, signal = generate_private_key(global_bits)
Cipher = PKCS1_v1_5.new(privateKey)
c = (Cipher.encrypt(flag.encode()))
print(c)
exit()
else:
exit()
Here menu 2 does not give p, and q is obviously predicted by the previous random number.
1, ed = 1 + k(p^2-1)(q^2-1) If the problem of decomposition, this paper will not be explained, the explanation is not clear, the solution is to decompose through continued fractions
The result is k, d, so first exchange 7 1s and 1 2 and then come back and process slowly to get the array of p, q, d.
from gmpy2 import iroot
def contfrac_attack(e,n):
convergents = continued_fraction(ZZ(e) / ZZ(int(n^2 -9/4*n + 1))).convergents()
for c in convergents:
k = c. numerator()
d = c.denominator()
if pow(pow(2,int(e),int(n)),int(d),n) == 2:
phi = (e*d - 1)//k
p_add_q = iroot(n^2 + 1 -phi + 2*n,2)[0]
p_sub_q = iroot(n^2 + 1 -phi -2*n,2)[0]
p = (p_add_q + p_sub_q)//2
q = n//p
#if p<q:
# p,q = q,p
#print('[',p,',',q,',',d,'],')
return p,q,d
N = [data[i] for i in range(0,len(data),2)]
E = [data[i + 1] for i in range(0,len(data),2)]
pqd = []
for e,n in zip(E,N):
p,q,d = contfrac_attack(e,n)
pqd.append([p,q,d])
2. Use MT19937 to restore random to find p, q
Since the order of p and q given is unknown, a blast is required here 2^7 is very small
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from extend_mt19937_predictor import ExtendMT19937Predictor
from gmpy2 import invert,next_prime
from math import lcm
import itertools
bits = 1024
e = 0x10001
def gen1(bits: int):
p = (getrandbits(bits - 32) << 32)
return next_prime(p)
def gen2(bits: int):
p = (predictor. predict_getrandbits(bits - 32) << 32)
return next_prime(p)
for o in itertools. product([0,1], repeat=7):
try:
predictor = ExtendMT19937Predictor()
for i,v in enumerate(pqd):
#print(v)
predictor.setrandbits(v[o[i]]>>32, 992) #31 + 31 + 30
predictor.setrandbits(v[1-o[i]]>>32, 992)
predictor.setrandbits(v[2]>>32, 960)
except:
continue
p,q = gen2(bits), gen2(bits)
n = p*q
phi = lcm(p-1,q-1)
d = invert(e, phi)
privateKey = RSA. construct((int(n), int(e), int(d), int(p), int(q)))
Cipher = PKCS1_v1_5.new(privateKey)
try:
flag = (Cipher.decrypt(c,'\x00'))
print(flag)
except:
continue
#b'NepCTF{c4e4356067fb3bedc53dde7af59beb1c}'
For the RSA packaged with PKCS1, it is also used to solve it, and we use our lcm(p-1,q-1) and (p-1)*(q-1) to solve the problem.
When MT19937 fills in the data, if there is a mistake in the repeated part, an error will be reported. At this time, the order of p and q should be incorrect. A total of 644 sets of 32-bit random numbers have been obtained for this question, and there are 20 sets, which are 20 sets more than 624. All the ones passed here are correct, but some sets are not used in the subsequent generation, so there are multiple sets of the same solution.
recover
This question is half stuck, and my mind is a little dizzy, and I didn’t see the format of the prompt flag.
from math import ceil
from hashlib import md5
from Crypto.Util.number import *
#from secret import key, flag
key = b'bfaxctvpacpfxsrljavvvmsi'
flag = b'flag{flag_is_the_readable_key_whose_md5_starts_with_3fe04}'
def MD5(x): return md5(x).hexdigest()
assert(len(flag) == 58)
assert(len(key) == 24)
P = [[0, 2, 3, 4, 5, 6],
[1, 4],
[0, 3],
[0, 3, 4, 5],
[0, 1, 2, 3, 4, 7],
[2, 3, 4, 5, 6],
[0, 1, 2, 3],
[1, 2, 3, 4, 5, 7],
[8, 12, 13, 14],
[8, 11, 12, 13, 15],
[9, 12, 15],
[11, 13, 15],
[8, 9, 10, 12, 13, 15],
[8, 9],
[11, 13, 14],
[10],
[16, 19, 20],
[16, 18, 19, 20, 21],
[16, 17, 18, 19],
[17, 18, 20, 22, 23],
[17, 19, 23],
[17, 18, 20, 21, 23],
[16, 18, 20, 21, 22, 23],
[16, 17, 18, 20, 21, 22, 23],
[25, 26, 29, 31],
[25, 26],
[26, 28, 30],
[27, 28, 29, 30, 31],
[25, 29],
[25, 26, 30, 31],
[28, 29, 30, 31],
[24, 26, 29, 31],
[35, 36, 39],
[33, 35, 38],
[33, 35, 37, 39],
[32, 33, 34, 35, 37, 38],
[32, 33, 34, 35, 37, 39],
[35, 38],
[33, 34, 38, 39],
[33, 34, 39],
[41, 42, 43, 44, 47],
[40, 41, 42, 45, 47],
[41, 42, 45, 47],
[40, 43, 44, 46],
[41, 46, 47],
[41, 42, 43, 44, 46, 47],
[41, 42, 44, 45],
[40, 41, 42, 45, 46],
[48, 50, 51, 52, 53, 54, 55],
[48, 49, 50, 52, 53, 54, 55],
[49, 55],
[48, 49, 50, 51, 52, 54],
[52, 53],
[48, 49, 53, 54, 55],
[48, 49, 52, 55],
[48, 49, 51, 52, 55],
[58, 59],
[56, 61, 63],
[57, 63],
[56, 59, 60],
[61, 63],
[57, 58, 61, 62, 63],
[57, 58],
[60, 62]]
def enc(v, keys, le):
t = v
for i in keys:
q = []
for j in P:
tmp = 0
for k in j:
tmp ^= t[k]
q.append(tmp)
t = [int(q[j]) ^ int(i[j]) for j in range(le)]
return t
keys = []
for i in range(len(key)//8):
l = bytes_to_long(key[i*8:i*8 + 8])
m = bin(l)[2:].zfill(8*8)
keys.append([int(i) for i in m])
fb = bin(bytes_to_long(flag))[2:].zfill(ceil(len(flag)/8)*8*8)
ciphertext = ""
for i in range(0, len(fb), 64):
t = enc([int(j) for j in fb[i:i + 64]], keys, 64)
ciphertext + = "".join([str(j) for j in t])
print(ciphertext)
cipher = '1110110010000011010110010110000110011011100100111000000010110000110011011000100110101110111010000100100001100010011 001100010100101000110001011101000000100010101000000110000110011110001101110110110111000000100010011011011011101011101000000 000100010000101001110100101011000001110010000000000100110001101110011111010001100101101111010101111101110100110101010011010 011010101110100001001101100110010000010000011100100101111010010000011001000110000100110111100010101011000100100111010000101 010110110001010110101111111'
print(cipher)
Here P has 64 sets of data. Obviously, every set of 8 can be regarded as the operation of m*A=c. Since the key has 24 bytes, this operation is performed 3 times, that is, for a character ((m* A + key1)*A + key2)*A + key3 After encrypting a byte in this way, the key may be in multiple groups.
Since the flag format flag{…} is given before 58 characters, 0 becomes 64 points and 8*8, so one or two plaintexts are given for each group according to the column, and the other plaintext prompts are small letters (wrong idea ), so it is easy to blast out a set of keys. Use this key to find other characters. Every time I change the idx, I can get a column of data, but later I couldn’t get a few groups, and found that it’s not just lowercase letters. It is said that the amount of blasting is actually extremely small, the kind that comes out in seconds.
idx = 4
v0 = [0,0,0,0,0,0,ord('f'),ord('l')]
tp = P[idx*8: idx*8 + 8]
tP = [[i-idx*8 for i in t] for t in tp]
print(tP)
for v1 in 'l':
for v in 'h':
vs = get_v(v0[idx],ord(v1),ord(v))
cs = [ciphers[idx], ciphers[idx + 8], ciphers[idx + 16]]
key0 = get_key(vs,cs,tP)
if key0 == False:
continue
print('Try:', idx, v1, v)
for i in range(8):
ok = False
for v2 in tab:
t = enc([int(i) for i in bin(ord(v2))[2:].zfill(8)], key0, 8, tP)
if all(int(ciphers[idx + i*8][j])==t[j] for j in range(8)):
ok = True
print(i,v2)
if not ok:
break
else:
print(f'key {idx}', key0)
'''
000000fl
ag{flag_
is_the_r
eadable_
key_whos
e_md5_st
arts_wit
h_3fe04}
'''
#flag{flag_is_the_readable_key_whose_md5_starts_with_3fe04}
Then the second step is stuck, here it is said that the flag is readable and the md5 header is this. I didn’t think of the format of the flag for a while, so there are more than 100 groups of possible keys for each group, and there are too many groups of 8 groups, so there is no way to get it. After looking at WP, the original prompt is used here. If the real key also has the flag{…} format, then there are 6 groups of prompts, and there are not many blasting.
Find the combination of each set of keys
def get_int(aa):
return [int(''.join(map(str, a)),2)for a in aa]
def get_list(k1,k2,k3):
return [[int(i) for i in bin(ord(a))[2:].zfill(8)] for a in [k1,k2,k3]]
def get_key2(vs,cs,tP):
keys = [BitVec(f'key_{i}',1) for i in range(24)]
key_arr = [keys[i:i + 8] for i in range(0,24,8)]
print(vs)
print(cs)
print(tP)
s = Solver()
s.add(keys[0] == 0)
s.add(keys[8] == 0)
s.add(keys[16] == 0)
for v,c in zip(vs,cs):
t = enc(v, key_arr,8, tP)
for i,tk in enumerate(t):
s.add(tk == int(c[i]))
allkey = []
while s.check() == sat:
d = s.model()
rkey = [d[keys[i]].as_long() for i in range(24)]
rkey_arr = [rkey[i:i + 8] for i in range(0,24,8)]
#print(rkey_arr)
tmp = get_int(rkey_arr)
if all(0x20<=v<0x7f for v in tmp):
allkey.append(tmp)
condition = []
for i in range(24):
condition.append(keys[i] != rkey[i])
s.add(Or(condition))
return all key
flag = b'flag{flag_is_the_readable_key_whose_md5_starts_with_3fe04}'
vs = [0]*6 + [v for v in flag]
#print(vs)
tab = string.ascii_lowercase
tabs = list('flag{') + [tab]*18 + ['}']
print(tabs)
for idx in range(8):
tp = P[idx*8: idx*8 + 8]
tP = [[i-idx*8 for i in t] for t in tp]
tv = [[int(i) for i in bin(vs[j*8 + idx])[2:].zfill(8)] for j in range(8)]
tc = [ciphers[idx + j*8] for j in range(8)]
allkey = []
for k1 in tabs[idx]:
for k2 in tabs[idx + 8]:
for k3 in tabs[idx + 16]:
key0 = get_list(k1,k2,k3)
for i,v2 in enumerate([vs[i*8 + idx] for i in range(8)]):
t = enc([int(i) for i in bin(v2)[2:].zfill(8)],key0, 8, tP)
if int(ciphers[idx + i*8],2) == int(''.join(map(str,t)),2):
allkey. append(k1 + k2 + k3)
print(list(set(allkey)))
Then blast these, and eyeball to find a set that can be read.
k = [
['fcw', 'fdo', 'fef'],
['lnd', 'lxn', 'lev'],
['asz', 'are', 'aqi', 'apv'],
['gan', 'gkj', 'gnf', 'gtr', 'gdb'],
['{ok', '{qy', '{bx'],
['cbk', 'ahm', 'ygt', 'joe', 'lio', 'tir', 'arr', 'jxc', 'ypr', 'vnm', 'yjm', 'ldv', ' agi', 'cor', 'nat', 'hre', 'gng', 'ppe', 'vct', 'esg', 'nvr', 'rba', 'lsp', 'pgc', 'tsm' , 'tfv', 'vyk', 'tqp', 'vvo', 'pjz', 'vai', 'ajp', 'cum', 'rug', 'lqm', 'nci', 'nyv', ' jmx', 'apo', 'yhp', 'vlp', 'juz', 'aet', 'rwz', 'eix', 'hpx', 'hec', 'tko', 'nlm', 'jwg' , 'hjg', 'rzc', 'cxt', 'cwp', 'tdk', 'gve', 'rox', 'eke', 'gya', 'eqz', 'cmo', 'yei', ' phg', 'vtr', 'yro', 'czi', 'nnp', 'hhz', 'rme', 'gac', 'eda', 'lkr', 'glz', 'lfk', 'gtx' , 'nto', 'prx'],
['kjy', 'hqr', 'qpb', 'tyf', 'vrs', 'tsi', 'cht', 'mxv', 'wbm', 'pfd', 'lhh', 'qzm', ' gqn', 'wdu', 'osc', 'xbq', 'aov', 'ept', 'fap', 'mry', 'yro', 'oyl', 'pjs', 'bre', 'cnl' , 'dfr', 'raf', 'tuq', 'cdc', 'nir', 'qvz', 'ytw', 'whb', 'rmq', 'evl', 'sqx', 'uix', ' ikc', 'wnz', 'fmg', 'ueo', 'dje', 'aey', 'lnp', 'xnf', 'zes', 'fgh', 'ain', 'igt', 'ucw' , 'bxj', 'nee', 'hwj', 'lbg', 'mta', 'zid', 'jph', 'aca', 'noj', 'ial', 'vtk', 'rki', ' kfn', 'zck', 'plk', 'jzg', 'xdi', 'kla', 'jvp', 'gwv'],
['zr}', 'pf}', 'xw}', 'rc}']]
from hashlib import md5
v=[0]*8
for v[0] in k[0]:
for v[1] in k[1]:
for v[2] in k[2]:
for v[3] in k[3]:
for v[4] in k[4]:
for v[5] in k[5]:
for v[6] in k[6]:
for v[7] in k[7]:
key = ''.join(''.join(r[i] for r in v) for i in range(3))
m = md5(key.encode()).hexdigest()
if m.startswith('3fe04'):
print(key, m)
#flag{hardertorecoverkey}
'''
flag{aapcnsabjcfwdznxpa} 3fe042d564d4e19a99c18038e95a4923
flag{npxcxsnovlwwnzfkrk} 3fe044e1e71f56918db24bc143cbdd02
flag{chrcxsnqmwcwnzfyoj} 3fe045110e1506d003ae582f22ce3d6c
flag{gsrcxpnbtqcwnvfxxx} 3fe044fcc37311bc71e76987e341ee16
flag{ycrcxptopncwnvrkrl} 3fe049dcd66d48a19f824ed9dfd51ae2
flag{vxrceraocncwvenktf} 3fe0477ae63f44db4e5657ae34b71f8e
flag{yrpcepkbrkfwvvjxoi} 3fe040c7d8ff041d0784e93b952f206a
flag{gvxdxsdqytwonzbyak} 3fe043b101bbbec84b04027f4872e6a5
flag{rwzdxpnobbronvfkam} 3fe04ea7bc9169f9565730a5786a767b
flag{hardertorecoverkey} 3fe0442d2939da2767c07fe4b735a917
flag{gczenstoldrfdzrkzc} 3fe04b78470cb999ecce16590b5a2a04
flag{nfpexsnqnmffnzfypg} 3fe04a6cce75c141462498c92e7517bf
flag{afpeesdbjgffvzbxph} 3fe04500376029ba4432e8af5d79b00b
'''
For the following two Enge code machine questions, the first one is based on the fact that the plaintext does not appear in the ciphertext. For example, the fifth digit of the plaintext is A, and the fifth digit in the ciphertext must not be A.
The second is based on a certain paper. jump over.
secureAgg
This question is very long, if you have time to understand and read the question, you can answer it.
AggServer.py
from Crypto.Util.number import *
from User import User
class AggServer:
def __init__(self, mbits):
self.N=8
self.g=2
self.p=0x9f785dd75d97d7dea66a89a038e7c880b962e526fa9d0f14639de8d82b953fbf0e01739495df3d5fdb189aa079c70e9cc49c7390c2fd3166d91fe8b51 1f918a7
self.mbits=mbits
self.users=[User(mbits,i) for i in range(self.N)]
self.M=getPrime(mbits + self.N.bit_length() + 1)
self.params=(self.g,self.p)
def genKeys(self):
for u in self. users:
u.genKey(self.params)
for u in self. users:
u. agree(self. users, self. params[1])
def get_enc_list(self): #disclosure
enc_list=[]
for u in self. users:
enc_data = u.get_enc_data(self.M)
enc_list.append(enc_data)
return enc_list
def aggregate(self): #generate key
self.key=sum([u.data for u in self.users])%self.M
return self.key
def update(self):
for u in self. users:
u.update_data(self.key)
def system_info(self):
info = ""
info + = "System params: \
"
info + = f"g={self.params[0]}\
p={self.params[1]}\
M={self.M}\
"
info + = "User pubkeys:\
"
info + = f"pubkeys={str([ u.pub for u in self.users])}\
"
return info
chall.py
# !/usr/bin/env python
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from base64 import b64encode
from FLAG import flag
from AggServer import AggServer
import socketserver
import os, sys, random
import signal, string
ROUNDS=20
BANNER=br'''
Welcome to my Secure Aggregation System.
If you can pass my 20 rounds of agg testing, I'll give you flag~
Have fun!
'''
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'\
'
self.request.sendall(msg)
except:
pass
def recv(self, prompt=b'>'):
self. send(prompt, newline=False)
return self._recvall()
def close(self):
self. request. close()
def handle(self):
signal.alarm(180)
self. send(BANNER)
self. send(b"Generating parameters...")
agg=AggServer(114)
agg. genKeys()
self. send(agg. system_info(). encode())
try:
for i in range(ROUNDS):
self. send(f'#Round {i + 1}'. encode())
enc_list = agg.get_enc_list()
self.send(f"enc_list={enc_list}".encode())
key=agg.aggregate()
message=''.join(random.sample(string.ascii_letters,16))
aes_key=sha256(str(key).encode()).digest()[:16]
aes=AES.new(aes_key,AES.MODE_CBC,iv=bytes(range(16)))
enc=aes.encrypt(pad(message.encode(),16))
self.send(f"enc={b64encode(enc)}".encode())
inp=self.recv(b"input your message: ").decode()
if inp==message:
self. send(b'Correct!')
else:
self. send(b'Error!')
exit(0)
agg. update()
self. send(flag)
except:
self. send(b'wtf?')
self. close()
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
class ForkedServer(socketserver. ForkingMixIn, socketserver. TCPServer):
pass
if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 12345
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()
usr.py
from Crypto.Util.number import *
class PRG:
def __init__(self, seed):
self.state=seed
self.a=114514
self.b=1919810
self.kbits = seed.bit_length()
self. bits = []
def gen(self):
self.state=(self.a*self.state + self.b) &((1<<self.kbits)-1)
bin_arr=list(map(int,bin(self.state)[2:].zfill(self.kbits)[::-1]))
self. bits. extend(bin_arr)
def randbits(self,n):
while len(self.bits)<n:
self. gen()
output=self.bits[:n]
self.bits = self.bits[n:]
return int(''. join(map(str, output)), 2)
class User:
def __init__(self, mbits, id):
self.mbits=mbits
self.id=id
self.data = getRandomNBitInteger(mbits)
def genKey(self, params):
g,p=params
self.priv=getRandomRange(1,p)
self.pub=pow(g,self.priv,p)
def agree(self, users, p):
self.agreement_keys={}
for u in users:
if u.id!=self.id:
u_pub=u.pub
k=pow(u_pub,self.priv,p)
self.agreement_keys.update({u.id:k})
def get_enc_data(self, M):
enc=(114*self.data + 514)%M
for id, k in self.agreement_keys.items():
if id>self.id:
enc + =PRG(k).randbits(self.mbits)%M
elif id<self.id:
enc-=PRG(k).randbits(self.mbits)%M
return enc
def update_data(self, key):
mask=(1<<self.mbits)-1
noise=getRandomNBitInteger(16)
self.data=(self.data ^ key ^ noise) & amp; mask
chall.py gives an interactive service, if it is correct 20 times, it will give the flag
First become Agg, and then give enc_list=agg.get_enc_list() in each round, this function calls users
def get_enc_list(self): #disclosure
enc_list=[]
for u in self. users:
enc_data = u.get_enc_data(self.M)
enc_list.append(enc_data)
return enc_list
Encryption in users is a very small LCG
def get_enc_data(self,M):
enc=(114*self.data + 514)%M
for id, k in self.agreement_keys.items():
if id>self.id:
enc + =PRG(k).randbits(self.mbits)%M
elif id<self.id:
enc-=PRG(k).randbits(self.mbits)%M
return enc
Obviously, the enc_data group here to find data only needs (sum(enc_data)-514*8)*114^-1 % M, and finally AES is enough if there is a key.
The last one about DES is too long, I didn’t read it, it is very simple.