Implementing RSA from Scratch in JavaScript

Please note that it is essential for me to emphasize that the code and techniques presented here are intended solely for educational purposes and should never be employed in real-world applications without careful consideration and expert guidance.

At the same time, understanding the principles of RSA cryptography and exploring various implementations is valuable for educational purposes and understanding how to code encryption methods, building secure encryption systems for practical use requires adherence to industry standards, best practices, and thorough security assessments. An inadequate implementation or improper usage of cryptographic techniques can lead to severe vulnerabilities, jeopardizing the confidentiality and integrity of sensitive data.

Explaining RSA Cryptography

RSA cryptography is a fundamental concept in modern encryption techniques, especially prevalent in web development for securing data transmission over networks. While many developers are familiar with the concept of RSA, understanding the underlying mathematical principles can be challenging. This article aims to demystify the math behind RSA encryption in the context of JavaScript.

Explaining RSA Cryptography with JavaScript

Understanding the Mathematics behind RSA

RSA encryption relies on the mathematical properties of prime numbers, modular arithmetic, and number theory. At its core, RSA involves two keys: a public key for encryption (e) and a private key for decryption (d). The encryption and decryption process follows the principle:

scssCopy code(m^e)^d ≡ m (mod n)

Where m represents the original message, e is the encryption key, d is the decryption key, and n is the modulus. The security of RSA lies in the difficulty of deriving d from e and n, especially when n is a large composite number resulting from the multiplication of two large prime numbers.

Key Generation in RSA

The process of generating RSA keys involves the following steps:

Selecting Prime Numbers: Choose two large prime numbers, typically denoted as p and q.
Calculating Modulus: Compute n = p * q, which serves as the modulus for both the public and private keys.
Calculating Euler's Totient Function: Compute λ(n) = lcm(p-1, q-1), where lcm denotes the least common multiple. This value is crucial for key generation.
Selecting Encryption Key: Choose an encryption exponent e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1. Common choices include 65537.
Calculating Decryption Key: Compute the decryption exponent d using the Extended Euclidean Algorithm to solve the equation ed ≡ 1 (mod λ(n)).

Implementation in JavaScript

Let's translate the key components of RSA into JavaScript:

function extendedEuclidean(a, b) {
    // Base cases
    if (a === 0) {
        return [b, 0, 1];
    }

    let [gcd, x1, y1] = extendedEuclidean(b % a, a);
    
    // Calculate x and y using results of recursive call
    let x = y1 - Math.floor(b / a) * x1;
    let y = x1;

    return [gcd, x, y];
}

function modularInverse(a, m) {
    let [gcd, x, y] = extendedEuclidean(a, m);
    if (gcd !== 1) {
        // Modular inverse does not exist if gcd(a, m) != 1
        return null;
    } else {
        // Ensure x is positive
        x = (x % m + m) % m;
        return x;
    }
}

function modularExponentiation(base, exponent, modulus) {
    if (modulus === 1) return 0;

    let result = 1;
    base = base % modulus; // Reduce base modulo modulus to handle large base values efficiently

    while (exponent > 0) {

        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }

        exponent = Math.floor(exponent / 2);
        base = (base * base) % modulus;
    }

    return result;
}

function generateRSAKeys(p, q) {
    let n = p * q;
    let lambdaN = lcm(p - 1, q - 1);
    let e = 65537;
    let d = euclideanAlgorithm(e, lambdaN)[0];
    if (d < 0) d += lambdaN;
    return { publicKey: { e, n }, privateKey: { d, n } };
}

function encrypt(message, publicKey) {
    return modularExponentiation(message, publicKey.e, publicKey.n);
}

function decrypt(ciphertext, privateKey) {
    return modularExponentiation(ciphertext, privateKey.d, privateKey.n);
}

// Testing
let keys = generateRSAKeys(31337, 31357);
let publicKey = keys.publicKey;
let privateKey = keys.privateKey;
let message = 80087;
let encrypted = encrypt(message, publicKey);
let decrypted = decrypt(encrypted, privateKey);

console.log(decrypted);

The Conclusion

Understanding the mathematical principles behind RSA cryptography is essential for implementing secure encryption systems. In this article, we've provided an overview of RSA encryption and demonstrated its implementation in JavaScript. While the code presented here covers the core components of RSA, additional considerations such as prime number generation and handling larger messages should be addressed for practical usage.

Do you like what you're reading from the CoderOasis Technology Blog? We recommend reading our Implementing RSA in Python from Scratch as your next choice.

The CoderOasis Community

Did you know we have a Community Forums and Discord Server? which we invite everyone to join us? Want to discuss this article with other members of our community? Want to join a laid back place to chill and discuss topics like programming, cybersecurity, web development, and Linux? Consider joining us today!

Join the CoderOasis.com Discord Server!

CoderOasis offers technology news articles about programming, security, web development, Linux, systems admin, and more. | 112 members