The Algorithms logo
The Algorithms
AboutDonate

Rsa Cipher

J
W
c
9
D
M
C
B
and 9 more contributors
import os
import sys

from . import rsa_key_generator as rkg

DEFAULT_BLOCK_SIZE = 128
BYTE_SIZE = 256


def get_blocks_from_text(
    message: str, block_size: int = DEFAULT_BLOCK_SIZE
) -> list[int]:
    message_bytes = message.encode("ascii")

    block_ints = []
    for block_start in range(0, len(message_bytes), block_size):
        block_int = 0
        for i in range(block_start, min(block_start + block_size, len(message_bytes))):
            block_int += message_bytes[i] * (BYTE_SIZE ** (i % block_size))
        block_ints.append(block_int)
    return block_ints


def get_text_from_blocks(
    block_ints: list[int], message_length: int, block_size: int = DEFAULT_BLOCK_SIZE
) -> str:
    message: list[str] = []
    for block_int in block_ints:
        block_message: list[str] = []
        for i in range(block_size - 1, -1, -1):
            if len(message) + i < message_length:
                ascii_number = block_int // (BYTE_SIZE**i)
                block_int = block_int % (BYTE_SIZE**i)
                block_message.insert(0, chr(ascii_number))
        message.extend(block_message)
    return "".join(message)


def encrypt_message(
    message: str, key: tuple[int, int], block_size: int = DEFAULT_BLOCK_SIZE
) -> list[int]:
    encrypted_blocks = []
    n, e = key

    for block in get_blocks_from_text(message, block_size):
        encrypted_blocks.append(pow(block, e, n))
    return encrypted_blocks


def decrypt_message(
    encrypted_blocks: list[int],
    message_length: int,
    key: tuple[int, int],
    block_size: int = DEFAULT_BLOCK_SIZE,
) -> str:
    decrypted_blocks = []
    n, d = key
    for block in encrypted_blocks:
        decrypted_blocks.append(pow(block, d, n))
    return get_text_from_blocks(decrypted_blocks, message_length, block_size)


def read_key_file(key_filename: str) -> tuple[int, int, int]:
    with open(key_filename) as fo:
        content = fo.read()
    key_size, n, eor_d = content.split(",")
    return (int(key_size), int(n), int(eor_d))


def encrypt_and_write_to_file(
    message_filename: str,
    key_filename: str,
    message: str,
    block_size: int = DEFAULT_BLOCK_SIZE,
) -> str:
    key_size, n, e = read_key_file(key_filename)
    if key_size < block_size * 8:
        sys.exit(
            "ERROR: Block size is {} bits and key size is {} bits. The RSA cipher "
            "requires the block size to be equal to or greater than the key size. "
            "Either decrease the block size or use different keys.".format(
                block_size * 8, key_size
            )
        )

    encrypted_blocks = [str(i) for i in encrypt_message(message, (n, e), block_size)]

    encrypted_content = ",".join(encrypted_blocks)
    encrypted_content = f"{len(message)}_{block_size}_{encrypted_content}"
    with open(message_filename, "w") as fo:
        fo.write(encrypted_content)
    return encrypted_content


def read_from_file_and_decrypt(message_filename: str, key_filename: str) -> str:
    key_size, n, d = read_key_file(key_filename)
    with open(message_filename) as fo:
        content = fo.read()
    message_length_str, block_size_str, encrypted_message = content.split("_")
    message_length = int(message_length_str)
    block_size = int(block_size_str)

    if key_size < block_size * 8:
        sys.exit(
            "ERROR: Block size is {} bits and key size is {} bits. The RSA cipher "
            "requires the block size to be equal to or greater than the key size. "
            "Did you specify the correct key file and encrypted file?".format(
                block_size * 8, key_size
            )
        )

    encrypted_blocks = []
    for block in encrypted_message.split(","):
        encrypted_blocks.append(int(block))

    return decrypt_message(encrypted_blocks, message_length, (n, d), block_size)


