АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Создание ключей

Читайте также:
  1. Алгоритм открытого распределения ключей Диффи - Хеллмана.
  2. Алгоритм создания открытого и секретного ключей
  3. Внешняя политика в царствование Александра III, создание франко-русского союза
  4. Вопрос 20. Создание специальных образовательных учреждений в дореволюционной России
  5. Г. ноябрь Создание партии «Союз 17 октября».
  6. Генерация ключей
  7. Глава VIII. СОЗДАНИЕ ИМИДЖА
  8. ГОСУДАРСТВЕННОЕ СТРОИТЕЛЬСТВО В РОССИИ.СОЗДАНИЕ СССР
  9. Екатерина Великая и Потемкин в истории Украины-Руси. Создание Новороссии и укрепление Малороссии
  10. Жизнь и церковная деятельность святого Саввы Сербского. Создание автокефальной Сербской Церкви. Провозглашение Сербского патриаршества.
  11. Завершающий этап формирования ЕВС. Создание евро
  12. ЗАДАНИЕ 11. Создание графических изображений

Создание ключей включает следующие задачи:

  1. Определить два простых числа р и q.
  2. Выбрать е и вычислить d.

Прежде всего, рассмотрим проблемы, связанные с выбором р и q. Так как значение n = p · q будет известно любому потенциальному противнику, для предотвращения раскрытия р и q эти простые числа должны быть выбраныиз достаточно большого множества, т.е. р и q должны быть большими числами. С другой стороны, метод, используемый для поиска большого простого числа, должен быть достаточно эффективным.

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

Были разработаны различные тесты для определения того, является ли число простым. Это тесты вероятностные, то есть тест показывает, что данное число вероятно является простым. Несмотря на это они могут выполняться таким образом, что сделают вероятность близкой к 1. Если n "проваливает" тест, то оно не является простым. Если n "пропускает" тест, то n может как быть, так и не быть простым. Если n пропускает много таких тестов, то можно с высокой степенью достоверности сказать, что n является простым. Это достаточно долгая процедура, но она выполняется относительно редко: только при создании новой пары (KU, KR).

На сложность вычислений также влияет то, какое количество чисел будет отвергнуто перед тем, как будет найдено простое число. Результат из теории чисел, известный как теорема простого числа, говорит, что простых чисел, расположенных около n в среднем одно на каждые ln (n) чисел. Таким образом, в среднем требуется проверить последовательность из ln (n) целых, прежде чем будет найдено простое число. Так как все четные числа могут быть отвергнуты без проверки, то требуется выполнить приблизительно ln (n)/2 проверок. Например, если простое число ищется в диапазоне величин 2200, то необходимо выполнить около ln (2200) / 2 = 70 проверок.

Выбрав простые числа р и q, далее следует выбрать значение е так, чтобы gcd(Φ(n), e) = 1 и вычислить значение d, d = e-1 mod Φ(n). Cуществует единственный алгоритм, называемый расширенным алгоритмом Евклида, который за фиксированное время вычисляет наибольший общий делитель двух целых и если этот общий делитель равен единице, определяет инверсное значение одного по модулю другого. Таким образом, процедура состоит в генерации серии случайных чисел и проверке каждого относительно Φ(n) до тех пор, пока не будет найдено число, взаимнопростое с Φ(n). Возникает вопрос, как много случайных чисел придется проверить до тех пор, пока не найдется нужное число, которое будет взаимнопростым с Φ(n). Результаты показывают, что вероятность того, что два случайных числа являются взаимнопростыми, равна 0.6.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)