RSA keyset generation using Euler's totient under 100 lines

rsa-euler.ts

/**
 * Calcula a potência de um número bigInt
 * O JS não suporta números inteiros maiores que 2^53-1
 * e BigInts não podem ser usados com o operador **, por isso
 * essa função foi criada
 */
function bigIntPower(base: number|bigint, exponent: number) {
  let result = 1n
  const bigBase = BigInt(base)
  for (let i = 0; i < exponent; i++) {
    result *= bigBase
  }
  return result
}

/** 
 * Calcula o mdc de dois números e os coeficientes de Bézout
 * usando o algoritmo de Euclides estendido
 */
function mdc(a: number, b: number) {
  let [absA, absB] = [Math.abs(a), Math.abs(b)]
  let [prevX, x] = [1, 0]
  let [prevY, y] = [0, 1]

  while (absB) {
    const q = Math.floor(absA / absB)
    ;[absB, absA] = [absA % absB, absB]
    ;[x, prevX] = [prevX - q * x, x]
    ;[y, prevY] = [prevY - q * y, y]
  }

  return {
    mdc: absA,
    x: prevX,
    y: prevY
  }
}

/**
 * Calcula o inverso modular de um número
 */
function modInverse(e: number, m: number) {
  const result = mdc(e, m)
  if (result.mdc !== 1) {
    throw new Error('modular inverse does not exist')
  }
  return ((result.x % m) + m) % m
}

/**
 * Calcula o expoente público de uma chave RSA
 */
function publicExponent(lambdaN: number) {
  let e = 2
  while (mdc(e, lambdaN).mdc !== 1 && e < lambdaN) {
    e++
  }
  return e
}

/**
 * Criptografa/Descriptografa uma mensagem usando a chave RSA
 */
function encrypt(message: number|bigint, key: Key) {
  return bigIntPower(message, key.exp) % BigInt(key.mod)
}

const p = 41 // numero primo p pequeno
const q = 97 // numero primo q pequeno
const n = p * q // módulo n = 3977
const psiN = Math.abs((p-1)*(q-1)) // totiente de Euler psi(n) = 3840
const e = publicExponent(psiN) // expoente publico 7
const d = modInverse(e, psiN) // expoente privado 343

// Chaves
type Key = { exp: number, mod: number }
const publicKey = { exp: e, mod: n }
const privateKey = { exp: d, mod: n }

// Exemplo de uso
const message = 42
const encrypted = encrypt(message, publicKey) // 698n
const decrypted = encrypt(encrypted, privateKey) // 42n -> mensagem original