VMPC

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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 (англ. Variably Modified Permutation Composition)[править | править код]

Функция 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)

Пример расчета функции VMPC 1 степени[править | править код]

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[править | править код]

Нахождение обратного значения функции 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. 

Алгоритм: 

  1. Для произвольного значения X ∈ {0,1,…n-1} и Y ∈ {0,1,…n-1} найти один элемент перестановки P из предположения P(X) = Y. 
    1. В случайном порядке выбирается: является ли X – parameter, Y − base, или X – base, Y − parameter элемента P(X) = Y. P(X) = Y − текущий элемент перестановки P. 
  2. Найти все элементы перестановки P по алгоритму поиска.
  3. Если все n  элементов перестановки найдены без противоречий, то завершить алгоритм.
  4. Иначе
    1. Найти новый элемент перестановки по алгоритму отбора, P(X) = Y − текущий элемент перестановки.
    2. Сохранить parameter текущего элемента перестановки.
    3. Перейти к п. 2.
  5. Если при выполнении п. 2. возникает противоречие:
    1. Удалить все найденные при выполнении п. 2. элементы перестановки P
    2. Для текущего элемента перестановки P: parameter = (parameter + 1) mod n,
    3. Если parameter принимает значение, сохраненное при выполнении п. 4.2 , то:
      1. удалить текущий элемент перестановки P.
      2. за текущий элемент перестановки принять значение, полученное при выполнении п. 1.
      3. перейти к п. 5.1.
  6. Перейти к п.2.

Алгоритм поиска[править | править код]

Нахождение всех возможных элементов перестановки P по заданному Q и уже найденным элементам перестановки P.

D, C − временные переменные

Обозначения:

statement y − последовательность y из k + 2 элементов перестановки P, использованных для вычисления Q(y).

word x последовательности y −элемент последовательности y под номером x.

Алгоритм:

  1. C = 0; D = 0;
  2. Если известен элемент P:
    1. Если элемент P(D) и k других известных элементов удовлетворяют общей схеме k + 1 элементов любой последовательности statement, то найти оставшееся word этой последовательности
    2. Если найденное word не является известным элементом P
      1. Обозначить найденное word как элемент P
      2. С = 1
    3. Если найденное word противоречит какому-либо из найденных ранее элементов, сообщить об ошибке, завершить алгоритм поиска.
  3. D = D + 1
  4. Если D < n перейти к п.2
  5. Если C = 1 перейти к п.1.

Алгоритм отбора[править | править код]

Выбор такого нового элемента перестановки P, вычисление которого позволит найти максимальное количество элементов P на последующих шагах алгоритма нахождения обратного значения функции VMPCk. В результате выполнения алгоритма отбора определяется base нового элемента и произвольно выбирается его значение parameter. Данный алгоритм подходит для случая k<4.

B, R − временные переменные

Ta, Tv − временные массивы

W[j] − массив чисел

Алгоритм:

  1. Инициализация переменных
    1. Ta = 0 , Tv = 0
    2. B = 0
    3. R = 1
  2. Подсчет количества m известных элементов перестановки, которые являются word в последовательности statement, в которой неизвестный элемент P является word R c аргументом B. Ta = Ta + W[m]
  3. Подсчет количества m известных элементов перестановки P, которые являются word в последовательности statement, в которой неизвестный элемент P является word R со значением B. Tv = Tv + W[m]
  4. R = R + 1
  5. Если R < n перейти к п.2.
  6. B = B + 1
  7. Если B < n перейти к п.1.c.
  8. Выбирается значения index − любой из индексов массивов Ta или Tv, при котором значение, хранимое в ячейке массива максимально.
  9. Если в п.8 выбран index массива Ta, то:
    1. X = index
    2. Случайно выбирается Y ∈ {0,1,…n-1}, такой что элемент перестановки со значением Y еще не найден.
    3. Результат: P(x) = Y X − base, Y – parameter
  10. Если в п.8 выбран index массива Tv , то:
    1. Y = index
    2. Случайно выбирается X ∈ {0,1,…n-1}, такой что элемент перестановки со значением X еще не найден.
    3. Результат: P(x) = Y X – parameter, Y − base

Особенности[править | править код]

Вероятность получения двух последовательных одинаковых результатов при генерации ключевой последовательности при использовании шифра VMPC равна  что совпадает с соответствующей вероятностью идеального генератора случайной последовательности[2].  -  число разрядов внутреннего состояния генератора псевдослучайной последовательности, обычно равно . В 2005 году А. Максимов показал, что на основании выходных бит возможно отличить последовательность генератора VMPC от случайного потока [4]

 Эксперименты, проведенные Б.Жултаком, показали, что не наблюдается статистически значимого отклонения вероятности появления в выходной последовательности:

  • каждого из возможных    значений (   для    байт выходной последовательности);
  • каждой из возможных    пар последовательных значений  (   для    байт выходной последовательности);
  • каждой из возможных   троек последовательных значений (   для    байт выходной последовательности)

Безопасность[править | править код]

Утверждается, что потоковый шифр, благодаря значительной модификации исходного RC4 с учетом его уязвимостей, более устойчив к существующим атакам на потоковые шифры и атакам на шифр RC4[2]. В то же время, безопасность большинства потоковых шифров практически сводится к нулю при использовании одного и того же ключа для зашифрования различных открытых текстов. В таком случае потоковый шифр уже не является генератором одноразового блокнота (потока случайных бит для зашифрования открытого текста). Данная проблема шифром VMPC в некотором роде решается использованием уникального вектора инициализации для каждого зашифрованного потока.

Утверждается, что сложность атаки на шифр составляет операций[2]. Однако, существует метод, защищающий алгоритм от возможных уязвимостей. Данный подход заключается в повторении зависимой от ключа перестановки два раза: до и после перестановки, зависимой от вектора инициализации. Данное ключевое расписание именуется KSA3.

Ссылки[править | править код]

См. также[править | править код]

Литература[править | править код]

  1. ↑ Габидулин Э.М., Кшевецкий А.С., Колыбельников А.И. Защита информации. — Москва: МФТИ, 2011. — P. 225.
  2. ↑ 1 2 3 4 5 6 7 8 9 Zoltak B. VMPC One-Way Function and Stream Cipher (англ.) // Bimal R., Meier W. Fast Software Encryption. — Berlin: Springer Berlin Heidelberg, 2004. — P. 210-225. — ISBN 978-3-540-25937-4. — doi:10.1007/978-3-540-25937-4_14. Архивировано 23 апреля 2018 года.
  3. ↑ Шнайер Б. Практическая криптография. — Москва: 2-е изд. — М.: Вильямс, 2005. — P. 610.
  4. ↑ Goutam P., Subhamoy M. RC4 stream cipher and its variants (англ.). — Boca Raton, FL: CRC Press, 2012. — ISBN 978-1-4398-3135-9.
Источник — https://ru.wikipedia.org/w/index.php?title=VMPC&oldid=131084230