Hardness of RSA: Based on factorization factor (prime number)
Hardness of ECC: Based on discrete logarithm

Motivation for Public Key Algorithm

Problems with Secret Keys (Symmetric Key)

• Key Management Issues:
  • Use lots of keys for $n$ users
  • Distributing so many keys securely is difficult
  • Secure storage for the keys
  • User having $n$ keys cannot memorize them all
• Question: Can we have a system with significantly fewer keys?
  • Answer: Yes!

The 1976 Breakthrough

• 1976 — Diffie and Hellman introduced Key pairs: $\langle K_{private}, K_{public} \rangle$

Key Management Complexity

Conventional (Symmetric) System

• For conventional (symmetric) system, there must be a common key between any pair of users
• Thus, a lot of keys must be generated and maintained
• There must be $\frac{n(n-1)}{2}$ keys for n users (for possible communication channels)

Analogy: Think of it like a group chat where everyone needs a separate secret language with everyone else. In a group of 10 people, you'd need 45 different secret languages! That's 10×9÷2 = 45 pairs.

Additional keys that must be generated if 1 user is added: increases quadratically

Public Key Cryptography Solution

The Two-Key Idea

• Idea: have 2 keys
  • One key is inverse of the other key
  • The two keys can be interchanged

$\boxed{D(K_{PRIV}, E(K_{PUB}, P)) = D(K_{PUB}, E(K_{PRIV}, P))}$

• Each user owns one private key and shares the corresponding public key with n-1 remaining users
• Only 2n keys for n users
• Reduce from $O(n^2)$ to $O(n)$

Analogy: Instead of needing a unique secret language with everyone, you now have one "encoding language" (private) and one "decoding language" (public). Everyone can use your public decoder to talk to you, but only you can encode messages with your private encoder.

Public-Key Cryptosystem

• Bob's public key ring contains public keys from Joy, Mike, Ted, and Alice
• Encryption process:
  • Plaintext input → Encryption algorithm (e.g., RSA) using Alice's public key
  • Transmitted ciphertext sent over network
  • Decryption algorithm (reverse of encryption algorithm) using Alice's private key
  • Plaintext output

Key Exchange

