Хорошо, давайте попробуем переписать это как функциональную программу.Я пойду дальше и использую Haskell, потому что это лучший инструмент не для всех работ, а для этой конкретной работы.C не был действительно разработан, чтобы сделать пример, подобный этому, элегантно.
Давайте начнем изнутри.Внутреннее тело вашего цикла выглядит следующим образом:
key[0] = letters[a];
key[1] = letters[b];
key[2] = letters[c];
key[3] = letters[d];
key[4] = letters[e];
if (strcmp(crypt(key, salt), hash) == 0)
{
printf("%s\n", key);
return 0;
}
Это зависит от массива с именем letters, индексов цикла a, b, c, d и e, переменные key, salt и hash, а также вызов библиотеки crypt.
Замечу, что существует условие завершения.Если зашифрованный текст равен хэшу, который вы пытаетесь расшифровать с помощью перебора, программа печатает текущий ключ и завершает работу.Это оба побочных эффекта, которые не могут появиться в чистой функции, и хотя мы могли бы включить их, я фактически буду возвращать либо Just key, либо Nothing, если совпадения нет.Если тип key имеет имя Key, это делает тип возвращаемого значения Maybe Key.
. Параметры с a по e каждый нумеруются от 0 до length - 1.В функциональной программе мы могли бы сделать эти пять отдельных параметров, но вместо этого я собираюсь объявить Key псевдоним типа (Char, Char, Char, Char, Char) (пять символов).
Далее мы можем определитьсписок всего ключевого пространства, от ('A','A','A','A','A') и затем ('A','A','A','A','B') до ('Z','Z','Z','Z','Z'), по порядку.К сожалению, шаблон для создания диапазона, подобного [firstKey..lastKey] work , слишком сложен, чтобы использовать его в качестве примера того, насколько хорошим может быть функциональный код, , но, по крайней мере, я могу написать его интуитивно в качестве понимания списка.
allKeys = [(a, b, c, d, e) | a <- ['A'..'Z'],
b <- ['A'..'Z'],
c <- ['A'..'Z'],
d <- ['A'..'Z'],
e <- ['A'..'Z'] ]
Обратите внимание, что, поскольку Haskell является языком с ленивой оценкой, он вычисляет только те значения, которые он фактически использует.Весь список не генерируется заранее.Фактически, GHC, возможно, вообще может избежать создания объекта связанного списка.
Параметры нашей внешней функции, которые не изменяются между итерациями цикла, вероятно, должны быть параметрами нашей внешней функции, которую мы будемЗвоните bruteForce.Для простоты мы примем 16-разрядную соль без знака и 64-разрядный хеш без знака.Для простоты, он будет перебором всего пространства ключей, а не разрешит его разбиение.
import Data.Word (Word16, Word64)
type Salt = Word16
type Hash = Word64
bruteForce :: Salt -> Hash -> Maybe Key
Существует множество способов записи bruteForce, но вы запросили рекурсивное решение, поэтому давайте напишемвспомогательная функция.Обычное имя для рекурсивного помощника будет go или bruteForce'.Я пойду с go, потому что он короче.Поскольку это вложенная локальная функция, она может ссылаться на параметры salt и hash.Позже я перенесу наше определение списка всего пространства клавиш внутри функции, которая его использует:
bruteForce :: Salt -> Hash -> Maybe Key
bruteForce salt hash = go allKeys
where
go :: [Key] -> Maybe Key
-- Terminating case: we exhausted the key space without finding a match.
go [] = Nothing
-- Terminating case: we found a match.
go (x:_) | crypt x salt == hash = Just x
-- Tail-recursive case: no match so far.
go (x:xs) = go xs
Остался, как вы могли заметить, один недостающий фрагмент.Эта хвостовая рекурсивная функция вызывает crypt x salt и сравнивает результат с hash, возвращая значение Just x, если они равны.В этом контексте x - это Key, а salt - это Salt, поэтому должна существовать некоторая функция crypt, которая принимает Key и Salt и возвращает Hash.
В демонстрационных целях я сделаю простое перечисление каждой возможной пары ключ / соль от (AAAAA, 0x0000) → 0 до (ZZZZZ, 0xFFFF) → 778 657 857 535.
Помещениевсе вместе, мы получаем:
module Crack (bruteForce, crypt) where
import Data.Word (Word16, Word64)
type Key = (Char, Char, Char, Char, Char)
type Salt = Word16
type Hash = Word64
bruteForce :: Salt -> Hash -> Maybe Key
bruteForce salt hash = go allKeys
where
allKeys = [(a, b, c, d, e) | a <- ['A'..'Z'],
b <- ['A'..'Z'],
c <- ['A'..'Z'],
d <- ['A'..'Z'],
e <- ['A'..'Z'] ]
go :: [Key] -> Maybe Key
-- Terminating case: we exhausted the key space without finding a match.
go [] = Nothing
-- Terminating case: we found a match.
go (x:_) | crypt x salt == hash = Just x
-- Tail-recursive case: no match so far.
go (x:xs) = go xs
crypt :: Key -> Salt -> Hash
crypt (a, b, c, d, e) salt = let
a' = fromLetter a
b' = fromLetter b
c' = fromLetter c
d' = fromLetter d
e' = fromLetter e
fromLetter x = fromIntegral ( fromEnum x -
fromEnum 'A' )
in
(((((a'*26 + b')*26 + c')*26 + d')*26) + e')*65536 +
(fromIntegral salt)
Когда вы помните, что только то, что находится под bruteForce, соответствует примеру кода, который вы написали, мы видим, что этот код довольно прост и достаточно быстр.
Итак, пара быстрых тестов.Если наш хеш равен 0x48080, последние шестнадцать бит, 0x8080, были просто нашей солью.(Никогда не пишите криптографическую хэш-функцию, подобную этой!) Остальные биты 0x4 означают номер четыре ключа, где ноль - AAAAA, то есть AAAAE.Проверка этого в REPL:
*Crack> bruteForce 0x8080 0x48080
Just ('A','A','A','A','E')
Проверка преобразования в оба конца:
*Crack> crypt ('N','I','F','T','Y') 0xCEED
398799326957
*Crack> bruteForce 0xCEED 398799326957
Just ('N','I','F','T','Y')
PS
Один из комментариев возразил, чтоязык, который я использовал, был не C. Теперь я люблю C, но, честно говоря, это не самый подходящий инструмент для этой работы.Ваша хвостовая рекурсивная функция будет иметь семь или восемь параметров и столько же особых случаев (или «обманывать», используя глобальные переменные и циклы).
Если бы я хотел использовать этот вид функциональной идиомы в C-подобномязыком, эффективно и лаконично, я бы написал это на C # с помощью LINQ и, возможно, yield return.Вот пример перевода, который я ранее опубликовал итеративного кода на C, в квазифункциональный код на C #.И - вот эталоны скорости его выполнения.
Реализация AC # может быть очень похожей: перечислить все пространство ключей в виде асинхронной последовательности и отсканировать его для первого подходящего ключахеш с заданной солью.
Вы можете изменить вышеуказанную программу на Haskell, и она уменьшит bruteForce до одной строки, вызов функции высшего порядка:
import Data.List (find)
bruteForce2 salt hash = find (\x -> crypt x salt == hash) allKeys