EdDSA

Systems in Rust

Author

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.

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

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

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

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

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

--- title: "EdDSA" --- # 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](https://toc.cryptobook.us/book.pdf) > 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](https://toc.cryptobook.us/book.pdf) > 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](https://theintercept.com/source/) <iframe id="source" title="source" width="70%" height="70%" src="https://theintercept.com/source/"></iframe> ## 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](https://www.google.com/search?client=firefox-b-1-d&q=reality+winner) ## 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. ## ```{dot} //| fig-width: 800px //| echo: false digraph RSA_Encryption { bgcolor="#191919"; node [fontcolor = "#ffffff", color = "#ffffff"] edge [color = "#ffffff", fontcolor = "#ffffff"] // Encryption subgraph cluster_encryption { fontcolor = "#ffffff"; color = "#ffffff"; label = "Encryption"; message [label="Message (M)"]; encrypt [label="Ciphertext (C) = M^e mod n"]; public_key_ref [label="Private Key: (n, d)", shape=note]; message -> encrypt; public_key_ref -> encrypt; } // Decryption subgraph cluster_decryption { fontcolor = "#ffffff"; color = "#ffffff"; label = "Decryption"; ciphertext [label="Ciphertext (C)"]; decrypt [label="Message (M) = C^d mod n"]; private_key_ref [label="Public Key: (n, e)", shape=note]; ciphertext -> decrypt; private_key_ref -> decrypt; } input [label="Unencrypted Transaction"] inter [label="Encrypted Transaction"] output [label="Decrypted Transaction"] // Connections between steps input -> message; encrypt -> inter; inter -> ciphertext; decrypt -> output; } ``` # 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.](https://en.wikipedia.org/wiki/Finite_field) ## Recall - The`u`$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.](https://en.wikipedia.org/wiki/Plane_curve) ## Graphs of Continous Functions - Often express as $f(x,y) = 0$ ::::{.columns} :::{.column width="50%"} ```py 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)] ``` ::: :::{.column width="50%"} ```{python} #| echo: false 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 ::: {.callout-note} ## Public key An EdDSA *public key* is a curve point $A \in E(\mathbb{F}_p)$ encoded in $b$ bits ::: ## Signature verification ::: {.callout-note} ## 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 ::: {.callout-note} ## 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 ::: {.callout-note} ## 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