Шифр Вернама

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

Опис ред.

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

Бути справді випадковим;
Збігатися за розміром з заданим відкритим текстом;
Застосовуватися тільки один раз;
Повинен зберігатися в повній таємниці сторонами, що спілкуються.

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

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

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

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

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

Криптографічна стійкість ред.

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

Наведемо підтвердження абсолютної криптографічної стійкості. Нехай повідомлення представлене двійковою послідовністю довжини $N:m=m_{1},m_{2},\ldots ,m_{n}$ . Розподіл ймовірності повідомлень $P_{m}(m)$ може бути будь-яким. Ключ також представлений двійковою послідовністю $k=k_{1},k_{2},\ldots ,k_{n}$ тієї ж довжини, але з рівномірним розподілом $P_{k}(k)=1/2^{N}$ для всіх ключів.

Відповідно до схеми шифрування, зробимо шифротекст, покомпонентно сумуючи за модулем 2 послідовності відкритого тексту та ключа:

$C=M\oplus K=(m_{1}\oplus k_{1},m_{2}\oplus k_{2},\ldots ,m_{N}\oplus k_{N})$

Легальний користувач знає ключ і здійснює розшифрування:

$M=C\oplus K=(c_{1}\oplus k_{1},c_{2}\oplus k_{2},\ldots ,c_{N}\oplus k_{N})$

Знайдемо ймовірнісний розподіл N-блоків шифротекстів, використовуючи формулу:

$P(c=a)=P(m\oplus k=a)=\sum _{m}{P(m)}P(m\oplus k=a|m)=\sum _{m}{P(m)1/2^{N}}=1/2^{N}$

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

Запишемо спільний розподіл відкритих текстів та шифротекстів:

$P(m=a,c=b)=P(m=a)P(c=b|m=a)$

Знайдемо умовний розподіл

$P(c=b|m=a)=P(m\oplus k=b|m=a)=P(k=b\oplus a|m=a)=P(k=b\oplus a)=1/2^{N},$

оскільки ключ та відкритий текст є незалежними випадковими величинами. Отже:

$P(c=b|m=a)=1/2^{N}$

Підстановка правої частини цієї формули у формулу для спільного розподілу дає

$P(m=a,c=b)=P(m=a)1/2^{N}$

Що доводить незалежність шифротекстів та відкритих текстів у цій системі. Це й означає абсолютну криптографічну стійкість.

Сфера застосування ред.

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

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

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

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

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

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

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

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

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

Приклад роботи ред.

Нехай потрібно зашифрувати повідомлення: "Wikipedia". Кожній букві алфавіту A(a) ... Z(z) (вважатимо, що повідомлення не чутливе до регістру) задається відповідно число від 0 до 25. Тобто a = 0, b = 1 і так далі до z = 25. Для роботи шифру необхідно утворити ключ, розміром як саме повідомлення, з дійсно випадкових чисел, ключ також можна задати відповідними літерами. Перетворення проводиться при шифруванні за таблицею Віженера. Тобто буква ключа є стовпцем, буква повідомлення — рядком, а шифртекст — це буква на перетині.

Шифрування ред.

Метод шифрування полягає в об’єднанні ключа і повідомлення за допомогою модульного додавання. Числове значення кожної літери додається до відповідного значення ключа за модулем 26 (кількість літер в алфавіті). Тобто якщо сума більша за 25, то від неї віднімається 26. Після чого утвореному числу відповідно ставиться буква.

Повідомлення: Wikipedia         ->  22    8   10    8   15    4   3    8   0
Ключ:         RPXHGQDYG         ->  17   15   23    7    6   16   3   24   6
Повідомлення + ключ             ->  39   23   33   15   21   20   6   32   6
(Повідомлення + ключ) за mod 26 ->  13   23    7   15   21   20   6    6   6
Зашифроване повідомлення: NXHPVUGGG

Дешифрування ред.

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

