67953

Джерела ключів асиметричних криптосистем та їх властивості

Практическая работа

Информатика, кибернетика и программирование

У стовпці 1 наведено число бітів ключа для блочного симетричного шифру. У стовпці 2 подано алгоритми симетричних криптографічних перетворень. У стовпці 3 поданий мінімальний розмір параметрів для крипто перетворень(стандартів0, що ґрунтуються на перетвореннях у кінцевих полях.

Украинкский

2014-09-16

95.28 KB

1 чел.

                                            Практичне заняття №4 (3.3)

                                                з дисципліни «ПРИКЛАДНА КРИПТОЛОГІЯ»

                                                                  Тема заняття

                                Джерела ключів асиметричних криптосистем та їх властивості

                                                     Навчальні питання ПЗ

4.1 Основні теоретичні положення відносно ключів  асиметричних криптосистем

4.1.1 Загальні відомості про ключеві дані

          В таблиці 9.1 наводиться опис ключів для асиметричних криптосистем.      У таблиці 9.2 наведено результати порівняння ключів( по стійкості) для визнаних крипто перетворень, що знайшли застосування в національних, регіональних та  міжнародних стандартах [12,173]. У стовпці 1 наведено число бітів ключа для блочного симетричного шифру. У стовпці 2 подано алгоритми симетричних криптографічних перетворень. У стовпці 3 поданий мінімальний розмір параметрів для крипто перетворень(стандартів0, що ґрунтуються на перетвореннях у кінцевих полях. Прикладами таких алгоритмів можуть бути FІPS 186-3 та ГОСТ 34.310-95 – для цифрових підписів, а також алгоритм Діффі - Геллмана (DH) і алгоритм узгодження ключів MQV, як визначено в [46, 119–120], де Lв – розмір відкритого ключа, а Lо – розмір особистого ключа. У стовпці 4 подано значення k (розмір модуля перетворення) для криптографічних перетворень, що ґрунтуються на складності вирішення задач факторизації, наприклад RSA алгоритм ANSX9.31 і PKCS#1. Посилання на ці специфікації подані у FІPS 186-3 для цифрових підписів. Значення k зазвичай використовують для того, щоб указати розмір ключа. У стовпці 5 наведено порядок базової точки для криптографічних перетворень у групі точок еліптичних кривих для встановлення ключів у [119–120]. Значенням f позначено розмір ключа (порядок базової точки n = 2).

    В таблиці 9.9. наведені аналогічні дані відносно направленого шифрування в кільці зрізаних поліномів та для функцій гешування. Там же, тобто в в таблиці 9.3, наведені дані відносно [  ] строків їх застосування, що рекомендуються.  

Таблиця 9.1 - Асиметричні криптографічні перетворення для реалізації направленого  шифрування

Параметри НШ/

Математичний апарат

Особистий ключ НРШ

Відкритий ключ НЗШ (сертифікат)

Асиметрична пара (ключ)

Загальні параметри

крипто перетворення

Сертифікати

Складність крипто аналізу

НШ  в кільці (RSA)

Di

Ei

(Di , Ei)

N = P Q

Еi

Субекспоненційна

НШ в полі Галуа F(P) 

Хi

Yi=gXi(mod P)

(Xi, Yi)

P, q, g

Yi

Субекспоненційна

НШ в групі точок еліптичних кривих Е(F(q))

di

Qi=di G(modq)

(di, Qi)

a, b, G, n, f(x)(P), h

Qi

Експоненційна

НШ в гіпереліптичних кривих

Сi

D2= ci D1

(ci, D2)

f(x), g(x), q, D1, g, J

D2

Експоненційна

НШ зі спарюванням точок еліптичних кривих

diD =s QiD

QiD=H1 (ID)

(diD, QiD)

G1, G2, e, H1, P, H2, H3,

F2m, Pp

QiD

Експоненційна – субекспоненційна

НШ в кільці зрізаних поліномів (NTRU)

f = 1+pF (modq)

h= f  1*g*p(modq)

(f, h)

N, q, p, f, g ,df, dg, c

Експоненційна – субекспоненційна

Таблиця 9.2 

Порівняння стійкості стандартизованих асиметричних крипто перетворень

Рівень стійкості, в бітах

Симетричні

Оцінка часу крипто аналізу, MIPS-years

Геш функції

Параметри асиметричних перетворень

DSA 

RSA 

EC-DSA 

IBE 

(BF, BB1) 

NTRU 

До 2010 р. (мін. 80 біт стійкості)

2TDEA

3TDEA

AES-128

AES-192

AES-256

109 

SHA-1,

SHA-224,

SHA-256,

SHA-384,

SHA-512

Min.: 

L = 1024; 

N =160 

Min.: 

k=1024 

Min.: 

f=160

Min.: 

p = 512 

q = 160 

N =263

q =2048

df = 113

До 2030 р.

(мін. 112 біт стійкості)

3TDEA 

AES-128 

AES-192 

AES-256 

1017 

SHA-224,

SHA-256,

SHA-384,

SHA-512

Min.:

L = 2048

N = 224

Min.:

k=2048

Min.:

f=224

Min.: 

p = 1024 

q = 224 

N =401

q =2048

df = 113

Після 2030 

(мін. 128 біт стійкості) 

AES-128 

AES-192 

AES-256 

1023 

SHA-256,

SHA-384,

SHA-512

Min.:

L = 3072

N = 256

Min.:

k=3072

Min.:

f=256

Min.: 

p = 1536 

q = 256 

N =449

q =2048

df  = 134

Рівень стійкості 192 біта

AES-192 

AES-256 

1041 

SHA-384,

SHA-512

Min.:

L = 7680

N = 384

Min.:

k=7680

Min.:

f=384

Min.: 

p = 3840 

q = 384 

N =677

q =2048

df = 153

Рівень стійкості 256 біта

AES-256 

1063 

SHA-512

Min.:

L = 15360

N = 512

Min.:

k=15360

Min.:

f=512

Min.: 

p = 7680 

q = 512 

N =1087

q =2048

df = 120

Таблиця 9.3

 Алгоритми і параметрb NTRU  , що рекомендуються

Обмеження дії

Рівень безпеки

Блоковий шифр

Функція гешування

Множина параметрів NTRU Х9.98 [  ]

2030

112-біт

Triple-DES (тільки  3 ключі), AES-128, AES-192, AES-256

SHA-224, SHA-256, SHA-384, SHA-512

ees401ep1, ees541ep1, ees659ep1

2031 і пізніше

128-біт

AES-128, AES-192, AES-256

SHA-256, SHA-384, SHA-512

ees449ep1, ees613ep1, ees761ep1

192-біт

AES-192, AES-256

SHA-384, SHA-512

ees677ep1, ees887ep1, ees1087ep1

256-біт

AES-256

SHA-512

ees1087ep2, ees1171ep1, ees1499ep1

4.1.2 Генерування ключів в системі RSA

Генерування асиметричної ключової пари. Система RSA відноситься до криптосистем з відкритими ключами. В цій системі ключі ЕkDk, причому один з них має бути особистим, а другий – відкритим. Наприклад, Еk – особистий, а Dk – відкритий, якщо вони використовуються для ЕЦП і навпаки, якщо використовуються для направленого шифрування.

Усі параметри (N,P,Q) також поділяються на 2 класи: N – відкритий, P,Q – конфіденційні (секретні).

Сутність забезпечення моделі взаємної недовіри – кожен користувач генерує ключі сам собі. Особистий ключ залишає в себе і забезпечує його строгу конфіденційність. Відкритий ключ розсилає всім користувачам, з якими він зв'язаний. Користувач також забезпечує цілісність і дійсність відкритих ключів.

Еk, Dk – мають вибиратися з повної множини випадково, порівняно ймовір-
но і незалежно, мають забезпечувати однозначну оборотність прямого та зворотного перетворення. Відповідним чином засвідчений відкритий ключ є сертифікатом (див.
п. 1.1.1).

Значення Еk, Dk для практичних використань мають задовольняти умову

,

де

.

Порівняння (1.54) можна звести до Діафантового рівняння:

ax+by=1.                                                       (9.9  1.56)

Це діафантове рівняння – нормоване, тому що справа коефіцієнт дорівнює 1; a, b – цілочисельні коефіцієнти, х, у – невідомі. Порівняння (9.7  1.54) можна подати у вигляді:

,                                          (9.10  1.57)

k – деяке невідоме число.

Діафантове рівняння (9.9 1.56) має цілочисельне розв’язання, якщо a і b цілочисленні, і , a і b взаємно прості. Подавши (9.10 1.57) у вигляді

,    (9.11  1.58)

отримаємо а=(N), x=(k), b=Ek, y=Dk .

Якщо Ek сформувати випадково, то а та b – відомі числа, а х та y – невідомі, що підлягають визначенню.

Найбільш швидке розв’язання (9.11 1.58) дає застосування ланцюгових дробів, які дозволяють визначити х та у як

,                                          (9.12  1.59)

де  – порядок ланцюгового дробу, a і b – параметри ланцюгового дробу.

Знаходимо параметри:

a/b подається у вигляді ланцюгового дробу

,                                  (9.13  1.60)

μ - порядок ланцюгового дробу, перший коефіцієнт, у якого залишок дорівнює 0.

Значення (а0,b0) та (а1,b1) визначаються як

                                     ,

               .

Значення (а2,b2), (а3,b3) і т.д. визначаються рекурентно відповідно до правил

 .                                          (9.14  1.61)

Середнє число ітерацій в (1.60), тобто , можна визначити як [16]

.

4.1.3  Генерування ключів в системі DSA

Нехай є просте поле Галуа F(p). Третя довірена сторона генерує загальні параметри , де - просте, як правило «сильне» просте число,  а - первісний елемент. Далі всі користувачі  генерують випадково по принципу « сам – собі» - особисті ключі і зберігають їх як таємні, де

                                     i.                                                                  (3.18)

Потім кожен  формує відкриті ключі, використовуючи загальносистемні параметри , тобто  кожен із  користувачів обчислює свій відкритий ключ

                                                                                                            (3.19   2)  

         

Кожний первісний елемент породжує поле ізоморфізмів поля Галуа

                       .

Приклад генерування ключів для двох користувачів наведений в таблиці 3.6

Таблиця 3.6

Генерування асиметричної пари ключів у полі Галуа

А

В

ХА

ХВ

Відкритий ключ сертифікують, тобто виготовляють сертифікат відкритого ключа  

            ,                                                                         (3.20  3)

де - особистий ключ сертифікації третьої довіреної сторони.

Створюється база всіх сертифікатів і до неї добавляється ключ сертифікації центра, разом з загальними параметрами.

                                                                                  (3.21 4)

4.1.4 Генерування ключів в групі точок ЕК

Генерація ключів еліптичної кривої

Для заданого дійсного набору параметрів еліптичної кривої особистий ключ і відповідний відкритий ключ можуть бути генеровані таким чином:

Вибирається випадкове або псевдовипадкове ціле d на відрізку [2, n–2], яке має бути захищене від несанкціонованого розкриття й бути непередбачуваним.

Обчислюється точка

P = (xP, yP) = dG.                                                          (1.31)

Як ключова пара вибирається (P, d), де P – відкритий ключ, і d – особистий ключ.

У деяких застосуваннях відкритий ключ обчислюється як e G, за умови, що de = 1 mod n.

                                   4.2    Приклади розв’язку задач до 3 розділу

Задача 3.11.3 Зашифруйте  направлено та розшифруйте повідомлення М   застосовуючи RSA  та використовуючи дані відносно параметрів та ключів, що наведені в таблиці 3.11.3.1. Ключову пару генеруйте знаючи один із ключів, що наведений в останній строчці таблиці 3.11.3.1.

Таблиця 3.11.3.1 – Параметри та ключі до задачі 3.11.3.

N

1

2

3

4

5

6

7

8

9

10

Mi

3

4

2

2

3

2

3

2

3

4

Pп

29

11

11

11

23

7

29

17

19

19

Qп

11

17

23

13

17

23

7

7

7

11

Ej /Dj

-/7

-/11

-/3

-/5

-/3

7/-

11/-

13/-

5/-

3/-

Розв’язок.

Розв’яжемо задачу для варіанта № 9: Mi = 3, Pn = 19, Qn = 7, Ej = 5.

  1.  Як відомо, у RSA-криптосистемі відкритий і особистий ключі зв’язані наступним співвідношенням:

ED  1 (mod ((N)))                                                                                         (1)

Знайдемо значення N та функції Ойлера від N:

N = PQ = 197 = 133; (N) = (P-1) (Q-1) = 618 = 108.

Необхідно розв’язати рівняння (1) відносно D:

5D  1 (mod 108).

Представимо рівняння у вигляді:108x + 5y = 1.

Розв’яжемо його методом ланцюгових дробів.

Кількість кроків  = 3.

y = Dj= =  = -.

=  = 21;

=  + 1 = 211 + 1 = 22;

=  +  = 221 + 21 = 43;

=  +  = 432 + 22 = 112.

y = - 43 mod 108 = 65  Dj = 65.

Зробимо перевірку, підставивши Dj у рівняння (1):

565  1 (mod 108);

325  1 (mod 108);

1 1 (mod 108).

  1.  Виконаємо направлене зашифрування і розшифрування повідомлення Mi = 3.

Задача 3.11.8 Знайдіть відкритий ключ Y асиметричної пари (x, Y) в скінченному полі GF(23) , якщо первісний елемент  М=15,  а особистий ключ х = 20.

Розвязок

 Спочаткуперевіримо, чи є М=15 первісним елементомGF(23). Для цього він повинензадовільняти вимогам:

  1.  або     ;
  2.   , де а – один з множників канонічного розкладу числа Р.

Проведеморозрахунки для заданихзначеньР та М:

 -   перша умовавиконується. Далізнайдемоканонічнийрозклад числа Р та перевіримо другу умову:

23 - 1 = 22 = 2 ∙ 11- отже, а1 = 2 і а2 = 11.

Таким чином умов 2 такожвиконується, а, отже, М – первіснийелемент у поліGF(23)/

Відкритий ключ Yасиметричної пари (x, Y) можна знайти за формулою Y = МХmodN. Підставимо задані значення M, x та N:

Y = 1520mod23 =  332525673007965087890625mod 23 =  9

 ЗАДАЧА  3.11.11 Зашифруйте та розшифруйте повідомлення М=(13,17), використовуючи направлений шифр в групі точок ЕК, якщо Р=23, a=1, b=1 (крива y2=(x3+x2+1)mod23), G=(17,20), n=7.

Решение:

Отправитель сообщения выбирает случайное (k=3).

Расчитывают одноразовый открытый ключ

C1=k*G=3*(17;20)

λ=(3+a)/2y1(mod 23)=(3*17*17+1)/40(mod 23)=848/40(mod 23)=1

      2G=(13;7)

λ=(y2-y1)/(x2-x1)(mod 23)=(7-20)/(13-7)(mod 23)=9

      3G=(5;19)

Одноразовый открытый ключ=(5;19)

Q=d*G-открытый ключ получателя

d-долговременный собственный ключ (d=2)

Q=2G=2*(17;20)=(13;7)

C2=M+k*Q=(13;7)+3*(13;7)

2(13;7)=(5;4)


3(13;7)=(17;3)

Получателю посылают открытый ключ  и зашифрованный текст

Расшифрование :

Получатель вычисляет d*= 2(5;19)

- d*= (11;22)- (17; 3)= (11;22)+(17;-3)=(11;22) + (17;20)

ЗАДАЧА 3.11.12.

Сформуйте пропозиції та реалізуйте алгоритм направленого шифрування в групі точок еліптичних кривих, якщо порівняння кривої має вигляд:

y2=(x3+x+6)mod11, G=(2,7),

особистий ключ хi=7.

Знайдіть відкритий ключ Аi користувача. Виробіть криптограму СМ , якщо М=(10,9), k=3. Сформуйте пропозиції та здійсніть розшифрування криптограми СМ.

Розв’язок задачі

Направлене шифрування повідомлення М буде здійснюватися наступним чином:

С2 = M + kQ

де k — сеансовий ключ (обирається випадково при початку нового сеансу)

Q — відкритий ключ користувача А, котрому адресується повідомлення.

Також обчислюється відкритий ключ сеансу:

С1 = kG

де G — базова точка.

Таким чином криптограма складається з двох точок на еліптичній кривій: (С1, С2).

Розшифрування відбувається наступним чином:

Користувач А, котрому була адресована криптограма впевнюється, що пара точок (С1, С2) належать еліптичній кривій. Далі отримується початкове повідомлення як:

M’ = C2 - dC1 = M + kQ - dkG = M + kdG - dkG = M

Таким чином криптоперетворення є зворотнім та однозначним.

Тепер нехай рівняння кривої має вигляд y2 = x3+x+6, а базова точка G=(2,7).

Здійснимо шифрування повідомлення М = (10,9) згідно алгоритму, наведеного вище, використовуючи ключ сеансу k=3. Розрахуємо відкритий ключ абонента:

Q = dG = 7(2, 7) = (7, 2)

Далі зашифруємо повідомлення:

C2 = M+kQ = (10, 9) + 3(7, 2) = (10, 9) + (3, 5) = (10, 2)

А також відкритий ключ сеансу:

C1 = kG = 3(2, 7) = (8, 3)

Таким чином, зашифроване повідомлення представляє собою пару точок (С1, С2) = ((8, 3), (2, 7)).

Тепер розшифруємо повідомлення:

M’ = C2 - dC1 = (10, 2) - 7(8, 3) = (10, 2) - (3, 5) = (10, 9)

Як видно, М та М’ співпадають, отже розшифрування відбулося вірно.

4.3 Задачі для самостійного розв’язку

ЗАДАЧА 3.11.6. В RSA системі відкритим ключем  направленого зашифрування  є число EJ=47, а модуль перетворення N = 11303. Знайдіть особистий ключ розшифрування DJ.

ЗАДАЧА 3.11.12.   Обґрунтуйте  пропозиції та реалізуйте алгоритм направленого шифрування в групі точок еліптичних кривих, якщо рівняння кривої має вигляд:

y2=(x3+x+6)mod11, G=(2,7), особистий ключ ni=7. Знайдіть відкритий ключ Аi користувача.

Виробіть криптограму С(М) , якщо М=(10,9), k=3. Зробіть пропозиції та здійсніть розшифрування криптограми С(М).

ЗАДАЧА 3.11.17. Зашифруйте та розшифруйтеповідомлення М = (562, 201), використовуючи направлений шифр в групіточок ЕК, якщоР=751, а= -1, b=188, крива  y2 =(x3-x+188) (mod751), G = (0, 376 ).

Задача 3.11.19 Знайдіть відкритий ключ Y асиметричної пари (x, Y) в скінченому полі. Відомо, що відкритий ключ користувача , - базова точка, що належить еліптичній кривій  . Порядок точки , порядок ЕК , де кофактор. Необхідно знайти відкритий ключ із порівняння

,

тобто в нашому випадку порівняння

.

ЗАДАЧА 3.11.20. В таблиці 3.11.20.1 наведені  аналітичні вирази для оцінки складності  основних операцій у групі точок еліптичної кривої, де через   позначено операції множення, зведення до другого ступеня та інвертування елементу скінченого поля,  над яким задана еліптична крива. Порівняйте складність додавання та подвоєння в указаних системах координат та розробіть відповідні пропозиції.

Таблиця 3.11.20.1 - Складність  основних операцій у групі точок ЕК

Система координат

Додавання

Подвоєння

Афінна

Проективна

Якобієва

                                         4.4 Контрольні запитання

3.11.1 Яка особливість ключових даних асиметричних криптоперетворень?

3.11.2 Дайте характеристику та обґрунтуйте вимоги до RSA ключової пари?

3.11.3  Дайте характеристику та обґрунтуйте вимоги до DSA ключової пари?

3.11.4 Дайте характеристику та обґрунтуйте вимоги до ключової пари крипто перетворення в групі точок еліптичної кривої?

3.11.5 Дайте характеристику та обґрунтуйте вимоги до  ключової пари для крипто перетворення в кільці зрізаних поліномів?

3.11.6 Дайте характеристику та обґрунтуйте вимоги до  ключової пари для крипто перетвореня зі спарюванням точок еліптичних кривих?

3.11.7 Для чого застосовується криптографічне перетворення типу направлене шифрування та які особливості використання ключів при зашифруванні та розшифруванні?

3.11.8  Дайте визначення та поясніть особливість застосування одиниці вимірювання складності криптоаналізу MIPS-рік, яке її фактичне значення?

3.11.9 Чому асиметричні крипто перетвореня вважають ймовірно стійкими?

3.11.10 Які вимоги до прямого  асиметричного  криптографічного  перетворення типу НШ  та з використанням якого ключа воно виконується?

3.11.11 Які вимоги до зворотного  асиметричного  криптографічного  перетворення типу НШ  та з використанням якого ключа воно виконується?

3.11.12 З якою довжиною може бути використана для НШ ключова RSA(DSA) пара для направленого шифрування інформації нині?

3.11.1З З якою довжиною може бути використана для НШ  ключова ЕС  пара для направленого шифрування інформації нині?

3.11.14 Порівняйте криптографічне RSA та DSA перетворенн між собою,які переваги вони мають перед іншими?

3.11.15 Порівняйте криптографічне RSA та ЕС перетворенн між собою, які переваги вони мають перед іншими?

3.11.16  Порівняйте криптографічне криптографічне перетвореня в групі точок еліптичної кривої з перетворенням в кільці зрізаних поліномів, які переваги має перетворення   в кільці зрізаних поліномів?

3.11.17 Які основні вимоги до генерування ключових даних  для асиметричних крипто перетворень?


 

А также другие работы, которые могут Вас заинтересовать

14134. Формування зображення на екрані ПЕОМ. Створення найпростіших лінійних програм 66.5 KB
  Тема уроку: Формування зображення на екрані ПЕОМ. Створення найпростіших лінійних програм Мета уроку: Дати дитині поняття про режими роботи монітору та принципи виведення зображення на екран в цих режимах.Тип уроку: Лекційний з практичними прикладами. Лекційний мате...
14135. Створення найпростіших лінійних програм 27 KB
  Тема уроку: Створення найпростіших лінійних програм Мета уроку: Дати дитині поняття про режими роботи монітору та принципи виведення зображення на екран в цих режимах.Тип уроку: Практична робота. На початку уроку необхідно нагадати дітям правила поведінки в комп'юте
14136. Розвязування задач з лінійними алгоритмами 61 KB
  Тема уроку: Розвязування задач з лінійними алгоритмами Мета уроку: Навчитися розвязувати прості задачі з лінійними алгоритмами. Тип уроку: Практична робота. На початку уроку необхідно нагадати дітям правила поведінки в компютерному класі та правильної роботи за к
14137. Вказівка розгалуження та її опис мовою програмування. Опис умов 40.5 KB
  Тема уроку: Вказівка розгалуження та її опис мовою програмування. Опис умов. Мета уроку: Дати поняття про структурні оператори вказівку розгалуження повну та скорочену форми та поняття про прості та складені умови.Тип уроку: Лекційний з практичними прикладами. Лекц
14138. Запис алгоритмів з використанням вказівки розгалуження мовою програмування 63.5 KB
  Тема уроку: Запис алгоритмів з використанням вказівки розгалуження мовою програмування. Мета уроку: Навчити складати алгоритми з використанням команди розгалуження та записувати їх мовою програмування.Тип уроку: Розбір задач що потребують для свого розв'язання вказ
14139. Запис алгоритмів з використанням вказівки розгалуження мовою програмування 70.5 KB
  Тема уроку: Запис алгоритмів з використанням вказівки розгалуження мовою програмування. Мета уроку: Навчити створювати математичні моделі задач складати алгоритми з використанням команди розгалуження та записувати їх мовою програмування.Тип уроку: Розбір задач що
14140. Запис алгоритмів з використанням вказівки розгалуження мовою програмування 69.5 KB
  Тема уроку: Запис алгоритмів з використанням вказівки розгалуження мовою програмування. Мета уроку: Навчити складати алгоритми з використанням команди розгалуження та записувати їх мовою програмування.Тип уроку: Розбір більш складних задач що потребують для свого р
14141. Вказівка повторення та її опис мовою блок-схем та мовою програмування 48.5 KB
  Тема уроку: Вказівка повторення та її опис мовою блоксхем та мовою програмування. Мета уроку: Дати поняття про вказівку повторення та її використання при розвязуванні задач про типи циклів та їх оформлення мовою програмування Паскаль та мовою блоксхем. Тип уроку: Лек
14142. Використання циклу з параметром для розвязування задач 66.5 KB
  Тема уроку: Використання циклу з параметром для розвязування задач. Мета уроку: Навчити використовувати цикл з параметром для розвязування типових задач. Тип уроку: Практичний. На початку уроку рекомендується провести письмове опитування можна у вигляді диктанту