BROE - Backref Encryption

An experimental combined encryption and compression.

by i_e_b

HTML

<p><b>DO NOT USE</b> this, it is just a curiosity.</p>
Input:<br/>
<textarea id="inp" rows="13" cols="80">--------------------
Your secret message.
--------------------
Make it as long as you like.
However, the algorithm does an exhaustive search, and is not optimised.
On a modern PC and browser, it should be fast enough for interactive use with short blocks of text.
Edit this text to see the encodings change as you type.

The length of the encoded output can change both based on the key, the pre-padding, and the redundancy in the secret message.</textarea>
<br/>
<button onclick="newKey()">New Key</button>
<button onclick="reEncode()">Repeat Same Key</button>
<br/>

Output: <canvas id="outpCanvas" height="32" width="32"></canvas> (first 1024 bytes as an image), all bytes as hex.
<pre id="outp">...</pre>

Recovered: <pre id="final">...</pre>

Key: <canvas id="keyCanvas" height="16" width="16"></canvas> (all bytes as image. Key is always 256 bytes)
<pre id="key">...</pre>

Recovered using a different key:<br/>
(note that repeated sections are recovered, and this ends up being a simple substitution cipher)
<pre id="guessString">...</pre>

<h2>About</h2>

<p>I don't know what the name of this kind of cipher is. Please <a href="https://crypto.stackexchange.com/questions/106072/what-is-the-name-of-this-kind-of-cipher-algorithm-and-description-provided">answer here if you know</a>. The helpful people at crypto.stackexchange pointed out some big problems with this as a cipher, so <b>DO NOT USE</b> this, it is just a curiosity.</p>

<p>The key is bytes valued 0..255, in a specific scattered order. This is prepended to the input.
The input is 'compressed' by back reference only -- no direct values are stored.</p>

<p>Each item in the output is a pair of (distance,length). Distance is number of bytes back to
the <b>end</b> of bytes to copy; length is number of bytes to copy. (so <code>position - distance - length</code> is the start of the range to copy). When searching for...

CSS

pre {
  font-size: 11px;
}

JavaScript

// ---[ TUNABLES ]---
const MinimumPad = 8;  // shortest allowable random padding
const MaximumPad = 31; // longest allowable random padding
const StopBias = 0.375; // bias toward stopping search early. 0..1
// ------------------


let key = shuffle(keySource()); // make random key

function createRandomKey(){
	key = shuffle(keySource()); // make random key
  
  // Display the key as a hex string:
	document.getElementById('key').innerText = bytesToStr(key);
  
  // Display the key as an image:
  fillCanvasWithBytes('keyCanvas', key);
}

function generatePrePad(){
	let padRange = MaximumPad - MinimumPad;
	let length = Math.floor(MinimumPad + Math.random() * padRange);
  let result = [];
  for (let i = 0; i < length; i++){
  	result.push(Math.floor(Math.random() * 255));
  }
  return result;
}

// Flip a coin. Returns true or false. This is allowed to be biased.
// This is used to stop looking for better matches further back in 
// the plaintext. This help with speed and making the output less
// deterministic in pathalogical cases, at a cost of larger outputs.
function stopHere(){
	return Math.random() < StopBias;
}

// Core encrypt function. Start at index 256, find greedy back-references
// Input is an array of 0..255 values.
// Output is an array of numbers, odds=distance, evens=length.
function encodeByBackref(byteArray) {
  let result = [];
  let cursor = 256;
  let longestEver = 0;
  let biggestOff = 0;

  while (cursor < byteArray.length) { // for each input chunk
    let bestStart = 0;
    let bestLength = -1;

    for (let i = cursor - 1; i >= 0; i--) { // search backward for best match (exhaustive)
      if (byteArray[i] !== byteArray[cursor]) continue; // no match
      // Got a match. find length of matching values
      let end = cursor - i;
      let l = 1;

      while (l < end && byteArray[i + l] == byteArray[cursor + l]) l++;

      // if this is the longest match yet, store it
      if (l > bestLength) {
        bestStart = i;
        bestLength...