Зашифроване повідомлення: NXHPVUGGG ->  13   23     7   15   21   20   6     6   6
Ключ:                     RPXHGQDYG ->  17   15    23    7    6   16   3    24   6
Повідомлення - ключ                 ->  -4    8   -16    8   15    4   3   -18   0
(Повідомлення - ключ) за mod 26     ->  22    8    10    8   15    4   3     8   0
Повідомлення: WIKIPEDIA

Вади ред.

Для роботи шифру Вернама необхідна дійсно випадкова послідовність нулів та одиниць (ключ). За визначенням, послідовність, отримана з використанням будь-якого алгоритму, є не зовсім випадковою, а псевдовипадковою. Тобто, потрібно отримати випадкову послідовність неалгорітмічно (наприклад, використовуючи радіоактивний розпад ядер, створений електронним генератором білий шум або інші досить випадкові події). Щоб зробити розподіл гранично близьким до рівномірного, випадкову послідовність зазвичай проганяються через хеш-функцію на кшталт MD5.

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

Можливі проблеми з надійним знищенням використаної сторінки. Це стосується як паперових сторінок блокнота, так і сучасних електронних реалізацій з використанням компакт-дисків або флеш-пам'яті.

Якщо третя сторона якимось чином зрозуміє повідомлення, вона легко відновить ключ і зможе підмінити повідомлення на інше такої ж довжини.

Шифр Вернама чутливий до будь-якого порушення процедури шифрування. Наприклад, контррозвідка США часто розшифровувала радянські та німецькі послання через неточності генератора випадкових чисел (програмний генератор псевдовипадкових чисел у німців і друкарка, що б'є по клавішах, в СРСР). Бували випадки, коли одна і та ж сторінка блокнота застосовувалася двічі - США також могли розшифровувати такі послання.

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

Реалізація ред.

Python ред.

Представлення літер в таблиці Unicode: A = 65 ... Z = 90

from random import randint # Генератор псевдовипадкових чисел

def encrypt(message):
    crypt_text = ""
    keys = []
    
    for symbol in message.upper():
        key = randint(0, 25) # Генерація псевдовипадкового число
        keys.append(str(key))
        
        if ord(symbol) < 65 or ord(symbol) > 90: # Якщо символ не з алфавіту, то замість нього ставиться пробіл
            crypt_text += " "
        else: # В іншому випадку за допомогою ключа шифрується літера
            num = ord(symbol) + key - 13
            crypt_text += chr((num % 26) + 65)
            
    str_keys = " ".join(keys) # Перетворення списку ключів у стрічку
    print(crypt_text)
    print(str_keys) 
    
def decrypt(crypt_text, keys):
    arr_keys = keys.split(" ") # Перетворення стрічки ключів у список
    decrypt_text = ""
    
    for idx, symbol in enumerate(crypt_text):
        if ord(symbol) < 65 or ord(symbol) > 90: # Якщо символ не з алфавіту, то замість нього ставиться пробіл
            decrypt_text += " "
        else: # В іншому випадку вираховується номер з таблиці Unicode
            num = ord(symbol) - int(arr_keys[idx]) - 13
            decrypt_text += chr((num % 26) + 65)
    
    print(decrypt_text)
    
encrypt("Wikipedia") # Шифрування
decrypt("NXHPVUGGG", "17 15 23 7 6 16 3 24 6") # Дешифрування

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

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

Цікаво ред.

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

Див. також ред.

Джерела ред.

Тарнавський (2018). Технології захисту інформації [Архівовано 3 грудня 2021 у Wayback Machine.]. КПІ ім. Ігоря Сікорського.

Примітки ред.

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

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

https://web.archive.org/web/20090226031750/http://www.cio-world.ru/bsolutions/e-safety/35728//
http://students.uni-vologda.ac.ru/pages/pm00/kan/symmetric.htm [Архівовано 23 квітня 2009 у Wayback Machine.]
offline.computerra.ru/1999/305/3111
www.agentura.ru/press/about/jointprojects/confident/crypto19end
Шифроблокнот КГБ [Архівовано 29 січня 2009 у Wayback Machine.](англ.)

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

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

[1]