Cryptanalysis of a cipher from Reddit

cryptanalysis.js

/// Cryptanalysis of https://www.reddit.com/r/cryptography/comments/1qfv98w/i_have_a_question_about_whether_something_would/
/// This is free and unencumbered software released into the public domain.

/** Generate a translation table of numbers corresponding to each character at the same index in `alphabet` */
function generate_translation_table(alphabet) {
  const used = new Set();
  const table = [];
  Array.from(alphabet).forEach(() => {
    let n = 0;
    while (n == 0 || used.has(n)) {
      n = Math.floor(Math.random() * 150) + 1;
    }
    used.add(n);
    table.push(n);
  });
  return table;
}

/** Generate a random password of the given `length`, using the characters in `alphabet`. */
function generate_password(alphabet, length) {
  return new Array(length).fill(0).map(() => alphabet[Math.floor(Math.random() * alphabet.length)]).join('');
}

/** Generate a suite of cipher functions using the given `alphabet` and `table` (public parameters). */
function create_cipher(alphabet, table) {
  function word_to_numbers(word) {
    return Array.from(word).map(ch => table[alphabet.indexOf(ch) % table.length]);
  }

  function word_from_numbers(numbers) {
    return numbers.map(n => alphabet[table.indexOf(n) % alphabet.length]).join('');
  }

  function numbers_to_encoded(numbers) {
    return numbers.map(n => n.toString(10).padStart(5, '0')).join('');
  }

  function numbers_from_encoded(encoded) {
    if (encoded.length === 0) {
      return [];
    } else {
      return [parseInt(encoded.substring(0, 5), 10), ...numbers_from_encoded(encoded.substring(5))];
    }
  }

  function encipher(password, message) {
    const key_numbers = word_to_numbers(password);
    const msg_numbers = word_to_numbers(message);
    return numbers_to_encoded(msg_numbers.map((n, i) => n * key_numbers[i % key_numbers.length]));
  }

  function decipher(password, ciphertext) {
    const key_numbers = word_to_numbers(password);
    const ciphertext_numbers = numbers_from_encoded(ciphertext);
    return word_from_numbers(ciphertext_numbers.map((n, i) => n / key_numbers[i % key_numbers.length]));
  }

  return {
    word_to_numbers,
    word_from_numbers,
    numbers_to_encoded,
    numbers_from_encoded,
    encipher,
    decipher,
  };
}

/** Euclidean algorithm for greatest common divisor */
function gcd(a, b) {
  if (a < b) {
    return gcd(b, a);
  } else if (b === 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

function break_cipher(encrypted_passwords, suite) {
  const { word_to_numbers, word_from_numbers, numbers_from_encoded } = suite;
  const password_numbers = encrypted_passwords.map(numbers_from_encoded);
  password_numbers.sort((a, b) => b.length - a.length);
  const key_guess = password_numbers[0].map((k, i) => (
    password_numbers
      .filter(pw => pw.length > i)
      .reduce(
        (k, pw) => gcd(k, pw[i]),
        k
      )
  ));

  const out_of_bounds_index = key_guess.findIndex(ki => ki > 150);
  const truncated_key = out_of_bounds_index >= 0 ? key_guess.slice(0, out_of_bounds_index) : key_guess;

  const cycle_scores = truncated_key.map((_, i) => i).map(len => {
    const score = truncated_key.filter((ki, i) => ki === truncated_key[i % len]).length;
    return { len, score };
  });
  cycle_scores.sort((a, b) => b.score - a.score);
  const unrepeated_key = key_guess.slice(0, (cycle_scores[0] || {}).len || key_guess.length);

  return { key_guess, unrepeated_key };
}


const alphabet = `abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()_+[]{}:"|;',.<>/?`;
const table = generate_translation_table(alphabet);
const suite = create_cipher(alphabet, table);
const { encipher, decipher, word_from_numbers } = suite;

const master_password = generate_password(alphabet, 16 + Math.floor(Math.random() * 32));
console.log({ master_password });

const passwords = new Array(40).fill(0).map(() => generate_password(alphabet, 8 + Math.floor(Math.random() * 56)));
console.log({ passwords });

const encrypted_passwords = passwords.map(pw => encipher(master_password, pw));
const decrypted_passwords = encrypted_passwords.map(ct => decipher(master_password, ct));
if (!decrypted_passwords.every((dpw, i) => dpw === passwords[i])) {
  throw new Error('Incorrect result after decryption');
}

for (let num_passwords = 1; num_passwords <= encrypted_passwords.length ; ++num_passwords) {
  const solution = break_cipher(encrypted_passwords.slice(0, num_passwords), suite);
  const { unrepeated_key: broken_key, key_guess } = solution;
  const broken_master_password = word_from_numbers(broken_key);
  const repeating_broken_master_password = word_from_numbers(key_guess);
  if (broken_master_password === master_password) {
    console.log(solution);
  }
  console.log(`Using ${num_passwords} encrypted passwords:`, { repeating_broken_master_password, broken_master_password });

  const repeating_decryptions = encrypted_passwords.map(ct => decipher(repeating_broken_master_password, ct));
  const repeating_correct_decryptions = repeating_decryptions.filter((dpw, i) => dpw === passwords[i]).length;
  const decryptions = encrypted_passwords.map(ct => decipher(broken_master_password, ct));
  const correct_decryptions = decryptions.filter((dpw, i) => dpw === passwords[i]).length;
  console.log(`Correct decryptions with repeating password: ${repeating_correct_decryptions} of ${passwords.length}`);
  console.log(`Correct decryptions with truncated password: ${correct_decryptions} of ${passwords.length}`);

  if (broken_master_password === master_password) {
    console.log(`Exact match found after ${num_passwords} encrypted passwords.`);
    break;
  }
}