"""
Cryptanalib3 - A series of useful functions for cryptanalysis
by Daniel "unicornFurnace" Crowley

dependencies - PyCryptodome
"""
# Get helper functions
from . import helpers
from . import frequency
import operator
from math import sqrt

# -------------------------
# Classical cryptography functions
# 
# This section contains functions useful for solving CTF and challenge site
# challenges. In general, you won't see cryptosystems vulnerable to these attacks
# being used in the real world. If you do, you should laugh.
# --------------------------
morse_table = {
   b'a': b'.-',
   b'b': b'-...',
   b'c': b'-.-.',
   b'd': b'-..',
   b'e': b'.',
   b'f': b'..-.',
   b'g': b'--.',
   b'h': b'....',
   b'i': b'..',
   b'j': b'.---',
   b'k': b'-.-',
   b'l': b'.-..',
   b'm': b'--',
   b'n': b'-.',
   b'o': b'---',
   b'p': b'.--.',
   b'q': b'--.-',
   b'r': b'.-.',
   b's': b'...',
   b't': b'-',
   b'u': b'..-',
   b'v': b'...-',
   b'w': b'.--',
   b'x': b'-..-',
   b'y': b'-.--',
   b'z': b'--..',
   b'1': b'.----',
   b'2': b'..---',
   b'3': b'...--',
   b'4': b'....-',
   b'5': b'.....',
   b'6': b'-....',
   b'7': b'--...',
   b'8': b'---..',
   b'9': b'----.',
   b'0': b'-----'
}


def morse_decode(text, dot=b'.', dash=b'-', space=b' '):
   '''
   Decodes a Morse encoded message. Optionally, you can provide an alternate
   single character for dot, dash, and space.

   Parameters:
   ``bytes`` text - A message to decode
   ``byte`` dot - An alternate dot char
   ``byte`` dash - An alternate dash char
   ``byte`` space - A char to split the text on

   Outputs:
   ``bytes`` The Morse-decoded version of ``text``, excluding any sequences that
      were not successfully decoded. Letters will be lower-case.
   '''
   dot_dash_trans = bytes.maketrans(b'.-', dot + dash)
   inverse_morse_table = [(bytes.translate(x, dot_dash_trans), y) for (y, x) in morse_table.items()]
   inverse_morse_table = dict(inverse_morse_table)
   result = b''
   for sequence in text.split(space):
      if sequence in inverse_morse_table.keys():
         result += inverse_morse_table[sequence]
   return result


def morse_encode(text, dot=b'.', dash=b'-', space=b' '):
   '''
   Encodes text into Morse code.

   Parameters:
   ``bytes`` text - The data to Morse-encode
   ``byte`` dot (optional) - An alternate character to use for dot
   ``byte`` dash (optional) - An alternate character to use for dash
   ``byte`` space (optional) - An alternate character to use to separate Morse sequences

   Outputs:
   ``bytes`` A ``space`` separated sequence of Morse-encoded sequences, including
      only the characters that could be encoded.
   '''
   dot_dash_trans = bytes.maketrans(b'.-', dot + dash)
   translated_morse_table = [(x_y1[0], bytes.translate(x_y1[1], dot_dash_trans)) for x_y1 in list(morse_table.items())]
   translated_morse_table = dict(translated_morse_table)
   output = []
   for char in text.lower():
      if bytes([char]) in helpers.lowercase_letters + helpers.digits:
         output.append(translated_morse_table[bytes([char])])
   return space.join(output)


def break_generic_shift(ciphertext, charset, num_answers=1, freq_table=frequency.frequency_tables['english'],
                        return_keys=False):
   '''
   Generic shift cipher brute forcer. Characters found in the ciphertext but not in the charset
   are ignored, but will still contribute to frequency scoring.

   Inputs:
   ``bytes`` ciphertext - Data encrypted with a shift cipher
   ``bytes`` charset - The character set, arranged in order (e.g. the alphabet,
      in order, when breaking Caesar's cipher)
   ``int`` num_answers - The number of answers to return
   ``dict`` freq_table - A dict of frequency information as generated by ``generate_frequency_table()``
   ``bool`` return_keys - Return the best keys alongside best candidate plaintexts

   Outputs:
   ``[bytes, ...]`` The num_answers best answers, as scored by plaintext detection. If ``return_keys``
      is ``True``, return ``[(bytes, int), ...]`` instead.
   '''

   def score_plaintext(sample):
      return helpers.detect_plaintext(sample, pt_freq_table=freq_table)

   answers = []
   charset_len = len(charset)
   for offset in range(charset_len):
      plaintext = b''
      for char in ciphertext:
         if bytes([char]) in charset:
            plaintext += charset[(charset.index(bytes([char])) + offset) % charset_len]
         else:
            plaintext += bytes([char])
      answers.append((plaintext, offset))
   if return_keys:
      return sorted(answers, key=lambda x: score_plaintext(x[0]))[:num_answers]
   else:
      return sorted([answer[0] for answer in answers], key=score_plaintext)[:num_answers]


def break_alpha_shift(ciphertext, num_answers=1, freq_table=frequency.frequency_tables['english_icase_letters'],
                      return_keys=False):
   '''
   Alphabetic shift (i.e. "Caesar", ROT-n) cipher brute forcer. Characters found in the
   ciphertext but not in the alphabet are ignored, but will still contribute to frequency scoring.
   
   Inputs:
   ``bytes`` ciphertext - A sample of alpha shift cipher encrypted text
   ``int`` num_answers - The number of best answers to return
   ``dict`` freq_table - Frequency information in the form returned by ``generate_frequency_table()``
   ``bool`` return_keys - Return the best keys alongside best candidate plaintexts

   Outputs:
   ``[bytes, ...]`` The num_answers best answers, as scored by plaintext detection. If ``return_keys``
      is ``True``, return ``[(bytes, int), ...]`` instead.
   '''
   return break_generic_shift(ciphertext.lower(), helpers.lowercase_letters, num_answers=num_answers, freq_table=freq_table,
                              return_keys=return_keys)


