유독 crypto에서 솔버가 적었던 ctf였다.
from Crypto.Hash import SHA256
from Crypto.Util.number import long_to_bytes
import random
FLAG = open("flag", "r")
A = []
B = []
Ahash = []
Bhash = []
Ainv = {}
Binv = {}
limit = 32
setSize = 17
reps = 8
def intersection(A, B):
return [v for v in A if v in B]
def F(x):
h = SHA256.new(data=long_to_bytes(x))
return h.digest().hex()
def hash_list(l):
h = SHA256.new(data=bytes(str(l), "utf-8"))
return h.digest()
def is_valid(Asi, Bsi):
if Asi == [] or Bsi == []:
return 0
if hash_list(Asi) != hash_list(Bsi):
return 0
cnt = {}
for a in Asi:
if Ainv[a] in cnt:
cnt[Ainv[a]] += 1
else:
cnt[Ainv[a]] = 1
for v in cnt.values():
if v != reps + 1:
return 0
cnt = {}
for b in Bsi:
if Binv[b] in cnt:
cnt[Binv[b]] += 1
else:
cnt[Binv[b]] = 1
for v in cnt.values():
if v != reps + 1:
return 0
return 1
for i in range(420):
A = random.sample(range(limit), setSize)
B = random.sample(range(limit), setSize)
Ahash = []
Bhash = []
Ainv = {}
Binv = {}
for i in range(setSize):
for j in range(1, reps + 1):
A.append(A[i] + limit * j)
B.append(B[i] + limit * j)
for a in A:
h = F(a)
Ahash.append(h)
Ainv[h] = a % limit
for b in B:
h = F(b)
Bhash.append(h)
Binv[h] = b % limit
print("Alice:", Ahash)
print("Bob:", Bhash)
Asi = input("Send PSI to Alice: ").split()
Bsi = input("Send PSI to Bob: ").split()
if is_valid(Asi, Bsi):
if intersection(Ahash, Bhash) == Asi and intersection(Ahash, Bhash) == Bsi:
print("Honesty is not a way to solve this challenge")
exit()
else:
print("Cheater!")
exit()
print("You got me! Here is your flag:", FLAG.read())
-0~32 범위의 random int 17개씩 선택 (초기값)
-선택한 random int에 32*i (1≤i≤8)을 더한 수를 추가
-각각의 수를 hash한 암호의 value를 초기값으로 설정 (Ainv, Binv)
-Alice와 Bob에게 PSI 전송 → is_valid 검증(hash암호문에 해당하는 초기값이 9개씩 있어야함) → 동시에 교집합인지 확인 → 420번
Alice와 Bob이 동시에 갖는 숫자 s선택
→ 초기값이 s인 숫자의 암호문 9개 각각 선택
→ send
from Crypto.Util.number import *
from Crypto.Hash import SHA256
from pwn import *
def F(x):
h = SHA256.new(data=long_to_bytes(x))
return h.digest().hex()
def lnum(li):
res = []
for i in range(len(li)):
j = 0
while(1):
if li[i] == F(j):
res.append(j)
break
j+=1
return res
p = remote("crypto-breakpsi.ch.bts.wh.edu.pl", 1337)
for _ in range(420):
print(f"now : {_}")
p.recvuntil(b"Alice: ")
Alice = eval(p.recvline().strip())
p.recvuntil(b"Bob: ")
Bob = eval(p.recvline().strip())
bobnum = lnum(Bob)
alicenum = lnum(Alice)
x = 0
while(1):
if alicenum[x] in bobnum:
s = alicenum[x]
break
x += 1
sendalice = []
for i in alicenum:
if (i-s)%32==0:
sendalice.append(Alice[alicenum.index(i)])
sendbob = []
for i in bobnum:
if (i-s)%32==0:
sendbob.append(Bob[bobnum.index(i)])
sa = ""
for i in sendalice:
sa += i + " "
sb = ""
for i in sendbob:
sb += i + " "
p.recvuntil(b"Alice: ")
p.sendline(f"{sa}")
p.recvuntil(b"Bob: ")
p.sendline(f"{sb}")
p.interactive()
BtSCTF{4lWAys_sHuff1e_PSI_seTs}
from Crypto.Util.number import getPrime, GCD, getRandomRange
from collections import namedtuple
with open('flag', 'r') as f:
flag = f.read()
public = namedtuple('public', 'n g')
secret = namedtuple('secret', 'n phi mu')
sig = namedtuple('sig', 's1 s2')
b = 1024
p = getPrime(b)
q = getPrime(b)
assert p != q
n = p * q
phi = (p - 1) * (q - 1)
g = n + 1
mu = pow(phi, -1, n)
pk = public(n, g)
sk = secret(n, phi, mu)
# mask for additional security!!!
mask = getRandomRange(2 ** (n.bit_length() * 2 - 2), (2 ** (n.bit_length() * 2 - 1)))
def h(s: bytes) -> int:
return int.from_bytes(s, 'big', signed=True)
def int_to_bytes(n: int) -> bytes:
return n.to_bytes(n.bit_length() // 8 + 1, 'big', signed=True)
def encrypt(m: bytes, pk: public) -> bytes:
n, g = pk
r = getRandomRange(1, n)
assert GCD(r, n) == 1
mh = h(m)
c = (pow(g, mh, n ** 2) * pow(r, n, n ** 2)) % (n ** 2)
return pow(c, mask, n ** 2)
def sign(m: bytes, sk: secret) -> sig:
n, phi, mi = sk
mh = (h(m) * mask) % (n ** 2)
d = pow(mh, phi, n ** 2)
e = (d - 1) // n
s1 = (e * mi) % n
n_inv = pow(n, -1, phi)
s2 = pow(mh * pow(g, -s1, n), n_inv, n)
return sig(s1, s2)
def verify(m: bytes, sig: sig, pk: public) -> bool:
s1, s2 = sig
n, g = pk
mh = (h(m) * mask) % (n ** 2)
m_prim = pow(g, s1, n ** 2) * pow(s2, n, n ** 2) % (n ** 2)
return m_prim == mh
if __name__=="__main__":
flag_enc = encrypt(flag.encode(), pk)
flag_enc = int_to_bytes(flag_enc)
print("Hello to my signing service ^^\n")
print("My public key:")
print("n =", pk.n)
print("g =", pk.g)
print("\nHere, have flag. It's encrypted and masked anyways, so who cares.\n")
print("flag =", (flag_enc.hex()), "\n")
while True:
print("What do you want to do?")
print("[1] Sign something", "[2] Verify signature", "[3] Exit", sep="\n")
function = input(">")
if function == "1":
message = bytes.fromhex(input("Give me something to sign!\n(hex)>"))
signature = sign(message, sk)
print(f"s1 = {signature.s1}\ns2 = {signature.s2}")
if function == "2":
message = bytes.fromhex(input("Message to verify\n(hex)>"))
print("Signature:")
signature = sig(int(input("s1:\n(int)>")), int(input("s2:\n(int)>")))
if verify(message, signature, pk):
print("verified!")
else:
print("not verified!")
if function == "3":
exit()
Paillier cryptosystem를 모르는 상태에서 푸느라 문제 코드를 분석하는 데에 1시간이 넘게 걸렸다. (알았으면 달랐을까..?) 8분 차이로 퍼블을 놓쳐서 아쉽다..
key point : →
function = 1 에서 0 send
→ phi = inverse(n-s1, n)
→ mask leak using vertify formula (m = 1이면 mh = mask)
→ flag
인텐인지는 잘 모르겠다..
from Crypto.Util.number import *
from pwn import *
p = remote("crypto-textbook.ch.bts.wh.edu.pl", 1337)
for _ in range(3):
p.recvline()
p.recvuntil(b"n = ")
n = int(p.recvline())
g = n + 1
p.recvuntil(b"flag = ")
enc_flag = int(p.recvline(), 16)
#0 send -> phi leak phi = inverse(n-s1, n)
p.sendline(b"1")
p.recvuntil(b"(hex)>")
p.sendline(b"00")
p.recvuntil(b"s1 = ")
s1 = int(p.recvline())
mi = (-s1) % n
phi = inverse(mi, n)
n_inv = pow(n, -1, phi)
#mask leak
#1 send -> m = 1
p.sendline(b"1")
p.sendline(b"01")
p.recvuntil(b"s1 = ")
ss1 = int(p.recvline())
p.recvuntil(b"s2 = ")
ss2 = int(p.recvline())
mask = pow(g, ss1, n ** 2) * pow(ss2, n, n ** 2) % (n ** 2)
left = pow(enc_flag, phi, n**2)
k = (left - 1)//n
print(long_to_bytes(k*inverse(mask, n)*inverse(phi, n) % n).decode())
p.interactive()
BtSCTF{wh4t_d0_y0u_m34n_1ts_h0m0m0rph1c}
from Crypto.Util.number import getPrime, GCD, getRandomRange
from collections import namedtuple
with open('flag', 'r') as f:
flag = f.read()
public = namedtuple('public', 'n g')
secret = namedtuple('secret', 'n phi mu')
sig = namedtuple('sig', 's1 s2')
b = 1024
p = getPrime(b)
q = getPrime(b)
assert p != q
n = p * q
phi = (p - 1) * (q - 1)
g = n + 1
mu = pow(phi, -1, n)
pk = public(n, g)
sk = secret(n, phi, mu)
# masks for additional security!!!
mask1 = getRandomRange(2 ** (n.bit_length() * 2 - 2), (2 ** (n.bit_length() * 2 - 1)))
mask2 = getRandomRange(2 ** (n.bit_length() * 2 - 2), (2 ** (n.bit_length() * 2 - 1)))
def h(s: bytes) -> int:
return int.from_bytes(s, 'big', signed=True)
def int_to_bytes(n: int) -> bytes:
return n.to_bytes(n.bit_length() // 8 + 1, 'big', signed=True)
def encrypt(m: bytes, pk: public) -> bytes:
n, g = pk
r = getRandomRange(1, n)
assert GCD(r, n) == 1
mh = h(m)
c = (pow(g, mh, n ** 2) * pow(r, n, n ** 2)) % (n ** 2)
return pow(c, mask1, n ** 2)
def sign(m: bytes, sk: secret) -> sig:
n, phi, mu = sk
mh = (h(m) * mask2) % (n ** 2)
d = pow(mh, phi, n ** 2)
e = (d - 1) // n
s1 = (e * mu) % n
n_inv = pow(n, -1, phi)
s2 = pow(mh * pow(g, -s1, n), n_inv, n)
return sig(s1, s2)
def verify(m: bytes, sig: sig, pk: public) -> bool:
s1, s2 = sig
n, g = pk
mh = (h(m) * mask2) % (n ** 2)
m_prim = pow(g, s1, n ** 2) * pow(s2, n, n ** 2) % (n ** 2)
return m_prim == mh
if __name__=="__main__":
flag_enc = encrypt(flag.encode(), pk)
flag_enc = int_to_bytes(flag_enc)
print("Hello to my signing service. You don't need any keys, all is handled by me ^^\n")
#print("My public key:")
#print("n =", pk.n)
#print("g =", pk.g)
print("\nHere, have flag. It's encrypted and masked anyways, so who cares.\n")
print("flag =", (flag_enc.hex()), "\n")
while True:
print("What do you want to do?")
print("[1] Sign something", "[2] Verify signature", "[3] Encrypt something", "[4] Exit", sep="\n")
function = input(">")
if function == "1":
message = bytes.fromhex(input("Give me something to sign!\n(hex)>"))
signature = sign(message, sk)
print(f"s1 = {signature.s1}\ns2 = {signature.s2}")
if function == "2":
message = bytes.fromhex(input("Message to verify\n(hex)>"))
print("Signature:")
signature = sig(int(input("s1:\n(int)>")), int(input("s2:\n(int)>")))
if verify(message, signature, pk):
print("verified!")
else:
print("not verified!")
if function == "3":
message = bytes.fromhex(input("Message to encrypt\n(hex)>"))
ciphertext = encrypt(message, pk)
print("c =", int_to_bytes(ciphertext).hex())
if function == "4":
exit()
textbook과 달라진 점 :
-encrypt할 때의 mask, sign과 vertify할 때의 mask가 다르다. (mask1, mask2)
-n을 주지 않는다.
-원하는 평문을 encrypt할 수 있는 메뉴가 생겼다. ([3] Encrypt something)
우선 n을 leak해야 한다. (여기에 가장 시간을 많이 썼다.)
idea : 메뉴1에 1, -1을 보내면 s1은 동일하고, n_inv가 홀수이니 s2의 부호만 반대일 것이다. (합이 n일 것이다.)
위의 방식대로 n leak
→ phi, mask2는 textbook과 동일하게 leak
→ 메뉴3에 1 send
→ mask1 leak
→ flag
from Crypto.Util.number import *
from pwn import *
p = remote("crypto-textbook-2.ch.bts.wh.edu.pl", 1337)
p.recvuntil(b"flag = ")
enc_flag = int(p.recvline(), 16)
#n leak
#1 send
p.sendline(b"1")
p.sendline(b"01")
p.recvuntil(b"s1 = ")
s1 = int(p.recvline())
p.recvuntil(b"s2 = ")
s2 = int(p.recvline())
#-1 send
p.sendline(b"1")
p.sendline(b"ff")
p.recvuntil(b"s1 = ")
ss1 = int(p.recvline())
p.recvuntil(b"s2 = ")
ss2 = int(p.recvline())
n = s2 + ss2
g = n + 1
#0 send -> phi leak phi = inverse(n-s1, n)
p.sendline(b"1")
p.recvuntil(b"(hex)>")
p.sendline(b"00")
p.recvuntil(b"s1 = ")
s1 = int(p.recvline())
mi = (-s1) % n
phi = inverse(mi, n)
n_inv = pow(n, -1, phi)
#mask2 leak
#1 send -> m = 1
p.sendline(b"1")
p.sendline(b"01")
p.recvuntil(b"s1 = ")
ss1 = int(p.recvline())
p.recvuntil(b"s2 = ")
ss2 = int(p.recvline())
mask2 = pow(g, ss1, n ** 2) * pow(ss2, n, n ** 2) % (n ** 2)
#mask1 leak
p.sendline(b"3")
p.sendline(b"01")
p.recvuntil(b"c = ")
enc = int(p.recvline(), 16)
c = pow(enc, phi, n**2)
mask1 = ((c-1)//n)*inverse(phi, n) % n
c_flag = pow(enc_flag, phi, n**2)
flag = ((c_flag-1)//n)*inverse(mask1, n)*inverse(phi, n) % n
print(long_to_bytes(flag).decode())
p.interactive()
BtSCTF{p4i11i3r_15_pr3tty_c001_4nd_fun_huh}
*2, 3번 문제는 cryptohack의 Roll your Own과 원리가 유사하다.
*Paillier cryptosystem를 더 공부하자.