Vigenère Cipher Cryptanalysis

Recover a message encrypted using a Vigenère cipher.

The message is lowercase ascii characters only and consists of permuted words from byte-heist.com. The key is 10-19 long.

For example, if the ciphertext is

bzvhljozbrsbulxjcomaezqxgftambtzqxvhukqwgtmlpqy...

corresponding to the key

abcdefghij

you should output the plaintext

byteheistisasitewhereyoucantestyourcodingskills...

Judge

(async function*(context: Context): Challenge {
  const words = "byte heist byte heist is a site where you can test your coding skills by solving challenges in as few bytes as possible the site will be similar to sites like code golf anarchy golf and the late week golf some unique features will include challenges will have a finite run time probably around months after this time all solutions will be made public a highly customizable judging system that will allow things like restricted source challenges alternate scoring systems self referential challenges etc though i also hope to have a good selection of basic code golf challenges too easily upload and colaberate on challenges via the interface built in ways to vote on challenges give feedback suggest test cases etc there will be curated challenges that contribute to a global leaderboard but you can also create private challenges to play with your friends or to use for cmcs etc right now there are already a few challenges you can try many things are incomplete expect the database to be wiped before help or keep up with updates consider joining the discord or watching the project on github pull requests very welcome".split(" ");
  for (let keyLength = 10; keyLength < 20; keyLength++){
    shuffle(words);
    const key = range(keyLength).map(x => rand(26));
    const plainText = words.join("");
    const cipherText = range(plainText.length).map((_,i) => String.fromCharCode((plainText.charCodeAt(i)-97 + key[i%keyLength])%26+97)).join("");
    yield (await context.run(cipherText)).assertEquals(plainText);
  }
  return context.noFailures();
})

Example Code

const words =
  "byte heist byte heist is a site where you can test your coding skills by solving challenges in as few bytes as possible the site will be similar to sites like code golf anarchy golf and the late week golf some unique features will include challenges will have a finite run time probably around months after this time all solutions will be made public a highly customizable judging system that will allow things like restricted source challenges alternate scoring systems self referential challenges etc though i also hope to have a good selection of basic code golf challenges too easily upload and colaberate on challenges via the interface built in ways to vote on challenges give feedback suggest test cases etc there will be curated challenges that contribute to a global leaderboard but you can also create private challenges to play with your friends or to use for cmcs etc right now there are already a few challenges you can try many things are incomplete expect the database to be wiped before help or keep up with updates consider joining the discord or watching the project on github pull requests very welcome".split(
    " "
  );
words.sort((a, b) => b.length - a.length);
const distinctWords = [...new Set(words)];
const range = (upperBound) => [...Array(upperBound).keys()];
const cipherText = require("fs").readFileSync(0) + "";
function gcd(a, b) {
  return a === 0 ? b : gcd(b % a, a);
}

function solve() {
  const substrings = {};
  for (let end = 10; end < cipherText.length; end++) {
    let start = end - 10;
    let substring = cipherText.slice(start, end);
    substrings[substring] = [...(substrings[substring] ?? []), start];
  }
  const substringsOrdered = Object.entries(substrings);
  substringsOrdered.sort((a, b) => b[1].length - a[1].length);
  const repeats = substringsOrdered.filter((x) => x[1].length > 1);
  const distances = [];
  for (const x of repeats) {
    for (let i = 1; i < x[1].length; i++) {
      distances.push(x[1][i] - x[1][i - 1]);
    }
  }
  const keyLengthMultiple = distances.reduce(gcd);
  const keyLengths = range(10)
    .map((x) => x + 10)
    .filter((x) => keyLengthMultiple % x == 0);

  for (const keyLength of keyLengths) {
    for (const repeat of repeats) {
      const key = range(keyLength).map((x) => 26);
      const offset = repeat[1][0] % keyLength;
      for (let i = 0; i < 10; i++) {
        key[(offset + i) % keyLength] =
          (repeat[0].charCodeAt(i) - "challenges".charCodeAt(i) + 260) % 26;
      }
      let plainText = range(cipherText.length)
        .map((x, i) => {
          const k = key[i % keyLength];
          if (k === 26) return 32;
          return ((cipherText.charCodeAt(i) - 97 - k + 26) % 26) + 97;
        })
        .map((x) => String.fromCharCode(x))
        .join("");
      const longerWords = distinctWords.filter((x) => x.length > 3);
      for (let i = 0; i < 10; i++) {
        for (const word of longerWords) {
          for (let s = 0; s < word.length; s++) {
            for (let e = s + 1; e < word.length; e++) {
              if (e - s > word.length - (i > 5 ? 3 : 5)) continue;
              const pattern = word.slice(0, s).padEnd(e, " ") + word.slice(e);
              plainText = plainText.replaceAll(pattern, word);
            }
          }
        }
        for (let j = 0; j < plainText.length; j++) {
          const c = plainText.charCodeAt(j);
          if (c === 32 || key[j % keyLength] !== 26) continue;
          key[j % keyLength] = (cipherText.charCodeAt(j) - c + 26) % 26;
        }
        plainText = range(plainText.length)
          .map((x, i) => {
            const k = key[i % keyLength];
            if (k === 26) return 32;
            return ((cipherText.charCodeAt(i) - 97 - k + 26) % 26) + 97;
          })
          .map((x) => String.fromCharCode(x))
          .join("");
      }

      if (
        !plainText.includes(" ") &&
        distinctWords.every((w) => plainText.includes(w))
      )
        return plainText;
    }
  }
}
console.log(solve());