2.4.2 Алгоритм Лемпеля-Зива
Классический алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования, предельно прост. Он формулируется следующим образом: "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность".
Так фраза "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодируется как "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ".
Распространенный метод сжатия RLE (англ. Run Length Encoding), который заключается в записи вместо последовательности одинаковых символов одного символа и их количества, является подклассом данного алгоритма. Рассмотрим, например, последовательность "ААААААА". С помощью алгоритма RLE она будет закодирована как "(А,7)", в то же время ее можно достаточно хорошо сжать и с помощью алгоритма LZ77 : "А(-1,6)". Действительно, степень сжатия именно такой последовательности им хуже (примерно на 30-40%), но сам по себе алгоритм LZ77 более универсален, и может намного лучше обрабатывать последовательности вообще несжимаемые методом RLE.
Программы Pkzip и WinZip позволяют создавать защищенные паролем архивы. Специалисты по криптографии утверждают, что в методе шифрования, используемом программой Pkzip, обнаружены "дыры", позволяющих взломать архив не только подобрав пароль, но и другими способами. Если подбор пароля будет производится с помощью обычного PC с использованием распространенных программ подбора ключа, Pkzip может послужить весьма удобным и быстрым способом защиты информации, хотя и обладающим недостатком, присущим всем системам криптозащиты с одним ключом.
Программ взлома существует довольно много. Все программы используют один из двух подходов по выбору пользователя. Они либо подбирают пароль с использованием большого словаря, либо атакуют в лоб (brute force), перебирая все возможные комбинации. Отсюда простой вывод: надо использовать пароль, который вряд ли есть в словаре, а главное - длинный (до 24 знаков), и содержащий цифры, специальные символы (?!$ и т.д..). Для лобовой атаки (подбор комбинации из всех возможных) со скоростью 200 000 комбинации в секунду (примерно соответствует возможностям PC Pentium 100) для пароля из 6 знаков расклад таков:
|
Набор символов |
Максимальное время |
|
только цифры |
5.0 секунд |
|
только строчные буквы |
25.7 минуты |
|
только символы |
1.8 часа |
|
строчные и заглавные буквы |
27.5 часа |
|
строчные, заглавные, цифры |
3.3 дня |
|
строчные, заглавные, цифры, символы |
42.5 дня |