In cryptography, we often encrypt and sign messages that contain characters. However, asymmetric key cryptosystems (where Alice and Bob use different keys), such as RSA and ElGamal, are based on arithmetic operations on integers. Symmetric key cryptosystems (where Alice and Bob use the same key), such as DES and AES, are based on bitwise operations on bits (a bit is either 0 or 1 and is an abbreviation for binary digit). Therefore, we must convert characters into integers or bits before applying the cryptosystem to the message.

Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, which uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is shown in the following table (note that the binary representation on the Wikipedia site uses only seven bits, but we use eight bits by prepending an extra 0):

For example, if Alice wants to send the message "Hey Bob!" encrypted to Bob using a symmetric key cryptosystem, she first converts it into its integer representation and then into its binary representation:

\( \eqalign{ H &\rightarrow 72 &&\rightarrow 01001000 \\ e &\rightarrow 101 &&\rightarrow 01100101 \\ y &\rightarrow 121 &&\rightarrow 01111001 \\ &\rightarrow 32 &&\rightarrow 00100000 \\ B &\rightarrow 66 &&\rightarrow 01000010 \\ o &\rightarrow 111 &&\rightarrow 01101111 \\ b &\rightarrow 98 &&\rightarrow 01100010 \\ ! &\rightarrow 33 &&\rightarrow 00100001 } \)

That is, the message "Hey Bob!" is represented with integers as "72 101 121 32 66 111 98 33" and in binary as "01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001".

While ASCII is sufficient for basic English text, modern cryptographic applications often need to handle international characters. Unicode standards like UTF-8 extend ASCII and can encode virtually all characters from all writing systems. In UTF-8, ASCII characters still use a single byte, while other characters may use 2-4 bytes.

Modern cryptographic algorithms typically operate on bytes (8-bit units) or words (groups of bytes). The binary representation shown above organizes characters into bytes, which serve as the fundamental unit for cryptographic operations in algorithms like AES, where data is processed in 128-bit (16-byte) blocks.

Notice the relationship between the different representations:

• The decimal form is what computers process mathematically
• The hexadecimal form (base 16) provides a more compact representation where each hex digit represents exactly 4 bits
• The binary form (base 2) shows the actual bit pattern stored in memory

It's important to note that encoding (converting characters to numbers or binary) is not the same as encryption. Encoding is a standardized, reversible process with no secret key. Anyone knowing the encoding scheme can decode the message. Encryption, on the other hand, requires a key to reverse the process, providing actual security.

Related Encoding Schemes in Cryptography

Several other encoding schemes are commonly used in cryptographic applications:

• Base64: Often used to encode binary data (like encryption keys or encrypted messages) into ASCII text for safe transmission over text-based channels
• Hex encoding: Frequently used to represent hashes, keys, and other binary values in a human-readable format
• Block padding: Many cryptographic algorithms operate on fixed-size blocks (e.g., AES uses 128-bit blocks), requiring messages to be padded to the appropriate length

The exponent of a number indicates how many times the number is multiplied by itself. For example:

\( 4^{3} = 4 \cdot 4 \cdot 4 = 64 \)

Here, 3 is the exponent (or power), and 4 is the base. In words, we say "4 to the power of 3."

Here are the laws of exponents:

Exponentiation in Modular Arithmetic

In cryptography, we often compute exponents in modular arithmetic:

\( a^b \mod n \) means raising \(a\) to power \(b\) and then taking the remainder when divided by \(n\)

Example: \( 3^4 \mod 7 = 81 \mod 7 = 4 \)

The same exponent rules apply in modular arithmetic:

\( (a^m \cdot a^n) \mod n = a^{m+n} \mod n \)

\( (a^m)^n \mod p = a^{m \cdot n} \mod p \)

Importance in Cryptography

These exponent rules are fundamental to many cryptographic algorithms:

• RSA: Uses the property that \((m^e)^d \mod n = m^{e \cdot d} \mod n\)
• Diffie-Hellman: Relies on \((g^a)^b \mod p = g^{ab} \mod p = (g^b)^a \mod p\)
• Fast exponentiation: Used for efficient computation of large powers in cryptographic operations

Computing Large Exponents Efficiently

For cryptographic applications, we need to efficiently compute large exponents. The square-and-multiply algorithm lets us calculate \(x^n\) with only \(O(\log n)\) multiplications:

1. Convert the exponent to binary representation
2. Start with result = 1
3. For each bit in the exponent (from left to right):
   • Square the result
   • If the current bit is 1, multiply by the base

Example: To compute \(3^{13}\), we use binary 13 = 1101:
result = 1
bit 1: result = \( 1^{2} \times 3 = 3 \)
bit 1: result = \( 3^{2} \times 3 = 27 \)
bit 0: result = \( 27^{2} = 729 \)
bit 1: result = \( 729^{2} \times 3 = 1,594,323 \)

