28583

Генерация случайных чисел., использование типовых узлов в качестве ДСПЧ

Доклад

Информатика, кибернетика и программирование

Хорошие датчики имеют весьма качественные характеристики и могут использоваться непосредственно для получения ключей однако они сложны и имеют высокую стоимость и поэтому не находят массового применения. Их стоимость существенно ниже они более надежны но использовать выход с них в качестве ключа в чистом виде не рекомендуется частично о том почему их можно использовать мы поговорим в когда будем говорить о системах с открытым ключом. В качестве ДСПЧ можно использовать один из следующих узлов. Использовать его можно несколькими...

Русский

2013-08-20

33.58 KB

1 чел.

Генерация случайных чисел., использование типовых узлов в качестве ДСПЧ

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

    Существует специальное направление в криптографии, которое занимается изучением данной проблемы. С теоретической точки зрения все просто - получение случайной двоичной последовательности длины N по схеме равновероятной выборки из VN(2) сводится к реализации биномиальной схемы с N испытаниями и вероятностью успеха 0.5. На практике такую схему можно смоделировать подбрасыванием монетки N раз (например 0 - орел, 1 - решка). Да не покажется странным, но еще в 50-ые годы случайные числа получали путем вытаскивания фишек из мешка. Сегодня получение случайных чисел превратилось в целую индустрию - разработка датчиков случайных чисел (ДСЧ), их производство, тестирование, эксплуатация и т.д.

    Здесь надо заметить, что для целей генерации ключей не подходят датчики псевдослучайных чисел (ДПСЧ), то есть генераторы последовательностей по статистическим свойствам близким к случайной равновероятной, но на самом деле получаемой по детерминированному закону. Например, в цикле линейной рекурренты максимального периода над GF(2) с минимальным  многочленом степени N вероятность встречи фиксированного отрезка нулей и единиц длины M (0<M< N) равна  отличается от величины 1/2M на величину порядка 1/2N, то есть практически совпадает с характеристиками случайной равновероятной последовательностью. Но по любому отрезку длины N вся рекуррента восстанавливается однозначно. Очевидно, что такие датчики для генерации ключей в чистом виде не подходят. О том, как они применяются ,мы поговорим ниже.

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

    На сегодняшний день достаточно отработана технология создания ДСЧ с использованием стохастических свойств различных физических процессов. Тестирование датчиков проводится по специальным методикам с использованием аппарата математической статистики.

   Обеспечить независимость битов в последовательности, генерируемой таким ДСЧ просто, более сложно обеспечивается равновероятность. Поэтому основной характеристикой ДСЧ является величина отклонения от 0.5 вероятности появления 1 (или 0) на выходе. Хорошие датчики имеют весьма качественные характеристики и могут использоваться непосредственно для получения ключей, однако они сложны и имеют высокую стоимость и поэтому не находят массового применения.

Более простые датчики могут быть реализованы либо в виде отдельной платы к персональному компьютеру, либо быть интегрированы в какую либо другую многофункциональную плату. Их стоимость существенно ниже, они более надежны, но использовать выход с них в качестве ключа в чистом виде не рекомендуется (частично о том почему их можно использовать мы поговорим в когда будем говорить  о системах с открытым ключом). Обычно они применяется совместно с ДПСЧ. Идея этого способа заключается в следующем.

    Рассмотрим две независимые случайные ноль - один величины  и  с вероятностью единицы p и q соответственно. Пусть p = 0.5 - 1, q = 0.5 - 2, тогда если =, то

    P(=1)=P(=1) P(=0)+ P(=0) P(=1)= (0.5 - 1) (0.5+2,)+ (0.5+1) (0.5-2,)

    P(=1)=0.5 - 21 2 

Так как и  1 и  2 меньше чем 0.5, то MAX(1 , 2) >21 2, следовательно, отклонение от 0.5 у величины  меньше, чем у величин  и . В частном случае, когда уклонения у суммируемых величин равны, уклонение а результата равна удвоенному квадрату первоначального уклонения. Таким образом, если просуммировать побитно две случайные последовательности с одним и тем же уклонением, то результирующая последовательность будет более «случайной» т.е. более близкой к равновероятной.

Простого суммирования в таком случае не всегда хватает, поэтому используют следующую схему:

1.   С помощью ДСЧ генерируют начальный вектор длины L (L>N)

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

3.   На ДПСЧ вырабатывают последовательность длины M (M>N)

4.   Из полученной последовательности выбирают N бит, которые используют в качестве случайной последовательности.

 

В качестве ДСПЧ можно использовать один из следующих узлов.
 
Сдвиговый регистр (Feedback Shift Register FSR).

Данный узел мы рассматривали на предыдущей лекции «Типовые элементы шифров». Использовать его можно несколькими способами.

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

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

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

