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

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

 


 

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

53769. Баскетбол, конспект уроку для 8 класу 44 KB
  Ноги трохи зігнуті, лікоть руки опущений вниз, пальці рук супроводжають м’яч. Відстань між студентами 4 м. пальці рук розставлені. Ведення правою – лівою рукою. Відстань 4 м. Кидок виконується після ведення, кидок м’яча в ціль.
53770. Організовуючі вправи. Загальнопідготовчі вправи. Стрибки зі скакалкою 85 KB
  Стійка ноги 810 Руки розводити долонями нарізно руки за голову. разів догори прогинаючись у 1 поворот тулуба ліворуч попереку голову відводити руки в сторони вдих; 2 в. видих; 3 поворот тулуба праворуч руки в сторони вдих; 4 в. нарізно руки в сторони; разів Ноги поставити 1 нахил уперед руки якнайширше.
53771. Конспект уроку з фізичної культури Для учнів 2-А класу - реферат українською 29.5 KB
  Ходьба: руки за голову навприсядки стрибками на носках на п‘ятках4. Загальнорозвиваючі вправи на місціА Вп руки до плечейКолові рухи руками вперед назад 8р вперед8р назадБ Вп руки в сторониКолові рухи руками вперед назад 1012 раз Руки пряміВ Вп права рука вгорі ліва внизу; 12 переміна положень рук 1012 раз Руки пряміГ Вп руки вперед. Схрещення рук 1012 раз Руки пряміД Вп ноги нарізно руки на поясі 1 нахил вліво 2 – в. 1012 раз Руки опущені ноги пряміІІ.
53772. Організуючі, стройові та ЗРВ. Спеціальні бігові та стрибкові вправи. Рухливі ігри 75 KB
  Стройові вправи: Праворуч Ліворуч Кругом Ліворуч Ліворуч Рівняйсь струнко Ходьба: звичайна навшпиньках на п’ятках з високим підніманням стегна руки перед собою у напівприсіді у повному присіді звичайна. руки на пояс. руки до плечей колові оберти зігнутими в ліктях руками вперед назад. руки в сторони сжаті в кулачки на 123 – розвести руки в сторони на 4 – зігнути руки до...
53773. Ярослав Стельмах. «Митькозавр із Юрківки, або химера лісогвого озера». Характеристика образів Сергія і Митька, їхньої поведінки у складних ситуаціях 48.5 KB
  Мета: Удосконалювати навички визначення рис характеру героїв твору вміння висловлювати свої думки про прочитане; розвивати навички переказу виразного і вибіркового читання спостережливість увагу; виховувати допитливість доброту любов до ближніх. Обладнання: схема з рисами характеру героїв портрет Ярослава Стельмаха. Завдання: учні мають удосконалити навички визначати риси характеру героїв твору і оцінювати їхні вчинки; закріпити вміння переказувати твір віднаходити цитати за поданим завданням висловлювати своє враження про...
53774. Малювання композиції Дерева у лісі 656 KB
  Провести бесіду В художникаграфіка; розвивати умінняспостерігати і виявляти особливості будови дерев різних порід; ознайомити звиразними особливостями ліній різної товщини навчити прийомам роботи зпаличкою пензлем пером або восковими крейдами на вибір учителя ітушшю; формувати уміння заповнювати зображенням усю площину аркушапаперу; виховувати любов до рідної природи дбайливе ставлення до матеріалівта інструментів акуратність під час роботи з тушшю;...
53775. Дієслова майбутнього часу 65.5 KB
  Життя прожити не поле перейти Хочеш знати – не соромся питати Гарно того вчити – хто хоче все знати Щоб довго жити треба працю любити Знайдіть дієслова в неозначеній формі. Чи можна визначити за цими дієсловами коли відбулася дія і хто її виконує Чому Не можна бо неозначена форма дієслова не вказує ні на час ні на особу 2. Запитання вчителя : Що називається дієсловом Частина мови що означає дію предмета і відповідає на питання що робити Що робив Що зробив Що робить Що зробить Що буде робити Яким...