Лекции по "Информационной безопасности"

Полем называется множество F с двумя отображениями (операциями), каждая из которых сопоставляет любой паре элементов из F однозначно определенный третий элемент из F, и эти отображения (+, ´) удовлетворяют девяти аксиомам, рассмотренным выше.

Для криптографии особенно важными являются конечные поля, поле же множества действительных чисел бесконечно.

Сконструируем конечное поле. Пусть Р – простое  число. Рассмотрим множество чисел: {0, 1, 2, ... P-1}. На этом поле применимы операции + и ´ по модулю Р.

Функция Эйлера j(n) – количество неотрицательных целых чисел, меньших n и взаимно простых с n [n=15   1,2,3,4,5,6,7,8,9,10,11,12,13,14  /8: j(15)=8.

15=3×5   j(15)=15×(1- )×(1- )   j(n)=n×(1- )×(1- )...]

Теорема Ферма:

Пусть р – простое число, а а– число взаимно простое с р, тогда а^р-1º1 mod p

Теорема Эйлера: Пусть a и n – взаимно простые числа, тогда а^j(n)º1 mod n 

Ассиметричные криптосистемы

Система RSA.

Получатель  вычисляет следующие величины:

p и q – два больших простых числа, которые держатся в секрете, Е – случайное целое число. n=p×q – открытое число. Это помещается в справочник для переписки. Е также помещается в открытый каталог и используется для шифрования сообщений. Е обладает одним свойством: НОД(Е,j(n))=1.

D – тайное число. Целое, используемое получателем для дешифровки. D выбирается как мультипликативное обратного числа E по модулю j(n): (D×E)modj(n)=1.

Эта мультипликативная  обратная существует, когда:

Теорема: Пусть А принадлежит множеству Z_m (целые), тогда А имеет мультипликативный обратный по модулю n элемент в том и только том случае, когда НОД (gcd) a и n =1.

Итак, М  – сообщение; n и Е – открытый ключ шифрования; p, q и D – секретные ключи дешифровки.

Отправитель знает М и каждый желающий знает  открытый ключ n и Е.

Сообщение М преобразуется в цифровую форму. Если число n достаточно большое, то шифровать можно целыми строками (n–1>M). Длинное сообщение разбивается на блоки, и длина блока такова, что его числовое значение не превосходит n. Отправитель берет каждый блок в сообщении М_i (каждый блок – некоторое большое число) и шифрует следующим образом: . Это попадает в канал связи. Получатель, получивший сообщение C_i вычисляет

, так как .

Если  шифровать по одной букве, то частотность  букв сохраняется, поэтому сообщение  шифруется блоками, для этого  p и q должны быть достаточно большими. D и Е не имеет смысла брать большими, поскольку они не влияют на дешифровку. 

Идеи  цифровой подписи

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

Отправитель: Е_А, D_А, n_А, p_Аq_А

Получатель: Е_В, D_В, n_В, p_Вq_В

Сообщение М, к нему применяется D_А, D_А(М) – это шифруем Е_В(D_А(М)) и это отправляется.

Получатель  своим тайным шифром дешиврует и  получает D_В(Е_В(D_А(М)))=D_А(М), понимает, от кого это сообщение, применяет Е_А. Если получается нормальное сообщение М, значит сообщение действительно зашифровал именно тот отправитель.