find-key.md

Find key

Introduction

Key space > Speculative plaintext scorer > Candidate promoter > Results

Key spaces

We need to define the key space to search.

Kinds of key spaces

Type	Description
IKeySpace<TKey>	Represents a synchronous, sequential keyspace. (for example: in-memory)
IAsyncKeySpace<TKey>	Represents an asynchronous, sequential keyspace. (for example: read file)
IPartitionedKeySpace<TKey>	Represents a synchronous, parallel keyspace. (for example: brute-force)

The IKeySpace<TKey> represents the most basic key space. It is applicable to a small or medium set of values which are either already available in-memory or can be generated synchronously.

public interface IKeySpace<TKey>
{
	IEnumerable<TKey> GetKeys();
}

See InMemoryKeySpace<TKey> or IntKeySpace for example.

The IAsyncKeySpace<TKey> represents a key space where values are generated asynchronously. It is applicable to reading data from a file or a remote source.

public interface IAsyncKeySpace<TKey>
{
	IAsyncEnumerable<TKey> GetKeys();
}

See FileWordlistKeySpace for example.

The IPartitionedKeySpace<TKey> is the most advanced key space. It supports parallel enumeration, by breaking the whole key space into partitions. State can be preserved in each partition to reuse memory and avoid pooling. It is applicable to large key spaces which can be divided into chunks, for example brute force of characters or numbers.

public interface IPartitionedKeySpace<TKey>
{
	IEnumerable<IKeySpace<TKey>> GetPartitions(int? desiredCount = null);
}

See ArrayKeySpace<TKey> for example.

Built-in key spaces

List of general use key spaces:

Type	Description
InMemoryKeySpace<TKey>	A predefined set of values of type T.
WordlistKeySpace	A predefined list of words.
FileWordlistKeySpace	Reads words from a file line by line asynchronously.
IntKeySpace	Enumerates integers from a minimum to a maximum value.
ArrayKeySpace<TKey>	Generates variations of a set of values (a.k.a. brute force). Supports partitions for parallel enumeration.
AggregateKeySpace<TKey>	Aggregates multiple key spaces.

List of key spaces specific to ciphers:

Type	Description
ShiftKeySpace	Key space for the Shift cipher.
AffineKeySpace	Key space for the Affine cipher.
NthCharacterKeySpace	Key space for the Nth character cipher.

Scoring

We try to decrypt the ciphertext with each key, but we need to score the results, whether the decrypted text is gibberish or something meaningful.

public interface ISpeculativePlaintextScorer
{
	double Score(ReadOnlySpan<char> speculativePlaintext);
}

List of language statistics based use scorers:

Type	Description
RelativeLetterFrequencies	Compares relative frequencies of letters to reference.
RelativeFirstLetterOfWordsFrequencies	Compares relative frequencies of first letters of words to reference.
RelativeNGramFrequencies	Compares relative frequencies of n-grams of letters to reference.

List of optimized language statistics based use scorers:

Type	Description
AsciiRelativeLetterFrequencies	Compares relative frequencies of ASCII letters to reference.
TwoGramAsciiLettersRelativeFrequencies	Compares relative frequencies of 2-grams of ASCII letters to reference.

List of other general use scorers:

Type	Description
Substring	Returns 1 if the specified substring is found, otherwise 0.
AnySubstring	Returns 1 if any of the substrings is found, otherwise 0.
Regex	Returns 1 if the specified regular expression matches, otherwise 0.
Charset	Returns the percentage of how many of the characters can be found in the specified character set.
Wordlist	Returns the percentage of how many of the words can be found in the specified wordlist.
Aggregate	Aggregates the scores of multiple scorers.

Promotion of candidates

All speculative results have a score now, but we still need to decide which ones to select for further/manual analysis.

public interface ICandidatePromoter
{
	bool Promote(double score);
}

List of general use candidate promoters:

Type	Description
AllCandidatePromoter	Promotes all candidates.
OverThresholdCandidatePromoter	Promotes candidates only which has a score higher than specified.
ProgressivelyBetterCandidatePromoter	The all time high is progressively adjusted when a better result is found, and all candidates with lower score than that are dropped.

Analysis

Once we have everything set up for a search, we can start the search by supplying the desired configuration to KeyFinder.

Use Solve with a basic key space:

foreach (var candidate in KeyFinder.Solve(
	"Wkh txlfn eurzq ira mxpsv ryhu wkh odcb grj.",
	new ShiftCipher(),
	new ShiftKeySpace(WellKnownAlphabets.English),
	new SubstringSpeculativePlaintextScorer("quick")
))
{
	var plaintext = candidate.SpeculativePlaintext.Plaintext;
	var score = candidate.SpeculativePlaintext.Score;
	var key = candidate.Key;
	// ...
}

Use SolveParallelAsync with a parallel key space:

await foreach (var candidate in KeyFinder.SolveParallelAsync(
	"Wkh txlfn eurzq ira mxpsv ryhu wkh odcb grj.",
	new XorCipher(),
	new ArrayKeySpace(1, 3, Enumerable.Range(32, 96).ToHashSet()),
	new RelativeNGramFrequenciesSpeculativePlaintextScorer(
		Languages.English.GetNGramFrequencies(2)
	),
	new ProgressivelyBetterCandidatePromoter()
))
{
	// ...
}

Use SolveAsync with an asynchronous key space:

await foreach (var candidate in KeyFinder.SolveAsync(
	"Wkh txlfn eurzq ira mxpsv ryhu wkh odcb grj.",
	new XorCipher().AsStringKeyed(),
	new FileWordlistKeySpace(@"english.txt"),
	new RelativeNGramFrequenciesSpeculativePlaintextScorer(
		Languages.English.GetNGramFrequencies(2)
	),
	new ProgressivelyBetterCandidatePromoter()
))
{
	// ...
}

Solve a specific cipher for best result:

var best = KeyFinder.SolveForBest(
	"Wkh txlfn eurzq ira mxpsv ryhu wkh odcb grj.",
	new ShiftCipher(),
	new ShiftKeySpace(WellKnownAlphabets.English),
	new SubstringSpeculativePlaintextScorer("quick")
);

Utilities