All programs (C++ and/or Python) has to be executable on Linux Debian (Ubuntu
18) shell.

1. The following question concerns the group ℤ55: a. How many elements are there in this group? b. Define f3:ℤ55→ℤ*55by f3(x)=[x3mod 55].Compute f3(8).
   c. What function is the inverse of f3(i.e fk(y)=x for every y = f3(x)mod 55)?
   d. Find x such that f3(x)=3
2. The following questions concern the group ℤ*23
   a. How many elements are there in this group?
   b. Find a generator of this group.
   c. Find an element of this group (besides the identity) that is not a generator.
   d. Two parties run the Diffie-Helman protocol using this group and g=4. Say Alice
   chooses x=10 and Bob chooses y=6. What are the messages sent in this execution
   of the protocol, and what is the key that the parties compute?
3. Twotime pads. A one-time pad is unbreakable crypto, but what happens if you
   reuse the pad? Solve the two time problem. HINT: This is a test of the Emergency
   Broadcast System.
   There is a crypto service running at IP:port. The flag is the encryption key. Write a C++ and/or
   Python program to retrieve the encryption key.
4. ECB. Why is it bad to use ECB mode with block cryptography? Solve the ECB
   problem.
   There is a crypto service running at IP:port. We were able to recover the source code:
   Hint: Why should you never use ECB mode?

!/usr/bin/python2

import os
import json
import sys
import time
from Crypto.Cipher import AES
cookiefile = open(“cookie”, “r”).read().strip()
flag = open(“flag”, “r”).read().strip()
key = open(“key”, “r”).read().strip()
welcome = “””
Welcome to ECB Secure Encryption Service version 1.25
“””
def encrypt(m):
cipher = AES.new(key.decode(‘hex’), AES.MODE_ECB)
return cipher.encrypt(m).encode(“hex”)
def decrypt(m):
cipher = AES.new(key.decode(‘hex’), AES.MODE_ECB)
return cipher.decrypt(m.decode(“hex”))

flush output immediately

sys.stdout = os.fdopen(sys.stdout.fileno(), ‘w’, 0)
print welcome
print len(cookiefile)
print “Here is an admin cookie: ” + encrypt(cookiefile)
print “But here is yours: ” + encrypt(“I am not an administrator. This cookie expires
2020-01-01…….”)

Get their cookie

print “What is your cookie?”
cookie2 = sys.stdin.readline()

decrypt, but remove the trailing newline first

cookie2decoded = decrypt(cookie2[:-1])
print cookie2decoded
if cookie2decoded.startswith(“I am yes an admin”):
exptime=time.strptime(cookie2decoded[47:57],”%Y-%m-%d”)
if exptime > time.localtime():
print “Cookie is not expired”
print “The flag is: ” + flag
else:
print “Cookie is expired”
else:
print “No flag for you!”

5. RSA. RSA public key cryptography depends on it being computationally hard to
   factor the product of two large primes. What happens if you can make the search
   space a lot smaller? In this example, you know that your target has used adjacent
   primes. Solve the RSA problem.
   HINT: Any library that finds the next prime can be helpful. E.g., code at:
   https://codegolf.stackexchange.com/questions/10701/fastest-code-to-find-the-nextprime.
   HINT: How can you lower your search space knowing the primes are adjacent?
   There is a crypto service running at IP:port. We were able to recover the source code as below. We
   have learned that the author chose adjacent primes for the RSA key. The answer will be 32 hex
   digits, all lowercase, obtained by decrypting the ciphertext and converting to hexadecimal.

!/usr/bin/python2

import os
import json
import sys
import time
from Crypto.PublicKey import RSA
prime1 = int(open(“prime1”, “r”).read().strip())
prime2 = int(open(“prime2”, “r”).read().strip())
flag = open(“flag”, “r”).read().strip()
welcome = “””
Welcome to Secure Encryption Service version 1.1
“””

egcd copied from

https://stackoverflow.com/questions/4798654/modular-multiplicative-inversefunction-in-python

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x – (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception(‘modular inverse does not exist’)
else:
return x % m

flush output immediately

sys.stdout = os.fdopen(sys.stdout.fileno(), ‘w’, 0)
print welcome
n=prime1prime2 e=65537L d=modinv(e,(prime1-1)(prime2-1))
key=RSA.construct((n,e,d,prime1,prime2))
plain=long(flag,16)
print “The public key is (“+str(e)+”,”+str(n)+”)”
print “The encrypted flag is ” + str(key.encrypt(plain,””))

6. Padding attacks. In this problem, you show how deterministic padding can be
   used to generate an oracle attack that totally breaks otherwise unbreakable AES
   encryption!
7. PCKS7
   There is a crypto service running at IP:port. We were able to recover the source code:
   HINT: Look up padding oracle attack on Wikipedia

!/usr/bin/python2

import os
import json
import sys
import time
from Crypto.Cipher import AES
cookiefile = open(“cookie”, “r”).read().strip()
flag = open(“flag”, “r”).read().strip()
key = open(“key”, “r”).read().strip()
welcome = “””
Welcome to Secure Encryption Service version 1.20
“””
def pad(s):
return s + (16 – len(s) % 16) * chr(16 – len(s) % 16)
def isvalidpad(s):
return ord(s[-1])*s[-1:]==s[-ord(s[-1]):]
def unpad(s):
return s[:-ord(s[len(s)-1:])]
def encrypt(m):
IV=”This is an IV456″
cipher = AES.new(key.decode(‘hex’), AES.MODE_CBC, IV)
return IV.encode(“hex”)+cipher.encrypt(pad(m)).encode(“hex”)
def decrypt(m):
cipher = AES.new(key.decode(‘hex’), AES.MODE_CBC, m[0:32].decode(“hex”))
return cipher.decrypt(m[32:].decode(“hex”))

flush output immediately

sys.stdout = os.fdopen(sys.stdout.fileno(), ‘w’, 0)
print welcome
print “Here is a sample cookie: ” + encrypt(cookiefile)

Get their cookie

print “What is your cookie?”
cookie2 = sys.stdin.readline()

decrypt, but remove the trailing newline first

cookie2decoded = decrypt(cookie2[:-1])
if isvalidpad(cookie2decoded):
d=json.loads(unpad(cookie2decoded))
print “username: ” + d[“username”]
print “Admin? ” + d[“is_admin”]
exptime=time.strptime(d[“expires”],”%Y-%m-%d”)
if exptime > time.localtime():
print “Cookie is not expired”
else:
print “Cookie is expired”
if d[“is_admin”]==”true” and exptime > time.localtime():
print “The flag is: ” + flag
else:
print “invalid padding”