Prepare To Implement The RSA Algorithm

By Sudheer S

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.

Mod Inverse

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

The modinv function computes the modular inverse of a number a modulo m. The modular inverse of a is a number x such that:

$$ (a \times x) mod m = 1 $$

This function is critical in RSA because it is used to calculate the private key d from the public key e and the modulus φ(n).

The modinv function is based on the Extended Euclidean algorithm, which is used to find the modular inverse of a modulo m. The function takes two arguments: a (the number you want the modular inverse of) and m (the modulus).

Initial Setup

m0 stores the original value of m because m will be modified during the algorithm, but we need the original value later. x0 and x1 are initialized to 0 and 1, respectively. These variables will help in building the solution as the algorithm progresses. If m is 1, the modular inverse doesn’t exist (division by 1 doesn’t make sense in modular arithmetic), so the function returns 0.

The Loop

Condition: The loop runs as long as a is greater than 1. q = a // m: q is the quotient when a is divided by m. It helps in updating the variables in each step. Update m and a: The algorithm repeatedly reduces a modulo m, swapping a and m (similar to how the Euclidean algorithm finds the GCD). Update x0 and x1: The variables x0 and x1 are updated using the quotient q. This step ensures that by the end of the loop, x1 will hold the modular inverse of a.

Final Adjustment

After the loop, x1 may be negative, which isn’t useful as a modular inverse. The adjustment x1 += m0 ensures that x1 is positive by adding the original modulus m to it. Finally, x1 is returned as the modular inverse of a modulo m.

The Extended Euclidean Algorithm works by expressing the greatest common divisor (GCD) of two numbers as a linear combination of those numbers. Since we know that the GCD of a and m is 1 (required for the modular inverse to exist), the algorithm finds coefficients that satisfy:

1 = ax + my

Here, x becomes the modular inverse of a modulo m.

To better understand the program, using a paper and pen, step through the program as it computes the modular inverse. Try a = 3 and m = 11, for example.

Generating The Prime Candidate

import random

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

Uses the random.getrandbits(length) function to generate a random number p with exactly length bits.

Example: If length is 8, p might be a random number between 0 and 255 (because 2^8 - 1 = 255).

However, without any adjustments, p could potentially be an even number or have leading zeros, which would not be ideal for a prime candidate. Apply a Mask to Set the Most Significant Bit (MSB) and Least Significant Bit (LSB) to 1

p |= (1 << length - 1) | 1

This line modifies p to ensure that the number has its MSB and LSB set to 1. Let’s break this down:

Set the MSB (Most Significant Bit) to 1:

(1 « length - 1) shifts the number 1 left by length - 1 positions.

Example: If length is 8, 1 « 7 results in 10000000 in binary (which is 128 in decimal).

p |= (1 << length - 1) ensures that the MSB of p is set to 1, meaning the number will have the full length of bits (no leading zeros).

Set the LSB (Least Significant Bit) to 1:

The | 1 part ensures that the least significant bit is 1, making p an odd number.

Example: If the LSB of p was 0, this operation flips it to 1, ensuring the number is odd (even numbers cannot be prime, except for 2).

Bitwise OR (|): The | operator performs a bitwise OR between p and the mask (1 << length - 1) | 1.

This operation ensures that the resulting number has both the MSB and LSB set to 1.

Generating A Large Prime Number

from sympy import isprime

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

Use the symbp library to test primality. Generate the prime candidate in a loop until we find a prime.

Using these functions as building blocks, we will implement the RSA algoritm in the next post.

References