Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Принцип роботи
|
|
Існує декілька широковідомих асиметричних криптосистем: RSA, Ель Гамаля (El Gamal), Рабіна (Rabin). Так як в цих криптосистемах перетворення визначає ключ, публікують лише відкритий ключ із вказівкою для якої криптосистеми він використовується. Таємний та відкритий ключ як правило взаємопов’язані між собою, але так, що отримати таємний ключ володіючи відкритим неможливо.
| Мал. 4‑ 2 |
Очевидно, що відкритий ключ потрібно захищати від підробки або слід забезпечити автентичну передачу ключа, тобто з підтвердженням автентичності. В іншому випадку зловмисник може підмінити відкритий ключ на свій власний і читати усі повідомлення.
Для того, щоб продемонструвати роботу асиметричних криптосистем, розглянемо в спрощеному вигляді опис схеми RSA і на її прикладі розглянемо основні моменти, характерні асиметричним системам.
- Вибираються p, q – великі прості числа. Обчислюється добуток n = p q.
- Вибирається число e - таке, що f(e,
(n))=1 (тобто e та 
(n) – взаємнопрості), де (n)=(p -1)(q -1) - функція Ейлера від n. - З рівняння ed=1(mod (n)) знаходиться число d. Запис x mod n означає, що береться залишок від ділення x на n (x по модулю n), а запис x = a (mod n) означає, що остача від ділення x на n рівна а. Тобто знаходиться таке число d, що остача від ділення добутку ed на (n) рівна 1.
Отримані числа e, n - відкритий ключ користувача, а d – таємний ключ. З умови 3 випливає, що ed=1+k (n), де k - деяке число.
Процедура зашифрування:
C=E(e, n)(M)=Me(mod n), де С – отримуваний шифротекст, M – відкритий текст, що задовольняє наступній умові: M (n)=1(mod n).
Процедура розшифровування:
M=D(d, n) (C)=Cd(mod n)=(Me)d(mod n)=(M1+k (n))(mod n)=M(M (n))k(mod n)=M.
У криптосистемі RSA як і у багатьох інших асиметричних криптосистемах, повідомлення представляється у вигляді деякого числа, яке пізніше опрацьовується певним чином (наприклад зашифровується). Практично усі асиметричні криптосистеми будуються на основі математичних проблем, для яких поки що не знайдено ефективного алгоритму вирішення. Відповідно усі параметри RSA повинні вибиратися таким чином, щоб зловмисник не зміг за прийнятний час отримати ключі схеми чи будь-які інші параметри (наприклад числа p та q), що дозволить йому організувати атаку. Так для RSA рекомендована довжина n 768 біт, а у випадку довготривалого використання - 1024 біта (в цьому випадку довжина p та q буде по 512 біт).
Швидкість роботи та експонента е
Так як криптосистема працює з досить великими числами і виконує складні операції піднесення до степеня, то швидкодія криптосистеми невисока. Асиметричні системи поступаються у швидкості симетричним власне завдяки використанню таких перетворень. Існують різні способи підвищення RSA. Наприклад в якості відкритого ключа e береться e=3. Тоді, для того щоб зашифрувати, необхідно всього на всього три перемноження. Правда в цьому випадку отримується велике значення d, але припускається, що абонент, який здійснює розшифровування, має достатньо часу. Однак використання малої експоненти e приводить до проблем з маленькими повідомленнями, тобто такими, що M< n1/e, поскільки в цьому випадку M може бути отримане з шифротексту C=Me mod n шляхом обрахунку кореня степеня e з C.
Додавання в повідомлення додаткової інформації (salting)
Для того щоб уникнути описаної проблеми для маленьких повідомлень, а також для неможливості здійснення інших атак в повідомлення добавляється деяка випадкова стрічка визначеної довжини (salt). Після отримання шифротексту та розшифровування дана стрічка видаляється.
Мультиплікативні властивості
Нехай m1 та m2 – два різних відкритих тексти, а c1 і с2 – відповідні їм шифротексти. Можна зауважити, що
(m1m2)e=m1e m2e=c1c2 (mod n)
іншими словами, шифротекст відкритого тексту m=m1m2 є c=c1c2 (mod n). Ця властивість також називається гомоморфною властивістю RSA, і дозволяє здійснювати атаку по вибраному шифротексту.