RSA

Scritto il

Introduction to RSA Encryption

RSA (Rivest-Shamir-Adleman), developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, represents one of the fundamental pillars of modern cryptography and information security. It is an asymmetric encryption algorithm, also known as public-key cryptography, which has revolutionized the way digital communications and online transactions are secured.

Unlike traditional symmetric cryptographic systems, which use a single shared key for both encrypting and decrypting messages, RSA is based on the concept of a mathematically related pair of keys:

  • Private key: used exclusively to decrypt messages encrypted with the corresponding public key and must be kept strictly secret
  • Public key: used to encrypt data and can be freely distributed without compromising the security of the system

Mathematical Foundations of RSA

The cryptographic strength of RSA is founded on a computational problem in number theory: the factorization of very large integers into prime factors. More specifically, the security of the system depends on the practical difficulty of factoring the product of two extremely large prime numbers—an operation that, given the current state of technology and mathematics, requires prohibitive computational resources for appropriately sized keys (typically 2048 or 4096 bits).

The Key Generation Process

  1. Selection of primes: two distinct and sufficiently large prime numbers, p and q, are chosen
  2. Modulus calculation: n = p × q is computed, which serves as the modulus for encryption and decryption operations
  3. Euler’s totient function: φ(n) = (p-1)(q-1) is calculated, representing the count of integers coprime to n
  4. Public exponent: an integer e is selected such that 1 < e < φ(n) and GCD(e, φ(n)) = 1
  5. Private exponent: d is computed as the multiplicative inverse of e modulo φ(n), such that e × d ≡ 1 (mod φ(n))

The public key consists of the pair (e, n), while the private key is represented by the pair (d, n).

Encryption and Decryption Operations

  • Encryption: given a message M, the ciphertext C is obtained through the operation C = M^e mod n
  • Decryption: to recover the original message, the operation M = C^d mod n is applied

The mathematical correctness of this process is guaranteed by Euler’s theorem and modular arithmetic properties.

Practical Applications

RSA finds application in numerous contexts within modern information security:

  • Communication encryption: protection of emails, instant messages, and VPN connections.
  • Web security protocols: SSL/TLS for securing HTTPS connections
  • Digital signatures: authentication of sender identity and guarantee of document integrity
  • Public Key Infrastructure (PKI): digital certificates and certification authorities

This article will walk through a JavaScript implementation of the RSA algorithm and then demonstrate a classic cryptanalytic technique known as frequency analysis to attempt to break the encryption.

The Mathematics Behind the Code

The provided code starts with a few helper functions that are essential for the RSA algorithm to work. These functions handle primality testing, finding the greatest common divisor (GCD), and calculating the modular inverse, which are the mathematical building blocks of RSA key generation.

Core Mathematical Functions

function isPrime(num) {
    if (num <= 1) return false;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) return false;
    }
    return true;
}

function gcd(a, b) {
    if (b === 0) {
        return a;
    }
    return gcd(b, a % b);
}

function modInverse(a, m) {
    for (let x = 1; x < m; x++) {
        if (((a % m) * (x % m)) % m === 1) {
            return x;
        }
    }
    return 1;
}

Generating the Keys

The generateKeys(p, q) function takes two prime numbers, p and q, and generates the public and private keys. Here’s a breakdown of the process:

  1. Calculate n: The product of p and q gives us n, the modulus for both the public and private keys.
  2. Calculate phi(n): The totient phi(n) = (p-1) * (q-1) is calculated.
  3. Find e: A public exponent e is chosen such that it is co-prime to phi(n).
  4. Find d: The private exponent d is the modular multiplicative inverse of e and phi(n).

The public key is the pair [e, n], and the private key is [d, n].

Key Generation Logic

// Function to generate RSA public and private keys
function generateKeys(p, q) {
    if (!isPrime(p) || !isPrime(q)) {
        throw new Error("Both numbers must be prime.");
    }

    const n = p * q;
    const phi = (p - 1) * (q - 1);

    let e = 3;
    while (gcd(e, phi) !== 1) {
        e += 2;
    }

    const d = modInverse(e, phi);

    return {
        publicKey: [e, n],
        privateKey: [d, n],
    };
}

Encryption and Decryption

With the keys generated, we can now encrypt and decrypt messages.

  • encrypt(publicKey, text): This function takes the public key and the plaintext message. It iterates through each character of the message, gets its character code, and then applies the formula ciphertext = (plaintext ^ e) mod n.
  • decrypt(privateKey, encryptedText): The decryption process is similar but uses the private key and the formula plaintext = (ciphertext ^ d) mod n.

The power(base, exp, mod) function is a helper function that efficiently calculates the modular exponentiation required for both encryption and decryption.

Encryption and Decryption Functions

function power(base, exp, mod) {
    let res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 === 1) res = (res * base) % mod;
        exp = Math.floor(exp / 2);
        base = (base * base) % mod;
    }
    return res;
}

function encrypt(publicKey, text) {
    const [e, n] = publicKey;
    const encrypted = [];
    for (let i = 0; i < text.length; i++) {
        const charCode = text.charCodeAt(i);
        encrypted.push(power(charCode, e, n));
    }
    return encrypted;
}

function decrypt(privateKey, encryptedText) {
    const [d, n] = privateKey;
    let decrypted = "";
    for (let i = 0; i < encryptedText.length; i++) {
        const charCode = power(encryptedText[i], d, n);
        decrypted += String.fromCharCode(charCode);
    }
    return decrypted;
}

Frequency Analysis: A Classic Cryptanalytic Attack

