67181

Асиметричні криптоперетворення та їх застосування для забезпечення конфіденційності

Лекция

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

Найбільшою особливістю асиметричних перетворень є використання асиметричної пари ключів, які містить відкритий ключ, що відомий всім, та особистого ключа, що пов’язаний з відкритим ключем за допомогою певного математичного перетворення.

Украинкский

2014-09-04

240.65 KB

12 чел.

6

ПРИКЛАДНА КРИПТОЛОГІЯ

ЛЕКЦІЯ №10(3.1)

Тема лекції

« Асиметричні крипто перетворення та їх застосування  

            для забезпечення конфіденційності »

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

10. 1 Перелік та загальна характеристика асиметричних крипто перетворень

10.2 Етапи створення і розвитку асиметричних крипто перетворень НШ.

10.3 Крипто перетворення НШ в кільцях (RSA)

10.4 Проблемні питання крипто перетворень типу RSA.

Додаток А  Асиметричні крипто алгоритми. Приклади розв’язку задач та
задачі для самостійного розв’язання

Джерела, що рекомендуються  до самостійної роботи

  1.  Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Монографія (електронний варіант). Харків, ХНУРЕ, 2011 р.
  2.  Горбенко І.Д., Горбенко Ю.І. Прикладна криптологія. Електронний конспект лекцій. Харків, ХНУРЕ, 2011 р.
  3.  Горбенко І. Д. Гриненко Т. О. Захист інформації в інформаційно-телекомунікаційних системах: Навч. посібник. Ч.1. Криптографічний захист інформації - Харків: ХНУРЕ, 2004 - 368 с.
  4.  Горбенко Ю.І., Горбенко І.Д. Інфраструктури відкритих ключів . Системи ЕЦП. Теорія та практика. Харків.  Форт. 2010 , 593с.

Додаткова лтература

1.В. Задірака . Компьютерная криптологія. Підручник. К, 2002 ,504с.

2. А. Менезис, П. Ван Аршот, С. Ватсон. Руководство по прикладной криптографии CRC Press, 1997, электронная копия, 662 с

10. Брюс Шнайер. Прикладная криптография. М., изд. Триумф. 2002 г., 797 с

        

       Найбільшою особливістю  асиметричних перетворень є використання асиметричної пари ключів, які містить відкритий ключ,що  відомий всім, та особистого ключа, що пов’язаний з відкритим ключем за допомогою певного математичного перетворення. При цьому вважається що обчислення особистого ключа, при знанні загальносистемних параметрів та відкритого ключа, повинно мати в гіршому випадку субекспоненційну складність, за умови коли  обчислення відкритого ключа при формуванні асиметричної ключової пари – поліноміальну. Зрозуміло що вказана особливість несе в собі як переваги так і недоліки, що і є предметом розгляду в цьому розділі

10. 1 Перелік та загальна характеристика асиметричних крипто перетворень

   

 З урахуванням викладеного в 2 розділі, важливим подальшому викладенні є визначення криптографічної стійкості асиметричного направленого шифрування, перше за все у порівняння зі стійкістю блочних симетричних шифрів. Такий підхід є загальновизнаним і широко застосовується  на практиці. В таблиці 10.1 подаються  рекомендації [11, 12, 63, 115, 119, 130, 163, 165 ] з оцінки криптографічної стійкості  асиметричних крипто перетворень, що наведені в таблиці 2.2.

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

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

     Необхідно відмітити, що до цих таблиць ми ще будемо не один раз будемо звертатись для порівняння того чи іншого крипто перетворення та алгоритмів ( стандартів),  які на їх основі будуть реалізовуватись. Дані в таблицях можна розглядати і як певну класифікацію асиметричних крипто перетворень , а також порівняння їх стійкості проти атаки повне розкриття по відношенню до блокових симетричних шифрів. Більш детально ці питання розглядаються нижче.

Таблиця 10.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

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

Таблиця 10.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

Таблиця 10.3

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

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

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

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

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

Множина параметрів NTRU Х10.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

10.2 Етапи створення і розвитку асиметричних крипто перетворень НШ.