You already use modulo computation when you look at a clock and, for example, need to figure out what time it will be 3 hours after 11 o'clock, which is 2 o'clock. In mathematics, we write this as:

\( (11 + 3) \: mod \: 12 = 2 \)

Here, 12 is the modulus because we want the time as an integer between 0 and 11 (in this case, 12 o'clock is denoted by 0). In words, we say "11 plus 3 modulo 12 equals 2." The result of a modulo computation is an integer between 0 and the modulus minus 1. For example, with modulus 3, we have:

• \( 1 \: mod \: 3 = 1 \)
• \( 2 \: mod \: 3 = 2 \)
• \( 3 \: mod \: 3 = 0 \)
• \( 4 \: mod \: 3 = 1 \)
• \( 5 \: mod \: 3 = 2 \)
• \( 6 \: mod \: 3 = 0 \)
• etc.

For example, if we look at \( 27 \: mod \: 5 \), modulo computes how many times 5 divides into 27 and then returns the remainder, which is 2 in this case. That is, \( 27 \: mod \: 5 = 2 \). But how do we get this result?

First, we compute how many times we can multiply 5 by an integer \( x \) so that the result is as close as possible to 27 without exceeding it. In other words, we find the maximum value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case, \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then, by subtracting 25 from 27, we get the answer: \( 27 - 25 = 2 \).

If the integer is negative, for example \( -27 \: mod \: 5 \), we have to do it slightly differently, and the answer is \( -27 \: mod \: 5 = 3 \). In this case, the integer \( x \) is negative and should be the closest integer such that \( 5 \cdot x \) does not exceed -27. That is, we find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Here, \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then, by subtracting -30 from -27, we get the answer: \( -27 - (-30) = -27 + 30 = 3 \).

It is important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \), etc., and NOT a fraction or decimal such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \), etc.

If two integers \( a \) and \( b \) modulo the same modulus \( c \) return the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). That is, if \( a \: mod \: c = r \) and \( b \: mod \: c = r \), then \( a \equiv b \: (mod \: c) \). Also, notice that if the modulus \( c \) is greater than the integer \( a \), i.e., \( c > a \), the result will always be \( a \: mod \: c = a \).

Properties of Modular Arithmetic

Modular arithmetic has several important properties that make it useful in cryptography:

• Addition: \((a + b) \: \text{mod} \: n = ((a \: \text{mod} \: n) + (b \: \text{mod} \: n)) \: \text{mod} \: n\)
• Subtraction: \((a - b) \: \text{mod} \: n = ((a \: \text{mod} \: n) - (b \: \text{mod} \: n)) \: \text{mod} \: n\)
• Multiplication: \((a \cdot b) \: \text{mod} \: n = ((a \: \text{mod} \: n) \cdot (b \: \text{mod} \: n)) \: \text{mod} \: n\)
• Exponentiation: \(a^b \: \text{mod} \: n = (a \: \text{mod} \: n)^b \: \text{mod} \: n\)

These properties allow us to perform calculations on smaller values rather than potentially very large ones, which is essential in cryptographic algorithms.

Modular Inverse

A modular inverse of an integer \(a\) with respect to modulus \(n\) is an integer \(a^{-1}\) such that:

\(a \cdot a^{-1} \equiv 1 \: (\text{mod} \: n)\)

The modular inverse exists if and only if \(a\) and \(n\) are coprime (i.e., their greatest common divisor is 1). Finding modular inverses is crucial in cryptography, particularly in algorithms like RSA where we need to find \(d\) such that \(e \cdot d \equiv 1 \: (\text{mod} \: \phi(n))\).

Important Theorems in Modular Arithmetic

Fermat's Little Theorem: If \(p\) is a prime number and \(a\) is not divisible by \(p\), then \(a^{p-1} \equiv 1 \: (\text{mod} \: p)\).

Euler's Theorem: If \(a\) and \(n\) are coprime, then \(a^{\phi(n)} \equiv 1 \: (\text{mod} \: n)\), where \(\phi(n)\) is Euler's totient function.

These theorems are fundamental to understanding and implementing many cryptographic algorithms, especially RSA.

Applications in Cryptography

Modular arithmetic is fundamental to many cryptographic algorithms:

• RSA: Relies on modular exponentiation for encryption and decryption
• Diffie-Hellman: Uses modular exponentiation for key exchange
• ElGamal: Employs modular arithmetic for public-key encryption
• Digital Signatures: Many signature schemes use modular operations
• Hash Functions: Often incorporate modular operations in their compression functions

A prime number is an integer greater than 1 that can only be divided evenly by 1 and itself. "Divided evenly" means the result is an integer, not a float. For example, if you divide 13 by 3, you get the float \( \frac{13}{3} = 4.333 \). We see that 13 is a prime number because it can only be divided evenly by 1 and itself: \( \frac{13}{1} = 13 \) and \( \frac{13}{13} = 1 \).

If an integer is not a prime number, it is called a composite number. For example, the integer 6 is a composite number because it can be divided evenly by 1, 2, 3, and 6:

\( \frac{6}{1} = 6 \), \( \frac{6}{2} = 3 \), \( \frac{6}{3} = 2 \), and \( \frac{6}{6} = 1 \)

The term "composite" means "something made by combining things." So, a composite number is an integer made by multiplying prime numbers:

• 2 is a prime
• 3 is a prime
• 4 is composite: \( 2 \cdot 2 = 4 \)
• 5 is a prime
• 6 is composite: \( 2 \cdot 3 = 6 \)
• 7 is a prime
• 8 is composite: \( 2 \cdot 2 \cdot 2 = 8 \)
• 9 is composite: \( 3 \cdot 3 = 9 \)
• etc.

Therefore, every integer greater than 1 is either a prime number or a product of prime numbers (a composite number).

The famous Greek mathematician Euclid proved that there are infinitely many prime numbers.

Michael Rabin and Gary Miller developed an algorithm that determines whether an integer is a prime or a composite number by testing the integer with multiple bases, denoted by \( a \). The algorithm is called the Rabin-Miller primality test.

The Fundamental Theorem of Arithmetic

Every integer greater than 1 can be expressed as a unique product of prime numbers (up to the order of the factors). This fundamental property makes prime numbers the "building blocks" of all natural numbers and is crucial for many cryptographic applications.

Importance in Cryptography

Prime numbers form the foundation of many cryptographic systems:

• RSA encryption relies on the difficulty of factoring the product of two very large primes
• Diffie-Hellman key exchange uses prime numbers to create secure shared secrets
• Elliptic curve cryptography often works over finite fields of prime order
• Digital signature algorithms like DSA and ECDSA use primes in their mathematical operations

Primality Testing

Determining whether a number is prime is crucial in cryptography. Several methods exist:

• Trial division: Dividing by all integers up to the square root (inefficient for large numbers)
• Fermat primality test: Based on Fermat's Little Theorem, but can be fooled by Carmichael numbers
• Miller-Rabin test: A probabilistic algorithm that can determine primality with high confidence
• AKS primality test: The first deterministic polynomial-time algorithm for primality testing

The Miller-Rabin test is particularly useful because it's efficient and can achieve any desired level of certainty by increasing the number of test rounds.

Special Types of Primes in Cryptography

• Safe primes: Primes p where (p-1)/2 is also prime. Used in Diffie-Hellman key exchange.
• Strong primes: Primes with certain properties that make them resistant to specific factoring algorithms, often used in RSA.
• Sophie Germain primes: Primes p where 2p+1 is also prime, useful for cryptographic applications.
• Mersenne primes: Primes of the form 2ⁿ-1, which allow for efficient arithmetic operations.

Definition

The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of the given integers without a remainder. It is denoted as \(\gcd(a, b)\) or sometimes as \((a, b)\).

Formally, for two integers \(a\) and \(b\), not both zero, \(\gcd(a,b)\) is the largest positive integer \(d\) such that \(d|a\) and \(d|b\) (where \(d|a\) means "\(d\) divides \(a\)" or "\(a\) is divisible by \(d\)").

Before we describe what the greatest common divisor of two integers is, we first define what we mean by a divisor. In this context, a divisor of an integer \( x \) is any integer that divides \( x \) evenly, meaning the result is not a fraction. For example, if you divide \( x=12 \) by 5, you get the fraction \( \frac{12}{5} = 2.4 \), so 5 is not a divisor of \( x=12 \). For \( x=12 \), the divisors are 1, 2, 3, 4, 6, and 12 because \( \frac{12}{1} = 12 \), \( \frac{12}{2} = 6 \), \( \frac{12}{3} = 4 \), \( \frac{12}{4} = 3 \), \( \frac{12}{6} = 2 \), and \( \frac{12}{12} = 1 \).

Similarly, the divisors of 16 are 1, 2, 4, 8, and 16 because \( \frac{16}{1} = 16 \), \( \frac{16}{2} = 8 \), \( \frac{16}{4} = 4 \), \( \frac{16}{8} = 2 \), and \( \frac{16}{16}=1 \).

The greatest common divisor of 12 and 16 is therefore 4, because it is the largest integer among their common divisors. In mathematics, we write this as \( \gcd(12, 16) = 4 \).

Two integers whose greatest common divisor is 1 are called relatively prime numbers or co-primes. For example, 15 and 28 are relatively prime because \( \gcd(15, 28) = 1 \) (note that 28 is not a prime number).

If one of the two integers is a prime number, the greatest common divisor will always be 1, i.e., \( \gcd(a, p) = 1 \), where \( a \) is any integer (either prime or composite) and \( p \) is a prime number.

Key Properties

• \(\gcd(a,b) = \gcd(b,a)\) (Commutativity)
• \(\gcd(a,b) = \gcd(a-b,b)\) when \(a \geq b\) (Subtraction property)
• \(\gcd(a,b) = \gcd(a \bmod b, b)\) when \(b \neq 0\) (Basis of the Euclidean algorithm)
• \(\gcd(a,0) = |a|\) for any \(a\) (Base case)
• If \(p\) is prime and \(p\) doesn't divide \(a\), then \(\gcd(a,p) = 1\)

