Introduction to Number Theory

Fermat’s Little Theorem

Fermat’s Little Theorem is a fundamental theorem in number theory that states:
If p is a prime number and a is any integer not divisible by p, then:

In other words, the remainder when   is divided by p is 1.

This theorem is widely used in public-key cryptography algorithms like RSA, primarily to perform efficient modular exponentiation and check for primality.

Why Fermat’s Little Theorem?

In RSA, Fermat’s Little Theorem simplifies computations by reducing powers modulo a prime. This efficiency is critical in real-world cryptography, where numbers are extremely large (hundreds of digits). Fermat’s theorem ensures correctness and efficiency in these computations.

Application in RSA Cryptography

RSA relies on modular arithmetic, and Fermat’s Little Theorem provides a shortcut to compute powers modulo ppp, which is computationally expensive for large numbers.

Key Steps in RSA Using Fermat’s Little Theorem:

1. Key Generation:
   • Choose two large prime numbers p and q.
   • Compute     (the modulus).
   • Calculate ϕ(n)= (p−1)(q−1) (Euler’s totient function).
   • Select an encryption key eee such that   and 
   • Compute the decryption key d such that  (modular inverse).
2. Encryption:
   • Given a plaintext M, compute the ciphertext C using 
   • Decryption:
     • Retrieve the plaintext M from C   

Example: Using Fermat’s Little Theorem

Problem: Encrypt and decrypt a message using RSA with Fermat’s Little Theorem.

1. Key Generation:
   • Choose p=7, q=11 (prime numbers).
   • Compute n=7 × 11= 77
   • Compute 
   • Choose e=1 (public key, gcd(17, 60) = 1)
   • Compute  
2. Encryption:
   • Message M=8.
   • Compute  
   • 
   • 
   • 
   • 
   •   So, C=43
3. Decryption:
   • Compute  M                      
   • 
   • 
   • 
   • 
   • Continue reducing until  
   • Recovered message M=8 

Output

1. Public Key: (e,n) = (17,77)
2. Private Key: (d,n) = (53,77)
3. Ciphertext: C=43C = 43C=43
4. Decrypted Message: M = 8

Euler’s Theorem

Euler’s Theorem asserts that for any integer aaa that is coprime to a positive integer mmm, the remainder when  is divided by m is 1. The reason we emphasize proving Euler’s Theorem is that Fermat’s Theorem is, in fact, a special case of it. This connection arises because when p is a prime number,  which makes Fermat’s Theorem a subset of Euler’s Theorem under these circumstances.

Euler’s Theorem is a crucial result in number theory, named after the Swiss mathematician Leonhard Euler. It reveals an important relationship between number-theoretic functions and modular arithmetic concepts. In this article, we will explore Euler’s Theorem, including its statement and proof.

Proof of Euler’s Theorem

For some a_i in {a₁, . . . , a_k}
Since this is the same set of numbers mod n as the original system, the two systems must have the same product mod n:

Now each a_i is invertible mod n, so multiplying both sides by   

Euler’s Theorem Formula

The statement of Euler’s Theorem can also serve as a formula for further calculations:

Where:

• a is any integer coprime to n
• n is a positive integer
• ϕ(n) is Euler’s totient function
• ≡ denotes equivalence
• mod n represents congruence modulo n

Example Showing Euler’s Theorem Formula

Problem: Verify Euler’s Theorem for a = 3 and n = 8.

Solution:

First, we calculate ϕ(8). The numbers less than 8 that are coprime to 8 are 1, 3, 5, and 7. Thus, ϕ(8)=4.
Next, calculate 3⁴ and find its remainder when divided by 8
3⁴ = 81
Now, find 81 mod 8
81 mod 8 ≡ 1
Thus, 3⁴ ≡ 1 (mod 8), which verifies Euler’s Theorem.

Applications of Euler’s Theorem

Euler’s Theorem has numerous applications across mathematics and other fields. Some notable uses include:

• RSA Encryption: Euler’s theorem is a cornerstone of modern cryptography, especially the RSA encryption algorithm. RSA involves generating public and private keys such that they are modular inverses modulo , where is the product of two large prime numbers.
• Problem Solving in Number Theory: Euler’s theorem is invaluable in solving number theory problems related to divisibility, remainders, and number properties in various systems.
• Primality Testing: Euler’s theorem is employed in primality testing algorithms, such as the Fermat primality test. Although this test can produce false positives for Carmichael numbers, it provides a quick way to identify non-prime numbers. If , then is not prime.
• Mathematical Proofs: Euler’s theorem serves as a general case for proofs involving modular arithmetic, divisibility tests, and number theory identities. It offers a robust foundation for rigorous mathematical arguments.

Euler’s Theorem Examples

Example 1: Find the remainder when 5¹⁰⁰ divided by 7.

Solution:

