WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 18 |

Считается, что количество импульсов N(T), зарегистрированных на интервале [0, T], подчиняется распределению Пуассона [2], для которого математическое ожидание и дисперсия равны M{N(T)} = s 2{N(T)}.

Известно, что распределение Пуассона является распределением с максимальной энтропией [3], что делает его использование предпочтительным при преобразованиях случайная величина ® элемент бинарной СЧП.

Действительно, начальный поток, события которого являются причиной появления шумовых импульсов на выходе диодовгенераторов, является пуассоновским [4]. Однако, в реальных источниках шума и в системах регистрации вследствие принципов их функционирования происходят потери событий. Поэтому законы распределения (ЗР) количества импульсов в единицу времени отличаются от пуассоновского, и, следовательно, уменьшается энтропия в выходной битовой последовательности. При прореживании пуассоновского потока постоянным мертвым временем I и II типов наблюдается уменьшение отношения s 2{N(T)} / M{N(T)} [5].

Методом имитационного моделирования было исследовано влияние мертвого времени I и II типов на ЗР числа событий в единицу времени N(T) результирующего потока. Определено, что для аппроксимации такого ЗР можно использовать нормальный ЗР со значениями M{N(T)} и s 2{N(T)}, рассчитанными с использованием формул [5]. При этом выбор величины интервала пересчета импульсов определяется симметричностью ЗР (M{N(T)} > (3ё4)s 2{N(T)}).

Рис. 1. Осцилограммы шумовых импульсов от тока через образцы Таким образом, мерой энтропии источника событий можно считать отклонение отношения s 2{N(T)} / M{N(T)} от единицы. В связи с этим, определим изменение отношения s 2{N(T)} / M{N(T)} для различных режимов работы диодовгенераторов импульсного шума.

На рис. 1 представлены осциллограммы шумов для двух значений среднего тока через образцы. Визуальный анализ показывает, что с увеличением среднего тока через образцы увеличивается средняя частота шумовых импульсов. При этом интервалы следования импульсов большой длительности исчезают, а минимальный интервал следования ограничен временем развития и затухания лавинного процесса в микроплазме. Поэтому логично предположить, что отношение s 2{N(T)} / M{N(T)} будет уменьшаться.

На рис. 2 (кривая 1) представлено изменение M{N(T)} (T = 10 мкс). Характер изменения M{N(T)} определяется вероятностями включения / выключения микроплазмы, которые являются функциями тока.

Рис. 2. M{N(T)} (1) и s 2{N(T)} / M{N(T)} (2) от тока через образцы На рис. 2 (кривая 2) представлено отношение s 2{N(T)} / M{N(T)} от тока. Видно, что отношение s 2{N(T)} / M{N(T)} уменьшается до токов ~ 70 мкА, а затем возрастает. Значение s 2{N(T)} / M{N(T)} определяется соотношениями таких величин, как частота попадания носителей заряда в область умножения (микроплазму), время развития лавинного умножения, вероятность выключения лавинного умножения.

Таким образом определено, что энтропия импульсного шума исследованных образцов диодовгенераторов уменьшается до токов ~ 70 мкА. При I > 70 мкА изменение энтропии становится положительным: s 2{N(T)} / M{N(T)} приближается к единице. Ввиду этого при формировании СЧП рекомендуется осуществлять выбор рабочего режима при токах более 70 мкА. Следует отметить, что время преобразования сигнала ® элемент бинарной СЧП с задаваемым уровнем энтропии будет существенно возрастать вследствие уменьшения M{N(T)}.

Библиографический список 1. Mury H. A general approach for generating natural random variables // IEEE Trans. on Computers.– 1970.– Vol. C19.– P. 1210–1213.

2. Vincent C. The generation of truly random binary numbers // Journal of Physics E.– 1970.– Vol. 3, № 8.– P. 594–598.

3. Harremoёs P. Binomial and Poisson Distributions as Maximum Entropy Distributions // IEEE Trans. on Inf. Theory.– 2001.– Vol. 47, № 5.– P. 20392041.

4. Burgess R. Electrical fluctuations in semiconductors // British J. Appl. Phys.– 1955.– № 6.– P. 185–190.

5. Ватутин В.А., Телевинова Т.М., Чистяков В.П. Вероятностные методы в физических исследованиях. – М.: Наука, 1985.– 208 с.

