Шифр Вернама

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Шифр Вернама (інша назва: англ. one-time pad - схема одноразових блокнотів) — у криптографії, система симетричного шифрування, винайдена в 1917 році співробітниками AT&T Мейджором Джозефом Моборном і Гільбертом Вернамом. Шифр Вернама є єдиною системою шифрування, для якої доведена абсолютна криптографічна стійкість.

Опис[ред.ред. код]

Для утворення шифртексту повідомлення об'єднується операцією XOR з ключем (названим одноразовим блокнотом або шифроблокнотом). При цьому ключ повинен мати три критично важливі властивості:

  1. Бути справді випадковим;
  2. Збігатися за розміром з заданим відкритим текстом;
  3. Застосовуватися тільки один раз.

Шифр названий на честь телеграфіста AT&T Гільберта Вернама, який у 1917 році побудував телеграфний апарат, що виконував цю операцію автоматично - треба було тільки подати на нього стрічку з ключем. Не будучи шифрувальником, Вернам, тим не менш, вірно помітив важливу властивість свого шифру - кожна стрічка повинна використовуватися тільки один раз і після цього знищуватися. Це було важко застосувати на практиці - тому апарат був перероблений на кілька зациклених стрічок із взаємно простими періодами.

Розвиток[ред.ред. код]

На початку 20 ст. для передачі повідомлень все ширше і ширше використовувалися телетайпи. Тому потрібні були методи, що дозволяють шифрувати текст не до того, як він потрапляє до телеграфіста, а безпосередньо в момент передачі, і, відповідно, розшифровувати в момент прийому. Дуже хотілося доручити цю справу машині. Як виявилося, коливання струму в лінії передачі можна легко записати за допомогою осцилографа і потім перетворити у літери переданого повідомлення. Змінивши з'єднання проводів телетайпа, телеграфісти отримували повідомлення, зашифроване методом одноалфавітної заміни. Усі розуміли, що такий захист надто слабкий, але, не зумівши вигадати нічого іншого, користувалися ним доти, поки Вернам не запропонував використовувати для кодування повідомлень особливості телетайпного коду, в якому знак, що кодується, виражається у вигляді п'яти елементів. Кожен з цих елементів символізує наявність («плюс») або відсутність («мінус») електричного струму в лінії зв'язку. Наприклад, літера «А» відповідає комбінація «+ - - - -». Підготовлене до відправки повідомлення набивається на перфострічці: отвору відповідає «плюс» коду, його відсутність - «мінус». В процесі передачі металеві щупи телетайпа проходять через отвори, замикаючись у ланцюг, і посилають імпульси струму («+»). Там, де отворів немає і папір не дозволяє щупам замкнути ланцюг, імпульс не передається («-»).

Для шифрування Вернам запропонував заздалегідь готувати «гаму» - перфострічку з випадковими знаками - і потім електромеханічно складати її імпульси з імпульсами знаків відкритого тексту. Отримана сума являла собою шифртекст. На приймальному кінці імпульси, отримані по каналу зв'язку, складалися з імпульсами тієї ж самої «гами», в результаті чого відновлювалися вихідні імпульси повідомлення. А якщо повідомлення перехоплювати, то без «гами» розшифрувати його було неможливо, противник бачив тільки беззмістовну послідовність «плюсів» і «мінусів».

Подальше вдосконалення методу, запропонованого Вернамом, належить майбутньому начальнику зв'язку військ США Джозеф Моборну, которий об'єднав хаотичність «гами», на яку спирався Вернам у своїй системі «автоматичного шифрування», з використовуваним у той час у військах правилом «одноразового шифрблокнота». Ідея Моборна полягала в тому, що кожна випадкова «гама» повинна використовуватися один, і тільки один раз. При цьому для шифрування кожного знака всіх текстів, які вже передані або будуть передані в найближчому майбутньому, повинен застосовуватися абсолютно новий і такий, що не піддається передбаченню, знак «гами».

Властивості[ред.ред. код]

У 1945 році Клод Шеннон написав роботу (розсекречену лише після Другої світової війни у 1949 р.), у якій довів абсолютну стійкість шифру Вернама. Інших шифрів з цією властивістю не існує. Але дана властивість забезпечується лише за умови використання випадкового ключа, довжина якого дорівнює довжині повідомлення. Це обмеження робить використання шифру недоцільним, оскільки для обміну ключами сторони мають передати по захищеному каналу об’єм інформації, що дорівнює повідомленню (за наявності такого каналу доцільніше одразу передати саме повідомлення).

Область застосування[ред.ред. код]

На практиці можна один раз фізично передати носій інформації з довгим дійсно випадковим ключем, а потім у міру потреби пересилати повідомлення. На цьому заснована ідея шифроблокнотів: шифрувальник при особистій зустрічі забезпечується блокнотом, кожна сторінка якого містить ключ. Такий же блокнот є і в приймаючої сторони. Використані сторінки знищуються.

Крім того, якщо є два незалежних канали, в кожному з яких ймовірність перехоплення низька, але відрізняється від нуля, шифр Вернама також можна застосувати: по одному каналу можна передати зашифроване повідомлення, по другому - ключ. Для того, щоб розшифрувати повідомлення, перехоплювач повинен прослуховувати обидва канали.

