Криптография, 06 лекция (от 05 октября)

Материал из eSyr's wiki.

Криптография с открытым ключом

Сегодня мы с вами немножко познакомимся с криптографией с открытым ключом и немножко про RSA.

В следующий раз продложим про RSA и рассморим другие криптосистемы с открытым ключом.

Криптграфия как наука началась где-то в 50 годах 20 столетия с работ Шеннона. Тогда это все динамически развивалось, параллельно с компьютерными технологиями.

Все вы слышали про арпанет. После его сохдания возникла задача -- как передавать на расстояние зашифрованные сообщения и каким образом вырабатывать ключи. Вы знаете что для криптосистем с закрытым ключом ключи для шифрования и расшифрования либо одинаковые, либо легко получаются друг из друга.

Если есть 100 абонентов, как их снабдить ключами? Эта проблема занимала многие умы. Первые решения были придуманы Меркелем. Он первый предложил схему распрделения ключей на расстояния -- головоломки Меркеля.

Схема была нежизнеспособной, в частности потому что Меркель не смог посмотреть на лсожностьалгоритмоы чуть более широким взглядом. Альтернативу предложили Хеллман И Диффи. С этих людей началась новая история криптографии.

Любая система с открытым ключом основывается на таком интересном объекте, как односторонняя фукция. Придумана она была задолго до Диффи и Хеллмана. Она обладает двумя свойствами -- значение в любой точке легко вычислить, но если дано значение то найти точку сложно.

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

Ящик с врезным замком -- крипторгафия с закрытым ключом.

Диффи с Хеллманом придумали добавить в оддностоннюю функцию параметр К, секрет. Односторонняя функция с секретом легко вычислима при известном К. Если к не знаете, то она будет сложно обратима. Если знаете, то легко.

Это еще более сложный объект. Доказано, что существует что-либо одно из этого, то существует и другое.

Как можно с помощью односторнней функции построить криптосистему с открытым ключом?

Представьте себе, что каждые может зашифровать, но расшифровать может только тот, кто знает ключ.

В криптосистеме с открытым ключом есть три функции.

1. генерация ключей
2. шифрование
3. расшифрование

предположим мы хотим передать зашифрованное сообщение.

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

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

На тот момент -- 1976 модель была революционной. Работы была на уровне концепции, как воплощать в жизнь было непонятно.

Шифрование осуществляется с помощью открытого ключа, а расшифрование с помощью секретного. Зная мой открытый ключ вы теоретически не должны иметь возможности восстановить мой секретный. Криптосистему с открытым ключом часто называют ассиметричными, а криптосистемы с закрытым ключом -- симметричными.

Если представлять себе криптосистему с секретынм ключом как ящик с замком, то моделирование системы с закрытым ключом сделать очень просто. Вы делаете копию ключа, даете мне, и дальше посылаете сообщение в закрытом ящике.

В крипторгафии с открытым ключом ам встречаться не надо. покупаем навесной замок, ключ вы оставляете себе, замок оставляете в хранилище. Когда мне надо отправить сообщение, покупаю ящик с ушками, беру замок и закрываю в ящике сообщение.

Эта модель хорошо иллюстрирует область применения. Что сложнее вскрыть -- навесной замок или врезной? Врезной. Так же и системы с закрытым ключом считаются более обоснованно надежными.

В 1978 году группа израильских математиков придумала реализацию концепции Диффи-Хеллмана в реальной жизни. Традиционно считается, что криптосистема RSA является первой. Вообще говоря это не так, в 1978 было создано 4 криптосистемы, то 3 из них в закрытом американском учереждении. А RSA была создана гражданскими лицами и первая опубликована. Тогда же была создана криптосистемы МакЭлиса и Рабина.

RSA настолько распространена, что используется сейчас очень часто. Если вы зайдете на страницу гугла по протоколу хттпс и посмотрите чем шифруется ваше соединение, вы увидеите, что алгоритме подписи есть три заветные буквы.

Открытый ключ RSA тоже виден в сертификате, и его длина 1024 бита. Позже пооворим о длинах ключей и прочем.

Создателями RSA были три человека -- Рон Ривест, Ади Шамир, Лео Адлеман.

Люди известные, у них много заслуг в математике. Лео Адлеман и вовсе занимается биоинформатикой. Входил в группу ученых, создававших алгоритмы записи днк.

Шамир занимается теорией информации.

Дадим вкратце описание криптосистемы RSA.

Она основывается на теории чисел. И односторонней функции является функция возведения в степень. В обыной математике эти функции являются очень простыми. Но как только вы переносите их в дискретные пространства, у вас возникают большие проблемы.

Что надо делать в RSA?

1. Абонент выбирает два больших простых числа. Вычисляем произведение N = p*q;
2. Вычслить функцию  \phi(N) = (p-1)(q-1) -- количество чисел взаимнопростых с данным.
3. Дальше находим число e, взаимнопростое в \phi(n)
4. Найти такое число d, которое было бы обратно e по модулю \phi(N)

Что у нас будет секретным ключом? Число d. А открытым -- число N и число e. Все остальные упомянутые числа после генерации ключа уничтожаются.

Как происходит шифрование?

Вы шифруете реальный текс, поэтому его надо закодировать. Число должно быть от 0 до N-1. Для шифрования надо возвести полученное число в степень e по модулю N.

Где та функция с секретом?

c = m^e mod N,  где m -- сообщение.

Секретом тут являются числа p и q.

Как расшифровать?

m = c^d mod N

Почему это так?

Если у вас числа d и e таковы что

