CO3326 Computer security

Coursework assignment 2 2022–2023

Important

Each student has been allocated a unique key and sequence of messages to use for this coursework assignment. You can obtain yours using your Student Reference Number (SRN) from the following URL:

foley.gold.ac.uk/cw23/api/cw2/{srn}. For example, if your SRN is 887766554, you would obtain your data from http://foley.gold.ac.uk/cw23/   api/cw2/887766554. If you have difculties obtaining your data, please email us at: [email protected]

Introduction

You may have noticed that recently there has been a buzz around quantum   computing. It probably ranks only below AI in terms of hype. One of the best known theoretical applications of quantum computers is that they can solve the hard problem of fnding the prime factors of large numbers exponentially faster than classical computers. As a result, a few encryption   schemes, referred to as post-quantum encryption schemes, such as lattice- based encryption, are receiving more attention. Unlike more widely used and known public-key schemes such as the RSA, Dife-Hellman or elliptic-curve   cryptosystems – which could, theoretically, be defeated using Shor’s algorithm on a quantum computer – some lattice-based constructions appear to be resistant to attack by both classical and quantum computers.

This coursework assignment is designed to extend your knowledge in the area of lattice-based cryptography by encouraging self-study and creativity. More specifcally, you will be working with a lattice-based public-key encryption     scheme that is based on the Learning with Errors problem (LWE). Through a practical exercise, this coursework assignment requires you to understand      key generation, and perform encryption and decryption with a given key.       The internet has plenty of information on the subject, so you will not fnd     it difcult to read up on the following topics:

• Lattice-based cryptography.

• Learning with Errors.

The coursework assignment is composed of two parts, an exercise and a report. Each part carries 50 marks (total 100 marks). For the exercise you   should check a list of intercepted messages which were signed by Alice, and    then impersonate Alice by signing a list of subsequent messages on her behalf. For the report you should answer the questions laid out below. They are

designed to lead you through the key considerations for the exercise.                 To solve the exercise, you may fnd it necessary to write a program. You        are welcome to use any programming language and any third-party libraries   available for SHA-256 and JSON. Libraries are available for most languages,  including – and not limited to – Java, C/C++, Scala, Python, JavaScript, etc. Please include key snippets of your code as an annex to your report.                 You should read the coursework assignment carefully and pay particular         attention to the submission requirements.

Part A – Exercise

You have been provided with the public and private key of a fctive person – Alice – , a ciphertext and a plaintext, in a format that looks like the following (this is an example for illustration): http://foley.gold.ac.uk/cw23/api/cw2/

887766554.

It is in JSON format. The srn and name felds should correspond to your      details and are there for marking purposes. Under the exercise hash you     fnd an alice hash, which is Alice’s key. The key conforms to a lattice-based public-key encryption scheme referred to as Learning with Errors (LWE), so it consists of a matrix a with n rows and m columns, whose entries are drawn uniformly at random from the space of integers modulo q, the private key sk (from secret key) is a vector of length m, the error e is a vector of length n    and the public key pk (from public key) is a vector of length n.

The messages hash under the exercise is a list of two messages, each     of which is supposed to be a pair consisting of a plaintext (text) and       a corresponding ciphertext (cipher), but only one half is given in each     message. The frst message has only the cipher, which is a list of (u,      v) pairs, where u is a vector of length m and v is an integer smaller           than q. The exercise requires you to use Alice’s key to decrypt the           ciphertext to obtain the corresponding plaintext (text). The second        message has only the plaintext (text). The exercise requires you to          use Alice’s key to encrypt the plaintext to obtain the corresponding         ciphertext (cipher). The complete two messages, with both text and      cipher, should be included in a list under a messages hash, which should be included under a solution hash that is to be on the same level as       the exercise hash. For the sample exercise above, a correct solution is:

http://foley.gold.ac.uk/cw23/CarlDavis_887766554_CO3326cw2.json. Note that both plaintexts are English dictionary words (game and node).                In order to be able to encrypt a plaintext message with the lattice-based encryption scheme, you will have to encode the string as a bit stream             and encrypt it one bit at a time. For example, game encodes as 01100111       01100001  01101101  01100101 and node as 01101110  01101111  01100100     01100101. As both plaintexts encode as arrays of 32 bits, the ciphertext is an array of (u,  v) pairs of length 32. Similarly, once you decrypt the ciphertext, you will obtain a bit stream that will need to be decoded in order to obtain   back the original plaintext. There are online tools where you can double-check that your encoding/decoding is correct, for example this. You can also use the following web helpers to double-check your encoding and decoding:

• http://foley.gold.ac.uk/cw23/api/toBinary?text=game

• http://foley.gold.ac.uk/cw23/api/toString?binary=01100111011000010110 110101100101

Simply replace game or 01100111011000010110110101100101 in the URL with the string or binary you want to check.

You will realise during your research that there are many possible correct    encryptions, as the encryption involves random sampling of a for each bit    of the encoded plaintext, but you can double-check that your encryption is  correct by being able to decrypt the ciphertext with Alice’s key and retrieve the plaintext you started with.

Part B – Report

Please answer the questions briefy and in your own words. Use diagrams      where possible and explain them. Copy-pasting Wikipedia articles or verbose explanations from ChatGPT will not get you very far. Your explanations      should use Alice’s key and the messages you have been given for the exercise. The context of the questions is public key encryption with Learning with       Errors (LWE).

Question 1

Explain how to generate the public and private keys. Show the formulae and use the key you have been given as an example for the explanation.

Question 2

Explain how to encrypt a 1-bit message. Show the formulae and use the key you have been given as an example for the explanation.

Question 3

Explain how to decrypt a 1-bit message. Show the formulae and use the key you have been given as an example for the explanation.

Question 4

Explain briefy and with the appropriate formulae why the decryption works. State explicitly the conditions that are necessary for the scheme to work.

Question 5

Explain briefy how to encode the plaintext as a bit stream. Include the relevant code snippet.

Question 6

Explain briefy how to decode the bit stream to obtain the plaintext. Include the relevant code snippet.

Question 7

Explain in your own words what is meant by the LWE problem.

Question 8

What are the typical dimensions of the key in real life that make the LWE scheme cryptographically strong?

Question 9

Describe briefy one of the advantages of the LWE encryption scheme as compared to the RSA scheme, other than it being resistant to attacks by quantum algorithms.

Question 10

Explain briefy how big a quantum machine is necessary for it to really be a threat to RSA-2048. State roughly how big the current – publicly known –  quantum machines are.

Question 11

Briefy – in one paragraph – describe the design of your code. Attach the   implementation of the encryption and decryption methods. Don’t forget to acknowledge any code re-use.

Reminder:   do not forget to acknowledge all sources. Make sure you           acknowledge any code re-use. It is important that your submitted coursework assignment is your own individual work and, for the most part, written in     your own words. You must provide appropriate in-text citation for both        paraphrase and quotation, with a detailed reference section at the end of       your assignment (this should not be included in the word count). Copying, plagiarism, unaccredited and/or wholesale reproduction of material from       books or from any online source is unacceptable, and will be penalised (see:   How to avoid plagiarism). You may fnd it helpful to look at the end of some journal or conference papers to get an idea of how to list your reference         material appropriately. The Harvard Referencing Guide provides a short       explanatory introduction and a checklist of examples, showing how to cite and reference material from various sources.