EdDSA

Systems in Rust

Prof. Calvin

Announcements

  • Welcome to Systems in Rust
  • Action Items:
    • Midterms verbal update.
    • Keep at ix
    • This unlocks the last and greatest of the cryptographic homeworks so we can get to graph theory.

Today

  • Private Key Cryptography
  • Digital Signatures
  • Edwards-curve Digital Signature Algorithm (EdDSA)
    • Some math where we need it
    • An aside on side channels if we get bored

Public Key Cryptography

Motivating Example

  • Canonical Example is Snowden x Greenwald 2013
    • Snowden wished to communicate a secret to Greenwald
    • Snowden and Greenwald had never met
    • Snowden could not transmit the secret in plain text
  • Vs enigma, no prior agreement on how to encrypt/decrypt

Reads Cryptobook

A key exchange protocol \(P\) is a pair of probabilistic machines \((A, B)\) that take turns in sending messages to each other. At the end of the protocol, when both machines terminate, they both obtain the same value \(k\). A protocol transcript \(T_P\) is the sequence of messages exchanged between the parties in one exe- cution of the protocol.

Reads Cryptobook

Since \(A\) and \(B\) are probabilistic machines, we obtain a different transcript every time we run the protocol. Formally, the transcript \(T_P\) of protocol \(P\) is a random variable, which is a function of the random bits generated by \(A\) and \(B\). The eavesdropping adversary \(E\) sees the entire transcript \(T_P\) and its goal is to figure out the secret \(k\).

Set the Stage

  • Snowden has e.g. files on a harddrive
    • The files contain keywords that cannot be safely transmitted over US-based internet connections.
    • Snowden is based in Hawai’i with no access to non-US-based connections.
    • Snowden needs to encrypt the files in such as a way that only a trusted destination may read them.

First Contact

  • Snowden contacts Greenwald to agree to use a secure messaging protocol
    • Use of such protocols is relatively non-suspicious, used for banking etc.
    • It was enough to raise alarms for Snowden, but not quickly enough to stop him.
  • Greenwald agrees to a recommended protocol

Initialization

  • Greenwald generates a combination of numerical values on a local computing device.
    • One of these is the public-key, which Greenwalk may circulate broadly.
  • We see an example of such a technology on the next slide.

SecureDrop

  • Embed doesn’t work for what are likely obvious reasons:
  • Link

Safety Note

  • Probably dropping to The Intercept is not recommended.
  • Reality Winner is currently incarcerated due to a leak fumbled by The Intercept
  • Read more

Step 2

  • Greenwald & co. hold in reserve a private-key
  • They defend it like lives depend on it, as they did for Winner and Snowden.
  • So: not stored in plaintext on a hard-drive
  • So: if on a hard-drive, hard-drive is in a secure site from e.g. federal law enforcement.

Step 3

  • Snowden, and hopefully enough others to avoid suspicion, use the public key to encrypt their payload.
  • In addition to e.g. top secret documents, concerned community members could send in less-secret materials such as analysis of policing data with which they would rather not be affiliated.
  • Journalists sift through the inputs.

It’s that simple

  • Okay but like how do we do that:
    • Any eaves-dropping adversary can see the public key.
    • One-to-one communication of a key is already dangerous
    • All this encryption/decryption needs to be managable by e.g. non-computing specialized journalists.

Digital Signatures

Motivating Example

  • I have a Bitcoin.
  • I can only spend it if other people can:
    • See it, to tell I have it
    • Not spend it, because it’s mine
  • I use a digital signature.

A transaction

Each owner transfers the coin to the next by digitally signing a hash of the previous transaction and the public key of the next owner and adding these to the end of the coin

  • I own a coin.
  • I have a public keys.
  • I transfer that a coin to new owner to buy the Grundrisse translated to Quenya
  • This happens over the open internet.

Signage

  • To verify it is (1) my coin and (2) me transferring it, I:
    • Write down the transactions details.
    • SHA256 hash the message
    • Encrypt with my private key
    • Release the hash and cipher (encrypted) text

Verify

  • The general public:
    • Decrypts the ciphertext with my public key
    • SHA256 hashes the decrypted text
    • If the hash matches our released hash, then it had to be us and the transaction is valid.

RSA_Encryption cluster_decryption Decryption cluster_encryption Encryption message Message (M) encrypt Ciphertext (C) = M^e mod n message->encrypt inter Encrypted Transaction encrypt->inter public_key_ref Private Key: (n, d) public_key_ref->encrypt ciphertext Ciphertext (C) decrypt Message (M) = C^d mod n ciphertext->decrypt output Decrypted Transaction decrypt->output private_key_ref Public Key: (n, e) private_key_ref->decrypt input Unencrypted Transaction input->message inter->ciphertext

EdDSA, algorithm

EdDSA

In public-key cryptography, Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of Schnorr signature based on twisted Edwards curves.

  • Ah, that really clarifies things.

