Виступ на семінарі:Олійник Ігор Богданович:Шифр Вернама
Презентація доповіді (університетський репозиторій)
Зміст
Опис
Для відтворення шифртексту відкритий текст об'єднується операцією «виключне АБО» з ключем(названим одноразовим блокнотом або шифроблокнотом). При цьому ключ повинен володіти трьома критично важливими властивостями:
1. Бути справді випадковим;
2. Збігатися з розміром з заданим відкритим текстом;
3. Застосовуватися тільки один раз.
Шифр названий на честь телеграфіста AT&T Гільберта Вернама, що в 1917 році побудував телеграфний апарат, який виконував цю операцію автоматично - треба було тільки подати на нього стрічку з ключем. Не будучи шифрувальником, тим не менше, Вернам вірно помітив важливу властивість свого шифру - кожна стрічка повинна використовуватися тільки один раз і після цього знищуватися. Це було важко застосувати на практиці - тому апарат був перероблений на кілька зациклених стрічок з взаємно простими періодами.
Властивості
В 1949 році Клод Шеннон опублікував роботу, в якій довів абсолютну стійкість шифру Вернама. Інших шифрів з цією властивістю не існує. Це по суті означає, що шифр Вернама є найбезпечнішою криптосистемою з усіх можливих. При цьому умови, яким повинен задовольняти ключ, настільки сильні, що практичне використання шифру Вернама є важко здійсненним. Тому він використовується тільки для передачі повідомлень найвищої секретності.
Розвиток
На початку 20 ст. для передачі повідомлень все ширше і ширше використовувалися телетайпи. Тому потрібні були методи, що дозволяють шифрувати текст не до того, як він потрапляє до телеграфіста, а безпосередньо в момент передачі, і, відповідно, розшифровувати в момент прийому. Дуже хотілося доручити цю справу машині. Як виявилося, коливання струму в лінії передачі можна легко записати за допомогою осцилографа і потім перетворити у літери переданого повідомлення. Змінивши з'єднання проводів телетайпа, телеграфісти отримували повідомлення, зашифроване методом одноалфавітной заміни. Всі розуміли, що такий захист надто слабкий, але, не зумівши вигадати нічого іншого, користувалися ним до тих самих пір, поки Вернам не запропонував використовувати для кодування повідомлень особливості телетайпного коду, в якому знак, що кодується виражається у вигляді п'яти елементів. Кожен з цих елементів символізує наявність («плюс») або відсутність («мінус») електричного струму в лінії зв'язку. Наприклад, літера «А» відповідає комбінація «+ - - - -». Підготовлене до відправки повідомлення набивається на перфострічці: отвору відповідає «плюс» коду, його відсутність - «мінус». В процесі передачі металеві щупи телетайпа проходять через отвори, замикаючись у ланцюг, і посилають імпульси струму («+»). Там, де отворів немає і папір не дозволяє щупам замкнути ланцюг, імпульс не передається («-»).
Для шифрування Вернам запропонував заздалегідь готувати «гаму» - перфострічку з випадковими знаками - і потім електромеханічно складати її імпульси з імпульсами знаків відкритого тексту. Отримана сума представляла собою шифртекст. На приймальному кінці імпульси, отримані по каналу зв'язку, складалися з імпульсами тієї ж самої «гами», в результаті чого відновлювалися вихідні імпульси повідомлення. А якщо повідомлення перехоплювати, то без «гами» розшифрувати його було неможливо, противник бачив тільки нічого не значущу послідовність «плюсів» і «мінусів».
Подальше вдосконалення методу, запропонованого Вернамом, належить майбутньому начальнику зв'язку військ США Джозеф Моборну, що об'єднав хаотичність «гами», на яку спирався Вернам у своїй системі «автоматичного шифрування», з використовуваним у той час у військах правилом «одноразового шифрблокнота». Ідея Моборна полягала в тому, що кожна випадкова «гама» повинна використовуватися один, і тільки один раз. При цьому для шифрування кожного знака всіх текстів, які вже передані або будуть передані в найближчому майбутньому, повинен застосовуватися абсолютно новий і такий, що не піддається передбаченню знак «гами».
Область застосування
На практиці можна один раз фізично передати носій інформації з довгим дійсно випадковим ключем, а потім по мірі необхідності пересилати повідомлення. На цьому заснована ідея шифроблокнотів: шифрувальник при особистій зустрічі забезпечується блокнотом, кожна сторінка якого містить ключ. Такий же блокнот є і у приймаючої сторони. Використані сторінки знищуються.
Крім того, якщо є два незалежних канали, в кожному з яких ймовірність перехоплення низька, але відрізняється від нуля, шифр Вернама також можна застосувати: по одному каналу можна передати зашифроване повідомлення, по другому - ключ. Для того, щоб розшифрувати повідомлення, перехоплювач повинен прослуховувати обидва канали.
Шифр Вернама може застосовуватися, якщо є односторонній захищений канал: ключ передається в одну сторону під захистом каналу, повідомлення в іншу сторону повідомлення захищаються ключем.
Не є шифром Вернама, але близька до нього схема одноразових кодів: наприклад, кодове слово «Альфа» означає «Повертаюсь».
Технічне застосування
У період між двома світовими війнами в більшості країн з'являються електромеханічні шифратори. Вони були двох типів. Перший - пристрій, що складається з комутаційних дисків та механізму зміни їх кутових положень. За обома сторонами комутаційного диска розміщені контакти, відповідні алфавіту відкритого та шифрованого тексту. Контакти ці з'єднуються між собою відповідно до деякого правила підстановки, що зветься комутацією диска. Ця комутація визначає заміну літер в початковому кутовому положенні. При зміні кутового положення диска змінюється і правило підстановки. Таким чином, ключ шифрування містить кілька невідомих: схему з'єднання контактів і початкове кутове положення. Якщо після шифрування кожної літери міняти кутове положення диска - отримаємо многоалфавітное шифрування. Ще більш складний пристрій отримаємо, з'єднавши послідовно кілька дисків, кутові положення яких змінюються з різною швидкістю.
Широко відома шифрмашина «Енігма», якою були оснащені німецькі війська часів Другої світової війни, є типовим прикладом пристрою на комутаційних дисках. Конструктивно «Енігма» походила на звичайну друкарську машинку, тільки натискання клавіші призводило не до удару молоточка по папері, а створювало електричний імпульс, що надходив у схему криптоперетворення. Американська шифрмашина М-209 - типовий приклад другого типу шифратора, - шифратора на цівочних дисках.
Цікаво, що Радянський Союз виробляв шифрмашини обох названих типів.
Таким чином, перед Другою світовою війною всі провідні країни мали на озброєнні електромеханічні шифрсистеми, що володіють високою швидкістю обробки інформації і високою стійкістю. Вважалося, що застосовувані системи неможливо розшифрувати і криптоаналізу більше робити абсолютно нічого. Як часто буває, ця думка була згодом спростована, і дешифровщики були безпосередніми учасниками бойових дій.
Переваги
Завдяки накладеним обмеженням на ключ, в 1949 році Клод Шенон довів, що шифр Вернама є абсолютно криптостійким.
Недоліки
1. Для роботи шифру Вернама необхідна дійсно випадкова послідовність нулів та одиниць (ключ). За визначенням, послідовність, отримана з використанням будь-якого алгоритму, є не зовсім випадковою, а псевдовипадковою. Тобто, потрібно отримати випадкову послідовність неалгорітмічно (наприклад, використовуючи радіоактивний розпад ядер, створений електронним генератором білий шум або інші досить випадкові події). Щоб зробити розподіл гранично близьким до рівномірного, випадкову послідовність зазвичай проганяються через хеш-функцію на кшталт MD5.
2. Проблемою є таємна передача послідовності та збереження її в таємниці. Якщо існує надійно захищений від перехоплення канал передачі повідомлень, шифри взагалі не потрібні: секретні повідомлення можна передавати з цього каналу. Якщо ж передавати ключ системи Вернама за допомогою іншого шифру (наприклад, DES), то отриманий шифр буде захищеним рівно настільки, наскільки захищений DES. При цьому, оскільки довжина ключа така ж, як і довжина повідомлення, передати його не простіше, ніж повідомлення. Шифроблокнот на фізичному носії можна вкрасти або скопіювати.
3. Можливі проблеми з надійним знищенням використаної сторінки. Цьому схильні як паперові сторінки блокнота, так і сучасні електронні реалізації з використанням компакт-дисків або флеш-пам'яті.
4. Якщо третя сторона якимось чином дізнається повідомлення, вона легко відновить ключ і зможе підмінити повідомлення на інше такої ж довжини.
5. Шифр Вернама чутливий до будь-якого порушення процедури шифрування. Наприклад, контррозвідка США часто розшифровувала радянські та німецькі послання із-за неточностей генератора випадкових чисел (програмний генератор псевдовипадкових чисел у німців і друкарка, що б'є по клавішах, в СРСР). Бували випадки, коли одна і та ж сторінка блокнота застосовувалася двічі - США також розшифровувати такі послання.
Тим не менш, схема шифроблокнотів досить надійна при ручній шифровці. Перераховані вище недоліки можна усунути, якщо застосувати квантову криптографію, зокрема, протокол BB84 для генерації та передачі одноразових блокнотів. У разі використання квантової криптографії шифр Вернама також буде досить надійним.
Висновки
Шифр Вернама найбільш надійним серед собі подібних, що забезпечується:
1. Абсолютною крипкостійтістю.
2. Навіть якщо підбирати ключ методом перебору, то якщо врахувати, що на кожен символ повідомлення припадає 8 біт(0 і 1), ми шифруємо повідомлення обємом 1 КБ, шифроване повідомлення – ~8 КБ, тобто більше 8000 символів. Для підбору ключа потрібно виконати 2^8000!!! операцій підстановки.
br> Він має ряд недоліків:br> - Взамін на абсолютну стійкість цей метод потребує надто великих обрахунків, що не завжди виправдано. Іноді достатньо забезпечити криптостійкість на деякий час.
Як говорив Остап Бендер: «Мені не потрібна вічна голка для примуса, я не планую жити вічно».
Список використаних джерел:
1. http://uk.wikipedia.org/wiki/
2. http://www.kriptolog.net/blog/shifr-vernama
3. http://cadzone.ru/content/view/1382/48/
