Користувач:Dima1tv/Криптосистема Рабіна
Криптосистема Рабіна - криптографічна система з відкритим ключем , безпека якої забезпечується складністю пошуку квадратних коренів складеного числа. Безпека системи, як і безпека методу RSA , обумовлена складністю розкладання на множники великих чисел. Зашифроване повідомлення можна розшифрувати 4-а способами. Недоліком системи є необхідність вибору істинного повідомлення з 4-х можливих.
У січні 1979 року Майкл О. Рабін опублікував опис своєї системи. Було доведено, що відновлення початкового тексту з зашифрованого настільки ж важко, як факторизація великих чисел. Система Рабіна стала першою асиметричною криптосистемою, для якої було виконано такий доказ. Складність відновлення пов'язана з трудністю вилучення квадратного кореня за модулем складеного числа N = р · q . Завдання факторизації і завдання по вилученню квадратного кореня еквівалентні, тобто:
- знаючи прості дільники числа N можна витягувати квадратний корінь по модулю N ;
- вміючи витягувати квадратний корінь по модулю N , можна розкласти N на прості множники.
Система Рабіна, як і будь асиметрична криптосистема , використовує відкритий і закритий ключі. Відкритий ключ використовується для шифрування повідомлень і може бути опублікований для загального огляду. Закритий ключ необхідний для розшифровки і повинен бути відомий тільки одержувачам зашифрованих повідомлень.
Процес генерації ключів наступний:
- вибираються два випадкових числа p і q з урахуванням таких вимог:
- числа повинні бути великими (див. розрядність ):
- числа повинні бути простими ;
- повинна виконуватися умова: P ≡ Q ≡ 3 mod 4 .
Виконання цих вимог сильно прискорює процедуру вилучення коренів за модулем р і q ;
- обчислюється число n = p · q ;
- число n - відкритий ключ; числа p і q - закритий.
Приклад. Нехай p = 7 і q = 11 . Тоді n = p · q = 7 · 11 = 77 . Число n = 77 - відкритий ключ, а числа p = 7 і q = 11 - закритий. Одержувач повідомляє відправникам число 77. Відправники шифрують повідомлення, використовуючи число 77, і відправляють одержувачу. Одержувач розшифровує повідомлення за допомогою чисел 7 і 11. Наведені ключі погані для практичного використання, так як число 77 легко розкладається на прості множники (7 і 11).
Початкове повідомлення m (текст) шифрується за допомогою відкритого ключа - числа n за такою формулою:
- c = m² mod n.
Завдяки використанню множення по модулю швидкість шифрування системи Рабина більше, ніж швидкість шифрування за методом RSA , навіть якщо в останньому випадку вибрати невелике значення експоненти.
Приклад (продовження). Нехай вихідним текстом m = 20 . Тоді зашифрованим текстом буде: c = m² mod n = 20² mod 77 = 400 mod 77 = 15.
Для розшифровки повідомлення необхідний закритий ключ - числа p і q . Процес розшифровки виглядає наступним чином:
- спочатку, використовуючи алгоритм Евкліда , з рівняння знаходять числа і ;;
- далі, використовуючи китайську теорему про залишки , обчислюють чотири числа:
Одне з цих чисел є істинним відкритим текстом m .
Приклад (закінчення). В результаті розшифровки отримуємо: . Бачимо, що один з коренів є вихідним текстом m .
Розшифровка тексту крім правильного наводить ще до трьох хибним результатам. Це є головним незручністю криптосистеми Рабіна і одним з факторів, які перешкоджали тому, щоб вона знайшла широке практичне використання.
Якщо вихідний текст являє собою текстове повідомлення, то визначення правильного тексту не є важким. Однак, якщо повідомлення є потоком випадкових бітів (наприклад, для генерації ключів або цифрового підпису), то визначення потрібного тексту стає реальною проблемою. Одним із способів вирішити цю проблему є додавання до повідомлення перед шифруванням відомого заголовка або якоїсь мітки.
Алгоритм Рабіна схожий на кодування RSA, але замість зведення повідомлення в ступінь е при шифруванні використовується операція піднесення блоку повідомлення в квадрат, що сприятливо позначається на швидкості виконання алгоритму без шкоди криптостойкости.
Для декодування китайська теорема про залишки застосована разом з двома зведення в ступінь по модулю. Тут ефективність порівнянна RSA.
Вибір потрібного тексту з чотирьох призводить до додаткових обчислювальним затратам. І це послужило тому, що криптосистема Рабина не отримала широкого практичного використання.
Велика перевага криптосистеми Рабіна полягає в тому, що випадковий текст може бути відновлений повністю від зашифрованого тексту тільки за умови, що дешифрувальник здатний до ефективної факторизації відкритого ключа n.
Криптосистема Рабина є доказовою стійкою до атаки на основі підібраного відкритого зашифрованого тексту в рамках підходу "все або нічого", тоді і тільки тоді, коли завдання про розкладання цілого числа на прості множники є важкою.
Стійкість за принципом "все або нічого" полягає в тому, що, маючи текст, зашифрований певним алгоритмом, атакуючий повинен відновити блок вихідного тексту, розмір якого, як правило, визначається параметром безпеки криптосистеми. Маючи вихідний і зашифрований текст, атакуючий повинен відновити цілий блок секретного ключа. При цьому атакуючий небудь домагається повного успіху, або не отримує нічого. Під словом «нічого» мається на увазі, що атакуючий не має ніякої секретної інформації ні до, ні після безуспішної атаки.
Криптосистема Рабина є абсолютно беззахисною перед атакою на основі обраного шифротекста. Як правило, атакуючий використовує всі наявні у нього можливості. Він вступає в контакт з атакованим користувачем, посилають йому зашифрований текст для подальшої розшифровки і вимагають повернути вихідний текст.
Наприклад, при додаванні надмірності, наприклад, повторення останніх 64 біта, можна зробити корінь єдиним. Алгоритм розшифрування в цьому випадку видає єдиний корінь, який вже відомий атакуючому.
Процес додатково уразливий, оскільки при кодуванні використовуються тільки квадратні залишки. У прикладі при n = 77 тільки використовується тільки 23 з 76 можливих станів.
Асиметричні алгоритми шифрування
Ранцева криптосистема Меркля-Хеллмана
1. http://www.ssl.stu.neva.ru/pws/crypto/appl_rus/ac_18_20.pdf
2. http://www.williamspublishing.com/PDF/5-8459-0847-7/part.pdf
Категорія :Криптографія