NumberTheory

Intended solution of waRSAw challenge from InCTF Internationals 2019 tl;dr variant of LSB Oracle Attack on unpadded RSA ...

Challenge Points: 223 Challenge Description: Someone told me not to use DSA, so I came up with this. In this challenge, we are given a script that signs any message given as an input: class PrivateSigningKey: def __init__(self): self.gen = 0x44120dc98545c6d3d81bfc7898983e7b7f6ac8e08d3943af0be7f5d52264abb3775a905e003151ed0631376165b65c8ef72d0b6880da7e4b5e7b833377bb50fde65846426a5bfdc182673b6b2504ebfe0d6bca36338b3a3be334689c1afb17869baeb2b0380351b61555df31f0cda3445bba4023be72a494588d640a9da7bd16L self.q = 0x926c99d24bd4d5b47adb75bd9933de8be5932f4bL self.p = 0x80000000000001cda6f403d8a752a4e7976173ebfcd2acf69a29f4bada1ca3178b56131c2c1f00cf7875a2e7c497b10fea66b26436e40b7b73952081319e26603810a558f871d6d256fddbec5933b77fa7d1d0d75267dcae1f24ea7cc57b3a30f8ea09310772440f016c13e08b56b1196a687d6a5e5de864068f3fd936a361c5L self.key = int(FLAG.encode("hex"), 16) def sign(self, m): def bytes_to_long(b): return long(b.encode("hex"), 16) h = bytes_to_long(sha1(m).digest()) u = bytes_to_long(Random.new().read(20)) assert(bytes_to_long(m) % (self.q - 1) != 0) k = pow(self.gen, u * bytes_to_long(m), self.q) r = pow(self.gen, k, self.p) % self.q s = pow(k, self.q - 2, self.q) * (h + self.key * r) % self.q assert(s != 0) return r, s We will use the notation below to represent the following variables: ...

Challenge Points: Challenge Description: We encrypted our flag, but we lost the keys. Can you help? This was a simple yet a very tricky challenge aimed at testing Number Theory basics. In this challenge we are given a small script: #!/usr/bin/env python3 import os from Crypto.Cipher import AES from Crypto.Hash import SHA256 from Crypto.Util import Counter from Crypto.PublicKey import RSA flag = open('flag.txt', 'rb').read().strip() key = RSA.generate(1024, e=3) open('pubkey.txt', 'w').write(key.publickey().exportKey('PEM').decode() + '\n') open('rsa.enc', 'wb').write(pow(int.from_bytes(flag.ljust(128, b'\0'), 'big'), key.e, key.n).to_bytes(128, 'big')) key = SHA256.new(key.exportKey('DER')).digest() open('aes.enc', 'wb').write(AES.new(key, AES.MODE_CTR, counter=Counter.new(128)).encrypt(flag)) If we analyse the script carefully, we would notice that the same flag is encrypted in two different, independent ways: ...

Challenge Points: 207 Challenge Description: We like the OPEC, but not oily one! This challenge is an Okamoto–Uchiyama cryptosystem. Let us see how encryption/decryption takes place in this public key cryptosystem. Okamoto Uchiyama Cryptosystem 101 Key Generation, Encryption and Decryption take place as follows (pasted from Wikipedia): We will see how the decryption formula gives us the message and hence prove it. We want to prove that: $$\frac{L(C^{p-1}\mod p^2)}{L(g^{p-1}\mod p^2)} = m \mod p$$ where \(L(x) = \frac{x-1}{p}\) ...

Challenge Points: 123 Challenge Description: Uncle Sam needs your help! The given challenge is a Schmidt-Samoa cryptosystem. Let us look at how encryption/decryption takes place in this public key cryptosystem and then move to solving the challenge. Schmidt-Samoa Cryptosystem 101 Two large primes p and q are chosen randomly, and the modulus is calculated: \(N = p*p*q\). The private key is calculated as \(d \equiv e^{-1} \mod lcm(p-1, q-1)\). The modulus is the public key too. Encryption: Message m < N is encrypted as \(enc = m^N \mod N\). Note that, unlike RSA, the encryption exponent and modulus is the same. Decryption: Message m is decrypted as \(m = enc^d \mod (pq)\) The security of this cryptosystem depends on the difficulty of factorisation of N. ...