VMPC (англ. Variably Modified Permutation Composition) — это потоковый шифр[1], применяющийся в некоторых системах защиты информации в компьютерных сетях. Шифр разработан криптографом Бартошем Жултаком (польск. Bartosz Żółtak,англ. Bartosz Zoltak) в качестве усиленного варианта популярного шифра RC4. Алгоритм VMPC строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов. Основные преимущества шифра, как и RC4 — высокая скорость работы, переменный размер ключа и вектора инициализации (от 128 до 512 бит включительно), простота реализации (буквально несколько десятков строк кода).[2]
Основа шифра - генератор псевдослучайных чисел[3], базой которого является односторонняя необратимая функция VMPC (англ. Variably Modified Permutation Composition):
Алгоритм преобразования ключа[2] и (дополнительно) вектора инициализации в 256-элементную перестановку P. Инициализация глобальной переменной s.
С : Длина ключа в байтах
K : Ключ
z : Длина вектора инициализации в байтах
V : Вектор инициализации
i : 8-разрядная переменная
j : 16-разрядная переменная
s : 8-разрядная глобальная переменная
P : таблица из 256 байт для хранения перестановок
1. s = 0 2. for i = 0 to 255: P[i] = i 3. for j = 0 to 767 // выполнить пп. 4-6: 4. i = j mod 256 5. s = P[(s + P[i] + K[j mod c]) mod 256] 6. Temp = P[i] P[i] = P[s] P[s] = Temp 7. Если используется преобразование вектора инициализации for j = 0 to 767 // выполнить пп. 8-10: 8. i = j mod 256 9. s = P[(s + P[i] + V[j mod z]) mod 256] 10. Temp = P[i] P[i] = P[s] P[s] = Temp
Генерация выходной ключевой последовательности[2].
Для генерации L байт выходного ключевого потока выполняются следующие операции:
L : длина ключевой последовательности в байтах
1. i = 0 2. Повтор пп. 3-6 L раз: 3. s = P[(s + P[i]) mod 256] 4. Output = P[(P[P[s]] + 1) mod 256] 5. Temp = P[i] P[i] = P[s] P[s] = Temp 6. i = (i + 1) mod 256
Функция VMPC[2] степени k < n над n-элементным множеством x∈A, A = {0,1,…n-1}:
for x = 0 to n-1: Qk(x) = VMPCk(P(x)) = P(Pk(Pk-1(…(P1(P(x)))…)))
Где P: A → A взаимно однозначная n-элементная перестановка
Pi (x) n-элементная перестановка,
Pi = fi (P(x)), Pi(x) ≠ P(x) ≠ Pj (x), i≠j i,j∈{1,2…k}
fi (x) = (x + i) mod n ,
Функция VMPC 1 степени Q1 (x)= VMPC1 (P(x) )=P(P(P(x))+1)
Функция VMPC 2 степени Q2 (x)= VMPC2 (P(x))=P(P(P(P(x))+1)+2)
Функция VMPC 3 степени Q3 (x)= VMPC3 (P(x))=P(P(P(P(P(x))+1)+2)+3)
P(x) – один из вариантов[2] перестановки {0,1,2,3,4}
x | 0 | 1 | 2 | 3 | 4 |
P(x) | 3 | 0 | 4 | 1 | 2 |
VMPC1 (P(x)) | 4 | 2 | 1 | 0 | 3 |
VMPC1 (P(x))=P(P(P(x)) + 1)
x = 0
P(0) = 3
P(P(0)) = 1
P(P(0)) + 1 = 2
P(P(P(0) + 1)) = 4
VMPC1 (P(0)) = 4
Нахождение обратного значения функции VMPC является вычислительно сложной задачей[2].
Например, при n = 256 для вычисления обратного значения функции VMPC1 требуется
операций, для VMPC2 -
, для VMPC3 -
.
Восстановление n − элементной перестановки P, соответствующей значению Q(X)= VMPCk (P(X)).
X, Y − временные переменные
Для элемента P(x) = y вводятся следующие обозначения:
X − аргумент: base или parameter
Y − значение: parameter или base соответственно
Пример: для элемента P(0) = 3: если аргумент 0 – parameter, то значение 3 – base.
Алгоритм:
Нахождение всех возможных элементов перестановки P по заданному Q и уже найденным элементам перестановки P.
D, C − временные переменные
Обозначения:
statement y − последовательность y из k + 2 элементов перестановки P, использованных для вычисления Q(y).
word x последовательности y −элемент последовательности y под номером x.
Алгоритм:
Выбор такого нового элемента перестановки P, вычисление которого позволит найти максимальное количество элементов P на последующих шагах алгоритма нахождения обратного значения функции VMPCk. В результате выполнения алгоритма отбора определяется base нового элемента и произвольно выбирается его значение parameter. Данный алгоритм подходит для случая k<4.
B, R − временные переменные
Ta, Tv − временные массивы
W[j] − массив чисел
Алгоритм:
Вероятность получения двух последовательных одинаковых результатов при генерации ключевой последовательности при использовании шифра VMPC равна что совпадает с соответствующей вероятностью идеального генератора случайной последовательности[2]. - число разрядов внутреннего состояния генератора псевдослучайной последовательности, обычно равно . В 2005 году А. Максимов показал, что на основании выходных бит возможно отличить последовательность генератора VMPC от случайного потока [4]
Эксперименты, проведенные Б.Жултаком, показали, что не наблюдается статистически значимого отклонения вероятности появления в выходной последовательности:
Утверждается, что потоковый шифр, благодаря значительной модификации исходного RC4 с учетом его уязвимостей, более устойчив к существующим атакам на потоковые шифры и атакам на шифр RC4[2]. В то же время, безопасность большинства потоковых шифров практически сводится к нулю при использовании одного и того же ключа для зашифрования различных открытых текстов. В таком случае потоковый шифр уже не является генератором одноразового блокнота (потока случайных бит для зашифрования открытого текста). Данная проблема шифром VMPC в некотором роде решается использованием уникального вектора инициализации для каждого зашифрованного потока.
Утверждается, что сложность атаки на шифр составляет операций[2]. Однако, существует метод, защищающий алгоритм от возможных уязвимостей. Данный подход заключается в повторении зависимой от ключа перестановки два раза: до и после перестановки, зависимой от вектора инициализации. Данное ключевое расписание именуется KSA3.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .