from Crypto.Util.number import * from string import ascii_letters, digits table = ascii_letters+digits cipher = "t6b7Tn{2GByBZBB-aan2-JRWn-GnZB-Jyf7a722ffnZ}" MOD = len(table)
deffind_ab(): for a inrange(MOD): for b inrange(MOD): if (a*table.find("0")+b) % MOD == table.find(cipher[0]): if (a*table.find("x")+b) % MOD == table.find(cipher[1]): if (a*table.find("G")+b) % MOD == table.find(cipher[2]): if (a*table.find("a")+b) % MOD == table.find(cipher[3]): print("a, b = {}, {}".format(a,b)) return (a, b)
flag = "" A, B = find_ab() for i in cipher: if i notin table: flag += i else: flag += table[inverse(A, MOD)*(table.find(i)-B) % MOD] print(flag)
0xGame{1b292822-33e1-46fe-be82-49ca3a11cce8}
equationSet
这题是个简单的解方程组,可以发现给出的值有
nst=p⋅q⋅r=p+q+r=p⋅(q+r)
我们需要求的是
ϕ(n)=(p−1)⋅(q−1)⋅(r−1)
其中
p=GCD(n,t)
所以
ϕ(n)=(p−1)⋅(q⋅r−(q+r)+1)=(p−1)⋅((n−t)/p+1)
exp:
1 2 3 4 5 6 7 8 9 10 11 12
from Crypto.Util.number import *
c = 216719040256186298397028655750064798850... n = 894056034566447301955142597300391580123... s = 296550633935119159669335323468002356547... t = 157435908314881832180551915807491465031...
p = GCD(n, t) phi = (p-1)*((n-t)//p+1) d = inverse(65537, phi) m = pow(c, d, n) print(long_to_bytes(m))
这个周期就是皮萨诺周期(Pisano periods),先对 n 进行素因数分解,然后求解每个素数幂的周期,最后通过中国剩余定理(Chinese remainder theorem)合并,一个素数幂 pn 的周期等于 pn−1 乘以 p 的周期,所以需要求出每个素因数的周期。这里分为两种情况,如果 5 是模 p 的二次剩余,那么 p 的周期是 p−1 的一个因数;如果不是,那么周期为 2(p+1) 的一个因数。5 是否为模 p 的二次剩余,可以通过勒让德(Legrend)符号来判断。
from Crypto.Util.number import * from gmpy2 import next_prime
defgenFibonacci(): a = [1, 1] for i inrange(2, 2**16): a.append(a[i-1]+a[i-2]) return a
defLegrend(a, p): if a == 1: return1 if p % a == 0: return0 if a % 2 == 0: return Legrend(a // 2, p) * pow(-1, (pow(p, 2) - 1) // 8) return Legrend(p % a, a) * pow(-1, (a - 1)*(p - 1) // 4)
defisPeriod(T, a): for t inrange(T): p = t+T while p < len(a): if a[p] != a[t]: returnFalse p += T returnTrue
defFactor_n(n): a = [] for i inrange(2**3, 2**5): if (not isPrime(i)) or (n % i): continue a.append([i, 0]) n = n//i while n % i == 0: n = n//i a[-1][1] += 1 return a
defFactor_x(x): a = [] for i inrange(2, x): if x % i == 0: a.append(i) return a
defsolve(a): per = [] for i inrange(len(a)): prime = a[i][0] if Legrend(5, prime) == 1: fac = Factor_x(prime-1) tmp = prime-1 else: fac = Factor_x(2*(prime+1)) tmp = 2*(prime+1) fib_mod = [(k % prime) for k in fib] for t in fac: if isPeriod(t, fib_mod): per.append(t*(prime**a[i][1])) break else: per.append(tmp*(prime**a[i][1]))
LCM = per[0] for i inrange(1, len(per)): LCM = (per[i]*LCM)//GCD(LCM, per[i]) return LCM
r = 6799657976717333 n = 34969 c = 18230697428395162035214602694158399484881314... N = 18856119995376203055253776689360000192482523...
fib = genFibonacci() a = Factor_n(n) T = solve(a)
fib_mod = [(k % n) for k in fib] S = sum(fib_mod[:T])*(r//T)+sum(fib_mod[:r%T]) p = next_prime(S**16) q = N//p m=pow(c,inverse(65537,(p-1)*(q-1)),N) print(long_to_bytes(m))
defCRT(a, m): Num = len(m) M = reduce(lambda x, y: x*y, m) Mi = [M//i for i in m] t = [invert(Mi[i], m[i]) for i inrange(Num)] x = 0 for i inrange(Num): x += a[i]*t[i]*Mi[i] return x % M
defgetData(): line = r.recvuntil(b"> ") r.sendline(b"1") line = r.recvline().decode().strip() mod, res = int(line[9:25], 16), int(line[37:54], 16) return (mod, res)
proof_of_work() m = [] a = [] for i inrange(8): mod, res = getData() m.append(mod) a.append(res) flag = CRT(a, m) print(long_to_bytes(flag)) r.interactive() # 0xGame{3a8f45be-a0cf-457e-958e-b896056841d7}
n = 15321211041844905603734344178124947... c = 14896093236493033914781929755936872... x = 26506090189848554080676908570070818... e = 65537 kphi = x*e-11 for r inrange(e): k = 7*e+11*r if kphi % k: continue phi = kphi//k iflen(bin(n-phi+1)[2:]) > 1025: continue print(long_to_bytes(pow(c, inverse(e, phi), n))) # 0xGame{cfac8284-3013-439b-8ff3-884decb642bb}
proof_of_work() r.recvuntil(b"n : ") n = int(r.recvline().decode().strip(), 16) e = 65537 flag=b"" for i inrange(44): mask=b"1"*(44-i-1) print(mask) r.sendlineafter(b"> ", b"1") r.sendlineafter(b"Your mask (in hex): ",hex(pow(bytes_to_long(mask),e,n))[2:].encode()) tar = int(r.recvline().decode().strip(), 16) for j inrange(32,128): guess=flag+long_to_bytes(j)+mask ifpow(bytes_to_long(guess),e,n)==tar: flag+=long_to_bytes(j) print(flag) break r.interactive()
ElGamal
这题的考点是判断二次剩余,如果发现了y是二次剩余的话,那么只需要判断c1是否为二次剩余就可以了。
1 2 3 4 5 6 7 8 9
from Crypto.Util.number import *
y = 2101136318398982764494355697982735290351867853540128399809061806690701481465143258501856786165972388085070268979718711434744226290744692988395355120277617 g = 8401562798890834492298947403582806359769363301996138198850077614144023393945770711612546197987255078645962298286362268504959833530010137313108031112774451 p = 10946148224653120484646906462803901217745837751637974066354601688874051778651193811412739372059281847771491564589986518154039493312147458591216351424346123
datalist = [c.split(", ") for c inopen("data", "r").read().split("\n")[:-1]] flag = "".join(["0"ifpow(int(c[1], 16), (p-1)//2, p) == 1else"1"for c in datalist]) print(long_to_bytes(int(flag,2)))
from Crypto.Util.number import * f = open("data", "r").read().split("\n")[:-1] datalist = [c.split(", ") for c in f]
y = 2101136318398982764494355697982735290351867853540128399809061806690701481465143258501856786165972388085070268979718711434744226290744692988395355120277617 g = 8401562798890834492298947403582806359769363301996138198850077614144023393945770711612546197987255078645962298286362268504959833530010137313108031112774451 p = 10946148224653120484646906462803901217745837751637974066354601688874051778651193811412739372059281847771491564589986518154039493312147458591216351424346123
flag = "" for c in datalist: output = -1 if (pow(y, (p-1)//2, p) == 1) or (pow(int(c[0], 16), (p-1)//2, p) == 1): ifpow(int(c[1], 16), (p-1)//2, p) == 1: flag += "0" else: flag += "1" else: ifpow(int(c[1], 16), (p-1)//2, p) == 1: flag += "1" else: flag += "0" flag = long_to_bytes(int(flag,2)) print(flag)