Л.К. Бабенко, Е.А. Ищукова Россия, г. Таганрог, ТРТУ ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МЕТОДА ДИФФЕРЕНЦИАЛЬНОГО КРИПТОАНАЛИЗА В 1990 году Эли Бихам и Ади Шамир представили миру новый вид криптоанализа – дифференциальный криптоанализ. В основе метода лежит использование атаки на основе выборочного открытого текста. Идея заключается в анализе процесса изменения несходства для пары открытых текстов, имеющих определенные исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом. При этом не существует какихлибо ограничений на выбор открытых текстов. Достаточно различия в некоторых позициях.

В работе [1] Бихам и Шамир показали, как можно вскрыть полный шестнадцатираундовый алгоритм шифрования DES. Для этого ими было предложено использовать в одном раунде такую разность, которая бы при прохождении Fфункции давала на выходе разность, равную нулю. То есть получается, что при двух разных входах на выходе функции F образуются два одинаковых значения. В этом случае можно было бы подбирать с высокой вероятностью входные и соответствующие им выходные разности для двух раундов шифрования.

Как выяснилось, вариант такой входной разности, дающей выходную разность с наибольшей вероятностью, равен 19 60 00 00х. В этом случае после прохождения таблицы перестановки с расширением на вход первого Sблока попадет значение разности 000011, на вход второго Sблока – 110010, на вход третьего – 101100, а на вход всех остальных блоков замены – нули. Вероятность того, что в этом случае на выходе первого Sблока появится нулевая разность, равна ; вероятность того, что на выходе второго Sблока будет нулевая разность, равна, и наконец, вероятность того, что на выходе третьего Sблока будет нулевая разность, равна (вероятности определяются с помощью статистических таблиц замены, которые строятся на подготовительной стадии, более подробное описание построения таких таблиц можно найти в [2]). Объединяя все вышесказанное, получаем, что вероятность того, что при поступлении на вход раунда разности 19 60 00 00, на выходе появится нулевая разность, равна:

.

При рассмотрении полного алгоритма шифрования DES Бихам и Шамир предложили использовать двухраундовую характеристику 6 раз (со 2го по 13 раунды). Вероятность шести двухраундовых характеристик будет равна:

При таком раскладе, на вход 14го раунда с вероятностью р = 247.22 поступит нулевая разность, которая в свою очередь с вероятностью p=1 даст на выходе тоже нулевую разность. Поэтому четырнадцатый цикл мы не учитываем при вычислении общей вероятности для 16раундового алгоритма шифрования.

Так как известна выходная разность 16го раунда и входная разность 14го раунда равна нулю, то на выходе fфункции 15го раунда появится разность, равная правой части выходной разности 16го раунда. Разность на входе 15го раунда известна, а значит, легко можно определить разность на выходе fфункции 16го раунда шифрования. Таким образом, использование двухраундовой характеристики со 2 по 13 раунд и точное знание выходной разности 16раунда шифрования позволяют нам не учитывать три последних раунда шифрования при вычислении общей вероятности для 16раундового алгоритма ширфования. Последние три раунда будут выполняться всегда с вероятностью р = 1.

При анализе также необходимо учитывать тот факт, что на выходе первого раунда ненулевые биты могут присутствовать в разности только лишь с первого по двенадцатый,. (3 выхода Sблоков по 4 бита). Таким образом, у нас может быть всего 212 выходных разностей, при этом каждая 12битовая разность может быть получена одним способом из 212. То есть всего возможно (212)2 = 224 комбинаций входных пар, и вероятность появления нужной разности равна.

Также при выборе правильных пар необходимо учитывать, что на выходе fфункции 16го раунда последние пять Sблоков дают нулевую разность. Таким образом, если имеются 224 возможных пар текстов, и при этом 220 из них могут иметь ненулевые последние 20 бит (выходы 5 последних Sблоков по 4 бита), то у нас остается примерно 24 = 16 возможных пар текстов.

Таким образом, задача сводится к зашифрованию и анализу 224 пар текстов с целью нахождения определенных 16 пар текстов, что представляет собой трудоемкую вычислительную процедуру и требует для своего выполнения значительного времени. Для сокращения этого времени целесообразно использовать параллельную реализацию. Для моделирования параллельных вычислений наиболее удобной с точки зрения авторов является модель на основе спецификации «Интерфейса Передачи Сообщений» (Message Passing Interface, сокращенно, MPI). В этой модели программа порождает несколько процессов, взаимодействующих между собой с помощью обращений к подпрограммам передачи и приема сообщений [3]. Обычно, при инициализации MPIпрограммы создается фиксированный набор процессов. При этом существует возможность как выполнения каждого процесса на своем процессоре, так и выполнения нескольких процессов на одном процессоре. В этих процессах могут выполняться разные программы, поэтому модель программирования MPI иногда называют MPMDмоделью (Multiple Program Multiple Data – множество программ множество данных).

