VMPC

VMPC (англ. Variably Modified Permutation Composition) — это потоковый шифр, применяющийся в некоторых системах защиты информации в компьютерных сетях. Шифр разработан криптографом Бартошем Жултаком (польск. Bartosz Żółtak,англ. Bartosz Zoltak) в качестве усиленного варианта популярного шифра RC4. Алгоритм VMPC строится как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов. Основные преимущества шифра, как и RC4 — высокая скорость работы, переменный размер ключа и вектора инициализации (от 128 до 512 бит включительно), простота реализации (буквально несколько десятков строк кода).

Основа шифра - генератор псевдослучайных чисел, базой которого является односторонняя необратимая функция VMPC (англ. Variably Modified Permutation Composition):

Реализация алгоритма

Ключевое расписание

Алгоритм преобразования ключа и (дополнительно) вектора инициализации в 256-элементную перестановку P. Инициализация глобальной переменной s.

С : Длина ключа в байтах <math>(16 \le c \le 64)</math>

K : Ключ

z : Длина вектора инициализации в байтах <math>(16 \le z \le 64)</math>

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

Алгоритм зашифрования

Генерация выходной ключевой последовательности.
Для генерации 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 степени 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-элементная перестановка
P_i (x)   n-элементная перестановка,
P_i = f_i (P(x)),   P_i(x) ≠ P(x) ≠ P_j (x),   i≠j   i,j∈{1,2…k}
f_i (x) = (x + i) mod n ,

Функция VMPC 1 степени Q₁ (x)= VMPC₁ (P(x) )=P(P(P(x))+1)

Функция VMPC 2 степени Q₂ (x)= VMPC₂ (P(x))=P(P(P(P(x))+1)+2)

Функция VMPC 3 степени Q₃ (x)= VMPC₃ (P(x))=P(P(P(P(P(x))+1)+2)+3)

Пример расчета функции VMPC 1 степени