One method to compute the greatest common divisor of two integers is by using the Euclidean algorithm, developed by the famous Greek mathematician Euclid. See "The extended Euclidean algorithm" for more information about how to compute the greatest common divisor of two integers.

The Euclidean Algorithm

The Euclidean algorithm is an efficient method to find the GCD of two integers. It works by repeatedly applying the division algorithm:

1. Start with two positive integers \(a\) and \(b\), where \(a \geq b\)
2. Divide \(a\) by \(b\) to get quotient \(q\) and remainder \(r\) such that \(a = bq + r\) where \(0 \leq r < b\)
3. If \(r = 0\), then \(\gcd(a,b) = b\)
4. Otherwise, set \(a = b\) and \(b = r\), and repeat from step 2

Example: Find \(\gcd(48, 18)\)

• \(48 = 18 \cdot 2 + 12\)
• \(18 = 12 \cdot 1 + 6\)
• \(12 = 6 \cdot 2 + 0\)

Since the remainder is now 0, \(\gcd(48, 18) = 6\).

Applications in Cryptography

The GCD has several important applications in cryptography:

• Key Generation: In RSA, we need to find two numbers \(e\) and \(d\) such that \(ed \equiv 1 \pmod{\phi(n)}\), which requires \(\gcd(e, \phi(n)) = 1\)
• Primality Testing: Many primality tests use GCD calculations
• Modular Arithmetic: Finding modular inverses (via the extended Euclidean algorithm) requires co-prime numbers
• Factorization Attacks: Some attacks on cryptosystems use GCD calculations to factor large numbers

Definition and Purpose

The extended Euclidean algorithm is an extension of the Euclidean algorithm, which only returns the greatest common divisor of two integers. Given two integers \( a \) and \( b \), the extended Euclidean algorithm returns the integers \( a \), \( b \), \( \lambda \), and \( \mu \) such that:

\( a \cdot \lambda + b \cdot \mu = \gcd(a, b) \)

Here, \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime, i.e., \( \gcd(a, b) = 1 \), then:

\( a \cdot \lambda + b \cdot \mu = 1 \)

In this case, \( \lambda \; mod \; b \) is the inverse of \( a \), denoted \( a^{-1} = \lambda \; mod \; b \), and \( \mu \: mod \: a \) is the inverse of \( b \), denoted \( b^{-1} = \mu \: mod \: a \) (see "Modulo computation" for more information about the \( mod \) operator). One useful property of an integer and its inverse is that \( a \cdot a^{-1} \; mod \; b = 1 \) and \( b \cdot b^{-1} \; mod \; a = 1 \).

Example

You can easily compute \( \gcd(a, b) \), \( \lambda \), and \( \mu \) for example with \( a=5 \) and \( b=39 \) using a simple table. First, let us create a table with three columns (we do not yet know how many rows there will be). Let us denote the entry in the first row and first column as [1,1], the entry in the first row and second column as [1,2], the entry in the second row and first column as [2,1], and so on.

Next, we write \( b=39 \) in entry [1,1] and \( a=5 \) in entry [2,1]. Then we try to find the largest integer \( q_{1} \) such that \( q_{1} \cdot a \leq b \). We have \( q_{1}=7 \), which we write in entry [2,2], because \( 7 \cdot 5 = 35 \leq 39 \), and a remainder of \( r_{1}=4 \), which we write in entry [3,1].

Again, we try to find the largest integer \( q_{2} \) such that \( q_{2} \cdot r_{1} \leq a \). We have \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \), and a remainder of \( r_{2}=1 \), which we write in entry [4,1]. Notice that we are repeating the same process as before, just with the numbers in the next row.

The next computation returns a remainder of \( r_{3} = 0 \) because \( q_{3} \cdot r_{2} = 4 \cdot 1 = 4 \leq 4 = r_{1} \). We have now computed \( \gcd(5, 39)=r_{2}=1 \) since \( r_{3} = 0 \). Because 5 and 39 are relatively prime, we know that \( \lambda \) and \( \mu \) exist, and we can start using the last column.

First, we write \( x_{1}=0 \) in entry [4,3] and \( x_{2}=1 \) in entry [3,3]. Then we write \( x_{3}=q_{2} \cdot x_{2} + x_{1} = 1 \cdot 1 + 0 = 1 \) in entry [2,3]. For entry [1,3], we compute as before, just with numbers from the row above, i.e., \( x_{4}=q_{1} \cdot x_{3} + x_{2} = 7 \cdot 1 + 1 = 8 \).

