rsa.js

// https://en.wikipedia.org/wiki/RSA_(cryptosystem)

// Least common multiple
function lcm(a, b) {
    let min = (a > b) ? a : b;
    while (true) {
        if (min % a === 0 && min % b === 0) {
            break;
        }
        min++;
    }
    return min;
}

// Modular multiplicative inverse
function modInverse(e, s) {
    for (let d = 1; d < s; d++) {
        if ((e * d) % s === 1) return d;
    }
}

// 1 - Choose two distinct prime numbers, such as
const p = 61;
const q = 53;
console.log('p:', p, 'q:', q);

// 2 -Compute n = pq (public key)
const n = p * q;
console.log('pub key - n:', n);

// 3 - Compute the Carmichael's totient function of the product as
// λ(n) = lcm(p − 1, q − 1)
const λ = lcm(p - 1, q - 1)
console.log('λ:', λ);

// 4 - Choose any number 1 < e < 780 that is coprime to 780.
// Choosing a prime number for e leaves us only to check that e is not a divisor of 780.
const e = 17;

// 5 - Compute d (private key), the modular multiplicative inverse of e (mod λ(n))
const d = modInverse(e, λ)
console.log('priv key - d:', d);

// https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
// in order to encrypt m = 65, one calculates
// c = 65^17 mod 3233 = 2790
let c = (BigInt(65) ** BigInt(e)) % BigInt(n)
console.log('Encrypted msg:', c);

// To decrypt c = 2790, one calculates
// m = 2790^413 % 3233 = 65
let m = (BigInt(c) ** BigInt(d)) % BigInt(n)
console.log('Decrypted msg:', m);

// https://crypto.stackexchange.com/questions/388/what-is-the-relation-between-rsa-fermats-little-theorem