RSA_Algorithm

Introduction • Key Generator • Encryption • Decryption •

---

Introduction

This RSA algorithm works for any prime number and generates output in hexadecimal. But select only large primes for better security. The program Keygenerator creates a public key for encryption and a private key for decryption. Suppose, Alice and Bob are communicating in a hybrid cryptosystem. Alice sends Bob a symmetric-encrypted message. But Bob doesn’t have the symmetric-key. So, he sends his public key to Alice. Alice encrypts the symmetric-key with Bob’s public key and transmit. The private key is kept secrect and only Bob can decrypt using it. Thus a secure communication is established. Here the processes are explained with an example below:

---

Key Generator

Input_key.txt file contains two primes (p and q) and an auxiliary number e (probably a prime) so that e>2 and GCD(e, (p-1) × (q-1)) = 1. Here,

p = 57704576143051, q = 838744063, and e = 2237

Two files- public_key and private_key are created. Public_key would contain ‘modulo’ = p × q and ‘e’. Private_key file contains only ‘p’ and ‘q’. Get primes from here: https://bigprimes.org/

---

🔒Encryption

Encryption function takes three parameters. Here,

Message = Down the-rabbit hole, Modulo = 48399370647915464956213, and e = 2237

From “modulo”, we got,

per_char = 9 and cyln = 23

This means- “Ciphertext length is a multiplication of 23 per 9 character of the message”. <If message length is (1-9) output is 23 character. If message length is (10-18) output is 46 characters (23*2). Here message length is- 20. So ciphertext will be 69 characters in decimal>

Then, the message is divided into three portion: 9 + 9 + 2. Here,

M1 = Down the-
M2 = rabbit ho
M3 = le

Each part convert to int. Here,

M1 = 1262410606558359086381
M2 = 2109946103777344907375
M3 = 27749

Convert to int: "Down the-" = "-eht nwoD" = 45 x 2560 + 101 x 2561 + 104 x 2562 + 116 x 2563 + 32 x 2564 + 110 x 2565 + 119 x 2566 + 111 x 2567 + 68 x 2568 = 1262410606558359086381

Ciphertext is produced by PowMod() function. Each part contains 23 characters. If less than 23, convert to string and add “0” in the beginning of each part.

• C1 = M1^e mod modulo = 1262410606558359086381²²³⁷ mod 48399370647915464956213 = 17004190389571278372483
  
• C2 = M2^e mod modulo = 2109946103777344907375²²³⁷ mod 48399370647915464956213 = 46911152036783136438187
  
• C3 = M3^e mod modulo = 27749²²³⁷ mod 48399370647915464956213 = 8084009132883873298763
  

Here, C3 has a length 22, less than 23. So a “0” is added before it. Finally

• C = C1+C2+C3 = 170041903895712783724834691115203678313643818708084009132883873298763
  

C is convert to hexadecimal giving the ciphertext. Here:

Ciphertext: 64EA4F894FB708BD613599C2821799381F581AAAEE8048DD9445AF94B

---

🔓Decryption

Decryption takes three parameters. Here,

Ciphertext: 64EA4F894FB708BD613599C2821799381F581AAAEE8048DD9445AF94B
Modulo = 48399370647915464956213 and e = 2237

Inside decryption function, private_key file is opened giving p and q. Here,

p = 57704576143051 and q = 838744063

Ciphertext is converted to decimal and phi is calculated. Here,

• C = 170041903895712783724834691115203678313643818708084009132883873298763
• phi = (p-1) × (q-1) = 48399370590210050069100
  

InvertModulo function takes e and phi and gives d such that e × d mod phi ≡ 1. Here,

d = 10125572389905365861573

From “modulo”, we got:

per_char = 9
cyln = 23

Ciphertext length = 69 in decimal. If less than 69 (ciphertext length mod cyln != 0), add 0 before the ciphertext.

Divide ciphertext by 23 characters, gives 3 portion. Here,

C1 = 17004190389571278372483
C2 = 46911152036783136438187
C3 = 08084009132883873298763

Now, using PowerMod function, we get M1, M2 and M3 in integer. Here,

• M1 = C1^d mod modulo = 17004190389571278372483^{10125572389905365861573} 48399370647915464956213 = 1262410606558359086381
  
• M2 = C2^d mod modulo = 46911152036783136438187^{10125572389905365861573} 48399370647915464956213 = 2109946103777344907375
  
• M3 = C3^d mod modulo = 08084009132883873298763^{10125572389905365861573} 48399370647915464956213 = 27749
  

Then, each part is converted to string. Here,

M1 = 1262410606558359086381 = Down the-
M2 = 2109946103777344907375 = rabbit ho
M3 = 27749 = le

Convert to string, M1 = Numb = 1262410606558359086381. Temp = Numb%256 = 45. Temp To ASCII = ‘-’. Numb = Numb – temp = 1262410606558359086336. Numb = Numb ÷ 256 = 4931291431868590181. Similarly, we get total “-eht nwoD”. Reverse it we get “Down the-”

Finally, M = M1+M2+M3 gives the message in plaintext. Here,

Plaintext = Down the-rabbit hole

©️Sazzad-Saju

END OF DOCUMENT 😄