Finally, we have that \( a \cdot x_{4} \pm b \cdot x_{3} = r_{2} \), where we need to decide whether it should be plus or minus between the two terms. Because \( a \cdot x_{4} = 5 \cdot 8 = 40 \), \( b \cdot x_{3} = 39 \cdot 1 \), and \( 40 \geq 39 \), we have \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)), so the Bézout coefficients are \( \lambda=8 \) and \( \mu=-1 \). Notice that \( a^{-1} = \lambda \; mod \; b = 8 \; mod \; 39 = 8\) and \( b^{-1} = \mu \; mod \; a = -1 \: mod \: 5 = 4\), where \( a \cdot a^{-1} \; mod \; b = 5 \cdot 8 \; mod \; 39 = 1 \) and \( b \cdot b^{-1} \; mod \; a = 39 \cdot 4 \; mod \; 5 = 1 \).

Table for the example

The table for computing \( 5 \cdot \lambda + 39 \cdot \mu = \gcd(5, 39) \) is:

Algorithm in Pseudocode

function extended_gcd(a, b)
    if b = 0 then
        return (a, 1, 0)
    else
        (d, x', y') = extended_gcd(b, a mod b)
        return (d, y', x' - (a div b) * y')

The function returns a tuple (d, x, y) such that d = gcd(a, b) and d = ax + by.

Applications in Cryptography

• RSA Key Generation: Computing the private key d where d ≡ e^-1 (mod φ(n)) requires finding the modular inverse of the public exponent e
• Chinese Remainder Theorem: Finding solutions to systems of modular congruences, which enables efficient RSA implementations
• Elliptic Curve Cryptography: Computing point addition and scalar multiplication operations
• Digital Signatures: Many schemes require modular inverse calculations
• Key Exchange Protocols: Used in various secure communication protocols

Relation to the Basic Euclidean Algorithm

While the standard Euclidean algorithm computes only the GCD through successive divisions, the extended version keeps track of the coefficients at each step. This "extension" allows us to express the GCD as a linear combination of the original numbers, which is crucial for finding modular inverses.

Computational Complexity

The extended Euclidean algorithm has the same time complexity as the standard Euclidean algorithm: O(log min(a,b)). This makes it highly efficient even for very large integers, which is crucial for its application in cryptographic systems.

In abstract algebra, a ring is a set with two operations (usually addition and multiplication) where addition forms an abelian group and multiplication is associative and distributes over addition. A group is a set with a single operation that satisfies closure, associativity, identity, and inverse properties.

Integers and Modular Arithmetic

The set of integers \( \{ \dots, -2, -1, 0, 1, 2, \dots \} \) is denoted by the symbol \( \mathbb{Z} \), i.e., \( \mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \} \), and is called the ring of integers or an additive group. The group of integers modulo \( n \) is a subset of \( \mathbb{Z} \) and is denoted by \( \mathbb{Z}/n\mathbb{Z} \), but we use the shorthand \( \mathbb{Z}_{n} \). This subset contains the following elements (because we compute modulo \( n \)):

\( \mathbb{Z}_{n} = \{ 0, 1, 2, \dots, n - 1 \}\)

Notice that whenever we perform addition or multiplication in \( \mathbb{Z}_{n} \), we always compute the result modulo \( n \) to obtain an integer in \( \mathbb{Z}_{n} \). To illustrate this, let us look at \( n = 5 \):

\( \mathbb{Z}_{5} = \{ 0, 1, 2, 3, 4 \}\)

When adding \( 3 \) and \( 4 \) in \( \mathbb{Z}_{5} \), we do the following: \( (3 + 4) \: mod \: 5 = 7 \: mod \: 5 = 2 \). Likewise, when multiplying \( 3 \) by \( 4 \) in \( \mathbb{Z}_{5} \), we have: \( (3 \cdot 4) \: mod \: 5 = 12 \: mod \: 5 = 2 \).

Units and Multiplicative Groups

An integer \( a \) in \( \mathbb{Z}_{n} \) has an inverse if the greatest common divisor of \( a \) and \( n \) is 1, i.e., \( \gcd(a, n) = 1 \) (see "The extended Euclidean algorithm" for more information). The integer \( a \) is then called a unit. The set of units (all integers with an inverse in \( \mathbb{Z}_{n} \)) is denoted by \( (\mathbb{Z}/n\mathbb{Z})^{*} \). Again, we use the shorthand \( \mathbb{Z}_{n}^{*} \). If \( a_{1} \) and \( a_{2} \) are units, then their product \( (a_{1} \cdot a_{2}) \: mod \: n \) is also always a unit (i.e., \( a_{1} \cdot a_{2} \) is in the group \( \mathbb{Z}_{n}^{*} \)), but the sum \( (a_{1} + a_{2}) \: mod \: n \) may NOT be a unit (i.e., \( a_{1} + a_{2} \) is in \( \mathbb{Z}_{n} \) but may not be in \( \mathbb{Z}_{n}^{*} \)). We see the difference in the two sets \( \mathbb{Z}_{8} \) and \( \mathbb{Z}_{8}^{*} \):