Історично першою у 80-і роки ХХ століття широке розповсюдження отримали асиметричні крипто перетворення(криптосистема) з відкритими ключами, що нині  відома як RSA [12-15] система. Розробниками RSA системи вважають Рона Рівеста, Аді Шаміра і Леонарда Адлемана, в підручнику „Фізика квантової інформації”, авторів Д. Бауместер, А. Екерт, А. Цайлингер на стор. 37-38[  ] стверджується, що в Англії RSA подібний алгоритм було винайдено на декілька років раніше. 

Основною особливістю RSA крипто системи є її асиметричність, коли  ключ зашифрування Кз не співпадає з ключем розшифрування Кр, тобто

,                                                         (10.1)

а знайти один ключ при відомому другому для відповідних значень загальносистемних параметрів можна не нижче ніж з суб експоненційною складністю. Хоч на сьогодні RSA криптосистема піддається нападкам і відносно неї даються різні прогнози, але вона проіснувала майже  35років і дозволяє реалізувати НШ. Крім того, на наш погляд, RSA система дозволяє якісно реалізувати криптографічними методами таку основну функцію, як спостережливість, в змісті причетності відправника та отримувача. Так причетність відправника може бути забезпечена за рахунок здійснення цифрового підпису з використанням особистого (таємного) ключа, а перевірка цілісності та справжності підписаної інформації здійснюються з використанням особистого (публічного) ключа. Далі направлене шифрування може бути здійснене з використанням другої ключової пари, відкритий ключ отримувача якої застосовують для направленого шифрування, а особистий ключ застосовується для розшифрування повідомлення. Тому розглянемо цю класичну систему докладно.

Для великих з великими простими множниками розкладання на множники є серйозною проблемою, але не настільки, як потрібно. Разючою ілюстрацією цього може служити наступна історія[  ].

У 1977 році винахідники алгоритму RSA наважилися запропонувати читачам популярного журналу Scientific American розкрити шифроване повідомлення, яке вони розмістили в розділі «Математичні ігри» Мартіна Гарднера (Martin Gardner). За розшифровку цього повідомлення вони запропонували нагороду в 100 дол. За їхніми оцінками, задача не могла бути вирішена раніше, ніж приблизно через 40 квадрильйонів років [10,18]. Але в квітні 1994 року група користувачів Internet зажадала виплати призової суми після всього восьми місяців спільної роботи в Internet. У запропонованій задачі використовувався відкритий ключ довжиною в 129 десяткових знаків (довжина модуля N), що дорівнює приблизно 428 бітам. З квітня 1996 р. до квітня 2003 р. були вирішені задачі для RSA-130 [18], RSA-140, RSA-155, RSA-160. RSA-150 залишився не факторизованим та в подальшому відкликаний із переліку задач. Важливою  з вирішених задач є задача для RSA-576, у якій довжина ключа дорівнює 576 бітів. За вирішення цієї задачі команда отримала 10000 дол. Відповідні результати наведені в  табл. 10.4. Одиницею вимірювання складності задачі в даному випадку є MIPS-рік – обсяг роботи, виконуваної протягом року процесором, що здійснює обробку одного мільйона команд у секунду, що приблизно еквівалентно виконанню 3*1013 команд. Так, машина на базі Pentium з частотою 2000 МГц показує швидкість 500 MIPS.

Число десяткових знаків

Приблизне число бітів

Дата вирішення

Необхідне число MIPS-літ

Використаний алгоритм

100

332

1991 р.

7

Квадратичне решето

110

365

1992 р.

75

Квадратичне решето

120

398

1993 р.

830

Квадратичне решето

129

428

1994 р.

5000

Квадратичне решето

130

431

1996 р.

500

Загальне решето числового поля

140

464

1999 р.

Загальне решето числового поля

153

512

1999 p.

8000

Загальне решето числового поля

155

514

1999 р.

Загальне решето числового поля

160

531

2003 р.

Загальне решето числового поля

174

576

2003 р.

Загальне решето числового поля

199

663

2005

1.28 105

Загальне решето числового поля

232

768

2009

4 106

Загальне решето числового поля

270

896

Відкритий

309

1024

Відкритий

463

1536

Відкритий

617

2048

Відкритий

