Cryptography Program

Published on: September 22, 2024

This program encrypts and decrypts messages using three different cryptographic methods:
Caesar Cipher, Linear Cipher, and RSA Cryptography.

It was developed in a Linux Ubuntu environment using C++.

🔹 Features

• Select from three cipher methods: Caesar Cipher, Linear Cipher, or RSA
• Support for key discovery in Linear Cipher
• Built-in brute-force decryption for unknown Linear Cipher keys
• Public and private key generation for RSA encryption
• Improved RSA encryption capacity (1 → 9 letters) using Boost Multiprecision (cpp_int)
• Optimized RSA decryption (from hours → seconds) with modular exponentiation improvements

---

📌 How It Works

1️⃣ Caesar Cipher

A simple shift cipher where each letter is shifted by a fixed number of places.

Encryption Formula:

Encrypted Letter = (Original Letter + 3) mod 26

Example:

Input: hello my name is Jacob

Output: khoor pb qqph lv mdfre

Decryption:

The user can input the encrypted message to retrieve the original text.

---

2️⃣ Linear Cipher

A more complex shift cipher that follows the formula:

Encryption Formula:

Encrypted Letter = (a * Original Letter + b) mod 26

Where a must be relatively prime to 26.

Example:

a = 21, b = 23

Input: nice to meet you

Output: kjnd gf pddg hfb

Decryption Options:

1. Decrypt with (a, b) keys: Input known values of a and b to retrieve the original message.
2. Decrypt without (a, b) keys: The program will try all possible 311 (a, b) combinations and display potential decryptions.
3. Find (a, b) keys: Given both the original and encrypted message, the program will calculate the encryption keys a and b.

Example 1 (Decrypt with a, b key):

Encrypted Message: kjnd gf pddg hfb

input keys: a = 21, b = 23

Original Message: nice to meet you

Example 2 (Decrypt without a, b key):

Encrypted Message: kjnd gf pddg hfb

results: all 311 combinations

Example 3 (Finding a, b key):

Original Message: nice to meet you

Encrypted Message: kjnd gf pddg hfb

output keys: a = 21, b = 23

---

3️⃣ RSA Cryptography

An asymmetric encryption method that uses public and private keys for secure message encryption.

Key Generation:

• Public key (n, e)
  • n = p * q (product of two prime numbers)
  • e is a randomly selected number relatively prime to Φ(n)
• Private key (d)
  • d is calculated such that:

    (e * d) ≡ 1 (mod Φ(n))
    

Encryption Formula:

Encrypted Message = (Original Message ^ e) mod n

Decryption Formula:

Original Message = (Encrypted Message ^ d) mod n

Example (Encrypting & Decrypting with RSA):

Encryption

Input: berkeley

The program converts string into Original int: 2505120511180502

Encryption Result:

Message: 666434558223740174

Public Key e: 19

Public Key n: 1000000610000092769

Private Key d: 631579331368479259

Decryption

Decryption Result:

Decrypted int: 2505120511180502

Decrypted Message: berkeley

Limitations:

• Each English letter requires two digits (e.g., z → 26).
• The encryption process is limited by the size of public key n, making it difficult to encrypt long messages due to integer overflow in C++.
  🔹 (Now Updated!) Future Improvement: Exploring large number handling in C++ and optimizing modular arithmetic with exponentiation.

---

(Updates!) Improvements:

✅ Increased encryption capacity (1 → 9 letters) using Boost Multiprecision (cpp_int)
✅ Reduced decryption time from hours → seconds by optimizing modular exponentiation

🛠 Setup & Compilation

Requirements

• C++ Compiler (g++)
• Linux Ubuntu Environment
• Boost Multiprecision Library

Compile & Run

make  # Generates 'a.out'
./a.out
🚀 Happy Encrypting & Decrypting!