shpori (1) / shpori (1)

34 Криптосистема с открытым ключом. Криптосистема rsa

В криптосистемах с открытым ключом Алиса и Боб имеют по 2 ключа – открытому и секретному(открытый ключи лежат в каталоге общего пользования)

Пусть PA и SA – открытый и секретный ключи Алисы, Пусть PB и SB – открытый и секретный ключи Боба, Пусть W – множество всех возможных сообщений ,Ключи PA и SA определяют отображения F_PA, F_SA: W®W.

Сообщение, зашифрованное с помощью PA, можно расшифровать с помощью SA и наоборот.

M = F_PA(F_SA(M)); M = F_SA(F_PA(M)). Т.е. F_PA = F_SA^-1

Ключ PA знают все – все могут вычислить F_PA

Идея: нужно задать такой ключ SA и функцию F_SA,чтобы никто, кроме Алисы, не мог вычислить F_SA за приемлемое время

Криптосистема RSA

f(n) – функция Эйлера. f(n) = |{m : m<n, (m,n)=1}|

Теорема f(n) = n

Z_n – кольцо вычетов по модулю n

Китайская теорема об остатках

Пусть n₁,…,n_k – попарно взаимно простые числа, n=n₁n₂…n_k

Т-ма чисел r₁,…..,r_kчисло xZ_n ,что x r_i(mod n_i)

Следствие Пусть p и q – простые числа n = pq , x ,y N Тогда xy(mod p) и x y (mod q), то xy(mod n)

Теорема Лагранжа. Пусть G – конечная мультипликативная группа с единицей e, |G|=n.Тогда aⁿ=e для любого aÎG.

Следствие (теорема Ферма). Пусть p – простое число. Тогда a^p^-1º1 (mod p) для любого а<p

Криптосистема RSA

1.Выбираем два больших числа p и q

2.Вычисляем n = pq f(n) = (p-1)(q-1)

3.Выбираем достаточно маленькое число e, взаимно простое с f(n)

4.Вычисляем число d такое, что de º 1 (mod f(n) ). Можно доказать, что такое d всегда существует и единственно.

5.Пара (e,n) будет открытым ключом PA, а Пара (d,n) – секретным ключом SA

В качестве множества W всех возможных сообщений будем использовать множество Z_n (например, битовую запись сообщения будем понимать как двоичную запись какого-то числа)

F_PA(M) := M^e (mod n) F_SA(M) := M^d (mod n)

Теорема. F_PA(M) и F_SA(M) – взаимно обратные отображения множества Z_n

Сертификаты

Боб – пользователь сайта, Алиса – сайт, Как Боб может быть уверен, что может доверять открытому ключу Алисы и что это вообще ключ Алисы? Пусть имеется авторитетный пользователь T,ключ которого широко известен, Ключ Алисы подтверждается сертификатом– цифровой подписью T

Чтобы взломать систему RSA, надо разложить число n на простые множители, получить таким образом p и q и c их помощью найти секретный ключ (d,n) Это невозможно сделать за адекватное время на любом существующем компьютере!

Содержание