Since 7 is a prime number, ϕ(7) = 7−1 = 6

According to Euler’s can be rewritten as 

Now,

Using modular exponentiation:

Simplify 

So, when 5¹⁰⁰  is divided by 7, the remainder is 2.

Chinese Remainder Theorem

We are given two arrays num[0..k-1] and rem[0..k-1]. In the array num[0..k-1], every pair of numbers is coprime (i.e., the greatest common divisor for each pair is 1). Our task is to find the smallest positive integer x such that:

x % num[0] = rem[0],
x % num[1] = rem[1],
...
x % num[k-1] = rem[k-1].

In essence, we are provided with k numbers, all of which are pairwise coprime, along with the remainders when an unknown number x is divided by these numbers. We need to determine the minimum possible value of x that satisfies all the given conditions.

Example 1:

• Input:
  num[] = {5, 7},
  rem[] = {1, 3}
• Output:
  31
  Explanation: 31 is the smallest number such that:
  • When divided by 5, the remainder is 1.
  • When divided by 7, the remainder is 3.

Example 2:

• Input:
  num[] = {3, 4, 5},
  rem[] = {2, 3, 1}
• Output:
  11
  Explanation: 11 is the smallest number such that:
  • When divided by 3, the remainder is 2.
  • When divided by 4, the remainder is 3.
  • When divided by 5, the remainder is 1.

RC4 is a stream cipher and a variable-length key encryption algorithm. It encrypts data one byte at a time (or sometimes in larger units). Using a pseudorandom bit generator, it produces an 8-bit key stream that is unpredictable without the input key. This key stream is combined with the plaintext one byte at a time using the XOR operation.

Example:

• RC4 Encryption:
  10011000 XOR 01010000 = 11001000
• RC4 Decryption:
  11001000 XOR 01010000 = 10011000

Chinese Remainder Theorem:

The Chinese Remainder Theorem guarantees that a solution always exists for this system of congruences. The first part of the theorem ensures that a solution exists, and the second part states that all solutions will produce the same remainder when divided by the product of num[0], num[1], ... , num[k-1]. For example, in the above case, the product of 3, 4, and 5 is 60, and 11 is one solution. Other solutions are of the form 11 + m*60 where m >= 0.

A naive approach to solve this problem is to start with 1 and increment it one by one, checking if dividing it by the numbers in num[] produces the corresponding remainders in rem[]. Once we find such an x, we return it. Below is the implementation using this approach.

Futheremore, all solutions of x of this system are congruent modulo the product, 

Python Code (Naive Approach):

# A Python3 program to demonstrate
# working of Chinese Remainder Theorem

# k is size of num[] and rem[].
# Returns the smallest number x
# such that:
# x % num[0] = rem[0],
# x % num[1] = rem[1],
# ..................
# x % num[k-2] = rem[k-1]
# Assumption: Numbers in num[]
# are pairwise coprime (gcd for
# every pair is 1)
def findMinX(num, rem, k):
    x = 1  # Initialize result

    # As per the Chinese remainder
    # theorem, this loop will
    # always break.
    while True:

        # Check if remainder of
        # x % num[j] is rem[j]
        # or not (for all j from
        # 0 to k-1)
        j = 0
        while j < k:
            if x % num[j] != rem[j]:
                break
            j += 1

        # If all remainders
        # matched, we found x
        if j == k:
            return x

        # Else try next number
        x += 1

# Driver Code
num = [3, 4, 5]
rem = [2, 3, 1]
k = len(num)
print("x is", findMinX(num, rem, k))

Output:

x is 11

Pseudo-Random Generation Algorithm (PRGA)

Once the vector S is initialized, the input key is no longer used. The algorithm continues by cyclically permuting S and generating a key stream byte k.

x % num[0] = rem[0],
x % num[1] = rem[1],
...
x % num[k-1] = rem[k-1].

Encrypt Using XOR:
RC4 encrypts plaintext by XORing it with the generated key stream.

News on RC4

In September 2015, Microsoft announced the discontinuation of RC4 support in Microsoft Edge and Internet Explorer 11.

Features of the RC4 Algorithm

• Symmetric key encryption: RC4 uses the same key for encryption and decryption.
• Stream cipher: It encrypts and decrypts data byte by byte, generating a pseudorandom key stream XORed with the plaintext to produce ciphertext.
• Flexible key size: RC4 supports key sizes from 40 to 2048 bits, making it adaptable to varying security needs.
• High speed: It is a fast algorithm, ideal for applications requiring rapid data encryption.
• Extensive usage: Historically, RC4 was used in wireless networks, SSL, VPNs, and file encryption.
• Vulnerabilities: Known issues, such as biases in the initial key stream, make it unsuitable for new applications.

Advantages of RC4

