Python Pool: RSA Encryption Implementation in Python

Introduction

Cryptography and computer network security have always been side interests for me. While reading about the RSA encryption technique in cryptography, I thought about writing an article on this amazing algorithm. Python is one of my favorite programming languages because of its simplicity, and implementing RSA Encryption using python will be fun. Let’s dive into the concepts of RSA encryption.

What is Encryption?

Encryption means encoding information. In technical terms, encryption is converting human-readable plaintext to alternative text, also known as ciphertext. Only authorized parties can decipher a ciphertext back to plaintext and access the original information.

Encryption

What is RSA Encryption in python?

RSA (Rivest–Shamir–Adleman) algorithm used by many companies to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. Asymmetric means that there are two different keys. This is also called public-key cryptography because one of the keys can be given to anyone. Companies such as Acer, Asus, HP, Lenovo, etc., use encryption in their products.

An example of asymmetric cryptography :

1. A browser sends its public key to the server and requests some data.
2. The server encrypts the data using the client’s public key and sends the encrypted data to the client.
3. The client receives this data and decrypts it.

Since this is asymmetric, nobody else except the browser can decrypt the data even if a third-party user has a public key in the browser.

RSA Encryption Implementation Without Using Library in Python

Mechanism behind RSA

Let us learn the mechanism behind RSA algorithm :

1.  Generating Public Key :

1. Select two prime no's. Suppose P = 47 and Q = 59.
2. Now First part of the Public key  : n = P*Q = 2773.
3.  We also need a small exponent say e : 
        But e Must be and an integer
4. Not be a factor of n. 
           1 < e < phi(n), 
5. Let us now consider it to be equal to 3.

2. Generating Private Key :

1.We need to calculate phi(n) :
       Such thatphiΦ(n) = (P-1)(Q-1)     
       so,  phi(n) = 2668
2. Now calculate Private Key, d : 
       d = (k*phi(n) + 1) / e for some integer k
       For k = 2, value of d is 1779.

Now, we are ready with our public key(n = 2773 and e = 3) and private key(d = 1779).

Now, let us encrypt ‘Hie’

1. Alphabetically H-8, E-5, I-9
2. Thus the Encrypted data wil be c = 895e mod n
     e = 3 , n=2773 so c = 8953 mod 2773
3. Our encrypted data is 1810

try:
   input = raw_input
except NameError:
   pass
try:
   chr = unichr
except NameError:
   pass
p=int(input('Enter prime p: '))
q=int(input('Enter prime q: '))
print("Choosen primes:\np=" + str(p) + ", q=" + str(q) + "\n")
n=p*q
print("n = p * q = " + str(n) + "\n")
phi=(p-1)*(q-1)
print("Euler's function (totient) [phi(n)]: " + str(phi) + "\n")
def gcd(a, b):
    while b != 0:
        c = a % b
        a = b
        b = c
    return a
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,phi) != None:
            l.append(x)
    for x in l:
        if x == modinv(x,phi):
            l.remove(x)
    return l
print("Choose the value of e:\n")
print(str(coprimes(phi)) + "\n")
e=int(input())
d=modinv(e,phi)
print("\nYour public key is a pair of numbers (e=" + str(e) + ", n=" + str(n) + ").\n")
print("Your private key is a pair of numbers (d=" + str(d) + ", n=" + str(n) + ").\n")
def encrypt_block(m):
    c = modinv(m**e, n)
    if c == None: print('No modular multiplicative inverse for block ' + str(m) + '.')
    return c
def decrypt_block(c):
    m = modinv(c**d, n)
    if m == None: print('No modular multiplicative inverse for block ' + str(c) + '.')
    return m
def encrypt_string(s):
    return ''.join([chr(encrypt_block(ord(x))) for x in list(s)])

s = input("Enter a message to encrypt: ")
print("\nPlain message: " + s + "\n")
enc = encrypt_string(s)
print("Encrypted message: " + enc + "\n")

OUTPUT:-

output

As you can see from the above, we have implemented the encryption of a message without using any library function. But as we are using python, we should take some advantage out of it. By this, I mean to say that we are having libraries available for the RSA implementation. Oh! Yeah, you heard it right.

RSA Encryption Implementation Using Library in Python

There are many libraries available in python for the encryption and decryption of a message, but today we will discuss an amazing library called pycryptodome.

The RSA algorithm provides:

• Key-pair generation: generate a random private key and public key (the size is 1024-4096 bits).
• Encryption: It encrypts a secret message (integer in the range [0…key_length]) using the public key and decrypts it back using the secret key.
• Digital signatures: sign messages (using the private key) and verify message signature (using the public key).
• Key exchange: It securely transports a secret key used for encrypted communication.

Before starting to code in python do not forget to install the library.

pip install pycryptodome

Now let’s understand how the RSA algorithms work by a simple example in Python. The below code will generate a random RSA key-pair, will encrypt a short message using the RSA-OAEP padding scheme.

RSA key generation

Now, let’s write the Python code. First, generate the RSA keys (1024-bit) and print them on the console as hex numbers and the PKCS#8 PEM ASN.1 format.

pip install pycryptodome

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import binascii

keyPair = RSA.generate(3072)

pubKey = keyPair.publickey()
print(f"Public key:  (n={hex(pubKey.n)}, e={hex(pubKey.e)})")
pubKeyPEM = pubKey.exportKey()
print(pubKeyPEM.decode('ascii'))

