Advertisement
CSenshi

Cryptography - HW1.6 (Challenge-06)

Jan 10th, 2020
471
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.99 KB | None | 0 0
  1. from base64 import b64decode
  2. from itertools import zip_longest
  3. import math
  4. import binascii
  5.  
  6.  
  7. def hamming_distance(s1, s2):
  8.     diffs = 0
  9.     for ch1, ch2 in zip(s1, s2):
  10.         if ch1 != ch2:
  11.             diffs += 1
  12.     return diffs
  13.  
  14.  
  15. def score(s):
  16.     # frequencies taken from web
  17.     freq = {'a': 6517, 'b': 1242, 'c': 2173, 'd': 3498, 'e': 10414, 'f': 1978, 'g': 1586, 'h': 4928, 'i': 5580, 'j': 90,
  18.             'k': 505, 'l': 3314, 'm': 2021, 'n': 5645, 'o': 5963, 'p': 1376, 'q': 86, 'r': 4975, 's': 5157, 't': 7293,
  19.             'u': 2251, 'v': 829, 'w': 1712, 'x': 136, 'y': 1459, 'z': 78, ' ': 19181}
  20.     # convert string to lowercase
  21.     s = s.lower()
  22.     # sum up frequencies
  23.     result = sum([freq[ch] if (ch in freq) else 0 for ch in s])
  24.  
  25.     return result
  26.  
  27.  
  28. def solve_multiple_xor(transposed_blocks):
  29.     arr = []
  30.     # iterate and solve for each block
  31.     for x in transposed_blocks:
  32.         # conert to characters and join to make string
  33.         l = ''.join(list(map(chr, x)))
  34.         # solve and append to array of solutions
  35.         arr.append(solve_single_xor(l))
  36.  
  37.     return arr
  38.  
  39.  
  40. def solve_single_xor(s):
  41.     # iterate over all characters
  42.     result_arr = []
  43.     for ind in range(256):
  44.         # xor each char
  45.         result = ''
  46.         for t in s:
  47.             r = ord(t) ^ ind
  48.             result += chr(r)
  49.         # if given text is built with regex return answer
  50.         cur_score = score(result)
  51.         result_arr += [(cur_score, result)]
  52.     # choose max from results
  53.     final_result = max(result_arr)
  54.     # return only string answer
  55.     return final_result[1]
  56.  
  57.  
  58. def transpose(chunks):
  59.     # transpose matrix (padded with None values to fill)
  60.     result = list(zip_longest(*chunks))
  61.     # remove None values from list
  62.     result = [list(filter(lambda a:a != None, x)) for x in result]
  63.     # return list of lists
  64.     return result
  65.  
  66.  
  67. def _eval_score_for_key(cipher, K_len):
  68.     score = 0
  69.     # for each pair find hamming distance
  70.     for i in range((len(cipher) // K_len) - 1):
  71.         # get pairs
  72.         s1 = cipher[i * K_len:(i + 1) * K_len]
  73.         s2 = cipher[(i + 1) * K_len:(i + 2) * K_len]
  74.         # evaluate current score (normalize with key size)
  75.         result = hamming_distance(s1, s2) / K_len
  76.         # append to score
  77.         score += result
  78.     # normalize final score with total pairs evaluated
  79.     score /= (len(cipher) // K_len) - 1
  80.     # return score and current K_len
  81.     return (score, K_len)
  82.  
  83.  
  84. def get_key_size(s):
  85.     # decode and encode with given base64
  86.     s = binascii.a2b_base64(s.encode()).decode()
  87.     # given ranges
  88.     R_MIN = 2
  89.     R_MAX = 41
  90.     # calculate score for each key size between 2 and 41
  91.     scores_array = [_eval_score_for_key(s, x) for x in range(R_MIN, R_MAX)]
  92.     # we say that it's minimum will be our result
  93.     _, K_len = min(scores_array)
  94.     # return key size
  95.     return K_len
  96.  
  97.  
  98. def break_repeating_key_xor(cipher):
  99.     """ Step 1: Find Key Size """
  100.     K_len = get_key_size(cipher)
  101.  
  102.     """ Step 2: Decode from Base64"""
  103.     cipher = b64decode(cipher)
  104.  
  105.     """ Step 3: break the ciphertext into blocks of KEYSIZE length. """
  106.     blocks = [cipher[i:i + K_len]
  107.               for i in range(0, len(cipher), K_len)]
  108.  
  109.     """ Step 4: Now transpose the blocks:
  110.                make a block that is the first byte of every block,
  111.                and a block that is the second byte of every block, and so on... """
  112.     transposed_blocks = transpose(blocks)
  113.  
  114.     """ Step 5: Solve each block as if it was single-character XOR. """
  115.     key = solve_multiple_xor(transposed_blocks)
  116.  
  117.     """ Step 6: Transpose back to normal """
  118.     result = transpose(key)
  119.  
  120.     """ Step 7: convert list of lists to string """
  121.     result = list(map(lambda x: ''.join(x), result))
  122.     result = ''.join(result)
  123.  
  124.     return result
  125.  
  126.  
  127. if __name__ == "__main__":
  128.     # input key
  129.     cipher = input()
  130.     # break cipher
  131.     plain_text = break_repeating_key_xor(cipher)
  132.     # ouput decrypted
  133.     print(plain_text)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement