бота зберігалася лише у внутрішніх документах центру, тому про її існування була не відомо до 1977 року. RSA став першим алгоритмом, придатним і для шифрування, і для цифрового підпису.
Взагалі, в основу відомих асиметричних криптосистем кладеться одна зі складних математичних проблем, яка дозволяє будувати односторонні функції та функції-лазівки. Наприклад, криптосистеми Меркля - Хеллмана і Хору - Ривеста спираються на так звану задачу про укладання рюкзака.
Основні принципи побудови криптосистем з відкритим ключем
Починаємо з важкого завдання. Вона повинна вирішуватися складно в сенсі теорії: не повинно бути алгоритму, за допомогою якого можна було б перебрати всі варіанти рішення задачі за поліноміальний час щодо розміру завдання. Більш правильно сказати: не повинно бути відомого полиномиального алгоритму, вирішального дану задачу - так як ні для однієї задачі ще поки не доведено, що для неї відповідного алгоритму немає в принципі.
Можна виділити легку підзадачу з. Вона повинна вирішуватися за поліноміальний час і краще, якщо за лінійне.
«перетасовують і збовтуємо», щоб отримати задачу, зовсім не схожу на початкову. Завдання має принаймні виглядати як оригінальна важковирішувана задача.
відкривається з описом, як вона може бути використана в ролі ключа зашифрування. Як з отримати, тримається в секреті як секретна лазівка.
Криптосистема організована так, що алгоритми розшифрування для легального користувача і криптоаналитика істотно різні. У той час як другий вирішує-задачу, перший використовує секретну лазівку і вирішує-задачу.
Криптографія з декількома відкритими ключами
У наступному прикладі показана схема, в якій Аліса шифрує повідомлення так, що тільки Боб може прочитати його, і навпаки, Боб шифрує повідомлення так, що тільки Аліса може розшифрувати його.
Нехай є 3 ключа,,, розподілені так, як показано в таблиці.
криптографія шифрування ключ симетричний
ЛіцоКлючАліса Боб Керол Дейв, Еллен, Франк, Тоді Аліса може зашифрувати повідомлення ключем, а Еллен розшифрувати ключами,, Керол - зашифрувати ключем, а Дейв розшифрувати ключами,. Якщо Дейв зашифрує повідомлення ключем, то повідомлення зможе прочитати Еллен, якщо ключем, то його зможе прочитати Франк, якщо ж обома ключами і, то повідомлення прочитає Керол. За аналогією діють й інші учасники. Таким чином, якщо використовується одне підмножина ключів для шифрування, то для розшифрування потрібні залишилися ключі множини. Таку схему можна використовувати для n ключів.
Шифрується ключомРасшіфровивается ключем і і і,,,
Тепер можна посилати повідомлення групам агентів, не знаючи заздалегідь склад групи.
Розглянемо для початку безліч, що складається з трьох агентів: Аліси, Боба і Керол. Алісі видаються ключі і, Бобу - і, Керол - і. Тепер, якщо отправляемое повідомлення зашифровано ключем, то його зможе прочитати тільки Аліса, послідовно застосовуючи ключі і. Якщо потрібно відправити повідомлення Бобу, повідомлення шифрується ключем, Керол - ключем. Якщо потрібно відправити повідомлення і Алісі і Керол, то для шифрування використовуються ключі і.
Перевага цієї схеми полягає в тому, що для її реалізації потрібно тільки одне повідомлення і n ключів (у схемі з n агентами). Якщо передаються індивідуальні повідомлення, тобто викори...