Спецификация MPI обеспечивает переносимость программ на уровне исходных кодов и большую функциональность. Поддерживается работа на гетерогенных кластерах и симметричных многопроцессорных системах.

Для нахождения 16 пар текстов при проведении дифференциального криптоанализа полного алгоритма шифрования DES необходимо проанализировать 212 различных входных разностей. Для каждой возможной входной разности главный процесс (процесс с номером 0) должен подобрать 212 пар открытых тестов, с помощью которых эта разность может быть образована. Найдя очередную пару текстов, обозначим ее как (Х, Х'), он посылает ее очередному процессу ( рис. 1).

Рис.1 Общая схема взаимодействия процессов Так как естественно, что процессов, скорее всего, будет меньше, чем 212, то данные будут передаваться по кругу, то есть сначала первому, потом второму, потом nному процессу, и снова первому, второму и так далее. Получив пару текстов (Х, Х') процесс производит зашифрование каждого текста на секретном ключе К, в результате чего получается пара соответствующих шифртекстов (Y, Y’). Найденную пару (Y, Y’) процесс посылает головному процессу, который в свою очередь проверяет, удовлетворяет ли полученная пара шифртестов начальным условиям. Таким образом, получается, что головной процесс все время занят подбором и передачей пар открытых текстов и приемом и анализом пар шифртекстов. В то же время все остальные процессы заняты, приемом данных от головного процесса, их шифрованием и отправкой полученных результатов шифрования обратно головному процессу.

Такой подход позволяет существенно ускорить процесс нахождения искомых пар текстов, а значит, и повысить эффективность метода дифференциального криптоанализа. Так, при наличии q процессоров ускореннее будет не менее, чем q/2.

Библиографический список Biham E., Shamir A., “Differential Cryptanalysis of the Full 16round DES”, Crypto'92, SpringerVelgar, 1998, p. Бабенко Л.К., Мишустина Е.А., Методическое пособие по изучению современных методов криптоанализа, Таганрог: ТРТУ, 2003г., 74 с.

Немнюгин С.А., Стесик О.Л., Параллельное программирование для многопроцессорных вычислительных систем, СПб.:БХВПетербург, 2002, 400с.

Л.К. Бабенко, А.М. Немова Россия, г. Таганрог, ТРТУ РАСПАРАЛЛЕЛИВАНИЕ КРИПТОАНАЛИТИЧЕСКИХ МЕТОДОВ:

“ВСТРЕЧИ В СЕРЕДИНЕ АТАКИ” И “РАЗДЕЛЯЙ И ПОБЕЖДАЙ” ДЛЯ МНОГОКРАТНЫХ ШИФРОВ Известны криптоаналитические методы: “встречи в середине атаки” и “разделяй и побеждай”, применяемые для атаки на блочные шифры. Они наиболее эффективны при анализе многократных шифров. Эти методы обладают значительно меньшей трудоемкостью по сравнению с методом полного перебора, но все же требуют значительной затраты времени. Предлагается для сокращения временных затрат, рассмотреть возможные варианты распараллеливания.

Пусть даны открытый и шифрованный тексты. Криптосистема состоит из шифрований. Ключ системы представляет собой сочетание из независимых и не имеющих общих битов ключей.

1. Алгоритм метода “встречи в середине атаки”.

Вход:, (открытый и шифрованный тексты).

1. Перебирая все возможные значения, для зашифровываем и.

2.. Перебирая все возможные значения, для расшифровываем и проверяем:

если не пусто, то и Выход:.

На выходе в обоих методах получается массив возможных ключей. Методом перебора этого массива, действуя на остальные блоки находим истинный ключ.

Рассмотрим пример применения метода “встречи в середине атаки” для алгоритма двойного DES:

Пусть для повышения стойкости исполь­зуется повторное шифрование алгоритмом на разных ключах и (рис. 1). Длина каждого ключа n = 56.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 18 |




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.