print(f"Private key: (n={hex(pubKey.n)}, d={hex(keyPair.d)})")
privKeyPEM = keyPair.exportKey()
print(privKeyPEM.decode('ascii'))

#encryption
msg = 'A message for encryption'
encryptor = PKCS1_OAEP.new(pubKey)
encrypted = encryptor.encrypt(msg)
print("Encrypted:", binascii.hexlify(encrypted))

OUTPUT:-

Public key: (n=0x9a11485bccb9569410a848fb1afdf2a81b17c1fa9f9eb546fd1deb873b49b693a4edf20e36ffc3da9953657ef8bee80c49c2c12933c8a34804a00eb4c81248e01f, e=0x10001)
 -----BEGIN PUBLIC KEY-----
 MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCaEUhbzLlWlBCoSPsa/fKoGxfB
 +p+etUb9HeuHO0m2k
 -----END PUBLIC KEY-----
 Private key: (n=0x9a11485bccb9569410a848fb1afdf2a81b17c1fa9f9eb546fd1deb873b49b693a4edf20eb8362c085cd5b28ba109dbad2bd257a013f57f745402e245b0cc2d553c7b2b8dbba57ebda7f84cfb32b7d9c254f03dbd0188e4b8e40c47b64c1bd2572834b936ffc3da9953657ef8bee80c49c2c12933c8a34804a00eb4c81248e01f, d=0x318ab12be3cf0d4a1b7921cead454fcc42ba070462639483394d6fb9529547827e9c8d23517b5566dd3d3e5b16ec737987337a0e497fdba4b5ad97af41c1c3cdd87542a4637d81)

 -----BEGIN RSA PRIVATE KEY-----

 MIICXAIBAAKBgQCaEUhbzLlWlBCoSPsa/fKoGxfB+p+etUb9HeuHO0m2k6Tt8g64
 NiwIXNWyi6EJ260r0legE/V/dFQC4kWwzC1VPHsrjbulfr2n+Ez7MrfZwlTwPb0B
 iOS45AxHtkwb0lcoNLk2/8PamVNlfvi+6AxJwsEpM8ijSASgDrTIEkjgHwIDAQAB
 AoGAMYqxK+PPDUobeSHOrUVPzEK6BwRiY5SDOU1vuVKVR4J+nI0jspSo4B+KEBna
 NONQ8jB3QOBqJwvvH+ZG5q0hPjG1KP3V9dA+YzwHxEdV7WIqYp156CLAlevfnMgO
 UXtVZt09PlsW7HN5hzN6Dkl/26S1rZevQcHDzdh1QqRjfYECQQDGDUIQXlOiAcGo
 d5YqAGpWe0wzJ0UypeqZcqS9MVe9OkjjopCkkYntifdN/1oG7S/1KUMtLoGHqntb
 c428zOO/AkEAxyV0cmuJbFdfM0x2XhZ+ge/7putIx76RHDOjBpM6VQXpLEFj54kB
 qGLAB7SXr7P4AFrEjfckJOp2YMI5BreboQJAb3EUZHt/WeDdJLutzpKPQ3x7oykM
 wfQkbxXYZvD16u96BkT6WO/gCb6hXs05zj32x1/hgfHyRvGCGjKKZdtwpwJBAJ74
 y0g7h+wwoxJ0S1k4Y6yeQikxUVwCSBxXLCCnjr0ohsaJPJMrz2L30YtVInFkHOlL
 i/Q4AWZmtDDxWkx+bYECQG8e6bGoszuX5xjvhEBslIws9+nMzMuYBR8HvhLo58B5
 N8dk3nIsLs3UncKLiiWubMAciU5jUxZoqWpRXXwECKE=

 -----END RSA PRIVATE KEY-----

 Encrypted: b'99b331c4e1c8f3fa227aacd57c85f38b7b7461574701b427758ee4f94b1e07d791ab70b55d672ff55dbe133ac0bea16fc23ea84636365f605a9b645e0861ee11d68a7550be8eb35e85a4bde6d73b0b956d000866425511c7920cdc8a3786a4f1cb1986a875373975e158d74e11ad751594de593a35de765fe329c0d3dfbbfedc'

Explanation of the code

1. Installed pycryptodome.
2. As we are using the RSA algorithm, we need to import it from Crypto.PublicKey.
3. We are also using the OAEP-Padding scheme. We have imported PKCS1_OAEP from Crypto.cipher.
4. To convert binary to ASCII, we have imported binascii.
5. Generating keypair values using RSA.generate.
6. Generating publickey value
7. Entering a message that is needed to be encrypted.
8. Using encrypt function to encrypt the message.

As you can see after installing a library our work became very simpler and more efficient.

Also Read | Python SHA256: Implementation and Explanation

Conclusion

In today’s detailed discussion, we have covered almost everything about RSA encryption implementation using python. Starting from the basics to encryption, we have understood about RSA algorithm. We have implemented RSA using a library and without using a library. But I recommend using the library pycryptodome as it is more efficient.

Nowadays, almost every MNC uses encryption for their information as hacking is quite easy in today’s world. However, encryption of the information makes it a difficult task for hackers to understand the data.

If you have any doubts, feel free to comment down below. Till then, keep exploring our tutorials.

The post RSA Encryption Implementation in Python appeared first on Python Pool.

from Planet Python
via read more