Below you will find pages that utilize the taxonomy term “DSA”

# Implement The RSA Algorithm

# 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.

# Prepare To Implement The RSA Algorithm

# 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.

# The RSA Algorithm

# 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.

# Eulers Totient Function

# 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:

# Chinese Remainder Theorem

# 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_{1} (mod m_{1})

# Extended Euclidean Algorithm

## 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:

# Bezouts Identity

## 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

# Euclidean Algorithm To Compute GCD

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.