На головну

Алгоритм криптографічного системи на основі обчислення дискретних логарифмів в кінцевому полі - алгоритм Ель Гамаля.

  1. B.3. Системи економетричних рівнянь
  2. D.3. Системи економетричних рівнянь
  3. GІІ. Викладаєте проблему групі. Разом з усіма виробляєте рішення на основі консенсусу. Виконуєте будь-яке рішення групи.
  4. I. Приклади деяких розподілів дискретних випадкових величин
  5. I. РОЗРОБКА АЛГОРИТМІВ. ГРАФІЧНЕ ЗОБРАЖЕННЯ (БЛОК-СХЕМИ) І СЛОВЕСНА ЗАПИС АЛГОРИТМІВ
  6. I. Суб'єктивні методи дослідження ендокринної системи.
  7. I. Суб'єктивні методи дослідження кровотворної системи.

Зазначена схема алгоритму криптографічних перетворень була запропонована Тахіром Ель Гамаль в 1985 році (США), вона обумовлена ??складністю обчислення дискретних логарифмів в кінцевому полі. Послідовність дій аналогічна алгоритму факторизації великих чисел RSA.

Дії абонента В - абонента одержувача закріптгорафірованного (зашифрованого) повідомлення.

1. На першому кроці алгоритму абонент В формує (генерує) пару ключів шифрування-дешифрування передаваних повідомлень: ДоОВ - Відкритий ключ, призначений для шифрування відкритих повідомлень; ДоЗВ - Закритий (секретний) ключ, призначений для дешифрування прийнятих криптограми.

Спочатку, з боку абонента В (абонента - одержувача зашифрованих повідомлень) випадковим чином задається велике просте число Р (модуль вироблених обчислень). На практиці це число становить більше 100 десяткових знаків, для спрощення процесу вивчення алгоритму Ель Гамаля приймається число Р = 977, потім вибирається ціле число G <Р, приймемо G = 378.

2. На другому етапі алгоритмізації випадковим чином задається ціле число КЗВ -Закриті (секретний) ключ для дешифрування прийнятих закріптографірованних повідомлень, для прикладу приймається ДоЗВ = 529; умовою обмеження є ДоЗВ <Р.

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

КОВ =  mod P = 378529 mod 977 = 402 mod 977 > 402.

4. Числові значення P, G, КОВ є відкритими параметрами криптографічного системи і передаються по незахищеному каналу всім абонентам зв'язку, зокрема і абоненту А для забезпечення можливості абоненту-відправнику використовувати ці параметри для шифрування відкритих повідомлень для абонента В. Параметри P и G розрахованої на багато користувачів корпоративної системи захисту і аутентифікації електронних повідомлень поширюються між усіма абонентами передачі-прийому зашифрованих повідомлень і є постійними для певного часового інтервалу, що задається адміністратором безпеки.

параметри ДоОВ -Відкритий ключ і КЗВ-Закриті (секретний) ключ формуються індивідуально на кожному робочому місці абонента захищеного зв'язку. ДоЗВ-Закриті (секретний) ключ зберігається у кожного абонента в захищеному варіанті (на знімних носіях) і ніколи нікому не передається. Відкритими ключами ДоО всі абоненти телекомунікаційної системи обмінюються між собою через відкриті канали.

У розглянутому прикладі параметри P, G, KOB від абонента В передаються відкрито абоненту А.

Дії абонента А для формування криптограми відкритих повідомлень для абонента В.

1. Абонент А своє відкрите повідомлення, призначене для шифрування і передачі сформованої криптограми абоненту-одержувачу В, відображає у вигляді цілих чисел відповідно до прийнятої таблицею (наприклад, таблиця Windows-кодування). Розглянемо приклад складання криптограми слова «Криптон». До > 171; р > 209; і > 201; п > 208; т > 211; про > 207; н > 206.

2. Для того, щоб зашифрувати повідомлення М > «Криптон» абонент А вибирає випадковим чином ціле число «К» з урахуванням наступних умов 1 <К <Р-1; НСД (К; (Р-1)) = 1. Умова, що найбільший спільний дільник (НСД) чисел До і (Р-1) дорівнює одиниці, означає їх взаємну простоту. Тобто число К повинно бути взаімопростим з числом (Р-1) = 976 і лежати в межах від 1 до 976. Наприклад приймається К = 473. Необхідно відзначити, що для кожного сеансу обміну зашифрованими повідомленнями число До індивідуально.

3. Абонент А виробляє обчислення чисел для формування криптограми для абонента В. Спочатку обчислюється загальне для даної криптограми число a = GK mod P. Для розглянутого прикладу К = 473; G = 378; Р = 977 отже число a = 378473 mod 977 = 950 mod 977 > U. Потім обчислюються криптографічні значення кожного символу відкритого тексту у відповідності з наступною залежністю:

Ci = (KOB)K * Mi mod P.

Для розглянутого прикладу: Ci = 402473 * Mi mod 977.

С1 = 402473 * M1 mod P = 402473 * 171 mod 977 = 497 mod 977 > 497 > P;

С2 = 402473 * M2 mod P = 402473 * 209 mod 977 = 716 mod 977 > 716 > K;

