1 of 59

Elliptic curve cryptography

2 of 59

What is an elliptic curve?*

*there are other types

Weierstrass form

3 of 59

4 of 59

No singular curves

5 of 59

What is an elliptic curve?

6 of 59

Point addition

7 of 59

8 of 59

Back to real life. Finite fields

Division

​

Curve equation

​

9 of 59

10 of 59

11 of 59

12 of 59

Point scalar multiplication

13 of 59

How to find the number of points on the curve?

14 of 59

How to find the number of points on the curve?

​

Schoof’s algorithm

15 of 59

What is an elliptic curve system? 2.0

It is a cyclic subgroup defined over some elliptic curve.

Its order is n.

It has a base point G, also called generator.

Cofactor h=N/n is always integer.

​

​

16 of 59

Cyclic subgroup

If we add P to itself multiple times, we will eventually result in zero (infinity) element.

​

P(3,6) - subgroup base point or generator

​

​

k = order of this subgroup or order of P

17 of 59

Order of P is the smallest integer n <= N such as n*P=0

18 of 59

How to generate subgroup?

  1. Calculate the order N of the elliptic curve.
  2. Choose the order n of the subgroup. For the algorithm to work, this number must be prime and must be a divisor of N.
  3. Compute the cofactor h = N/n.
  4. Choose a random point on the curve P.
  5. Compute G=hP.
  6. If G is 0, then go back to step 4. Otherwise we have found a generator G of a subgroup with order n and cofactor h.

19 of 59

Summary

ECC algorithms work on a cyclic subgroup of an elliptic curve over a finite field.

Needed parameters:

  • The prime p that specifies the size of the finite field.
  • The coefficients a and b of the elliptic curve equation.
  • The base point G that generates our subgroup.
  • The order n of the subgroup.
  • The cofactor h of the subgroup.

​

20 of 59

Tasks time!

21 of 59

Imagine Q=n*P

​

How can we calculate n from Q?🤔

22 of 59

Imagine Q=n*P

​

How can we calculate n from Q?🤔 == discrete logarithm problem

23 of 59

Solutions

  1. Bruteforce 😢 — O(n)

24 of 59

Solutions

  • Bruteforce 😢 — O(n)
  • Baby-step, Giant-step — O(sqrt(n)) both memory and computation 🤔

25 of 59

Solutions

  • Bruteforce 😢 — O(n)
  • Baby-step, Giant-step — O(sqrt(n)) both memory and computation 🤔
  • Pollard’s rho — O(sqrt(n)) computation and O(1) memory 😍

26 of 59

Pollard’s rho

27 of 59

Pollard’s rho

28 of 59

Tortoise and hare algorithm

29 of 59

Real stuff

  • The private key is a random integer d chosen from {1, …, n-1} (where n is the order of the subgroup).
  • The public key is the point Q=dG (where G is the base point of the subgroup).

30 of 59

ECDH — elliptic curve Diffie-Hellman

  1. Alice and Bob generate private and public keys: ��
  2. Alice and Bob exchange their public keys ����
  3. ​

31 of 59

ECDH, problems

  • Sustainable from passive Man-in-the-Middle attacks

​

​

​

​

  • NOT sustainable from active Man-in-the-Middle attacks

32 of 59

ECDHE

ECDHE == ECDH Ephemeral

Each party generates new key pair every time they want to exchange keys.

Preferred way to exchange keys, used in TLS

33 of 59

ECDSA — elliptic curve digital signature algorithm

0. z = HA = hash(message) mod n

  1. Take a random integer k in range {1, ... , n-1}
  2. Calculate the point P = kG
  3. Calculate number r = xP mod n
  4. If r == 0, then go to step 1
  5. Calculate s=k-1(z + rdA) mod n
  6. If s = 0, then go to step 1

The pair (r, s) is the signature

34 of 59

ECDSA — verification

  1. Calculate u1=s-1z mod n
  2. Calculate u2=s-1r mod n
  3. Calculate P = u1G + u2HA

If r == xP mod n, then signature is valid

35 of 59

If k is the same

36 of 59

If k is the same

37 of 59

If k is the same

38 of 59

If k is the same

39 of 59

Tasks time!

40 of 59

Other curve formats

  • Montgomery curve
  • Edwards curve
  • Twisted Edwards curve
  • ...

http://hyperelliptic.org/EFD/g1p/index.html

41 of 59

Not today/other interesting stuff

  • Bilinear pairings
  • Invalid curves attacks
  • Singular curves attacks
  • Anomalous curves

42 of 59

How to solve ECC/crypto tasks on CTFs?

  1. Google it.
  2. If nothing found, go to step 1 (3 times max).�Else, I M P R O V I S E
  3. CTF Writeup? Try to understand, write your own solution. (easy)
  4. Blog post? Try to understand, write your own solution. (medium)
  5. Math paper? Read briefly. Try to understand, write your own solution.

43 of 59

PRNGs

Pseudo Random Number Generators

44 of 59

What is a PRNG?

PRNG :)

seed

number/byte

45 of 59

LCG — Linear Congruential Generator

46 of 59

Breaking LCG

  1. Bruteforce seed — O(n)

47 of 59

Breaking LCG

  • Bruteforce seed — O(n)
  • Apply brains — < O(n) 👌

48 of 59

Case 1: everything known

  • Generate next value == apply formula :)
  • Compute previous value(s)/seed�

49 of 59

Case 2: unknown increment

50 of 59

Case 3: unknown increment and multiplier

51 of 59

Case 4: everything unknown

😢🔮

52 of 59

Case 4: everything unknown

There is a high probability that gcd(m*n) == m

53 of 59

Case 4: everything unknown🤔

54 of 59

Case 4: everything unknown🤔

55 of 59

LFSR — Linear Feedback Shift Register

56 of 59

Mersenne twister

57 of 59

MT19937

MT19937 — period is 2^19937-1

=> Need to observe 624 values to recover seed

58 of 59

we did it🔫

59 of 59

References