ної завданням. Зворотній їй завдання носить назву логарифмирование в кінцевому полі і є на кілька порядків більш складним завданням. Тобто навіть якщо зловмисник знає числа e і n, то по ci прочитати вихідні повідомлення mi він не може ніяк, окрім як повним перебором mi.
А ось на приймальній стороні процес дешифрування все ж можливий, і допоможе нам в цьому збережене в секреті число d. Досить давно була доведена теорема Ейлера, окремий випадок якій стверджує, що якщо число n представимо у вигляді двох простих чисел p і q, то для будь-якого x має місце рівність (x (p - 1) (q - 1)) mod n=1. Щоб дешифрувати RSA-повідомлень скористаємося цією формулою. Зведемо обидві її частини в ступінь (-y):
(x (-y) (p - 1) (q - 1)) mod n=1 (-y)=1.
Тепер помножимо обидві її частини на x:
(x (-y) (p - 1) (q - 1) +1) mod n=1 * x=x.
А тепер згадаємо як ми створювали відкритий і закритий ключі. Ми підбирали за допомогою алгоритму Евкліда d таке, що e * d + (p - 1) (q - 1) * y=1, тобто e * d=(- y) (p - 1) (q - 1) +1. А отже в останньому виразі попереднього абзацу ми можемо замінити показник ступеня на число (e * d). Отримуємо (xe * d) mod n=x. Тобто для того щоб прочитати повідомлення ci=((mi) e) mod n достатньо звести його в ступінь d по модулю m:
((ci) d) mod n=((mi) e * d) mod n=mi.
Насправді операції зведення в ступінь великих чисел досить трудомісткі для сучасних процесорів, навіть якщо вони виробляються за оптимізованим за часом алгоритмам. Тому зазвичай весь текст повідомлення кодується звичайним блоковим шифром (набагато більш швидким), але з використанням ключа сеансу, а от сам ключ сеансу шифрується як раз асиметричним алгоритмом за допомогою відкритого ключа одержувача і поміщається в початок файлу.
. 2 Асиметричні алгоритми
Асиметричне шифрування припускає наявність двох ключів. Перший ключ - відкритий (public) - розповсюджується абсолютно вільно, без всяких запобіжних заходів, а другий - закритий, особистий (private), потрібно тримати в секреті. Будь-яке повідомлення, зашифроване з використанням одного з цих ключів, може бути розшифровано тільки з використанням другого ключа. Як правило, відправник повідомлення користується відкритим ключем одержувача, а одержувач - своїм особистим.
У асиметричною схемою шифрування обидва ключі є похідними від єдиного порождающегомастер-ключа (master-key), як це показано на рис. 6. Коли два ключа сформовані на основі одного, вони залежні в математичному сенсі, але жоден з них не може бути обчислений на основі іншого. Після того, як обчислені обидва ключі, майстер-ключ знищується і таким чином присікається будь-яка спроба відновити надалі значення похідних від нього ключів.
Малюнок 1 - Схема асиметричного шифрування
Ідея асиметричних алгоритмів тісно пов'язана з розвитком теорії односторонніх функцій і з теорією складності. Під односторонньою функцією ми будемо розуміти легковичісляемое відображення f (x): X? Y, x ® X, при цьому зворотне відображення є складним завданням. Вона називається трудновичісляемой, якщо немає алгоритму для її вирішення з поліноміальним часом роботи. Легковичісляемой будемо називати задачу, що має алгоритм з часом роботи, представленим у вигляді полінома низького ступеня щодо вхідного розміру задачі, а ще краще алгоритм з лінійним часом роботи.
Розвитком ідеї односторонніх функцій з'явилася побудова односторонніх функцій з секретом (з потайним ходом). Такою функцією називається f (x)=y8, значення якої, як і в попередньому випадку, легко обчислити, тоді як зворотне значення без знання деякого секрету важко вирахувати. Знання ж секрету дозволяє досить просто реалізовувати операцію звернення односторонніх функцій з секретом. На практиці при застосуванні асиметричного алгоритму шифрування в роле секретного ключа виступає саме знання секрету, а в ролі відкритого ключа - знання процедури обчислення односторонньої функції з секретом.
Разом з тим необхідно відзначити, що стійкість більшості сучасних асиметричних алгоритмів базується на двох математичних проблемах, які на даному етапі є трудновичісляемимі навіть для методу грубої сили :
· дискретного логарифмування в кінцевих полях;
· факторизація великих чисел.
Оскільки на сьогоднішній день не існує ефективних алгоритмів вирішення даних завдань або їх вирішення вимагають залучення великих обчислювальних ресурсів або тимчасових витрат, ці математичні завдання знайшли широке застосування в побудові асиметричних алгоритмів. Їх стійкість розглядається як можливість звести про...