Вопрос о статистических свойствах случайных чисел полученных таким образом в общем виде решения не имеет и существенно зависит от свойств функции обратной связи. В силу этого использовать этот узел в качестве ДПСЧ не специалистам не рекомендуется. Более просто дело обстоит с частным случаем данного узла.

 


 

А также другие работы, которые могут Вас заинтересовать

81414. Основные аспекты взаимосвязи социологии и социальной работы 36.7 KB
  Изучая тему студент должен исходить из тесной взаимосвязи социологии и социальной работы в теоретическом учебнообразовательном и прикладном аспектах. В подготовке специалистов по соцработе социология занимает одно из ведущих мест Универсальный многопрофильный характер социальной работы сближает ее прежде всего с социологией. Речь идет о близости объектов и предметов социологии и социальной работы.
81415. Социологическое знание в социальной работе. Категории индивид, личность, группа, общность, общество. Понятия «социальный факт», «социальная реальность» и «социальное действие» 37.24 KB
  Социологические исследования в социальной работе выполняют многообразные функции. Социологические методы и техника изучения проблем социальной работы выполняют двоякую функцию расширения и углубления социологического и социального образования в целом и получения важной первичной социальной информации без чего невозможны анализ практической социальной работы накопление опыта его обобщения и в целом повышение ее эффективности. Влияние социологии на социальную работу: использование результатов изучения социологами социальной структуры...
81416. Социологические проблемы социального взаимодействия в социальной работе. Понятия: социальная структура, социальные изменения, конфликты интересов основных социальных групп 37.54 KB
  Понятия: социальная структура социальные изменения конфликты интересов основных социальных групп. Социальные изменения представляют собой смену состояний свойств и связей социальных систем. В соответствии со строением и главной характеристикой любой системы можно выделить следующие виды изменений вообще и социальных изменений в частности: Содержательные изменения Под содержанием в науке понимают совокупность элементов системы поэтому здесь речь идет об изменении элементов системы их возникновении исчезновении или изменении ими своих...
81417. Социология в теории социальной работы –наука об обществе как целостной системе и об отдельных социаль 34.67 KB
  Социология в теории социальной работы – наука об обществе как целостной системе и об отдельных социальных институтах рассматриваемых в их связи с общественным целым. Влияние социологии на социальную работу: использование результатов изучения социологами социальной структуры общества и других фундаментальных проблем социологического знания и практической деятельности применение этих данных в подготовке и переподготовке социальных работников анализ самой социальной работы сточки зрения участия в ней разных групп социальных работников...
81418. Социологические парадигмы в анализе социальной работы 38.2 KB
  Парадигма социальных фактов связана с именем Э. Парадигма понимания или социологии действия связана с именами М. Парадигма социального поведения представлена социальным бихевиоризмом Б. Парадигма социальноисторического детерминизма связана с именами К.
81419. Структурно-функциональные социологические парадигмы в анализе социальной работы 35.85 KB
  Основное внимание социологов данного направления сосредотачивается на исследовании того какой вклад различные части общества структуры вносят в интеграцию целостного – социальной системы. Конфликтная модель общества Р. В результате обострение противоречий внутри общества может быть обусловлено рядом причин: диспропорция в распределении власти и отсутствие свободных каналов перераспределения власти. Суть его концепции в следующем: ав каждый момент общество переживает социальный конфликт социальный конфликт вездесущ; б любое общество...
81420. Парадигмы социального поведения при анализе социальной работы 39.02 KB
  Для социального бихевиоризма Скиннера сформировавшегося под влиянием воззрений представителей ортодоксального неопозитивизма и отчасти утилитаризма характерно отождествление механизмов коллективного поведения животных и людей которое рассматривается...
81421. Основные социологические теории и возможность их применения для анализа социальной работы 37.06 KB
  Понимание – познание социального действия через его субъективный смысл который вкладывает в данное действие сам субъект. Суть использования понимания состоит в том чтобы поставить себя в положение других людей для того чтобы увидеть какое именно значение они придают своим действиям или каким целям по своему убеждению служат. Исследование значений человеческих поступков – это в какойто степени просто развитие наших повседневных попыток понять действия множества различных окружающих нас людей. Действие которое соотносится с действиями...
81422. Конформация пептидных цепей в белках (вторичная и третичная структуры). Слабые внутримолекулярные взаимодействия в пептидной цепи; дисульфидные связи 108.54 KB
  Слабые внутримолекулярные взаимодействия в пептидной цепи; дисульфидные связи. βлисты складчатые слои несколько зигзагообразных полипептидных цепей в которых водородные связи образуются между относительно удалёнными друг от друга 0347 нм на аминокислотный остаток в первичной структуре аминокислотами или разными цепями белка а не близко расположенными как имеет место в αспирали. Стабильность вторичной структуры обеспечивается в основном водородными связями определенный вклад вносят и главновалентные связи – пептидные и...