Requirements

• Part A will contain the number of points for Student's answers to the final test questions.
• Part B will contain the number of points gathered by the Student during the course of the exercises.

• Path.1: The Student decided not to take the test. Then I acknowledge that Student's knowledge of the subject is correctly reflected by the points gathered by the Student during the course of the exercises. Therefore formally, for Part A I set Student's number of points from part B, and the formula above for the final score is equivalent to:
  
  100%*(Student's number of points from part B)
  Then Student's global score is translated to the grade according to the assignments below.
• Path.2: The Student takes the test. By opening the test form the Student rejects the possibility of choosing Path.1. In such a case the usual rules apply.

• 2 for the final score in the interval [0,40)
• 3 for the final score in the interval [40,60)
• 3+ for the final score in the interval [60,70)
• 4 for the final score in the interval [70,80)
• 4+ for the final score in the interval [80,90)
• 5 for the final score in the interval [90,100]
• 5+ for the global score > 100

The Test

• The scope of the material for the test is the material presented during the lectures.
• The maximum number of points for the test (Part A above) is 100 pts.
• The opportunity to take the test will be available during the last exercises. That is on 09.06.2022, 7:30-9:00, Room 3, Building C-5

Lectures

Program of lectures

• Field characteristic and short Weierstrass form.
• Addition and doubling formulas.
• Point compression and square root algorithms for prime fields.
• Hasse theorem, what co-factor means.
• ECDSA, ECDH.
• Different coordinate systems: projective, jacobian, ... - cf. Explicit-Formulas Database for EC point addition and doubling
• Fast arithmetic for a fixed base - the comb method (Lim/Lee algorithm) and a follow up paper "Improving and Extending the Lim/Lee Exponentiation Algorithm".
• Projective coordinates leak (cf. also the paper From A to Z: Projective coordinates leakage in the wild)
• Montgomery Ladder - timing resistance.
• Why brainpool curves are better than NIST ones? Some fault attack and twisted curves - cf. the two papers:
  • Improved Elliptic Curve Multiplication Methods Resistant against Side Channel Attacks
  • Fault Attack on Elliptic Curve with Montgomery Ladder Implementation
• Montgomery curves.
• Twisted Edwards curves.
• EdDSA
• Pairing (if time permits :)

The lectures

• Lecture 1, for the birthday paradox - see e.g. Theorem 10.1 in lecture notes by Andrew Sutherland
• Lecture 2
• Lecture 3
• Lecture 4
• Lecture 5
• Lecture 6
• Lecture 7
• Lecture 8, and for those who are interested: my handwritten notes - derivation of point addition and point doubling formulas in Jacobian and Chudnovsky coordinates
• Lecture 9
• Lecture 10 and some notes on optimization of the comb method for elliptic curves in the mbedtls library
• Lecture 11
• Lecture 12, for consequences of small leakage in the ephemeral keys of ECDSA signatures see e.g., the paper "LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage"
• Lecture 13
• Lecture 14
• Lecture 15, and for those who are interested: my handwritten notes covering the topic in more detail

Literature

• Neal Koblitz: A Course in Number Theory and Cryptography
• Andreas Enge: Elliptic Curves and Their Applications to Cryptography
• Darrel Hankerson, Alfred J.Menezes, Scott Vanstone: Guide to Elliptic Curve Cryptography

Exercises

Some notes

• Definition of a field
• Elliptic curve equation - the criterion for multiple roots
• How to generate instance to L1
• How to generate instance to L2
• Why ord(g̃) is p̃
• Point addition and doubling in projective coordinates
• List 4: why the hare finds a difficulty in catching the turtle when projective coordinates are used

Lists of tasks:

• If you could not present the solution during the deadline-class then, to preserve the deadline, please e-mail me the solution or the value.
  of its hash (I do not accept logs provided by git and in general by any revision control system).
  The solution you have e-mailed will be evaluated when we meet.
• Any delay that is no longer than a week is counted as a week of delay.
• The consequence for a week of delay is the loss of 50% of the maximum number of points from the list.
• If more than one week of delay has passed then it is counted as two weeks of delay and it means that the score for that list is 0 pts.
• In one of the lists below one of the tasks is wrongly constructed. This is done on purpose. For a report explaining what is overlooked in the task, and why exactly the expected solution behaves in such unexpected way you may score 20 additional points (beyond the 100-point pool). The deadline for the report is the same as for the original task.

1. List 1, deadline: the third fourth exercises
2. List 2 and the script ec-prime-order.sage, deadline: the fifth sixth exercises
3. List 3, deadline: the eighth exercises
4. List 4, deadline: the tenth eleventh exercises
5. List 5, deadline: the twelfth exercises
6. List 6, deadline: the fourteenth exercises