алгоритм Діффі
Алгоритм Діффі - Хеллмана (англ. Diffie-Hellman. DH) - алгоритм. дозволяє двом сторонам отримати загальний секретний ключ, використовуючи незахищений канал зв'язку. Цей ключ може бути використаний для шифрування подальшого обміну за допомогою алгоритму симетричного шифрування.
Історія Правити
Роком пізніше був винайдений перший алгоритм асиметричного шифрування RSA. який вирішив проблему спілкування через незахищений канал кардинально, вже не вимагаючи, щоб кожна сторона мала копію одного і того ж секретного ключа.
«Ця система ... з тих пір відома під назвою алгоритму Діффі - Хеллмана. Однак, коли система була вперше описана на папері Діффі і мною, це була система поширення публічних ключів, концепція якої була вироблена Меркле, і тому вона повинна називатися "алгоритмом Діффі - Хеллмана - Меркле", якщо її пов'язують з іменами. Я сподіваюся що це невелика зміна допоможе визнанню рівного вкладу Меркле в винахід криптографії з відкритими ключами. »[1]
У патенті U.S. Patent 4,200,770 (англ.) (В даний час минулий), що описує даний алгоритм, винахідниками значаться Хеллман, Діффі і Меркле.
Опис алгоритму Правити
Припустимо, що обом абонентам відомі деякі два числа g і p (наприклад, вони можуть бути «зашиті» в програмне забезпечення), які не є секретними і можуть бути відомі також іншим зацікавленим особам. Для того, щоб створити невідомий більш нікому секретний ключ, обидва абонента генерують великі випадкові числа: перший абонент - число a, другий абонент - число b. Потім перший абонент обчислює значення і пересилає його другого, а другий обчислює і передає першому. Передбачається, що зловмисник може отримати обидва цих значення, але не модифікувати їх (тобто у нього немає можливості втрутитися в процес передачі). На другому етапі перший абонент на основі наявної в нього і отриманого по мережі обчислює значення, а другий абонент на основі наявної в нього і отриманого по мережі обчислює значення. Як неважко бачити, у обох абонентів вийшло одне і те ж число:. Його вони і можуть використовувати в якості секретного ключа, оскільки тут зловмисник зустрінеться з практично нерозв'язною (за розумний час) проблемою обчислення по перехоплених і, якщо числа обрані досить великими.
При роботі алгоритму, кожна сторона:
- генерує випадкове натуральне число a - закритий ключ
- спільно з віддаленої стороною встановлює відкриті параметриp і g (зазвичай значення p і g генеруються на одній стороні і передаються іншій), де p є випадковим простим числом g є первісним коренем за модулем p
- обчислює відкритий ключA. використовуючи перетворення над закритим ключомA = g a mod p
- обмінюється відкритими ключами з віддаленої стороною
- обчислює загальний секретний ключK. використовуючи відкритий ключ віддаленої сторони B і свій закритий ключ aK = B a mod Pк виходить рівним з обох сторін, тому що: B a mod p = (gb mod p) a mod p = g ab mod p = (ga mod p) b mod p = A b mod p
У практичних реалізаціях, для a і b використовуються числа близько 10 100 і p близько 10 300. Число g не повинно бути великим і зазвичай має значення 2 або 5.
Криптографічний стійкість Правити
Криптографічний стійкість алгоритму Діффі - Хеллмана (тобто складність обчислення K = g ab mod p по відомим p. G. A = g a mod p і B = g b mod p), заснована на передбачуваній складності проблеми дискретного логарифмування. Однак, хоча вміння вирішувати проблему дискретного логарифмування дозволить зламати алгоритм Діффі - Хеллмана, зворотне твердження до сих є відкритим питанням (іншими словами, еквівалентність цих проблем не доведена).
Необхідно ще раз відзначити, що алгоритм Діффі - Хеллмана працює тільки на лініях зв'язку, надійно захищених від модифікації. Якби він був застосуємо на будь-яких відкритих каналах, то давно зняв би проблему поширення ключів і, можливо, замінив собою всю асиметричну криптографію. Однак, в тих випадках, коли в каналі можлива модифікація даних, з'являється очевидна можливість вклинювання в процес генерації ключів «зловмисника-посередника» за тією ж самою схемою, що і для асиметричної криптографії.