As developers, we often get comfortable with a language and ecosystem, mastering its quirks and nuances. But what happens when we need to step out of our comfort zone? What if the best tool for the job is in a language we haven’t touched before? The transition from one language to another used to be a daunting task, requiring days of reading books, writing small programs, and debugging mysterious errors. However, in the era of AI-assisted development, this learning curve has flattened significantly.

In the past, formal education was primarily accessible through schools, colleges, and universities. However, this is no longer the only path to gaining knowledge. Today, with the vast array of modern tools and technologies available online, self-education has become more viable than ever. If you have the motivation and discipline, you can learn virtually any subject without attending a traditional institution.

Education is now widely accessible through various online resources, including:

The Tech Chorus DevOps Platform

Over the last decade, the way we develop and deploy software has transformed significantly. This transformation has brought together various sub-disciplines, collectively known as DevOps engineering, including:

• IT Engineering: Focused on hardware and networking infrastructure.
• System Administration: Responsible for managing servers in racks, data centers, or colocation services.
• Cloud Infrastructure Engineering: Specializes in managing public cloud infrastructure.
• Platform Engineering: Builds and maintains platforms for deploying software applications, abstracting away complexity for users.

Introducing the Tech Chorus DevOps Platform

The Tech Chorus DevOps Platform is both a framework and software platform designed to host and run software applications and services. It facilitates the creation of cloud-based infrastructure from scratch and adheres to an opinionated approach, integrating best practices and tradeoffs. The platform offers a reference architecture and implementation to meet the most common use cases, with a strong emphasis on open-source technologies.

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