Для порівняльного аналізу в таблиці 10.5  результати досягненm в області крипто аналізу з зазначенням довжини ключа, часу, який був витрачений на здійснення крипто аналізу та року  коли було здійснено крипто аналіз. Одиницею виміру тимчасова складність в  MIPS-Year та просторова складність у вигляді обсягу  пам’яті, що  була використана в процесі здійснення крипто аналізу[7].

Таблиця 10. 5

Досягнення  в здійсненні крипто аналізу  відносно асиметричних криптосистем

Рік

Довжина ключа, біт

Час,MIPS-Year

Пам'ять ОЗУ/HDD, Гб

RSA

1999

512

8000

0,064/2,3

2005

663

0,128*106

1/35

2009

768

4*106

5/1000

DSA

2001

607

20000

0,256 /5

2011

907

2,775*108

1/35*

EC-DSA

2001

109

13100

1/400

2009

112

36557

0,512/600

NTRU

2009

N = 167

2*106

2/150

Наведені в табл.. 10.5 дані підтверджують, що асиметричні крипто перетворення скоріше є  ймовірно стійкими, розвиток спеціальних розділів математики та збільшення потужності крипто аналітичних систем дозволяють компрометувати їх з часом. Як правило,  виходом із такої ситуації є  збільшення розмірів загальних параметрів та ключів, або заміна більш стійкими крипто перетвореннями[  ].

Наведені в таблиці 10.5 фактичні дані також відображають і етапи на основі асиметричних перетворень і створення та розвитку асиметричних криптосистем. Детально ці питання розглядаються в 9 розділі.

 

  Необхідно відмітити, що згідно вимог нормативних документів та міжнародних стандартів в інформаційних технологіях повинні надаватися послуги причетності джерела та одержувача інформації (спостережливість). Причетність джерела, тобто авторство може бути забезпечено за рахунок застосування ЦП. Складніше забезпечити причетність одержувача. Ця задача може бути розв’язана за рахунок використання направлених шифрів.

Особливістю  крипто перетворень типу НШ є такі:

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

зворотне криптографічне перетворення виконується з використанням особистого ключа .

Ключова пара (К, К) повинна бути випадковою та вибиратись із повної множини дозволених для використання ключових пар, причому  

  (1)

Згідно вимог нормативних документів та міжнародних стандартів в інформаційних технологіях повинні надаватися послуги причетності джерела та одержувача інформації (спостережливість). Причетність джерела, тобто авторство може бути забезпечено за рахунок застосування ЦП. Складніше забезпечити причетність одержувача. Ця задача може бути розв’язана за рахунок використання направлених шифрів.

Особливість крипто перетворень типу НШ:

пряме з використанням відкритого ключа .

зворотне з використанням особистого ключа .

Ключова пара (К, К) повинна бути випадковою та вибиратись із повної множини дозволених для використання ключових пар, причому  

  

Відомий ряд методів побудування Криптографічних систем направленого шифрування. Основними з них є такі:

1)  Метод складання рюкзака [  ]. Необхідно вкласти в рюкзак предмети з різною вагою, але щоб вага рюкзака залишалася постійною. Це не стійка система.

2) У 1978р. була опублікована стаття, у якій був запропонований алгоритм RSA  направленого шифрування . Він закріплений в міжнародному стандарті ISO 11166-1,2. Крім того в США він закріплений в стандарті  ANSI Х10.31.

3) У 1985р. Єль - Гамаль запропонував нову схему НШ Є-Г. Всі ці алгоритми були запатентовані. На сьогодні рекомендовано до застосування стандарти Х10.30 та у міжнародних стандартах ISO/IEC 1170-3  ISO/IEC 15946-10.

 

В

  10.3 Крипто перетворення НШ в кільцях (RSA)

  В 10.2, по суті , розглянуто етапи створення та певні властивості RSA направленого шифру. В цьому підрозділі розглянемо сутність RSA направленного шифру.

Алгоритм направленного шифрування.RSA криптоалгоритм є блоковим, у ньому повідомлення М розбивається на блоки Мi, з довжиною блоку (на сьогодні 2048 біт мінімум), реально 2048, 3072 і більше бітів. Блок криптограма Сі обчислюється за правилом

