祥云杯wp

Guess

key和xnuca2020 diamond中的一步类似，拿网上脚本改了改参数，用LLL规约，有时候会报错，报错就重新跑，最后拿到四组

f=open('hint','r')
B=[]
for line in f:
    l=line[1:-2].split(' ')
    for i in l:
        B.append(int(i))
BB=[]
for i in range(0, len(B), 20):
    BB.append(B[i:i+20])

As = []
for i in range(1000):
    shuffle(BB)
    for line in matrix(len(BB), 20, BB).LLL(delta=float(randint(25000, 99999)/100000)):
        if line[0] < 0:
            line = -line
        if line not in As and all(map(lambda x: 100 <= x <= 1000, line)):
            print(line)
            As.append(line)

a=[119, 521, 142, 637, 614, 746, 299, 416, 638, 288, 995, 498, 639, 585, 114, 885, 558, 783, 899, 751]
b=[241, 232, 548, 400, 186, 333, 646, 727, 286, 877, 810, 121, 237, 745, 201, 542, 244, 396, 158, 641]
c=[718, 550, 349, 939, 148, 355, 942, 685, 313, 577, 184, 130, 307, 983, 611, 903, 271, 530, 566, 427]
d=[647, 918, 613, 936, 461, 281, 977, 888, 128, 653, 309, 780, 526, 216, 944, 123, 430, 860, 113, 129]
m=matrix([a,b,c,d])
m=m.transpose()
l=[]
for i in m:
    for j in i:
        l.append(j)
print(l)

然后是https://en.wikipedia.org/wiki/Paillier_cryptosystem，这个加密系统，利用它乘法同态性，只需要把发来的平方，发回来的除二就可以了，然后需要找key。由于R是偶数，所以可以判断了

from pwn import *
from hashlib import sha256
key=[119, 241, 718, 647, 521, 232, 550, 918, 142, 548, 349, 613, 637, 400, 939, 936, 614, 186, 148, 461, 746, 333, 355, 281, 299, 646, 942, 977, 416, 727, 685, 888, 638, 286, 313, 128, 288, 877, 577, 653, 995, 810, 184, 309, 498, 121, 130, 780, 639, 237, 307, 526, 585, 745, 983, 216, 114, 201, 611, 944, 885, 542, 903, 123, 558, 244, 271, 430, 783, 396, 530, 860, 899, 158, 566, 113, 751, 641, 427, 129]


def pppow(end, sha):
    table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"
    for a in table:
        for b in table:
            for c in table:
                for d in table:
                    if sha256((a + b + c + d).encode() + end.encode()).hexdigest() == sha:
                        return a + b + c + d
