Исследование алгоритмов скремблирования данных
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
В·овать некий генератор псевдослучайных чисел с входными данными, известными и отправителю, и получателю. Один из таких часто применяемых генераторов - линейный конгруэнтный ГПСЧ (ГСПЧ это генератор псевдослучайных чисел).
Мы, конечно, догадываемся, что это плохо, но что же именно плохо в этом подходе? Проблема в том, что довольно трудно генерировать параметры для самого генератора. Программно подобрать хорошие параметры для линейного конгруэнтного ГПСЧ, чтобы последовательность была длинная и невырожденая, довольно трудно. По этому поводу можно почитать в 3.2.1 в книге Д.Кнута Искусство программирования.
Поэтому зачастую эти параметры вколачивают в код как константы и, как следствие, потенциальный взломщик получает множество сообщений зашифрованых с одним ключом, что значительно упрощает его работу.
Использование самих данных для генерации этой псевдослучайной последовательности
На первый взгляд кажется, что это невозможно, ведь нам нужен генератор, который выдавал бы одинаковую последовательность и при шифровке, и при расшифровке. Как ни странно, именно этот убийственный тезис и даёт нам путь к созданию такого генератора. Да, нам нужен алгоритм, который меняет значения своих внутренних переменных одинаково, если ему дать исходный байт (или что там у нас является атомарной единицей кодирования) и зашифрованый байт. Как этого достичь? Всё гениальное просто - для вычисления следующего значения ключа можно задействовать коммутативные операции для пар исходных-шифрованых байт. Так как результат операции не зависит от порядка операндов в паре, то очевидно, что такой алгоритм будет менять свои переменные при расшифровке точно так же как и при шифровке, но последовательность ключей для других входных данных будет другой.
Пример генератора ключей, зависящего от входных данных
Чтоб было понятней, рассмотрим простенький пример такого алгоритма.
Пусть xn - это очередной код в исходных данных, kn - текущий ключ, kn+1 - следующее значение ключа, yn - зашифрованый код xn. Q(a,b) - некая коммутативная функция, т.е. такая, что q(a,b)==q(b,a). (a,b,c) - некая целочисленная функция.гда итерацию по (де)кодированию можно описать так:
n := xn xor kn;n+1 := F( kn, Q( xn, yn ), n );
Если для функции F() понятно, что её имплементация в общем-то ограничена лишь нашей фантазией и здравым смыслом, то про Q(), вероятно, вам хочется увидеть подробностей, а именно, каким таким условиям она должна соответствовать, чтобы быть коммутативной. Самый простой способ этого достичь - использовать аргументы только парами в коммутативных операциях, например xor, сложение, умножение. Примеры:
(a,b) = ((a xor b) or 1) * (( a + b ) xor 1).
Как видите, придумать свою супер-пупер функцию Q() совсем не сложно. Другое дело, нужно ли её делать сложной? Думаю, что особого смысла в её переусложнении нет.
Перемешиватель данных (shuffler)
Обычно для решения этой задачи используют некий ГСПЧ для получения пар индексов кодов в блоке данных, которые меняют местами. Неприятность этого метода в том, что трудно гарантировать, что какая-то часть данных не останется на том же месте. Также не совсем понятно, сколько же перестановок нужно сделать, чтобы достичь приемлемого результата, хотя для надёжности можно просто пройтись по всем кодам сообщения и обменять каждый со случайным. Но есть ещё одна неприятность - если генератор имеет плохое распределение по квадрату (а линейный конгруэнтный именно такой болезнью и болеет, и причём безнадёжно), то при определённых размерах блока можно нарваться на зацикливание выдаваемых значений. Я довольно долго шёл к идее быстрого псевдослучайного перемешивателя данных (shuffler) и считаю, что она заслуживает вашего внимания не только как алгоритм для скремблирования.
Немного теории. В пункте 3.2.1.2 книги Д.Кнута Искусство программирования можно найти критерии для выбора множителя для линейного конгруэнтного генератора, чтобы длина генерируемой последовательности равнялась модулю. Что это означает? Это значит, что для генератора с модулем m каждое значение от 0 до m-1 будет выдано ровно один раз. Зачем это нам? Вспомним, что для нашего перетасовщика было бы желательно гарантировать, что все байты(коды) сообщения поменяли своё место. То есть, если длина данного блока данных равна этому самому m, то нам будет достаточно просто записывать очередной входной байт(код) сообщения в выходной буффер по индексу, равному очередному значению из генератора. Простота этого алгоритма настолько сооблазнительна, что я не мог пройти мимо.
Но, как всегда случается с чем-то сооблазнительным, не обошлось без проблем. Во-первых, не все m одинаково хороши. Из той же главы той же книги мы видим, что если m является произведением простых чисел в первой степени, то полного перебора элементов мы достичь не можем в принципе (не считая перебора подряд, что нам, конечно, не интересно). Получается, что получить нужный нам генератор с заданной длиной последовательности нельзя, и, следовательно, если у нас сообщения произвольной длины, то мы не всегда можем найти такой генератор. Тупик? А действительно ли нам нужны генераторы произвольной длины? Вспомним о том, что для потенциального взломщика знание длины сообщения очень даже небес?/p>