/
challenge_6.ex
81 lines (69 loc) · 2.28 KB
/
challenge_6.ex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
defmodule SetOne.ChallengeSix do
use Bitwise
alias SetOne.ChallengeThree, as: ChallengeThree
@doc """
Attempts to find the key of a given ciphertext encrypted with repeating XOR.
http://cryptopals.com/sets/1/challenges/6
"""
@spec find_key_repeating_xor(binary) :: [binary]
def find_key_repeating_xor(ciphertext) do
guess_keysizes(ciphertext)
|> Helpers.pmap(&find_key_repeating_xor(ciphertext, &1))
end
def find_key_repeating_xor(ciphertext, {keysize, _}) do
ciphertext
|> :binary.bin_to_list()
|> Stream.chunk_every(keysize, keysize, :discard)
|> Helpers.transpose()
|> Helpers.pmap(fn list ->
{key, _, _} = ChallengeThree.my_decoder(list)
key
end)
end
@doc """
Attempts to guess the keysize by calculating the average hamming distance of blocks and picking the three smallest
"""
@spec guess_keysizes(binary) :: [{pos_integer, pos_integer}]
def guess_keysizes(ciphertext) do
2..40
|> Helpers.pmap(&{&1, calculate_block_distance(&1, ciphertext)})
|> Enum.sort_by(fn {_keysize, distance} -> distance end)
|> Enum.take(3)
end
@doc """
Calculates the normalized averages of the hamming distances
"""
@spec calculate_block_distance(pos_integer, binary) :: float
def calculate_block_distance(block_size, ciphertext) do
ciphertext
|> :binary.bin_to_list()
|> Enum.chunk_every(block_size)
|> sum_hamming_and_average
end
defp sum_hamming_and_average(blocks), do: sum_hamming(blocks) / length(blocks)
defp sum_hamming([_first]), do: 0
defp sum_hamming([first | tail]) do
hamming(first, hd(tail)) / length(first) + sum_hamming(tail)
end
@doc """
Calcualtes the Hamming Distance of two strings
http://cryptopals.com/sets/1/challenges/6/
### Examples
iex> SetOne.ChallengeSix.hamming("abc", "abc")
0
iex> SetOne.ChallengeSix.hamming("0", "1")
1
"""
@spec hamming(binary, binary) :: pos_integer
def hamming(first, second) when is_binary(first) and is_binary(second) do
a = :binary.bin_to_list(first)
b = :binary.bin_to_list(second)
hamming(a, b)
end
@spec hamming([byte], [byte]) :: pos_integer
def hamming(a, b) do
Enum.zip(a, b)
|> Enum.map(fn {x, y} -> x ^^^ y end)
|> Enum.reduce(0, fn x, acc -> acc + Helpers.count_bits(x) end)
end
end