,  (10.2  1.49)

де – є відкритий ключ прямого перетворення, N – модуль перетворення є добутком виду

,                                                 (10.3   1.50)

де в свою чергу P, Q – великі прості, скоріше сильні, числа.

Якщо  lp є довжина простого числа Р, наприклад в бітах, а lq – довжина простого числа Q, то довжина модуля N

.                                               (10.4    1.51)

Розшифрування блока криптограми здійснюється за правилом:

,                                     (10.5  1.52)

де Dк – є ключ зворотного перетворення, тобто розшифрування .

Однозначність розшифрування можна підтвердити, підставивши (10.5 1.52) в (10.2  1.49). В результаті отримаємо:

.                                         (10.6  1.53)

Оскільки ключова пара пов’язана між собою порівнянням:

,                                          (10.7  1.54)

де є функцією Ойлера від модуля N

= .

Якщо (10.7 1.54) має єдине рішення, тобто існує єдина пара , то такий шифр є однозначним і при таких умовах RSA криптосистема забезпечує однозначне направлене шифрування.

Зазначимо, що з точки зору забезпечення максимально можливої крипто-стійкості прості числа P i Q мають бути сильними в широкому або вузькому значенні [7]. Так просте число Р вважатимемо сильним в широкому значенні, якщо

,   (10.8  1.55)

де R – також велике просте число.

Аналогічно визначається і сильне в широкому значенні просте число Q.

Просте число Р вважається сильним у вузькому значенні, якщо містить в своєму канонічному розкладі велике просте число R, Р+1 містить в своєму розкладі велике просте число S, а крім того R-1 містить в своєму розкладі велике число T.

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

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

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

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

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

,

де

.

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

ax+by=1.                                                       (10.9  1.56)

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

,                                          (10.10  1.57)

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

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

,    (10.11  1.58)

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

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

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

,                                          (10.12  1.59)

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

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

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

,                                  (10.13  1.60)

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

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

                                     ,

               .

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

 .                                          (10.14  1.61)

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

.

Попередня оцінка стійкості. В системі RSA крипто аналіз, метою якого є визначення особистого (таємного) ключа, наприклад Ек ключа ключової пари (), де Dк є відкритий ключ, може бути здійснений таким чином:

  1.  Зловмисник отримує системні параметри (однакові для обох користувачів) та відкритий ключ Ек.
  2.  Використовуючи спеціальну крипто аналітичну систему здійснюється факторизація модуля , в результаті чого він визначає прості числа та .
  3.  Розраховується значення функції Ойлера

 .

  1.  Використовуючи методику, наведену в (1.49), здійснюється розв’язок порівняння .

Взагалі, найбільш простим методом крипто аналізу є підбір ключової пари (), тобто при відомих визначається .

Нехай має довжину тоді, якщо , то

.

Область існування для ключа можна визначити, як всі цілі числа, що не перевищують та є взаємно простими, тобто . Підбір із повної множини є задачею, що набагато складніша, ніж алгоритм, заданий вище пп. 1-4.

Проведені дослідження підтвердили, що необхідний рівень стійкості в RSA забезпечується в тому випадку, якщо прості числа є сильними.

Покладемо, що як використовуються прості числа, тоді справедливе таке: , , .

Використовуючи теорему Чебишева [17], визначимо кількість особистих ключів, як

 .                         (10.15  1.62)

Приклад 1. Визначимо число простих 1024 бітних чисел

.

Щоб розв’язати цю задачу методом тотального перебору не вистачить енергії сонця.

Згідно з сучасними поглядами найбільш перспективними методами крипто аналізу є методи, що базуються на пп. 1-4, що розглянуті вище. При цьому найбільш складна задача факторизації модуля N вимагає найбільших ресурсів і суттєво залежить від використовуваного методу. На сьогодні відомо та апробовано такі методи факторизації:

  1.  спробного поділу;
  2.  -Полларда і -1 Полларда;
  3.  Ленстра, з використанням еліптичних кривих ;
  4.  квадратичне решето;
  5.  загальне та спеціальні решета числового поля тощо

