Иванов М.А. КМЗИ сети. Криптографические методы защиты информации
 Скачать 3.04 Mb.
|
|
ГЛАВА 12. КРИПТОСИСТЕМЫ, ОСНОВАННЫЕ НА СВОЙСТВАХ ЭЛЛИПТИЧЕСКИХ КРИВЫХ Множество криптографических протоколов можно разделить на два больших класса: базовые протоколы и протоколы высше- го уровня (соответственно примитивные и прикладные протоко- лы). К базовым можно отнести протоколы распределения клю- чей, электронной подписи, разделения секрета и т. п. Протоколы высшего уровня основываются на базовых протоколах. Напри- мер, если говорить о гипотетическом протоколе проведения бан- ковских транзакций, то для него потребуются как минимум про- токолы электронной подписи и аутентификации сообщений. Здесь необходимо отметить, что замена одного протокола элек- тронной подписи другим (с аналогичной стойкостью) не повлия- ет ни на безопасность протокола, ни на его функциональность. Если говорить о протоколах, основанных на свойствах эллип- тических кривых, то отличия от старых проверенных схем на основе проблемы дискретного логарифмирования можно про- следить лишь на базовых протоколах, да и то не на всех, так как фактически отличия заключаются только во множестве элемен- тов, над которым производятся вычисления. В этой главе рассматриваются несколько важнейших базовых схем, основанных на эллиптических кривых. Сейчас наблюдает- ся тенденция постепенного перехода систем на основе дискрет- ного логарифма к эллиптическим кривым, причем для большин- ства существующих протоколов это происходит совершенно безболезненно. 12.1. Схема симметричного шифрования на эллиптических кривых Зашифрование информации (абонент A защищает сообщение M, пр едназначенное для абонента B) (рис. 12.1): А преобразовывает открытый текст M в точки эллиптиче- ской кривой; А выбирает секретный ключ K; А вычисляет закрытый текст С C = M + K. 329 Расшифрование информации (абонент B преобразует закры- тый текст С) (рис. 12.2): В вычисляет обратный ключ (–K). В восстанавливает открытый текст M M = C + (–K). M Q K C y x M K C y x -K Q Рис. 12.1. Прямое преобразование Рис. 12.2. Обратное преобразование Пример. Пусть задана кривая E (GF(23)) вида 1 3 2 x x y Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B): А преобразовывает открытый текст M в точку эллиптиче- ской кривой M = (12, 19); А выбирает секретный ключ K = (13, 7); А вычисляет закрытый текст С C = M + K = (12, 19) + (13, 7) = (4, 0). Расшифрование информации (абонент B восстанавливает за- крытый текст С, полученный от абонента А): В вычисляет обратный ключ (–K) –K = (13, –7) mod 23 = (13, 16); В восстанавливает открытый текст M M = C + (–K) = (4, 0) + (13, 16) = (12, 19). 330 12.2. Схема асимметричного шифрования на эллиптических кривых В этом и последующих алгоритмах должны быть определены следующие открытые параметры, общие для всех пользователей системы: конечное поле GF(p); эллиптическая кривая E(GF(p)); порядок n, который является простым числом; базовая точка G порядка n. Генерация ключей. Каждый пользователь системы генерирует пару ключей следующим образом: выбирается случайное целое число d, 1 1 n d ; вычисляется точка G d Q Секретным ключом пользователя является число d, открытым ключом – точка Q. Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B): А выбирает случайное целое число k, 1 1 n k ; А вычисляет точку G k y x 1 1 , ; А вычисляет точку Q k y x 2 2 , , используя открытый ключ Q пользователя В; А вычисляет 2 1 x M c ; закрытые данные: 1 1 1 , , c y x C Расшифрование информации (абонент B восстанавливает за- крытые данные 1 1 1 , , c y x C , полученные от абонента A): В вычисляет точку 1 1 2 2 , , y x d y x , используя свой сек- ретный ключ d; В восстанавливает исходное сообщение 2 1 x c M Пример Параметры: конечное поле GF(23); эллиптическая кривая E (GF(23)) вида 1 3 2 x x y ; базовая точка G = (13, 7); порядок n = 7. 331 Генерация ключей: выбирается случайное целое число d = 3; вычисляется точка G d Q = 3(13, 7) = (17, 3). Секретным ключом пользователя является число d = 3, от- крытым ключом – точка Q = (17, 3). Пусть сообщение M = 9. Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B): А выбирает случайное целое число k = 4; А вычисляет точку G k y x 1 1 , = 4(13, 7) = (17, 20); А вычисляет точку Q k y x 2 2 , = 4(17, 3) = (5, 19); А вычисляет 2 1 x M c = 9 5 = 12; закрытые данные: 1 1 1 , , c y x C = (17, 20, 12). Расшифрование информации (абонент B восстанавливает за- крытые данные 1 1 1 , , c y x C = (17, 20, 12), полученные от або- нента A): В вычисляет точку 1 1 2 2 , , y x d y x = 3(17, 20) = (5, 19); В восстанавливает исходное сообщение 2 1 x c M = 12 5 = 9. 12.3. Схема электронной цифровой подписи на эллиптических кривых Выбор параметров и процедура генерации ключей описаны в разделе 12.2. Формирование подписи (абонент A подписывает сообщение M): А вычисляет хеш-образ сообщения M h e ; А выбирает случайное целое число k, 1 1 n k ; А вычисляет точку G k y x 1 1 , ; А вычисляет n e x r mod 1 ; А вычисляет n d r k s mod , используя свой секретный ключ d. В том случае, если r = 0 или s = 0, выбор k осущест- вляется заново; подписью сообщения является пара (r, s). Проверка подписи (абонент B проверяет подпись (r, s) або- нента A на сообщении M): 332 В вычисляет точку Q r G s y x 1 1 , , используя откры- тый ключ Q абонента A; В вычисляет хеш-образ сообщения M h e ; В вычисляет n e x r mod 1 1 ; подпись считается верной, если r r 1 Пример Параметры: конечное поле GF(23); эллиптическая кривая E (GF(23)) вида 1 3 2 x x y ; базовая точка G = (13, 7); порядок n = 7. Генерация ключей: выбирается случайное целое число d = 3; вычисляется точка G d Q = 3(13, 7) = (17, 3). Секретным ключом пользователя является число d = 3, откры- тым ключом – точка Q = (17, 3). Пусть сообщение M = 10111001. Формирование подписи (абонент A подписывает сообщение M): А вычисляет хеш-образ сообщения M h e = 6; А выбирает случайное целое число k = 4; А вычисляет точку G k y x 1 1 , = 4(13, 7) = (17, 20); А вычисляет n e x r mod 1 = (17 + 6) mod 7 = 2; А вычисляет n d r k s mod = 4 – (2 3) mod 7 = 5; Подписью сообщения является пара (r, s) = (2, 5). Проверка подписи (абонент B проверяет подпись (r, s) = (2, 5) абонента A на сообщении M): В вычисляет точку Q r G s y x 1 1 , = 5(13, 7) + 2(17, 3) = (17, 20); В вычисляет хеш-образ сообщения M h e = 6; В вычисляет n e x r mod 1 1 = (17 + 6) mod 7 = 2; подпись считается верной в случае r 1 = 2. 333 12.4. Схема ЭЦП на эллиптических кривых (ECDSA) Выбор параметров и процедура генерации ключей описаны в разделе 12.2. Формирование подписи (абонент A подписывает сообщение M): A вычисляет хеш-образ сообщения M h e ; А выбирает случайное целое число k, 1 1 n k ; А вычисляет точку G k y x 1 1 , и n x r mod 1 ; A вычисляет n d r e k s mod 1 - , используя свой сек- ретный ключ d; в случае, если r = 0 или s = 0, повторяется выбор k; подписью сообщения являются (r, s). Проверка подписи (абонент B проверяет подпись сообщения (r, s) абонента A под сообщением M): B вычисляет хеш-образ сообщения M h e ; B вычисляет n e s u mod 1 - и n r s v mod 1 - ; B вычисляет точку Q v G u y x 1 1 , , используя от- крытый ключ Q абонента А; B вычисляет n x r mod 1 1 ; подпись считается верной, если r r 1 Пример Параметры: конечное поле GF(23); эллиптическая кривая E (GF(23)) вида 1 3 2 x x y ; базовая точка G = (13, 7); порядок n = 7. Генерация ключей: выбирается случайное целое число d = 3; вычисляется точка G d Q = 3(13, 7) = (17, 3). Секретным ключом пользователя является число d = 3, от- крытым ключом – точка Q = (17, 3). Пусть сообщение M = 10111001. Формирование подписи (абонент A подписывает сообщение M): A вычисляет хеш-образ сообщения M h e = 6; A вычисляет случайное целое число k = 3; 334 A вычисляет точку G k y x 1 1 , = 3(13, 7) = (17, 3) и n x r mod 1 = 17 mod 7 = 3; A вычисляет n d r e k s mod 1 - = 3 –1 (6 + (3 3)) mod 7 = = 5 (6 + 9) mod 7 = 5; подписью сообщения являются (r, s) = (3, 5). Проверка подписи (абонент B проверяет подпись сообщения (r, s) = (3, 5) абонента A под сообщением M): B вычисляет хеш-образ сообщения M h e = 6; B вычисляет n e s u mod 1 - = 5 –1 6 mod 7 = 3 6 mod 7 = 4 и n r s v mod 1 - = 5 –1 3 mod 7 = 2; B вычисляет точку Q v G u y x 1 1 , = 4(13, 7) + 2(17, 3) = (17, 3); B вычисляет n x r mod 1 1 = 17 mod 7 = 3; подпись считается верной в случае r 1 = 3. 12.5. Протокол выработки общего секретного ключа (ECKEP) Это протокол, где два абонента A и B устанавливают общий секретный ключ K, называемый сеансовым ключом. Он позво- ляет создать защищенный канал связи между абонентами и слу- жит для решения задач обеспечения конфиденциальности и ау- тентичности информации. Процедуры определения параметров системы и генерации ключей аналогичны рассмотренным ранее. Предположим, что общий секретный ключ вычисляется абонентами A и B. Абонент A имеет секретный ключ a и открытый ключ A A A y x G a Q , , аналогично b и B B B y x G b Q , являются соответственно секретными и открытыми ключами абонента B. Общий секретный ключ вычисляется в четыре этапа: 1) абонент A выполняет следующие действия: выбирает случайное целое число A k , 1 1 n k A ; 335 вычисляет точку G k R A A ; вычисляет точку B A Q k y x 1 1 , ; вычисляет n x x a k s A A A mod 1 ; пересылает A R абоненту B; 2) абонент B выполняет следующие действия: выбирает случайное целое число B k , 1 1 n k B ; вычисляет точку G k R B B ; вычисляет точку A B Q k y x 2 2 , ; вычисляет n x x b k s B B B mod 2 ; пересылает B R абоненту A; 3) абонент A выполняет следующие действия: вычисляет точку B R a y x 2 2 , Вычисляет общий секретный ключ B B B A Q x x R s K 2 ; 4) абонент B выполняет следующие действия: вычисляет точку A R b y x 1 1 , ; вычисляет общий секретный ключ A A A B Q x x R s K 1 , что эквивалентно B B B A Q x x R s K 2 Пример Параметры: конечное поле GF(23); эллиптическая кривая E (GF(23)) вида 1 3 2 x x y ; базовая точка G = (13, 7); порядок n = 7. Генерация ключей: A выбирает случайное целое число a = 3; A вычисляет точку A A A y x G a Q , = 3(13, 7) = (17, 3); B выбирает случайное целое число b = 6; B вычисляет точку B B B y x G b Q , = 6(13, 7) = (13, 16). Общий секретный ключ вычисляется в четыре этапа: 1) абонент A выполняет следующие действия: 336 выбирает случайное целое число A k = 4; вычисляет точку G k R A A = 4(13, 7) = (17, 20); вычисляет точку B A Q k y x 1 1 , = 4(13, 16) = (17, 3); вычисляет n x x a k s A A A mod 1 = = 4 + (3 17 17) mod 7 = 3; пересылает A R = (17, 20) абоненту B; 2) абонент B выполняет следующие действия: выбирает случайное целое число B k = 2; вычисляет точку G k R B B = 2(13, 7) = (5, 4); вычисляет точку A B Q k y x 2 2 , = 2(17, 3) = (13, 16); вычисляет n x x b k s B B B mod 2 = = 2 + (6 13 13) mod 7 = 1; пересылает B R = (5, 4) абоненту A; 3) абонент A выполняет следующие действия: вычисляет точку B R a y x 2 2 , = 3(5, 4) = (13, 16); вычисляет общий секретный ключ B B B A Q x x R s K 2 = = 3((5, 4) + (13 13 (13, 16))) = (17, 3); 4) абонент B выполняет следующие действия: вычисляет A R b y x 1 1 , = 6(17, 20) = (17, 3); вычисляет общий секретный ключ A A A B Q x x R s K 1 = = 1((17, 20) + (17 17 (17, 3))) = (17, 3). 12.6. Схема гибридного шифрования (ECKAP) В схеме ECKAP строится защищенный канал связи между абонентами на основе использования сеансового ключа. Проце- дуры определения параметров системы и генерации ключей ана- логичны рассмотренным ранее. Обозначения: 337 M – сообщение; Q – открытый ключ абонента B; d – секретный ключ абонента B; S K – сеансовый ключ; M C – шифротекст; K C – зашифрованный ключ; S E , S D – соответственно за- и расшифрование с использо- ванием симметричного криптоалгоритма; A E , A D – соответственно за- и расшифрование с использо- ванием асимметричного криптоалгоритма. Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B): А вычисляет M C , преобразуя сообщение M на сеансовом ключе S K с использованием алгоритма S E ; А вычисляет K C , преобразуя на открытом ключе Q абонента B сеансовый ключ S K с использованием алгоритма A E ; сообщение для абонента В включает закрытый текст M C и преобразованный ключ K C . Расшифрование информации (абонент B восстанавливает по- лученное сообщение, включающее закрытый текст M C и преоб- разованный ключ K C ): В восстанавливает сеансовый ключ S K , преобразуя K C на своем секретном ключе d с использованием алгоритма A D ; В восстанавливает исходное сообщение M, преобразуя M C на полученном сеансовом ключе S K с использованием алго- ритма S D . Пример Параметры: конечное поле GF(23); эллиптическая кривая E (GF(23)) вида 1 3 2 x x y ; базовая точка G = (13, 7); порядок n = 7. Генерация ключей: 338 B выбирает секретный ключ d = 6; B вычисляет открытый ключ G d Q = 6(13, 7) = (13, 16). Пусть открытый текст M = 6 и сеансовый ключ S K = (17, 3). Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B): А вычисляет закрытый текст S M K M C = 6 17 = 23; А вычисляет преобразованный ключ K C : А выбирает случайное целое число k = 2; А вычисляет точку G k y x 1 1 , = 2(13, 7) = (5, 4); А вычисляет точку Q k y x 2 2 , = 2(13, 16) = (5, 19); А вычисляет 2 x K C S K = (17, 3) 5 = (20, 6); закрытие данных: M C = 23, K C = (20, 6), 1 1 , y x = (5, 4). Расшифрование информации (абонент B восстанавливает полученное от абонента A сообщение M C = 23, используя ключ K C = (20, 6) и 1 1 , y x = (5, 4)): абонент В восстанавливает сеансовый ключ S K : вычисляет точку 1 1 2 2 , , y x d y x = 6(5, 4) = (5, 19); восстанавливает сеансовый ключ S K 2 x C K K S = (20, 6) 5 = (17, 3); абонент В восстанавливает исходное сообщение: S M K C M = 23 17 = 6. 12.7. Российский стандарт на ЭЦП ГОСТ Р 34.10-2001 ГОСТ Р 34.10-2001 – российский стандарт, описывающий ал- горитмы формирования и проверки электронной цифровой под- писи. Введен в действие вместо ГОСТ Р 34.10-94. Старый стан- дарт описывал алгоритм ЭЦП на основе проблемы дискретного 339 логарифмирования в конечном поле, новый же предписывает использовать эллиптические кривые над полем GF(p). В отличие от западных аналогов в российском стандарте не регламентируются алгоритмы формирования ключей, парамет- ров кривых и начальных точек, однако задаются определенные условия, которым должны удовлетворять используемые кривые. Обозначения: V 256 – множество всех двоичных векторов длиной 256 бит; V – множество всех двоичных векторов произвольной конечной длины; Z – множество всех целых чисел; p – простое число, p > 3; GF(p) – конечное простое поле из p элементов {0, 1, 2, ..., (p – 1)}; b mod p – минимальное неотрицательное число, сравнимое с b по модулю p; h – двоичный вектор, например, двоичный вектор длиной 256 бит может быть представлен в виде h = ( 255 1 0 ), i {0, 1}, числу соответствует вектор h, если выполняется равенство = i 2 i ; M – сообщение, М V ; (h 1 , h 2 ) – конкатенация (объединение) двух двоичных векторов, пусть h 1 = ( 255 1 0 ), i {0, 1}, h 2 = ( 255 1 0 ), i {0, 1}, тогда (h 1 , h 2 ) = ( 255 1 0 255 1 0 ); a, b – коэффициенты эллиптической кривой; m – порядок группы точек эллиптической кривой; q – порядок подгруппы группы точек эллиптической кривой; O – бесконечно удаленная точка эллиптической кривой; P – точка эллиптической кривой порядка q; 340 d – целое число, ключ формирования подписи; Q – точка эллиптической кривой, ключ проверки подписи; sign (M) – цифровая подпись под сообщением М. Механизм цифровой подписи включает в себя две основные процедуры: 1) формирование подписи (рис. 12.3); 2) проверку подписи (рис. 12.4). Схема реализована с использованием операций группы точек эллиптической кривой, определенной над конечным простым полем, а также хеш-функции. Стойкость схемы цифровой под- писи основывается на сложности решения задачи дискретного логарифмирования на группе точек эллиптической кривой, а также стойкости используемой хеш-функции. Алгоритм хеши- рования определен в ГОСТ 34.11. Разрядность цифровой подписи устанавливается равной 512 бит. Математические предпосылки Инвариантом эллиптической кривой Е называется величина J(E), удовлетворяющая тождеству J(E) 1728 (4a 3 /(4a 3 + 27b 2 )) mod p. Коэффициенты a и b эллиптической кривой по известному инварианту J определяются следующим образом: a 3k mod p, b 2k mod p, где k J(E)/(1728 – J(E)) mod p, J(E) 0, J(E) 1728. Для абелевой группы порядка m, которую образуют точки эл- липтической кривой E, справедливо неравенство p + 1 – 2 p m p + 1 + 2 p . Точка Q называется точкой кратности k или просто кратной точкой эллиптической кривой Е, если для некоторой точки Р выполняется равенство Q = kP. 341 1 2 3 4 5 6 Вычисление хеш-образа сообщения Сообщение М, ключ формирования подписи d Вычисление α и определение е Вычисление точки эллиптической кривой C = kP, r = x C mod q sign (M) s = 0 Нет Да Вычисление k r = 0 Да Нет Вычисление s Вычисление подписи sign (M) Рис. 12.3. ГОСТ Р 34.10-2001. Схема формирования цифровой подписи Параметры схемы цифровой подписи: простое число p > 2 255 , при этом p i 1 mod q для всех целых i, меньших 32; эллиптическая кривая Е, задаваемая своим инвариантом или коэффициентами a и b; целое число m – порядок группы точек эллиптической кри- вой Е (m p); простое число q – порядок циклической подгруппы группы точек кривой Е, для которого выполняются условия 342 m = nq, n Z, n 1, 2 254 < q < 2 256 ; точка P O кривой Е с координатами (x P , y P ), удовлетво- ряющая равенству qP = O. Ключ формирования подписи – целое число d, удовлетво- ряющее неравенству 0 < d < q. Ключ проверки подписи – точка эллиптической кривой Q с координатами (x Q , y Q ), удовлетворяющая равенству dP = Q. 1 3 4 5 6 Вычисление r и s по полученной подписи Сообщение М, подпись sign (M), ключ проверки подписи Q 2 0 < r < q 0 < s < q Да Нет Вычисление хеш-образа полученного сообщения Вычисление α и определение e Вычисление ν Вычисление z 1 и z 2 Вычисление точки эллиптической кривой C = z 1 P + z 2 Q и определение R R = r Да Нет Подпись принимается Подпись отвергается Рис. 12.4. ГОСТ Р 34.10-2001. Схема проверки цифровой подписи 343 Последовательность формирования цифровой подписи сообщения М V : 1) вычислить хеш-образ h(M) сообщения М; 2) вычислить целое число , двоичным представлением которого является вектор h и определить e mod q; ес- ли е = 0, то определить e = 1; 3) сформировать случайное число k, удовлетворяющее условию 0 < k < q; 4) вычислить точку эллиптической кривой С = kP и опреде- лить r x C mod q, где x C – координата точки С; если r = 0, то вернуться к шагу 3; 5) вычислить значение s (rd + ke) mod q; если s = 0, то вернуться к шагу 3; 6) вычислить двоичные векторы r и s и определить цифро- вую подпись sign (M) как конкатенацию двух двоичных векторов (r, s). Последовательность проверки цифровой подписи: 1) по полученной подписи sign (M) вычислить целые числа r и s; если выполнены неравенства 0 < r < q, 0 < s < q, то перейти к следующему шагу, в противном случае под- пись отвергается; 2) вычислить хеш-образ h(M) полученного сообщения М; 3) вычислить целое число , двоичным представлением которого является вектор h, и определить e mod q; если е = 0, то определить e = 1; 4) вычислить значение e -1 mod q; 5) вычислить значения z 1 s mod q, z 2 – r mod q; 6) вычислить точку эллиптической кривой C = z 1 P + z 2 Q и определить R x C mod q, где x С – координата точки С; 7) если выполняется равенство R = r, то подпись принима- ется, в противном случае – отвергается. 344 Контрольные вопросы 1. Приведите пример построения криптосистемы с откры- тым ключом, основанной на свойствах эллиптических кривых. 2. Приведите примеры эллиптических алгоритмов форми- рования и проверки ЭЦП. 3. Приведите пример построения гибридной криптосистемы на основе ECCS. |