# 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

### Applications of Public-Key Cryptography

- Encryption
- Confidentiality (Secrecy) Function
- 用對方的 public key 加密
- Digital Signature
- 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
- 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

## 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


- $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
- Verification

### 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（認識就好，不用記）

## 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.
- 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.
- The Number of Qubits required to Break RSA
- The time is listed in units of “**1-qubit additions**”.