def break_ascii_shift(ciphertext, num_answers=1, freq_table=frequency.frequency_tables['english'], return_keys=False):
   '''
   ASCII shift cipher brute forcer. Characters found in the ciphertext but not in the
   alphabet are ignored, but will still contribute to frequency scoring.
   
   Inputs:
   ``bytes`` ciphertext - A sample of ASCII shift cipher encrypted text
   ``int`` num_answers - The number of best answers to return
   ``dict`` freq_table - Frequency information in the form returned by ``generate_frequency_table()``
   ``bool`` return_keys - Return the best keys alongside best candidate plaintexts

   Outputs:
   ``[bytes, ...]`` The ``num_answers`` best answers, as scored by plaintext detection. If ``return_keys``
      is ``True``, return ``[(bytes, int), ...]`` instead.
   '''
   return break_generic_shift(ciphertext, [bytes([x]) for x in range(256)], num_answers=num_answers,
                              freq_table=freq_table, return_keys=return_keys)


def break_columnar_transposition(ciphertext, pt_freq_table=frequency.frequency_tables['single_english'], num_answers=1):
   '''
   Uses brute force and plaintext detection to break columnar transposition

   Inputs:
   ``bytes`` ciphertext - The sample, encrypted with a columnar transposition cipher
   ``dict`` pt_freq_table - A frequency table as generated by ``generate_frequency_table()``
   ``int`` num_answers - The number of best answers to return
   
   Outputs:
   ``[bytes, ...]`` The ``num_answers`` best answers, as scored by plaintext detection.
   '''
   results = {}
   ciphertext_len = len(ciphertext)
   for num_cols in range(2, int(ciphertext_len / 2)):  # int works as floor() here
      result = b''.join([ciphertext[num::num_cols] for num in range(num_cols)])
      results[result] = helpers.detect_plaintext(result, pt_freq_table=pt_freq_table, detect_words=True)
   return sorted(list(results.items()), key=operator.itemgetter(1))[:num_answers]


def to_char(number):
   '''
   Converts an alphabetic offset into a letter, zero-indexed.

   Inputs:
   ``int`` number, an offset into the alphabet

   Outputs:
   ``bytes`` 
   '''
   return bytes([number + ord('A')])


def to_number(character):
   '''
   Converts ``character`` into an ``int`` representing its offset in the alphabet, zero-indexed.

   Inputs:
   ``bytes`` character - an English letter.

   Outputs:
   ``int``
   '''
   return character - 65  # ord('A') == 65


def ind_of_coinc(text, distance):
   '''
   Find the index of coincidence for a given sample ``text``, measuring characters that are 
   ``distance`` apart and finding how often characters are identical at some multiple of
   ``distance``.

   Inputs:
   ``bytes`` text - The sample to use
   ``int`` distance - The distance between characters to be checked for coincidence.

   Outputs:
   ``float`` The index of coincidence as a decimal number.
   '''
   # Cut list to length which is divisible through distance
   length = len(text)
   cutting = length % distance
   text = text[:length - cutting]
   # Initialize frequency list
   freq = [[0 for i in range(26)] for i in range(distance)]
   times = len(text) // distance
   if times == 1:
      # So called one time pad -> no chance!
      return 0
   ioc = [0] * distance
   for offset in range(distance):
      # Build a frequency table for each offset
      for i in range(times):
         freq[offset][to_number(text[i * distance + offset])] += 1
      # Calculate index of coincidence for each offset
      for f in freq[offset]:
         ioc[offset] += f * (f - 1.0) / (times * (times - 1.0))
   # Take the average over all processed offsets
   ioc_total = 0.0
   for i in ioc:
      ioc_total += i

   # Alternative: distance to reference index of coincidence of 0.065 (for english language)
   # ioc_total = 0
   # for i in ioc:
   #    ioc_total += (i-0.065)**2
   # return 1/ioc_total*len(ioc)
   return ioc_total / len(ioc)


def translate_vigenere(text, key, decrypt):
   '''
   Apply the Vigenere cipher in encrypt mode (or decrypt mode, if ``decrypt`` is ``True``)
   against ``text`` using ``key`` as the key. 

   Inputs:
   ``bytes`` text - The sample to process
   ``bytes`` key - The Vigenere key
   ``bool`` decrypt - Whether or not to decrypt (True to decrypt, False to encrypt)

   Outputs:
   ``bytes`` The processed data, uppercase, with only alphabetic characters included.
   '''
   result = []
   key_index = 0
   key = key.upper()
   for c in text:
      try:
         number = helpers.uppercase_letters.index(bytes([c]).upper())
      except ValueError:
         # Character not alphabetic -> skip encryption/decryption
         result.append(bytes([c]))
         continue
      current_shift = to_number(key[key_index])

      new_number = (number + (-current_shift if decrypt else current_shift)) % len(helpers.uppercase_letters)
      result.append(helpers.lowercase_letters[new_number] if bytes([c]).islower() else helpers.uppercase_letters[new_number])
      key_index = (key_index + 1) % len(key)

   return b"".join(result)


