Лекция Криптосистемы с открытым ключем Лектор: профессор Яковлев В.А.

Хронология развития систем ЭЦП 1976 г. – открытие М. Хэлменом и У. Диффи асимметричных криптографических систем; 1978 г. – Р. Райвест, А. Шамир, Л. Адельман – предложили первую систему ЭЦП, основанную на задаче факторизации большого числа; 1985 г. – Эль Гамаль предложил систему ЭЦП, основанную на задаче логарифмирования в поле чисел из р элементов; 1991 г.- Международный стандарт ЭЦП ISO/IEC 9796 (вариант РША); 1994 г. – Стандарт США FIPS 186 (вариант подписи Эль Гамаля); 1994 г. – ГОСТ Р (вариант подписи Эль Гамаля); 2000 г. – Стандарт США FIPS 186 – 2; 2001 г. – ГОСТ Р (ЭЦП на основе математического аппарата эллиптических кривых).

Односторонняя функция Пусть X и Y дискретные множества. Функция y=f(x), где x X, y Y называется односторонней (однонаправленной), если y легко вычисляется по любому x, а обратная функция x=f -1 (y) является трудно вычислимой. Пример ОФ. y=a x (modp), где p- простое число, x - целое число, a -примитивный элемент поля Галуа GF(p). То есть a такое число, что все его степени a i (modp), i= 1,2…p-1, принимают все значения в множестве чисел от 1 до p-1.

Пример односторонней функции функции Пусть p=7, a=3. Проверим, что a примитивный элемент - a 1 =3(mod7), a 2 =2(mod7), a 3 =6(mod7), a 4 =4(mod7), a 5 =5(mod7), a 6 =1(mod7). Если x=4, то y=34(mod7)=4. Сложность нахождения функции возведения в степень N в =O(2logp). Обратная функция x=log a y (функция дискретного логарифмирования) трудно вычислима. Если p - сильно простое число, то N лог =O((p) 1/2 ).

Оценки сложности вычислений прямой и обратной функций Пусть 1000 разрядное двоичное число, тогда для решения задачи возведения в степень числа х по modp потребуется примерно 2000 = 2*10 3 операций, а для нахождения логарифма такого числа потребуется примерно p 1/2 =2 500 ~ операций, что вычислительно невозможно осуществить ни за какое реально обозримое время.

Односторонняя функция с потайным ходом Это не просто ОФ, обращение которой невозможно, она содержит потайной ход (trapdoor), который позволяет вычислять обратную функцию, если известен секретный параметр - ключ. y=f(x,s) – легковычислима; x=f -1 (y) – трудновычислима; x= f -1 (y,s)- легковычислима.

Общий принцип построения криптосиcтемы с открытым ключем А - генерирует пару ключей: SK(A) - секретный ключ, PK(A) - открытый ключ. B - генерирует пару ключей: SK(B) - секретный ключ, PK(B) - открытый ключ. Открытые ключи помещаются в общедоступную базу PK(A), PK(B) Шифрование. А выбирает открытый ключ PK(B) Осуществляет шифрование E A =f(M A,PK(B)) Расшифрование. M A =g(E A,SK(B)) EAEA PK(A) PK(B)

Требования к системам с открытым ключем 1. Вычисление пары ключей PK, SK должно быть просто решаемой задачей; 2. При известном ключе шифрования PK вычисление криптограммы E=f(M,PK) должно быть простым; 3. При известном ключе расшифрования SK восстанавливает сообщение M=g(E,SK) должно быть простым; 4. При известном ключе шифрования PK вычисление ключа расшифрования SK должно быть сложным; 5. При известном ключе шифрования PK, но неизвестном ключе расшифрования SK вычисление М по известной криптограмме E должно быть весьма сложным.

Система шифрования Эль-Гамаля Пусть p -простое число; a - примитивный элемент. Генерирование пары открытых ключей A - генерирует число x A, вычисляет открытый ключ y A =a x (modp). (SK= x A, PK= y A ). y A передается корр. B. Шифрование сообщения Пусть корр. B хочет послать корр.А сообщение m

