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

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.