Згідно сучасних поглядів найбільш перспективним з точки зору мінімізації складності  факторизації модуля  є метод, що реалізований у вигляді загального решета числового поля [  ] та спеціального решета числового полях[  ]. В таблицях  10.2 та 10.3  показано результати, які отримано в світі при розв’язку задач факторизації. 

10.4 Проблемні питання крипто перетворень типу RSA.

 Існує ряд проблемних питань теорії та практики RSA. В першу чергу до них необхідно віднести такі.

1). Є публікації  в яких стверджується існування та запропоновано один із варіантів якби «поліноміального» методу факторизації модуля. Більш детальніше   ці результати розглядаються в 9 розділі.

2). Отримані теоретичні та практичні результати факторизації , перше за все у вигляді спеціального решета числового  поля та загального решета числового поля, якими підтверджено субекспоненціальний характер  складності факторизації. Так для двійкового та загального решіт числового поля складність крипто аналізу може бути оцінена як[11, 12]:

                  ,                                        (10.16   18)

– параметри методу. Наприклад, для квадратичного решета δ=1,96; ν=1/3, спеціального решета  числового поля δ=1,92; ν=1/10.

3) Необхідність постійного збільшення з метою забезпечення допустимого рівня стійкості довжини модулі N криптографічного перетворення , так нині рекомендується довжина модуля не менше 2048 бітів, що створює проблеми форматів, стандартизації, апаратної реалізації тощо.

4)  Збільшення довжини ключів практично до довжини модуля, що викликає підвищення складності прямих та зворотних криптографічних перетворень, а також проблемні питання з форматами та уніфікацією.

5) Числа P і Q мають бути не просто простими, а «сильно» простими числами, наприклад, мати вигляд:

                  P=2R+1,                                                                                         (10.17    17)

де R – в свою чергу також просте число.

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

- відбраковувати ключі-близнята, тобто відмовлятися від ключової пари у якої Ek = Dk;

- відмовлятися від простих чисел P та Q, які близькі за значенням, тобто PQ;

- відслідковувати можливу появу блоків повідомлень, що не зашифровуються , та приймати відповідні зміни в повідомленні тощо.

Додаток А  Асиметричні криптоалгоритми. Приклади розв’язку задач та
задачі для самостійного розв’язання

1.8.1 Приклади розв’язку задач

1.8 Асиметричні криптоалгоритми. Приклади розв’язку задач та
задачі для самостійного розв’язання

1.8.1 Приклади розв’язку задач

Задача 1.

Нехай Р=11, Q=7, Еk=37. Побудуйте ключову пару (Ek, Dk) для RSA-перетворення.

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

Модуль перетворення має значення

N = P*Q = 11*7 = 77.

Розраховуємо значення функцій Ойлера

(N) = (P-1)(Q-1) = 10*6 =60 = 22 3 5.

Для знаходження Dk ключа розв’яжемо порівняння

.

Подамо це порівняння у вигляді (1.58)

.

Підставимо значення  (Nj) та Ek маємо

.

Подамо а/b у вигляді ланцюгового дробу

;

60/37=1+23/37; 37/23=1+14/23; 23/14=1+9/14; 14/9=1+5/9; 9/5=1+4/5; 5/4=1+1/4; 4/1=4+0.

Це означає, що =6.

Тоді значення можна знайти з виразу

.

Підрахуємо коефіцієнти, а0, а1, а2, а3, а4 та а5.

Визначимо ключ розшифрування

y = Dk = (-1)6*13 = 13;

.

Перевірку здійснюємо підстановкою значень Ek та Dk в основне порівняння

.

Таким чином (Ek =37 та Dk= 13) є ключовою парою RSA-перетворення.

Задача 2.

Нехай Р=11 і Q=7. Побудувати пару (Ek, Dk) для RSA-перетворення, обґрунтувавши та вибравши один із випадкових ключів.

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

Знаходимо модуль перетворення та значення функції Ойлера  (N)

Порівняння виду

.

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

.

Вибравши випадково Ek =17 ключ, взаємопростий з функцією Ойлера, тобто (Ek,  (N)) = 1, маємо

.

Тепер подамо a/b у вигляді ланцюгового дробу:

;

60/17=3+9/17; 17/9=1+8/9; 9/8=1+1/8; 8/1=8+0.

