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

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

 


 

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

38437. Многокритериальный синтез позиционного управления на основе многопрограммной стабилизации 2.76 MB
  Комбинированный метод многокритериального синтеза позиционного управления формирует аналитический вид управления, как набор параметров и известных функций состояния из состава «сетевого оператора» конечной сети этих функций и операций над ними
38438. Разработка моделирование процесса поддержки заданных климатических условий в помещении в системе InTouch 2.09 MB
  Трехдиапазонный регулятор температуры 60 3. Ведь отапливать рабочие помещения в выходные и праздничные дни не следует так интенсивно как по будням или скажем интенсивность отопления должна зависеть от температуры за окном а не от календарного времени года: вспомним хотя бы минувшую зиму когда в январе была плюсовая температура а отопление по интенсивности было “зимним†приходилось открывать окна в зданиях а можно было всего лишь снизить мощность обогрева тем самым сэкономить значительные средства. Возможные колебания...
38439. Синтез системы управления спуском космического аппарата на поверхность Марса методом интеллектуальной эволюции 1.52 MB
  Преодолеть указанные ограничения в данной работе предлагается путем ухода от построения оптимального управления как функции времени, так как оно не учитывает поведения системы уже в процессе функционирования и влияния этого поведения на дальнейшее состояние всей системы.
38440. Информационной безопасности облачных сервисов на базе мобильных облачных вычислений с использованием метода PP-CP-ABE 2.51 MB
  Целью данной работы является анализ существующих методов информационной безопасности и выбор соответствующего метода который должен подходить под соответствующие требования: Обеспечение надёжного шифрования данных при передаче их от пользователя к провайдеру услуг по хранению данных Минимизация нагрузки на облачные сервисы Возможность применения метода для лёгких мобильных устройств. Эффективные и безопасные операции по хранению данных для мобильного облачного вычисления. Параметры для хранения данных....
38441. Многокритериальный синтез позиционного управления с моделью 6-го порядка на основе метода формирования притягивающих многообразий 4.39 MB
  Можно выделить три типовых подхода в которых сгруппирован ряд известных методов. Это, так называемые, прямые интерактивные методы, например, на основе конусов доминирования и генетического программирования; методы скаляризации, такие как, свертка показателей, пороговая и лексикографическая оптимизация
38442. Исследование экономических показателей предприятия при помощи систем СТЭК 2.3 MB
  Исходные данные для среднестатистического предприятия олигополии В работе имеют место следующие исходные данные: годовая характеристика спроса на товар определяемая бюджетными ограничениями потребителей их предпочтениями и эластичностью вычислить по предложенной методике на базе Const=40 млн. год; доля капитала уплачиваемая за аренду оборудования = 150 год; показатели технологического процесса фирм ; ; планируемые производственные затраты фирм млн. допустимые значения ресурсов труда и капитала: чел; млн. 1 2 3 СТЭК 1 7 1...
38443. Разработка и исследование метода грамматической эволюции для структурно-параметрического синтеза системы управления динамическим объектом 1.63 MB
  Цель синтеза управления заключается в том, чтобы найти такое управление, при котором поведение объекта управления удовлетворяло бы заданным критериям. Данная задача до сих пор не решена аналитически в общем виде.
38444. Разработка и исследование метода сетевого оператора для логического вывода экспертной системы 1.29 MB
  Экспертные системы обычно определяют как программы ЭВМ, моделирующие действия эксперта-человека при решении задач в узкой предметной области на основе накопленных знаний, составляющих базу знаний. ЭС выдают советы, проводят анализ, дают консультации, выполняют классификацию и т.д. Практическое применение ЭС на предприятиях способствует значительному увеличению эффективности работы.
38445. Расчёт плиты опертой по контуру 210.72 KB
  22:2006 для торгових приміщень 15 12 18 Всего p=15 p=18 Полная Всего gp=8219 gp=9313 Поле плиты в осях 15АД: Нагрузка приходящая на всё поле плиты: Максимальные изгибающие моменты на полосе шириной 1м: для пролётных моментов: для опорных моментов: де табличные коэффициенты для опирания плиты. Для пролетных моментов: Для опорных моментов: Определяем пролетную арматуру в направлении lк: Rs = 355 МПа расчетное сопротивление арматуры растяжению для...