首发于安全客
前言
芜湖，这次祥云杯又是神仙打架，密码学一共有四道题，个人觉得最后一道题目有意思一些。
Random_RSA
task.py
1234567891011121314151617181920212223242526272829303132333435 |
from Crypto.Util.number import *import gmpy2import libnumimport randomimport binasciiimport osflag=r'flag{}'p=getPrime(512)q=getPrime(512)e=0x10001n=p*qct=pow(flag,e,n)print("n="+ n)print("ct="+ ct)dp=r''seeds = []for i in range(0,len(dp)): seeds.append(random.randint(0,10000))res = [] for i in range(0, len(dp)): random.seed(seeds[i]) rands = [] for j in range(0,4): rands.append(random.randint(0,255)) res.append(ord(dp[i]) ^ rands[i%4]) del rands[i%4] print(str(rands))print(res) print(seeds) |
题目不长，也意外的简单，值得一提的是题目介绍：一把梭，好像不行哦。
然而好像就是一把梭的题目吖，没get到出题人的点喔，而且很奇怪的是，题目用的python2的环境，却直接在给flag字符串做整型pow操作，属实奇怪。
回到题目本身，倒也没有什么好说的，给了seeds，我们利用每个seeds生成四个随机数，用第四个随机数异或res的输出，然后ord一下，就能得到dp的一个数字，最后拼起来就能获得dp了。至于已知e,n,dp三个参数解密c获得明文，这里就不再赘述了，一把梭的事。
123456789101112131415161718192021222324252627282930313233343536 |
from Crypto.Util.number import *import gmpy2import randomimport binasciiimport osseeds=[...]dps=[]res = [...]for i in range(0, len(res)): random.seed(seeds[i]) rands = [] for j in range(0,4): rands.append(random.randint(0,255)) dps.append(res[i]^rands[i%4])dp = int(''.join(chr(i) for i in dps))n=...ct=...e=0x10001def rsa_nedp(n,e,dp):for i in range(1,e):if (dp*e-1)%i == 0:if n%(((dp*e-1)/i)+1)==0:p=((dp*e-1)/i)+1q=n/(((dp*e-1)/i))+1return p,qp,q = rsa_nedp(n,e,dp)d = inverse(e,p-1)print(long_to_bytes(pow(ct,d,p))) |
最后这里解密flag直接用p了，（单纯懒，少写一个字符是一个字符了）
Guess
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175 |
from Crypto.Util.number import ( bytes_to_long, getPrime, long_to_bytes, getRandomNBitInteger,)import randomimport hashlibfrom math import gcdimport socketserverKEYSIZE = 512WELCOME = "welcome to my funny challenge !!! Can you guess right 32 times in a row? "String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"def exgcd(a, b): if b == 0: return 1, 0, a else: x, y, q = exgcd(b, a % b) x, y = y, (x - (a // b) * y) return x, y, qdef invert(a,p): x, y, q = exgcd(a,p) if q != 1: raise Exception("No solution.") else: return (x + p) % pdef lcm(a,b): return a*b // gcd(a,b)def proof_of_work(): STR = "".join([String[random.randint(0, len(String) - 1)] for _ in range(16)]) HASH = hashlib.sha256(STR.encode()).hexdigest() return STR[:4], STR[4:], HASHdef keygen(): # part 1 p, q = getPrime(KEYSIZE), getPrime(KEYSIZE) n = p * q g = n + 1 LAMBDA = lcm(p - 1, q - 1) # part 2 _key = open("key", "r").read() key = [] for i in _key.split("\n"): for j in i[1:-1].split(" "): if int(j) not in key: key.append(int(j)) assert len(key) == 80 #assert key[0] == 119 and key[1] == 241 and key[2] == 718 and key[3] == 647 return n, g, LAMBDA, keydef enc(n, g, m): while 1: r = random.randint(2, n - 1) if gcd(r, n) == 1: break c = (pow(g, m, n ** 2) * pow(r, n, n ** 2)) % (n ** 2) return cdef dec(n, g, LAMBDA, c): L1 = (pow(c, LAMBDA, n ** 2) - 1) // n L2 = (pow(g, LAMBDA, n ** 2) - 1) // n m = (invert(L2, n) * L1) % n return mclass server(socketserver.BaseRequestHandler): def _recv(self): data = self.request.recv(1024) return data.strip() def _send(self, msg, newline=True): if isinstance(msg, bytes): msg += b"\n" else: msg += "\n" msg = msg.encode() self.request.sendall(msg) def handle(self): # print("Service start.") # START, END, HASH = proof_of_work() # self._send("SHA-256(?+{}) == {}".format(END, HASH)) # RCV = self._recv().decode() # if RCV != START: # return # flag = open("flag", "rb").read() # self._send(WELCOME) # step 1. keygen for _ in range(32): self._send("round " + str(_+1)) n, g, LAM, KEY = keygen() self._send("Step 1 - KeyGen. This is my public key.") self._send("n = " + str(n)) self._send("g = " + str(g)) # step 2. Phase 1 self._send( "Step 2 - Phase 1. Now, you can give me one ciphertexts,I will return the corresponding plaintext." ) self._send("Please give me one decimal ciphertext.") cipher = int(self._recv().decode()) print(cipher) plaintext = str(dec(n, g, LAM, cipher)) self._send("This is the corresponding plaintext.") self._send(plaintext) # step 3. challenge self._send( "Step 3 - Challenge. Now, you must give me two decimal plaintexts(m0,m1), I will encry them and return a ciphertext randomly" ) self._send("Give me m0.") plaintext1 = int(self._recv().decode()) self._send("Give me m1.") plaintext2 = int(self._recv().decode()) if ( plaintext1 <= 2 or plaintext2 <= 2 or len(bin(plaintext1)) != len(bin(plaintext2)) ): return R = 2 * random.randint(0, 39) I = random.randint(0, 1) cipher1 = enc(n, g, plaintext1 * plaintext2 * KEY[R]) cipher2 = enc(n, g, plaintext1 * plaintext2 * KEY[R + 1]) self._send("This is a ciphertext.") self._send(str([cipher1, cipher2][I])) # step 4. Phase 2 self._send( "Step 4 - Phase 2. Now, you can give me some ciphertexts,I will return the corresponding plaintext.But you can not give me the ciphertext that I give you in step 3." ) self._send("Please give me one decimal ciphertext ") cipher = int(self._recv().decode()) plaintext = str(dec(n, g, LAM, cipher)) if int(plaintext) == plaintext1 * plaintext2 * KEY[R] or int(plaintext) == plaintext1 * plaintext2 * KEY[R+1]: print(plaintext) return self._send("This is the corresponding plaintext.") self._send(plaintext) # step.5 Guess self._send( "Step 5 - Guess. You must tell me which ciphertext was I give you in step 3, 0 or 1(m0 -> c0 , m1 -> c1)?" ) Guess = int(self._recv().decode()) if Guess == I: self._send("Good! You are right") else: self._send("Sorry!") return self._send(flag)class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer): passif __name__ == "__main__": HOST, PORT = "0.0.0.0", 10001 server = ForkedServer((HOST, PORT), server) server.allow_reuse_address = True server.serve_forever() |
这道题代码还挺长的，不过并不难看懂。
首先再定义server类上面的是enc和dec，其实就是paillier系统，不熟悉的读者可以移步我的这一片文章。
然后这道题目不知道是不是非预期了，因为题目给的hint我并没有到。step2的交互我也没有利用。（太奇怪了，预期该是啥样呢）
由于题目用的pailliar密码系统，具有同态（竟然说不上是乘法同态还是加法同态，只能说两个明文之和的密文，是两个明文分别的密文之积）
我们看到step4-5
题目向我们要两个明文plaintext1和plaintext2，然后加密的内容为
12 |
cipher1 = enc(n, g, plaintext1 * plaintext2 * KEY[R])cipher2 = enc(n, g, plaintext1 * plaintext2 * KEY[R + 1]) |
由于plaintext1和plaintext2可控，而两条密文的唯一区别是KEY的内容不一样。然后题目加密后随机返回一条，让我们猜返回的是哪个。
我们可以看到，这加密的明文唯一的区别就是用的是KEY[R]和KEY[R+1]，而R = 2 * random.randint(0, 39)，是一个偶数。
那么这里我们选择“炼丹”：
首先我们可以利用同态获取到实际的KEY：题目在step3发送密文cipher后，在step4会帮我们解密一条数据，但是这条数据不能是服务器加密的那两条密文之一，那么，我们就给他cipher * enc(5)，这样他就会解密后并返回plaintext1 * plaintext2 * KEY[R] + 5 或者 plaintext1 * plaintext2 * KEY[R+1] + 5, 我们再处理一下（不处理问题也不大），减掉5，除掉plaintext1 * plaintext2，就可以获取一个KEY_i 了。
然后我们到step5，我们只知道了一个KEY_i，但是不知道它具体的位置，我们直接发送0，如果返回正确，那么我们知道，这个KEY_i 在偶数位，如果返回错误，服务断掉，那么我们知道，这个KEY_i 在奇数位。那么，由于服务端的KEY序列是固定的，那么我们就开始炼丹咯。
我们构造两个数组，一个存奇数位，一个存偶数位。每次连上去，我们解密得到一个KEY_i，如果这个KEY_i 在我们的数组里，我们就能够直接返回正确答案，如果不在，我们就”炼“，猜对了，放进数组，继续猜，猜错了，放进数组，重新连。（再非不过80次连接）
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115 |
from Crypto.Util.number import ( bytes_to_long, getPrime, long_to_bytes, getRandomNBitInteger,)import randomimport hashlibKEYSIZE = 512WELCOME = "welcome to my funny challenge !!! Can you guess right 32 times in a row? "String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz"from math import gcddef exgcd(a, b): if b == 0: return 1, 0, a else: x, y, q = exgcd(b, a % b) x, y = y, (x - (a // b) * y) return x, y, qdef invert(a,p): x, y, q = exgcd(a,p) if q != 1: raise Exception("No solution.") else: return (x + p) % pdef lcm(a,b): return a*b // gcd(a,b)def proof_of_work(): STR = "".join([String[random.randint(0, len(String) - 1)] for _ in range(16)]) HASH = hashlib.sha256(STR.encode()).hexdigest() return STR[:4], STR[4:], HASHdef enc(n, g, m): while 1: r = random.randint(2, n - 1) if gcd(r, n) == 1: break c = (pow(g, m, n ** 2) * pow(r, n, n ** 2)) % (n ** 2) return cdef dec(n, g, LAMBDA, c): L1 = (pow(c, LAMBDA, n ** 2) - 1) // n L2 = (pow(g, LAMBDA, n ** 2) - 1) // n m = (invert(L2, n) * L1) % n return mfrom pwn import *from pwnlib.util.iters import mbruteforcefrom hashlib import sha256#context.log_level = 'debug'def proof_of_work(sh): sh.recvuntil("?+") suffix = sh.recvuntil(')').decode("utf8")[:-1] log.success(suffix) sh.recvuntil("== ") cipher = sh.recvline().strip().decode("utf8") proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() == cipher, string.ascii_letters + string.digits, length=4, method='fixed') sh.sendline(proof)vanish=[]#奇s=[]#偶ss=[]for _ in range(80):sh=remote("47.104.85.225","57811")proof_of_work(sh)while True:tmp = sh.recvuntil("n = ")n = int(sh.recvuntil("\n")[:-1])sh.recvuntil("g = ")g = int(sh.recvuntil("\n")[:-1])sh.recvuntil("decimal ciphertext.\n")sh.sendline("123")sh.recvuntil("Give me m0.\n")sh.sendline("5")sh.recvuntil("Give me m1.\n")sh.sendline("5")sh.recvuntil("This is a ciphertext.\n")c = int(sh.recvuntil("\n")[:-1])sh.recvuntil("Please give me one decimal ciphertext \n")sh.sendline(str((enc(n,g,5)*c)%(n**2)))sh.recvuntil("This is the corresponding plaintext.\n")m = (int((sh.recvuntil("\n")[:-1]))-5)//25sh.recvuntil("0 or 1(m0 -> c0 , m1 -> c1)?\n")if m in s:sh.sendline('1')tmp = sh.recvuntil("\n")elif m in ss:sh.sendline('0')tmp = sh.recvuntil("\n")else:sh.sendline('1')tmp = sh.recvuntil("\n")if b"Good! You are right" in tmp:s.append(m)elif b"Sorry" in tmp:ss.append(m)sh.close()breakprint(s)print(ss) |
myRSA
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 |
# myRSAfrom Crypto.Util.number import getPrime,bytes_to_long as b2lfrom math import gcdimport hashlibimport randomimport socketserverKEYSIZE = 512alpha = 2.0314159265358979WELCOME = 'Welcome to use my better RSA!!!!!!So, what do you want now?'menu = '1. encry \n2. getflag\n3. exit'String = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890abcdefghijklmnopqrstuvwxyz'def proof_of_work(): STR = ''.join([String[random.randint(0,len(String)-1)] for _ in range(16) ]) HASH = hashlib.sha256(STR.encode()).hexdigest() return STR[:4],STR[4:],HASHdef key_gen(): while True: p,q = getPrime(KEYSIZE),getPrime(KEYSIZE) e = 0x10001 if gcd(e,(p-1)*(q-1)): break key = [getPrime(int(KEYSIZE*alpha)) for _ in range(2)] return (p,q,e),key# encryptodef encry(message,key,p,q,e): k1,k2 = key[0],key[1] x = p**2 * (p + 3*q - 1 ) + q**2 * (q + 3*p - 1) y = 2*p*q + p + q z = k1 + k2 c = pow(b2l(message),e,p*q) return x * c + y * c + z# get flagdef getflag(flag,key,p,q,e): return encry(flag,key,p,q,e)class server(socketserver.BaseRequestHandler): def _recv(self): data = self.request.recv(1024) return data.strip() def _send(self, msg, newline=True): if isinstance(msg , bytes): msg += b'\n' else: msg += '\n' msg = msg.encode() self.request.sendall(msg) def handle(self): START,END,HASH = proof_of_work() self._send('SHA-256(?+{}) == {}'.format(END,HASH)) RCV = self._recv().decode() if RCV != START: return self._send("I'm a CryptoRookie,so my Crypto system take time, please wait a minute XD!") (p,q,e),key = key_gen() flag = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" self._send(WELCOME) self._send('This is my public key:\nn = {}\ne = {}'.format(str(p*q),str(e))) for _ in range(16): self._send(menu) COI = int(self._recv().decode()) if COI == 1 : self._send('Give me your message') message = self._recv() self._send('Your encry message:') self._send(str(encry(message,key,p,q,e))) elif COI == 2: self._send('This is your favourite:\n') self._send(str(encry(flag,key,p,q,e))) elif COI == 3: self._send('Bye~') breakclass ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer): passif __name__ == "__main__": HOST, PORT = '0.0.0.0', 10001 server = ForkedServer((HOST, PORT), server) server.allow_reuse_address = True server.serve_forever() |
这道题，emmm，也是奇怪的加密方式，
1234567 |
def encry(message,key,p,q,e): k1,k2 = key[0],key[1] x = p**2 * (p + 3*q - 1 ) + q**2 * (q + 3*p - 1) y = 2*p*q + p + q z = k1 + k2 c = pow(b2l(message),e,p*q) return x * c + y * c + z |
题目提供提供十六次交互，它可以帮你加密，但每次加密用的z随机
x * c + y * c + z =( x+y ) * c + z
其中( x+y ) = ( p+q )^3 - ( p+q )^2 + ( p+q ) - 4 * n
那么我们发送明文 ’\x01’ 过去，就能得到enc = x + y + z，所以 enc + 4 * n = (p+q)^3 - (p+q)^2 + (p+q) + z
我们可以将其看作关于（p+q）的方程 f(x) ，由于z不知道，没法根据返回值解一个具体的值x。
但是算一下长度，(p+q)^3 有 513 * 3 = 1539 bit，z 才 1024bit左右，相对比较小。那么我们直接不管z，去解方程（这里我是用2分法去逼近的），然后我们可以得到一个大概的值。
有了大概的 $x \approx (p+q)$，再利用n，就能得到一个大概的p值，
$p \approx \frac{x - \sqrt{x^2 - 4n}}{2}$
有了大概的p值，我们可以本地起一组数据看看和真正的p值差多少，可以发现就差小几万，那么我们直接一手small_roots恢复p。p，q都恢复了，我们直接交互拿到flag的密文 ( x + y) * pow(flag, e, n) + z
直接整除 (x + y) 得到pow(flag, e, n)，（z太小了，整除就给消没了），后面，rsa解密，得到flag。
P.S.不懂出题人干嘛搞一个genkey浪费时间，有啥必要么，还是说，又又又又又又又又又又又又非预期了？确实没用到16次交互。
12345678910111213141516171819202122232425262728293031323334353637383940414243 |
#交互拿到数据a = x + y + z; c = pow(flag,e,n) * (x + y) + zfrom Crypto.Util.number import *def f(x): return x**3 - x**2 + x + 4*nn = ...e = 65537a = ...c = ...floor = 0sky = 2**1041while floor+1 < sky: mid = (floor + sky) // 2 if f(mid) < a: floor = mid else: sky = midimport gmpy2 p_sub_q = gmpy2.iroot(int(mid**2-4*n),int(2))[0]pw = (mid-p_sub_q)//2N = npbar = pwZmodN = Zmod(N)P.<x> = PolynomialRing(ZmodN)ff = int(pbar) + xx0 = ff.small_roots(X=2^40, beta=0.4)[0]p = int(int(pbar) + x0)n = int(n)q = n // ptmp = f(p+q)c //= tmpprint(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),n))) |
ok，终于来到最有意思的一题了，也是足足做了我快5个小时（虽然中途思路断了的时候去把XMAN结营赛的密码学赛题AK了下）
secret_share
task
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105 |
#! /usr/bin/env pythonfrom libnum import n2s, s2nfrom random import getrandbitsfrom hashlib import sha256import SocketServerfrom secret import flagp, g = 0xb5655f7c97e8007baaf31716c305cf5950a935d239891c81e671c39b7b5b2544b0198a39fd13fa83830f93afb558321680713d4f6e6d7201d27256567b8f70c3, \ 0x85fd9ae42b57e515b7849b232fcd9575c18131235104d451eeceb991436b646d374086ca751846fdfec1ff7d4e1b9d6812355093a8227742a30361401ccc5577def 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, sdef 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, capdef 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:], prefixdef 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): passclass 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\n2. 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: continueif __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)
看到这个pk_of_one_user，
12345678 |
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, spk_of_one_user, sk_of_one_user = key_gen(512) |
基于离散对数问题的公私钥对 $pk \equiv g^{sk} \pmod p$
然乎看到enc的加密方式
12345678 |
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 |
可以化为式子： $c \equiv m \cdot pk^{e+v} \equiv m \cdot g^{(e+v)\cdot sk} \equiv m \cdot (E \cdot V) ^ {sk}\pmod p $
那么想获取flag，就要搞到这个私钥sk咯，看看怎么能搞到。
第一目标：拿到sk
可以看到交互提供三个功能，第一个，获取你自己的公私钥对 pk，sk
再看下第三个，返回flag的密文，
然后第二个比较长，核心功能也就在这里了，
1234567891011121314 |
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) |
流程描述：
他会生成一个随机数m，
然后它的公钥加密m得到cur_cipher，
然后将它的私钥和我们的公钥放进rk_gen这个函数，会得到 rk, encoder, prefix
然后mul = mul * rk % p，
然后用rk，re_enc这个cur_cipher
然后把re_enc后的密文，encoder, prefix 发送给我们。
然后然我们解密m，对了继续，错了拜拜。
循环四次，都通过返回给你mul。
整理逻辑。如果我们都通过了，就能拿到 mul = rk_1 * sk * rk_2 * sk * rk_3 sk * rk_4 % p
有了这个mul，有啥意义么？这里还看不出来，我们继续往前走先，不过有一个问题很明确，既然出题人就这么布置了，我们当然是需要解密m了。
第二目标，解密m
想要解密m，我们相关信息只有re_enc后的cipher，当前轮次的encoder, prefix
看看这个re_enc
123456 |
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_) |
可以发现，整个函数都没有操作c，就更新了一下E, V, s
那么更新一下我们手里的信息，$cipher \equiv m \cdot g^{sk \cdot (e+v) } \equiv m \cdot (E\cdot V) ^{sk},E_ \equiv E^{rk},V_ \equiv V^{rk}, s \equiv s \cdot rk $
就这么多了，我们再去看看返回encoder, prefix 的 rk_gen函数，
12345678910111213141516 |
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 |
先不管其他的，看到最下面，rk = sk * dd
我们回想到 mul = rk_1 * sk * rk_2 * sk * rk_3 sk * rk_4 % p ，
那么可以转化为 mul = sk^4 * dd1 * dd2 * dd3 * dd4 % p ，
有了dd的product，那么我们再在模p下给sk^4开个四次根就能拿到sk了！
而 dd = h2(prefix + n2s(r).rjust(64, ‘\x00’)) | 1，其中prefix已知，所以目标很明确
第三目标，获取r
我们能够注意到，返回给我们的encder与r相关， 其中encoder[-1] += r，所以我们需要恢复出原来的encoder，
那就得从头看这个函数了，我们首先看到，prefix = n2s(pow(g, x * sk, p)).rjust(64, ‘\x00’)，其中x是未知随机数，sk是服务端公钥，
然后初始 encoder = [1, -pow(pki, x * sk, p) % p]，划重点，需要注意到，这里的pki，用的是再step1中给我们的pk，我们是知道其对应的sk的！我们把自己的sk记为ski，避免搞混，那么式子：$encoder \equiv - pki^{x \cdot sk} \equiv -g^{ski \cdot s \cdot sk}$，这个时候，再去看看prefix的表达式 $prefix = g^{s \cdot sk}$，就只差一个 ski ，而这个ski我们是已知的，所以我们就获得了初始 encoder = [1, -pow(prefix, ski, p) % p]
核心的迭代来了
12345678 |
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 |
cur = pow(pkj, x * sk, p)，pkj是一个随机数，所以cur显然无法直接得到，然后是循环里的 new_encoder.append((encoder[j] + (-1) * cur * encoder[j - 1]) % p)
走出后还来一下 new_encoder.append(encoder[i] * cur * (-1) % p)
这里建议画个美丽的图会稍微清晰一些
可以看到，如果对于cur2那一行，在我们知道 x 的前提下，我们是能够通过第二项获取到 （cur1 + cur2） 的值的，
在我们知道（cur1 + cur2） 的值的前提下，我们是能够获得第三项中 （cur1 * cur2）的值的。
有了（cur1 * cur2）的值，我们再将他乘以x，我们就获得了encoder最后一项的值了。
芜湖，起飞！（如果觉得就分析这么三轮还不够的化，可以再画第四轮，就很清晰了）
那么我们迎来了处理 encoder的核心解法，基本上可以宣布此题告破了。
我们只需要用题目给的 encoder 和 prefix，进行上述操作
1234567 |
encoder,prefix = ...x = -pow(prefix,sk,p)%pencoder_i=1for i in encoder[:-1]: encoder_i = (i-encoder_i*x)%pr = (encoder[-1] - encoder_i*x)%p |
就能够获取到r了！
有了r，我们就可以生成dd，但是为了获取到最后的mul，我们还要去解密一下m，
再此看到m的密文 $cipher \equiv m \cdot g^{sk \cdot (e+v) } \equiv m \cdot (E\cdot V) ^{sk}$
我们还知道 $rk = sk \cdot dd,E_ \equiv E^{rk},V_ \equiv V^{rk}, s \equiv s \cdot rk $
解密m就要知道 $(E\cdot V) ^{sk}$
但是想要知道$(E\cdot V) ^{sk}$，就一定需要知道sk么？我们拥有$E_ \cdot V_ = (E\cdot V) ^ {rk} \equiv (E\cdot V) ^ {sk \cdot dd} $
而我们知道 dd，所以直接求一个$(E_ \cdot V_)^{dd^{-1}} \equiv (E \cdot V) ^ {sk \cdot dd \cdot dd^{-1}} \equiv (E \cdot V) ^ {sk}$，（需要注意一下，给dd求逆的时候，模的是 p - 1，这个应该不用解释了）
好了，这样我们就能解密m，通过check，拿到mul，开根得到备选sk（四次根，不出意外有多解），再用通过功能3，拿一份flag的cipher，用备选sk计算 $(E \cdot V) ^ {sk}$，求逆然后乘以cipher，然后顺利拿到flag，完结撒花！
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394 |
from pwn import * from random import getrandbitsfrom hashlib import sha256from Crypto.Util.number import *def n2s(n): return long_to_bytes(n)def s2n(n): return bytes_to_long(n)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, sdef 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, capp, g = ...#context.log_level = 'debug'sh = remote("47.104.85.225","62351")#sh = remote("0.0.0.0","1213")sh.recvuntil("choice>")sh.sendline("1")sh.recvuntil("Please take good care of it!\n")tmp = sh.recvuntil("\n")[:-1]#获取自己的pk和skpk,sk = eval(tmp)B=[]sh.recvuntil("choice>")sh.sendline("2")for _ in range(4):sh.recvuntil("The cipher shared to you\n")tmp = sh.recvuntil("\n")[:-1]#获取到 re_enc(m) 后给的 c, (E_, V_, s_)c, (E_, V_, s_) = eval(tmp)sh.recvuntil("prefix, encoder = ")tmp = sh.recvuntil("\n")[:-1]#利用 encoder,prefix 获取r，从而得到ddencoder,prefix = eval(tmp)prefixx = prefix.decode('hex')prefix = int(prefix,16)x = -pow(prefix,sk,p)%ptmp=1for i in encoder[:-1]:tmp = (i-tmp*x)%pr = (encoder[-1] - tmp*x)%pprefix = n2s(pow(g, x * sk, p)).rjust(64, '\x00')dd = h2(prefixx + n2s(r).rjust(64, '\x00')) | 1B.append(dd)dd_ = inverse(dd,p-1)#有了dd利用 E_ * V_ 解密m m = inverse(pow(E_*V_,dd_,p),p)*c % psh.sendline(hex(m)[2:])sh.recvuntil("You are a clever boy! Now I can share you some other information!\n")tmp = sh.recvuntil("\n")[:-1]#拿着通关后给的mul，待会去开根mul = eval(tmp)sh.recvuntil("choice>")sh.sendline("3")tmp = sh.recvuntil("\n")[:-1]#获取flag密文相关的参数c, (E, V, s) = eval(tmp)#把mul里的dd去掉，得到sk^4for i in B:mul = mul * inverse(i,p) % psk_4 = mul sh.interactive() |
拿到 sk^4 后要开根，这里我切到sagemath去直接用nth_root了
123456789101112 |
a,b = Mod(sk_4,p).nth_root(4,all=True)tmp = pow(int(E*V),int(a),int(p))m = c * inverse_mod(int(tmp),int(p)) % int(p)print(long_to_bytes(m))tmp = pow(int(E*V),int(b),int(p))m = c * inverse_mod(int(tmp),int(p)) % int(p)print(long_to_bytes(m))b'flag{504d0411-6707-469b-be31-9868200aca95}'b'\x9at\x03O\xbd;.\xb5\x97Tz$t2V\x9b\x92\xa8\x0c.O\x89V\x05\xbf\xb9\x0e\xfb\xfcRC\x8e\x948qB\xee\x92y\x02\xbf|\xf6Sq\x81\xdf;!\xd1\x9fmJ\xfb\x87#\xbb10\xa4t\xfd\xd4\x9a' |
结语
整体来看，这次比赛的题目难度中等叭，第一题一把梭没啥好说的，第二题非预期的炼丹，也还行吧，赛后也没问着hint怎么用，不过第一次交互好像是用来获取lamda的，我直接用同态过check好像也是非预期了。第三题化二元方程为一元，然后二分（哦，求一下导可以知道后面是递增的所以能二分）去求一个大概解，也挺有意思的。不过最喜欢的还是最后一题，初看觉得整个代码的处理流程很冗长，但是一点点去将题目解析，将问题一点点规约下去，这种一点点拨开云雾见天日，守得云开见月明的感觉属实不错，而且难度也刚好在我的level，舒服了。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论