RSA

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 it is different from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the “factoring problem”. The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), had developed an equivalent system in 1973, but this 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 with currently published methods, and if the public key is large enough, only someone with knowledge of the prime numbers can decode the message feasibly. Breaking RSA encryption is known as the RSA problem. Whether it is as difficult as the factoring problem remains an open question.

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.

Imports

from primesieve import nth_prime

RSA Algorithm

  1. Take two distinct, large primes p and q (Ideally these have a similar byte-length)
  2. Multiply p and q and store the result in n
  3. Find the totient for n using the formula φ(n)=(p−1)(q−1)
  4. Take an e coprime that is greater, than 1 and less than n
  5. Find d using the formula d⋅e≡1modφ(n)

At this point, the pair (e, n) is the public key and the private key (d, n) is the private key.

p = nth_prime(10)
q = nth_prime(15)

n = p*q

print (p,q,n)

29 47 1363

totient = (p-1)*(q-1)

print (totient)

1288

Totient

In number theory, Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler’s phi function. It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n.

title

The line on the top represents distribution of prime numbers. The phi of a prime number is simply the (n-1)

  • Phi function is multiplicative (for relatively prime numbers).
  • Therefore, phi of A times B where A and B are prime is (A-1) times (B-1)

Coprime

In number theory, two integers a and b are said to be relatively prime, mutually prime, or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1. Consequently, any prime number that divides one does not divide the other. This is equivalent to their greatest common divisor (gcd) being 1

from math import gcd
import random

def modinv(a, m):
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

def coprimes(a):
    l = []
    for x in range(2, a):
        if gcd(a, x) == 1 and modinv(x,a) != None:
            l.append(x)
    for x in l:
        if x == modinv(x,a):
            l.remove(x)
    return l

coprime_list = coprimes(totient)

secure_random = random.SystemRandom()
e = secure_random.choice(coprime_list)

d = modinv(e, totient)

d

685

Private and Public key pairs

print ('Public key pair:', e, n)

Public key pair: 1021 1363

print ('Private key pair:', d, n)

Private key pair: 685 1363

Test

test = 2**e % n

test

1029

test**d % n

2

Encryption and Decryption

def encrypt(msg, pub, pri, mod):
    chars = [ord(x) for x in list(msg)]
    cipher = []
    for char in chars:
        cipher.append(chr(char**pub%mod))
    return ''.join(cipher)

def decrypt(msg, pub, pri, mod):
    chars = [ord(x) for x in list(msg)]
    cipher = []
    for char in chars:
        cipher.append(chr(char**pri%mod))
    return ''.join(cipher)

cipher = encrypt(msg = 'hello', pub=e, pri=d, mod=n)

decrypt(cipher, pub=e, pri=d, mod=n)

'hello'

Python library

import rsa

Bob generates a keypair, and gives the public key to Alice. This is done such that Alice knows for sure that the key is really Bob’s (for example by handing over a USB stick that contains the key).

(bob_pub, bob_priv) = rsa.newkeys(512)
(alice_pub, alice_priv) = rsa.newkeys(512)

Alice writes a message, and encodes it in UTF-8. The RSA module only operates on bytes, and not on strings, so this step is necessary.

message = 'hello Bob!'.encode('utf8')

Alice encrypts the message using Bob’s public key, and sends the encrypted message

cipher = rsa.encrypt(message, bob_pub)

Bob receives the message, and decrypts it with his private key.

decrypt_cipher = rsa.decrypt(cipher, bob_priv)

print (decrypt_cipher)

b'hello Bob!'

Since Bob kept his private key private, Alice can be sure that he is the only one who can read the message. Bob does not know for sure that it was Alice that sent the message, since she didn’t sign it.

Signature

Suppose Alice uses Bob’s public key to send him an encrypted message. In the message, she can claim to be Alice but Bob has no way of verifying that the message was actually from Alice since anyone can use Bob’s public key to send him encrypted messages. In order to verify the origin of a message, RSA can also be used to sign a message.

Suppose Alice wishes to send a signed message to Bob. She can use her own private key to do so. She produces a hash value of the message, raises it to the power of d (modulo n) (as she does when decrypting a message), and attaches it as a “signature” to the message. When Bob receives the signed message, he uses the same hash algorithm in conjunction with Alice’s public key. He raises the signature to the power of e (modulo n) (as he does when encrypting a message), and compares the resulting hash value with the message’s actual hash value. If the two agree, he knows that the author of the message was in possession of Alice’s private key, and that the message has not been tampered with since.

This works because multiplication is commutative so {\displaystyle h=hash(m);(h^{e})^{d}=h^{ed}=h^{de}=(h^{d})^{e}\equiv h{\pmod {n}}} {\displaystyle h=hash(m);(h^{e})^{d}=h^{ed}=h^{de}=(h^{d})^{e}\equiv h{\pmod {n}}} Thus, the keys may be swapped without loss of generality, that is a private key of a key pair may be used either to:

signature = rsa.sign(message, alice_priv, 'SHA-1')

rsa.verify(message, signature, alice_pub)

'SHA-1'

Complete

Bob and Alice generate a keypair and share public keys.

(bob_pub, bob_priv) = rsa.newkeys(512)
(alice_pub, alice_priv) = rsa.newkeys(512)

Alice writes a message.

message = 'hey Bob!'.encode('utf8')

Alice signs the message with private key

signature = rsa.sign(message, alice_priv, 'SHA-1')

Alice encrypts the message using Bob’s public key, and sends the encrypted message

cipher = rsa.encrypt(message, bob_pub)

Bob receives the message and checks for authenticity using alice’s public key

rsa.verify(message, signature, alice_pub)

'SHA-1'

Bob decrypts the message using his private key

decrypt_cipher = rsa.decrypt(cipher, bob_priv)

print (decrypt_cipher)

b'hey Bob!'

signature

b'\x07Of\xabW^\x0b\xaeFh\x01L\xf3\x11\xe0\xe9\\\x99r\xc9\x1c\x044\x11\xfc{5\xa3_ \xeb\xba\xf8\x84b\x1e\xb7\xadK)\xdf\x9b\x8f|\xc4>\x89\x9d\xdf\x98OI\xc1\x87\xc2\xdd\xf3\xf6\x16\xae2`my'