А. А. СВЕНЧ
Омский государственный университет
АЛГОРИТМ РАЗДЕЛЕНИЯ СЕКРЕТА НА ОСНОВЕ ВЫСОКОВЕРОЯТНЫХ БИГРАММ И ТРИГРАММ
В данной работе рассматривается метод улучшения приведенного ниже алгоритма разделения секрета на основе генерации символов, образующих с символами исходного сообщения наиболее вероятные биграммы и триграммы с целью усложнения восстановления исходного сообщения по одной из частей секрета до полного перебора вариантов.
Постановка задачи.
В данной работе рассматривается задача об оптимальном подборе символов для алгоритма разделения секрета, описанного ниже. Суть оптимизации заключается в подборе символов, образующих существующие биграммы и триграммы с символами исходного текста, так что задача взлома по одной части сообщения становится наиболее трудоемкой.
Рассматривается следующий алгоритм разделения секрета.
На вход алгоритма подаётся сообщение F. В результате разделения на выходе получаем две последовательности S1 и S2, которые и представляют собой две части разделённого секрета.
Вначале S1 и S2 пусты. Далее для каждого символа c сообщения F генерируется две подпоследовательности длины n. Далее одна из этих подпоследовательностей пришивается к уже сформированной части последовательности S1, а другая - к S2. Проделав эту операцию для всего сообщения F, получим готовые последовательности S1 и S2.
Задача состоит в том, чтобы максимизировать время взлома секрета путем генерации дополнительных символов для последовательностей S1 и S2 таким образом, чтобы их различные комбинации максимально часто содержали существующие в данном языке биграммы и триграммы, таким образом, при взломе удастся отбросить очень малое количество комбинаций символов перехваченной последовательности.
Предлагается следующий алгоритм шифрования исходного текста:
Генерация последовательностей S1 и S2 производится последовательно, т. е. исходный текст просматривается посимвольно, и для каждого символа выполняется процедура генерации символов для шифрования.
Шаг 1. Для каждого символа исходного сообщения из алфавита выбирается как можно больше различных символов, таких, что в данном языке существуют биграммы и триграммы, образуемые этими символами и уже полученными на предыдущих этапах символами (должны существовать не обязательно все биграммы и триграммы, а как можно больше), и существуют биграммы и триграммы, образуемые этими символами с последующими соседними символами исходного сообщения. Если таких символов набирается меньше, чем 2n-2, то недостающие символы выбираются из алфавита произвольно.
Шаг 2. Для выбранного множества символов (если оно содержит более 2n-2 элементов) производится выбор 2n-2 оптимальных символов. При этом предпочтение отдается символам, для которых выше вероятность перехода к последующим символам исходного сообщения. Этот критерий описан в [1] более подробно.
Шаг 3. Выбранные 2n-2 символа делятся на 2 подмножества по n-1 символов, в каждое подмножество добавляется символ c, после чего символы первого подмножества извлекаются из него в произвольном порядке, и присоединяются к уже сгенерированной части S1, а символы второго подмножества - к S2.
Выводы и методы усовершенствования.
Данный метод оптимизации алгоритма разделения секрета был протестирован для N = 2 на сообщениях, являющихся законченными предложениями на литературном русском языке. При генерации дополнительных символов для основного сообщения было установлено, что алгоритм генерации успешно справляется с участками исходного текста, которые состоят из высоковероятных в русском языке биграмм(триграмм), но плох для маловероятных символов. Этот недостаток метода сильно проявляется при больших значениях n, так как в этом случае алгоритм может не справляться с генерацией даже для распространенных букв. Здесь можно предложить усовершенствование алгоритма частой генерацией пробелов в качестве дополнительных символов, но это применимо только для достаточно больших n. Таким образом, имеется возможность улучшения данного алгоритма, и можно добиться того, что вскрытие сообщения по одной части секрета будет сводиться к полному перебору.
Список литературы
1. Криптография и защита сетей: принципы и практика. 2-е изд. М.: Вильямс, 2003.