def evaluate_vigenere_key_length(ciphertext, max_length):
   '''
   Find the likely key length of the key used to encrypt a Vigenere-encrypted ``ciphertext``
   by checking index of coincidence between characters at various lengths up to ``max_length``.

   Inputs:
   ``bytes`` ciphertext - The sample to evaluate
   ``int`` max_length - The longest key length to try

   Outputs:
   ``[int, ...]`` The most likely key length according to IOC measurements
   '''
   # Calculate the index of coincidence for every key length assumption
   ioc_list = []
   for length in range(1, min(max_length + 1, len(ciphertext))):
      ioc_list.append(ind_of_coinc(ciphertext, length))

   # Check if we possibly caught a multiple of the actual key length:
   # subtract median from every index of coincidence and square
   ioc_median = sorted(ioc_list)
   ioc_median = ioc_median[len(ioc_list) // 2]
   ioc_contrast = [(x > ioc_median) * (x - ioc_median) ** 2 for x in ioc_list]

   # Look at the peaks
   ioc_sorted = sorted(list(enumerate(ioc_contrast, start=1)), key=lambda tup: tup[1], reverse=True)
   ioc_best_guesses = [tup for tup in ioc_sorted if tup[1] > 0.15 * max(ioc_contrast)]
   key_length_best_guesses = [list(x) for x in zip(*ioc_best_guesses)][0]
   key_length = key_length_best_guesses[0]

   # If a divisor of the guessed key length is also possible -> pick that one!
   repeat = True
   while repeat:
      repeat = False
      for divisor in range(2, int(sqrt(max_length))):
         if key_length % divisor == 0 and key_length / divisor in key_length_best_guesses:
            # Found a reasonable divisor -> key length can be reduced
            key_length /= divisor
            # With new key length: repeat process until no reasonable divisors are left
            repeat = True
            break

   # Change priority order if neccessary
   if not key_length == key_length_best_guesses[0]:
      key_length_best_guesses.remove(key_length)
      key_length_best_guesses.insert(0, key_length)

   return key_length_best_guesses


def break_vigenere(ciphertext, scan_range, num_answers=1, max_best_shifts=2,
                   num_key_lengths=1, letter_frequency=frequency.frequency_tables['english_icase_letters'],
                   num_key_guesses=100, coefficient_char_deviation=0, coefficient_word_count=1):
   '''
   Decrypt Vigenere-encrypted ``ciphertext`` without knowledge of the key, by
   checking different potential key lengths up to ``scan_range`` bytes long.

   Inputs:
   ``bytes`` ciphertext - The sample to decrypt
   ``int`` scan_range - The maximum key length to evaluate
   ``int`` num_answers - The number of answers to return
   ``int`` max_best_shifts - The number of different shifts to try when solving each
      letter shift
   ``int`` num_key_lengths - The number of key lengths to try when attempting to find
      the right key
   ``dict`` letter_frequency - A frequency table as generated by ``generate_frequency_table()``
   ``int`` num_key_guesses - The number of potential keys to generate and evaluate
   ``float`` coefficient_char_deviation - Multiplier to adjust scoring from ``detect_plaintext()``
      result based on deviation from expected character frequency
   ``float`` coefficient_word_count - Multiplier to adjust scoring from ``detect_plaintext()``
      result based on word count

   Outputs:
   ``[bytes, ...]`` A list of potential Vigenere keys ``num_answers`` long.
   '''

   def _break_shift(ciphertext, ref_letter_freq):
      # Measure letter frequency
      n = float(len(ciphertext))
      freq = [0] * 26
      for symbol in ciphertext:
         freq[to_number(symbol)] += 1
      freq = [i / n for i in freq]

      # Perform frequency analysis
      # Break shift cipher by chi-square like comparison of distribution with reference
      chi_square_shifts = []
      for shift in range(26):
         chi_square = []
         for k in range(26):
            chi_square.append((freq[(k + shift) % 26] - ref_letter_freq[k]) ** 2 / ref_letter_freq[k])
         chi_square_shifts.append(n * sum(chi_square))
      # Sort the shift guesses by ascending chi square value
      shifts = sorted(list(enumerate(chi_square_shifts)), key=lambda tup: tup[1])
      shifts = [(to_char(tup[0]), tup[1]) for tup in shifts]

      # Filter out the best few
      shifts_trunc = list(shifts)
      for k in range(len(shifts) - 1):
         if shifts[k + 1][1] < 50:
            continue
         elif shifts[k + 1][1] / shifts[k][1] > 1.6:
            # If the step from this chi square value to the next higher one is too big,
            # export only the list up to this value.
            shifts_trunc = shifts[:k + 1]
            break
      return list(zip(*shifts_trunc))[0]

   def _count_up(ll_indices, list_of_lists):
      for digit in range(len(ll_indices)):
         # For every digit: start increasing the left most
         ll_indices[digit] += 1
         if ll_indices[digit] < len(list_of_lists[digit]):
            # As soon as no carry overflow happens: stop increasing
            return ll_indices
         else:
            # Carry overfow to the next digit
            ll_indices[digit] = 0
            digit += 1
            continue
      # If all digits were cycled through, return None as stop sequence
      return None

   # First strip cipher from non-alphabetical characters, convert to upper
   ciphertext = bytes(filter(lambda x: chr(x).isalpha(), ciphertext))

   # This module has had issues dealing with short ciphertexts, and it's
   # statistically super unlikely to solve ciphertexts short enough to cause
   # it issues. Reject any ciphertexts less than 10 characters in length.
   if len(ciphertext) < 10:
      print('[*] Skipping sample, too short to solve statistically')
      return False

   # Determine the key length
   key_lengths = evaluate_vigenere_key_length(ciphertext, scan_range)[:num_key_lengths]

   # Blockwise frequency analysis:
   # Preparation for fast break_shift function: sort out single char probabilities
   ref_letter_freq = [letter_frequency[k] for k in list(helpers.lowercase_letters)]
   keys = {}

   #  Quick pre-sorting of the keys by single letter frequency analysis
   for key_length in key_lengths:
      # For every key_length guess in the list:
      # cut list to length which is divisible through the key length
      sub_blocks = [[ciphertext[i + j * key_length] for j in range(0, int(len(ciphertext) / key_length))] for i in
                    range(0, key_length)]

      # For every digit in the key (whose length we have now guessed), use an ascii shift cipher breaker
      # against all subblocks consisting of every k-th letter with k = key_length
      digits_shifts = []
      for i, sub_block in enumerate(sub_blocks):
         # Apply shift breaker. That one works on letter frequency analysis and returns
         # a list of the most likely shift guesses.
         shifts = _break_shift(sub_block, ref_letter_freq)
         digits_shifts.append(shifts[:min(len(shifts), max_best_shifts)])

      # Out of these shift guesses, construct all possible combinations of complete keys
      digit_shift_index = [0] * key_length
      while True:
         # Construct keys from different shift possibilities for each digit
         current_key = b"".join([digits_shifts[digit][digit_shift_index[digit]] for digit in range(len(digits_shifts))])

         # If more than one key lengths were guessed:
         if len(key_lengths) > 1 and key_length == min(key_lengths):
            # At the smallest key length: don't pre-sort and score theses, the more advanced multigraph and word
            # analysis further down will be quick on them -> just add them to the top of the list straight away.
            keys[current_key] = 0
         else:
            # Perform an encryption with this possible key and score its plaintext with single letter frequency
            plaintext = translate_vigenere(ciphertext, current_key, decrypt=True)
            keys[current_key] = helpers.detect_plaintext(plaintext.lower(), detect_words=False)

         if _count_up(digit_shift_index, digits_shifts) is None:
            break
   keys_sorted_by_single_letter_score = sorted(list(keys.items()), key=operator.itemgetter(1))

   # Now do a more advanced analysis on plaintext detection, this time additionally with
   # multigraph frequency analysis and common word count -> this is very slow but more accurate
   keys2 = []
   for (current_key, score) in keys_sorted_by_single_letter_score[:num_key_guesses]:
      plaintext = translate_vigenere(ciphertext, current_key, decrypt=True)
      keys2.append((current_key, helpers.detect_plaintext(plaintext.lower(), detect_words=(coefficient_word_count != 0.0),
                                                  individual_scores=True)))

   # weighting the different detect_plaintext analysis and sort the list
   weighting = lambda x: coefficient_char_deviation * x[1][0] + coefficient_word_count * x[1][1]
   keys_by_combinations = sorted(keys2, key=weighting)

   # strip list from score
   key_list = list(zip(*keys_by_combinations))[0]

   # Deal with possible key multiplication (eg. "SECRETSECRET" instead of "SECRET")
   if len(key_list) > 1:
      first_len = len(key_list[0])
      second_len = len(key_list[1])
      if first_len != second_len and first_len % second_len == 0:
         if key_list[1] == key_list[0][:second_len]:
            key_list.remove(key_list[1])

   return key_list[:num_answers]

"""
Cryptanalib3 - A series of useful functions for cryptanalysis
by Daniel "unicornFurnace" Crowley

dependencies - PyCryptodome
"""
# Get helper functions
from . import helpers
from . import frequency
import operator
from math import sqrt

# -------------------------
# Classical cryptography functions
# 
# This section contains functions useful for solving CTF and challenge site
# challenges. In general, you won't see cryptosystems vulnerable to these attacks
# being used in the real world. If you do, you should laugh.
# --------------------------
morse_table = {
   b'a': b'.-',
   b'b': b'-...',
   b'c': b'-.-.',
   b'd': b'-..',
   b'e': b'.',
   b'f': b'..-.',
   b'g': b'--.',
   b'h': b'....',
   b'i': b'..',
   b'j': b'.---',
   b'k': b'-.-',
   b'l': b'.-..',
   b'm': b'--',
   b'n': b'-.',
   b'o': b'---',
   b'p': b'.--.',
   b'q': b'--.-',
   b'r': b'.-.',
   b's': b'...',
   b't': b'-',
   b'u': b'..-',
   b'v': b'...-',
   b'w': b'.--',
   b'x': b'-..-',
   b'y': b'-.--',
   b'z': b'--..',
   b'1': b'.----',
   b'2': b'..---',
   b'3': b'...--',
   b'4': b'....-',
   b'5': b'.....',
   b'6': b'-....',
   b'7': b'--...',
   b'8': b'---..',
   b'9': b'----.',
   b'0': b'-----'
}


def morse_decode(text, dot=b'.', dash=b'-', space=b' '):
   '''
   Decodes a Morse encoded message. Optionally, you can provide an alternate
   single character for dot, dash, and space.

   Parameters:
   ``bytes`` text - A message to decode
   ``byte`` dot - An alternate dot char
   ``byte`` dash - An alternate dash char
   ``byte`` space - A char to split the text on

   Outputs:
   ``bytes`` The Morse-decoded version of ``text``, excluding any sequences that
      were not successfully decoded. Letters will be lower-case.
   '''
   dot_dash_trans = bytes.maketrans(b'.-', dot + dash)
   inverse_morse_table = [(bytes.translate(x, dot_dash_trans), y) for (y, x) in morse_table.items()]
   inverse_morse_table = dict(inverse_morse_table)
   result = b''
   for sequence in text.split(space):
      if sequence in inverse_morse_table.keys():
         result += inverse_morse_table[sequence]
   return result


def morse_encode(text, dot=b'.', dash=b'-', space=b' '):
   '''
   Encodes text into Morse code.

   Parameters:
   ``bytes`` text - The data to Morse-encode
   ``byte`` dot (optional) - An alternate character to use for dot
   ``byte`` dash (optional) - An alternate character to use for dash
   ``byte`` space (optional) - An alternate character to use to separate Morse sequences

   Outputs:
   ``bytes`` A ``space`` separated sequence of Morse-encoded sequences, including
      only the characters that could be encoded.
   '''
   dot_dash_trans = bytes.maketrans(b'.-', dot + dash)
   translated_morse_table = [(x_y1[0], bytes.translate(x_y1[1], dot_dash_trans)) for x_y1 in list(morse_table.items())]
   translated_morse_table = dict(translated_morse_table)
   output = []
   for char in text.lower():
      if bytes([char]) in helpers.lowercase_letters + helpers.digits:
         output.append(translated_morse_table[bytes([char])])
   return space.join(output)


def break_generic_shift(ciphertext, charset, num_answers=1, freq_table=frequency.frequency_tables['english'],
                        return_keys=False):
   '''
   Generic shift cipher brute forcer. Characters found in the ciphertext but not in the charset
   are ignored, but will still contribute to frequency scoring.

   Inputs:
   ``bytes`` ciphertext - Data encrypted with a shift cipher
   ``bytes`` charset - The character set, arranged in order (e.g. the alphabet,
      in order, when breaking Caesar's cipher)
   ``int`` num_answers - The number of answers to return
   ``dict`` freq_table - A dict of frequency information as generated by ``generate_frequency_table()``
   ``bool`` return_keys - Return the best keys alongside best candidate plaintexts

   Outputs:
   ``[bytes, ...]`` The num_answers best answers, as scored by plaintext detection. If ``return_keys``
      is ``True``, return ``[(bytes, int), ...]`` instead.
   '''

   def score_plaintext(sample):
      return helpers.detect_plaintext(sample, pt_freq_table=freq_table)

   answers = []
   charset_len = len(charset)
   for offset in range(charset_len):
      plaintext = b''
      for char in ciphertext:
         if bytes([char]) in charset:
            plaintext += charset[(charset.index(bytes([char])) + offset) % charset_len]
         else:
            plaintext += bytes([char])
      answers.append((plaintext, offset))
   if return_keys:
      return sorted(answers, key=lambda x: score_plaintext(x[0]))[:num_answers]
   else:
      return sorted([answer[0] for answer in answers], key=score_plaintext)[:num_answers]


def break_alpha_shift(ciphertext, num_answers=1, freq_table=frequency.frequency_tables['english_icase_letters'],
                      return_keys=False):
   '''
   Alphabetic shift (i.e. "Caesar", ROT-n) cipher brute forcer. Characters found in the
   ciphertext but not in the alphabet are ignored, but will still contribute to frequency scoring.
   
   Inputs:
   ``bytes`` ciphertext - A sample of alpha shift cipher encrypted text
   ``int`` num_answers - The number of best answers to return
   ``dict`` freq_table - Frequency information in the form returned by ``generate_frequency_table()``
   ``bool`` return_keys - Return the best keys alongside best candidate plaintexts

   Outputs:
   ``[bytes, ...]`` The num_answers best answers, as scored by plaintext detection. If ``return_keys``
      is ``True``, return ``[(bytes, int), ...]`` instead.
   '''
   return break_generic_shift(ciphertext.lower(), helpers.lowercase_letters, num_answers=num_answers, freq_table=freq_table,
                              return_keys=return_keys)


def break_ascii_shift(ciphertext, num_answers=1, freq_table=frequency.frequency_tables['english'], return_keys=False):
   '''
   ASCII shift cipher brute forcer. Characters found in the ciphertext but not in the
   alphabet are ignored, but will still contribute to frequency scoring.
   
   Inputs:
   ``bytes`` ciphertext - A sample of ASCII shift cipher encrypted text
   ``int`` num_answers - The number of best answers to return
   ``dict`` freq_table - Frequency information in the form returned by ``generate_frequency_table()``
   ``bool`` return_keys - Return the best keys alongside best candidate plaintexts

   Outputs:
   ``[bytes, ...]`` The ``num_answers`` best answers, as scored by plaintext detection. If ``return_keys``
      is ``True``, return ``[(bytes, int), ...]`` instead.
   '''
   return break_generic_shift(ciphertext, [bytes([x]) for x in range(256)], num_answers=num_answers,
                              freq_table=freq_table, return_keys=return_keys)


def break_columnar_transposition(ciphertext, pt_freq_table=frequency.frequency_tables['single_english'], num_answers=1):
   '''
   Uses brute force and plaintext detection to break columnar transposition

   Inputs:
   ``bytes`` ciphertext - The sample, encrypted with a columnar transposition cipher
   ``dict`` pt_freq_table - A frequency table as generated by ``generate_frequency_table()``
   ``int`` num_answers - The number of best answers to return
   
   Outputs:
   ``[bytes, ...]`` The ``num_answers`` best answers, as scored by plaintext detection.
   '''
   results = {}
   ciphertext_len = len(ciphertext)
   for num_cols in range(2, int(ciphertext_len / 2)):  # int works as floor() here
      result = b''.join([ciphertext[num::num_cols] for num in range(num_cols)])
      results[result] = helpers.detect_plaintext(result, pt_freq_table=pt_freq_table, detect_words=True)
   return sorted(list(results.items()), key=operator.itemgetter(1))[:num_answers]


def to_char(number):
   '''
   Converts an alphabetic offset into a letter, zero-indexed.

   Inputs:
   ``int`` number, an offset into the alphabet

   Outputs:
   ``bytes`` 
   '''
   return bytes([number + ord('A')])


def to_number(character):
   '''
   Converts ``character`` into an ``int`` representing its offset in the alphabet, zero-indexed.

   Inputs:
   ``bytes`` character - an English letter.

   Outputs:
   ``int``
   '''
   return character - 65  # ord('A') == 65


def ind_of_coinc(text, distance):
   '''
   Find the index of coincidence for a given sample ``text``, measuring characters that are 
   ``distance`` apart and finding how often characters are identical at some multiple of
   ``distance``.

   Inputs:
   ``bytes`` text - The sample to use
   ``int`` distance - The distance between characters to be checked for coincidence.

   Outputs:
   ``float`` The index of coincidence as a decimal number.
   '''
   # Cut list to length which is divisible through distance
   length = len(text)
   cutting = length % distance
   text = text[:length - cutting]
   # Initialize frequency list
   freq = [[0 for i in range(26)] for i in range(distance)]
   times = len(text) // distance
   if times == 1:
      # So called one time pad -> no chance!
      return 0
   ioc = [0] * distance
   for offset in range(distance):
      # Build a frequency table for each offset
      for i in range(times):
         freq[offset][to_number(text[i * distance + offset])] += 1
      # Calculate index of coincidence for each offset
      for f in freq[offset]:
         ioc[offset] += f * (f - 1.0) / (times * (times - 1.0))
   # Take the average over all processed offsets
   ioc_total = 0.0
   for i in ioc:
      ioc_total += i

   # Alternative: distance to reference index of coincidence of 0.065 (for english language)
   # ioc_total = 0
   # for i in ioc:
   #    ioc_total += (i-0.065)**2
   # return 1/ioc_total*len(ioc)
   return ioc_total / len(ioc)


def translate_vigenere(text, key, decrypt):
   '''
   Apply the Vigenere cipher in encrypt mode (or decrypt mode, if ``decrypt`` is ``True``)
   against ``text`` using ``key`` as the key. 

   Inputs:
   ``bytes`` text - The sample to process
   ``bytes`` key - The Vigenere key
   ``bool`` decrypt - Whether or not to decrypt (True to decrypt, False to encrypt)

   Outputs:
   ``bytes`` The processed data, uppercase, with only alphabetic characters included.
   '''
   result = []
   key_index = 0
   key = key.upper()
   for c in text:
      try:
         number = helpers.uppercase_letters.index(bytes([c]).upper())
      except ValueError:
         # Character not alphabetic -> skip encryption/decryption
         result.append(bytes([c]))
         continue
      current_shift = to_number(key[key_index])

      new_number = (number + (-current_shift if decrypt else current_shift)) % len(helpers.uppercase_letters)
      result.append(helpers.lowercase_letters[new_number] if bytes([c]).islower() else helpers.uppercase_letters[new_number])
      key_index = (key_index + 1) % len(key)

   return b"".join(result)


def evaluate_vigenere_key_length(ciphertext, max_length):
   '''
   Find the likely key length of the key used to encrypt a Vigenere-encrypted ``ciphertext``
   by checking index of coincidence between characters at various lengths up to ``max_length``.

   Inputs:
   ``bytes`` ciphertext - The sample to evaluate
   ``int`` max_length - The longest key length to try

   Outputs:
   ``[int, ...]`` The most likely key length according to IOC measurements
   '''
   # Calculate the index of coincidence for every key length assumption
   ioc_list = []
   for length in range(1, min(max_length + 1, len(ciphertext))):
      ioc_list.append(ind_of_coinc(ciphertext, length))

   # Check if we possibly caught a multiple of the actual key length:
   # subtract median from every index of coincidence and square
   ioc_median = sorted(ioc_list)
   ioc_median = ioc_median[len(ioc_list) // 2]
   ioc_contrast = [(x > ioc_median) * (x - ioc_median) ** 2 for x in ioc_list]

   # Look at the peaks
   ioc_sorted = sorted(list(enumerate(ioc_contrast, start=1)), key=lambda tup: tup[1], reverse=True)
   ioc_best_guesses = [tup for tup in ioc_sorted if tup[1] > 0.15 * max(ioc_contrast)]
   key_length_best_guesses = [list(x) for x in zip(*ioc_best_guesses)][0]
   key_length = key_length_best_guesses[0]

   # If a divisor of the guessed key length is also possible -> pick that one!
   repeat = True
   while repeat:
      repeat = False
      for divisor in range(2, int(sqrt(max_length))):
         if key_length % divisor == 0 and key_length / divisor in key_length_best_guesses:
            # Found a reasonable divisor -> key length can be reduced
            key_length /= divisor
            # With new key length: repeat process until no reasonable divisors are left
            repeat = True
            break

   # Change priority order if neccessary
   if not key_length == key_length_best_guesses[0]:
      key_length_best_guesses.remove(key_length)
      key_length_best_guesses.insert(0, key_length)

   return key_length_best_guesses


def break_vigenere(ciphertext, scan_range, num_answers=1, max_best_shifts=2,
                   num_key_lengths=1, letter_frequency=frequency.frequency_tables['english_icase_letters'],
                   num_key_guesses=100, coefficient_char_deviation=0, coefficient_word_count=1):
   '''
   Decrypt Vigenere-encrypted ``ciphertext`` without knowledge of the key, by
   checking different potential key lengths up to ``scan_range`` bytes long.

   Inputs:
   ``bytes`` ciphertext - The sample to decrypt
   ``int`` scan_range - The maximum key length to evaluate
   ``int`` num_answers - The number of answers to return
   ``int`` max_best_shifts - The number of different shifts to try when solving each
      letter shift
   ``int`` num_key_lengths - The number of key lengths to try when attempting to find
      the right key
   ``dict`` letter_frequency - A frequency table as generated by ``generate_frequency_table()``
   ``int`` num_key_guesses - The number of potential keys to generate and evaluate
   ``float`` coefficient_char_deviation - Multiplier to adjust scoring from ``detect_plaintext()``
      result based on deviation from expected character frequency
   ``float`` coefficient_word_count - Multiplier to adjust scoring from ``detect_plaintext()``
      result based on word count

   Outputs:
   ``[bytes, ...]`` A list of potential Vigenere keys ``num_answers`` long.
   '''

   def _break_shift(ciphertext, ref_letter_freq):
      # Measure letter frequency
      n = float(len(ciphertext))
      freq = [0] * 26
      for symbol in ciphertext:
         freq[to_number(symbol)] += 1
      freq = [i / n for i in freq]

      # Perform frequency analysis
      # Break shift cipher by chi-square like comparison of distribution with reference
      chi_square_shifts = []
      for shift in range(26):
         chi_square = []
         for k in range(26):
            chi_square.append((freq[(k + shift) % 26] - ref_letter_freq[k]) ** 2 / ref_letter_freq[k])
         chi_square_shifts.append(n * sum(chi_square))
      # Sort the shift guesses by ascending chi square value
      shifts = sorted(list(enumerate(chi_square_shifts)), key=lambda tup: tup[1])
      shifts = [(to_char(tup[0]), tup[1]) for tup in shifts]

      # Filter out the best few
      shifts_trunc = list(shifts)
      for k in range(len(shifts) - 1):
         if shifts[k + 1][1] < 50:
            continue
         elif shifts[k + 1][1] / shifts[k][1] > 1.6:
            # If the step from this chi square value to the next higher one is too big,
            # export only the list up to this value.
            shifts_trunc = shifts[:k + 1]
            break
      return list(zip(*shifts_trunc))[0]

   def _count_up(ll_indices, list_of_lists):
      for digit in range(len(ll_indices)):
         # For every digit: start increasing the left most
         ll_indices[digit] += 1
         if ll_indices[digit] < len(list_of_lists[digit]):
            # As soon as no carry overflow happens: stop increasing
            return ll_indices
         else:
            # Carry overfow to the next digit
            ll_indices[digit] = 0
            digit += 1
            continue
      # If all digits were cycled through, return None as stop sequence
      return None

   # First strip cipher from non-alphabetical characters, convert to upper
   ciphertext = bytes(filter(lambda x: chr(x).isalpha(), ciphertext))

   # This module has had issues dealing with short ciphertexts, and it's
   # statistically super unlikely to solve ciphertexts short enough to cause
   # it issues. Reject any ciphertexts less than 10 characters in length.
   if len(ciphertext) < 10:
      print('[*] Skipping sample, too short to solve statistically')
      return False

   # Determine the key length
   key_lengths = evaluate_vigenere_key_length(ciphertext, scan_range)[:num_key_lengths]

   # Blockwise frequency analysis:
   # Preparation for fast break_shift function: sort out single char probabilities
   ref_letter_freq = [letter_frequency[k] for k in list(helpers.lowercase_letters)]
   keys = {}

   #  Quick pre-sorting of the keys by single letter frequency analysis
   for key_length in key_lengths:
      # For every key_length guess in the list:
      # cut list to length which is divisible through the key length
      sub_blocks = [[ciphertext[i + j * key_length] for j in range(0, int(len(ciphertext) / key_length))] for i in
                    range(0, key_length)]

      # For every digit in the key (whose length we have now guessed), use an ascii shift cipher breaker
      # against all subblocks consisting of every k-th letter with k = key_length
      digits_shifts = []
      for i, sub_block in enumerate(sub_blocks):
         # Apply shift breaker. That one works on letter frequency analysis and returns
         # a list of the most likely shift guesses.
         shifts = _break_shift(sub_block, ref_letter_freq)
         digits_shifts.append(shifts[:min(len(shifts), max_best_shifts)])

      # Out of these shift guesses, construct all possible combinations of complete keys
      digit_shift_index = [0] * key_length
      while True:
         # Construct keys from different shift possibilities for each digit
         current_key = b"".join([digits_shifts[digit][digit_shift_index[digit]] for digit in range(len(digits_shifts))])

         # If more than one key lengths were guessed:
         if len(key_lengths) > 1 and key_length == min(key_lengths):
            # At the smallest key length: don't pre-sort and score theses, the more advanced multigraph and word
            # analysis further down will be quick on them -> just add them to the top of the list straight away.
            keys[current_key] = 0
         else:
            # Perform an encryption with this possible key and score its plaintext with single letter frequency
            plaintext = translate_vigenere(ciphertext, current_key, decrypt=True)
            keys[current_key] = helpers.detect_plaintext(plaintext.lower(), detect_words=False)

         if _count_up(digit_shift_index, digits_shifts) is None:
            break
   keys_sorted_by_single_letter_score = sorted(list(keys.items()), key=operator.itemgetter(1))

   # Now do a more advanced analysis on plaintext detection, this time additionally with
   # multigraph frequency analysis and common word count -> this is very slow but more accurate
   keys2 = []
   for (current_key, score) in keys_sorted_by_single_letter_score[:num_key_guesses]:
      plaintext = translate_vigenere(ciphertext, current_key, decrypt=True)
      keys2.append((current_key, helpers.detect_plaintext(plaintext.lower(), detect_words=(coefficient_word_count != 0.0),
                                                  individual_scores=True)))

   # weighting the different detect_plaintext analysis and sort the list
   weighting = lambda x: coefficient_char_deviation * x[1][0] + coefficient_word_count * x[1][1]
   keys_by_combinations = sorted(keys2, key=weighting)

   # strip list from score
   key_list = list(zip(*keys_by_combinations))[0]

   # Deal with possible key multiplication (eg. "SECRETSECRET" instead of "SECRET")
   if len(key_list) > 1:
      first_len = len(key_list[0])
      second_len = len(key_list[1])
      if first_len != second_len and first_len % second_len == 0:
         if key_list[1] == key_list[0][:second_len]:
            key_list.remove(key_list[1])

   return key_list[:num_answers]

Cryptanalib3 - A series of useful functions for cryptanalysis by Daniel "unicornFurnace" Crowley  dependencies - PyCryptodome # Get helper functions # ------------------------- # Classical cryptography functions # # This section contains functions useful for solving CTF and challenge site # challenges. In general, you won't see cryptosystems vulnerable to these attacks # being used in the real world. If you do, you should laugh. # -------------------------- Decodes a Morse encoded message. Optionally, you can provide an alternate    single character for dot, dash, and space.     Parameters:    ``bytes`` text - A message to decode    ``byte`` dot - An alternate dot char    ``byte`` dash - An alternate dash char    ``byte`` space - A char to split the text on     Outputs:    ``bytes`` The Morse-decoded version of ``text``, excluding any sequences that       were not successfully decoded. Letters will be lower-case. Encodes text into Morse code.     Parameters:    ``bytes`` text - The data to Morse-encode    ``byte`` dot (optional) - An alternate character to use for dot    ``byte`` dash (optional) - An alternate character to use for dash    ``byte`` space (optional) - An alternate character to use to separate Morse sequences     Outputs:    ``bytes`` A ``space`` separated sequence of Morse-encoded sequences, including       only the characters that could be encoded. Generic shift cipher brute forcer. Characters found in the ciphertext but not in the charset    are ignored, but will still contribute to frequency scoring.     Inputs:    ``bytes`` ciphertext - Data encrypted with a shift cipher    ``bytes`` charset - The character set, arranged in order (e.g. the alphabet,       in order, when breaking Caesar's cipher)    ``int`` num_answers - The number of answers to return    ``dict`` freq_table - A dict of frequency information as generated by ``generate_frequency_table()``    ``bool`` return_keys - Return the best keys alongside best candidate plaintexts     Outputs:    ``[bytes, ...]`` The num_answers best answers, as scored by plaintext detection. If ``return_keys``       is ``True``, return ``[(bytes, int), ...]`` instead. Alphabetic shift (i.e. "Caesar", ROT-n) cipher brute forcer. Characters found in the    ciphertext but not in the alphabet are ignored, but will still contribute to frequency scoring.        Inputs:    ``bytes`` ciphertext - A sample of alpha shift cipher encrypted text    ``int`` num_answers - The number of best answers to return    ``dict`` freq_table - Frequency information in the form returned by ``generate_frequency_table()``    ``bool`` return_keys - Return the best keys alongside best candidate plaintexts     Outputs:    ``[bytes, ...]`` The num_answers best answers, as scored by plaintext detection. If ``return_keys``       is ``True``, return ``[(bytes, int), ...]`` instead. ASCII shift cipher brute forcer. Characters found in the ciphertext but not in the    alphabet are ignored, but will still contribute to frequency scoring.        Inputs:    ``bytes`` ciphertext - A sample of ASCII shift cipher encrypted text    ``int`` num_answers - The number of best answers to return    ``dict`` freq_table - Frequency information in the form returned by ``generate_frequency_table()``    ``bool`` return_keys - Return the best keys alongside best candidate plaintexts     Outputs:    ``[bytes, ...]`` The ``num_answers`` best answers, as scored by plaintext detection. If ``return_keys``       is ``True``, return ``[(bytes, int), ...]`` instead. Uses brute force and plaintext detection to break columnar transposition     Inputs:    ``bytes`` ciphertext - The sample, encrypted with a columnar transposition cipher    ``dict`` pt_freq_table - A frequency table as generated by ``generate_frequency_table()``    ``int`` num_answers - The number of best answers to return        Outputs:    ``[bytes, ...]`` The ``num_answers`` best answers, as scored by plaintext detection. # int works as floor() here Converts an alphabetic offset into a letter, zero-indexed.     Inputs:    ``int`` number, an offset into the alphabet     Outputs:    ``bytes`` Converts ``character`` into an ``int`` representing its offset in the alphabet, zero-indexed.     Inputs:    ``bytes`` character - an English letter.     Outputs:    ``int`` # ord('A') == 65 Find the index of coincidence for a given sample ``text``, measuring characters that are     ``distance`` apart and finding how often characters are identical at some multiple of    ``distance``.     Inputs:    ``bytes`` text - The sample to use    ``int`` distance - The distance between characters to be checked for coincidence.     Outputs:    ``float`` The index of coincidence as a decimal number. # Cut list to length which is divisible through distance # Initialize frequency list # So called one time pad -> no chance! # Build a frequency table for each offset # Calculate index of coincidence for each offset # Take the average over all processed offsets # Alternative: distance to reference index of coincidence of 0.065 (for english language) # ioc_total = 0 # for i in ioc: #    ioc_total += (i-0.065)**2 # return 1/ioc_total*len(ioc) Apply the Vigenere cipher in encrypt mode (or decrypt mode, if ``decrypt`` is ``True``)    against ``text`` using ``key`` as the key.      Inputs:    ``bytes`` text - The sample to process    ``bytes`` key - The Vigenere key    ``bool`` decrypt - Whether or not to decrypt (True to decrypt, False to encrypt)     Outputs:    ``bytes`` The processed data, uppercase, with only alphabetic characters included. # Character not alphabetic -> skip encryption/decryption Find the likely key length of the key used to encrypt a Vigenere-encrypted ``ciphertext``    by checking index of coincidence between characters at various lengths up to ``max_length``.     Inputs:    ``bytes`` ciphertext - The sample to evaluate    ``int`` max_length - The longest key length to try     Outputs:    ``[int, ...]`` The most likely key length according to IOC measurements # Calculate the index of coincidence for every key length assumption # Check if we possibly caught a multiple of the actual key length: # subtract median from every index of coincidence and square # Look at the peaks # If a divisor of the guessed key length is also possible -> pick that one! # Found a reasonable divisor -> key length can be reduced # With new key length: repeat process until no reasonable divisors are left # Change priority order if neccessary Decrypt Vigenere-encrypted ``ciphertext`` without knowledge of the key, by    checking different potential key lengths up to ``scan_range`` bytes long.     Inputs:    ``bytes`` ciphertext - The sample to decrypt    ``int`` scan_range - The maximum key length to evaluate    ``int`` num_answers - The number of answers to return    ``int`` max_best_shifts - The number of different shifts to try when solving each       letter shift    ``int`` num_key_lengths - The number of key lengths to try when attempting to find       the right key    ``dict`` letter_frequency - A frequency table as generated by ``generate_frequency_table()``    ``int`` num_key_guesses - The number of potential keys to generate and evaluate    ``float`` coefficient_char_deviation - Multiplier to adjust scoring from ``detect_plaintext()``       result based on deviation from expected character frequency    ``float`` coefficient_word_count - Multiplier to adjust scoring from ``detect_plaintext()``       result based on word count     Outputs:    ``[bytes, ...]`` A list of potential Vigenere keys ``num_answers`` long. # Measure letter frequency # Perform frequency analysis # Break shift cipher by chi-square like comparison of distribution with reference # Sort the shift guesses by ascending chi square value # Filter out the best few # If the step from this chi square value to the next higher one is too big, # export only the list up to this value. # For every digit: start increasing the left most # As soon as no carry overflow happens: stop increasing # Carry overfow to the next digit # If all digits were cycled through, return None as stop sequence # First strip cipher from non-alphabetical characters, convert to upper # This module has had issues dealing with short ciphertexts, and it's # statistically super unlikely to solve ciphertexts short enough to cause # it issues. Reject any ciphertexts less than 10 characters in length. # Determine the key length # Blockwise frequency analysis: # Preparation for fast break_shift function: sort out single char probabilities #  Quick pre-sorting of the keys by single letter frequency analysis # For every key_length guess in the list: # cut list to length which is divisible through the key length # For every digit in the key (whose length we have now guessed), use an ascii shift cipher breaker # against all subblocks consisting of every k-th letter with k = key_length # Apply shift breaker. That one works on letter frequency analysis and returns # a list of the most likely shift guesses. # Out of these shift guesses, construct all possible combinations of complete keys # Construct keys from different shift possibilities for each digit # If more than one key lengths were guessed: # At the smallest key length: don't pre-sort and score theses, the more advanced multigraph and word # analysis further down will be quick on them -> just add them to the top of the list straight away. # Perform an encryption with this possible key and score its plaintext with single letter frequency # Now do a more advanced analysis on plaintext detection, this time additionally with # multigraph frequency analysis and common word count -> this is very slow but more accurate # weighting the different detect_plaintext analysis and sort the list # strip list from score # Deal with possible key multiplication (eg. "SECRETSECRET" instead of "SECRET")