• Efficiency: RC4 is highly efficient and suitable for use in low-power devices or scenarios requiring quick encryption.
• Simplicity: The algorithm’s design is straightforward, enabling easy implementation in both software and hardware.
• Adaptable key size: RC4’s variable key size allows it to meet diverse security requirements.
• Historical adoption: It was widely used in applications such as SSL, VPNs, and file encryption.

Disadvantages of RC4

• Vulnerabilities: Known weaknesses, including key stream biases, make RC4 susceptible to key recovery attacks.
• Security limitations: Its design has inherent flaws, making it less secure compared to modern algorithms like AES or ChaCha20.
• Restricted key length: The maximum key length of 2048 bits may not suffice for applications requiring stronger encryption.
• Deprecated usage: Due to its vulnerabilities, RC4 is no longer recommended for new implementations. Modern stream ciphers such as AES-CTR or ChaCha20 are preferred.

Implementation of RC4 algorithm

RC4 is a symmetric stream cipher with a variable key length that is used for both encryption and decryption. It achieves this by XORing the data stream with a generated key sequence. The algorithm operates in two distinct phases:

Key Scheduling Algorithm (KSA)

1. This phase creates a State array by applying a permutation based on a variable-length key (0 to 256 bytes).
2. The key is stored in K[0] to K[255].If the key length is less than 256 bytes, repeat the key values.
3. Perform permutations:

• • For i = 0 to 255:
    • S[i] = i
    • K[i] = key[i mod key_length]
  • Swap elements using the formula:
    • j = (j + S[i] + K[i]) mod 256
    • Swap S[i] and S[j].

Pseudo-Random Generation Algorithm (PRGA)

After the State array is initialized, PRGA generates the keystream for encryption and decryption. In this phase:

1. Maintain counters iii and jjj, initially set to 0.
2. For each output byte:
   • Increment iii: i=(i+1)mod  256i = (i + 1) \mod 256i=(i+1)mod256
   • Update jjj: j=(j+S[i])mod  256j = (j + S[i]) \mod 256j=(j+S[i])mod256
   • Swap S[i]S[i]S[i] and S[j]S[j]S[j].
   • Calculate the keystream byte: t=(S[i]+S[j])mod  256t = (S[i] + S[j]) \mod 256t=(S[i]+S[j])mod256 and keystreamByte=S[t]keystreamByte = S[t]keystreamByte=S[t].

Example Inputs and Outputs

Example 1:

• Input: Plain text = 001010010010, Key = 101001000001, n=3n = 3n=3
• Output:
  • Cipher text = 110011100011
  • Decrypted text = 001010010010

Example 2:

• Input: Plain text = 1111000000001111, Key = 0101010111001010, n=4n = 4n=4
• Output:
  • Cipher text = 0011011110100010
  • Decrypted text = 1111000000001111

Implementation in Python

The code below demonstrates encryption and decryption with detailed outputs of each step, including initialization, key scheduling, keystream generation, and XOR operations for both encryption and decryption.

# Python3 implementation of RC4 algorithm

def encryption():
    global key, plain_text, n
    plain_text = "110101001011"
    key = "101100110011"
    n = 4

    print("Plaintext:", plain_text)
    print("Key:", key)
    print("n:", n)

    S = [i for i in range(2 ** n)]
    print("State Vector (S):", S)

    key_list = [key[i:i + n] for i in range(0, len(key), n)]
    for i in range(len(key_list)):
        key_list[i] = int(key_list[i], 2)

    pt = [plain_text[i:i + n] for i in range(0, len(plain_text), n)]
    for i in range(len(pt)):
        pt[i] = int(pt[i], 2)

    print("Plaintext Array:", pt)

    diff = len(S) - len(key_list)
    for i in range(diff):
        key_list.append(key_list[i])

    print("Key List:", key_list)

    def KSA():
        j = 0
        for i in range(len(S)):
            j = (j + S[i] + key_list[i]) % len(S)
            S[i], S[j] = S[j], S[i]

    KSA()

    def PRGA():
        i = j = 0
        keystream = []
        for _ in range(len(pt)):
            i = (i + 1) % len(S)
            j = (j + S[i]) % len(S)
            S[i], S[j] = S[j], S[i]
            t = (S[i] + S[j]) % len(S)
            keystream.append(S[t])
        return keystream

    keystream = PRGA()

    cipher_text = [keystream[i] ^ pt[i] for i in range(len(pt))]
    cipher_bits = "".join(f"{bin(c)[2:]:0{n}b}" for c in cipher_text)

    print("Ciphertext:", cipher_bits)

encryption()

Output:

Plaintext: 110101001011
Key: 101100110011
n: 4

State Vector (S): [0, 1, 2, ..., 15]
Plaintext Array: [13, 10, 4, 11]
Key List: [11, 12, 3, 11, 11, 12, 3, 11]

Ciphertext: 011001101110