NumberTheory

Challenge Points: 303 Challenge is running on the service: nc 47.75.39.249 23333 After surpassing the Proof of Work, we get the following challenge: On selecting the option get code, we get the following code that is being used for encryption: #!/usr/bin/env python3 # -*- coding=utf-8 -*- from Crypto.Util.number import getPrime, GCD, bytes_to_long from hashlib import sha256 import random import signal import sys, os signal.alarm(20) m = b"xxxxxxxxxxxxxx" n = 21727106551797231400330796721401157037131178503238742210927927256416073956351568958100038047053002307191569558524956627892618119799679572039939819410371609015002302388267502253326720505214690802942662248282638776986759094777991439524946955458393011802700815763494042802326575866088840712980094975335414387283865492939790773300256234946983831571957038601270911425008907130353723909371646714722730577923843205527739734035515152341673364211058969041089741946974118237091455770042750971424415176552479618605177552145594339271192853653120859740022742221562438237923294609436512995857399568803043924319953346241964071252941 e = 3 def proof(): strings = "abcdefghijklmnopqrstuvwxyzWOERFJASKL" prefix = "".join(random.sample(strings, 6)) starwith = str(random.randint(10000, 99999)) pf = """ sha256("%s"+str).hexdigest().startswith("%s") == True Please give me str """%(prefix, starwith) print(pf) s = input().strip() if sha256((prefix+s).encode()).hexdigest().startswith(starwith): return True else: return False def cmd(): help = """ 1. get code 2. get flag Please tell me, what you want? """ while True: print(help) c = input().strip() if c == "1": return True elif c == "2": return False else: print("Enter Error!") def main(): if not proof(): print("Check Failed!") return welcom() if cmd(): f = open("file.py") print(f.read()) return mm = bytes_to_long(m) assert pow(mm, e) != pow(mm, e, n) sys.stdout.write("Please give me a padding: ") padding = input().strip() padding = int(sha256(padding.encode()).hexdigest(),16) c = pow(mm+padding, e, n) print("Your Ciphertext is: %s"%c) if __name__ == '__main__': main() Upon selecting the get flag option, the following computation is done: $$c \equiv (flag + sha256(input))^3\mod n$$ where input is an input string that we give to the server, sha256() is a function that generates integer representation of SHA-256 hash of the input and c is the corresponding ciphertext. ...

Challenge Points: 100 We are given an encryption script simple.py: Other than the ciphertext, values of n, g, h are also public. The following function is used to generate values for the challenge: def generate(nbits): p = getPrime(nbits) q = getPrime(nbits) n = p * q * p g = random.randint(1, n) h = pow(g, n, n) return (n, g, h) The encryption function: def encrypt(m, n, g, h): r = random.randint(1, n) c = pow(pow(g, m, n) * pow(h, r, n), 1, n) return c As we can see, the ciphertext for each character in the plaintext is generated separately. For \(i^{th}\) byte of message we can write the corresponding ciphertext as: $$c_i \equiv ((g^{m_i}\mod n) * (h^r\mod n)) \mod n$$ Given: \(h \equiv g^n \mod n\). We can now write: $$c_i \equiv ((g^{m_i}\mod n) * (g^{nr}\mod n)) \mod n$$ $$\implies c_i \equiv g^{m_i + nr}\mod n$$ ...

Challenge Points: 349 The idea behind the challenge involved knowledge of basic Number Theory which was pretty cool! We are given an encryption script and public key parameters that are used for encrypting a message. Everything in the script works normally except the GenerateKeys function: def GenerateKeys(p, q): e = 65537 n = p * q pi_n = (p-1)*(q-1) d = mulinv(e, pi_n) h = (d+p)^(d-p) g = d*(p-0xdeadbeef) return [e, n, h, g] There is are two extra variables other than the regular public key parameters whose values are known: g and h ...

Challenge Points: 158 Ciphertext is generated as following: def encrypt(nbit, msg): msg = bytes_to_long(msg) p = getPrime(nbit) q = getPrime(nbit) n = p*q s = getPrime(4) enc = pow(n+1, msg, n**(s+1)) return n, enc We have: \((n+1)^{msg}\mod n^{s+1}\) Expanding the above equation Binomially, we get: $$\binom{msg}{0}n^{msg} + \binom{msg}{1}n^{msg-1} + \binom{msg}{2}n^{msg-2} + … + \binom{msg}{msg-1}n + \binom{msg}{msg}n^0$$ $$(\binom{msg}{0}n^{msg-2} + \binom{msg}{1}n^{msg-3} + … + \binom{msg}{2})n^2 + \binom{msg}{msg-1}n + \binom{msg}{msg}n^0$$ This can be written as: \((x)n^2 + mn + 1\), where $$x = \binom{msg}{0}n^{msg-2} + \binom{msg}{1}n^{msg-3} + … + \binom{msg}{2}$$ ...

Challenge Points: 50(+100) Challenge Description: Hey there fellow lizard how nice of you to drop by! Did you know those filthy humans really think that some numbers have special meanings? Seven, 13 and for some strange reason even 9000. Go and show them that a good prime does not make a secure cryptosystem! Given encryption script: g = 5 d = key m = int(flag.encode('hex'), 16) % p B = pow(g, d, p) # Equation-1 k = pow(A, d, p) # Equation-2 c = k * m % p # Equation-3 Values p, A, g, B, c are known. Prerequisites: ...