---
# System prepended metadata

title: 'Ch09: Public-Key Cryptography and RSA'
tags: [密碼學]

---

# Public-Key Cryptography and RSA

## Background of Public-Key Cryptography

### Introduction

- **Public-Key Cryptography $\equiv$ Asymmetric Cryptography**
- Inventors: Whitfield Diffie and Martin Hellman (Stanford University, 1976)
  - “New Directions in Cryptography” **IEEE Transactions on Information Theory**, vol. IT-22, no. 6, pp.644-654, 1976.
- Based on **Mathematical Functions**
- Keys: Private Key and Public Key (in pair)
  - Private Key
    - known **only to the owner**（與 secret key 不同）
    - used for decrypting, signing, or both
  - Public key
    - public to all
      - Knowing the Public Key, it is still **computationally infeasible** to compute the Private Key.
      - 兩個 key 互為反運算
    - used for **encrypting, verifying signatures**, or both
- **Misconceptions** concerning Public-Key Encryption
  - ❌Public-key encryption is more secure than symmetric encryption.
  - ❌Public-key encryption has made symmetric encryption obsolete.（皆有存在的需要）
  - ❌Key distribution is trivial when using public-key encryption, compared to the one involved in symmetric encryption.
- Terminology
  ![image](https://hackmd.io/_uploads/SyLGuN3E6.png)

### Applications of Public-Key Cryptography

- Encryption
  ![image](https://hackmd.io/_uploads/r1MsO43Ep.png)
  - Confidentiality (Secrecy) Function
  - 用對方的 public key 加密
- Digital Signature
  ![image](https://hackmd.io/_uploads/B1OTFE24a.png)
  - Authentication Function
    - Digital Signature authenticates the **integrity of the signed data** and the **identity of the signer** and can be used in proving to a **third party** that data was actually signed by the generator of the signature.
  - The requirements for a digital signature S
    - S must be a bit pattern that **depends on the message being signed**.
    - S must use some information **unique to the signer**.
    - Easy to produce S.
    - Easy to verify S.
    - Computationally infeasible to forge S.
  - Applications of Digital Signature
    - Electronic mail
    - Electronic funds transfer
    - Electronic data interchange
    - Software distribution
    - Data storage
    - Other applications which require data integrity assurance and data origin authentication.
- Encryption & Digital Signature
  ![image](https://hackmd.io/_uploads/HysDi4nNT.png)
  - Confidentiality (Secrecy) and Authentication Functions
- Key Exchange
  - Two sides cooperate to **exchange a session key**, which is a secret key for symmetric encryption generated for use for a particular transaction (or session) and valid for a short period of time.
- Applications supported by the widely used Public-Key Algorithms
  ![image](https://hackmd.io/_uploads/SkhBhV3VT.png)

## Well-Known Public-Key Algorithms

- Used for **Encryption only**
  - ElGamal Cryptosystem
- Used for **Digital Signatures only**
  - ElGamal Digital Signature Scheme
  - DSA (Digital Signature Algorithm)
  - ECDSA (Elliptic Curve Digital Signature Algorithm)
- Used for **Both Encryption and Digital Signatures**
  - RSA
  - ECC (Elliptic Curve Cryptosystem)
- Used for Key Exchange only
  - DH (Diffie-Hellman Algorithm)
  - ECDH (Elliptic Curve Diffie-Hellman Algorithm)

## Public-Key Cryptanalysis

- General Concerns
  - Resistance to **Chosen-Plaintext attacks**
    - Because the the public key, PU, is accessible by anyone.
    - Given C = E(PU, M), the attacker can guess the value of M and easily check his guess.
    - This is a serious problem if the number of possible plaintext messages is small enough to allow exhaustive search.
    - This problem can be solved by padding messages with sufficient random bits.
- Common Security Basis
  - **Integer Factorization** Problem (IFP)
  - **Discrete Logarithm** Problem (DLP)
  - **Elliptic Curve Discrete** Logarithm Problem (ECDLP)

## Introduction to RSA

- Inventors: Ron Rivest, Adi Shamir, and Leonard Adleman (MIT, 1977)
  - “On Digital Signatures and Public Key Cryptosystems,” Communications of the ACM, vol. 21 no 2, pp.120-126, Feb. 1978.
- Can be used for
  - Encryption
  - Digital Signature
  - Key Exchange
- One of the most widely used Public-Key Algorithms
- Security
  - Security Basis: IFP (**Integer Factorization Problem**)
  - No practical weaknesses have been found yet
- Standards
  - **PKCS #1**: RSA Cryptography Standard, RSA
    - Republished as [RFC 8017](https://datatracker.ietf.org/doc/html/rfc8017) (2016
    - Current Version: v2.2 (2012)
      - Major Changes from v2.1 (2002)
        - Supports **multi-prime RSA**
          - modulus may have more than two prime factors
          - lower computational cost for the decryption and signature
        - **Updates allowed hashing algorithms** to align with FIPS 180-4
          - adding SHA-224, SHA-512/224 and SHA-512/256
  - **IEEE P1363** (Standard Specifications for Public-Key Cryptography)
  - **ANSI X9.31** (Only for Signature Use)
  - **NIST FIPS PUB 186-5** (2023) (Only for Signature Use)
- Patents: USA (expired on 2000/9/20)

## Algorithm of RSA

### Key Generation Algorithm

![image](https://hackmd.io/_uploads/r1SUEB2E6.png)

- $p$: first factor
- $q$: second factor
- $n$: modulus
- $e$: public exponent
- $d$: private exponent
- 需要至少 1024 bits 的質數

### Encryption/Decryption Algorithm

- Encryption
  - Plaintext: $M < n$
  - Ciphertext: $C = M^e \bmod n$
- Decryption
  - Ciphertext: $C$
  - Plaintext: $M = C^d \bmod n$

### Theorem: RSA algorithm is a Cryptosystem.

**Proof**:  
Suppose M (< n) is the plaintext, $e \times d \equiv 1 \bmod \phi(n)$  
$$
\begin{align}
&D(PR, E(PU, M)) \\
&= (M^e \bmod n)^d \bmod n \\
&= (M^e)^d \bmod n \\
&= M^{e \times d} \bmod n \\
&= M^{e \times d \bmod \phi(n)} \bmod n \\
&= (M)^1 \bmod n \\
&= M \bmod n \\
&= M
\end{align}
$$

### Digital Signature Algorithm

- Signing
  ![image](https://hackmd.io/_uploads/BkRi_r3VT.png)
- Verification
  ![image](https://hackmd.io/_uploads/B1N6_r3Na.png)

### Representations of Private Key

- $(n, d)$: Original representation specified in RSA.
- $(p, q, dP, dQ, qInv)$
  - CRT can be used to speed up decrypting/signing operations.
  - $dP$: the first factor’s exponent
  - $dQ$: the second factor’s exponent
  - $qInv$: the CRT coefficient
  - The exponents $dP$ and $dQ$ are positive integers less than $p$ and $q$ respectively satisfying
    $$
    e \cdot dP \equiv 1 \pmod {(p – 1)} \\
    e \cdot dQ \equiv 1 \pmod {(q – 1)}
    $$
  - The CRT coefficient qInv is a positive integer less than $p$ satisfying $q \cdot qInv \equiv 1 \pmod p$

### Primitive Method for Encrypting Multiple Blocks

<!-- TODO -->


- OAEP (optimal asymmetric encryption padding) Encoding Method
  ```
                      +----------+------+--+-------+
                 DB = |  lHash   |  PS  |01|   M   |
                      +----------+------+--+-------+
                                     |
           +----------+              |
           |   seed   |              |
           +----------+              |
                 |                   |
                 |-------> MGF ---> xor
                 |                   |
        +--+     V                   |
        |00|    xor <----- MGF <-----|
        +--+     |                   |
          |      |                   |
          V      V                   V
        +--+----------+----------------------------+
  EM =  |00|maskedSeed|          maskedDB          |
        +--+----------+----------------------------+
  ```
  - L: optional label to be associated with the message (default: empty string)
  - lHash = Hash(L)
  - PS: padding string consisting of zero octets
  - seed: random octet string
  - MGF: mask generation function (based on hash functions)
  - M: message to be encrypted

### RSA Signature Signing/Verification Standard

- PKCS #1 v1.5

<!-- TODO p.25 ~ p.27 -->

### Speedups for RSA operations

- Using **Small** $e$
  - Three choices of $e$ are most commonly selected for requiring fewer multiplication operations
    - 3 (PKCS #1 recommendation)
    - 17
      - $2^4 + 1$
      - $10001_2$
    - 65537 (X.509 and PKCS #1 recommendation)
      - $2^{16} + 1$
      - $100000000000000001_2$
  - $e$ 太大反而可能會讓 $d$ 很小
  - Using **Montgomery’s Method** for Modular Exponentiation operations.
- Using **CRT** to **speedup Decrypting and Signing** (using private key)
  - Theoretically, about **3 ~ 4 times faster** can be achieved.
  - Algorithm（認識就好，不用記）
  ![image](https://hackmd.io/_uploads/H1LePvBSp.png)

## RSA Security

### IFP (Integer Factorization Problem)

- IFP: Given $n$, it is hard to find its factors $p$ and $q$.
- The Security of RSA is based on IFP
  - 最弱的地方也要難以破解
  - Guessing the value of $(p – 1)(q – 1)$ is no easier than factoring $n$.
  - Trying every possible $d$ is no easier than factoring $n$.
- Factorization Algorithms
  - Basic: Trial Division Method
  - Advanced
    - Special-Purpose Factoring Algorithms
      - factoring numbers with small factors
      - the numbers used for the modulus in most existing ciphers **do not have any small factors**.
    - General-Purpose Factoring Algorithms
- General-Purpose Factoring Algorithms
  - **MPQS** (Multiple Polynomial Quadratic Sieve; 1987)
  - **NFS** (Number Field Sieve; 1992)
    - Improved version: GNFS (Generalized Number Field Sieve)
    - NFS is more efficient than MPQS in factoring numbers larger than 115 digits.
    - RSA/140 (140 digits $\approx$ 140 $\approx$ **3.32 bits** $\approx$ 465 bits) was factored using GNFS (Feb. 1999).
    - GNFS overtaken MPQS as the most widely used factoring algorithm, as the size of the numbers being factored increases from about 130 digits to 140 or 150 digits.
  - **Lattice Sieve** (1993)
    - Proposed by J. M. Pollard (The development of the number field sieve)
- Factorization Records
  - <https://en.wikipedia.org/wiki/RSA_Factoring_Challenge>
  - **RSA-250** (250 digits, 829 bits) was factored by using **NFS** in 2020
- Recommendations for RSA key size
  - NIST SP 800-131A: **at least 2048 bits**
  - The European Union Agency for Network and Information Security: **at least 3072 bits**
  - Canada’s Communications Security Establishment: **at least 2048 bits**

### Low Encryption Exponent Attack

- Attack Scenario for the **Initial** RSA algorithm（只針對最原始的版本）
<!-- TODO p.34 -->

### Strong Prime

### Timing Attack

- A timing attack is a type of **side-channel attack** that may be used to compromise the security of RSA in some **implementations**.
  - [Montgomery’s Modular Method](https://hackmd.io/PGzjr6oyTsmBECZhhATgTw#Montgomery%E2%80%99s-Method)
  - Proposed by Kocher (1996) and Kaliski (1996)
  - An attacker can **measure the time it takes for decryption** and may use this information to **deduce information about the private key**.
<!-- TODO p.37 ~ p.38 -->

### Chosen Ciphertext Attack (CCA)

- The **Initial** RSA algorithm is vulnerable to CCA.
- CCA is an attack in which the attacker **chooses ciphertexts** and then **gets the corresponding plaintexts**, decrypted with the target’s private key.
  - **Assumption**: The attacker is given the access to **decryption oracle**.
    - The attacker is allowed to submit ciphertexts and gets back the corresponding message, but does not get to hold the decryption key directly.
  - **Restriction**: The attacker is **not allowed** to ask the decryption oracle to **decrypt the target ciphertext directly**.
- Base on the property of RSA
  $$
  E(PU, M_1) \times E(PU, M_2) = E(PU, [M_1, M_2])
  $$
- Attack Scenario
  - The attacker can use decrypt the captured ciphertext $C = M^e \bmod n$ to obtain the target message $M$ using a CCA as follows.
  ![image](https://hackmd.io/_uploads/H1jBgdHSp.png)
- However, RSA cryptosystems with simple encoding method may still vulnerable to **more sophisticated CCAs**.
  - To counter more sophisticated CCAs, RSA Security Inc. recommended the **OAEP** (optimal asymmetric encryption padding) **Encoding Method** as follows.

### Quantum Threat to RSA

- A Quantum Computer is a machine that performs computations based on the laws of Quantum Mechanics, which is the behavior of particles at the subatomic level.
- **Shor's quantum algorithm** can **efficiently solve IFP** (Integer Factorization Problem) by using **large-scale quantum computers**, which do not exist yet.
  ![image](https://hackmd.io/_uploads/SJLbWdSBp.png)
- The Number of Qubits required to Break RSA
  ![image](https://hackmd.io/_uploads/Hym_-OSHa.png)
  - The time is listed in units of “**1-qubit additions**”.
