§ 2. Асимметричные криптосистемы.
При использовании симметричных криптосистем возникает проблема распределения ключей: ключ должен быть сгенерирован отправителем сообщения, а затем в секретном порядке передан получателю.
Это проблема не возникает при использовании асимметричных криптосистем (систем с открытым ключом).
В асимметричных криптосистемах используются два ключа (открытый и закрытый ) математически связанные друг с другом.
Шифрование производится с помощью открытого ключа доступного всем желающим отправителям.
Дешифровка осуществляются с помощью закрытого ключа известного только получателю сообщения.
Для установления связи между открытым и закрытым ключом используются односторонние функции, такие что для любого xDom f легко вычислить y = f(x) ,но при известном y трудно или практически невозможно вычислить x = f -1(y) на современном уровне развития вычислительной техники за обозримый промежуток времени.
Современные асимметричные криптосистемы используют следующие типы односторонних преобразований:
-разложение больших чисел на простые множители;
-вычисление логарифма в конечном поле;
-вычисление корней алгебраических уравнений.
Направления использования асимметричных криптосистем:
-как самостоятельное средство защиты для шифрования сообщений.
-как средство для распределения ключей, т.е. для шифрования ключей объём которых незначителен. После передачи ключа для шифрования большого объёма информации применяется симметричная криптосистема.
-как средства аутентификации пользователя (электронная подпись).
§ 17 Криптографическая система rsa.
Разработана в 1997 году, получила название в честь создателей : Рон Ривест ( Ron Rivest ), Ади Шамир (Adi Shamir), Леонард Эдлеман (Leonard Adleman).
Используется тот факт , что
1) нахождение больших простых чисел и их произведений производится легко в вычислительном отношении.
2) разложение на множители произведения двух больших простых чисел практически невыполнимо в общем случае.
Доказано, что раскрытие шифра RSA эквивалентно такому разложению. Это даёт возможность математически оценить криптостойкость системы RSA с учётом производительности современных компьютеров.
Необходимые сведения из теории чисел.
Все числа – целые, m>1.
Определение 1. Говорят, что a≡b(mod m) если (a-b) кратно m, т.е. a-b=mk, kℤ.
Теорема 1.(критерий сравнимости) a≡b(mod m) а и b имеют одинаковые остатки при делении на m.
Определение 2. Операция взятия остатка b при делении a на m:
a mod m=b a≡b(mod m) и 0 ≤ b <m.
Определение 3. Класс вычетов по модулю m c представителем а: ={xZ| x≡a(mod m)}, при этом для любого b: =.
Множество всех классов вычетов по модулю m обозначается =. На ℤm задаются операции сложения и умножения классов вычетов по правилам: +=·=.
Множество всех классов вычетов, взаимно простых с m: ℤm*={ℤm|(a, m)=1}. ℤm*- коммутативная группа относительно “·”, в частности, для любого элемента существует-1 такой, что -1=.
Определение 4. Функция Эйлера φ(n) для любого n∈ℕ определяет количество натуральных чисел, взаимно простых с n и не превосходящих n.
Теорема 2.(вычисление функции Эйлера) Если n=– каноническое разложениеn, то
φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pk).
Теорема 3. (Ферма) Если p – простое число, то ℤp*(т.е при (a, p)=1) выполняется a φ(p)=a p-1≡1(mod p).
Теорема 4. (следствие из “китайской теоремы об остатках”)Если n1, n2,… ,nk – попарно взаимно простые числа aℤ, xℤ, то
x≡a(mod n1n2…nk ) x≡a(mod ni ), i=1,2,..k.