О распределении первого выходного символа криптосистемы RC4. Московский физико-технический институт (государственный университет). МФТИ (ГУ)

М. А. Пудовкина

Московский инженерно-физический институт

(технический университет)

Во многих программах по защите информации используется криптосхема RC4 (также известная как ARCFOUR), которая представляет собой поточный алгоритм шифрования с произвольным размером ключа, разработанный в 1987 году Rivest R. для RSA Data Security, Inc [1].

В данной работе показано, что распределение первого знака выходной последовательности не является равномерным.

Теорема

Предположим, что перестановка S равновероятно выбирается из множества всех перестановок множества {0,…,m-1} и начальные значения индексов $i_0, j_0$ . Тогда распределение первого выходного символа $z_1$ не равномерно.

Следствие

1. $i_0=2j_0.$

a) $P\left\{ z_1=\nu | \nu\ne j0\right\}= \frac{1} {m} – \frac{1}{{m(m - 1)}}$ ,

b) $P\left\{ z_1= j_0\right\}= \frac{2}{m}$ .

2. $m=0 (mod 2), i_1=1 (mod 2)$ .

a) $P\left\{ z_1=\nu | \nu\ne j_0, i_1–j_0\right\}=\frac{1}{m}+ \frac{2}{{m(m - 1)(m - 2)}}$ ,

b) $P\left\{ z_1= j_0}= P{z_1= i_1–j_0}=\frac{1}{m}– \frac{1}{{m(m - 1)}\right\}$ ,

3. m=1 (mod 2).

a) $P\left\{ z_1=\nu | \nu\ne j_0, i_1–j_0, 0.5i_1(mod m) \right\} =\frac{1}{m}+ \frac{3}{{m(m - 1)(m - 2)}}$ ,

b) $P\left\{ z_1= j_0\right\}= P\left\{z_1= i_1–j_0}=P{ z1=0.5i_1(mod m)}=\frac{1}{m}–\frac{1}{{m(m - 1)}}+ \frac{1}{{m(m - 1)(m - 2)}\right\}$ ,

4. $m=0 (mod 2), i_1=0 (mod 2)$ .

a) $P\left\{ z_1=\nu | \nu\ne j_0, i_1–j_0, 0.5i_1(mod m), 0.5i_1+m/2(mod m)\right\} = \frac{1}{m}+ \frac{4}{{m(m - 1)(m - 2)}}$ ,

b) $P\left\{ z_1= j_0\right\}= P\left\{z_1= i_1–j_0}= P{ z_1=0.5i_1(mod m)}= P{ z_0=0.5i_1+m/2(mod m)}=\frac{1}{m}–\frac{1}{{m(m - 1)}}+ \frac{2}{{m(m - 1)(m - 2)}\right\}$ ,

Литература

Варфоломеев А. А., Жуков А.Е., Пудовкина М. А. Поточные криптосистемы. Основные свойства и методы анализа стойкости. 2000
Mantin I. Shamir A. “A practical attack on broadcast RC4”, Proceeding of FSE’2001, Springer-Verlag.
Pudovkina M. “Short cycles of the alleged RC4 keystream generator ”, 3nd International Workshop on Computer Science and Information Technologies, CSIT’2001, YFA, 2001