• \( \mathbb{Z}_{8} = \{ 0, 1, 2, 3, 4, 5, 6, 7 \}\)
• \( \mathbb{Z}_{8}^{*} = \{ 1, 3, 5, 7 \} \)

If we choose \( n \) to be a prime number \( p \), then for all integers \( a \) except 0 in \( \mathbb{Z}_{p} \), we have \( \gcd(a, p) = 1 \), which means that \( \mathbb{Z}_{p}^{*} \) contains all integers from \( \mathbb{Z}_{p} \) except 0, i.e.:

\( \mathbb{Z}_{p}^{*} = \{ 1, 2, 3, \dots, p - 1 \}\)

For example, for \( p=7 \), the only difference between the two sets \( \mathbb{Z}_{7} \) and \( \mathbb{Z}_{7}^{*} \) is the integer 0:

• \( \mathbb{Z}_{7} = \{ 0, 1, 2, 3, 4, 5, 6 \}\)
• \( \mathbb{Z}_{7}^{*} = \{ 1, 2, 3, 4, 5, 6 \} \)

Euler's Phi Function

The number of elements in \( \mathbb{Z}_{n}^{*} \) is denoted by \( \phi(n) \), named after the famous Swiss mathematician Euler, and is called Euler's phi function. As we saw previously, if \( n \) is a prime number \( p \), then \( \phi(p) = p-1 \). The number of elements in a group \( G \) is also called the order of \( G \) and is written as \( \left| G \right| \). The order of:

• \( \mathbb{Z}_{n} \) is \( \left| \mathbb{Z}_{n} \right| = n \) where \( n \) is a composite number
• \( \mathbb{Z}_{n}^{*} \) is \( \left| \mathbb{Z}_{n}^{*} \right| = \phi(n) \) where \( n \) is a composite number
• \( \mathbb{Z}_{n}^{*} \) is \( \left| \mathbb{Z}_{n}^{*} \right| = \phi(n) = (p-1) \cdot (q-1) \) where \( n = p \cdot q \) and \( p \) and \( q \) are prime numbers
• \( \mathbb{Z}_{p}^{*} \) is \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \) where \( p \) is a prime number

Euler's phi function \(\phi(n)\) can be computed efficiently when the prime factorization of \(n\) is known:

For a prime power \(p^k\): \(\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})\)

For a product of prime powers: \(\phi(n) = n \prod_{p|n} (1 - \frac{1}{p})\)

For example, \(\phi(36) = \phi(2^2 \cdot 3^2) = 36 \cdot (1 - \frac{1}{2}) \cdot (1 - \frac{1}{3}) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12\)

Modular Exponentiation Rules

If, for example, we choose the elements \( x \), \( a \), and \( b \) from the group \( \mathbb{Z}_{p}^{*} \) and want to compute \( x^{a + b} \: mod \: p \), then in the exponent we actually compute \( a + b \) modulo the order of the group, i.e., \( a + b \: mod \: (p-1) \) because \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \). So, what we actually compute is \( x^{a + b \: mod \: (p-1)} \: mod \: p \). The same is true if we had chosen one of the other groups: we always compute modulo the order of the group in the exponent. Therefore, next time you look at an equation from a cryptosystem and wonder why they suddenly compute, for example, modulo \( p-1 \) instead of modulo \( p \), it is because the equation is used in the exponent of some integer.

Units are particularly important in cryptography because they have multiplicative inverses, allowing operations like division in modular arithmetic. The existence of these inverses is crucial for many cryptographic algorithms, including RSA, where we need to find values \(e\) and \(d\) such that \(e \cdot d \equiv 1 \pmod{\phi(n)}\).

Important Theorems

Fermat's Little Theorem: If \(p\) is a prime number and \(a\) is not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\).

Euler's Theorem: For any coprime integers \(a\) and \(n\), \(a^{\phi(n)} \equiv 1 \pmod{n}\). This generalizes Fermat's Little Theorem and forms the mathematical foundation of the RSA cryptosystem.

Applications in Cryptography

• RSA: Uses the fact that \(m^{ed} \equiv m \pmod{n}\) when \(ed \equiv 1 \pmod{\phi(n)}\)
• Diffie-Hellman: Operates in the multiplicative group \(\mathbb{Z}_p^*\) where \(p\) is prime
• ElGamal: Relies on modular exponentiation in \(\mathbb{Z}_p^*\)
• Digital Signatures: Many schemes use properties of these groups for verification

Formal Statement

Let \(m_1, m_2, \ldots, m_k\) be pairwise coprime positive integers (meaning \(\gcd(m_i, m_j) = 1\) for all \(i \neq j\)). Then for any given integers \(a_1, a_2, \ldots, a_k\), there exists a unique solution \(x\) modulo \(M = m_1 \cdot m_2 \cdot \ldots \cdot m_k\) to the system of congruences:

\begin{align} x &\equiv a_1 \pmod{m_1} \ x &\equiv a_2 \pmod{m_2} \ &\vdots \ x &\equiv a_k \pmod{m_k} \end{align}

