Шифрование с использованием алгоритма RSA

Задача, положенная в основу метода состоит в том, чтобы найти такую функцию y=f(x), чтобы получение обратной функции x=f-1(y), было бы в общем случае очень сложной задачей (NP-полной задачей), однако, если знать некую секретную информацию, то сделать это существенно проще. Такие функции также называют односторонними функциями с лазейкой или потайным ходом. Например, получить произведение двух чисел n=p*q просто, а разложить n на множители, если p и q достаточно большие простые числа, сложно.

1. Первым шагом в использовании алгоритма RSA является генерация ключей. Для этого нужно:

2. Выбрать два очень больших простых числа p и q.

3. Вычислить произведение n= p*q.

4. Выбрать большое случайное число d, не имеющее общих сомножителей с числом (p-1)*(q-1).

5. Определить число e, чтобы выполнялось (e*d) mod ((p-1)*(q-1))=1.

Тогда открытым ключом будут числа e и n, а секретным ключом - числа d и n.

Теперь, чтобы зашифровать данные по известному ключу {e,n}, необходимо сделать следующее:

· Разбить шифруемый текст на блоки, где i-й блок может быть представлен в виде числа m(i)=0,1,2..., n-1. Их должно быть не более n-1.

· Зашифровать текст, рассматриваемый как последовательность чисел m(i) по формуле c(i)=(m(i)e)mod n.

Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо вычислить: m(i) = (c(i)d) mod n. В результате будет получено множество чисел m(i), которые представляют собой часть исходного текста.

Например, зашифруем и расшифруем сообщение AБВ, которое представим, как последовательность чисел 123 (в диапазоне 0-32)

· Выбираем p=5 и q=11 (числа на самом деле должны быть большими).

· Находим n=5*11=55

· Определяем (p-1)*(q-1) = 40. Тогда d будет равно, например 7.

· Выберем e, исходя из (e*7) mod 40=1. Например, e=3.

Теперь зашифруем сообщение, используя открытый ключ {3,55}

· C1 = (13)mod 55 = 1

· C2 = (23)mod 55 = 8

· C3 = (33)mod 55 = 27

Теперь расшифруем эти данные, используя закрытый ключ {7,55}.

· M1 = (17)mod 55 = 1

· M2 = (87)mod 55 = 2097152mod 55 = 2

· M3 = (277)mod 55 = 10460353203 mod 55 = 3

Таким образом, все, данные расшифрованы.

Задача

Компьютер, чьи процессы имеют 1024 страницы в своем адресном пространстве, хранит таблицы страниц в памяти. На чтение слова из таблицы страниц требуется 5 нс. Чтобы уменьшить затраты, в компьютере существует буфер быстрого преобразования адреса (TLB), содержащий 32 пары (виртуальная страница – физический страничный блок), который может выполнять поиск за 1 нс. При какой частоте обращений к памяти, успешно реализуемых в TLB, средние затраты будут ниже 2 нс?

Время поиска: 1 в случае успеха, 5+1 в случае, если записи нет.

Среднее время: P*1+(1-p)*(1+5)=6-5*p<2 => 1>p>0,8