d*e = 1 mod \phi(n)

то

m^ed = m mod N.

Называется теоремой Эйлера, или теорема о корректности функции расшифрования RSA.

Как ее доказать?

По определению

d*e = 1 + k(p-1)*(q-1).

m^{k(p-1)(q-1) + 1} 

и вспомним интересный результат из теории групп -- малую теорему ферма. Для любого простого p

m^{p-1} = 1 mod p. 

Это один из самых значимых результатов теории групп, теории конечных полей. То есть оказывается, если вы возведете любой м в степень п-1 где п простое, вы всегда получите 1 по модулю п. Тогда что мы имеем?

m^(p-1) = 1 mod p; m^(q-1) = 1 mod q;

Значит по отдельности по модулю п и ку у нас получается. Теперь надо доказать, что верно и по модулю произведения. Здесь надо вспомнить великую китайскую теорему об остатках.

Она в частности говорит, что если какое то соотношение верно по частным модулям, то оно верно по произведению.

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

Рассмотрим все числа от 1 до какого-нибудь N-1. Можем на них ввести операции сложения и умножения по модулю N-1.

Оказывается, если N простое число, то эти числа можно выстроить в виде степеней одного из этих чисел.

Если N простое, то найдется 1<=a<=N-1, такое что все числа от 1 до N-1 могут быть представлены как a^1 ,,, a^{N-1}

Возьмем какое то число и начнем до опупения возводить в степень. Рано или поздно вы должны получить единицу, потому что множество конечное. Раз это так, то давайте найдем для все элементов множества минимальную соответствующуй степень, и из этих минимальных возьмем максимальную. r_min называется порядком элемента х. r_max == максимамальный порядок по всем элементам. Окажется, что этот порядок равен p-1. Это значит, что вы пройдете все элементы.

Из совокупности этих шаманских утверждений мы заключаем, что в криптосистеме RSA операции взамно обратные.

Всегда возникает вопрос, почему e*d = 1 mod \phi (N), хотя у нас все по модулю Н? А вот именно потому, что если брать по модулю Н, то преобразования не будут взаимно обратными.

Рассмотрим угрозы RSA.

Угрозы RSA

Какие угрозы были для дес? Либо прочитать сообщение, либо восстановить ключ. Как восстановить? Например с помощью частотного анализа. В криптоситеме с закрытым ключом криптографии инетересно только восстановить ключ.

В крипторграфии с открытым ключом интересно ивосстановить закрытый ключ, и текст.

Первая угроза -- угроза восстановления по крипторграмме открытого сообщения. c = m^e mod N известно все, кроме м, найти м. Если не знать разложения Н на множители, то это вычислительно сложная задача.

Что здесь доказано?

Все крутится вокруг п и ку, то есть вокруг факторизации. Известно, что все задачи факторизации своядтся к разложению на два множителя.

Известно, что решив проблему факторизации вы сможете сломать RSA, но алгоритм взлома у вас будет немножко вероятностным.

Известно так же, что взломав RSA вы не факт, что сможете решить проблему факторищации.

Это же значит, что теоретически вы можете решить RSA не решая проблему факторизации. И тут у вас очень зыбкая почва под ногами. Формального сведения даже к проблеме факториации нет. Правда сейчас имеются результаты на уровне идей, что проблема RSA не сложная, а простая. Но эффективных алгоритмов факторизации пока не построено.

Как вы думаете, сложно определить является ли число простым? Не далее как в 2001 году группа индусских уеных предложила полиномиальный алгоритм проверки простоты.

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

Но индусские математики предожили алгоритм без предположения о верности гипотезы Римана.

Мы тут говорили, что числа п и ку должны быть уничтожены. А почму нужно уничтожать фи он н? Оказалось, что знание функции эйлера эквивалентно знанию эффективного алгоритма разложения исла на множителия.

\phi(n) = N + 1 - ( p+q) -- линейное кравнение на п и ку.

Добавим уравнение

(p-q)^2 = (P+q)^2 - 4N.

Получим систему линейных уравнений.

Проблема факторизации полностью эквивалента восстановлению секретного ключа RSA.

Расширенный алгоритм Евклида

640/21 = 30 + 10/21 = 30 + 1/(21/10)

21/10 = 2 + 1/10

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

Это называется разложение дроби в цепные дроби.

Цепную дробья для числа е можно описать детерминированным алгоритмом, а вот для числа пи -- невохможно.

составляем табличку

  30 2 10
0 1

Дальше будем заполнять табличку так

   30 2  10
0 1 30 61 640

Предпоследний стоблец, число 61 -- и будет решением лиофантовго уравнения, только осталось определиться со знаком.

Если столбей четный, то знак плюс, если нечетный, то минус. (То есть н минус число).

Того решение 61.

Итого мы быстро нашли число d с помщью расширенного алогритма евклида.

Итого, открытым ключом будет 697 и 21.

а открытым 61.

Чтобы реально что-то зашифровавать закодируем буквы русского алфаыита закодируем строчками из 5 бит.

Зашифруем слово ОЙ

0111001001 = 457

Теперь наша задача -- зашифровать 457.

457^{21}mod 697

как?

21 = 16 + 4 + 1 = 2^4 + 2^2 + 1

457^21 = 457* (457)^2^{2^2+1} mod 697 = 457 * 446^2^{2^2 + 1} mod 697 = 457 * 271^2^2 * 271 mod 697 = 457 * 256^2 * 271 mod 697 = 457 * 18 * 271 mod 697 = 240 mod 697