Example

Consider the system:

• \(x \equiv 2 \pmod{3}\)
• \(x \equiv 3 \pmod{5}\)
• \(x \equiv 2 \pmod{7}\)

To solve this using CRT:

1. Calculate \(M = 3 \cdot 5 \cdot 7 = 105\)
2. For each modulus \(m_i\), calculate \(M_i = M/m_i\):
   • \(M_1 = 105/3 = 35\)
   • \(M_2 = 105/5 = 21\)
   • \(M_3 = 105/7 = 15\)
3. Compute \(M_i^{-1}\) (the multiplicative inverse of \(M_i\) modulo \(m_i\)):
   • \(35^{-1} \equiv 2 \pmod{3}\) (since \(35 \cdot 2 = 70 \equiv 1 \pmod{3}\))
   • \(21^{-1} \equiv 1 \pmod{5}\) (since \(21 \cdot 1 = 21 \equiv 1 \pmod{5}\))
   • \(15^{-1} \equiv 1 \pmod{7}\) (since \(15 \cdot 1 = 15 \equiv 1 \pmod{7}\))
4. The solution is \(x = \sum a_i \cdot M_i \cdot M_i^{-1} \mod M\):
   • \(x = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 \equiv 23 \pmod{105}\)

Therefore, \(x = 23\) is the solution to the system.

Applications in Cryptography

The Chinese Remainder Theorem has several important applications in cryptography:

• RSA Speedup: In RSA, computing \(m^d \mod n\) can be accelerated by separately computing \(m^d \mod p\) and \(m^d \mod q\) and then combining the results using CRT.
• Secret Sharing: Shamir's Secret Sharing and other threshold schemes use principles related to CRT.
• Multi-prime RSA: Variants of RSA that use more than two primes utilize CRT for efficient computation.

Definition

Let \( n \) be the product of two large prime numbers \( p \) and \( q \), i.e. \( n = p \cdot q \). Then, if you know the value of \( n \) it's hard to compute \( p \) and \( q \) from \( n \).

The problem of computing \( p \) and \( q \) is called the prime factorization problem.

Computational Hardness

What makes the prime factorization problem difficult is that while multiplication is easy (computing \(n = p \cdot q\) is straightforward), the reverse operation of factoring has no known efficient classical algorithm. The computational complexity grows exponentially with the number of bits in \(n\).

Simple Example

For small numbers, factorization is trivial: If \(n = 15\), we can easily find \(p = 3\) and \(q = 5\).

However, when the primes are large (hundreds of digits), factoring becomes practically impossible with current classical computing methods. For example, factoring a 2048-bit RSA modulus would take billions of years using the best-known algorithms.

Factorization Algorithms

• Trial Division: Simply try dividing by all primes up to \(\sqrt{n}\). Extremely inefficient for large numbers.
• Pollard's Rho: A probabilistic algorithm good for finding small factors.
• Quadratic Sieve: More efficient for numbers up to 100 digits.
• General Number Field Sieve (GNFS): Currently the most efficient algorithm for factoring large integers (>100 digits).

Importance in Cryptography

The security of the RSA cryptosystem fundamentally depends on the hardness of the prime factorization problem:

• The public key contains \(n = p \cdot q\) while the private key requires knowledge of \(p\) and \(q\)
• If an attacker could efficiently factor \(n\), they could derive the private key and break the encryption
• By choosing sufficiently large primes (typically 1024 bits or larger each), the factorization becomes computationally infeasible

The Quantum Threat

In 1994, Peter Shor developed a quantum algorithm that can factor integers in polynomial time. If large-scale quantum computers become available, they could break RSA encryption by efficiently solving the prime factorization problem. This threat has motivated research into post-quantum cryptography algorithms that aren't vulnerable to quantum attacks.

Current Records

As of 2023, the largest RSA number factored using general methods is RSA-250 (829 bits), which was factored in February 2020. Current cryptographic recommendations suggest using RSA keys of at least 2048 bits for security through the next decade.

Chosen Plaintext Attack (CPA) Security

The security of an asymmetric (public-key) cryptosystem, such as RSA or ElGamal, is measured with respect to chosen plaintext attacks (CPA) and chosen ciphertext attacks (CCA).

In a chosen plaintext attack (sometimes called a semantic attack), Alice and Bob's adversary, Eve, is passive; she only observes the ciphertexts sent between Alice and Bob and tries to guess the plaintexts. An asymmetric cryptosystem is considered CPA-secure if Eve's advantage in correctly guessing the plaintext in the following game is negligible:

Eve sends a message \( m \) to an oracle, which returns a ciphertext \( c \) that is either an encryption of \( m \) or a random message of the same length as \( m \). Eve then tries to guess what \( c \) is an encryption of.

Therefore, if an asymmetric cryptosystem is CPA-secure, the only information that a ciphertext reveals is the length of the encrypted message.

