Цель: взломать шифр Хилла
Доброго времени суток, уважаемые читатели! Сегодня я хотел поделиться способом, который помог мне вскрыть текст, зашифрованный методом Хилла. Что такое метод Хилла описывать не буду: до меня уже постарались опытные умельцы донести особенности данного способа. Ссылка на пост.
Что имеем?
Скажу сразу, что на руках не имелось ни открытого текста, ни ключа. Было известно, что текст длинной 6286 символов был зашифрован матрицей 7 х 7. Поэтому для нашего же удобства, мы разобьем текст на 898 строчек по 7 символов. В тексте не содержатся буквы 'ё' и 'ъ'. В целях благоразумства, я не буду приводить весь зашифрованный текст, а лишь его часть:
тчгяцмекещэнлжсвтйджтчгсмнежздыщзяотьдрпюмимаадрх...
На вид бессмысленная ерунда, пока что…
Как будем ломать?
Рассмотрим атаку «грубой силой». Выше было оговорено, что из алфавита исключены две буквы, поэтому все линейные комбинации при шифровании (как и при дешифровке) берутся по mod 31 (учитывая, что это простое число, текст становится чуть более безопасным).
Если рассматривать перебор обратных матриц-ключей, то всего нам придется перебрать $inline$31^{49} $inline$ комбинаций (это число примерно умещается в 75 знаков). Поэтому такой способ исключается моментально, хотя! Если из этого множества можно было бы каким-нибудь более-менее быстрым способом перебрать подмножество невырожденных матриц, то возможно задача облегчилась бы. К сожалению я такого способа не знаю и не уверен, что такой вообще существует!
Читать полностью »