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

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

 


 

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

46409. Доказательство и доказывание в гражданском процессе 118.5 KB
  Представители по гражданскому делу, или защитники по уголовному делу, делу об административном правонарушении, или медиаторы - об обстоятельствах, которые стали им известны в связи с исполнением обязанностей представителя, защитника или медиатора...
46410. Розмір речення та ідіостиль 36.21 KB
  Підготувала студентка 2го курсу ФІФ Група 2338 н Бреніч Наталія Розмір речення та ідіостиль Ця доповідь присвячена висвітленню теми Розмір речення та ідіостиль Поліни Ігорівни Климової. Обьектом статті є речення в свою чергу предметом є розмір речення та поняття іліостиль. Адмоні даючи детальну характеристику особливостям побудови речення в творах цього письменника наголошував на тому що у фразі Томаса Манна наявний процес пошуку істини це проявляється. Цією статтею робимо спробу дослідити недостатньо вивчений аспект ідіостиля...
46411. Аналіз умов та факторів виходу на зовнішній ринок українських літакобудівних підприємств 1.41 MB
  Цю стратегію переважно використовують невеликі авіакомпанії які мають невеликий парк літаків або взагалі орендують літаки. Але частка нових літаків в повітряному парку світу залишилась нижче рекордних показників зафіксованих в 1991 та 1999 роках. Прогноз оновлення парку літаків у світі Підтримка промисловості здійснюється урядами в різних формах: від істотної суттєвої частки долі у фінансуванні наукових досліджень до прямого субсидування виробництва і державного страхування експорту. На сьогоднішній день Boeing та irbus постачають на...
46412. Статус Рахункової Палати в Україні: українське законодавство, зарубіжний досвід та шляхи удосконалення 254 KB
  Нижче розглянуто основні віхи становлення Рахункової палати як органу фінансового контролю її завдання повноваження та проблеми діяльності на сучасному етапі зарубіжний досвід правового регулювання статусу аналогічних органів в окремих зарубіжних державах. На основі проведеного дослідження розроблено пропозиції щодо можливих шляхів удосконалення правового регулювання діяльності Рахункової палати в Україні. Денис КОВРИЖЕНКОексперт Лабораторії законодавчих ініціатив Основні етапи інституціоналізації Рахункової палати У 1992 році з ініціативи...
46413. Педагогічні особливості культури офіцера. Військово-педагогічні процеси 112 KB
  Сформувати у курсантів навички пошуку узагальнення критичного аналізу навча1льного матеріалу вміння висувати і захищати свої погляди з питань що розглядаються; Формувати у курсантів риси необхідні військовому керівнику для професійної діяльності; Формувати світогляд курсантів спираючись на національні історичні та військовопатріотичні традиції загальнолюдські цінності; Сприяти розвитку у курсантів почуття свідомої військової дисципліни відповідальності і цілеспрямованості.
46416. Надійність машин і устаткування 1.13 MB
  Причини утворення і розвитку несправностей деталей машин Практично будьяка несправність є наслідком зміни механічних властивостей матеріалу конструктивних розмірів деталей і стану їхньої поверхні. У свою чергу зміна механічних властивостей відбувається внаслідок зміни складу і структури матеріалу деталей. До конструктивних факторів відносяться фактори що були враховані на стадії проектування: конструктивне виконання деталей і складальних одиниць форма величина зазорів і натягів у спряженнях шорсткість і твердість поверхонь і т.;...
46417. Відновлення деталей типу вал(вісь) 264 KB
  Для відновлення нерухомих сполучень, широко розповсюджена елекроконтактне приварювання металевої стрічки (дроту). Перевага – незначний нагрів деталей, зменшення витрат наплавних матеріалів, значне підвищення продуктивності і умов праці.