Introduction

In our last post, we wrote some Python functions in preparation to implement the RSA algorithm. In this post, we will implement the RSA algorithm.

Program On The Receiver’s Side

Create the public and private keys. Share the public key with the sender.

import random
from sympy import isprime

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def modinv(a, m):
    m0, x0, x1 = m, 0, 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        m, a = a % m, m
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += m0
    return x1

def generate_prime_candidate(length):
    p = random.getrandbits(length)
    # Apply a mask to set MSB and LSB to 1 to ensure a proper length prime
    p |= (1 << length - 1) | 1
    return p

def generate_large_prime(length=1024):
    p = 4
    while not isprime(p):
        p = generate_prime_candidate(length)
    return p

def generate_keypair(keysize):
    p = generate_large_prime(keysize)
    q = generate_large_prime(keysize)
    n = p * q
    phi = (p - 1) * (q - 1)

    # Choose e
    e = random.randrange(2, phi)
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(2, phi)
        g = gcd(e, phi)

    # Generate d
    d = modinv(e, phi)

    return ((n, e), (n, d))

def decrypt(private_key, ciphertext):
    n, d = private_key
    # Decrypt each character
    plain = [chr((char ** d) % n) for char in ciphertext]
    return ''.join(plain)

# RSA Key Generation
keysize = 8  # Small size for demonstration; use 1024 or 2048 for real applications
public_key, private_key = generate_keypair(keysize)

print(f"Public Key: {public_key}")
print(f"Private Key: {private_key}")

Execute the program on the receiver’s computer. Take note of the public and private key. Share the public key with the sender.

Prerequisites

• Familiarity with binary arithmetic. Know what are MSB and LSB.
• Bitwise operations. Logical shift.
• Primality Testing

Introduction

Continuing with the series of posts on number theory and cryptograpy, let us take a look at the RSA algorithm.

Before writing the RSA program, let’s prepare some useful functions.

GCD

Here’s a simple recurisve function to computed the GCD of two integers.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

We have discussed the non-recursive implementation of the Euclidean algorithm at length in this series.

Introduction

Continuing with the series of posts on number theory and cryptograpy, let us take a look at the RSA algorithm.

RSA is an algorithm to perform encryption and decryption of data.

The Basic Idea

RSA uses two keys to encrypt and decrypt messages:

• Public Key: Anyone can see this key. It’s used to encrypt the message.
• Private Key: Only you should know this key. It’s used to decrypt the message.

When someone wants to send you a secret message, they use your public key to encrypt the message. Once it’s encrypted, only your private key can decrypt it.

Introduction

Continuing with the series of posts on number theory and cryptograpy, let us take a look at the Euler’s Totient Function.

Euler’s Totient Function, denoted as ϕ(n), is a function that counts the number of positive integers less than or equal to n that are relatively prime to n. Two numbers are relatively prime (or coprime) if their greatest common divisor (GCD) is 1.

Prerequisites

• Familarity with the Inclusion-Exclusion principle
• Familarity with the modular arithmetic

Definition

For any positive integer n, the Euler’s Totient Function ϕ(n) is defined as:

Introduction

Continuing with the series of posts on number theory and cryptograpy, let us take a look at the Chinese Remainder Theorem.

Prereseqisites

• Modular arithmetic, especially modular inverses
• The Extended Euclidean Algorithm

The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) provides a solution to a system of simultaneous congruences with different moduli. Here’s a step-by-step explanation:

Problem Setup

Suppose you have a system of congruences like this:

x ≡ a₁ (mod m₁)

Introduction

In this series of articles about number theory and cryptography, we have discussed

• The Euclidean algorithm to compute the GCD for two integers a and b
• The Bezout’s Identity: ax + bc = GCD(a,b)

This article will introduce the reader to the Extended Euclidean algorithm to compute the coefficients of the Bezout’s Identity.

Bézout’s identity states that for any two integers a and b, their greatest common divisor (GCD) can be expressed as:

Introduction

In this series of articles on number theory, today we talk about the Bézout’s Identity.

Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. The integers of the form az + bt are exactly the multiples of d.

The integers x and y are called Bézout coefficients for (a, b); they are not unique

This is a long-form post about the Euclidean algorithm to compute the greatest common divisors of two integers. The article starts from the fundamentals and explains why it works better than the naive algorithm. The author also explains the computational complexity and the mathematics of the algorithm.

Prereseqisites

• Fundamental arithmetic and an understanding of the greatest common divisor(GCD).
• Introductory concepts in algebra and logarithms, including mathematical induction.
• Overview of modular arithmetic.
• Familiarity with the Fibonacci series. An excellent video tutorial of the Fibonacci series on Youtube.
• An introduction to the big O notation.
• Basics Python programming skills.
• Curiosity.
• Patience to read long articles. It is okay to read it in more than one sitting. Taking notes will be benefitial for the learner. Re-reading the article a few times is encouraged.

Introduction

What Is GCD?

GCD, the greatest common divisor is the largest number that divides the given two integers.