## Transcribed Text

Problem 3 — RSA primes too close together, 18 marks)
This problem explores a difference of squares approach to factoring an RSA modulus due to
Fermat, and hence also known as Fermat factorization. Fermat’s idea was to attempt to find a
representation of an integer n as a difference of squares n = x
2 − y
2 where 0 < y < x < n, which
would lead to a factorization n = (x + y)(x − y). Of course if x + y = n and x − y = 1, then this
doesn’t help. But if n = pq is an RSA modulus for example, the hope is that
x + y = p , x − y = q
or vice versa; in which case
x =
p + q
2
, y =
p − q
2
.
When p and q are close together, the quantity y is very small compared to x and we will see
that this represents a serious attack on RSA.
Let n = pq with odd primes p, q, and assume without loss of generality that p > q (so y > 0). In
this problem, all square roots are assumed to be positive, i.e. when we write √
z for some z > 0,
we mean the positive square root of z.
(a) (3 marks) Prove that p > x > √
n.
(b) (8 marks) Consider the following algorithm:
Algorithm Fermat Factorization
Input: n = pq with p > q
Output: q
1: Put a = d
√
n e (
√
n rounded up to the nearest integer)
2: b := √
a
2 − n
3: while b is not an integer do
4: a := a + 1; b := √
a
2 − n
5: end while
6: Output a − b.
Prove that this algorithm terminates when a = x and outputs q. Note that there are three
items to show here:
• The “while” clause is satisfied when a = x;
• The algorithm does not terminate sooner, i.e. it does not terminate for any value a < x;
• When the algorithm terminates with a = x, it outputs q.
(c) (2 marks) Show that the number of loop iterations executed by the algorithm is x−d√
ne+1.
(d) (3 marks) Prove that x − d√
ne <
y
2
2
√
n
.
(Hint: Consider (x −
√
n)(x +
√
n).)
(e) (2 marks) Finally, the coup-de-grˆace. Suppose p − q < 2B
√4 n for some integer B that is
very small compared to n; e.g. B could be on the order of a power of log2
(n). In other
words, p and q are very close together; they agree in nearly half of their most significant
bits. Prove that the above algorithm factors n after at most
B2
2
+ 1
loop iterations.
Problem 4 – The El Gamal public key cryptosystem is not semantically secure, 12 marks
This problems requires typesetting Legendre symbols. To facilitate this, include at the
beginning of your assignment file, right after the line \documentclass{assignment} the
two lines
\usepackage{amsmath}
\providecommand{\Leg}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
Be sure that you copy these verbatim; the easiest is to copy and paste them right from
this PDF file. The assignment template provided on the course website already includes
these lines. The command $\Leg{a}{n}$ will produce the typeset output
a
n
, which is
much easier than producing a fraction with large parentheses around it.
Recall that for the El Gamal public key cryptosystem, a user Alice produces her public and
private keys as follows:
Step 1. Selects a large prime p and a primitive root g of p.
Step 2. Randomly selects x such that 0 < x < p − 1 and computes
y ≡ g
x
(mod p).
Alice’s public key: {p, g, y}
Alice’s private key: {x}
To encrypt a message M ∈ Z
∗
p
intended for Alice, Bob selects a random integer k ∈ Zp−1,
computes C1 ≡ g
k
(mod p) and C2 ≡ Myk
(mod p), and sends C = (C1, C2) to Alice.
Alice decrypts the ciphertext C = (C1, C2) by computing C2C
p−1−x
1 ≡ M (mod p).
In this problem, you will prove that the El Gamal PKC is not polynomially secure, and hence
not semantically secure. This is because an attacker Mallory can distinguish messages according
to whether they are quadratic residues or quadratic nonresidues modulo p.
Mallory mounts her attack with the following procedure:
Step 1. Selects two messages M1 and M2 such that M1 ∈ QRp and M2 ∈ QNp,
and obtains ciphertext C = (C1, C2) = E(Mi) where i = 1 or 2
(Mallory’s task is precisely to ascertain whether i = 1 or i = 2).
Step 2. Computes the Legendre symbols
y
p
,
C1
p
and C2
p
Step 3. If
y
p
= 1 and C2
p
= 1, she asserts that C = E(M1).
If
y
p
= 1 and C2
p
= −1, she asserts that C = E(M2).
If
y
p
= −1, C1
p
= 1 and C2
p
= 1, she asserts that C = E(M1).
If
y
p
= −1, C1
p
= 1 and C2
p
= −1, she asserts that = E(M2).
If
y
p
= −1, C1
p
= −1 and C2
p
= 1, she asserts that C = E(M2).
If
y
p
= −1, C1
p
= −1 and C2
p
= −1, she asserts that C = E(M1).
Note that this procedure requires three Legendre symbol computations — which can be done
with modular exponentiation by Euler’s Criterion — and hence always takes polynomial time.
Note also that Mallory states her assertions with certainty, i.e. probability 1.
Prove that Mallory’s assertions are correct, so the El Gamal system is not semantically secure.
Problem 5 — An IND-CPA, but not IND-CCA secure version of RSA, 12 marks
Consider the following semantically secure variant of the RSA public key cryptosystem:
Parameters:
• m — length of plaintext messages to encrypt (in bits)
• (n, e) — Alice’s RSA public key (n has k bits)
• d — Alice’s RSA private key
• H : {0, 1}
k
7→ {0, 1}
m a public random function
Encryption of an m-bit message M:
Step 1. Generate a random k-bit number r < n.
Step 2. Compute C = (sk t) where s ≡ r
e
(mod n) and t = H(r) ⊕ M.
Decryption of ciphertext C:
Compute M ≡ H(s
d
(mod n)) ⊕ t.
Prove that this cryptosystem is not IND-CCA secure.
Hint: To mount her CCA, Mallory gets to choose two plaintexts and submit one ciphertext for
encryption. Almost any two plaintexts M1, M2 will do. Let
C = (sk t) = (r
e
(mod n) k H(r) ⊕ Mi) where i = 1 or 2
be the encryption of one them; Mallory needs to ascertain whether i = 1 or i = 2. Mallaory
now chooses as her ciphertext C
0 = (sk t ⊕ M1) and obtains its decryption (be sure to chose M1
such that C
0 6= C; that’s the only restriction on the plaintexts). Prove that Mallory can with
certainty (i.e. probability 1) and in polynomial time detect whether C is an encryption
Programming Problem
Problem 8 — Secure file transfer with prior key agreement, 37 marks
Don’t be daunted by the long description of this problem! Most of it is very clear specifications,
including those for the autograder, to make your life easier.
Overview. Transport Layer Security (TLS) is a security protocol which aims to provide endto-end communication security over networks. It provides both privacy and data integrity.
While TLS has many steps, our focus will be on the cipher suite, a set of algorithms that add
cryptographic security to a network connection. There are typically four components to a cipher
suite:
• Key Exchange Algorithm
• Authentication algorithm (signature)
• Bulk Encryption Algorithm (block cipher and mode of operation)
• Message Authentication Algorithm
Cipher suites are specified in shorthand by a string such as
SRP-SHA3-256-RSA-AES-256-CBC-SHA3-256.
• This implies SRP-SHA3-256 as the key exchange algorithm, RSA signatures for authentication, AES-256-CBC for encryption and SHA3-256 as the MAC (used as HMAC).
• SRP is the protocol implemented in Assignment 2. Please replace the former hash algorithm
SHA-256 with SHA3-256 (see cryptography library).
• Using SHA3-256 as the MAC implies the use of HMAC with SHA3-256 (see cryptography
library).
In a TLS handshake, upon connection two parties automatically negotiate TLS settings, including the cipher suite to use. Through an exchange of messages the two parties verify each other
and establish a session key. In this assignment, the two parties will be a server and client. The
server will authenticate itself to the client by means of a certificate, and if successful, will derive
a shared session key. The two parties are then able to use the session key to exchange encrypted
and authenticated messages.
In reality, a certificate is an electronic document which contains a public key and information
about the owner of the key. The certificate must be signed by a trusted authority to verify the
8
contents of the certificate. For us, the certificate will merely be a name concatenated with a
public key, concatenated with the signature of a trusted third party (TTP).
Problem specifications. For this assignment, assume that the Client and Server have negotiated SRP-SHA3-256-RSA-AES-256-CBC-SHA3-256 as the TLS cipher suite.2 At a high-level,
your task is to implement a toy version of the TLS handshake using the cipher suite specified
above. The protocol will have two parties a Client and Server, each run by the commands
python3 Client.py filename1 python3 Server.py filename2
where filename1 is the name of a file that will be encrypted and sent to the server and filename2
is the name of the server’s decrypted output file. For testing purposes, we will assume the sent
file is small, i.e. less than 1 MB. Our simplified version of the TLS handshake proceeds as
follows:
(a) The Client first registers itself to the server as in Assignment 2 (see registration step).
(b) The Client sends its username I to the Server.
• First encode I as a byte array in ’utf-8’ format, Ibytes. Then encode the length of Ibytes,
denoted len(I) into a 4-byte array in big-endian. Send the concatenation len(I)|| Ibytes.
(c) The Server sends a certificate consisting of the server’s name and public key as well as a
signature of these two values by a Trusted Third Party (details are described in the next
section).
• The server encodes its name in a byte array S in ‘utf-8’ format.
• Encode the length of S in a 4-byte array len(S) and concatenate it along with the
server’s public key Server PK. Note that the Server’s public key should consist of the
modulus N concatenated with the public exponent e, each encoded as 128-byte bigendian numbers.
• Finally, append the TTP’s signature TTP SIG (obtained at an earlier time) to this
byte array. The signature TTP SIG will be encoded in 128-bytes big-endian. The
Server’s certificate should be of the form len(S)|| S || Server PK || TTP SIG.
• Upon receiving the certificate, the Client should verify the signature of the TTP.
(d) Initiate the SRP protocol from Assignment 2 (the protocol, not the registration) with the
following modifications:
• Instead of the client sending A as plaintext, they will send Enc(A), the RSA encryption
of A under the Server’s public key.
• Upon receiving Enc(A) the server will decrypt to obtain A.
• In case you did not implement the following check in Assignment 2: the server should
ensure that the value A is not congruent to 0 under the SRP modulus and abort
otherwise (it may be fun to think about why).
• The remainder of the protocol proceeds as n Assignment 2 (derive the shared key and
verify).
(e) With the shared key derived, the client encrypts and authenticates the file using the shared
key and the symmetric algorithms specified in the suite (Note, Bob’s protocol from Assignment 1 will help with this).
2With TLS 1.3, there has been a move towards using authenticated encryption schemes such as AES-GCM. For
pedagogical reasons, we will look at a more classic cipher-suite.
9
(f) Have the server decrypt and verify the tag, creating a new file called PTXT that contains
the decrypted message.

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.

import socket

import sys

import os

from numpy import lcm

from Crypto.Random import get_random_bytes

from Crypto.Util import number

from cryptography.hazmat.primitives import hashes

from cryptography.hazmat.backends import default_backend

from sympy import mod_inverse, igcd

# generates secure 512-bit random prime number

def genPrime():

while(True):

x = number.getPrime(511, randfunc = get_random_bytes)

N = 2*x+1

if (number.isPrime(N)):

break

return N

# Converts all numbers from list l to bytes and concats them into the byte string

def numbers2bytes(l):

return b''.join([tobytes(x) for x in l])

def tobytes(x):

if (type(x) == int):

return number.long_to_bytes(x, 128)

else:

return x

# hasing function

def SHA512(bts):

hasher = hashes.Hash(hashes.SHA512(), default_backend())

hasher.update(bts)

return hasher.finalize()

# logging functions

# print values according to the specifications

def log(name, val=None):

if (type(val) == bytes):

val = number.bytes_to_long(val)

if (val != None):

print(f'TTP: {name...