Требование к выбору параметров rsa:

1. Простое числа должны быть большие.

2. Разность |p-q| также должна быть большою.

3. Числа p+-1, q+-1 должны содержать большой простой множитель.

4. (p-1,q-1)общий делитель должен быть не большим.

5. Нельзя выбрать ключи e и d с короткой секретной экспонентой, нужно придерживать нормального случаю.

Безопасность метода RSA. Безопасность завит от проблемы разложение больших чисел на множители. Математически некогда не догадывалось что нужно Nразложить на множители что бы восстановить сообщение по y ключу E . Для крипто анализа R1SA может применён другой способ, позволит получить D его также можно применить для разложение больших чисел на множители. Шифр можно также вскрыть угадав значение произведение (p-1) (q-1) такое вскрытие не проще чем разложение числа N. Большинство общих принятых алгоритмов вычисление простых p,q носят вероятностный характер. Вероятность то что p,qбудут составные, такое событие можно примести к минимум, и если такое событие будет т его можно будет обнаружить .Cущественным недостатком асимметрически методам шифрование является их сложность, а следовательно низкое быстродействие. По этому такие методы основанные на RSA используются в сочетании с симметричными. Асимметричные методы работают на 3-4 порядка медленней чем симметричные. Как принцип шифровании так и при расшифрованные алгоритмы состоит из операции возведение в степень которая выполняться последовательный ряд умножение. В практический приложений для открытого ключа обычно выбирается относительно не большой показатель и часто целые группы пользователь имеют один и тот же показатель . но каждый с различным модулем. Если открытый показатель не изменений то вводиться некоторые ограничение на главные делители модуля(факторами), при этом формование данных происходит быстрей чем расшифрованные. Если в шифруемого модуля k-бит то а алгоритмах RSA обычно количество шагов необходимой для операций открытым кличем k2. Кол-во шагов для операций секретного ключа пропорционально к3Для создание ключей в k4. Методы быстрого умножение(основанные на методе Курэ). Алгоритм RSA намного медленней чем алгоритм DESи другие алгоритмы блочного шифрование. Программная реализации DES работает в 100 быстрей. Возможные атаки на систему RSA. Для взлома необходимо по известным водным величинам N,Eи зашифрованному сообщению необходимо найти такое значение x є (Z/(N)) y=xe(mod N). Наиболее распространённый вид атаки повторённое шифрование.

Лекция 10 Вычисление ключей

Выбор р.д. ключей должны быть простыми. Вычисление n=pq

Вычисление ф(n) =(р-1)(q-1). Выбор целого e ed(ф(n),e)=1 1<e<ф(n)

Вычисление d=e-1mod ф(n). Открытый ключ КU={e,n}

Личный ключ KR={d,n}

Сравнительные характеристик традиционгго шифрованлього и шифрование с открытом ключем

Что необходимо
Тр.	О.К.
Один алгоритм с одним и тем же ключом служит для шифрование и для расшифрованные	Для расшифрованные и расшифрованные используется одни алгоритм, но 2 ключа.
Отправитель и получатель должны использовать одинаковый алгоритм и ключ	Отправитель и получатель должны иметь по одному из пары соответствующих друг другу ключей
Необходимо для защиты
Ключ должен сохраняться в секрете	Один из ключей должен сохраняться в секрете
Должно быть невозможно или практически невозможно было расшифровать сообщение при отсутствии дополнительной информации	Должно быть невозможно или практически невозможно расшифровать сообщение отсутствии необходимой информации
Знание Алгоритма и наличная образцов шифрованного текста должно и наличия образцов шифрованного текста должно быть недостаточно для восстановление ключа	Знание алгоритма и одного ключа из ключей и образцов шифровано текста должно быть недостаточно что бы восстановить другой ключ

При рассмотрении сложности RSA: сложность шифрование дешифрование, сложность вычислений ключей используемый, для шифровании и дешифровании. Если возведение в степень выполнять непосредственно с целыми числа, а затем проводит равнение по модулю N то промежуточные при это значении могут оказаться огромные величины. Для того что бы немного упростить. [(a modn)*(b modn)]=mod n=(a*b)mod n Эта запись позволяет промежуточные вычислении уже брать по модулю. В этом случае становиться практически реализуемые.

Эффективная реализация операции возведение в степень . Сгруппировать данные. Необходимом найти am, где a,m положительные числа. Если число b приставить в 2 коде bnbn-1…..b1b0 m=ZZ 2i am=a ZZ 2i= Пa(2i). ammod n =[Па(2i)] mod n= Пbi<>o[a(2i)mod n].

Вычисление ключей прежде чем использовать алгоритм с открытым ключом у каждой стороны должна быть возможность сгенерировать пару ключей. Определение 2 простых числе p,q вычисление и выбор одного из числе e,d и вычисление другого. Так как e,qбуте известная то что бы не позволит с помощью простого перебора вариантов эти простые числа должны быть выбранные из достаточно большого множителя. Метод нахождения больших числе должен быть практически эффективным на практике. Настоящие время нет хороших методов вычисляй произвольно больших простых чисел, и для их определения прибегают ктаким хитростями. Чаше всего процедура заключается в выборе случайного нечетного числа приблизительно желаемой и выясняется является оно простым, если оно не является простым то выбирается следующее пока не будут простым. Для проверки того что числа простые существует ряд тестов. Практически все носят вероятностей характер. В результата в таком тесте признает но вероятно что оно является простым, достоверность то что оно простое близкая к 1. Одним из наиболее популярным алгоритм Миллера Рабина. проверка простоты числа n заключается в выполнении ряда вычислений в которых используется само nи некоторое выбранен число а. Если nне выдерживает тестирование то оно не является простым, если N выдерживает одно тестирование то оно может оказаться простыми или нет. Если значение n проходит целый ряд с различными выбранными числами aто это дает наиболее простым.

Процедура выбора простого числа:

1. Выбрать нечетное целое число некоторым случайным образом.

2. Выбирается целое число меньше чем n случайным образом .

3. Выполняется вероятностный тест на простоту, если число не выдерживает тест на простоту, если n выдерживает то это значение n выбирается .

4. Если N проходит испытание, то возвращаемся к пункту 2. Если же число N выдерживает ряд испытаний, то оно подходит на роль целого и простого.

Лекция 11

При этом полезно знать, как много чисел окажутся отброшенными прежде чем будет найдено нужное просто число.

Простые числа около некоторого числа N распределяются в среднем по одному на каждые lnN целых чисел. В среднем придётся протестировать порядка lnNцелых чисел прежде, чем найдётся одно простое число.

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

После определения простых чисел p и q процесс вычисления ключей завершается выбором значения е и вычислением d или наоборот.