одноразовий шифроблокнота

Кілька років тому одного британського айтішника надовго посадили за співпрацю з терористами, з якими він листувався допомогою самопального шифру, запрограмованого в Ексель. Незважаючи на те, що йому цілком була доступна сучасна криптографія, некомпетентність його підвела і легко розкрита правоохоронними органами листування була використана проти нього ж в суді. Oops ...

У криптографії є ​​кілька емпіричних законів, найголовніший з яких формулюється дуже просто: ніколи не винаходьте власний шифр! Шифри винаходять або новачки-дилетанти, або фахівці з криптографії. У першому випадку шифр легко ламається фахівцем або навіть просто більш-менш міркувати дилетантом, у другому ... буває по-різному, особливо з урахуванням бурхливого зростання продуктивності комп'ютерів. Але деякі шифри витримують випробування часом. Про один такий шифр і піде мова.

Для застосування більшості сучасних надійних шифрів потрібна наявність більш-менш пристойної ЕОМ. Але, на щастя, є шифр, який доступний в будь-століття і часи і не вимагає серйозних обчислювальних потужностей, залишаючись принципово невзламиваемим. Більш того, це єдиний на сьогоднішній день шифр, невзламиваемость якого доводиться математично (це довів Клод Шеннон в 1945 році). Знайомтеся: шифр Вернама , Або, як його ще називають в паперовому варіанті, одноразовий шифроблокнота.

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

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

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

Спочатку треба перетворити ваш текст в цифри. Для цього використовується стискає таблиця (straddling checkerboard). В якомусь сенсі це аналог алгоритмів, що лежать в основі zip, rar і ​​т.п., тільки таблиця стиснення у нас фіксована. Ні, ви звичайно можете і просто зіставити буквах цифри за принципом А = 1, Б = 2 і т.д, але через надмірність мови ви будете змушені потім шифрувати десь на третину більше. Просидівши кілька годин з олівцем за тупий арифметикою, ви швидко оціните переваги стискає таблиці ...

Для створення стискає таблиці запам'ятовуємо: А І ТЕСНО. Тут задіяно сім найчастіших букв в російській мові. Для англійської беремо скажімо AT ONE SIR (в англійській мові менше букв і можна обійтися тільки двома доп. Рядками) і т.п. Складаємо таблицю, в першому рядку якої йдуть часто зустрічаються символи, а в інших залишки алфавіту. Зверніть увагу, що в першому рядку не задіяні цифри 8, 9 і 0, і вони ж позначають, що буква (рідше зустрічається) кодується не однієї цифрою, а двома. Отже, для кодування літери шукаємо її, якщо вона знаходиться в першому рядку, то ми вибираємо номер її колонки (наприклад Т = 3), якщо вона в інших колонках, то ми спочатку вибираємо номер її рядки, а потім номер колонки, наприклад Б = 81, а? = 07:

1 2 3 4 5 6 7 8 9 0 А І Т Е С Н Про 8 Б В Г Д Ж З К Л М П 9 Р У Ф Х Ц Ч Ш Щ ред И 0 Ь Е Ю Я. ,?

Можна додати ще-щось корисне в що залишилися три осередки в останньому рядку (в реальності крім букв часто використовувалися спеціальні коди для початку передачі цифр, почала передачі спеціальних кодів з кодових таблиць і т.п.). Отже, нам треба зашифрувати коротке повідомлення:

ВТЕЧА ЗАВТРА

Перша буква повідомлення знаходиться в другому рядку таблиці, так що беремо номер рядка, а потім номер колонки: 80. Далі друга буква має високу частоту і знаходиться в першому рядку, тому беремо тільки її колонку: 7. Отримуємо послідовність цифр. Добиваємо нулями останню групу до п'яти цифр:

80781 48386 18239 11000

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