def main() -> None:
    filename = "encrypted_file.txt"
    response = input(r"Encrypt\Decrypt [e\d]: ")

    if response.lower().startswith("e"):
        mode = "encrypt"
    elif response.lower().startswith("d"):
        mode = "decrypt"

    if mode == "encrypt":
        if not os.path.exists("rsa_pubkey.txt"):
            rkg.make_key_files("rsa", 1024)

        message = input("\nEnter message: ")
        pubkey_filename = "rsa_pubkey.txt"
        print(f"Encrypting and writing to {filename}...")
        encrypted_text = encrypt_and_write_to_file(filename, pubkey_filename, message)

        print("\nEncrypted text:")
        print(encrypted_text)

    elif mode == "decrypt":
        privkey_filename = "rsa_privkey.txt"
        print(f"Reading from {filename} and decrypting...")
        decrypted_text = read_from_file_and_decrypt(filename, privkey_filename)
        print("writing decryption to rsa_decryption.txt...")
        with open("rsa_decryption.txt", "w") as dec:
            dec.write(decrypted_text)

        print("\nDecryption:")
        print(decrypted_text)


if __name__ == "__main__":
    main()
About this Algorithm

About RSA Algorithm

RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and distinct from the decryption key which is kept secret (private).

Algorithm

  1. Select 2 Prime Numbers - p & q

  2. Calculate n as $$n = p * q$$

  3. In number theory, Euler's Totient function counts the positive integers up to a given integer n that are relatively prime to n.

    Calculate Euler's Totient Function of n. $$φ(n) = (p-1) * (q-1)$$

    Note, that Euler's Totient works only if $p$ and $q$ are Prime Numbers.

  4. Select Public Key - $e$ , such that $e$ and $φ(n)$ are Co-primes, i.e, $$\gcd(e , φ(n))=1$$

  5. Calculate Private Key, $d$ such that $$(d * e) \mod φ(n) = 1$$

Public and Private Keys

  1. The Public key is ( e , n ) which is known to all in the network.
  2. The Private key is ( d , n ) which is known ONLY to the User to whom message is to be sent.

Encryption & Decryption

Encryption Algorithm

The Cipher Text, C is generated from the plaintext, M using the public key, e as:

$$C = M^e \mod n$$

Decryption Algorithm

The Plain Text, M is generated from the ciphertext, C using the private key, d as:

$$M = C^d \mod n$$

Encryption & Decryption Mechanism

The Encryption and Decryption mechanism block diagram with sample message encryption.

RSA-Encryption-Decryption-block-diagram.png

Explanation

The explanation for the above example,

RSA-Example-maths-only-diagram.png

Simple Implementation of RSA using Python

from sympy import *
import math 

#Generate p and q
p = randprime(1, 10)
q = randprime(11, 20)

# Generate n and l(n)
n = p*q
l = (p-1)*(q-1)

# Function to test Co-Primality for generation of list of Public Keys
def isCoPrime(x):
    return math.gcd(l, x) == 1

# Function to find mod Inverese of e withl(n) to generate d     
def modInverse(e, l):
    e = e % l
    for x in range(1, l):
        if (e * x) % l == 1:
            return x
    return 1

# List for Co-Primes
listOfCP = []
for i in range(1, l):
    if isCoPrime(i) == True:
        listOfCP.append(i)

# Print values of P, Q, N, L        
print("Value of P = ", p)
print("Value of Q = ", q)
print("Value of N = ", n)
print("Value of L = ", l)

print(" ")

# Print List of Co-Primes for e
print("List of Available Public Keys")
print(listOfCP)

print(" ")

# select a Public Key from list of Co-Primes
e = int(input("Select Public Key from the Above List ONLY: "))

# Value of d
d = modInverse(e, l)

print(" ")

# Print Public and Private Keys
print("PUBLIC KEY  : { e , n } = {", e ,",", n , "}")
print("PRIVATE KEY : { d , n } = {", d ,",", n , "}")

print(" ")

# Encryption Algorithm
def encrypt(plainText):
    return (plainText**e)%n

# Decryption Algorithm
def decrypt(cipherText):
    pvtKey = int(input("Enter your Private Key: "))
    return (cipherText**pvtKey)%n

# Driver Code

# Message Input
pt = int(input('Enter the Plain Text: '))
print("CipherText: ", encrypt(pt))

print(" ")

# CipherText Input
ct = int(input('Enter the Cipher Text: '))
print("PlainText: ", decrypt(ct))
Value of P =  7
Value of Q =  19
Value of N =  133
Value of L =  108
     
List of Available Public Keys
[1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107]
     
Select Public Key from the Above List ONLY: 47
     
PUBLIC KEY  : { e , n } = { 47 , 133 }
PRIVATE KEY : { d , n } = { 23 , 133 }
     
Enter the Plain Text: 51
CipherText:  116
     
Enter the Cipher Text: 116
Enter your Private Key: 23
PlainText:  51

Implementations