Некоторые алгоритмы криптанализа для кодовых криптосистем | Вестн. Том. гос. ун-та. 2000. № 271.

Некоторые алгоритмы криптанализа для кодовых криптосистем

Предлагаются алгортмы криптанализа для кодовых криптосистем с закрытым ключом с целью нахождения ключа при возможности выбора сообщений и для кодовых криптосистем с открытым ключом с целью нахождения сообщения, если известны открытый ключ и криптограмма.

Cryptanalysis algorithms for code cryptosystems.pdf Другой стороны, так как fv/^Xsf (d)\zsf/(d))>s^х y(se,vsM^ *srl(OvsM)=fld) и vi/M^rVW Sle^l(sAd)^0)=f(d), то f(d)v /(d) ^(dyrftd^fidyrfrdrf^id). Следовательно, f(d)v v/ffif^id), откуда получаем: /'=/oVJl/i//uJ2=/ov vJ/|VJ/2,"/=/'urfJu''u*=/oV,i/ivJ/2...vJ/r. Лемма доказана. Лемма 10. Пусть / - произвольная функция из Введение Кодовые криптосистемы строятся на основе линейных кодов, исправляющих ошибки. Как и все криптосистемы, они делятся на два класса - симметричные, или с закрытым ключом, и несимметричные, или с открытым ключом. Криптанализу последних посвящены работы [1,2, 3], где для некоторых кодовых криптосистем с открытым ключом решена задача нахождения закрытого ключа по соответствующему открытому ключу. В данной работе рассматриваются двоичные (на основе двоичных кодов) кодовые криптосистемы. Для таких криптосистем первого класса решается задача криптанализа с целью нахождения закрытого ключа при возможности выбора открытого текста (сообщений). Предлагается вероятностный алгоритм, доставляющий решение задачи с вероятностью, близкой к 1. Приводятся результаты испытаний алгоритма на компьютере. Для кодовых криптосистем второго класса решается задача криптанализа с целью нахождения сообщения, если известны открытый ключ и криптограмма По существу это есть задача декодирования для произвольного кода, исправляющего ошибки, для которой в настоящее время не известны алгоритмы решения с полиномиальной сложностью. В данной работе предлагается эвристический алгоритм поиска её решения путём перебора возможных кандидатов на решение с использованием некоторых правил сокращения перебора В отдельных случаях это сокращение может оказываться значительным и приводить к решению задачи за полиномиальное время. Криптанализ симметричных систем Шифрование в симметричной двоичной кодовой криптосистеме над полем GF(2) описывается следующим уравнением: •j=*>e©«.# О)" где х - булев вектор с к компонентами, являющийся сообщением; у - булев вектор с п компонентами, являющийся криптограммой; G - булева матрица размера кхп, которая является закрытым ключом и представляет собой порождающую матрицу некоторого двоичного линейного (л, А)-кода, исправляющего fel ошибок; е - случайный булев вектор с п компонентами, который содержит не более t единиц и играет роль вектора ошибок. Задача криптанализа для нахождения закрытого ключа при возможности выбирать открытый текст заключается в данном случае в том, что требуется так выбрать значения вектора х, чтобы по этим значениям и по соответствующим значениям вектора y=xG®e, при случайных значениях вектора е можно было бы найти матрицу G. Предлагается следующий подход к решению этой задачи. Будем выбирать в качестве значений вектора х единичные векторы (100.. .0), (010.. .0),.. .,(00.. .01), причем каждый такой вектор может браться некоторое число s раз, 5>3. Тогда рассматриваемая здесь задача криптанализа сводится к решению к раз следующей частной задачи: пусть булевы векторы g,yiyуъ ■■■,)>!, eh е2,..., es одной и той же длины п удовлетворяют уравнениям yrg®ehi= 1,2.....s, (2) и вес каждого вектора е, не превосходит заданного числа i> 1; требуется, зная векторы_уьу2,.. ,,у„ найти векторы g, еь еъ ..., е3. В самом деле, если в уравнении (1) вектору х придать s раз значение одного и того же единичного вектора с 1 в j-й компоненте, то получим соотношение (2), где g есть j-я строка искомой матрицы G. Заметим, что есть много других практических ситуаций, в которых возникает эта частная задача. Вот только два примера. Пример 1. Здесь: g - сигнал в форме двоичного вектора, многократно (s раз) передаваемый по симметричному двоичному каналу с шумом; е, - вектор ошибки, случающейся в нем при /-й передаче; t -максимально возможная кратность ошибки; задача приемника состоит в определении сигнала g путем исключения неизвестных ошибок в], е2,..., е., из принимаемых векторову\,уг, ...,у„. Пример 2. Здесь: конкатенация е=е\е2...е< - это некоторое сообщение, конкатенация • -Уж - это криптограмма, полученная из е по ключу g методом Виженера; задача криптоаналитика заключается в определении по у ключа g и сообщения е. Предлагается следующий алгоритм решения частной задачи. Векторы е, однозначно определяются по >>; и g, поэтому достаточно найти g. Пусть у,= =У1\Уа-Ут, г=1,2,..., s. Для каждого у'= 1,2, ..., п подсчитаем вес Wj вектора y\jyy...ysj, и полагаем g'y=l, если Wj>s/2, и g'/=0, если w,

Ключевые слова

Авторы

ФИООрганизацияДополнительноE-mail
Пронина Инна ВикторовнаТомский государственный университетпрограммист кафедры защиты информации и криптографии факультета прикладной математики и кибернетики
Агибалов Геннадий ПетровичТомский государственный университетпрофессор, доктор технических наук, заведующий кафедрой защиты информации и криптографии факультета прикладной математики и кибернетикиagibalov@fpmk.tsu.ru
Всего: 2

Ссылки

Сидельников В.М. Открытое шифрование на основе двоичных кодов Рида-Маллера // Дискретная математика. 1994. Вып. 2.
Сидельников В.М., Шестаков С.О. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона // Дискретная математика. 1992. Вып. 3.
Брикет Э.Ф., Одлижко Э.М. Криптоанализ: Обзор новейших результатов // ТИИЭР. 1998. № 5.
Радюк Л.Е., Терпугов А.Ф. Теория вероятностей и случайных процессов. Томск: Изд-во Том. ун-та, 1988.
Аснис И.Л., Федоренко С.В., Шабунов К.Б. Краткий обзор криптосистем с открытым ключом // Защита информации. 1994. № 2.
Агибалов Г.П. Адекватные модели полурешеток, функций и автоматов на полурешетках // Вестник ТГУ. 2000. № 271.
 Некоторые алгоритмы криптанализа для кодовых криптосистем | Вестн. Том. гос. ун-та. 2000. № 271.

Некоторые алгоритмы криптанализа для кодовых криптосистем | Вестн. Том. гос. ун-та. 2000. № 271.

Полнотекстовая версия