1.3. Критерии выбора ансамблей псевдослучайных последовательностей

Глава 3. псевдослучайные последовательности

1.3. Критерии выбора ансамблей псевдослучайных последовательностей

К псевдослучайным последовательностям предъявляются следующие требования:

· хорошие авто- и взаимнокорреляционные характеристики;

· сбалансированность структуры;

· высокая эквивалентная линейная сложность;

· большой ансамбль сигналов;

· простота генерации.

Автокорреляционные и взаимнокорреляционные функции

Пусть — кодовая последовательность, — длительность единичного элемента ПСП, — период ПСП.

Периодическая ВКФ кодовой последовательности будет определяться соотношением

, (3.1)

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

При получаем периодическую АКФ:

. (3.2)

ПАКФ показывает связь сигнала со своей копией, смещенной во времени на величину .

Пусть — пиковое значение бокового лепестка ВКФ; — пиковое значение бокового лепестка АКФ; наибольшее пиковое значение бокового лепестка корреляционной функции. Качество корреляционных характеристик определяется наименьшим значением .

Корреляционные свойства кодовых последовательностей, используемых в широкополосных СПИ, зависят от типа кодовой последовательности , ее длины , частоты следования символов , посимвольной структуры [25-32].

Сбалансированность структуры

Сбалансированность кодовой последовательности заключается в том, что число единиц и нулей в ней должно отличаться не более, чем на один символ. Выполнение данного требования позволяет исключить постоянную составляющую информационного сигнала.

Эквивалентная линейная сложность

Под эквивалентной линейной сложностью (ЭЛС) последовательности понимается степень непредсказуемости ее символов. Обычно линейная сложность численно равна длине эквивалентного регистра с обратной связью, посредством которого может быть сформирована данная псевдослучайная последовательность.

Ансамбль сигналов

Под ансамблем (объемом) сигналов понимается число возможных различных сигналов, формируемых на единой алгоритмической основе.

Все перечисленные параметры играют важную роль при выборе того или иного семейства последовательностей. Основные характеристики хорошо известных и новых двоичных ПСП представлены в табл.3.1.

Таблица 3.1

Семейство Период Объем Линейная сложность Максимальное значение боковых пиков
М-последователь-ности
Голда   , -нечетно
, -четно
Касами Малое -четно
Касами Большое -четно
Бент-после-довательности
Мак Элис
GMW
Де Брейна
Холла
Лежандра
Последовательности No ,
Норм-следовые последовательности TN ,
Последовательности Кердока -четно
QF- последовательности ,
IMY tr (Y =3) , -нечетно
IMY tr(Y =3) , -четно
IMY tr(Y) =0

М-последовательности

М-последовательности, известные еще как последовательности Хаффмена, относятся к линейным рекуррентным последовательностям максимального периода.

Значение каждого текущего символа в M-последовательности зависит от значений предыдущих символов и определяется рекуррентным правилом:

(3.3)

где и могут принимать значение 0 или 1; Å — знак сложения по модулю два; число называется памятью последовательности . Из выражения (3.3) следует, что устройство, вырабатывающее двоичную линейную рекуррентную последовательность, должно помнить последних символов последовательности и складывать их по модулю два с весами задаваемыми правилом кодирования.

M-последовательности строятся на основе неприводимых примитивных двоичных многочленов. Общее число возможных различных M-последовательностей максимального периода в ансамбле определяется из выражения [26,27]

, (3.4)

где — функция Эйлера, — степень неприводимого примитивного многочлена

M-последовательности обладают следующими свойствами:

· являются периодическими с периодом , где — длина регистра, с помощью которого формируется M-последовательность;

· все импульсы в периоде распределены равновероятно;

· сумма двух M-последовательностей, сдвинутых относительно друг друга, также является M-последовательностью;

· в M-последовательности длиной содержатся все n-значные комбинации двоичных символов кроме нулевой;

· в каждом периоде общее число единиц отличается от общего числа нулей не более чем на единицу.

М-последовательности, будучи линейными, характеризуются малым значением эквивалентной линейной сложности , равным . Для раскрытия структуры линейного кода достаточно безошибочно принять следующих подряд элементов последовательности.

Формируются M-последовательности с помощью сдвиговых регистров и схем суммирования по модулю два. Структура цифрового автомата для формирования М-последовательности полностью определяется видом неприводимого примитивного многочлена.

М-последовательности служат основой для формирования других многочисленных ансамблей ПСП: последовательностей Голда, Касами, Бент-последовательностей, последовательностей GMW.

Пример. Построить М-последовательность над полем Галуа , схему формирования и АКФ.

Выберем из табл.3.2 неприводимый двоичный многочлен .

Пусть начальное состояние регистра 1000.

Тогда формирование -го элемента последовательности будет определяться выражением (3.3):

. (3.5)

