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

Posts

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.

read more
Posts

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.

read more
Posts

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.

read more