Шифр Вернама може застосовуватися, якщо є односторонній захищений канал: ключ передається в одну сторону по захищеному каналу, в іншу сторону повідомлення захищаються ключем.

Не є шифром Вернама, але близька до нього схема одноразових кодів: наприклад, кодове слово «Альфа» означає «Повертаюсь».

Технічне застосування[ред.ред. код]

У період між двома світовими війнами в більшості країн з'являються електромеханічні шифратори. Вони були двох типів. Перший - пристрій, що складається з комутаційних дисків та механізму зміни їх кутових положень. За обома сторонами комутаційного диска розміщені контакти, які відповідають алфавіту відкритого та шифрованого тексту. Контакти ці з'єднуються між собою відповідно до деякого правила підстановки, що зветься комутацією диска. Ця комутація визначає заміну літер в початковому кутовому положенні. При зміні кутового положення диска змінюється і правило підстановки. Таким чином, ключ шифрування містить кілька невідомих: схему з'єднання контактів і початкове кутове положення. Якщо після шифрування кожної літери міняти кутове положення диска - отримаємо многоалфавітное шифрування. Ще складніший пристрій отримаємо, з'єднавши послідовно кілька дисків, кутові положення яких змінюються з різною швидкістю.

Широко відома шифрмашина «Енігма», якою були оснащені німецькі війська часів Другої світової війни, є типовим прикладом пристрою на комутаційних дисках. Конструктивно «Енігма» була схожою на звичайну друкарську машинку, тільки натискання клавіші призводило не до удару молоточка по папері, а створювало електричний імпульс, що надходив у схему криптоперетворення. Американська шифрмашина М-209 - типовий приклад другого типу шифратора, - шифратора на цівочних дисках.

Цікаво, що Радянський Союз виробляв шифрмашини обох названих типів.

Таким чином, перед Другою світовою війною всі провідні країни мали на озброєнні електромеханічні шифрсистеми, що мають високу швидкість обробки інформації і високу стійкість. Вважалося, що застосовувані системи неможливо розшифрувати, і криптоаналізу більше робити абсолютно нічого. Як часто буває, ця думка була згодом спростована, і дешифрувальники були безпосередніми учасниками бойових дій.

Вади[ред.ред. код]

  • Для роботи шифру Вернама необхідна дійсно випадкова послідовність нулів та одиниць (ключ). За визначенням, послідовність, отримана з використанням будь-якого алгоритму, є не зовсім випадковою, а псевдовипадковою. Тобто, потрібно отримати випадкову послідовність неалгорітмічно (наприклад, використовуючи радіоактивний розпад ядер, створений електронним генератором білий шум або інші досить випадкові події). Щоб зробити розподіл гранично близьким до рівномірного, випадкову послідовність зазвичай проганяються через хеш-функцію на кшталт MD5.
  • Проблемою є таємна передача послідовності та збереження її в таємниці. Якщо існує надійно захищений від перехоплення канал передачі повідомлень, шифри взагалі не потрібні: секретні повідомлення можна передавати з цього каналу. Якщо ж передавати ключ системи Вернама за допомогою іншого шифру (наприклад, DES), то отриманий шифр буде захищеним рівно настільки, наскільки захищений DES. При цьому, оскільки довжина ключа така ж, як і довжина повідомлення, передати його не простіше, ніж повідомлення. Шифроблокнот на фізичному носії можна вкрасти або скопіювати.
  • Можливі проблеми з надійним знищенням використаної сторінки. Це стосується як паперових сторінок блокнота, так і сучасних електронних реалізацій з використанням компакт-дисків або флеш-пам'яті.
  • Якщо третя сторона якимось чином зрозуміє повідомлення, вона легко відновить ключ і зможе підмінити повідомлення на інше такої ж довжини.
  • Шифр Вернама чутливий до будь-якого порушення процедури шифрування. Наприклад, контррозвідка США часто розшифровувала радянські та німецькі послання через неточності генератора випадкових чисел (програмний генератор псевдовипадкових чисел у німців і друкарка, що б'є по клавішах, в СРСР). Бували випадки, коли одна і та ж сторінка блокнота застосовувалася двічі - США також могли розшифровувати такі послання.

Тим не менш, схема шифроблокнотів досить надійна при ручній шифровці. Перераховані вище недоліки можна усунути, якщо застосувати квантову криптографію, зокрема, протокол BB84 для генерації та передачі одноразових блокнотів. У разі використання квантової криптографії шифр Вернама також буде досить надійним.

Шифр Вернама в мистецтві[ред.ред. код]

В американському кінофільмі 2001 року "Пароль «Риба-меч»" хакер (якого грає Х'ю Джекмен) зламує саме шифр Вернама.

Цікаво[ред.ред. код]

Ще в середині 1990-х шифр Вернама використовували для зв'яку між Москвою і Вашингтоном, ключ доставляли довіреним кур'єром.[1]

Примітки[ред.ред. код]

  1. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Handbook of applied cryptography. — CRC-Press, 1996. — С. 21. — ISBN 0849385237.

Посилання[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.