Система шифрования Эль-Гамаля Расшифрование сообщения. Корр.А вычисляет c 1 x (modp) = a kx (modp), Затем находит c 2 a kx (modp)= m (y A -1 ) k a kx (modp)= m a -xk a kx (modp)=m Замечание. Как найти y A -1 ? y A p-2 (modp)= y A p-1 (modp) y A -1 (modp) = y A -1 (modp )

Стойкость системы Эль-Гамаля 1. Раскрытие секретного ключа эквивалентно решению задачи дискретного логарифмирования. 2. Нахождение m без знания ключа возможно, если случайное число k используется дважды и в одном случае нарушитель знает открытый текст c 2 = m (y A -1 ) k (modp), c 2 = m (y A -1 ) k (modp) Зная c 2, c 2 и m несложно найти m m= c 2 m c -1 2 (modp) k должно меняться случайным образом при шифровании нового сообщения.

Пример системы Эль-Гамаля p=11, a=4, a- примитивный элемент GF(2 p ) Пусть x=3 – закрытый ключ y=4 3 (mod11)=64(mod11)=9 открытый ключ y y Шифрование сообщения m=6 Генерирование СЧ k=4 Вычисление: С 1 =a k (modp)=4 4 (mod11)=256(mod11)=3 y -1 =y p-2 (modp)= 9 9 (mod11)= (mod11)= 4*4*4*4*9(mod11)=5*5*9(mod11)=5 C 2 =my -1k (modp)=6*5 4 (mod11)=6*3*3(mod11)=10 C 1,C 2 Расшифрование C 1 x (modp)=3 3 (mod11)=5 C 2 *C 1 x (modp)=10*5 (mod11)=50(mod11)=6

Система РША (1978г.) Генерирование ключей. Случайно выбираются два простых числа p и q. Находится модуль N=pq. Находится функция Эйлера (N)= (p-1)(q-1). Выбираем число e такое, что НОД(e, (N))=1. Находим d, как обратный элемент к e, de=1(mod (N)). Объявляем d=SK, (e,N)=PK. PK сообщается всем корреспондентам. Шифрование. Корр. А передает зашифрованное сообщение корр.В (использует открытый ключ корр. В) E=m e (modN) Расшифрование. Корр. В расшифровывает принятую криптограмму от корр.А,используя свой секретный ключ. m=E d (modN)

Доказательство обратимости операции дешифрования операции шифрования Покажем, что E d (modN) =(m e ) d (modN) =m По т. Эйлера m (N) 1(modN) для любого m взаимно простого с N. Умножая обе части сравнения на m, получаем сравнение m (N)+1 m(modN) справедливое уже для любого целого m. Перепишем соотношение ed 1(mod (N)) в виде ed=1+k (N) для некоторого целого k. Тогда E d =(m e ) d =m 1+k (N) = m 1+ (N) m (k-1) (N) = =m m (k-1) (N) = m 1+(k-1) (N) =m 1+ (N) m (k-2) (N) = …. = m 1+ (N) =m Что и требовалось доказать.

Пример системы РША p=3, q=11 N=33 Генерирование ключей e=7, НОД(7,20)=1 d=7 -1 (mod20) = 3 Шифрование m=6 E=m e (modN)= 6 7 (mod33)= (mod33)= =3*3*3*3*2=30 Расшифрование E d (modN)=30 3 (mod33)=900*30(mod33)=9*30(mod33)=6

Оценки стойкости системы РША 1. Нахождение чисел p и q по известному модулю N. Задача факторизации имеет сложность O((N) 1/2 ). 2. Будем последовательно возводить полученную криптограмму в степень равную значению открытого ключа т.е. (((((E e ) e )…..) e. Если при некотором шаге окажется, что E i =E, то это означает, что E i-1 =m. Доказывается, что данная атака требует непереборно большого числа шагов. 3. Поиск слабых ключей, для которых m e = m, т.е. возведение в степень не меняет сообщения. Эта атака имеет малую вероятность успеха, если p и q выбираются среди сильно простых чисел. Сильно простое число, это число, для которого p-1 не содержит в разложении маленьких сомножителей, и имеет в разложении хотя бы один большой сомножитель. 4.

Алгоритм формирования ключей на основе однонаправленных функций (алгоритм Диффи-Хеллмана ) А В yAyA yByB

Гибридные системы шифрования