В неприводимом двоичном многочлене коэффициенты , , следовательно,

. (3.6)

Тогда, ;

;

… .

Таким образом, получим последовательность: 100011110101100 1000111101… .

На рис.3.1 приведена схема формирования М-последовательности, в которой число элементов задержки и количество сумматоров определяется выражением (3.6).

Рис.3.1. Схема формирования М-последовательности

Периодическая АКФ М-последовательности рассчитана в пакете Matcad по формуле (3.2) и показана на рис.3.2.

Рис.3.2. Периодическая АКФ М-последовательности

Задание к лабораторной работе «Построение и расчет



Источник: https://infopedia.su/17x111f7.html

Подробно о генераторах случайных и псевдослучайных чисел

1.3. Критерии выбора ансамблей псевдослучайных последовательностей

На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора.

Основная цель — получить feedback и поделиться знаниями.

Генераторы случайных чисел — ключевая часть веб-безопасности.

Небольшой список применений:

  • Генераторы сессий(PHPSESSID)
  • Генерация текста для капчи
  • Шифрование
  • Генерация соли для хранения паролей в необратимом виде
  • Генератор паролей
  • Порядок раздачи карт в интернет казино

Как отличить случайную последовательность чисел от неслучайной?

Пусть есть последовательность чисел: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9. Является ли она случайной? Есть строгое определение для случайной величины.

Случайная величина — это величина, которая принимает в результате опыта одно из множества значений, причём появление того или иного значения этой величины до её измерения нельзя точно предсказать.

Но оно не помогает ответить на наш вопрос, так как нам не хватает информации для ответа. Теперь скажем, что данные числа получились набором одной из верхних строк клавиатуры. «Конечно не случайная» — воскликните Вы и тут же назовете следующие число и будете абсолютно правы.

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

Чуть более сложный пример или число Пи

Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью.

Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты. Данный пример накладывает ещё одно ограничение на генераторы случайных чисел.

Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.

Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)

Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел.

ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии. Энтропия – это мера беспорядка.

Информационная энтропия — мера неопределённости или непредсказуемости информации. Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.

Уязвимости ГПСЧ

  • Предсказуемая зависимость между числами.
  • Предсказуемое начальное значение генератора.
  • Малая длина периода генерируемой последовательности случайных чисел, после которой генератор зацикливается.

Линейный конгруэнтный ГПСЧ(LCPRNG)

Распространённый метод для генерации псевдослучайных чисел, не обладающий криптографической стойкостью.

Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой: где a(multiplier), c(addend), m(mask) — некоторые целочисленные коэффициенты.

Получаемая последовательность зависит от выбора стартового числа (seed) X0 и при разных его значениях получаются различные последовательности случайных чисел. Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].

Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений

Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия [8], эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.

Предсказание результатов линейно-конгруэнтного метода

Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь [4](есть онлайн запуск) и здесь [5]. Описание алгоритма можно найти в [9]. Простая реализация конгруэнтного метода на Java.

public static int a = 45;public static int c = 21;public static int m = 67;public static int seed = 2; public static int getRand() { seed = (a * seed + c) % m; return seed;} public static void main(String[] args) { for(int i=0; i> (48 — bits));} Результатом является nextseed сдвинутый вправо на 48-32=16 бит.

Данный метод называется truncated-bits, особенно неприятен при black-box, приходится добавлять ещё один цикл в brute-force. Взлом будет происходить методом грубой силы(brute-force). Пусть мы знаем два подряд сгенерированных числа x1 и x2.