Але ПОКИ ЩО це ще не шифр! Закодований вищенаведеним способом текст уже помітно складніше взяти в лоб простим частотним аналізом, але все одно на шифр воно ніяк не тягне. Тепер видирає сторінку з одноразового шифроблокнота, наведеного на ілюстрації і починаємо з нею працювати. Увага! Ніколи не можна в кодуванні вказувати номер сторінки шифроблокнота, щоб не дати можливість проаналізувати послідовність кодувань або вгадати час її відправки (що може виявитися не менш критичним, ніж її вміст)! Замість цього для ідентифікації сторінки використовується перша група, її не слід використовувати для шифрування, а записати як є. Під цифрами шифровки записуємо цифри одноразового коду починаючи з другої групи, після чого складаємо цифри в кожному стовпчику, завжди відкидаючи виникає перенесення:

80781 48386 18239 11000 + 14358 89753 24133 40169 26799 = 14358 69434 62419 58398 37799

Ось це вже і є шифровка:

14358 69434 62419 58398 37799

Тепер залишилося спалити сторінку, за допомогою якої ми шифрували, і відправити нашу шифровку за призначенням. Одержувач дістане свою копію шифроблокнота, знайде потрібну сторінку по першій групі і зробить спочатку зворотну операцію, віднімаючи з кожної цифри шифровки цифру з шифроблокнота, завжди відкидаючи мінус. Потім візьме стискає таблицю і за допомогою неї вже остаточно розкодує текст. Точно так же - беремо 8, ага, це другий рядок, 0 колонка, значить перша буква П., і так далі. А потім теж спалить свою копію і більше ніхто і ніколи не зможе розшифрувати перехоплене повідомлення. А якщо шифроблокнота буде вчасно знищений, то і терморектальний криптоаналіз не допоможе в розшифровці: жодна людина не в змозі пригадати хоча б півсторінки шифроблокнота з випадковими числами.

Ну, а тепер найголовніше (і саме трудомістке): як згенерувати достатню кількість випадкових чисел. Адже одноразовий шифроблокнота передбачає знищення кожної сторінки після розшифровки, і для передачі певного обсягу тексту треба таку ж кількість випадкових даних! Це і є другим недоліком одноразового шифроблокнота: створення шифроблокнота заняття тривале і трудомістке, причому треба зуміти створити реально випадкову послідовність. Перше, що спадає на думку, це взяти кістки і накидати набір чисел, ось тільки на звичайних гральних кістках всього лише цифри від 1 до шести, а кидати пару кісток і складати цифри не можна, тому що розподіл суми вже підпорядковується цілком зрозумілою закономірності і у вас вийде не зовсім випадкова послідовність цифр. Можна звичайно спробувати зробити кістка на d10, як на ілюстрації справа, але спробуйте її виточити напилком з достатньою точністю!

Якщо ж використовувати звичайні гральні кістки, то треба скласти таблицю і вже використовувати її для генерації випадкових чисел, кидаючи кістку для кожного числа два рази, ігноруючи послідовності, що починаються з шістки:

11 = 0 21 = 6 31 = 2 41 = 8 51 = 4 12 = 1 22 = 7 32 = 3 42 = 9 52 = 5 +13 = 2 23 = 8 33 = 4 43 = 0 53 = 6 14 = 3 24 = 9 34 = 5 44 = 1 54 = 7 15 = 4 25 = 0 35 = 6 45 = 2 55 = 8 +16 = 5 26 = 1 36 = 7 46 = 3 56 = 9

Так само можна використовувати кулі лото, пронумеровані від 0 до 9. При цьому, діставши кулю і записавши його номер, його необхідно покласти назад і перемішати всю купу, інакше знову ж виникнуть проблеми з розподілом.

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

Але! Озброївшись всього лише олівцем, папером і гральною кісткою можна буде потім, після створення пари шифроблокнота і передачі одного з них по безпечному каналу, листуватися через всю галактику. При цьому ви будете впевнені, що ваше повідомлення ніхто не прочитає, крім власника другої копії шифроблокнота. Хіба що десь якийсь джедай використовує Силу, щоб прочитати минуле і побачити вас записуючим вийшла випадкову послідовність ...