• To share symmetric key/session key
  • Key $k$ is generated
  • Alice needs to share $k$ to Bob (using PKE)
    1. Enc_RSA(k, Bob’s Public Key) = CTk
    2. Dec_RSA(CTk, Bob's Private Key) = k

This is the secure way to share key!

Practical Data Encryption (Hybrid Encryption)

• Key sizes (practical)
  • AES: 128 / 256 bits (symmetric key)
  • RSA: 2048 bits (1024 is deprecated)

Data Encryption (Alice → Bob)

1. Key Generation
   • Alice generates a random symmetric key: $k_{AES} \leftarrow \text{SecureRandom}()$
2. Data Encryption (AES)
   • Alice encrypts the message ( M ) using AES: $CT_M = \text{Enc}_{AES}(k_{AES}, M)$
3. Key Encryption (RSA)
   • Alice encrypts the AES key using Bob’s public key: $CT_K = \text{Enc}_{RSA}(PK_{Bob}, k_{AES})$
4. Transmission
   • Alice sends: $(CT_K, CT_M)$

Data Decryption (Bob)

1. Key Decryption (RSA)
   • Bob recovers the AES key using his private key: $k_{AES} = \text{Dec}_{RSA}(SK_{Bob}, CT_K)$
2. Data Decryption (AES)
   • Bob decrypts the message: $M = \text{Dec}_{AES}(k_{AES}, CT_M)$

But this way, Bob cannot verify really that the message come from Alice → Digital signature (Later!)

Key Insight (important)

• AES encrypts the data
• RSA encrypts the AES key
• This is called Hybrid Encryption

RSA is slow → encrypt only the key
AES is fast → encrypt the actual data

Public Key Algorithm Requirements

Three Critical Requirements:

1. Computational Ease: It must be computationally easy to encipher or decipher a message given the appropriate key
2. Key Derivation Hardness: It must be computationally infeasible to derive $K_{PRIV}$ from $K_{PUB}$
3. Chosen Plaintext Security: It must be computationally infeasible to determine $K_{PRIV}$ from a chosen plaintext

Mathematical Foundation

Public Key Cryptosystem Basis

Based on modular arithmetic:

• Modular addition
• Modular multiplication
• Modular exponentiation

They are also based on the fact about prime numbers

Prime Numbers

Definition and Examples

• An integer $n > 1$ is called a prime number if its positive divisors are only 1 and n
• Prime numbers are central to number theory

Prime numbers less than 200:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199

Modular Arithmetic

Basic Definition

For any integers, $a$ and $n$:

• $a \bmod n$ = remainder when $a$ is divided by $n$
• $a = q \cdot n + r$ where $0 \leq r < n$

Congruence

Two integers $a$ and $b$ are said to be congruent modulo n, if:

• $(a \bmod n) = (b \bmod n)$, or can be written as

$\boxed{a \equiv b \pmod{n}}$
Definition: $a \equiv b \pmod{n}$ if and only if $n \mid (a - b)$

Using the definition of "divides", $n \mid (a - b)$ can be translated to $a - b = kn$ for some integer $k$.

Example: $100 \equiv 34 \pmod{11}$

• อันนี้ก็จะคือ $100 \% 11 = 1$, $34\% 11 = 1$

Properties

• $b$ is called the residue of $a \bmod n$
• All integers can always write: $a = qn + b$
• Usually have $0 \leq b \leq n-1$

Example: $-12 \bmod 7 \equiv -5 \bmod 7 \equiv 2 \bmod 7 \equiv 9 \bmod 7$

Note: Mod of negative number, the result must be positive number.

• e.g., $-12 \bmod 7 \rightarrow (-2 \times 7) + 2$, thus the result is 2
• e.g., $-5 \bmod 7 \rightarrow (-1 \times 7) + 2$, thus the result is 2

Exercise - Modular Arithmetic

Calculate the following:

• $3 \bmod 7 =$ 3
• $5 \bmod 7 =$ 5
• $5 \bmod 5 =$ 0
• $-10 \bmod 7 =$ 4
• $8 \bmod 5 =$ 3
• $-8 \bmod 5 =$ 2
• $-7 \bmod 3 =$ 2
• $-5 \bmod 1 =$ 0

Modular Multiplication

Multiplicative Inverse

Multiplicative inverse of $x$ (written as $x^{-1}$)

• Multiplication mod $n$ yields 1
• e.g., inverse of 4 mod 7 is 2
  • since $(4 \times 2) \bmod 7 = 8 \bmod 7 = 1 \bmod 7$

Important Properties

Some numbers have no inverse

• e.g., 4 has no inverse under mod 8

Finding Inverse:

• Use Extended Euclidian algorithm to find inverse
• Given $x$, $n$, find $y$ such that $xy = 1 \bmod n$

Key Rule:

• Only the numbers relatively prime to $n$ will have multiplicative inverse mod $n$

Greatest Common Divisor (GCD, ห.ร.ม)

Definition

GCD of $a$ and $b$ is the greatest common value which divides both $a$ and $b$. It is usually defined as $\gcd(a,b)$

Example: $\gcd(60, 24) = 12$

Relatively Prime

Two integers, $a$ and $b$, are relatively prime if their only common divisor is 1
$\boxed{\gcd(a, b) = 1}$

Useful Theorems

Important Number Theory Theorems

Theorem 3: If $p$ is prime s.t. $|Z_p^*| = p-1$

Theorem 4: $\forall a \in Z_p^*$ s.t. $\forall a^{\phi(p)} = 1 \bmod p$

Theorem 5: Let $p$ and $q$ are prime and $p \neq q$;

$\boxed{\phi(pq) = \phi(p) \cdot \phi(q)}$

Theorem 6: Extended Euclidean algorithm says if there is $\gcd(a, b) = 1$;

$\boxed{\exists m, n \in Z; \text{ s.t. } ma - nb = 1 \text{ where } a > b}$

RSA (Rivest, Shamir, Adleman)

Overview

• It's a public key encryption algorithm
• Support both encryption and digital signature
  • Digital signature (only public key encryption can only be used to compute one.)
  • Symmetric key ให้แบบนี้กับคุณไม่ได้นะ

Theoretical Basis

Assumption/theoretical basis:

• Factoring a big number is hard

$P(Q)=1252151251235234234125$. If we want to break RSA จะต้อง Factor out ให้ได้ ออกเป็น Prime number สองตัว!!

Key Characteristics

• Variable key length (usually 512, 1024, 2048 bits)
  • 1024 ควรจะเป็น minimum แล้วตอนนี้!
• Variable plaintext block size
  • Plaintext block must be "smaller" than modulus
  • Ciphertext block size is also smaller than modulus
• Slower to compute than AES → mostly used to encrypt a secret key

RSA Key Selection

Key Generation Process

To generate a key pair (one public key and its corresponding private key):

1. Select large primes, $p$ and $q$ which are almost same size ($\approx \sqrt{n}$)
2. Compute $n = pq$ and $\phi(n) = (p-1)(q-1)$ (Theorem 3, 5)
3. Keep $p$ and $q$ with yourself! (เก็บไว้ในใจ)

Mathematical Foundation

Before going to Step 4, understand this:

Suppose $x \in Z_{pq}^*$, we know that:

$\boxed{x^{(p-1)(q-1)} = 1 \bmod pq}$

(Theorem 4)

4. Choose $e$ that is relatively prime to $(p-1)(q-1)$ and $1 < e < (p-1)(q-1)$

We know from Theorem 6 that:

$\exists d, k \in Z; \text{ s.t. } de - k(p-1)(q-1) = 1$

Therefore:

$\boxed{de = 1 + k(p-1)(q-1)}$

Suppose we have $x^e$ where $x \in Z_{pq}^*$, we can retrieve $x$ from $x^e$ by powering it with $d$ then modulo by $pq$:

$\boxed{x^{de} = x^{1+k(p-1)(q-1)} \bmod pq \equiv x \bmod pq}$

5. Keep $e$ then find $d$ which is $de = 1 \bmod pq = 1 \bmod n$
6. Securely delete $p$ and $q$ since we don't need to use them anymore
7. Send pair of $e$ and $n$: $\langle e, n \rangle$ as a public key for encryption
8. Keep $\langle d, n \rangle$ as private key for decryption

RSA Key Generation Algorithm

Summary of Key Generation Steps

1. Generate two large random primes, $p$ and $q$, of approximately equal size such that their product $n = pq$ is of the required bit length, e.g. 1024 bits
2. Compute $n = pq$ and (phi) $\phi = (p-1)(q-1)$
3. Choose an integer $e$, $1 < e < \phi$, such that $\gcd(e, \phi) = 1$
4. Compute the secret exponent $d$, $1 < d < \phi$, such that $ed \equiv 1 \pmod{\phi}$
   • → $d = e^{-1} \bmod \phi$
5. The public key is $(n, e)$ and the private key $(d, p, q)$. Keep all the values $d$, $p$, $q$ and $\phi$ secret.
   • We prefer sometimes to write the private key as $(n, d)$ because you need the value of $n$ when using $d$. Other times we might write the key pair as $((N, e), d)$.

Terminology

• $n$ is known as the modulus
• $e$ is known as the public exponent or encryption exponent or just the exponent
• $d$ is known as the secret exponent or decryption exponent

How Hard is RSA?

Security Analysis

• We know that RSA uses product of two primes to generate $n$ (suppose $p$ and $q$)
• Since we have to randomly choose $e$ as the encrypt exponent and send $\langle e, n \rangle$ as the encryption key.
• Let the attacker knows $\langle e, n \rangle$ and he also knows that there is $d$ which $\gcd(d, e) = 1$ used for decryption.

However:

• It is very hard for attacker to guess what $d$ is used without knowing $p$ and $q$
• (since there are many possible integers which $\gcd(X, e) = 1$; $d \in X$)

Analogy: It's like knowing someone mixed red and blue paint to get purple, but you don't know the exact amounts. Even though you know the result (purple/n) and one method (red/e), figuring out the exact recipe (blue/d) without knowing the original amounts (p and q) is incredibly difficult when the numbers are huge.

Naive RSA Encryption/Decryption

Encryption Process

To encrypt a message $M$ by the sender:

• Obtains public key of recipient, Pub-key = $\langle e, n \rangle$
• Computes:

$\boxed{C = M^e \bmod n}$

where $M \in Z_{pq}^*$ and $n = pq$

Decryption Process

To decrypt the ciphertext $C$ by the receiver:

• Uses their private key, Pri-key = $\langle d, n \rangle$
• Computes:

$\boxed{M = C^d \bmod n}$

RSA Demo

YouTube Demo Link:
https://www.youtube.com/watch?v=9sY57iwNDJw

Security of RSA

Possible Approaches to Attacking RSA:

1. Brute force key search (infeasible given size of numbers)
2. Mathematical attacks (based on difficulty of computing $\phi(n)$, by factoring modulus $n$)
3. Timing attacks (on running of decryption)
4. Chosen ciphertext attacks (given properties of RSA)
5. Shor's algorithm on quantum computing can break any cryptographic algorithms which use integer factorization as a hard problem to secure their Pri-key and Pub-key. RSA is included!

Other Public-Key Cryptosystems

Elliptic Curve Cryptography (ECC)

• At same security level of RSA, ==ECC needs smaller key size==
• Instead of using integer factorization as RSA, ECC uses discrete logarithm problem as a hard problem for security

Elgamal Encryption

• Faster than RSA for decryption, a bit slower for encryption
• Elgamal was not patented but RSA was (in USA)
  • (now RSA's patent is already expired)

Exercise – RSA Encryption/Decryption

Online Tool:
https://www.devglan.com/online-tools/rsa-encryption-decryption

Elliptic Curve Cryptography (ECC)

ECC Introduction

Motivation for ECC

The Problem

Problem: Asymmetric schemes like RSA and Elgamal require exponentiations in integer rings and fields with parameters of more than 1000 bits.

• High computational effort on CPUs with 32-bit or 64-bit arithmetic
• Large parameter sizes critical for storage on small and embedded devices

The Motivation

Motivation: Smaller field sizes providing equivalent security are desirable

The Solution

Solution: Elliptic Curve Cryptography uses a group of points (instead of integers) for cryptographic schemes with coefficient sizes of 160-256 bits, reducing significantly the computational effort.

Analogy: Instead of working with giant numbers (like RSA's 1024+ bits), ECC works with points on a curve using much smaller numbers (160-256 bits). It's like using a complex 3D map (ECC) instead of a really, really long street address (RSA) - both get you to the destination securely, but one is more compact.

Computations on Elliptic Curves

Weierstraß Equation

Elliptic curves are polynomials that define points based on the (simplified) Weierstraß (VY-er-shtrass) equation:
$\boxed{y^2 = x^3 + ax + b}$
for parameters $a, b$ that specify the exact shape of the curve

Curve Characteristics

• On the real numbers and with parameters $a, b \in \mathbb{R}$, an elliptic curve looks like the diagram shown (a smooth curve with symmetry about the x-axis)
• Elliptic curves can not just be defined over the real numbers $\mathbb{R}$ but over many other types of finite fields

Example: $y^2 = x^3 - 3x + 3$ over $\mathbb{R}$

Finite Field

Definition

• A finite field, also known as a Galois field, is a mathematical field that contains a finite number of elements
• A field is a set equipped with two operations, addition and multiplication, that satisfy the basic field properties:
  • Associativity
  • Commutativity
  • Distributivity
  • Existence of identity elements
  • Inverses

Common Examples

The most common examples of finite fields are given by the integers mod p when $p$ is a prime number.

Computations on Elliptic Curves (continued)

In Cryptography

In cryptography, we are interested in elliptic curves modulo a prime $p$:

Definition: Elliptic Curves over prime fields

The elliptic curve over $Z_p$, $p > 3$ is the set of all pairs $(x, y) \in Z_p$ which fulfill
$\boxed{y^2 = x^3 + ax + b \bmod p}$
together with an imaginary point of infinity $\theta$, where $a, b \in Z_p$ and the condition
$\boxed{4a^3 + 27b^2 \neq 0 \bmod p}$
Note that $Z_p = \{0, 1, ..., p-1\}$ is a set of integers with modulo p arithmetic

Computations on Elliptic Curves (continued)

Special Considerations

Some special considerations are required to convert elliptic curves into a group of points

• In any group, a special element is required to allow for the identity operation, i.e., given $P \in E$: $P + \theta = P = \theta + P$

• This identity point (which is not on the curve) is additionally added to the group definition

• This (infinite) identity point is denoted by $\theta$

Symmetric = fold paper along horizontal axis

Symmetry Properties

Elliptic Curve are symmetric along the x-axis

• Up to two solutions $y$ and $-y$ exist for each quadratic residue $x$ of the elliptic curve

• For each point $P = (x, y)$, the inverse or negative point is defined as $-P = (x, -y)$

Analogy: Think of the elliptic curve like a butterfly - it's perfectly symmetric about the x-axis. If you have a point P above the x-axis, its "mirror image" -P is directly below it at the same x-coordinate. The point at infinity θ is like a meeting point where parallel lines meet - an abstract concept that makes the math work.

Computations on Elliptic Curves (continued)

Point Addition Operation

Generating a group of points on elliptic curves based on point addition operation $P + Q = R$, i.e., $(x_P, y_P) + (x_Q, y_Q) = (x_R, y_R)$

Geometric Interpretation of Point Addition Operation

• Draw straight line through P and Q; if P=Q use tangent line instead
• Mirror third intersection point of drawn line with the elliptic curve along the x-axis

Elliptic Curve Point Addition and Doubling Formulas

$\boxed{x_3 = s^2 - x_1 - x_2 \bmod p \text{ and } y_3 = s(x_1 - x_3) - y_1 \bmod p}$
where