"Человек - самое уязвимое место в системе безопасности.."
Главная » Защита информации - Разное » Конгруэнтные генераторы

Конгруэнтные генераторы

Линейные конгруэнтные генераторы

Пусть x0, a, c Є Vn — случайно фиксированные элементы. Обычно говорят, что последовательность x1, x2, … Є Vn создается линейным конгруэнтным генератором с параметрами (xn, a, c, N), если такая последовательность удовлетворяет рекуррентному соотношению:

  • xi+1 = (axt + c) mod N, t = 0,1,2,…; (формула №1)

Характеристика x0 Є Vn называют начальным параметров, a ≠ 0 — множителем, с — приращением, N — сила алфавита за модулем. Если c = 0, то (формула №1) определяет мультипликативный конгруэнтный генератор, а если c ≠ 0 — смешанный конгруэнтный генератор. Нужно отметить, что Д. Лемер предложил мультипликативный конгруэнтный генератор в 1948 году, а У. Томсон смешанный конгруэнтный генератор в 1958 году.

Теорема 1.

Для любых K ≥ 1, t ≥ 0 общий показатель конгруэнтной последовательности (формула №1) удовлетворяет соотношению xi+k:

  • (xi +kc) mod N, если a = 1
  • (akxi + (ak-1)/(a-1)×c) mod N, если a > 1
  • Формула №2

при этом будет такой номер 0 ≤ T ≤ N — 1, что последовательность (формула №1), начиная с этого номера T, зацикливается с периодом 1 ≤ U ≤ N, таким, что T + U ≤ N:

  • x0, x1, …, xT, …, xT+U-1 — различный
  • xT+U = xT, t ≥ T
  • Формула №3

Доказательство

Соотношение (формула №2) получается К-кратным рекурсивной реализации соотношение (формула 1) с учетом известного равенства:

  • 1+ a + a2 + … + ak-1 = (ak-1)/(a-1)

