CS Algorithms 101 – RSA

RSA (Rivest-Shamir-Adleman) is a public-key cryptosystem used for secure data transmission. It is based on the mathematical concept of prime factorization. Here is an example of how RSA encryption and decryption can be implemented in JavaScript:

function generateKeys(p, q) {
  const n = p * q;
  const phiN = (p - 1) * (q - 1);

  let e = 2;
  while (e < phiN && gcd(e, phiN) !== 1) {
    e++;
  }

  const d = modInverse(e, phiN);

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

function encrypt(message, publicKey) {
  const { e, n } = publicKey;
  return modPow(message, e, n);
}

function decrypt(ciphertext, privateKey) {
  const { d, n } = privateKey;
  return modPow(ciphertext, d, n);
}

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

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

  let result = 1;
  base = base % modulus;

  while (exponent > 0) {
    if (exponent % 2 === 1) {
      result = (result * base) % modulus;
    }
    exponent = Math.floor(exponent / 2);
    base = (base * base) % modulus;
  }

  return result;
}

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

// Example usage
const p = 11;
const q = 13;
const message = 7;
const keys = generateKeys(p, q);
const ciphertext = encrypt(message, keys.publicKey);
const plaintext = decrypt(ciphertext, keys.privateKey);
console.log(`Encrypted message: ${ciphertext}`);
console.log(`Decrypted message: ${plaintext}`);

Here are the steps for RSA encryption and decryption using JavaScript:

Generate two large prime numbers p and q and calculate their product n. These two numbers will be used to generate the public and private keys.

Calculate the Euler totient function of n, denoted by phi(n). This value is equal to (p-1) * (q-1).

Choose a public exponent e that is relatively prime to phi(n). In this example, we choose the smallest possible value e = 2 and increment it until we find an e that is relatively prime to phi(n).

Calculate the private exponent d such that d * e ≡ 1 (mod phi(n)). This can be done using the Extended Euclidean Algorithm or by calculating the modular multiplicative inverse of e modulo phi(n).

The public key consists of the pair (e, n) and the private key consists of the pair (d, n).

To encrypt a message, we convert it to a numerical value using a predetermined mapping, and then raise it to the power of e modulo n.

To decrypt the ciphertext, we raise it to the power of d modulo n.

To ensure the security of the RSA algorithm, it is essential to choose large prime numbers for p and q. These primes should be kept secret and should not be disclosed to anyone.

In summary, RSA encryption and decryption involve the use of a public key and a private key. The public key is used to encrypt messages, and the private key is used to decrypt them. The security of the algorithm relies on the fact that it is computationally infeasible to factorize large numbers into their prime factors. Therefore, an attacker cannot derive the private key from the public key, and hence, the message remains secure.