commit 002593ce2fc3f75c20fc2cf4f28303e1e8b5f25d
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 10 May 2024 19:53:10 +0200
Add solution
Diffstat:
3 files changed, 146 insertions(+), 0 deletions(-)
diff --git a/chall/main.py b/chall/main.py
@@ -0,0 +1,48 @@
+import secrets
+import hashlib
+from Crypto.Util.number import isPrime, long_to_bytes
+
+FLAG = b'grey{fake_flag}'
+
+e = 0x10001
+
+def checkN(N):
+ if (N < 0):
+ return "what?"
+ if (N.bit_length() != 4096):
+ return "N should be 4096 bits"
+ if (isPrime(N) or isPrime(N + 23)):
+ return "Hey no cheating"
+ return None
+
+def xor(a, b):
+ return bytes([i ^ j for i,j in zip(a,b)])
+
+def encrypt(key, msg):
+ key = hashlib.shake_256(long_to_bytes(key)).digest(len(msg))
+ return xor(key, msg)
+
+print("This is my new Oblivious transfer protocol built on top of the crypto primitive (factorisation is hard)\n")
+print("You should first generate a number h which you know the factorisation,\n")
+print("If you wish to know the first part of the key, send me h")
+print(f"If you wish to know the second part of the key, send me h - {23}\n")
+
+N = int(input(("Now what's your number: ")))
+
+check = checkN(N)
+if check != None:
+ print(check)
+ exit(0)
+
+k1, k2 = secrets.randbelow(N), secrets.randbelow(N)
+k = k1 ^ k2
+
+print("Now I send you these 2 numbers\n")
+print(f"pow(k1, e, N) = {pow(k1, e, N)}")
+print(f"pow(k2, e, N+23) = {pow(k2, e, N + 23)}\n")
+
+print("Since you only know how to factorise one of them, you can only get one part of the data :D\n")
+print("This protocol is secure so sending this should not have any problem")
+print(f"flag = {encrypt(k, FLAG).hex()}")
+print("Bye bye!")
+
diff --git a/solve/requirements.txt b/solve/requirements.txt
@@ -0,0 +1,2 @@
+pwntools==4.9.0
+pycryptodome==3.18.0
diff --git a/solve/solve.py b/solve/solve.py
@@ -0,0 +1,96 @@
+from pwn import *
+from math import lcm
+from Crypto.Util.number import isPrime, long_to_bytes
+
+def checkN(N):
+ if (N < 0):
+ return "what?"
+ if (N.bit_length() != 4096):
+ return "N should be 4096 bits"
+ if (isPrime(N) or isPrime(N + 23)):
+ return "Hey no cheating"
+ return None
+
+def xor(a, b):
+ return bytes([i ^ j for i,j in zip(a,b)])
+
+def decrypt(key, msg):
+ key = hashlib.shake_256(long_to_bytes(key)).digest(len(msg))
+ return xor(key, msg)
+
+# generated with: openssl dhparam 4091
+# might take multiple tries to hit 4096-bit N
+p = """
+07:79:28:c9:e4:cf:f8:bb:ee:5e:88:73:32:40:88:
+08:2f:85:d8:e5:94:d0:c9:9b:ea:29:73:3b:6a:a7:
+1d:ff:f7:c6:a2:96:cf:b9:a4:2f:a8:b1:26:ab:ec:
+15:ae:14:06:89:ee:67:1e:55:de:89:db:b6:61:41:
+5d:ff:0c:09:3f:04:09:85:98:e5:5c:3e:95:a2:5b:
+a5:e9:0e:8b:4e:0a:7b:ea:eb:4b:d3:5f:10:fd:2e:
+a6:8b:2a:91:21:a2:b5:c0:95:74:67:69:9c:76:95:
+5d:8c:a5:db:a7:1a:b1:9b:84:35:95:98:fd:77:41:
+05:68:da:84:0b:13:d4:bb:69:05:6e:92:57:f1:6a:
+da:ed:7b:57:ae:dc:d0:96:9e:78:e5:35:cf:7c:1e:
+3b:26:db:10:0d:aa:85:56:ae:27:ca:ea:f6:ef:b7:
+d7:9f:58:02:b3:83:73:18:7d:f2:af:7b:a2:ba:63:
+de:79:d5:cf:f1:66:37:2c:cf:8b:39:dc:af:1b:9d:
+c2:b5:60:78:f8:a6:45:e9:7d:4c:34:a3:ec:3a:4e:
+64:13:a9:de:f0:94:c9:d9:c8:d1:ee:e3:41:09:f1:
+94:1c:e0:8e:00:9d:d3:80:51:84:37:2d:08:07:e6:
+cb:83:d4:43:de:1c:84:ae:81:1a:04:9c:4b:3b:27:
+7e:2a:aa:ac:e4:62:4f:ce:ee:5b:38:d0:cc:48:d3:
+5e:17:fe:b7:83:98:4b:9f:8e:55:aa:c6:98:c3:66:
+e9:10:eb:e9:28:9d:b8:a2:90:64:4a:24:bc:ea:d7:
+0c:19:7f:6b:ae:5f:ea:03:25:0d:1e:ac:e1:7f:98:
+18:2f:19:99:81:ae:79:29:67:5d:08:22:f7:59:54:
+d0:07:07:30:3b:52:6a:3b:de:11:75:a7:f4:28:fc:
+20:f4:be:f3:a0:6e:b4:2a:d6:20:26:21:61:54:02:
+61:8c:c6:6b:73:43:46:23:57:5a:39:67:c2:95:2b:
+dd:1b:4a:f1:94:50:c4:77:40:a7:30:31:ee:6e:3e:
+6b:5a:51:fe:0a:e7:d1:80:98:c6:12:28:00:8a:94:
+43:bb:9e:38:bb:24:6f:3c:2f:04:e3:71:4b:48:85:
+b8:08:4d:f3:12:73:47:a1:38:2d:85:22:d3:dd:81:
+1a:ca:eb:42:df:cf:32:5a:e7:23:a1:98:04:08:a7:
+ae:87:7b:4e:ff:c2:35:a1:04:23:c1:9d:ae:46:1e:
+43:9f:e8:5d:a7:96:b0:72:09:db:a2:ad:3d:c8:fe:
+e4:76:71:15:60:d9:ea:0e:d8:d0:c5:b7:0a:76:3b:
+29:c3:94:34:8d:bd:75:cd:9a:d5:ac:f2:38:13:02:
+35:bf
+"""
+p = int.from_bytes(bytes([int(v,16) for v in p.replace("\n", "").split(":")]), "big")
+import math
+print(math.log2(p))
+assert(isPrime(p) and isPrime(p//2))
+pp = p // 2 # 4090.? - 1 = 4089.?
+
+e = 0x10001
+n = pp * 2 * 23 # 4089.? + 1 + 4.523 = 4094.? or 4095.?
+n2 = p * 23
+print(math.log2(n))
+assert(checkN(n) is None)
+
+while True:
+ io = process("python3 ../chall/main.py".split())
+ io.sendline(str(n).encode())
+ io.readuntil(b" = ");
+ r1 = int(io.readline())
+ io.readuntil(b" = ");
+ r2 = int(io.readline())
+ io.readuntil(b" = ");
+ flag = bytes.fromhex(io.readline().strip().decode())
+
+ carmichael = lambda *a: lcm(*[v-1 for v in a])
+
+ d1 = pow(e, -1, carmichael(pp, 2, 23))
+ k1 = pow(r1, d1, n)
+
+ d2 = pow(e, -1, carmichael(p, 23))
+ k2 = pow(r2, d2, n2)
+
+ out = decrypt(k1 ^ k2, flag)
+ if b"grey" in out:
+ print(out)
+ break
+
+ io.close()
+
