Спосіб криптографічної обробки з використанням еліптичної кривої і пристрій для криптографічної обробки, що містить процесорний вузол

1 Спосіб криптографічної обробки з використанням еліптичної кривої на комп'ютері, згідно з яким виконують такі кроки а) задають еліптичну криву у першій формі, причому еліптичну криву характеризують кількома першими параметрами, б) еліптичну криву трансформують у другу форму у = х3 + с4ах + c6b шляхом визначення кількох других параметрів, причому, щонайменше один із других параметрів має меншу довжину, ніж перший параметр, причому х, у означають ЗМІННІ a, b означають перші параметри с означає константу, в) принаймні параметр а вкорочують шляхом такого вибору константи с, що коефіцієнт с4а mod p має значно меншу довжину, ніж параметр b і попередньо задана величина р, г) еліптичну криву у другій формі використовують для криптографічної обробки 2 Спосіб згідно з попереднім пунктом, який відрізняється тим, що першу форму еліптичної кривої задають рівнянням у2 = х3 + ах + Ь, Де х, у означають ЗМІННІ a, b означають перші параметри 3 Спосіб згідно з одним із попередніх пунктів, який відрізняється тим, що здійснюють криптографічне кодування 4 Спосіб згідно з одним із попередніх пунктів, який відрізняється тим, що здійснюють криптографічне декодування 5 Спосіб згідно з одним із попередніх пунктів, який відрізняється тим, що здійснюють видачу коду 6 Спосіб згідно з одним із попередніх пунктів, який відрізняється тим, що здійснюють цифровий підпис 7 Спосіб за п 6, який відрізняється тим, що здійснюють верифікацію цифрового підпису 8 Спосіб згідно з одним із попередніх пунктів, який відрізняється тим, що здійснюють асиметричну аутентифікацію 9 Пристрій для криптографічної обробки, що містить процесорний вузол, виконаний таким чином, що а) задається еліптична крива у першій формі, причому еліптичну криву характеризують кілька перших параметрів, б) еліптична крива трансформується у другу форму у - х3 + с 4 ах+ c6b шляхом визначення кількох других параметрів, причому, щонайменше один із других параметрів має меншу довжину, ніж перший параметр, причому х, у означають ЗМІННІ a, b означають перші параметри с означає константу, в) принаймні параметр а вкорочують шляхом такого вибору константи с, що коефіцієнт с4а mod p має значно меншу довжину, ніж параметр b і попередньо задана величина р, г) еліптичну криву у другій формі використовують для криптографічної обробки 10 Пристрій згідно з п 9, який відрізняється тим, що пристрій є чіп-карткою з пам'яттю, виконаною з можливістю запису в пам'яті параметрів еліптичної кривої 11 Пристрій згідно з п 10, який відрізняється тим, що він виконаний з можливістю запису секретного коду в захищену ділянку пам'яті О 00 ю 57827 Винахід стосується способу та пристрою для криптографічної обробки з використанням еліптичної кривої на основі процесорного вузла Кінцеве поле називається полем Галуа Стосовно властивостей і визначення поля Галуа можна зробити посилання на [3] Зі всебічним поширенням комп'ютерних мереж і ВІДПОВІДНИХ прикладних програм, що передаються через електронні системи зв'язку (комунікаційні мережі), зростаючі вимоги пред'являються до захисту даних Аспект захисту даних передбачає, крім іншого, можливість припинення передачі даних, можливість корумпованих даних, автентичність даних, тобто можливість встановлення і ідентифікації відправника, захист конфіденційності даних Під терміном "код" слід розуміти дані, що використовуються при криптографічній обробці Відома криптографічна система з кодом загального користування [4], в якій використовуються секретні і відкриті коди "Зловмисником" є неуповноважена особа, що намагається здобути код Зокрема у комп'ютерній мережі, а також у зростаючій мірі і в переносних засобах, наприклад, у мобільних телефонах чи чіп-картках, необхідно забезпечити, щоб записаний код не став доступним навіть тоді, коли зловмисник заволодіє комп'ютером, мобільним телефоном чи чіп-карткою Для забезпечення надійності криптографічного способу коди, особливо в разі асиметричного способу, мусять мати довжину в кілька сот біт Пам'ять комп'ютера чи переносного засобу у більшості випадків обмежена Записаний у ній код довжиною у кілька сот біт значною мірою впливає на вільний об'єм пам'яті, необхідний для основної роботи комп'ютера чи іншого засобу, тому записані можуть бути лише кілька таких кодів Із [1] і [2] відома еліптична крива і її застосування при криптографічній обробці Задача винаходу полягає в розробці способу криптографічної обробки з використанням щонайменше однієї еліптичної кривої на комп'ютері, здійснення якого потребує менше місця в пам'яті Розроблено спосіб криптографічної обробки з використанням щонайменше однієї еліптичної кривої на комп'ютері, при якому еліптична крива перебуває у першій формі, причому, еліптичну криву у першій формі визначають кілька перших параметрів Еліптичну криву трансформують у другу форму шляхом завдання кількох других параметрів, причому, щонайменше один із других параметрів має меншу довжину порівняно з довжиною одного із перших параметрів Еліптичну криву після трансформації, тобто, у другій формі, використовують для криптографічної обробки Завдяки значному вкороченню одного із перших параметрів, досягається економія пам'яті, необхідної для запису цього параметра Оскільки пам'ять, наприклад, у чіп-картці, має обмежений обсяг, завдяки економії кількох сот біт на кожному вкороченому параметрі отримують ВІЛЬНІ ДІЛЯНКИ пам'яті, наприклад, для розміщення інших секретних кодів Незважаючи на вкорочення параметрів, надійність криптографічного способу не зменшується При використанні еліптичної кривої в криптографічному способі витрати, які мусить вкласти зловмисник для визначення коду, експоненційно залежать від його довжини Вдосконалення винаходу полягає у тому, що перша форма еліптичної кривої описується рівнянням у2 = х3 + ах+ bBGF(p) (1) де GF(p) означає поле Галуа з р елементами х, у, a, b означають елементи поля GF(p) Використовуване далі позначення "mod p" означає спеціальний випадок для поля Галуа, а саме натуральні числа, менші від р "mod" означає "по модулю" (MODULO) і охоплює ділення цілих чисел із залишком Інше вдосконалення полягає в тому, що друга форма еліптичної кривої описується рівнянням y2 = x3 + c 4 ax+c 6 bBGF(p) (2) де с означає константу Для економії пам'яті рівняння (1) трансформують у рівняння (2) і вкорочують параметр, що характеризує еліптичну криву згідно з рівнянням (2) Наступне вдосконалення полягає в укороченні параметра а шляхом такого вибору константи с, що коефіцієнт с a mod p (3) стає значно коротшим, ніж ІНШІ параметри, що описують еліптичну криву згідно з рівнянням (2) Завдяки цьому вкороченню, параметр потребує ВІДПОВІДНО менше місця в пам'яті Інше вдосконалення полягає у застосуванні способу в одному із таких випадків - Кодування або декодування дані кодуються відправником - симетричним чи асиметричним способом - і декодуються отримувачем - Передача коду сертифікаційним органом організація, яка заслуговує на довіру (сертифікаційний орган), передає код, причому, має гарантуватися, що код походить саме від цього сертифікаціного органу - Цифровий підпис або верифікація цифрового підпису електронний документ підписується і підпис додається до документу Отримувач за допомогою підпису може встановити, чи справді цей документ підписав бажаний відправник - Асиметрична аутентифікація за допомогою асиметричного способу користувач може довести свою ідентичність Це здійснюють переважним чином шляхом кодування з ВІДПОВІДНИМ секретним (особистим) кодом За допомогою ВІДПОВІДНОГО відкритого коду цього користувача кожен може встановити, що кодування виконане дійсно цим користувачем - Укорочення кодів 57827 цей варіант криптографічної обробки охоплює укорочення коду, який може бути використаний для подальшого використання у криптографії Крім того, розроблено пристрій, який містить процесорний вузол, виконаний таким чином, що задається еліптична крива у першій формі, причому, еліптична крива задається кількома першими параметрами, еліптична крива трансформується у другу форму шляхом завдання кількох других параметрів, причому, щонайменше один із других параметрів укорочений порівняно з довжиною перших параметрів Отримана еліптична крива у другій формі використовується для криптографічної обробки Цей пристрій може бути чіп-карткою, що містить захищену і незахищену ділянки пам'яті, причому, як у захищеній, так і у незахищеній ділянках пам'яті можуть бути записані коди, тобто параметри, що визначають еліптичну криву Цей пристрій придатен, зокрема, для здійснення винайденого способу або одного із описаних вище вдосконалень цього способу Вдосконалення винаходу відображені у залежних пунктах формули винаходу Нижче приклади виконання винаходу детальніше пояснюються з використанням фігур На них зображено фіг 1 Спосіб криптографічної обробки за допомогою еліптичної кривої, причому, щонайменше один параметр еліптичної кривої укорочують, досягаючи таким чином економії частини ділянки пам'яті, необхідної для запису параметрів еліптичної кривої, фіг 2 Можливості ДЛЯ вибору простого числа р таким чином, що параметр а еліптичної кривої укорочується, фіг 3 Спосіб завдання параметрів еліптичної кривої і наступна трансформація у другу форму, фіг 4 Пристрій для криптографічної обробки, фіг 5 Процесорний вузол На фіг 1 зображено блок-схему способу обробки з використанням еліптичної кривої Для цього еліптичну криву у першій формі (блок 101) трансформують у другу форму (блок 102), параметр другої форми укорочують (блок 103) і другу форму записують з метою використання для криптографічної обробки (блок 104) Нижче описуються названі кроки, причому, наводяться приклади можливостей для вкорочення параметрів Нижче описано, яким чином досягають зменшення довжини параметра а у рівнянні еліптичної кривої (еліптична крива у першій формі, блок 101) у2 = х3 + ах + bBGF(p) (3) причому, р означає просте число більше, ніж З, a GF(p) означає поле Галуа з р елементами Еліптичну криву у2 = х3 + ах + bBGF(p) (4) шляхом трансформації можна перетворити у бірацюнально ізоморфну еліптичну криву (еліптичну криву другої форми, блок 102) y2 = x3 + c 4 a x + c 6 b B G F ( p ) (5) Шляхом ВІДПОВІДНОГО вибору константи с коефіцієнт с4а (6) або 6 4 -с а (7) може бути вкорочений, завдяки чому місце в пам'яті, необхідне для запису цього коефіцієнта, буде значно меншим, ніж для запису параметра а ВІДПОВІДНО ДО рівняння (51, нижче наводяться 4 визначення для коефіцієнтів с а (або -с а) і с 4 1 Визначення числа "с а" 4 4 Для визначення числа с а (або -с а) розрізняють два випадки 1 1 р = 3 mod 4 В цих полях ДІЙСНІ такі положення всі квадрати також є показниками четвертого степеня, ' - 1 ' не є квадратом Хай р = 4к + 3, a s означає четвертий степінь, який утворює мультиплікативну підгрупу четвертих степенів (квадратів) у GF(p) Тоді V = {1,s,s 2 ,s 3 , ,s 2k } Означає множину четвертих степенів у GF(p), a NQ = {-1,-s,-s ,-s 3 , ,-s2k} Означає множину неквадратів у GF(p) 1 Для кожного елемента а = s[ із V існує елемент, с 4 = s 2 k + 1 [ із V для якого с 4 а = s 2 k + 1 - 1 в GF(p) 2 Для кожного елемента а = -s[ із V існує елемент, с 4 = s 2 k + 1 [ із V для якого с 4 а = - s 2 k + 1 = -1 в GF(p) При цьому s, t і k означають елементи поля GF(p) Для р = 3 mod 4 параметр а можна шляхом ВІДПОВІДНОГО вибору констант с перетворити в число с 4 а = 1 в GF(p) або с 4 а = -1 в GF(p) 1 2 р = 1 mod 4 В цих полях ДІЙСНІ такі положення елементи (р-1)/4 мультиплікативної групи поля є показниками четвертого степеня, елементи (р-1)/4 мультиплікативної групи поля є квадратами, але не є показниками четвертого степеня, елементи (р-1)/2 мультиплікативної групи поля є не-квадратами, ' - 1 ' не є не-квадратом А) р = 5 mod 8 В цих полях додатково ДІЙСНІ такі положення ' - 1 ' є квадратом, але не є четвертим степенем, '+2', '-2' є не-квадратами Хай р = 8к + 5, a s означає четвертий степінь, який утворює мультиплікативну підгрупу четвертих степенів у GF(p) Тоді V = {1,s,s 2 ,s 3 , ,s 2k } Означає множину четвертих степенів у GF(p), a Q = {-1,-s,-s2,-s , ,-s2k} Означає множину квадратів, які не є четвертими степенями у GF(p) NQ = {2,2s,2s 2 ,2s 3 , ,2s 2k ,-2,-2s,-2s 2 ,-2s^, ,-2s 2k } Означає множину не-квадратів у GF(p) 1 Для кожного елемента а = s[ із V існує елемент, с 4 = s 2 k + 1 [ із V для якого с 4 а = s 2 k + 1 - 1 в GF(p) 2 Для кожного елемента а = -s[ із Q існує елемент, с 4 = s 2 k + 1 [ із V для якого с 4 а = - s 2 k + 1 = -1 в GF(p) 3 Для кожного елемента а = 2s f із NQ існує елемент, с 4 = s 2 k + [ із V для якого с 4 а = 2 s 2 k + 1 = 2 в GF(p) 57827 4 Для кожного елемента а = -2sf із NQ існує елемент, с4 = s 2 k + 1 [ із V для якого с4а = -2s 2k+1 = -2 в GF(p) Для р = 5 mod 8 параметр а можна шляхом ВІДПОВІДНОГО вибору констант с перетворити в число с4а = 1, або -1, або 2, або -2 в GF(p) В) р = 1 mod 8 Число с4а можна визначити за такою схемою Для г= 1,-1,2,-2,3,-3,4,-4, утворити z = га 1 mod p, вирахувати u = z(p 1|/4 mod p, припинити, якщо u = 1, записати z = с4 і г = с4а 2 Визначення числа "с2 в GF(p)" Для визначення числа с2 mod p 2 1 р = 4к + З В цих полях обчислюють u = а(р 1|/2 у GF(p) ЯКЩО U = 1 у GF(p), то а є четвертим степенем (або квадратом) У цьому разі с4 = а 1 у GF(p) Якщо u = -1 у GF(p), то а є не-квадратом У цьому разі с4 = -а у GF(p) 2 2 р = 8к + 5 В цих полях обчислюють u = а(р 1|/4 у GF(p) ЯКЩО U = 1 у GF(p) то а є четвертим степенем У цьому разі с4 = а у GF(p) ЯКЩО U = -1 у GF(p), то а є квадратом, але не є четвертим степенем У цьому разі с4 = -а 1 у GF(p) Якщо u не дорівнює ні 1, ні -1 у GF(p), то а є не-квадратом у GF(p) У цьому разі обраховують v = (2а)(р 1|/4 у GFfp) Якщо v = 1 у GF(p), то с4 = 2а 1 у GF(p), інакше с = -2а 1 у GF(p) 2 3 р = 8к + 1 В цих полях згідно зі схемою, описаною в 1 2, випадок В, z = с4 У всіх трьох випадках з використанням ОПод р) можна вирахувати обидва корені (с2 і с 2) із с Для випадку р = 4к + 3 допустимим є лише одне із двох рішень, а саме те, яке є квадратом у GF(p) В інших випадках допустимі обидва рішення Таким чином можна обчислити коефіцієнт c6b еліптичної кривої На основі замкнутих формул для випадків р = 4к + 3 і р = 8к + 5 на практиці перевагу мають такі прості числа Приклад 1 Хай є просте число р = 11 => випадок 11 р = З mod 4 Таблиця 1 Квадрати і четверті степені mod 11 Число Квадрати Q Четверті степені V 1 1 1 2 4 5 3 9 4 4 5 3 5 3 9 6 3 9 7 5 3 8 9 4 9 4 5 10 1 1 Таким чином отримуємо множину квадратів Q, 8 множину четвертих степенів квадратів NQ Q = V = {1,3,4,5,9}, NQ = {2,6,7,8,10} а є V = Q => ас4 = 1 V множину не Таблиця 2 Визначення с4 при заданому параметрі а с4 = 1 4 3 9 5 а= 1 3 4 5 9 а є NQ => ас = -1 Таблиця З Визначення с4 при заданому параметрі а С4 = 5 9 3 4 1 а= 2 6 7 8 10 Приклад 2 Хай є просте число р = 13 => випадок 1 2 А) р = 1 mod 4 і одночасно р = 5 mod 8 Таблиця 4 Квадрати і четверті степені mod 13 Число 1 2 3 4 5 6 7 8 9 10 11 12 Квадрати Q 1 4 9 3 12 10 10 12 3 9 4 1 Четверті степені V 1 3 3 9 1 9 9 1 9 3 3 1 Таким чином отримуємо множину квадратів Q (які не є четвертими степенями), множину четвертих степенів V і множину не-квадратів NQ Q = {4,10,12}, V = {1,3,9}, NQ = {2,5,6,7,8,11} а є V ^> с4 є V 57827 Таблиця 5 Визначення с при заданому параметрі а 4 а= 1 3 9 => ас = 1 mod 13 а єQ с = 1 9 3 Таблиця 6 Визначення с при заданому параметрі а а= 4 10 12 4 с = 3 9 1 4 ас = 12 = -1 mod 13 90 = -1 mod 13 12 = -1 mod 13 => ас = -1 mod 13 а є NQ NQ = {2,5,6,7,8,11} 2 * V = {1,5,6} 2 * Q = {7,8,11} Випадок а а є NQ і а є (2 * V) 10 криву трансформують (див рівняння (2)) Після трансформування еліптична крива характеризується параметрами a', b', p і ZP Штрихи у параметрах а' і Ь' означають, що параметри а і b змінені, причому, один параметр, переважно параметр а', коротший порівняно з параметром а, завдяки чому при запису параметрів еліптичної кривої досягається економія пам'яті На фіг 4 зображено пристрій для криптографічної обробки Переносний засіб 401, переважно чіп-картка, містить незахищену ділянку пам'яті MEM 403 і захищену ділянку пам'яті SEC 402 За допомогою штерфейса IFC 404 через канал 405 здійснюється обмін даними між засобом 401 і комп'ютерною мережею RN 406 Комп'ютерна мережа 406 складається із багатьох з'єднаних між собою комп'ютерів, між якими здійснюється зв'язок Дні ДЛЯ роботи переносного засобу 401 в загальному випадку розподілені в комп'ютерах мережі Захищена ділянка 402 пам'яті виконана без можливості зчитування Дані, записані у захищеній ДІЛЯНЦІ 402 пам'яті, використовуються обчислювальним вузлом, розміщеним на переносному засобі 401 або у комп'ютерній мережі 406 Так, наприклад, може бути здійснена операція порівняння введених даних з кодом, записаним у захищеній ДІЛЯНЦІ 402 пам'яті Таблиця 7 Визначення с при заданому параметрі а а= с4 = ас4 = 2 1 2 = 2mod 13 5 3 15 = 2 mod 13 6 9 54 = 2 mod 13 => ас = 2 mod 13 Випадок b а є NQ і а є (2 * Q) Таблиця 8 Визначення с при заданому параметрі а а= & = ас 7 9 63 = -2 mod 13 = 8 3 24 = -2 mod 13 = 11 1 11 --2 mod 13 =>ас =-2mod13 Отриману описаним чином еліптичну криву у другій формі (блок 103) використовують для криптографічної обробки На фіг 2 зображено можливості для вибору простого числа р для вкорочення параметра а (блок 201), як описано вище Можливість 202 задає р таким, що р = 3 mod 4 В цьому разі параметр а можна вкоротити з використанням описаного вище підходу Те ж дійсне для р = 1 mod 4 (випадок 203), причому, цей випадок має два варіанти р = 5 mod 8 (випадок 204) і р = 1 mod 8 (випадок 205) Закриті формули для визначення вкороченого параметра а наведені вище Фіг 2 виразно ілюструє вибір можливостей без намагання здійснювати широкий вибір На фіг 3 у першому кроці 301 задають еліптичну криву з параметрами а, Ь, р і КІЛЬКІСТЮ ТОЧОК ZP згідно з рівнянням (1) У кроці 302 еліптичну Параметри еліптичної кривої записані у захищеній ДІЛЯНЦІ 402 або у не захищеній ДІЛЯНЦІ 403 пам'яті Наприклад, у захищеній ДІЛЯНЦІ пам'яті може бути записаний секретний або особистий код, а у незахищеній ДІЛЯНЦІ пам'яті - відкритий код На фіг 5 зображено обчислювальний вузол 501 Обчислювальний вузол 501 містить процесор CPU 502, запам'ятовуючий пристрій 503 і інтерфейс 504 введення/виведення даних, який через вихідний інтерфейс 505 обчислювального вузла 501 може бути використаний різним чином через графічний інтерфейс може здійснюватися виведення даних на монітор 507 і/або на принтер 508 Введення даних здійснюється за допомогою мишки 509 або клавіатури 510 Крім того, обчислювальний вузол 501 оснащено шиною 506, яка забезпечує зв'язок між запам'ятовуючим пристроєм 502, процесором 502 і інтерфейсом 504 введення/виведення даних До того ж, до шини 506 можна приєднати додаткові компоненти додатковий запам'ятовуючий пристрій, накопичувач на жорсткому магнітному диску і т п Список літератури 1 Neal Kobhtz A Course in Number Theory and Cryptography, Springer Verlag New York, 1987, ISBN 0-387-96576-9, Seiten 150-179 2 Alfred J Menezes Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Massachusetts 1993, ISBN 0-7923-9368-6, Seiten 83-116 3 Rudolf Lidl, Harald Niederreiter Introduction to finite fields and their applications, Cambridge University Press, Cambridge 1986, ISBN 0-52130706-6, Seiten 15, 45 4 Chnstoph Ruland Informationssicherheit in Datennetzen, DATACOM-Verlang, Bergheim 1993, ISBN 3-89238-081-3/Seiten 73-85 11 12 57827 ФІГ. З Вибір еліптичної кривої з а, Ь, р s КІЛЬКІСТЮ точок ZP Трансформація першої форми у другу форму Трансформація еліптичну криау з a', b1, p І КІЛЬКІСТЮ точок ZP Вкорочення параметра другої форми Запис друга! форми для криптографічне^ обробки ФІГ 4 404 . ї ЇНТЕРФЕИС 1 Переносний засіб 4G1 Комп'ютерна верстка Е Гапоненко Підписано до друку 05 08 2003 Тираж39 прим Міністерство освіти і науки України Державний департамент інтелектуальної власності, Львівська площа, 8, м Київ, МСП, 04655, Україна ТОВ "Міжнародний науковий комітет", вул Артема, 77, м Київ, 04050, Україна