Iterative Definition

An EdDSA signature scheme is a choice.

Iterative Definition

An EdDSA signature scheme is a choice over:

  • A finite field \(\mathbb{F}_p\) where we take \(p\) to be an odd prime.

Galois field

In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that has a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are the integers mod p \(p\) when \(p\) is a prime number.

Recall

  • Theu\(n\)s and i\(n\)’s in Rust are rings
    • They have addition and multiplication
  • They aren’t fields - zero is divisible
    • Spoiler alert, but \(2^{\frac{n}{2}} \times 2^{\frac{n}{2}} \equiv 0 \pmod{2^n}\)
  • So: not \(\mathbb{Z}/2^8\mathbb{Z}\)
    • What about \(\mathbb{Z}/(2^8+1)\mathbb{Z}\)?
      • That’s \(\mathbb{F}_p\) where \(p = 2^8+1\)

Iterative Definition

An EdDSA signature scheme is a choice over:

  • A finite field \(\mathbb{F}_p\).
  • An elliptic curve \(E\) over \(\mathbb{F}_p\)
    • We simply as:
      • A plane curve over
      • A finite field
      • of form \(a x^2+y^2= 1+dx^2y^2\)

Plane Curve

In mathematics, a plane curve is a curve in a plane that may be a Euclidean plane, an affine plane or a projective plane. The most frequently studied cases are smooth plane curves (including piecewise smooth plane curves), and algebraic plane curves. Plane curves also include the Jordan curves (curves that enclose a region of the plane but need not be smooth) and the graphs of continuous functions.

Graphs of Continous Functions

  • Often express as \(f(x,y) = 0\)
import matplotlib.pyplot as plt
import numpy as np
import sympy
from sympy.abc import x, y

r = 1

curve = sympy.Eq(0,x**2 + y**2 - r)
for_y = sympy.solve(curve, y)
f = sympy.lambdify(x, for_y)

x = np.linspace(-r, r, 1000)

_ = [plt.plot(x, y) for y in f(x)]

Iterative Definition

An EdDSA signature scheme is a choice over:

  • A finite field \(\mathbb{F}_p\).
  • An elliptic curve \(E\) over \(\mathbb{F}_p\)
    • Whose group \(E(\mathbb{F}_p)\) of \(\mathbb{F}_p\)-rational points has order \(#E(\mathbb{F}_p) = 2^C \ell\) where \(\ell\) is a large primce and \(2^c\) is the cofactor
      • Take a 400-level math class
      • Basically this is a measure of the area within the ellipse.

Iterative Definition

An EdDSA signature scheme is a choice over:

  • A finite field \(\mathbb{F}_p\).
  • An elliptic curve \(E\) over \(\mathbb{F}_p\)
  • A base point \(B \in E(\mathbb{F}_p)\)
    • This is the only parameter set when generating your own keys.
    • Everything else is pre-computed.
    • Basically a point on the curve.

Iterative Definition

An EdDSA signature scheme is a choice over:

  • A finite field \(\mathbb{F}_p\).
  • An elliptic curve \(E\) over \(\mathbb{F}_p\)
  • A base point \(B \in E(\mathbb{F}_p)\)
  • A hash function \(H\) with \(2b\)-bit outputs, where \(2^{b-1} > q\)
    • This just allows machine representation.

EdDSA, terms

Public key

Public key

An EdDSA public key is a curve point \(A \in E(\mathbb{F}_p)\) encoded in \(b\) bits

Signature verification

Signature verification

An EdDSA signature on a message \(M\) by public \(A\) is the (ordered) pair \((R,S)\) encoded in \(2b\) bits, where \(R\) is a curve point \(R \in E(\mathbb{F}_p)\) and \(S\) is non-negative integer less than the size of the large prime \(\ell\). \((R,S)\) must satisfy the following equation (where \(\parallel\) is string concatenation).

\[ 2^c S B = 2^c R + 2^c H(R \parallel A \parallel M) A \]

Private key

Private key

An EdDSA private key is a \(b\)-bit string \(k\) which should be chosen uniformly at random. The corresponding public key is \(A = s B\), where \(s = H_{0,\dots,b - 1}(k)\) is the least significant \(b\) bits of \(H(k)\) interpreted as an integer.

Signing

Signing

The signature on a message \(M\) is deterministically computed as \((R, S)\) where \(R = r B\) for \(r = H(H_{b,\dots,2b - 1}(k) \parallel M)\), and \[ S \equiv r + H(R \parallel A \parallel M) s \pmod \ell \] This satisfies the verification equation \[ \begin{align} 2^c S B &= 2^c (r + H(R \parallel A \parallel M) s) B \\ &= 2^c r B + 2^c H(R \parallel A \parallel M) s B \\ &= 2^c R + 2^c H(R \parallel A \parallel M) A. \end{align} \]

EdDSA, Ed25519