Тогда необходимо перебрать 216 = 65536 вариантов oldseed и применять к x1 формулу: ((x1*multiplier + addend) & mask) 16); if (nextInt == v2) { System.out.

println(«Seed found: » + seed); Random crackingRandom = new Random(); try { /* set the seed for Random to be convinced that we have found the right seed because constructor Random (long seed) uses the private static long initialScramble (long seed) { return (seed multiplier) & mask; } for simplicity will use Reflection */ Field privateSeedField = Random.class.

getDeclaredField(«seed»); privateSeedField.setAccessible(true); AtomicLong crackingSeed = (AtomicLong)privateSeedField.get(crackingRandom); crackingSeed.set(seed); }catch(Exception e) { System.out.println(e.toString()); System.exit(1); } long cv1 = crackingRandom.nextInt(); long cv2 = crackingRandom.nextInt(); long cv3 = crackingRandom.nextInt(); long cv4 = crackingRandom.

nextInt(); System.out.println(«Set fiend seed and generate random numbers»); System.out.

println(«cv1=» + cv1 + «cv2=» + cv2 + «cv3=» + cv3 + «cv4=» + cv4); break; } } }} Вывод данной программы будет примерно таким: v1 = -1184958941v2 = 274285127v3 = -1566774765v4 = 30466408Seed found: -77657469128792Set fiend seed and generate random numberscv1 = 274285127cv2 = -1566774765cv3 = 30466408cv4 = -803980434 Несложно понять, что мы нашли не самый первый seed, а seed, используемый при генерации второго числа. Для нахождения первоначального seed необходимо провести несколько операций, которые Java использовала для преобразования seed, в обратном порядке. public static long getPreviousSeed(long prevSeed) { long seed = prevSeed; // reverse the addend from the seed seed -= addend; // reverse the addend long result = 0; // iterate through the seeds bits for (int i = 0; i < 48; i++) { long mask = 1L 1) ((php_uint32)(-(php_int32)(loBit(u))) & 0x9908b0dfU)) /* {{{ php_mt_reload */static inline void php_mt_reload(TSRMLS_D){ /* Generate N new values in state Made clearer and faster by Matthew Bellew (matthew.bellew@home.com) */ register php_uint32 *state = BG(state); register php_uint32 *p = state; register int i; for (i = N - M; i--; ++p) *p = twist(p[M], p[0], p[1]); for (i = M; --i; ++p) *p = twist(p[M-N], p[0], p[1]); *p = twist(p[M-N], p[0], state[0]); BG(left) = N; BG(next) = state;}/* }}} */ /* {{{ php_mt_initialize */static inline void php_mt_initialize(php_uint32 seed, php_uint32 *state){ /* Initialize generator state with seed See Knuth TAOCP Vol 2, 3rd Ed, p.106 for multiplier. In previous versions, most significant bits (MSBs) of the seed affect only MSBs of the state array. Modified 9 Jan 2002 by Makoto Matsumoto. */ register php_uint32 *s = state; register php_uint32 *r = state; register int i = 1; *s++ = seed & 0xffffffffU; for( ; i < N; ++i ) { *s++ = ( 1812433253U * ( *r (*r >> 30) ) + i ) & 0xffffffffU; r++; }}/* }}} */ /* {{{ php_mt_srand */PHPAPI void php_mt_srand(php_uint32 seed TSRMLS_DC){ /* Seed the generator with a simple uint32 */ php_mt_initialize(seed, BG(state)); php_mt_reload(TSRMLS_C); /* Seed only once */ BG(mt_rand_is_seeded) = 1;}/* }}} */ /* {{{ php_mt_rand */PHPAPI php_uint32 php_mt_rand(TSRMLS_D){ /* Pull a 32-bit integer from the generator state Every other access function simply transforms the numbers extracted here */ register php_uint32 s1; if (BG(left) == 0) { php_mt_reload(TSRMLS_C); } —BG(left); s1 = *BG(next)++; s1 = (s1 >> 11); s1 = (s1 18) );}
Можно заметить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 (s1 >> 18)). В бинарном представление операция выглядит так:

10110111010111100111111001110010 s1

00000000000000000010110111010111100111111001110010 s1 >> 18

10110111010111100101001110100101 s1 (s1 >> 18)