Факт зацикливания последовательности {xt} вытекает из вида рекуррентного соотношения (формула 1). Действительно, множество разрешимых значение xt, не может иметь других элементов, кроме элементов множества {0, 1, …, N — 1} силы N. Однако, если для некоторого наименьшего значения индекса t` совпали компоненты последовательности xt` = x, где t« — t` = U, то такое соотношение сохранится и для следующих значений индексов:

  • xt = xt+u, t = t` + 1, t` + 2, …

Из (формула №2) видно, что при a = 1 нецелесообразно реализовывать для имитации РРСП.

Следствие теоремы 1

Для любого k ≥ 1 при a > 1 подпоследовательность [x0, xk,x2k, x3k…] взятая из конгруэнтной последовательности (формула 1) удалением всех членов с номерами, не кратными k, является линейной смешанной конгруэнтной последовательностью с параметрами (x0,a¬,c¬,N), где a¬ = ak mod N, c¬ = (ak-1)/(a-1) mod N.

Доказательство

Исследуемую подпоследовательность обозначим xi = xik, i = 0,2,.. Тогда (формула №2) будет иметь вид:

  • i+1 = (a¬x¬i + c¬) mod N, i = 0,1,2,..

Что и видно, согласно (формула 1), конгруэнтную последовательность с новыми параметрами.

Следствие 2

Для общего члена линейной смешанной конгруэнтной последовательности (формула 1) при a > 1:

  • xk = ((akx0) + (ak-1)/(a-1) × C) mod N, k = 1,2..
  • Формула №4

Доказательство

Полагая в (формула 2) t = 0, получаем (формула 4).

Следствие 3

Максимальное возможный период конгруэнтной последовательности (формула 4) не превышает силы текущего алфавита Umax ≤ N.

Доказательство

Из теоремы 1, U ≤ N — T, где 0 ≤ T ≤ N — 1. Поэтому Umax ≤ N.

Одной из главных задач при создании конгруэнтного генератора является поиск значений x0,a,c для которых период достигает максимально разрешимого значение Tmax. Тонкости программного использования такого генератора (формула 1) приводит к трём самым реализуемым вариантам задания модуля N:

  • N = 2q, где q + 1: число двоичных разрядов ЭВМ, нужных для целочисленной арифметики
  • N = 10q, q ≥ 1
  • N — простое число

Теорема 2

Для линейной конгруэнтной последовательности (формула 1) максимальное значение периода Umax = N достигается, когда выполнены следующие условия:

  • c и N — взаимно простые числа
  • число b = a — 1 кратно P для любого числа P, являющегося делителем N
  • число b кратно 4, если N кратно 4

Теорема 3

Если с = 0, то максимально возможный период мультипликативной конгруэнтной последовательности равен Umax = λ(N) и достигается, если x0 и N — взаимно простые числа и а — первообразный элемент по модулю N (aλ(N))

Следствие 4

Если N = 2q, q ≥ 4, то максимальное значение периода Umax = 2q-2 = N/4 достигается, если x0 ≥ 1 — нечётное число и a (mod8) Є {3,5}.

Теорема 4

Если c = 0, N = 10q, q ≥ 5 и x0 не кратно двум или пяти, то максимально разрешимое значение периода Umax = 5 × 10q-2 = N/20 достигается тогда, когда вычет a (mod 200) принимает одно из следующих 32 магических значений:

  • 3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 91, 109, 117, 123, 131, 133, 139, 141, 147, 163, 171, 173, 179, 181, 187, 189, 197

Теорема 5

Если c = 0, x0 и N — простое число, то максимально разрешимое значение периода Umax = N — 1 достигается, если a (mod N) ne; 0 и :

  • a(N-1)/pj — 1 ≠ 0 (mod N), j = 1, s‾1

где p1… ps — простые числа, определяющие каноническое разложение числа N — 1: N — 1 = p1m1…, а m1.. — некоторые натуральные числа.

К примеру.

N = 25 — 1 = 31, N — 1 = 2 × 3 × 5, так что s = 3, p1 = 2, p2 = 3, p3 = 5. Согласно теореме 5, получаем следующие ограничения на выбор множителя a:

  • a ≠ 0 (mod 31), a15 — 1 ≠ 0 (mod 31)
  • a10 — 1 ≠ 0 (mod 31), a6 — 1 ≠ (mod 31)

Нужно отметить, что в мультипликативных конгруэнтных генераторах РРСП для ПК Pentium часто используют модуль N = 231 — 1 = 2147483647. При этом рекомендуемыми значениями множителя а являются следующие числа:

  • 16807, 630360016, 1078318381, 1203248318, 397204094, 2027812808, 13232572445, 764261123, 112718

При этом достигается максимальное значение периода Umax = N — 1 ~ 2.14 * 109.

Линейные конгруэнтные генераторы псевдослучайных последовательностей имеют слабость, которая может быть взята в основу криптоатак. Если смотреть последовательность биграммы (z1, z2): z1 = xt, z2 = xt+1, то в силу (формула 1) на плоскости R2 точки (z1,z2) будут лежать на прямых семейства:

  • z2 = az1 + c — kN, k Є {0,1,2..}

Если бы {xt} являлась РРСП, то точки z1,z2 были бы распределены равномерно. На рис.1 видна диаграмма рассеяния для простого смешанного конгруэнтного генератора (для 64 последовательных значений).

  • xt+1 = (9xt + 13) (mod 64), x0 = 0
  • z2 = 9z1 + 13 — 64k, k Є {0,1..,9}

Диаграмма рассеяния конгруэнтного генератораРисунок — 1, Диаграмма рассеяния для М = 64

На рис.2 показано диаграмма рассеяния для генератора 500 значения:

  • xt+1 = (16807xt + 13) (mod (231 — 1)), x0 = 0

Диаграмма рассеяния конгруэнтного генератораРисунок 2, Диаграмма рассеяния для M = 231 — 1

Для скрытия этих недостатков реализуют нелинейные конгруэнтные генераторы.

Нелинейные конгруэнтные генераторы

Квадратичный конгруэнтный метод

  • zt+1 = (dx2t + axt + c) mod N, t = 0,1,2…

Характеристики (x0, a, c, d, N) Є V4N × N квадратичной конгруэнтной последовательности (следствие 5) реализует максимально возможный период Umax, определяются теоремой 6.

Теорема 6

Квадратичная конгруэнтная последовательность (следствия 5) имеет самый больший период Umax = N тогда, когда реализованы следующие 4 условия:

  • c и N — взаимно простые числа
  • d и a — кратные Р, где Р — любой нечётные простой делитель для N
  • d — чётное число, причём d = a — 1 (mod 4), если N кратно 4, и d = a-1 (mod 2), если N кратно двум
  • если N кратно девяти, то либо d (mod 9) = 0, либо d (mod 0) = 1 и cd(mod9) = 6

Следствие 5

Если N = 2q, q ≥ 2, то самый больший период Umax = 2q для квадратичной конгруэнтной последовательности, достигается тогда, когда C нечётно, d чётно, а a — нечётное число:

  • a = ( d + 1) mod 4

Квадратный метод Ковэю

  • xt+1 = (xt(xt+1))mod2q, t = 0,1,2..

Где модуль N = 2q, q ≥ 2, а начальное значение x0 выбирается так, что x0 (mod 4) = 2. Максимальное значение периода Umax = 2q-2 = N/4. Для повышения компьютерного быстродействия этого нелинейного генератора целесообразно выбирать q равным числу двоичных разрядов, нужных для записи целого числа в ЭВМ (к примеру q = 31)

Метод середины квадрата

  • xt+1 = (xt2(mod 23q) — xt2(mod 2q))/2q, t = 0,1,2..

где q, x0 — параметры этого нелинейного генератора псевдослучайной последовательности. Начальное значение x0 ≠ 1 выбирается среди натуральных чисел, не превосходящих числа 22q — 1, так, чтобы x20 (mod 2q) ≠ 0. Этот метод первым предложил Джоном фон Нейманом в 1946 году.