so easy but not rsa

This was my favorite problem, the only one I really liked, even though it was painful to implement. I’ll post the full task code because I thought it was a little clever.

from Crypto.Util.number import bytes_to_long as b2l
from Crypto.Util.number import long_to_bytes as l2b
import random


Zx.<x> = ZZ[]
def convolution(f,g):
  return (f * g) % (x^n-1)

def balancedmod(f,q):
  g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
  return Zx(g)  % (x^n-1)

def randomdpoly(d1, d2):
  result = d1*[1]+d2*[-1]+(n-d1-d2)*[0]
  return Zx(result)

def invertmodprime(f,p):
  T = Zx.change_ring(Integers(p)).quotient(x^n-1)
  return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q):
  assert q.is_power_of(2)
  g = invertmodprime(f,2)
  while True:
  r = balancedmod(convolution(g,f),q)
  if r == 1: return g
  g = balancedmod(convolution(g,2 - r),q)

def keypair():
  while True:
    f = randomdpoly(61, 60)
    f3 = invertmodprime(f,3)
    fq = invertmodpowerof2(f,q)
  except Exception as e:
  g = randomdpoly(20, 20)
  publickey = balancedmod(3 * convolution(fq,g),q)
  secretkey = f
  return publickey, secretkey, g

def encode(val):
  poly = 0
  for i in range(n):
    poly += ((val%3)-1) * (x^i)
    val //= 3
  return poly

def encrypt(message, publickey):
  r = randomdpoly(18, 18)
  return balancedmod(convolution(publickey,r) + encode(message), q)

n, q = 263, 128
publickey, _, _ = key # key = keypair()

flag = b2l(open('flag', 'rb').read())
print(encrypt(flag, publickey))

# generate a lots of random data
data = [ random.getrandbits(240) for _ in range(200)]
for random_msg in data:
  print(l2b(random_msg).hex(), encrypt(random_msg, publickey))

Gawd, it’s painfully obvious to me now, but it took me a good two hours or more before I realized…

For context it’s probably important to note that I didn’t know the cryptosystem (NTRU) as I haven’t been exposed to it before, just heard of it. I didn’t actually learn about NTRU until the next day. At first I had my hands full just exploring (in the REPL) what these strange polynomials were and how they behaved to get a feel for it.

Then I moved on to trying to think of ways for recovering the secret key, some kind of incremental brute force or lattice…? Finally I wanted to incorporate all this extra data we get, the random encryptions. Only then did it dawn on me they were absolutely useless as they didn’t involve the secret key, they’d be equivalent to any data I could generate myself. (If the author wanted to be really sadistic, he’d involve the secret key here somehow, but without any path to recovery, and I’d probably be stuck for way longer.)

Of course. All the polynomials and whatever is irrelevant, it’s just Mersenne untwisting.

So the attack is to recover the MT state from the 240-bit random numbers you get directly from its output. (Each one discards a 16-bit halfword but it’s easily recovered from future numbers.) Once I knew this I actually put it on hold and did other tasks, because I’d have to go digging to recover bits and pieces of code I’ve written before for MT reversing, as it tends to be very bug-prone.

Coming back to it though, there’s the interesting concept of reversing the shuffle in randomdpoly(). I’ve considered making problems involving random.shuffle() before, because it is not injective and discards a nondeterministic amount of information. However I found it was a lot easier than I had previously thought, especially just a single large shuffle like this (I wanted to make a task that involved reversing a lot of small shuffles) since you can sort of bisect the range of numbers it will consume and the correct shuffle was found easily.

I liked this one, cause it almost had me fooled but I still figured it out, so I got that trace amount of dopamine.