Таким чином

.

Розраховуємо значення y=Dk, використовуючи співвідношення (1.59)

.

Знаходимо рекурентно значення а2:

Підставивши значення а2. в (1.10.12), маємо

.

Таким чином пара

складає RSA ключову пару.

Перевірка:

Підставивши значення ключів Ek =17та Dk = 53, маємо

.

Задача 10.

Нехай Р=11 і Q=7. Виберемо Ek=9 як випадковий ключ і побудуємо пару (Ek, Dk) для RSA ключів.

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

Знаходимо модуль RSA  перетворення та значення функції Ойлера:

Ключ Dk знайдемо із порівняння

,

далі зведемо вищенаведене порівняння до Діафантового рівняння

Знайдемо розклад ланцюгового дробу:

;

60/9=6+6/9; 9/6=1+3/6; 6/3=2+0.

Оскільки НСД , то розв’язку для пари ключів (Ek, Dk) немає.

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

Задача 1. Побудувати пару (Ek,Dk) для RSA криптоалгоритму, якщо (значення Р і Q дивись у табл. 1.3).

Таблиця 1.3 – Значення Р і Q для задачі 1

n

1

2

3

4

5

6

7

8

9

10

Pп

29

11

11

11

23

7

29

17

19

19

Qп

11

17

23

13

17

23

7

7

7

11

 де – номер за списком.

Якщо , то .

Задача 2. Розв’язати порівняння , якщо N = Nп (значення Р і Q дивись у табл. 1.4).

Таблиця 1.4 – Значення Р і Q для задачі 2

n

1

2

3

4

5

6

7

8

9

10

Nп

187

203

297

189

351

209

133

391

143

145

 де - номер за списком.

Якщо , то .

Задача 1.

Нехай Р=11, Q=7, Еk=37. Побудуйте ключову пару (Ek, Dk) для RSA-перетворення.

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

Модуль перетворення має значення

N = P*Q = 11*7 = 77.

Розраховуємо значення функцій Ойлера

(N) = (P-1)(Q-1) = 10*6 =60 = 22 3 5.

Для знаходження Dk ключа розв’яжемо порівняння

.

Подамо це порівняння у вигляді (1.58)

.

Підставимо значення  (Nj) та Ek маємо

.

Подамо а/b у вигляді ланцюгового дробу

;

60/37=1+23/37; 37/23=1+14/23; 23/14=1+9/14; 14/9=1+5/9; 9/5=1+4/5; 5/4=1+1/4; 4/1=4+0.

Це означає, що =6.

Тоді значення можна знайти з виразу

.

Підрахуємо коефіцієнти, а0, а1, а2, а3, а4 та а5.

Визначимо ключ розшифрування

y = Dk = (-1)6*13 = 13;

.

Перевірку здійснюємо підстановкою значень Ek та Dk в основне порівняння

.

Таким чином (Ek =37 та Dk= 13) є ключовою парою RSA-перетворення.

Задача 2.

Нехай Р=11 і Q=7. Побудувати пару (Ek, Dk) для RSA-перетворення, обґрунтувавши та вибравши один із випадкових ключів.

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

Знаходимо модуль перетворення та значення функції Ойлера  (N)

Порівняння виду

.

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

.

Вибравши випадково Ek =17 ключ, взаємопростий з функцією Ойлера, тобто (Ek,  (N)) = 1, маємо

.

Тепер подамо a/b у вигляді ланцюгового дробу:

;

60/17=3+9/17; 17/9=1+8/9; 9/8=1+1/8; 8/1=8+0.

Таким чином

.

Розраховуємо значення y=Dk, використовуючи співвідношення (1.59)

.

Знаходимо рекурентно значення а2:

Підставивши значення а2. в (1.10.12), маємо

.

Таким чином пара

складає RSA ключову пару.

Перевірка:

Підставивши значення ключів Ek =17та Dk = 53, маємо

.

Задача 10.

Нехай Р=11 і Q=7. Виберемо Ek=9 як випадковий ключ і побудуємо пару (Ek, Dk) для RSA ключів.

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

Знаходимо модуль RSA  перетворення та значення функції Ойлера:

Ключ Dk знайдемо із порівняння

,

далі зведемо вищенаведене порівняння до Діафантового рівняння

Знайдемо розклад ланцюгового дробу:

;

60/9=6+6/9; 9/6=1+3/6; 6/3=2+0.

Оскільки НСД , то розв’язку для пари ключів (Ek, Dk) немає.

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

Задача 1. Побудувати пару (Ek,Dk) для RSA криптоалгоритму, якщо (значення Р і Q дивись у табл. 1.3).

Таблиця 1.3 – Значення Р і Q для задачі 1

n

1

2

3

4

5

6

7

8

9

10

Pп

29

11

11

11

23

7

29

17

19

19

Qп

11

17

23

13

17

23

7

7

7

11

 де – номер за списком.

Якщо , то .

Задача 2. Розв’язати порівняння , якщо N = Nп (значення Р і Q дивись у табл. 1.4).

Таблиця 1.4 – Значення Р і Q для задачі 2

n

1

2

3

4

5

6

7

8

9

10

Nп

187

203

297

189

351

209

133

391

143

145

 де - номер за списком.

Якщо , то .


 

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

83336. Понятие организации и её роли в менеджменте 4.74 KB
  Таким образом понятие организации звучит так: это некая группа людей от двух человек и более работающая совместно ради достижения каких-либо общих целей. Организация и менеджмент В системе менеджмента организация понятие сложное. Понятие организации обязательно включает в себя элемент управления.
83337. Фонетико-фонематическое недоразвитие речи 17.03 KB
  Фонематический слух являясь частью физиологического слуха направлен на соотнесение и сопоставление слышимых звуков с их эталонами которые хранятся в памяти человека упорядочение в решетке фонем. Каждый человек имеет индивидуальные особенности произношения звуков: один говорит тихо другой громко...
83338. Макросередовище маркетингу 25.99 KB
  Виділяють принаймні шість факторів які в певний спосіб позитивно або негативно можуть впливати на управління системою маркетингу: демографічні економічні природні науково-технічні політичні фактори та фактори культурного оточення.
83339. Порядок захисту права на комерційну таємницю 63.5 KB
  Комерційною таємницею можуть бути відомості технічного організаційного комерційного виробничого та іншого характеру за винятком тих які відповідно до закону не можуть бути внесені до комерційної таємниці. Важливим для забезпечення комерційної таємниці є забезпечення дії нормативно-правових актів...
83340. Secretary’s work 19.74 KB
  Professional receptionist (квалифицированный секретарь) is an irreplaceable assistant (помощник руководителя) to the head and face of the company. Secretary’s job is a good school of life and a great launching pad (стартовая площадка) to start a career.
83341. Підсумковий урок з теми «Числівник» 59.5 KB
  Мета: Систематизувати та узагальнити знання про числівник як частину мови, вправляти учнів в доцільному та правильному вживанні числівників у мовленні; розвивати вміння аналізувати, порівнювати, зіставляти, узагальнювати, роботи висновки; розвивати мовлення, логічне мислення...
83342. Закріплення вивченого про числівник, його роль у мовленні. Вживання числівників у загадках 39.5 KB
  Закріпити знання учнів з теми Числівник; з’ясувати роль числівників у мовленні; вживання числівників у загадках. Як називається це речення прислів’я Поясніть як ви його розумієте Чи є числівники в нашому девізі Назвіть їх.
83343. Вживання прикметників для всебічної характеристики предметів 57.5 KB
  Закріплювати знання учнів про відмінювання прикметників, удосконалювати вміння визначати рід, число, відмінок прикметників у реченнях, добирати синоніми та антоніми до них. Розвивати вміння вживати прикметники в мовленні ля повнішого розкриття думки, характеристики предметів...
83344. Відмінювання іменників. Орудний відмінок іменників жіночого роду 552.5 KB
  Формувати вміння вживати в усному і писемному мовленні іменників жіночого роду з нульовим закінченням в Орудному відмінку; розвивати зв’язне мовлення, увагу, пізнавальну самостійність; виховувати ретельне ставлення до вивчення української мови, любов до рідного краю, бережливе ставлення до свого здоров’я.