RSA Algorithm in Python

An asymmetric cryptography algorithm is the RSA algorithm. In actuality, asymmetric refers to the fact that it operates on both the public and private keys. As implied by the name, the private key is kept secret while the public key is distributed to everybody.

Asymmetric cryptography example:

• A client requests data from the server by sending its public key to it, such as a browser.
• Using the client's public key, the server encrypts the data before sending it.
• After receiving this data, the client decrypts it.

Because this is asymmetric, even if someone else has the browser's public key, only the browser itself can decode the data.

The notion! Large integers are hard to factorize, which is the foundation for the RSA concept. Two numbers make up the public key, one of which is the product of two big prime numbers. The same two prime numbers are also used to generate the private key. Therefore, the private key is compromised if the huge integer can be factorized. As a result, the key size determines the encryption strength entirely, and the strength of the encryption rises exponentially as the key size is doubled or tripled. RSA keys are normally 2048 or 1024 bits long, but experts predict that 1024-bit keys will soon be cracked. However, it appears to be an impossible feat as of yet.

Now let's examine the workings of the RSA algorithm:

• Public Key Generation:

• Private Key Generation:

We are now prepared with our private key (d = 2011) and public key (n = 3127 and e = 3). We will now encrypt "HI":

The RSA algorithm's implementation is shown below:

Method 1:

Small numerical values are encrypted and decrypted.

Output:

Message data = 12.000000
Encrypted data = 3.000000
Original Message Sent = 12.000000

Method 2:

Using the ASCII value of each letter and number to encrypt and decode plain text messages:

Output:

Initial message:
Test Message

The encoded message(encrypted by public key)
863312887135951593413927434912887135951359583051879012887

The decoded message(decrypted by private key)
Test Message

RSA Cryptosystem Implementation in C++ with Primitive Roots

Using primitive roots, we shall put RSA into practice in a basic manner.

Step 1: Generating Keys

First, we must produce the two big prime numbers, p and q. The product of these primes, which should be somewhat bigger than the message we wish to encrypt, should have nearly equal lengths.

Any primality testing algorithm, such as the Miller-Rabin test, can produce the primes. After obtaining the two prime numbers, we can calculate their product, n = p*q, which serves as our RSA system's modulus.

To calculate gcd(e, phi(n)) = 1, we must next select an integer e such that 1 < e < phi(n), where phi(n) = (p-1)*(q-1) is Euler's totient function. The public key exponent will be this value of e.

We must identify an integer d such that d*e = 1 (mod phi(n)) to compute the private key exponent d. You may do this by applying the extended Euclidean method.

We have (n, e) as our public key and (n, d) as our private key.

Step 2: Encryption

A message m must be converted to an integer between 0 and n-1 to be encrypted. Reversible encoding schemes like UTF-8 or ASCII can be used for this.

After obtaining the message's integer representation, we calculate the ciphertext c using the formula c = m^e (mod n). Binary exponentiation is one of the efficient modular exponentiation algorithms that may be used for this.

Step 3: Decryption

We calculate the plaintext m as m = c^d (mod n) in order to decipher the ciphertext c. Once more, modular exponentiation algorithms allow us to do this task quickly.

Step 4: Example

Let's go over an example to show how the RSA cryptosystem functions utilizing tiny numbers.

Assume that n = 143 and phi(n) = 120 result from our selection of p = 11 and q = 13. Given that gcd (7, 120) = 1, we may select e = 7. Since 7*103 = 1 (mod 120), we can calculate d = 103 using the extended Euclidean technique.

We have (143, 7) as our public key and (143, 103 as our private key.

Let's say we wish to encrypt the "HELLO" message. Using ASCII encoding, we can translate this to the number 726564766. We calculate the ciphertext as c = 726564766^7 (mod 143) = 32 using the public key.

Using the private key, we can decrypt the ciphertext by computing the original message, m = 32^103 (mod 143) = 726564766.

Example Code:

Program Explanation:

The RSA (Rivest-Shamir-Adleman) cryptosystem, a popular asymmetric encryption technique, is implemented by this C++ program. It produces a random primitive root modulo 'n' after computing Euler's totient function (phi) of a given composite number 'n.' The software calculates a private key made up of 'd' and 'n' and a public key made up of 'e' and 'n .'Raising a message' to the power of 'e' modulo 'n' and the ciphertext 'c' to the power of 'd' modulo 'n' respectively show how encryption and decryption work. To illustrate the RSA encryption and decryption procedure, the original message, the encrypted message, and the decrypted message are printed.

Output:

Public key: {3, 3233}
Private key: {2011, 3233}
Original message: 123456
Encrypted message: 855
Decrypted message: 123456

Advantages:

• Security: The RSA method is frequently used for secure data transfer since it is thought to be exceedingly secure.
• Public-key cryptography: The RSA algorithm employs two separate keys for encryption and decryption, making it a public-key cryptography algorithm. The data is encrypted using the public key and decrypted using the private key.
• Key exchange: Two parties can exchange a secret key without actually sending it over the network by using the RSA method for safe key exchange.
• Digital signatures: A sender can use their private key to sign a message, and the recipient can use the sender's public key to verify the signature. This technique is known as the RSA method.
• Speed: Due to its effectiveness and speed, the RSA approach is well-suited for use in real-time applications.
• Widely used: The RSA algorithm is widely developed in several sectors and applications, including online banking, e-commerce, and secure communications.

Disadvantages:

• Slow processing speed: The RSA algorithm processes data more slowly than other encryption methods, especially when handling big volumes of data.
• Large key size: The security of the RSA method depends on huge key sizes, which necessitate greater processing power and storage capacity.
• Vulnerability to side-channel attacks: The RSA method is susceptible to side-channel attacks, which allow an attacker to get the private key by using data released through side channels, including electromagnetic radiation, power usage, and timing analysis.
• Limited usage in some applications: Because of its sluggish processing speed, the RSA method is not appropriate for some applications, such as those that need to encrypt and decode enormous volumes of data constantly.
• Complexity: The RSA algorithm is a complex mathematical method that might be difficult for some people to understand and apply.
• Key Management: Although it can occasionally be challenging, the RSA technique requires the safe administration of the private key.
• Capability to Handle Quantum Computing: The RSA algorithm is vulnerable to assault by quantum computers, which might lead to data decryption.