University of London
Computing and Information Systems/Creative
Computing
CO3326 Computer security
Coursework assignment 1 2022–2023
Important
Each student has been allocated a unique public 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/cw1/{srn}. For example, if your SRN is 887766554, you would obtain your data from http://foley.gold.ac.uk/cw23/api/cw1/ 887766554. If you have difculties obtaining your data, please email us at: intcomp@gold.ac.uk
Introduction
This coursework assignment is designed to extend your knowledge in the area of digital signature schemes by encouraging self-study and creativity. More specifcally, you will be working with the El Gamal signature scheme, large primes and linear congruences by taking a practical example. Chapter 9 (pages 95-104) of the subject guide, including the suggested supplementary reading, is a good starting point to familiarise yourself with the El Gamal encryption scheme, the notation, and the mathematical principles. Building on this, you need to research the El Gamal signature scheme and how you can exploit a simple mistake to recover the private key.
Through a practical exercise, this coursework assignment requires you to verify a few messages that have been signed by a fctive Alice using the El Gamal signature scheme. Due to sloppy coding, rather than using a unique k for each signature, she has reused one k value across several messages.
Exploiting this, you can perform a same-k attack, allowing you to recover Alice’s private key. You will then be able to impersonate Alice by signing a few messages on her behalf. The internet has plenty of information on the subject, so you will not fnd it difcult to read up on the following topics:
• El Gamal signature scheme.
• Same-k attack.
• Linear congruence.
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 key of a fctive person – Alice – and a list of intercepted messages, in a format that looks like the following (this is an example for illustration): http://foley.gold.ac.uk/cw23/api/cw1/88776655
4.
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 a key, which is Alice’s public key. The key conforms to the El Gamal signature scheme, so it consists of a prime number p, a corresponding generator g and a public key pk (from public key).
The intercepted is a list of intercepted messages containing the plain text and the El Gamal signature. The hash function used for the signature is SHA-256.
For example, if you look at the message corresponding to providence in Carl
Davis’s assignment, providence is frst hashed to bae3632ffa8b538a0930a41 0b2607cdba6bf8354798655a4fc925af32ef085d6. This is then transformed to an integer: 515260227954214640070896060773998611699728261769405203180
834037179424846748423265479265106973181080273460993475850979391190 2924767267144784680717959652406, which is then used with the El Gamal signature scheme to produce the signature, which is the (r, s) pair.
If you use Java, you can use Apache Commons Codec to obtain the hash with the following code:
public String hash(final String text) { return DigestUtils.sha256Hex(text);
}
Furthermore, you can rely on the following code to transform a string to a number:
public BigInteger encode(final String text) { return new BigInteger(text.getBytes(StandardCharsets.UTF_8));
}
You can also use the following web helpers to double-check your hashing and string to number encoding:
• http://foley.gold.ac.uk/cw23/api/hash?text=providence
• http://foley.gold.ac.uk/cw23/api/encode?hash=bae3632ffa8b538a0930a4
10b2607cdba6bf8354798655a4fc925af32ef085d6
Simply replace providence or bae3632ffa8b538a0930a410b2607cdba6b f8354798655a4fc925af32ef085d6 in the URL with the text or hash you want to check.
Note: for simplicity, all numbers in all JSON references throughout this coursework assignment are given and expected as decimal integers written as strings (i.e. integers between double quotes).
Step 1
The frst part of the exercise requires you to flter the messages based on whether they verify against the El Gamal signature scheme, and only include in the solutions those messages that do. You only need Alice’s public key to do this. The solution is expected to be included under a solution hash, which is expected to be on the same level as the exercise hash. Include the verifed messages under an intercepted hash in the solution. For the sample exercise above, the correct solution is: http://foley.gold.ac.uk/cw2
3/CarlDavis_887766554_CO3326cw1.json. Note that providence and laboratory (among other words) are in the solution as their signatures verify against Alice’s public key, but vegetarian and television (among other words) are not, as their signatures do not verify.
Step 2
The second part of the exercise requires you to impersonate Alice and sign on her behalf the following four texts using the El Gamal signature scheme:
data confidentiality data integrity authentication non-repudiation
By looking carefully at the verifed messages you identify in Step 1, you will realise that rather than using a unique k for each signature, one k has been reused, which allows you to perform a same-k attack. This will allow you to fnd the private key, and thus produce counterfeit signatures. Make sure that you do not make the same mistake when you produce the counterfeit signatures. Include the private key in the key hash under the solution as sk (from secret key) next to p, g and pk. Include the list of impersonated messages under an impersonated hash on the same level as the intercepted hash.
You can see in the sample solution the signatures for the required four plain texts. Do not get distracted by the blank space or the hyphen in the texts. Once you hash them, and subsequently encode them, these do not make any diference. For example, data confidentiality hashes to
d02f03b38f33eca138eacf5b2f01a63aaef2bb4ba6b31cb1ec6fec49b92ccd0c, which is then encoded as 5247285421845087059140387699923700103986285229
205296479476138331600546258380271833856861742724101495518137268812 152047708294477265904690099019107925241955. You can use the web helpers to check:
• http://foley.gold.ac.uk/cw23/api/hash?text=data%20confdentiality
• http://foley.gold.ac.uk/cw23/api/encode?hash=d02f03b38f33eca138eacf 5b2f01a63aaef2bb4ba6b31cb1ec6fec49b92ccd0c
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 will not get you very far. Your explanations should use Alice’s key and the signed messages you have been given for the exercise.
Question 1
Using Fermat’s little theorem, show that 17616640590392624387 is a prime number. Explain briefy the heuristic you use.
Question 2
Show that 2 is a generator for prime 17616640590392624387 in the context of the El Gamal signature scheme.
Question 3
Explain in simple terms, using an example from the messages you have been given, how messages are signed using the El Gamal signature scheme.
Question 4
Show how a signature produced with the El Gamal signature scheme can be verifed. Use an example from the messages that you have been given.
Question 5
Show the correctness of the scheme in the sense that a signature generated with the El Gamal signing algorithm can be checked by a verifer.
Question 6
Find integer x such that 2491773869989059992 x = 4564732769545516204 (mod 17616640590392624386). Show your working.
Question 7
Explain how you fnd the solutions of the linear congruence equation: a x = b (mod n), where a, b and n are given integers and x is an unknown integer.
Question 8
Show that where Alice uses the same value of k to sign two diferent messages m1 and m2, using the El Gamal signature scheme, you can recover the value
of k. Show how once having k you can recover Alice’s private key.
Question 9
Explain step-by-step, using messages that you have been given, and with the appropriate formulae, how you recover Alice’s private key. Show all your working. State the linear congruence equations that you have to solve and explain how you select the right solution.
Question 10
Briefy – in one paragraph – describe the design of your code. Attach the implementation of the signature, verifcation, linear congruence and private key hacking methods. Don’t forget to acknowledge any code re-use.
Question 11
Explain briefy, in your own words, what the implications are if you manage to hack an institution’s private key.
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.
Submission requirements
You should upload two single fles only. These must not be placed in a folder, zipped, etc.
The report should be submitted as a PDF document using the fle naming conventions below: YourName_SRN_COxxxcw#.pdf, for example
CarlDavis_887766554_CO3326cw1.pdf. YourName is your full name as it appears on your student record (check your student portal), SRN is your
Student Reference Number, for example 887766554, COXXXX is the course number, for example CO3326, and cw# is either cw1 (coursework 1) or cw2 (coursework 2).
The exercise should be submitted as a JSON fle with a strict format and naming scheme. The exercise will be automatically checked by an algorithm,
so pay particular attention to its format. The name of the fle should be
YourName_{srn}_CO3326cw1.json; for example, Carl Davis with SRN 887766554 would submit CarlDavis_887766554_CO3326cw1.json.
Note: as the JSON is evaluated by an algorithm, every quote, comma, colon, curly brace upper/lower case is crucial. Please pay attention to these, and check your JSON very carefully against the sample solution provided.
It would be a shame to lose a potential 50% of the total marks for this coursework assignment because of a misplaced comma or a missing quote, etc. There are also online tools you can use for JSON formatting and validation, for example https://jsonformatter.curiousconcept.com/, so double-check that your JSON is syntactically correct.
[END OF COURSEWORK ASSIGNMENT 1]