Cryptography and computer security - Tutorial 22.12.2020

--- tags: vaje, kirv, signatures hackmd: https://hackmd.io/o1tJDJoZRcmRIJAMgqMFyw plugins: mathjax --- # Cryptography and computer security - Tutorial 22.12.2020 --- ## Digital signatures ### "Textbook" RSA signature * Key generation: same as for RSA encryption * Signing: $\sigma = m^d \bmod{n}$ * Verifying: $m \stackrel{?}{\equiv} \sigma^e \pmod{n}$ ### ElGamal signature * Key generation: - Choose a large prime $p$ and $\alpha \in \mathbb{Z}_p^*$ such that $\langle \alpha \rangle = \mathbb{Z}_p^*$ - Choose the **private key** $a \stackrel{R}{\in} \mathbb{Z}_{p-1} \setminus \lbrace 0 \rbrace$ - Compute $\beta = \alpha^a \bmod{p}$ - Publish $(p, \alpha, \beta)$ as the **public key** * Signing $m \in \mathbb{Z}_{p-1}$: - Choose $k \stackrel{R}{\in} \mathbb{Z}_{p-1} \setminus \lbrace 0 \rbrace$ - Compute $\gamma = \alpha^k \bmod{p}$ and $\delta = (m - a \gamma) k^{-1} \bmod{(p-1)}$ - If $\gamma \equiv 0 \pmod{p-1}$ or $\delta = 0$, start over by choosing a new $k$ - The **signature** is $\sigma = (\gamma, \delta)$ * Verifying a signature $\sigma = (\gamma, \delta) \in \mathbb{Z}_p^*$${}\times \mathbb{Z}_{p-1}$ of a message $m \in \mathbb{Z}_{p-1}$: - Check that $\alpha^m \equiv \beta^\gamma \gamma^\delta \pmod{p}$ ### DSA signature * Key generation: - Choose a 1024-bit prime $p$ and $\alpha \in \mathbb{Z}_p^*$ of order $q$ a 160-bit prime - Choose the **private key** $a \stackrel{R}{\in} \mathbb{Z}_q \setminus \lbrace 0 \rbrace$ - Compute $\beta = \alpha^a \bmod{p}$ - Publish $(p, q, \alpha, \beta)$ as the **public key** * Signing $m \in \mathbb{Z}_q$: - Choose $k \stackrel{R}{\in} \mathbb{Z}_q \setminus \lbrace 0 \rbrace$ - Compute $\gamma = (\alpha^k \bmod{p}) \bmod{q}$ and $\delta = (m + a \gamma) k^{-1} \bmod{q}$ - If $\gamma = 0$ or $\delta = 0$, start over by choosing a new $k$ - The **signature** is $\sigma = (\gamma, \delta)$ * Verifying a signature $\sigma = (\gamma, \delta) \in (\mathbb{Z}_q)^*$ of a message $m \in \mathbb{Z}_q$: - Verify that $\gamma, \delta \ne 0$ - Compute $\theta = \delta^{-1} \bmod{q}$ - Check that $((\alpha^m \beta^\gamma)^\theta \bmod{p}) \bmod{q} = \gamma$ --- ### Attacks on digital signatures * **Universal forgery**: an adversary can forge a valid signature $\sigma$ for any given message $m$. * **Selective forgery**: an adversary can forge a valid signature $\sigma$ for a message $m$ chosen by a challenger. * **Existential forgery**: an adversary can forge a valid message-signature pair $(m, \sigma)$ which had not been previously produced by a legitimate signer. ### Attack models * **Key-only attack**: the adversary only has access to the public key. * **Known-message attack**: the adversary has access to a number of valid message-signature pairs $(m_i, \sigma_i)$. * **Chosen-message attack**: the attacker can obtain valid signatures $\sigma_i$ for messages $m_i$ of his own choice. --- ### Exercise 1 Show that the textbook RSA signature scheme is existentially forgeable under a key-only attack and a known-message attack, and universally forgeable under a chosen-message attack. Describe the easiest way to prevent these attacks. ---- * Existential forgery under a key-only attack: - the adversary knows $n, e$ - cho ose $\sigma \in \mathbb{Z}_n$ - compute $m = \sigma^e \bmod{n}$ * Existential forgery under a known-message attack: - the adversary knows $n, e$ and some $(m_i, \sigma_i)$ - $m = m_1 m_2 \bmod{n}$ - $\sigma = \sigma_1 \sigma_2 \bmod{n}$ * Universal forgery under a chosen-message attack: - we want to obtain a signature for a message $m$ - find $m_1, m_2 \ne m$ such that $m_1 m_2 \equiv m \pmod{n}$ - obtain signatures $\sigma_1$, $\sigma_2$ of $m_1$, $m_2$ - compute $\sigma = \sigma_1 \sigma_2 \bmod{n}$ --- ### Exercise 2 - the reblocking problem Suppose that Alice wants to send Bob a signed and encrypted message $m$. She will use RSA for both signing and encrypting. She first uses her private key $(n_A, d_A)$ to obtain the signature $s = m^{d_A} \bmod{n_A}$, and then uses Bob's public key $(n_B, e_B)$ to obtain the ciphertext $c = s^{e_B} \bmod{n_B}$. She sends $c$ to Bob, who then decrypts it with his private key $(n_B, d_B)$ to obtain $s' = c^{d_B} \bmod{n_B}$, and finally recovers the message $m' = s'^{e_A} \bmod{n_A}$ using Alice's public key $(n_A, e_A)$. Assuming that $m$ has been chosen uniformly at random from $\mathbb{Z}_{n_A}$, what is the probability that $m \ne m'$ - i.e., that Bob does not decrypt the message correctly? Compute the probability for $n_A = 62894113$ and $n_B = 55465219$. How could this problem be mitigated? ---- $$ \begin{aligned} m' &= s'^{e_A} \bmod{n_A} \\ &= (c^{d_B} \bmod{n_B})^{e_A} \bmod{n_A} \\ &= ((s^{e_B} \bmod{n_B})^{d_B} \bmod{n_B})^{e_A} \bmod{n_A} \\ &= (((m^{d_A} \bmod{n_A})^{e_B} \bmod{n_B})^{d_B} \bmod{n_B})^{e_A} \bmod{n_A} \\ &= ((m^{d_A} \bmod{n_A}) \bmod{n_B})^{e_A} \bmod{n_A} \end{aligned} $$ * If $n_A < n_B$, everything will be OK. * If $n_A > n_B$: $m' \ne m$ with probability $1 - \frac{n_B}{n_A}$. Revised protocol: 1. Alice produces a signature $\sigma$ of $m$. 2. Alice encrypts $m \| \sigma$ to produce a ciphertext $c$ and sends it to Bob. 3. Bob decrypts the ciphertext $c$ to obtain the message $m'$ and signature $\sigma'$. 4. Bob verifies that $\sigma'$ is Alice's signature of $m'$. --- ### Exercise 3 Describe why the value $\gamma \bmod{p-1}$ in the ElGamal signature scheme should not be $0$. ---- * If $\gamma \equiv 0 \pmod{p-1}$, then the private key is not used in signing. * If $\delta = 0$, then we can compute $a = m\gamma^{-1} \bmod{p-1}$. --- ### Exercise 4 Compare the ElGamal and DSA signature schemes. Does the difference in efficiency affect the security of DSA? ---- Assume $p$ is a 1024-bit prime, $q$ is 160-bit prime. * ElGamal signature: - signature length: $2048$ bits - signing: $O(\log^3 p) \approx 1024^3$ - verifying: $3 \cdot O(\log^3 p) \approx 3 \cdot 1024^3$ * DSA signature: - signature length: $320$ bits - signing: $O(\log^3 p) \approx 1024^3$ - verifying: $3 \cdot O(\log^3 p) \approx 3 \cdot 1024^3$ * Index calculus on $p$ is about as efficient as doing baby-step/giant-step algorithm in a subgroup of order $q$

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.