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数就很小,如果对其开三次方,就不会有很大影响。可以近似认为。然后对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
用下面的数学公式表示
题目给了我们。再看到交互流程,先生成了两组key,加密,用于后续加密。选项1给我们,选项3给我们加密后的flag,即。
选项2:首先生成一个随机数m,然后用加密得到cur_cipher,同时用生成rk,encoder,prefix,给了我们后两个。再用rk加密cur_cipher,得到new_cipher,加密过程如下
加密后会给我们new_cipher,其中包括了,我们需要求出随机数m。再看到rk的生成。
所以我们想知道m,就需要把求出来,从而得到,进而得到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,找到它的一些性质。可以看到,对于前一项后面的常数,是后一项的系数。我们对每一项乘,相加后可以发现,他们的和正好为0(项数从0开始数)。
有了上面的规律,我们就可以把我们得到的encoder补一个第0项:1,然后进行上面的操作,就可以得到r。得到r后,dd就可以算出来,m就可以得到。四轮之后,得到mul
我们只需要求4个逆,然后在有限域上开4次方,就可以得到,然后就可以求出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/
Comments NOTHING