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

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

Генерування ключів. Оберемо два великих різних простих числа p і q (Натуральне число називається простим, якщо воно ділиться тільки на себе і на 1. Додаток В.) та знайдемо їх добуток

Обчислимо функцію Ейлера за формулою:

Таємний ключ добираємо з умов: і в заємно просте з

тобто d\j(n) не мають спільних дільників. Відкритий ключ є обираємо з умов:

Остання умова означає, що різниця де - 1 повинна ділитись на j(n) без залишку. Для визначення числа є слід підібрати таке число к, що:

В алгоритмі RSA (є, п)- відкритий ключ, (d,n)-секретний ключ.

39. Шифрування і Дешифрування в криптосистемы RSA

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

де С- шифроблок, що відповідає блоку відкритого повідомлення М. Шифрблоки з'єднуються в шифрограму.

Дешифрування. При дешифруванні шифрограма розбивається на блоки відомої довжини і кожен шифрблок дешифрується окремо за наступною формулою:

Функція хешування. Функцією хешування називається перетворення даних, що переводить рядок бітів М довільної довжини в рядок бітів h (M) деякої фіксованої довжини (кілька десятків чи сотень біт). Хеш-функція h (M) повинна задовольняти наступним умовам:

■=> хеш-функція h (M) повинна бути чутливою до будь-яких змін вхідної послідовності М;

•=> для даного значення h (M) повинно бути неможливо знайти значення м- ^ для даного значення h (M) повинно бути неможливо знайти значення М №М таке, щоіі(М') =h(M) .

Ситуація, за якої для різних вхідних послідовностей М, М співпадають значення їх хеш-образів: називається колізією При побудові хеш-образу, вхідна послідовність М розбивається на блоки А/ фіксованої довжини і оброблгється поблочно за формулою:

Хеш-значення, що обчислюється при введенні останнього блоку повідомлення, стає хеш-значенням всього повідомлення. В якості прикладу розглянемо спрощений варіант хеш-функціїіз рекомендацій МККТТХ.509: де п = pq, piq- великі прості числа, HQ - довільний початковий вміст, А/ - /-тий блок повідомлення М-М1М2... Мк.

44. Генерування ключів в криптосистемі Рабіна

Генерація ключа

Як будь-яка асиметрична криптосистема, система Рабіна використовує і відкритий і закритий ключі. Відкритий ключ необхідний для шифрування документів і може бути опублікований для загального огляду. Закритий ключ повинен бути відомий тільки одержувачам зашифрованих повідомлень.

Процес генерації ключів наступний:

Вибираються два великих простих числа p і q, які задовольняють умові . Такий спеціальний вид простих чисел сильно прискорює процедуру вилучення коренів за модулем р і q. Тоді n - відкритий ключ. Числа p і q - закритий ключ.

Для шифрування повідомлення необхідний відкритий ключ n. Щоб розшифрувати зашифрований текст потрібні p і q.

Розглянемо простий приклад. Нехай p=7 і q=77, тоді n=77 . Відкритий ключ, 77, публікується для загального огляду, за допомогою його шифруються повідомлення. Закриті ключі, 7 та 11, залишаються відомі тільки власникові, і за допомогою їх розшифровуються повідомлення. Такий вибір ключів - добре підходить для прикладу. Але поганий для практичного використання, тому що розкладання на множники 77 тривіально.

Шифрування

Для шифрування використовується тільки відкритий ключ n. За допомогою його вихідний текст перетворюється в зашифрований. Для шифрування повідомлення m потрібно просто обчислити:

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

У нашому прикладі. Нехай вихідним текстом є m=20. Тоді зашифрованим текстом буде:

Розшифрування

Розшифрування в цьому алгоритмі більш складне. Для нього потрібен закритий ключ p і q. Процес виглядає наступним чином: Спочатку, використовуючи алгоритм Евкліда , з рівняння знаходимо числа і .

Далі, використовуючи китайську теорему про залишки , можна обчислити числа.

Один з цих коренів r,-r, s,-s є істинним відкритим текстом m.

Повернемося в нашому прикладу: В результаті розшифровки отримуємо: . Бачимо, що один з коренів є вихідним текстом m.

46. Криптосистема Ель-Гамаля

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

Для ключа вибирається велике просте число р, а також число g, причому 1 <g <p-1. Числа р і g не є таємними і перебувають у загальних користуванні. Кожен абонент мережі вибирає випадкове число a (1 <a <p-1) і вважає h = ga mod p. Відкритий ключ становитимуть числа p, g і h, а таємний - число а. Шифрування в криптосистема Ель Гамала здійснюється блоками. Відкритий текст М перетворюють в крипто тексті таким шляхом:

вибирається випадкове число r (1 <r <p-1);

вважаємо С = (С1, С2), де С1 = (g ^ r) mod p, C2 = (M * h ^ r) mod p.

Таким чином, пара чисел (С1, С2) буде визначати кріптотексте. Для розшифровки кріптотексте З використовуємо формулу: М = (С2 / ((С1) ^ a)) mod p.

Як бачимо, ідея цієї криптосистеми досить-таки проста. Відкритий текст М перетворюємо до виду С2, і разом з ним пересилається підказка С1. Основним недоліком даного алгоритму є те, що зашифрований текст в два рази більше початкового.

47. Шифрування і Дешифрування Криптосистеми Ель-Гамаля

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

Шифрування

Повідомлення М шифрується наступним чином:

1. Вибирається сесійний ключ - випадкове ціле число k таке, що

2. Обчислюються числа і

3. Пара чисел (a,b) є шbфротекстом.

Неважко побачити, що довжина шифротексту в схемі Ель-Гамаля довша вихідного повідомлення М вдвічі.

Розшифровання

Знаючи закритий ключ x, Вихідне повідомлення можна обчислити з шифротексту (a,b) за формулою:

При цьому неважко перевірити, що , і тому

Для практичних обчислень більше підходить наступна формула:

Так як в схему Ель-Гамаля вводиться випадкова величина k, То шифр Ель-Гамаля можна назвати шифром багатозначною заміни. Через випадковості вибору числа k таку схему ще називають схемою імовірнісного шифрування. Імовірнісний характер шифрування є перевагою для схеми Ель-Гамаля, так як у схем імовірнісного шифрування спостерігається велика стійкість у порівнянні зі схемами з певним процесом шифрування. Недоліком схеми шифрування Ель-Гамаля є подвоєння довжини зашифрованого тексту в порівнянні з початковим текстом. Для схеми імовірнісного шифрування саме повідомлення Mі ключ не визначають шіфротекст однозначно. У схемі Ель-Гамаля необхідно використовувати різні значення випадкової величини k для шифровки різних повідомлень i . Якщо використовувати однакові k, то для відповідних шbфротектів (a,b) і виконується співвідношення З цього виразу можна легко обчислити Якщо відомо M.

49. Електронний цифровий підпис

Електронний цифровий підпис (ЕЦП) — вид електронного підпису, отриманого за результатом криптографічного перетворення набору електронних даних, який додається до цього набору або логічно з ним поєднується і дає змогу підтвердити його цілісність та ідентифікувати підписувача. Електронний цифровий підпис накладається за допомогою особистого ключа та перевіряється за допомогою відкритого ключа

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

Електронний цифровий підпис призначений для використання фізичними та юридичними особами - суб'єктами електронного документообігу: для ідентифікації підписувача; для підтвердження цілісності даних в електронній формі [Закон України Про електронний цифровий підпис. Стаття 4].

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

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

Електронний цифровий підпис підтверджує достовірність і цілісність документа. Якщо в документ в процесі пересилки були внесені які-небудь зміни, нехай навіть зовсім незначні, то підміна виявиться. Сертифікат відкритого ключа містить персональну інформацію про власника, що дозволяє однозначно ідентифікувати автора документу.

50. Електронний цифровий підпис в системах RSA і Ель-Гамаля

Електронний цифровий підпис RSA. Цифровий підпис у цифрових документах грає ту ж роль, що і підпис, поставлений від руки в документах на папері: це дані, що приєднуються до повідомлення, котре передається, та підтверджують, що власник підпису склав чи завірив це повідомлення. Отримувач повідомлення за допомогою цифрового підпису може перевірити, що автором повідомлення є саме власник підпису і що в процесі передачі не було порушено цілісність отриманих даних.

При розробці механізму цифрового підпису виникають наступні задачі:

· Р створити підпис таким чином, щоб її неможливо було підробити;

· Р мати можливість перевірки того, що підпис дійсно належить вказаному власнику;

· Р мати можливість запобігти відмові від підпису.

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

· ■=> застосовує до вихідного повідомлення хеш-функцію;

· ■=> обчислює цифровий підпис за хеш-образом повідомлення з використанням секретного ключа створення підпису;

· оформує нове повідомлення, яке складається з вихідного повідомлення та доданого до нього цифрового підпису.

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

Підпис повідомлень

Для підпису повідомлення М виконуються наступні операції :

1. Обчислюється дайджест повідомлення М :

2. Вибирається випадкове число взаємно просте з і обчислюється

3. За допомогою розширеного алгоритма Евкліда обчислюється число , Що задовольняє порівнянні :

4. Підписом повідомлення М є пара (n,s).

Головною перевагою схеми цифрового підпису Ель-Гамаля є можливість виробляти цифрові підписи для великого числа повідомлень з використанням тільки одного секретного ключа. Щоб зловмиснику підробити підпис, йому потрібно вирішити складні математичні задачі з перебуванням логарифма в поле.

51. Алгоритм DSA

DSA (Digital Signature Algorithm) - алгоритм з використанням відкритого ключа для створення електронного підпису , але не для шифрування (на відміну від RSA і схеми Ель-Гамаля). Підпис створюється таємно, але може бути публічно перевірена. Це означає, що тільки один суб'єкт може створити підпис повідомлення, але будь-хто може перевірити її коректність . Алгоритм заснований на обчислювальної складності взяття логарифмів в кінцевих полях.

икористання алгоритму

Для підписування повідомлень необхідна пара ключів - відкритий і закритий. При цьому закритий ключ повинен бути відомий тільки тому, хто підписує повідомлення, а відкритий - будь-якому охочому перевірити справжність повідомлення. Також загальнодоступними є параметри самого алгоритму. Для забезпечення такого доступу достатньо авторитетна організація (або кілька організацій) підтримує базу відповідності між реальними реквізитами автора (це може бути як приватна особа, так і організація) і відкритими ключами , а також всіма необхідними параметрами схеми цифрового підпису (використовувана хеш-функція ). Ця організація також видає цифрові сертифікати .

54. Криптографічний протокол

Криптографічний протокол - це абстрактний чи конкретний протокол, що включає набір криптографічних алгоритмів. В основі протоколу лежить набір правил, що регламентують використання криптографічних перетворень та алгоритмів в інформаційних процесах.

Завдання криптографічного протоколу:

· Забезпечення різних режимів аутентифікації

· Генерація, розподіл і узгодження криптографічних ключів

· Захист взаємодій учасників

· Розподіл відповідальності між учасниками

Протоколи аутентифікованим розподілу ключів

Протоколи цього класу поєднують аутентифікацію користувачів з протоколом генерації і розподілу ключів по каналу зв'язку. Протокол має двох або трьох учасників; третім учасником є центр генерації та розподілу ключів (ЦГРК), званий для стислості сервером S. Протокол складається з трьох етапів, що мають назви: генерація, реєстрація і комунікація. На етапі генерації сервер S генерує числові значення параметрів системи, в тому числі, свій секретний і відкритий ключ. На етапі реєстрації сервер S ідентифікує користувачів за документами (при особистій явці або через уповноважених осіб), для кожного об'єкта генерує ключову і / або ідентифікаційну інформацію і формує маркер безпеки, що містить необхідні системні константи і відкритий ключ сервера S (при необхідності). На етапі комунікації реалізується власне протокол аутентифікованим ключового обміну, який завершується формуванням спільного сеансового ключа.

55. Криптоаналіз та частотний аналіз

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

Частотний аналіз, частотний криптоаналіз - вид криптоаналізу, який ґрунтується на частоті появи знаків шифротексту. Власне - на припущенні про існування нетривіального статистичного розподілу окремих символів і їх послідовностей як у відкритому тексті, так і в шифротексті, який, з точністю до заміни символів, буде зберігатися в процесі шифрування і дешифрування. Спрощено, частотний аналіз передбачає, що частота появи заданої літери алфавіту в досить довгих текстах одна і та ж для різних текстів однієї мови. При цьому у випадку моноалфавітного шифрування якщо в шифротексті буде символ з аналогічною ймовірністю появи, то можна припустити, що він і є зазначеною зашифрованою буквою. Аналогічні міркування застосовуються до біграм (двобуквених послідовностей), триграм і т.д. у разі поліалфавітного шифрів.

1 2 34