С3 = 402473 * M3 mod P = 402473 * 201 mod 977 = 927 mod 977 > 927 >>;

С4 = 402473 * M4 mod P = 402473 * 208 mod 977 = 376 mod 977 > 376 >. ;

С5 = 402473 * M5 mod P = 402473 * 211 mod 977 = 419 mod 977 > 419 > B;

С6 = 402473 * M6 mod P = 402473 * 207 mod 977 = 36 mod 977 > 36 > C;

С7 = 402473 * M7 mod P = 402473 * 206 mod 977 = 673 mod 977 > 673 > L;

Два числа (a; Ci) Для кожного семантичного символу відкритого повідомлення є його криптограмою. Загальний вигляд криптограми всього відкритого повідомлення «Криптон» має наступне відображення:

С = {950 497; 950 716; 950 927; 950 376; 950 419; 950 36; 950 673} >

> {U P; U K; U>; U.; U b; U C; U L}.

Як видно з відображення криптограми «С» в разі її формування за алгоритмом Ель Гамаля (алгоритм дискретного логарифмування в кінцевому полі) довжина шифртекста стає вдвічі більше довжини вихідного відкритого повідомлення «М». Таким чином, з боку абонента А формується криптограма С для абонента В за допомогою відкритого ключа абонента В - ДоОВ. Ця криптограма по каналах теледоступ передається від абонента А до абонента В. Отримавши криптограму С, абонент В виробляє її дешифрування за допомогою свого секретного ключа КЗВ, Який зберігається тільки у абонента В під секретом.

дія абонента В по прийому і розшифровки криптограми С, отриманої від абонента А.

4. Абонент В по мережевих каналах телекомунікацій приймає криптограму С від абонента-відправника А, Яка зашифрована відкритим ключем абонента В - ДоОВ. В цьому випадку абонент В є санкціонованим абонентом, які мають спеціальний закритий (секретний) ключ - ДоЗВ безпосередньо функціонально пов'язаний з відкритим ключем КОВ, За допомогою якого і була сформована криптограма С.

За допомогою свого закритого (секретного) ключа КЗВ абонент В робить дешифрування криптограми, отриманої від абонента А, Використовуючи такі функціональні перетворення:

Mi =  mod P

Кожен елемент криптограми дешифрується самостійно, в розглянутому прикладі а = 950; ДоЗВ = 529; Р = 977.

Mi =  mod 977

Виконавши операцію зведення числа в ступінь по модулю знаменника представленої залежності, отримують:

950529 mod 977 = 340 mod 977 > 340.

Методика такого обчислення наведена в розділі 2.3, а сам алгоритм представлений на рис. 2.

Мал. 2. Алгоритм зведення числа а = 950 в ступінь 529 по модулю 977.

Після виконання операції піднесення числа «а = 950» в ступінь 529 по модулю 977 отримують відповідність функціонального перетворення криптограми у відкритий текст повідомлення, прийнятого від абонента А.

Mi =  mod 977

Для обчислення значень відкритого тексту необхідно скористатися методом обчислення зворотних величин по модулю. Для чого значення Mi представляється як: Mi = Ci * 340-1 mod 977.

Спочатку обчислюється значення інверсії числа 340 по модулю 977, тому що число 977 є простим числом, то це перетворення може бути відображено як: 340-1 mod 977 = 340?(P) -1 mod P, тому що Р - просте число, то ? (Р) = Р-1 = 977 - 1 = 976.

Отже, 340-1 mod 977 = 340975 mod 977 = 250 mod 977

Для обчислення значень Mi отримуємо наступну залежність:

Mi = Ci * 250 mod 977

Звідки отримуємо:

M1 = C1 * 250 mod 977 = 497 * 250 mod 977 = 124 250 mod977 = 171 mod977

> До;

M2 = C2 * 250 mod 977 = 716 * 250 mod 977 = 179000 mod977 = 209 mod977

> р;

M3 = C3 * 250 mod 977 = 927 * 250 mod 977 = 231 750 mod977 = 201 mod977

> і;

M4 = C4 * 250 mod 977 = 376 * 250 mod 977 = 94000 mod977 = 208 mod977

> п;

M5 = C5 * 250 mod 977 = 419 * 250 mod 977 = 104 750 mod977 = 211 mod977

> т;

M6 = C6 * 250 mod 977 = 36 * 250 mod 977 = 9000 mod977 = 207 mod977

> про;

M7 = C7 * 250 mod 977 = 673 * 250 mod 977 = 168 250 mod977 = 206 mod977

> н.

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



Попередня   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   Наступна

В. В. Сюзев | В. Ф. Макаров | Вступ | Основні напрямки криптології. | Методи криптографічних перетворень з відкритим ключем. | Обчислення зворотних величин в модулярной алгебри. | Алгоритм операції зведення числа в ступінь по модулю. | Визначення односторонньої функції. | Основні операції криптографічних перетворень в метриці еліптичних кривих. | Перетворення Діффі-Хеллмана в системах криптографії з відкритим ключем. |

© um.co.ua - учбові матеріали та реферати