RSA (cryptosystem)

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). In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the "factoring problem". The acronym RSA is the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 1977. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), had developed an equivalent system in 1973, which was not declassified until 1997.

A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value. The prime numbers must be kept secret. Anyone can use the public key to encrypt a message, but only someone with knowledge of the prime numbers can decode the message. Breaking RSA encryption is known as the RSA problem. Whether it is as difficult as the factoring problem is an open question. There are no published methods to defeat the system if a large enough key is used.

RSA is a relatively slow algorithm, and because of this, it is less commonly used to directly encrypt user data. More often, RSA passes encrypted shared keys for symmetric key cryptography which in turn can perform bulk encryption-decryption operations at much higher speed.

Encrypting message

$\displaystyle c=m^{p}\mod {q}$

Decrypting message

$\displaystyle m=c^{d}\mod {q}$

  • Number: m
  • Cipher number: c
  • Public key: p & q
  • Private key: d

Python algorithm

In [1]:
def rsa_str(p, q, text):
    temp = ""
    for char in text:
        temp+= chr(pow(ord(char), p) % q)
    return temp

Example

  • Public key: 17, 3233
  • Private key: 2753
In [2]:
text = "Hello World!"
cipher_text = rsa_str(17, 3233, text)
decipher_text = rsa_str(2753, 3233, cipher_text)
print(
    "Original text:", text,
    "\nCipher text:", cipher_text,
    "\nDecipher text:", decipher_text
)

Original text: Hello World! 
Cipher text: ஸԡ˩˩ࢉ߈ɜࢉ६˩ۭܽ 
Decipher text: Hello World!

Generating keys

In [3]:
import random

Function for greatest common divisor

In [4]:
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

Function for co-prime

In [5]:
def coprime(x, y):
    return gcd(x, y) == 1

Function for prime numbers (Sieve of Eratosthenes)

In [6]:
def primes(limit):
    a = [True] * limit
    a[0] = a[1] = False
    
    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):
                a[n] = False

def random_prime():
    return list(primes(1000))[random.randint(10, 20)]

Calculate e

In [7]:
def calculate_e(n,f):
    limit = random.randint(10, 20)
    count = 0
    for i in range(1, f):
        if coprime(i, n) and coprime(i, f):
            count+= 1
            if count > limit:
                return i

Generating keys

  1. Choose two different large random prime numbers p and q
  2. Calculate $n = pq$
  3. Calculate the totient: $\phi(n) = (p−1)(q−1)$
  4. Choose an integer e such that $1 < e < ϕ(n)$, and e is co-prime to $\phi(n)$
  5. Compute d to satisfy the congruence relation $d e \equiv 1 (mod \phi(n))$
  • n is the modulus for the public key and the private keys
  • e is released as the public key exponent
  • d is kept as the private key exponent
In [8]:
def generate_keys():
    d = 0.1
    # Stupid fix
    while int(d)-d != 0:
        p = random_prime()
        q = random_prime()
        n = p*q
        f = (p-1)*(q-1)
        e = calculate_e(n, f)
        d = (1 + (2*f))/e
    d = int(d)
    return [e,n,d]

Example

In [9]:
keys = generate_keys()
print("Public key: ", keys[0], ",", keys[1], "\nPrivate key:", keys[2])

Public key:  29 , 2491 
Private key: 165
In [10]:
text = "Hello World!"
cipher_text = rsa_str(keys[0], keys[1], text)
decipher_text = rsa_str(keys[2], keys[1], cipher_text)
print(
    "Original text:", text,
    "\nCipher text:", cipher_text,
    "\nDecipher text:", decipher_text
)

Original text: Hello World! 
Cipher text: ߈őӰӰ׮ƚࣈ׮ࣹӰĺ΂ 
Decipher text: Hello World!

Source