Formally, Eve's "advantage" in these security games is defined as the absolute difference between 1/2 and the probability that Eve correctly guesses whether she received an encryption of her chosen message: |Pr[Eve wins] - 1/2|. We say this advantage is "negligible" if it decreases faster than any polynomial in the security parameter (typically the key length).

Chosen Ciphertext Attack (CCA) Security

In a chosen ciphertext attack, Eve is active, making this a stronger attack compared to a chosen plaintext attack. Now, Eve can have ciphertexts decrypted by the oracle. An asymmetric cryptosystem is considered CCA-secure if Eve's advantage in correctly guessing the plaintext in the following game is negligible:

Eve sends a ciphertext \( c_{i} \) to an oracle, which returns the decrypted message \( m_{i} \) of \( c_{i} \). This can be repeated as many times as Eve wants. Then, Eve sends a message \( m \) to the oracle, which returns a ciphertext \( c \) that is either an encryption of \( m \) or a random message of the same length as \( m \). Finally, Eve sends a ciphertext \( c_{i}' \), which must be different from \( c \), to the oracle, and it returns the decrypted message \( m_{i}' \) of \( c_{i}' \). This can also be repeated as many times as Eve wants. Eve then tries to guess what \( c \) is an encryption of.

Again, if an asymmetric cryptosystem is CCA-secure, the only information that a ciphertext reveals is the length of the encrypted message.

In cryptographic security models, an "oracle" refers to a theoretical entity that performs certain cryptographic operations (like encryption or decryption) when queried. It represents the capability an attacker might have to interact with the cryptosystem.

Cryptographers further distinguish between two levels of CCA security:

• CCA1 (non-adaptive CCA): Eve can only query the decryption oracle before receiving the challenge ciphertext.
• CCA2 (adaptive CCA): Eve can query the decryption oracle both before and after receiving the challenge ciphertext (except for the challenge ciphertext itself), as described in our game above.

CCA2 security is considered the gold standard for modern asymmetric encryption schemes.

Security of Common Asymmetric Cryptosystems

• Basic RSA (textbook RSA) is neither CPA nor CCA secure
• RSA-OAEP (Optimal Asymmetric Encryption Padding) is designed to be CCA2-secure under certain assumptions
• Basic ElGamal is CPA-secure but not CCA-secure
• Modern elliptic curve cryptosystems like ECIES can achieve CCA2 security when properly implemented

Real-world Implications

The distinction between CPA and CCA security matters significantly in practice:

• Systems that are only CPA-secure may be vulnerable to attacks where the adversary can trick legitimate users into decrypting specially crafted messages
• For applications like secure messaging or financial transactions, CCA2-security is typically required
• In some constrained environments where decryption queries are impossible for an attacker, CPA security might be sufficient

The security of digital signatures, such as RSA and ElGamal, is typically measured using the concept of Existential Unforgeability under Chosen Message Attack (EUF-CMA), which is analogous to CPA security for encryption schemes.

In a chosen plaintext attack, Alice and Bob's adversary, Eve, is passive; she only observes the messages and signatures exchanged between Alice and Bob and tries to forge a signature. A digital signature scheme is considered CPA-secure if Eve's advantage in forging a signature in the following game is negligible:

Eve sends a message \( m_{i} \) to an oracle (which represents the legitimate signer's capabilities), which returns its signature \( \sigma_{i} \). This process can be repeated as many times as Eve wishes. Finally, Eve outputs a message \( m \), which must be different from all previously queried messages \( m_{i} \), along with a signature \( \sigma \). Eve wins the game if \( \sigma \) is a valid signature for the message \( m \).

Types of Signature Forgeries

Cryptographers classify forgeries into several types:

• Existential forgery: The adversary can forge a signature for at least one message (possibly meaningless)
• Selective forgery: The adversary can forge a signature for a specific message of their choosing
• Universal forgery: The adversary can forge signatures for any message
• Total break: The adversary can recover the signer's private key

Real-world Implications of Signature Security

Secure digital signatures are critical in many applications:

• Code signing to verify software authenticity
• Certificate authorities in PKI infrastructure
• Non-repudiation in legal documents and financial transactions
• Blockchain transactions

If a signature scheme is vulnerable to forgery attacks, these systems could be compromised.

Security of Common Digital Signature Schemes

• RSA signatures (plain, without hashing) are vulnerable to existential forgery
• RSA-PSS (Probabilistic Signature Scheme) provides provable security under reasonable assumptions
• DSA and ECDSA are EUF-CMA secure if the underlying hash function is collision-resistant
• EdDSA (like Ed25519) offers strong security with additional benefits like deterministic signing

The Role of Hash Functions in Signature Security

Most secure signature schemes operate on hashed messages rather than raw messages. This serves two purposes:

• It allows signing messages of arbitrary length
• It prevents mathematical attacks that exploit the algebraic structure of the signature algorithm

The security of the signature scheme depends heavily on the security of the underlying hash function.