Frequency analysis is a technique for breaking ciphers by analyzing the frequency of letters or groups of letters in a ciphertext. In the English language, for example, the letter ‘e’ is the most common, followed by ‘t’, ‘a’, ‘o’, ‘i’, ‘n’, ‘s’, ‘h’, ‘r’, ‘d’, ‘l’, and ‘u’. By counting the occurrences of each character in a ciphertext, a cryptanalyst can make educated guesses about which ciphertext characters correspond to which plaintext characters.

The frequencyAnalysisAttack(ciphertext) function in the provided code attempts to do just that:

  1. It counts the frequency of each number in the ciphertext.
  2. It sorts the encrypted numbers by their frequency, from most common to least common.
  3. It then maps the most frequent ciphertext number to ‘e’, the second most frequent to ‘t’, and so on, based on the known frequencies of English letters.
  4. Finally, it uses this mapping to “decrypt” the message.

Frequency Analysis

function frequencyAnalysisAttack(ciphertext) {
    const englishFrequencies = 'ETAOINSHRDLCUMWFGYPBVKJXQZ'.toLowerCase();

    const frequencies = {};
    for (const num of ciphertext) {
        frequencies[num] = (frequencies[num] || 0) + 1;
    }

    const sortedCipher = Object.keys(frequencies).sort((a, b) => frequencies[b] - frequencies[a]);

    const mapping = {};
    for (let i = 0; i < sortedCipher.length; i++) {
        mapping[sortedCipher[i]] = englishFrequencies[i];
    }

    let decryptedText = "";
    for (const num of ciphertext) {
        decryptedText += mapping[num];
    }

    return decryptedText;
}

Putting It All Together: The main Function

The main function demonstrates the entire process:

  1. It generates a public and private key pair using the prime numbers 17 and 31.
  2. It takes a long sample message and cleans it by removing spaces and punctuation and converting it to lowercase.
  3. It encrypts the cleaned message using the public key.
  4. It decrypts the message using the private key to verify that the encryption and decryption processes work correctly.
  5. It then attempts to crack the encrypted message using the frequencyAnalysisAttack function.
  6. Finally, it compares the original cleaned message to the cracked message and calculates the accuracy of the attack.

Main Execution Block

function main() {
    const p = 17;
    const q = 31;
    const keys = generateKeys(p, q);
    console.log("Generated Public Key:", keys.publicKey);
    console.log("Generated Private Key:", keys.privateKey);

    const originalMessage = `[Text from Moby Dick]`; 

    console.log("\nOriginal Message:", originalMessage);

    const cleanedMessage = originalMessage.toLowerCase().replace(/[^a-z]/g, "");
    console.log("\nCleaned Message for Encryption:", cleanedMessage);

    const encryptedMessage = encrypt(keys.publicKey, cleanedMessage);
    console.log("\nEncrypted Message (Ciphertext):", encryptedMessage.join(' '));

    const decryptedMessage = decrypt(keys.privateKey, encryptedMessage);
    console.log("\nDecrypted Message (with private key):", decryptedMessage);

    console.log("\n--- Starting Frequency Analysis Attack ---");
    const crackedMessage = frequencyAnalysisAttack(encryptedMessage);
    console.log("\nCracked Message (via Frequency Analysis):", crackedMessage);

    console.log("\n--- Comparison ---");
    console.log("Original (cleaned):", cleanedMessage);
    console.log("Cracked Message:   ", crackedMessage);

    let correctChars = 0;
    for (let i = 0; i < cleanedMessage.length; i++) {
        if (cleanedMessage[i] === crackedMessage[i]) {
            correctChars++;
        }
    }
    const accuracy = (correctChars / cleanedMessage.length) * 100;
    console.log(`\nAttack Accuracy: ${accuracy.toFixed(2)}%`);
}

main();

The following two figures illustrate the frequency distributions observed in the analyzed text. Figure 1 displays the letter frequencies in the original plaintext, while Figure 2 shows the corresponding numerical values obtained after encrypting each character using the RSA cryptosystem. As can be observed, the letter ‘e’ exhibits the highest frequency in the plaintext, whereas the number 33 appears most frequently in the ciphertext. This correspondence suggests a potential vulnerability: theoretically, each occurrence of 33 in the encrypted text could be substituted with the letter ‘e’, thereby enabling a frequency analysis attack.

Why Frequency Analysis Fails Against This Implementation

While frequency analysis represents a powerful cryptanalytic technique against classical substitution ciphers, its effectiveness is significantly limited when applied to properly implemented RSA encryption, as demonstrated in the code under examination.

In classical substitution ciphers, each plaintext character is deterministically mapped to a fixed ciphertext symbol—for instance, every occurrence of ‘a’ is consistently replaced with ‘q’. This deterministic one-to-one mapping preserves the underlying frequency distribution of the source language, rendering the cipher vulnerable to statistical attacks.

In contrast, the RSA implementation presented in this work encrypts each character independently using modular exponentiation based on the public key parameters (n, e). A critical distinction lies in the fact that identical plaintext characters may produce different ciphertext values depending on their position and context within the message, or when probabilistic padding schemes are employed. This non-deterministic behavior—a fundamental property of modern public-key cryptography—effectively disrupts the frequency patterns of the plaintext, thereby providing inherent resistance to frequency analysis attacks.

Conclusion

The JavaScript implementation presented in this work provides a practical demonstration of the RSA cryptosystem alongside an illustrative attempt to compromise it through classical cryptanalytic methods. While frequency analysis has proven historically significant in breaking classical ciphers—most notably contributing to the decryption of the Enigma machine during World War II—its ineffectiveness against this RSA implementation underscores a fundamental paradigm shift in cryptographic security. This contrast effectively illustrates the robustness of modern public-key cryptography and the substantial advancement from classical symmetric encryption schemes to contemporary asymmetric algorithms such as RSA.