CO3326: Plot the SECP256K1 Elliptic Curve and Explain in Simple Terms the Group law for Elliptic Curves: Computer security Assignment, UOL, Singapore

Introduction
Many experts think that the most costly hack to fix is the loss of trust, where the private keys of an organization are leaked. This can compromise all the things that are signed by those keys, including documents and executables.
Imagine if Sony’s private keys were hacked, and we could then not trust any document or executable that was signed by those keys. Hackers could create their own executable (or document) and then sign it with a valid key. There would have to be large-scale revocation, and virtually everything that was associated with Sony’s private keys would have to be re-installed.

This is exactly what happened in 2010. The hacker group fail0Overflow demonstrated that they could break the security methods of the Sony PlayStation 3. They managed to recreate Sony’s private key, and then break the signatures on the hypervisor and on the signed executables. The signatures were based on the Elliptic Curve Digital Signature Algorithm
(ECDSA), but the core problem was related to sloppy coding and oversight of an important requirement within the signing process. ECDSA, which uses Elliptic Curve Cryptography (ECC), has been widely used in TLS, PGP, and SSH, which are three of the main technologies on which modern Web security is based. It is also widely used in Bitcoin and other cryptocurrencies.

Part A – Exercise
You have been provided with the public key of a fictive person – Alice – and a list of intercepted messages, in a format that looks like the following (this is an example for illustration):

It is in JSON format. The srn and name fields should correspond to your details and are there for marking purposes. Under Alice, you find Alice’s public key, which is a point on the SECP256K1 elliptic curve over the field Fp. The curve and field parameters are available here:  p is the field characteristic, a and b are the curve coeÿcients (E: y2 = x3 + ax + b), g is the base point and n is the subgroup order.

The signed messages are a list of intercepted messages containing the plain text and the ECDSA signature. The hash function used for the signature is SHA-256, which you are already familiar with from coursework assignment 1.

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 helper to double-check your hashing and
string to number encoding:

• http://foley.gold.ac.uk/cw21/api/hash?text=introduce
• http://foley.gold.ac.uk/cw21/api/encode?hash=0fee7196f6817d6f81e75c
  ac8e2d3d0b11987caa6b71d91d0657b638b093f54b

obviously, by replacing introduce or 0fee7196f6817d6f81e75cac8e 2d3d0b119 87caa6b71d91d0657b638b093f54b in the URL with the text or hash you want to encode.

Step 1
The first part of the exercise requires you to filter the messages based on whether they verify against ECDSA over the SECP256K1 elliptic curve described above, and only include in the solutions those messages that do. You only need Alice’s public key to do this. For the sample exercise above, the solution is.  Note that introduce and reflect (among other words) are in the solution as their signatures verify against Alice’s public key but alleged and prevent (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 five texts:
Neal Koblitz
Victor Miller
Taher Elgamal
Whitfield Diffie
Martin Hellman
By looking carefully at the verified messages you identify in Step 1, you will realize that the same mistake has been made that happened at Sony when a few of the messages were signed. This will allow you to find the private key, and thus produce counterfeit signatures. Make sure that you do not make the same mistake when you produce counterfeit signatures.

Part B – Report
Please answer the questions briefly 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. To answer the questions below, for
explanations please use the key – Alice’s – and the signed messages you have been given for the exercise.
Question 1
Plot the SECP256K1 elliptic curve and explain in simple terms the group law for elliptic curves.
Question 2
Demonstrate geometric addition and scalar multiplication with arbitrary points on the curve.
Question 3
Explain in simple terms, using your own words, how elliptic curves are restricted to a finite prime field Fp.
Question 4
Demonstrate, with the aid of an example, geometric addition and scalar multiplication over the prime field Fp.
Question 5
In the ECC context explain, using your own words, what the easy problem is, and what seems to be the hard problem. How do you generate a private and public key pair?

Question 6
State, with the appropriate formulae, how you sign a message and demonstrate it with one of the messages you have been given.
Question 7
State, with the appropriate formulae, how you verify a signature and demonstrate it with one of the messages you have been given against Alice’s public key.
Question 8
How do you interpret the following joke that circulated after the Sony security
breach, and what is the main takeaway in regard to ECDSA? public int get random number() {
return 4; // chosen by fair dice roll
// guaranteed to be random
}
Question 9
Explain, with an example from the exercise and with the appropriate formulae,
how you managed to revert the private key.
Question 10
Briefly – in one paragraph – describe the design of your code. Attach the
implementation of the signature, verification, and private key hacking methods. Don’t forget to acknowledge any code re-use.