P(x) – один из вариантов перестановки {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

VMPC₁ (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

VMPC₁ (P(0)) = 4

Поиск обратного значения функции VMPC

Нахождение обратного значения функции VMPC является вычислительно сложной задачей.
Например, при n = 256 для вычисления обратного значения функции VMPC₁ требуется <math>2^{260}</math> операций, для VMPC₂ - <math>2^{420}</math> , для VMPC₃ - <math>2^{550}</math>.

Алгоритм

Восстановление n − элементной перестановки P, соответствующей значению Q(X)= VMPC_k (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 на последующих шагах алгоритма нахождения обратного значения функции VMPC_k. В результате выполнения алгоритма отбора определяется base нового элемента и произвольно выбирается его значение parameter. Данный алгоритм подходит для случая k<4.

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

T_a, T_v − временные массивы

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

Алгоритм:

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

Особенности

Вероятность получения двух последовательных одинаковых результатов при генерации ключевой последовательности при использовании шифра VMPC равна <math>2^{-N}</math> что совпадает с соответствующей вероятностью идеального генератора случайной последовательности.  <math>N</math> -  число разрядов внутреннего состояния генератора псевдослучайной последовательности, обычно равно <math>8</math>. В 2005 году А. Максимов показал, что на основании <math>2^{40}</math> выходных бит возможно отличить последовательность генератора VMPC от случайного потока

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

• каждого из возможных <math>2^{8}</math>   значений (<math>P = 1/256</math>   для <math>2^{41.85}</math>   байт выходной последовательности);
• каждой из возможных <math>2^{16}</math>   пар последовательных значений  (<math>P = 1/65536</math>   для <math>2^{40.1}</math>   байт выходной последовательности);
• каждой из возможных <math>2^{24}</math>   троек последовательных значений (<math>P = 1/16777216</math>   для <math>2^{41.6}</math>   байт выходной последовательности)

Безопасность

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

Утверждается, что сложность атаки на шифр составляет <math>2^{900}</math> операций. Однако, существует метод, защищающий алгоритм от возможных уязвимостей. Данный подход заключается в повторении зависимой от ключа перестановки два раза: до и после перестановки, зависимой от вектора инициализации. Данное ключевое расписание именуется KSA3.

Ссылки

• [www.vmpcfunction.com/cipher_e.htm VMPC Stream Cipher]
• [www.vmpcfunction.com/vmpc.pdf Спецификация VMPC]
• Bartosz Zoltak [www.springerlink.com/content/rx53d29tv4vu0he2/ VMPC One-Way Function and Stream Cipher]

См. также

• RC4

Отрывок, характеризующий VMPC

Петя отер руками пот, покрывавший его лицо, и поправил размочившиеся от пота воротнички, которые он так хорошо, как у больших, устроил дома.
Петя чувствовал, что он имеет непрезентабельный вид, и боялся, что ежели таким он представится камергерам, то его не допустят до государя. Но оправиться и перейти в другое место не было никакой возможности от тесноты. Один из проезжавших генералов был знакомый Ростовых. Петя хотел просить его помощи, но счел, что это было бы противно мужеству. Когда все экипажи проехали, толпа хлынула и вынесла и Петю на площадь, которая была вся занята народом. Не только по площади, но на откосах, на крышах, везде был народ. Только что Петя очутился на площади, он явственно услыхал наполнявшие весь Кремль звуки колоколов и радостного народного говора.
Одно время на площади было просторнее, но вдруг все головы открылись, все бросилось еще куда то вперед. Петю сдавили так, что он не мог дышать, и все закричало: «Ура! урра! ура!Петя поднимался на цыпочки, толкался, щипался, но ничего не мог видеть, кроме народа вокруг себя.
На всех лицах было одно общее выражение умиления и восторга. Одна купчиха, стоявшая подле Пети, рыдала, и слезы текли у нее из глаз.
– Отец, ангел, батюшка! – приговаривала она, отирая пальцем слезы.
– Ура! – кричали со всех сторон. С минуту толпа простояла на одном месте; но потом опять бросилась вперед.
Петя, сам себя не помня, стиснув зубы и зверски выкатив глаза, бросился вперед, работая локтями и крича «ура!», как будто он готов был и себя и всех убить в эту минуту, но с боков его лезли точно такие же зверские лица с такими же криками «ура!».
«Так вот что такое государь! – думал Петя. – Нет, нельзя мне самому подать ему прошение, это слишком смело!Несмотря на то, он все так же отчаянно пробивался вперед, и из за спин передних ему мелькнуло пустое пространство с устланным красным сукном ходом; но в это время толпа заколебалась назад (спереди полицейские отталкивали надвинувшихся слишком близко к шествию; государь проходил из дворца в Успенский собор), и Петя неожиданно получил в бок такой удар по ребрам и так был придавлен, что вдруг в глазах его все помутилось и он потерял сознание. Когда он пришел в себя, какое то духовное лицо, с пучком седевших волос назади, в потертой синей рясе, вероятно, дьячок, одной рукой держал его под мышку, другой охранял от напиравшей толпы.
– Барчонка задавили! – говорил дьячок. – Что ж так!.. легче… задавили, задавили!
Государь прошел в Успенский собор. Толпа опять разровнялась, и дьячок вывел Петю, бледного и не дышащего, к царь пушке. Несколько лиц пожалели Петю, и вдруг вся толпа обратилась к нему, и уже вокруг него произошла давка. Те, которые стояли ближе, услуживали ему, расстегивали его сюртучок, усаживали на возвышение пушки и укоряли кого то, – тех, кто раздавил его.
– Этак до смерти раздавить можно. Что же это! Душегубство делать! Вишь, сердечный, как скатерть белый стал, – говорили голоса.
Петя скоро опомнился, краска вернулась ему в лицо, боль прошла, и за эту временную неприятность он получил место на пушке, с которой он надеялся увидать долженствующего пройти назад государя. Петя уже не думал теперь о подаче прошения. Уже только ему бы увидать его – и то он бы считал себя счастливым!
Во время службы в Успенском соборе – соединенного молебствия по случаю приезда государя и благодарственной молитвы за заключение мира с турками – толпа пораспространилась; появились покрикивающие продавцы квасу, пряников, мака, до которого был особенно охотник Петя, и послышались обыкновенные разговоры. Одна купчиха показывала свою разорванную шаль и сообщала, как дорого она была куплена; другая говорила, что нынче все шелковые материи дороги стали. Дьячок, спаситель Пети, разговаривал с чиновником о том, кто и кто служит нынче с преосвященным. Дьячок несколько раз повторял слово соборне, которого не понимал Петя. Два молодые мещанина шутили с дворовыми девушками, грызущими орехи. Все эти разговоры, в особенности шуточки с девушками, для Пети в его возрасте имевшие особенную привлекательность, все эти разговоры теперь не занимали Петю; ou сидел на своем возвышении пушки, все так же волнуясь при мысли о государе и о своей любви к нему. Совпадение чувства боли и страха, когда его сдавили, с чувством восторга еще более усилило в нем сознание важности этой минуты.
Вдруг с набережной послышались пушечные выстрелы (это стреляли в ознаменование мира с турками), и толпа стремительно бросилась к набережной – смотреть, как стреляют. Петя тоже хотел бежать туда, но дьячок, взявший под свое покровительство барчонка, не пустил его. Еще продолжались выстрелы, когда из Успенского собора выбежали офицеры, генералы, камергеры, потом уже не так поспешно вышли еще другие, опять снялись шапки с голов, и те, которые убежали смотреть пушки, бежали назад. Наконец вышли еще четверо мужчин в мундирах и лентах из дверей собора. «Ура! Ура! – опять закричала толпа.
– Который? Который? – плачущим голосом спрашивал вокруг себя Петя, но никто не отвечал ему; все были слишком увлечены, и Петя, выбрав одного из этих четырех лиц, которого он из за слез, выступивших ему от радости на глаза, не мог ясно разглядеть, сосредоточил на него весь свой восторг, хотя это был не государь, закричал «ура!неистовым голосом и решил, что завтра же, чего бы это ему ни стоило, он будет военным.
Толпа побежала за государем, проводила его до дворца и стала расходиться. Было уже поздно, и Петя ничего не ел, и пот лил с него градом; но он не уходил домой и вместе с уменьшившейся, но еще довольно большой толпой стоял перед дворцом, во время обеда государя, глядя в окна дворца, ожидая еще чего то и завидуя одинаково и сановникам, подъезжавшим к крыльцу – к обеду государя, и камер лакеям, служившим за столом и мелькавшим в окнах.
За обедом государя Валуев сказал, оглянувшись в окно:
– Народ все еще надеется увидать ваше величество.
Обед уже кончился, государь встал и, доедая бисквит, вышел на балкон. Народ, с Петей в середине, бросился к балкону.
– Ангел, отец! Ура, батюшка!.. – кричали народ и Петя, и опять бабы и некоторые мужчины послабее, в том числе и Петя, заплакали от счастия. Довольно большой обломок бисквита, который держал в руке государь, отломившись, упал на перилы балкона, с перил на землю. Ближе всех стоявший кучер в поддевке бросился к этому кусочку бисквита и схватил его. Некоторые из толпы бросились к кучеру. Заметив это, государь велел подать себе тарелку бисквитов и стал кидать бисквиты с балкона. Глаза Пети налились кровью, опасность быть задавленным еще более возбуждала его, он бросился на бисквиты. Он не знал зачем, но нужно было взять один бисквит из рук царя, и нужно было не поддаться. Он бросился и сбил с ног старушку, ловившую бисквит. Но старушка не считала себя побежденною, хотя и лежала на земле (старушка ловила бисквиты и не попадала руками). Петя коленкой отбил ее руку, схватил бисквит и, как будто боясь опоздать, опять закричал «ура!», уже охриплым голосом.
Государь ушел, и после этого большая часть народа стала расходиться.
– Вот я говорил, что еще подождать – так и вышло, – с разных сторон радостно говорили в народе.
Как ни счастлив был Петя, но ему все таки грустно было идти домой и знать, что все наслаждение этого дня кончилось. Из Кремля Петя пошел не домой, а к своему товарищу Оболенскому, которому было пятнадцать лет и который тоже поступал в полк. Вернувшись домой, он решительно и твердо объявил, что ежели его не пустят, то он убежит. И на другой день, хотя и не совсем еще сдавшись, но граф Илья Андреич поехал узнавать, как бы пристроить Петю куда нибудь побезопаснее.


15 го числа утром, на третий день после этого, у Слободского дворца стояло бесчисленное количество экипажей.
Залы были полны. В первой были дворяне в мундирах, во второй купцы с медалями, в бородах и синих кафтанах. По зале Дворянского собрания шел гул и движение. У одного большого стола, под портретом государя, сидели на стульях с высокими спинками важнейшие вельможи; но большинство дворян ходило по зале.
Все дворяне, те самые, которых каждый день видал Пьер то в клубе, то в их домах, – все были в мундирах, кто в екатерининских, кто в павловских, кто в новых александровских, кто в общем дворянском, и этот общий характер мундира придавал что то странное и фантастическое этим старым и молодым, самым разнообразным и знакомым лицам. Особенно поразительны были старики, подслеповатые, беззубые, плешивые, оплывшие желтым жиром или сморщенные, худые. Они большей частью сидели на местах и молчали, и ежели ходили и говорили, то пристроивались к кому нибудь помоложе. Так же как на лицах толпы, которую на площади видел Петя, на всех этих лицах была поразительна черта противоположности: общего ожидания чего то торжественного и обыкновенного, вчерашнего – бостонной партии, Петрушки повара, здоровья Зинаиды Дмитриевны и т. п.
Пьер, с раннего утра стянутый в неловком, сделавшемся ему узким дворянском мундире, был в залах. Он был в волнении: необыкновенное собрание не только дворянства, но и купечества – сословий, etats generaux – вызвало в нем целый ряд давно оставленных, но глубоко врезавшихся в его душе мыслей о Contrat social [Общественный договор] и французской революции. Замеченные им в воззвании слова, что государь прибудет в столицу для совещания с своим народом, утверждали его в этом взгляде. И он, полагая, что в этом смысле приближается что то важное, то, чего он ждал давно, ходил, присматривался, прислушивался к говору, но нигде не находил выражения тех мыслей, которые занимали его.
Был прочтен манифест государя, вызвавший восторг, и потом все разбрелись, разговаривая. Кроме обычных интересов, Пьер слышал толки о том, где стоять предводителям в то время, как войдет государь, когда дать бал государю, разделиться ли по уездам или всей губернией… и т. д.; но как скоро дело касалось войны и того, для чего было собрано дворянство, толки были нерешительны и неопределенны. Все больше желали слушать, чем говорить.