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 тактов работы использовать состояние регистра, в качестве случайного числа.

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

 


 

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

21722. МОДЕЛИ ОЦЕНКИ НАДЕЖНОСТИ ЭМС 117.5 KB
  Распределение экстремальных значений Пусть имеется случайная выборка объемом n взятая из бесконечной совокупности имеющей распределение Fx где х– непрерывная случайная величина.1 Так как разрушение материала связано с существованием наиболее слабой точки в работах по теории надежности рассматривается распределение экстремальных значений. Здесь будет рассмотрено распределение наименьших значений однако этот подход может быть использован и при выводе распределений наибольших значений. Функция распределения наименьших значений функция...
21723. Модели надёжности установок с восстановлением 310 KB
  Модели надёжности установок с восстановлением При экспоненциальном законе распределения времени восстановления и времени между отказами для расчёта показателей надёжности установки с восстановлением пригоден математический аппарат марковских случайных процессов. Дискретный случайный процесс называется марковском если все вероятностные характеристики будущего протекания этого процесса при зависят лишь от того в каком состоянии этот процесс находился в настоящий момент времени и не зависят от того каким образом этот процесс протекал до...
21724. Общие принципы определения ущерба от нарушений электроснабжения 80 KB
  Общие принципы определения ущерба от нарушений электроснабжения Проблема оценки ущерба от нарушений электроснабжения вызываемых отказами электрооборудования возникает как при проектировании так и при эксплуатации энергетических объектов. При проектировании потребность в характеристике ущерба ощущается как правило когда определяется экономическая эффективность капитальных вложений при выборе вариантов технических и организационнохозяйственных решений влияющих на степень надежности электроснабжения потребителей. При эксплуатации...
21725. Технико-экономическая оценка последствий от нарушений электроснабжения объектов производственных систем 240 KB
  Техникоэкономическая оценка последствий от нарушений электроснабжения объектов производственных систем 8.1 Модель поведения участка производства при нарушениях его электроснабжения По характеру последствий все отказы участков производственной системы можно разделить на три группы: 1 не обесценивающие производственную продукцию; 2 частично обесценивающие; 3 полностью обесценивающие. В этом случае длительность простоя производственного участка соответствует длительности нарушения электроснабжения . Большинство нарушений электроснабжения...
21726. Накопители на жестких магнитных дисках 116 KB
  1 БУСД – блок управления 3х фазным синхронным двигателем шпинделя; И –инвертор; СД – синхронный двигатель; БП блок питания; ВК – внутренний контроллер БУП – блок управления позиционированием головки; ОЗУ – оперативное запоминающее устройство ВК; см – сервометка; ДПГ – датчик позиционирования головки. Кроме того он дает разрешение на выпуск головки при достижении минимальной скорости вращения. Для записи и считывания используются магнитные головки представляющие собой катушки индуктивности которые выполняются по тонкопленочной технологии....
21727. Устройства массовой памяти на сменных носителях 180 KB
  Устройства массовой памяти на сменных носителях Вопросы: Магнитооптические диски. Оптические диски CD DVD PD. Эти устройства подключаются к компьютеру с помощью следующих интерфейсов: АТА SCSI USB Наибольшей популярностью пользуются в настоящее время CD DVD и магнитооптические диски. Магнитооптические диски.
21728. Аудио система персонального компьютера 245.5 KB
  Собственно цифровые каналы звуковой карты проходят через интерфейсные схемы например MIDI от шины расширения до ЦАП и от АЦП обратно к шине. На этих картах располагается и порт традиционного MIDI. Интерфейс MIDI Цифровой интерфейс музыкальных инструментов MIDI Musical Instrument Digital Interface является последовательным асинхронным интерфейсом с частотой передачи 3125 Кбит с. В настоящее время интерфейс MIDI имеют и дорогие синтезаторы и дешевые музыкальные клавиатуры пригодные в качестве устройств ввода компьютера.
21729. Коммуникационные устройства 306.5 KB
  Обмен данными требуется для различных целей: передачи файлов совместного использования периферийных устройств например принтеров доступа к разнообразным информационным услугам Интернета и частных сетей приема и передачи факсимильных сообщений посылки сообщений на пейджеры и мобильные телефоны установление голосовой связи IPтелефония видеосвязи и даже совместных игр по сети. СОМпорт Последовательный интерфейс для передачи данных в одном направлении использует одну сигнальную линию по которой информационные биты передаются друг за...
21730. Беспроводные интерфейсы связи 575 KB
  Инфракрасный интерфейс IrDA 2. В беспроводных интерфейсах используются электромагнитные волны инфракрасного IrDA Infrared Data Association и радиочастотного Blue Tooth диапазонов. Инфракрасный интерфейс IrDA 1. Общая характеристика IrDA Применение излучателей и приемников инфракрасного ИК диапазона позволяет осуществлять беспроводную связь между парой устройств удаленных на расстояние нескольких метров.