host,post='47.104.85.225', 57811
r = remote(host, post)
r.recvuntil(b'SHA-256(?+')
end=r.recv(12).decode()
r.recvuntil(b' == ')
sha=r.recvuntil(b'\n')[:-1].decode()
r.sendline(pppow(end,sha).encode())
for _ in range(32):
    r.recvuntil(b"n = ")
    n=int(r.recvuntil(b'\n').decode()[:-1])
    print(n)
    r.recvuntil(b"g = ")
    g=int(r.recvuntil(b'\n').decode()[:-1])
    r.recvuntil(b"Please give me one decimal ciphertext.\n")
    r.sendline(str(n).encode())
    r.recvuntil(b"Give me m0.\n")
    r.sendline('5'.encode())
    r.recvuntil(b"Give me m1.\n")
    r.sendline('5'.encode())
    r.recvuntil(b"This is a ciphertext.\n")
    cipher=int(r.recvuntil(b'\n')[:-1])
    r.recvuntil(b"Please give me one decimal ciphertext \n")
    r.sendline(str(pow(cipher,2,n**2)).encode())
    r.recvuntil(b"This is the corresponding plaintext.\n")
    plain=int(r.recvuntil(b'\n').decode()[:-1])
    i=key.index(plain//(5*5*2))
    i=i%2
    r.recvuntil(b"(m0 -> c0 , m1 -> c1)?\n")
    r.sendline(str(i).encode())
    print('ok')
flag=r.recv().decode()
print(flag)

 

myRSA

化简式子得到

对比

后面的东西相差不大，所以我们需要让c尽可能大，这样z/c的bit数就很小，如果对其开三次方，就不会有很大影响。可以近似认为$[\sqrt[3]{(x+y)}]=p+q-1$。然后对flag除x+y，z同样可以近似忽略。

from pwn import *
from random import *
from Crypto.Util.number import *
from hashlib import sha256
def Root(n,e):
	L,R=0,n
	while L<=R:
		M=(L+R)//2
		if(M**e<n):
			L=M+1
		if(M**e>n):
			R=M-1
		if(M**e<=n and (M+1)**e>n):
			return M

def Pow(end, sha):
    table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"
    for a in table:
        for b in table:
            for c in table:
                for d in table:
                    s = (a + b + c + d).encode() + end.encode()
                    if sha256(s).hexdigest() == sha:
                        return a + b + c + d


p = remote("47.104.85.225", 49823)
p.recvuntil(b'SHA-256(?+')
end = p.recv(12).decode()
p.recvuntil(b' == ')
sha = p.recvuntil(b'\n')[:-1].decode()
p.sendline(Pow(end, sha).encode())
p.recvuntil(b'n = ')
n = int(p.recvuntil(b'\n')[:-1].decode())
e = 0x10001
p.sendline(b'1')
p.recv()
p.sendline(long_to_bytes(n - 1))
p.recvuntil(b'Your encry message:\n')
cipher = int(p.recvuntil(b'\n').strip())
p.recv()
p.sendline(b'2')
p.recvline()
p.recvline()
flag = int(p.recvline().strip())
g=Root(c//(n-1),3)+1
p=(g-Root(g**2-4*n,2))//2
q=n//p
f=flag//((p+q)**3-(p-q)**2+(p+q))
print(long_to_bytes(pow(f, inverse(e, (p - 1) * (q - 1)), n)))

Random_RSA

没意思，硬卡python版本，搞半天结果要python2.7。

逆回去得到dp直接脚本梭了

from Crypto.Util.number import *
import gmpy2
import random

e = 0x10001
res = [55, 5, 183, 192, 103, 32, 211, 116, 102, 120, 118, 54, 120, 145, 185, 254, 77, 144, 70, 54, 193, 73, 64, 0, 79,
       244, 190, 23, 215, 187, 53, 176, 27, 138, 42, 89, 158, 254, 159, 133, 78, 11, 155, 163, 145, 248, 14, 179, 23,
       226, 220, 201, 5, 71, 241, 195, 75, 191, 237, 108, 141, 141, 185, 76, 7, 113, 191, 48, 135, 139, 100, 83, 212,
       242, 21, 143, 255, 164, 146, 119, 173, 255, 140, 193, 173, 2, 224, 205, 68, 10, 77, 180, 24, 23, 196, 205, 108,
       28, 243, 80, 140, 4, 98, 76, 217, 70, 208, 202, 78, 177, 124, 10, 168, 165, 223, 105, 157, 152, 48, 152, 51, 133,
       190, 202, 136, 204, 44, 33, 58, 4, 196, 219, 71, 150, 68, 162, 175, 218, 173, 19, 201, 100, 100, 85, 201, 24, 59,
       186, 46, 130, 147, 219, 22, 81]
seeds = [4827, 9522, 552, 880, 7467, 7742, 9425, 4803, 6146, 4366, 1126, 4707, 1138, 2367, 1081, 5577, 4592, 5897, 4565,
         2012, 2700, 1331, 9638, 7741, 50, 824, 8321, 7411, 6145, 1271, 7637, 5481, 8474, 2085, 2421, 590, 7733, 9427,
         3278, 5361, 1284, 2280, 7001, 8573, 5494, 7431, 2765, 827, 102, 1419, 6528, 735, 5653, 109, 4158, 5877, 5975,
         1527, 3027, 9776, 5263, 5211, 1293, 5976, 7759, 3268, 1893, 6546, 4684, 419, 8334, 7621, 1649, 6840, 2975,
         8605, 5714, 2709, 1109, 358, 2858, 6868, 2442, 8431, 8316, 5446, 9356, 2817, 2941, 3177, 7388, 4149, 4634,
         4316, 5377, 4327, 1774, 6613, 5728, 1751, 8478, 3132, 4680, 3308, 9769, 8341, 1627, 3501, 1046, 2609, 7190,
         5706, 3627, 8867, 2458, 607, 642, 5436, 6355, 6326, 1481, 9887, 205, 5511, 537, 8576, 6376, 3619, 6609, 8473,
         2139, 3889, 1309, 9878, 2182, 8572, 9275, 5235, 6989, 6592, 4618, 7883, 5702, 3999, 925, 2419, 7838, 3073, 488,
         21, 3280, 9915, 3672, 579]
n = 81196282992606113591233615204680597645208562279327854026981376917977843644855180528227037752692498558370026353244981467900057157997462760732019372185955846507977456657760125682125104309241802108853618468491463326268016450119817181368743376919334016359137566652069490881871670703767378496685419790016705210391
c = 61505256223993349534474550877787675500827332878941621261477860880689799960938202020614342208518869582019307850789493701589309453566095881294166336673487909221860641809622524813959284722285069755310890972255545436989082654705098907006694780949725756312169019688455553997031840488852954588581160550377081811151
a = []
for i in range(0, 154):
    random.seed(seeds[i])
    rands = []
    for j in range(0, 4):
        rands.append(random.randint(0, 255))
    a.append(rands[i%4])
dp=[]
for i in range(154):
    dp.append(a[i]^res[i])
print(dp)
ddp = ''
for i in dp:
    ddp += chr(i)
dp=int(ddp)
print(dp)
e=0x10001
n=81196282992606113591233615204680597645208562279327854026981376917977843644855180528227037752692498558370026353244981467900057157997462760732019372185955846507977456657760125682125104309241802108853618468491463326268016450119817181368743376919334016359137566652069490881871670703767378496685419790016705210391
c=61505256223993349534474550877787675500827332878941621261477860880689799960938202020614342208518869582019307850789493701589309453566095881294166336673487909221860641809622524813959284722285069755310890972255545436989082654705098907006694780949725756312169019688455553997031840488852954588581160550377081811151
for x in range(1, e):
    if(e*dp%x==1):
        p=(e*dp-1)//x+1
        if(n%p!=0):
            continue
        q=n//p
        phin=(p-1)*(q-1)
        d=gmpy2.invert(e, phin)
        m=pow(c, d, n)
        if(len(hex(m)[2:])%2==1):
            continue
        print(long_to_bytes(m))

secret_share

这题当时没出，第二天上的题，当天出去玩了。赛后复现2021 祥云杯 Crypto-Write Up - 安全客，安全资讯平台 (anquanke.com)

from libnum import n2s, s2n
from random import getrandbits
from hashlib import sha256
import SocketServer
from secret import flag

p, g = 0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3, 
       0x85fd9ae42b57e515b7849b232fcd9575c18131235104d451eeceb991436b646d374086ca751846fdfec1ff7d4e1b9d6812355093a8227742a30361401ccc5577


def h2(m):
    return int(sha256(m).hexdigest(), 16)


def key_gen(nbits):
    s = getrandbits(nbits) % p
    while s.bit_length() < nbits - 2:
        s = getrandbits(nbits) % p
    pk = pow(g, s, p)
    return pk, s


def enc(m, pk):
    m = s2n(m)
    e, v = getrandbits(256), getrandbits(256)
    E, V = pow(g, e, p), pow(g, v, p)
    s = v + e * h2(n2s(E) + n2s(V))
    c = m * pow(pk, e + v, p) % p
    cap = (E, V, s)
    return c, cap


def rk_gen(sk, pki, group=9):
    x, r = getrandbits(512) % p, getrandbits(512) % p
    prefix = n2s(pow(g, x * sk, p)).rjust(64, '\x00')
    encoder = [1, -pow(pki, x * sk, p) % p]
    for i in range(1, group + 1):
        pkj = getrandbits(512)
        new_encoder = [1]
        cur = pow(pkj, x * sk, p)
        for j in range(1, i + 1):
            new_encoder.append((encoder[j] + (-1) * cur * encoder[j - 1]) % p)
        new_encoder.append(encoder[i] * cur * (-1) % p)
        encoder = new_encoder
    encoder[-1] += r
    dd = h2(prefix + n2s(r).rjust(64, '\x00')) | 1
    rk = sk * dd
    return rk, encoder[1:], prefix


def re_enc(rk, cipher):
    c, (E, V, s) = cipher
    E_ = pow(E, rk, p)
    V_ = pow(V, rk, p)
    s_ = s * rk % p
    return c, (E_, V_, s_)


class ThreadedTCPServer(SocketServer.ThreadingMixIn, SocketServer.TCPServer):
    pass


class EncHandler(SocketServer.BaseRequestHandler):
    def handle(self):
        self.request.sendall("Welcome to our netdisk system! Our system store only users' ciphertext\n")
        self.request.sendall("Now you can choose what you wanna do\n")
        self.request.sendall("1. generate your key\n2. start challenge\n3. get the ciphertext")
        pk_of_one_user, sk_of_one_user = key_gen(512)
        cipher = enc(flag, pk_of_one_user)
        pk, sk = key_gen(512)
        while 1:
            mul = 1
            self.request.sendall('Input your choice\n')
            self.request.sendall("choice>")
            choice = self.request.recv(16).strip()
            if choice == '1':
                self.request.sendall('Please take good care of it!\n' + hex(pk) + ',' + hex(sk) + '\n')
            elif choice == '2':
                group_list = [32, 64, 128, 256]
                for group in group_list:
                    m = getrandbits(200)
                    plaintext = n2s(m)
                    cur_cipher = enc(plaintext, pk_of_one_user)
                    rk, encoder, prefix = rk_gen(sk_of_one_user, pk, group=group)
                    mul *= rk
                    mul %= p
                    new_cipher = re_enc(rk, cur_cipher)
                    self.request.sendall('The cipher shared to you\n' + str(new_cipher) + '\n')
                    self.request.sendall('prefix, encoder = ' + str((encoder, prefix.encode('hex'))) + '\n')
                    ans = self.request.recv(1024).strip()
                    if int(ans, 16) != m:
                        exit(1)
                self.request.sendall('You are a clever boy! Now I can share you some other information!\n' + hex(mul) + '\n')
            elif choice == '3':
                self.request.sendall(str(cipher) + '\n')
                exit(1)
            else:
                continue


if __name__ == "__main__":
    HOST, PORT = "0.0.0.0", 1213
    server = ThreadedTCPServer((HOST, PORT), EncHandler)
    server.serve_forever()

我们找到flag加密的地方，cipher = enc(flag, pk_of_one_user)。

def key_gen(nbits):
    s = getrandbits(nbits) % p
    while s.bit_length() < nbits - 2:
        s = getrandbits(nbits) % p
    pk = pow(g, s, p)
    return pk, s

pk_of_one_user, sk_of_one_user = key_gen(512)

这是一个基于离散对数的key生成方式，然后我们看到enc这个加密函数。

def enc(m, pk):
    m = s2n(m)
    e, v = getrandbits(256), getrandbits(256)
    E, V = pow(g, e, p), pow(g, v, p)
    s = v + e * h2(n2s(E) + n2s(V))
    c = m * pow(pk, e + v, p) % p
    cap = (E, V, s)
    return c, cap

用下面的数学公式表示

题目给了我们$p,g$。再看到交互流程，先生成了两组key，$pk_1,sk_1$加密$flag$，$pk_2,sk_2$用于后续加密。选项1给我们$pk_2,sk_2$，选项3给我们加密后的flag，即$cipher$。

选项2：首先生成一个随机数m，然后用$pk_1$加密得到cur_cipher，同时用$sk_1,pk_2$生成rk，encoder，prefix，给了我们后两个。再用rk加密cur_cipher，得到new_cipher，加密过程如下

加密后会给我们new_cipher，其中包括了$c,E\_,V\_,s$，我们需要求出随机数m。再看到rk的生成$rk=sk_1*dd$。

所以我们想知道m，就需要把$dd$求出来，从而得到$(EV)^{sk_1}$，进而得到m。于是我们看到rk_gen()。

def rk_gen(sk, pki, group=9):
    x, r = getrandbits(512) % p, getrandbits(512) % p
    prefix = n2s(pow(g, x * sk, p)).rjust(64, '\x00')
    encoder = [1, -pow(pki, x * sk, p) % p]
    for i in range(1, group + 1):
        pkj = getrandbits(512)
        new_encoder = [1]
        cur = pow(pkj, x * sk, p)
        for j in range(1, i + 1):
            new_encoder.append((encoder[j] + (-1) * cur * encoder[j - 1]) % p)
        new_encoder.append(encoder[i] * cur * (-1) % p)
        encoder = new_encoder
    encoder[-1] += r
    dd = h2(prefix + n2s(r).rjust(64, '\x00')) | 1
    rk = sk * dd
    return rk, encoder[1:], prefix

可以看到dd是由prefix和r进行sha256之后得到的，而r操作了endoder的最后一项，所以我们只需要通过encoder得到r，就可以求出dd。于是，我们就只需要研究中间的循环过程。

我们可以手写列举前几个encoder的递推过程

每项的规律已经很明显了，我们需要找的是对于一个encoder，找到它的一些性质。可以看到，对于前一项后面的常数，是后一项的系数。我们对每一项乘$(-1)^{i}x^{n-i}$，相加后可以发现，他们的和正好为0（项数从0开始数）。

有了上面的规律，我们就可以把我们得到的encoder补一个第0项：1，然后进行上面的操作，就可以得到r。得到r后，dd就可以算出来，m就可以得到。四轮之后，得到mul

我们只需要求4个逆，然后在有限域上开4次方，就可以得到$sk$，然后就可以求出flag。

这里贴的是striving师傅的脚本

from libnum import n2s, s2n
from hashlib import sha256
from gmpy2 import *
from pwn import *
 
def h2(m):
    return int(sha256(m).hexdigest(), 16)
 
p=remote('47.104.85.225',62351)
context.log_level='debug'
 
#1
p.recvuntil('choice>')
p.sendline('1')
p.recvuntil('Please take good care of it!\n')
pk_sk=p.recvuntil('\n')[:-1].decode()[2:-1].split('L,0x')
pk,sk=int(pk_sk[0],16),int(pk_sk[1],16)
 
#2
p.recvuntil('choice>')
p.sendline('2')
pp, g = 0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3, \
           0x85fd9ae42b57e515b7849b232fcd9575c18131235104d451eeceb991436b646d374086ca751846fdfec1ff7d4e1b9d6812355093a8227742a30361401ccc5577
   
group_list = [32, 64, 128, 256]
D=1
for group in group_list:
    p.recvuntil('The cipher shared to you\n')
    cc=int(p.recvuntil('L, ')[1:-3])
    new_cipher=[cc]
    new_cipher+=eval(p.recvuntil(')\n')[:-2].decode().replace('L',''))
    c,E_,V_,s_=new_cipher
    
    p.recvuntil('prefix, encoder = ')
    lateset_encoder,prefix=pre_enc=eval(p.recvuntil('\n')[:-1].decode().replace('L',''))
    prefix=int(prefix,16)
    encoder=[1,(-pow(prefix,sk,pp)) %pp]
    prefix = n2s(prefix).rjust(64, b'\x00')
    
    ml=[1]
    for i in range(len(lateset_encoder)):
        ml.append((ml[-1]*encoder[-1]+lateset_encoder[i]*(-1)**(i+1))%pp)
    r=-ml[-1]%pp
    dd = h2(prefix + n2s(r).rjust(64, b'\x00')) | 1
    D*=dd
    d=invert(dd,pp-1)
    cccc=E_*V_%pp
    xx=pow(cccc,d,pp)
    m=c*invert(xx,pp)%pp
    p.send(hex(m)[2:])
p.recvuntil('You are a clever boy! Now I can share you some other information!\n0x')
mul=int(p.recvuntil('\n')[:-2],16)
 
print("*****************************************************")
print(D)
print(mul)
print("*****************************************************")
#3
p.recvuntil('choice>')
p.sendline('3')
cc=int(p.recvuntil('L, ')[1:-3])
cipher=[cc]
cipher+=eval(p.recvuntil(')\n')[:-2].decode().replace('L',''))
print("*****************************************************")
print(cipher)
print("*****************************************************")
 
'''
from gmpy2 import *
p=0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3
D=
mul=
c=mul*invert(D,p)%p
e=4
R.<x> = Zmod(p)[]
f = x ^ e- c
f = f.monic()
res1 = f.roots()
print(res1)
'''
 
'''
from Crypto.Util.number import *
from gmpy2 import *
pp=0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3
sk=3415391405045794570454819264678842883406589094879440924771251075986414212665514615692960890299627279215019657097231396800926908716766924569917256830117771
cipher=[2527933870918239983384943711339580604598094277545525217834226330258419910301299206846573883556622915108773654201000637301174540362470098333217770989148988, 1534944798391033818702709152362158543885444981173771976353948339054898890879750350964082465225558424319599976320653165768478628695969238760863936634123497, 6480111027732079088305364577732332359884279592380152181509453693475437439597161069742983512858501419606525584662299391909461177747617022491590642108315732, 3294517958162409271434180708054007225109922377603959481825421096746414863994421950281118003999380326689412683711381872657890904915131742940967848977783892]
c,E,V,s=cipher
xx=E*V%pp
m=c*invert(pow(xx,sk,pp),pp)%pp
print(long_to_bytes(m))
#flag{504d0411-6707-469b-be31-9868200aca95}
'''
#http://www.zbc53.top/archives/146/