Видно, что первые 18 бит (выделены жирным) остались без изменений. Напишем две функции для инвертирования битового сдвига и xor public static long unBitshiftRightXor(long value, long shift) { // we part of the value we are up to (with a width of shift bits) long i = 0; // we accumulate the result here long result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part long partMask = (-1 >> (shift * i); // obtain the part long part = value & partMask; // unapply the xor from the next part of the integer value = part >>> shift; // add the part to the result result |= part; i++; } return result;} public static long unBitshiftLeftXor(long value, long shift, long mask) { // we part of the value we are up to (with a width of shift bits) long i = 0; // we accumulate the result here long result = 0; // iterate until we've done the full 32 bits while (i * shift < 32) { // create a mask for this part long partMask = (-1 >>> (32 — shift))

Источник: https://habr.com/post/151187/

12.2. Псевдослучайные последовательности. 12. Методы расширенного спектра. Теоретические основы цифровой связи

1.3. Критерии выбора ансамблей псевдослучайных последовательностей

12.2.1. Свойства случайной последовательности

12.2.2. Последовательности, генерируемые регистром сдвига

12.2.3. Автокорреляционная функция псевдослучайного сигнала

Системы связи расширенного спектра с передачей опорного сигнала (transmitted reference — TR) могут использовать истинно случайный кодовый сигнал для расширения и сужения, поскольку кодовый сигнал и модулированный данными кодовый сигнал одновременно передаются в разных областях спектра.

Метод хранения опорного сигнала (stored reference — SR) не позволяет использовать истинно случайные кодовые сигналы, поскольку код должен храниться или генерироваться приемником.

В системах SR должен применяться псевдошумовой (pseudonoise) или псевдослучайный (pseudorandom) кодовый сигнал.

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

Псевдослучайный код на самом деле не является случайным — это детерминированный периодический сигнал, известный передатчику и приемнику.

Так почему же он называется «псевдослучайным»? Причина в том, что он имеет все статистические свойства дискретного белого шума. Для «неуполномоченного» пользователя такой сигнал будет казаться абсолютно случайным.

12.2.1. Свойства случайной последовательности

Каким должен быть псевдослучайный код, чтобы казаться истинно случайным? Существует три основных свойства любой периодической двоичной последовательности, которые могут быть использованы в качестве проверки на случайность.

1. Сбалансированность. Для каждого интервала последовательности количество двоичных единиц должно отличаться от числа двоичных нулей не больше чем на на один элемент.

2. Цикличность. Циклом называют непрерывную последовательность одинаковых двоичных чисел. Появление иной двоичной цифры автоматически начинает новый цикл. Длина цикла равна количеству цифр в нем.

Желательно, чтобы в каждом фрагменте последовательности приблизительно половину составляли циклы обоих типов длиной 1, приблизительно одну четверть— длиной 2, приблизительно одну восьмую — длиной 3 и т. д.

3. Корреляция. Если часть последовательности и ее циклично сдвинутая копия поэлементно сравниваются, желательно, чтобы число совпадений отличалось от числа несовпадений не более чем на единицу.

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

12.2.2. Последовательности, генерируемые регистром сдвига

Рассмотрим линейный регистр сдвига с обратной связью (рис. 12.7), который состоит из четырехразрядного регистра для хранения и сдвига, сумматора по модулю 2 (операция суммирования по модулю 2 была определена в разделе 2.9.3), а также контура обратной связи с входом регистра.

Работа регистра сдвига управляется последовательностью синхронизирующих импульсов (не показанных на рисунке). С каждым импульсом содержимое регистров сдвигается на одну позицию вправо, а содержимое регистров Х3и Х4 суммируется по модулю 2 (линейная операция). Результат суммирования по обратной связи подается на разряд Х1.

Последовательность, генерируемая регистром сдвига, — это, по определению, выход последнего регистра (в данном случае Х4).

Рис.12.7. Пример линейного регистра сдвига с обратной связью

Предположим, что разряд X, содержит единицу, а все остальные разряды — нули, т.е. начальным состоянием регистра является 1000. В соответствии с рис. 12.7, последующие состояния регистра будут следующими.

1000 0100 0010 1001 1100 0110 1011 0101

1010 1101 1110 1111 0111 0011 0001 1000

Поскольку последнее состояние, 1000, идентично начальному, видим, что приведенная последовательность повторяется регистром через каждые 15 тактов. Выходная последовательность определяется содержимым разряда Х4 на каждом такте. Эта последовательность имеет следующий вид.

0 0 0 1 0 0 1 1 0 1 0 1 1 1 1

Здесь крайний «левый бит является самым ранним. Проверим полученную последовательность на предмет соответствия критериям, приведенным в предыдущем разделе. Последовательность содержит семь нулей и восемь единиц, что соответствует условию сбалансированности.

Рассмотрим циклы нулей — всего их четыре, причем половина их имеет длину 1, а одна четвертая — длину 2. То же получаем для циклов единиц. Последовательность слишком коротка, чтобы продолжать проверку, но видно, что условие цикличности выполняется.

Условие корреляции будет проверено в разделе 12.2.3.

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

Последовательности на выходе генератора могут классифицироваться как имеющие максимальную или не максимальную длину.

Период повторения (в тактах) последовательности максимальной длины, генерируемой n-каскадным линейным регистром сдвига с обратной связью, равен следующему.

(12.3)

Очевидно, что последовательность, сгенерированная регистром сдвига на рис. 12.7, является примером последовательности с максимальной длиной. Если длина последовательности меньше (), говорят, что последовательность имеет не максимальную длину.

12.2.3. Автокорреляционная функция псевдослучайного сигнала

Автокорреляционная функция Rx() периодического сигнала x(t) с периодом Т0была представлена в уравнении (1.23) и приводится ниже в нормированной форме.

, (12.4)

где

(12.5)

Если x(t) является периодическим импульсным сигналом, представляющим псевдослучайный код, каждый из элементарных импульсов такого сигнала называют кодовым символом (code symbol) или элементарным сигналом (chip). Нормированная автокорреляционная функция псевдослучайного сигнала с единичной длительностью элементарного сигнала и периодом р элементарных сигналов может быть записана следующим образом.

(12.6)

График нормированной автокорреляционной функции последовательности максимальной длины показан на рис. 12.8. Очевидно, что для =0, т.е. когда сигнал x(t) и его копия идеально совпадают, = 1. В то же время для любого циклического сдвига между x(t) и x(t+) при (1

Источник: https://siblec.ru/telekommunikatsii/teoreticheskie-osnovy-tsifrovoj-svyazi/12-metody-rasshirennogo-spektra/12-2-psevdosluchajnye-posledovatelnosti

Scicenter1
Добавить комментарий