Хочу показать, как можно слегка улучшить простенькие алгоритмы шифрации на основе обычных, не криптостойких ГПСЧ.
Такой типичный простенький алгоритм выглядит примерно так:
Ei = Ri ⊕ Ci,где Ei ‒ зашифрованный символ;
Ri ‒ i-е случайное число;
Ci ‒ i-е исходный символ;
⊕ ‒ обычно операция исключающее ИЛИ.
По большому счету, наверное, все равно, но лучше вместо побитовой операции исключающее ИЛИ использовать полноценное сложение. Использование ИЛИ оправдывается только тем, что на примитивных процессорах эта операция выполняется быстрее сложения. Но сложение дает более непредсказуемые результаты из-за наличия переносов.
В любом случае такой простой алгоритм при наличии открытого и шифрованного теста вскрывается очень легко. Также легко он вскрывается, если есть только несколько шифрованных сообщений, содержащих одинаковые последовательности шифротекста.
В этом случае криптоаналитик может сделать предположение о том, какой открытый текст может содержаться в этом месте сообщения и путем несложного перебора найти ключ.
Например, очень часто в начале текстовых сообщений содержится приветствие, а в конце ‒ прощание. Одинаковое приветствие в случае такого алгоритма всегда будет кодироваться одинаково, а прощание ‒ только в том случае, если в двух сообщениях оно расположено на одном и том же расстоянии от начала текста.
Рассмотрим сначала, как можно избавиться от проблемы одинаковых суффиксов в исходном тексте.
Для этого воспользуемся тем фактом, что энтропия открытого текста, хоть и не бесконечна, но тем не менее обычно существенно выше нуля. Поэтому некоторую случайность в открытом тексте можно использовать для того, что бы сделать ГПСЧ более непредсказуемым.
Например, обычный ЛКГ можно описать следующим образом:
Xn = a × Xn-1 + c,
где
Xn, Xn-1 ‒ текущее и предыдущее случайное число;
a, c‒ константы метода;
Для использования энтропии шифруемого текста ЛКГ может выглядеть следующим образом:
Xn = a × (Xn-1 + Ln-1)+ c,
где
Ln-1 ‒ код предыдущего символа кодируемого текста;
Добавления подобного смещения в случае неудачных параметров метода может ухудшить свойства генератора с одной стороны. С другой стороны, может их и улучшить. Оба исхода на мой взгляд, равновероятны, поэтому на длинных сообщениях не смогут привести к вырождению шифра.
В результате даже одинаковые суффиксы будут шифроваться по-разному, если префиксы различные.
Тем не менее, остается проблема одинаковых префиксов, например, начальных приветствий в текстовых сообщениях, а также полностью идентичных сообщений, например, служебных сообщений протоколов передачи данных.
Для решения этой проблемы нужно добавить к открытому тексту случайный префикс, после чего эту общий текст подвергнуть процессу шифрации. После дешифрации случайную строку, естественно, надо удалить.
Таким образом, даже два совершенно одинаковых сообщения будут после шифрации дадут два совершенно разных шифротекста.
Тем не менее, криптоаналитик, при наличии у него как открытого, так и шифрованного текста, может ускорить полный перебор, отбрасывая те варианты ключей, начало дешифрованного текста которых не совпадает с исходным. Для большей криптостойкости алгоритмы было бы более выгодно, что бы в случае полного перебора криптоаналитик был вынужден каждый раз дешифровывать сообщение до конца.
Первоначально у меня возникла идея использовать для этого замену алфавита в исходном сообщении. Тут возможны различные варианты реализации. Одним из них является применение какого-либо алгоритма энтропийного сжатия с динамической моделью над открытым текстом со случайным префиксом. Наличие случайного префикса будет приводить к генерации каждый раз немного разного алфавита даже для одного и того же сообщения, что потребует при криптоанализе перебором полной дешифрации. Но использование энтропийного сжатия ‒ достаточно затратная операция, хоть в случае кодирования/декодирования издержки не так уж значительны.
Тем не менее, как-то в очередной раз мучаясь от приступа бессонницы и язвы желудка😄, мне пришла в голову более производительная идея.
Просто нужно, используя тот же ГСПЧ c подмешиванием , с тем же ключом, перемешать открытый текст со случайным префиксом. Это тоже своеобразный метод шифрации, тем не менее, очень слабый. Исходное сообщение относительно легко восстанавливается перебором, после чего криптоаналитик получает ключ на блюдечке с голубой каемочкой.
После чего необходимо зашифровать полученную "кашу" из символов с помощью вышеописанного метода с ГПСЧ с подмешиванием. Такое шифрование в два прохода существенно увеличит криптостойкость метода.
Такой метод использования простых некриптостойких ГПСЧ я предлагаю для "любительского" шифрования. На первый взгляд, получается достаточно неплохо. Но я, естественно, не проводил обзор публикаций по этой теме, так что не могу утверждать, что описанный алгоритм оригинален. Скорее всего, что-то подобное уже приходило кому-нибудь в голову. Если же алгоритм все же нигде и никогда не использовался, то можно утверждать, что он пока никем не вскрыт, по аналогии с неуловимым Джо😄.
Также я не могу ни доказать криптостойкость данного алгоритма, ни опровергнуть ее, банально из-за недостаточности математических знаний. Поэтому, естественно, его нельзя использовать для шифрации критически важной информации.
Скорее данное описание можно трактовать не как заявку на что-то серьезное в области шифрации, а лишь как мое небольшое увлечение, забаву, не более того.
Для этого воспользуемся тем фактом, что энтропия открытого текста, хоть и не бесконечна, но тем не менее обычно существенно выше нуля. Поэтому некоторую случайность в открытом тексте можно использовать для того, что бы сделать ГПСЧ более непредсказуемым.
Например, обычный ЛКГ можно описать следующим образом:
Xn = a × Xn-1 + c,
где
Xn, Xn-1 ‒ текущее и предыдущее случайное число;
a, c‒ константы метода;
Для использования энтропии шифруемого текста ЛКГ может выглядеть следующим образом:
Xn = a × (Xn-1 + Ln-1)+ c,
где
Ln-1 ‒ код предыдущего символа кодируемого текста;
Добавления подобного смещения в случае неудачных параметров метода может ухудшить свойства генератора с одной стороны. С другой стороны, может их и улучшить. Оба исхода на мой взгляд, равновероятны, поэтому на длинных сообщениях не смогут привести к вырождению шифра.
В результате даже одинаковые суффиксы будут шифроваться по-разному, если префиксы различные.
Тем не менее, остается проблема одинаковых префиксов, например, начальных приветствий в текстовых сообщениях, а также полностью идентичных сообщений, например, служебных сообщений протоколов передачи данных.
Для решения этой проблемы нужно добавить к открытому тексту случайный префикс, после чего эту общий текст подвергнуть процессу шифрации. После дешифрации случайную строку, естественно, надо удалить.
Таким образом, даже два совершенно одинаковых сообщения будут после шифрации дадут два совершенно разных шифротекста.
Тем не менее, криптоаналитик, при наличии у него как открытого, так и шифрованного текста, может ускорить полный перебор, отбрасывая те варианты ключей, начало дешифрованного текста которых не совпадает с исходным. Для большей криптостойкости алгоритмы было бы более выгодно, что бы в случае полного перебора криптоаналитик был вынужден каждый раз дешифровывать сообщение до конца.
Первоначально у меня возникла идея использовать для этого замену алфавита в исходном сообщении. Тут возможны различные варианты реализации. Одним из них является применение какого-либо алгоритма энтропийного сжатия с динамической моделью над открытым текстом со случайным префиксом. Наличие случайного префикса будет приводить к генерации каждый раз немного разного алфавита даже для одного и того же сообщения, что потребует при криптоанализе перебором полной дешифрации. Но использование энтропийного сжатия ‒ достаточно затратная операция, хоть в случае кодирования/декодирования издержки не так уж значительны.
Тем не менее, как-то в очередной раз мучаясь от приступа бессонницы и язвы желудка😄, мне пришла в голову более производительная идея.
Просто нужно, используя тот же ГСПЧ c подмешиванием , с тем же ключом, перемешать открытый текст со случайным префиксом. Это тоже своеобразный метод шифрации, тем не менее, очень слабый. Исходное сообщение относительно легко восстанавливается перебором, после чего криптоаналитик получает ключ на блюдечке с голубой каемочкой.
После чего необходимо зашифровать полученную "кашу" из символов с помощью вышеописанного метода с ГПСЧ с подмешиванием. Такое шифрование в два прохода существенно увеличит криптостойкость метода.
Такой метод использования простых некриптостойких ГПСЧ я предлагаю для "любительского" шифрования. На первый взгляд, получается достаточно неплохо. Но я, естественно, не проводил обзор публикаций по этой теме, так что не могу утверждать, что описанный алгоритм оригинален. Скорее всего, что-то подобное уже приходило кому-нибудь в голову. Если же алгоритм все же нигде и никогда не использовался, то можно утверждать, что он пока никем не вскрыт, по аналогии с неуловимым Джо😄.
Также я не могу ни доказать криптостойкость данного алгоритма, ни опровергнуть ее, банально из-за недостаточности математических знаний. Поэтому, естественно, его нельзя использовать для шифрации критически важной информации.
Скорее данное описание можно трактовать не как заявку на что-то серьезное в области шифрации, а лишь как мое небольшое увлечение, забаву, не более того.
