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.