Некоторое время назад мне понадобился сложный пароль. Тем не менее, я также хотел, чтобы это было что-то, что я могу запомнить. Что легче запомнить, «Пароль123456789» или «Uz8!;JNEw.B›vS?Q2»? Поэтому я решил собрать свой собственный обфускатер. Просто для удовольствия.
Моими требованиями были:
- Алгоритм должен работать быстро
- Учитывая один запутанный пароль в качестве входных данных, необходимо создать новый запутанный пароль. Таким образом, мне нужно запомнить только один пароль, который можно использовать для создания множества разных, казалось бы, непонятных паролей. Отлично подходит для мест, требующих частой смены пароля :)
- В качестве расширения предыдущего требования алгоритм должен генерировать много разных паролей, прежде чем возвращать ранее сгенерированный пароль.
В оставшейся части этого поста будет рассказано о шифре Цезаря и о том, как использовать его в качестве основы для более продвинутого обфускатера.
шифр Цезаря
Это очень старый и известный шифр. Это просто замена букв другими буквами на расстоянии n букв. Например, шифр Цезаря со сдвигом +4 отобразит «цезарь» в «геидев», потому что теперь каждая буква заменяется буквой на 4 буквы позже в алфавите. В случае, когда мы выходим за пределы алфавита (что идет через 4 буквы после z в алфавите?), мы просто возвращаемся к началу алфавита, так что z отображается в d.
Расшифровка — это обратная операция. . Если мы кодировали со сдвигом +4, то декодируем со сдвигом -4, так что «геидев» отображается на «цезарь». Еще раз, если мы дойдем до начала алфавита, мы продолжим с конца, так что «d» станет «z».
Если мы переведем числа в буквы, так что a=›0, b=› 1, …, z=›25, то мы можем записать функцию кодирования E и функцию декодирования D для некоторого количества сдвигов n:
E(x) = (x +n) mod 26< br /> D(x) = (x -n) mod 26
Интересным частным случаем шифра Цезаря является случай, когда n = 13. В этом случае E(x) = D(x). Поскольку в алфавите 26 букв, если дважды повернуть на 13, получится начальное слово. Подробнее о шифре Цезаря можно прочитать в Википедии.
Улучшение: индексный шифр Цезаря.
В шифрах на основе подстановки (таких как шифр Цезаря) одним из распространенных векторов атаки является просто выполнение частотного анализа. Это включает в себя просто подсчет различных букв в зашифрованном тексте и попытку угадать, какая буква какая. В английском языке наиболее распространенной буквой является е, поэтому вполне логично, что наиболее часто встречающаяся буква в зашифрованном тексте соответствует е и так далее. Еще раз, вы можете прочитать больше в Википедии.
Другой вектор атаки против шифра Цезаря — это когда мы знаем, что он зашифрован шифром Цезаря, но не знаем, какова сумма сдвига. В этом случае мы можем просто попробовать разные смены и посмотреть, что дает что-то, что имеет смысл.
Мы можем бороться с этим, меняя буквы по-другому. Например, первая буква сдвигается на 4, вторая на 4*4 = 16, третья на 4*4*4 = 64 и так далее. Таким образом, частотный анализ больше невозможен, поскольку несколько букв могут отображаться в одну и ту же букву в зависимости от их индекса. Вторая атака все еще возможна, если злоумышленник знает о шифре. Но так как это не общий шифр, это маловероятно. Это пример безопасности по неизвестности, но поскольку цель состоит в том, чтобы создать что-то, что запутывает пароли, а не реальную схему шифрования, это нормально :)
В общем случае функции шифрования и дешифрования таковы:
E(x, i) = (x +n^i) по модулю 26
D(x, i) = (x -n^i) по модулю 26
Где индексы имеют 1 индекс. Работа с модульными показателями известна как модульное возведение в степень.
Давайте еще раз запутаем слово «цезарь» с помощью 4 в качестве количества сдвига:
c: E(2, 1) = 2+4¹ mod 26 = 6
a: E(0, 2) = 0+4² mod 26 = 16
e: E(4, 3) = 4 + 4³ mod 26 = 16
z: E(25, 4) = 25 + 4⁴ mod 26 = 21
> a: E(0, 5) = 0+4⁵ mod 26 = 10
r: E(17, 6) = 17+4⁶ mod 26 = 5
В целом это дает запутанную строку « гкквкф». Интересно, что, как и предполагалось, «а» сопоставляется с двумя разными значениями, а два разных значения сопоставляются с одним и тем же значением 16 (или буквой «q»).
Циклы количества сдвига и размер алфавита
Рассмотрим теперь пример, когда мы хотим запутать «caezarcaezar» на 4. Мы уже знаем, что запутанная строка будет начинаться с «gqqvkf». Итак, давайте вычислим остаток строки:
c: E(2, 7) = 2 + 4⁷ mod 26 =6
a: E(0, 8) = 0 + 4⁸ mod 26 =16< br /> e: E(4, 9) = 4 + 4⁹ mod 26 = 16
z: E(25, 10) = 25 + 4¹⁰ mod 26 = 21
a: E(0, 11 ) = 0 + 4¹¹ mod 26 =10
c: E(17, 12) = 17 + 4¹² mod 26 =5
О, о. Кажется, мы начинаем повторять значения. Вычисление:
4^k mod 26 для различных значений k дает почему:
4¹ mod 26 = 4
4² mod 26 = 16
4³ mod 26 = 12
4⁴ mod 26 = 22
4⁵ mod 26 = 10
4⁶ mod 26 = 14
4⁷ mod 26 = 4
4⁸ mod 26 = 16
И так далее. Действительно, мы попали в цикл. Это может показаться не таким уж плохим, но добавляет некоторую предсказуемость, чего мы не хотели. Однако мы не можем полностью избежать этого; в конце концов, может быть максимум 26 различных значений по модулю 26, после чего он будет повторяться. Итак, мы хотим выбрать величину сдвига так, чтобы длина цикла была максимальной. Как оказалось, самый длинный возможный цикл для модуля 26 имеет длину 12 (что вы получите, используя 7 для значения сдвига). Это мы знаем из теории групп, поскольку мы, хотя я и не говорил об этом, на самом деле работаем с так называемым мультипликативным групповым модулем n,где n равно 26. Если только вы не интересуетесь математикой (если интересуетесь, прочитайте статью в Википедии), в основном важно знать, что самый длинный цикл для числа n равен количеству целых чисел меньше n, для которых n не имеет общих делителей (это известно как тотиентная функция Эйлера). Например, 26 = 2*13, поэтому любое четное число меньше 26 (их 12) будет иметь общий делитель (2), 13 будет иметь общий делитель (13), а тривиальная 1 будет иметь общий делитель, что дает 14 чисел, для которых 26 делит делитель. Действительно, 26–14 = 12, что дает максимально возможную длину цикла.
Чтобы получить более длинные циклы, мы хотим работать по модулю другого числа, желательно такого, чтобы под ним не было чисел, для которых оно имеет общие делители, за исключением числа 1, так как это минимизирует количество чисел, для которых общий делитель является общим. Отсюда следует, что для оптимизации длины цикла мы должны работать по модулю простого числа. И мы можем сделать это, расширив наш алфавит, чтобы он также включал символы !/#, так что размер алфавита (строчные буквы и три специальных символа) теперь имеет длину 29, простое число.
Примечание здесь заключается в том, что не все величины смещения максимизируют продолжительность цикла. Напомним, что числа 4 и 7 давали разную длину по модулю 26. Мы можем оптимизировать, найдя число n такое, что по модулю некоторого простого числа p:
n^((p-1)/2) mod p = p-1
Если вы хотите попробовать, используя число 2 в качестве величины сдвига, вы получите длину цикла 28 для алфавита размером 29. Проверьте это, вычислив 2¹⁴ по модулю 29 = 28.
Выбор числа для суммы перевода
Я упомянул о том, как разные величины сдвига дадут разную длину цикла и как мы можем просто выбрать другую, чтобы получить лучшую длину цикла. Однако есть и другая и более опасная проблема, которую следует учитывать при выборе величины сдвига, а именно то, что мы будем быстро использовать те же числа.
Рассмотрим еще раз алфавит строчных английских букв, в котором 26 букв, и что мы по-прежнему используем 4 для сдвига. Давайте еще раз поиграем с буквой «цезарь» и несколько раз запутаем их:
- 0-я итерация: caezar
- 1-я итерация: gqqvkf
…
- 12-я итерация: yksdqd
- 13-я итерация: caezar
Аааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааа Он он его?? его его его него он он ему он ему?? Опять же, мы не можем избежать их (это и следовало ожидать после 26 итераций), но, выбрав число 4, я принял плохое решение, а именно выбрал число, имеющее общий делитель с 26 — число 2. Если бы я вместо этого выбрано 5, циклирование произойдет только после 26 итераций, максимизируя количество различных строк, которые мы можем сгенерировать из исходного «цезаря».
Итак, еще раз, убедившись, что наш алфавит имеет размер простого числа, мы можем довольно свободно выбирать любые суммы сдвига, кроме 1, потому что 1 ^ n = 1, и поэтому это даст только простой шифр Цезаря: )
Собираем все вместе
Теперь, когда фон готов, мы можем составить алгоритм. Но сначала вам нужно выбрать, какие буквы можно использовать, и убедиться, что количество букв является простым числом. Например, вы можете использовать строчные буквы, прописные буквы и цифру 0, что дает 53 разных буквы:
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0
Затем выберите число меньше разрешенной длины символов и больше 1. Давайте выберем число 5, так как оно соответствует следующим критериям:
5²⁶ mod 53 = 52
Теперь в псевдокоде мы можем запутать пароль:function obfuscate(input: string, characters: char[])
obfuscated_string = ""
for i in range(0, input.length):
— character = input[i]
— nextCharacterIndex = characters.indexOf(character) + 5^(i+1)
— nextCharacter = characters[nextCharacterIndex%characters.length]— obfuscated_string = obfuscated_string+nextCharacter
return obfuscated_string
И это все! Я реализовал алгоритм на JavaScript здесь, с 5 в качестве суммы смещения и 83 допустимыми символами. Не стесняйтесь использовать инструмент (на свой страх и риск, я не обещаю не удалять его в будущем, так что не полагайтесь на него) или просто скопируйте исходный код и используйте его где-нибудь еще.
Оптимизации
При работе с модульной арифметикой мы имеем следующие правила перезаписи:
a + b mod m = (a mod m) + (b mod m) mod m
a*b mod m = (a mod m ) * (b mod m) mod m
Это означает, что вычисление 5⁴+3 mod 4 можно вычислить как:
(5 mod 4)*(5 mod 4)*(5 mod 4)*( 5 по модулю 4) + 3 по модулю 4
= 1*1*1*1 + 3 по модулю 4 = 0 по модулю 4
Это устраняет необходимость вычисления 5⁴ и действительно ускоряет вычисление. Это действительно вступает в игру, если бы мы, например, вычислили 23¹⁹, где это дало бы очень большое число. Тот, который также переполнил бы целые числа, так что хорошо, что мы можем этого избежать.
Еще одна вещь, которую я не касался, но до сих пор только предполагал, — это то, как сортируется алфавит. Ну, это отсортировано по алфавиту, верно? Но что, если вместо abcdefghijklmnopqrstuvwxyz в качестве алфавита использовать lobirvwkmjtczfsgpaenuxqhyd? Теперь сдвиг строки «lo» с использованием 3 для суммы смещения дает «it», что делает вывод еще более случайным.
Вывод
С переписыванием арифметики из раздела оптимизации код работает очень быстро. Это удовлетворяет требованиям скорости. Очевидно, что кодирование запутанной строки дает новую, другую строку, удовлетворяющую моему второму требованию. Действительно, входные данные можно пропустить через обфускатор p раз для некоторого простого числа, прежде чем получить исходное — удовлетворяя последнему требованию. Так что теперь мне нужно только запомнить мой пароль «1337password», чтобы сгенерировать много случайных паролей. Потрясающий!
В качестве бонуса, несмотря на то, что это никогда не было целью, вся используемая математика является обратимой, а это означает, что мы также можем использовать ее для шифрования и расшифровки данных. На самом деле мы не должны этого делать, и делать и использовать свой собственный алгоритм шифрования — плохая идея, но для случая обфускации паролей с помощью пользовательского обфускатора, о котором больше никто не знает, алгоритма достаточно.
На этом завершается предыстория и реализация моего пользовательского обфускатера. Весь смысл в том, чтобы попытаться применить некоторые знания по абстрактной алгебре в реальном мире. Вы можете задаться вопросом: почему бы просто не использовать более простой метод, например, обычный алгоритм хеширования, такой как MD5 или SHA256? Ну, это было бы не так весело, как это :)
