Невзламываемый шифр Вернама

Про­дол­жа­ет­ся цикл ста­тей о шиф­ро­ва­нии и крип­то­гра­фии. В преды­ду­щих сери­ях:

Сего­дня раз­бе­рём невзла­мы­ва­е­мый сим­мет­рич­ный шифр. 

Вся крип­то­гра­фия осно­ва­на на том, что для взло­ма шиф­ра зло­умыш­лен­ни­ку потре­бу­ют­ся десят­ки или сот­ни лет даже при досту­пе к боль­шим вычис­ли­тель­ным ресур­сам. Но в сим­мет­рич­ном шиф­ро­ва­нии есть алго­рит­мы, кото­рые при пра­виль­ном исполь­зо­ва­нии вооб­ще невоз­мож­но взло­мать. Один из таких алго­рит­мов — шифр Вер­на­ма.

Как работают такие алгоритмы

Общие пра­ви­ла для абсо­лют­но стой­ких шиф­ров в сим­мет­рич­ном шиф­ро­ва­нии такие:

  1. Одно шиф­ро­ва­ние — один уни­каль­ный ключ. Вто­рое сооб­ще­ние шиф­ро­вать этим же клю­чом уже нель­зя.
  2. Ключ состо­ит из слу­чай­ных битов, и каж­дый бит не зави­сит от дру­го­го. Это зна­чит, что нель­зя исполь­зо­вать в каче­стве клю­ча, напри­мер, отры­вок из кни­ги, пото­му что это рез­ко сни­жа­ет устой­чи­вость шиф­ра ко взло­му.
  3. Дли­на клю­ча долж­на быть рав­на длине сооб­ще­ния или ключ дол­жен быть чуть длин­нее. Если ключ коро­че сооб­ще­ния, кото­рое нуж­но зашиф­ро­вать, то абсо­лют­ной стой­ко­сти не полу­чит­ся.

Если в алго­рит­ме соблю­да­ют­ся все три пра­ви­ла, то такой шифр взло­мать нель­зя даже тео­ре­ти­че­ски.

Шифр Вернама — это просто

В 1917 году теле­гра­фист Гиль­берт Вер­нам изоб­рёл шифр, кото­рый осно­ван на поби­то­вом исклю­ча­ю­щем ИЛИ. Если корот­ко и про­сто, то на каж­дую бук­ву ваше­го сооб­ще­ния накла­ды­ва­ет­ся дру­гая мас­ки­ру­ю­щая бук­ва, кото­рая дела­ет исход­ную бук­ву нечи­та­е­мой.

Шифр Вернама — это сложно

Теперь попро­бу­ем объ­яс­нить подроб­нее. 

1. Сооб­ще­ние хра­нит­ся в виде битов дан­ных. Допу­стим, мы шиф­ру­ем текст. Ком­пью­тер не уме­ет рабо­тать с тек­стом как тако­вым, он этот текст хра­нит как набор чис­ло­вых кодов (про­ще гово­ря, у ком­пью­те­ра все бук­вы про­ну­ме­ро­ва­ны и он пом­нит толь­ко эти номе­ра).

Чис­ла, в свою оче­редь, ком­пью­тер хра­нит в виде дво­ич­но­го кода, то есть битов дан­ных. Это пока что не отно­сит­ся к шиф­ро­ва­нию, это про­сто то, как хра­нит­ся любая тек­сто­вая инфор­ма­ция в ком­пью­те­ре.

Бук­ваКод в ASCIIБиты дан­ных
K7501001011
O7901001111
D6801000100

Если мы напи­шем KOD в коди­ров­ке ASCII, то для ком­пью­те­ра это будет после­до­ва­тель­ность из трёх чисел, а каж­дое чис­ло — это набор битов: 

01001011 01001111 01000100

2. Берём слу­чай­ные биты в каче­стве клю­ча шиф­ро­ва­ния. На вхо­де у нас три чис­ла по 8 бит. Что­бы их зашиф­ро­вать, нам нуж­ны 24 слу­чай­ных бита. Возь­мём их с потол­ка, они ниче­го не зна­чат: 

10101101 01111010 10101011

3. Накла­ды­ва­ем коды друг на дру­га и при­ме­ня­ем алго­ритм шиф­ро­ва­ния. Шифр Вер­на­ма постро­ен на прин­ци­пе «исклю­ча­ю­ще­го ИЛИ», он же XOR. Он смот­рит на каж­дую пару битов и пыта­ет­ся понять, они оди­на­ко­вые или раз­ные. Если биты оди­на­ко­вые, резуль­тат про­вер­ки будет 0, если раз­ные — 1.

Мож­но про­ве­рить себя так: XOR зада­ёт вопрос «Эти биты раз­ные»? Если да — то 1, если нет — то 0.

Бук­ва K01001011
Ключ10101101
XOR (Они раз­ные?)11100110

Если мы таким обра­зом зако­ди­ру­ем три бук­вы, мы полу­чим три новых набо­ра битов: 

KOD (сооб­ще­ние)010010110100111101000100
Ключ101011010111101010101011
Резуль­тат шиф­ро­ва­ния с помо­щью XOR111001100011010111101111

Полу­ча­ет­ся, что на вхо­де у нас было 24 бита дан­ных и на выхо­де 24 бита дан­ных. Но эти дан­ные теперь совсем дру­гие. Если пере­ве­сти эти чис­ла обрат­но в текст, мы полу­чим: 

KOD → æ5ï

Расшифровка шифра Вернама

Если у нас есть зако­ди­ро­ван­ное сооб­ще­ние и ключ от него, то рас­ко­ди­ро­вать его не соста­вит тру­да. Мы про­сто пишем алго­ритм, кото­рый при­ме­ня­ет опе­ра­цию XOR как бы в обрат­ном поряд­ке к каж­до­му биту сооб­ще­ния. Напри­мер: 

  1. Если в клю­че шиф­ро­ва­ния в каком-то бите сто­ит 1, то мы берём этот же бит в зашиф­ро­ван­ном сооб­ще­нии и меня­ем его. Если был 1, то меня­ем на 0. Если был 0, то меня­ем на 1. 
  2. Если в клю­че шиф­ро­ва­ния в каком-то бите сто­ит 0, то этот же бит в зашиф­ро­ван­ном сооб­ще­нии мы не меня­ем.
  3. Про­хо­дим так по каж­до­му биту сооб­ще­ния и полу­ча­ем исход­ный текст.

Ком­пью­тер может совер­шать мил­ли­ар­ды таких опе­ра­ций в секун­ду. Глав­ное — иметь на руках ключ для рас­шиф­ров­ки. 

Почему этот шифр невзламываемый

Для нача­ла дого­во­рим­ся, что под взло­мом мы пони­ма­ем про­чте­ние это­го сооб­ще­ния без клю­ча. Если бы у нас был ключ, мы бы про­чи­та­ли это сооб­ще­ние почти сра­зу, и это уже не взлом. 

Теперь посмот­рим, поче­му без клю­ча этот шифр невоз­мож­но взло­мать. 

  • Каж­дый бит наше­го исход­но­го сооб­ще­ния шиф­ру­ет­ся соот­вет­ству­ю­щим битом, кото­рый берёт­ся из клю­ча шиф­ро­ва­ния.
  • Ключ шиф­ро­ва­ния — это слу­чай­ные биты, такой «циф­ро­вой шум». Он не име­ет смыс­ла и в нём нет ника­кой логи­ки. Каж­дый сле­ду­ю­щий бит может быть каким угод­но. 
  • Шиф­ро­ва­ние про­ис­хо­дит на самом низ­ком уровне — на уровне битов. Мы даже не зна­ем, что перед нами: бук­вы, циф­ры, чис­ла, кар­тин­ки или аудио. Про­сто какой-то набор битов, кото­рые выгля­дят как циф­ро­вой шум. 

Един­ствен­ный спо­соб рас­шиф­ро­вать целое сооб­ще­ние — это полу­чить целый ключ. Если мы полу­чим лишь часть клю­ча, мы не смо­жем уга­дать или вос­ста­но­вить недо­ста­ю­щую часть. Сколь­ко клю­ча у нас есть — столь­ко битов сооб­ще­ния мы и рас­шиф­ру­ем. Нет клю­ча — нет рас­шиф­ров­ки. 

Пример работы

Если мы зашиф­ру­ем так фра­зу «При­вет, это жур­нал Код!», то можем полу­чить что-то такое:

hi857ов9njg5jоlр6;p0ора

Шту­ка в том, что одна и та же бук­ва в шиф­ров­ке не озна­ча­ет оди­на­ко­вые бук­вы в исход­ном сооб­ще­нии, пото­му что биты шиф­ро­ва­ния выбра­ны слу­чай­ным обра­зом. Поэто­му при попыт­ке рас­шиф­ров­ки зло­умыш­лен­ник полу­чит такие вари­ан­ты:

Сроч­но под­пи­шись на код

Вер­ни день­ги, а то вилы

мама, я сдал зачёт, ура

Ваш зам пре­да­тель и вор

Ваш зам ни при чём, вот

Так­же он может полу­чить любые дру­гие соче­та­ния букв, цифр и про­бе­лов в рам­ках тех 23 сим­во­лов, кото­рые у нас были в исход­ном сооб­ще­нии. Может быть, это не текст вовсе, а набор цифр. Может быть, это текст на каком-то дру­гом язы­ке. Может быть, это не текст вовсе, а очень малень­кая кар­тин­ка. Все эти вари­ан­ты мож­но полу­чить из нашей зашиф­ро­ван­ной стро­ки, пото­му что зло­умыш­лен­ник не зна­ет ключ. 

Минусы шифра Вернама

Если бы у это­го шиф­ра не было мину­сов, все бы поль­зо­ва­лись толь­ко им, но сей­час этот шифр исполь­зу­ет­ся ред­ко. Всё дело в том, что им очень неудоб­но поль­зо­вать­ся, что­бы выпол­нить все усло­вия.

Что­бы этот шифр нель­зя было взло­мать, нуж­но, что­бы сек­рет­ный ключ был у обе­их сто­рон и при этом его нель­зя было пере­хва­тить. Но если так мож­но пере­дать сек­рет­ный ключ, то вме­сто него мож­но пере­дать и само сооб­ще­ние.

Даже если удаст­ся зара­нее пере­дать набор клю­чей каж­дой сто­роне для буду­щих шиф­ро­вок, их нуж­но дер­жать в пол­ной физи­че­ской без­опас­но­сти, что­бы нель­зя было их украсть, под­смот­реть, поте­рять или пере­пу­тать.

Имен­но из-за таких тре­бо­ва­ний к без­опас­но­сти клю­ча этот шифр сей­час исполь­зу­ет­ся очень ред­ко. 

Что дальше

Поиг­ра­ем в шпи­о­нов и напи­шем свой алго­ритм шиф­ра Вер­на­ма на JavaScript. Заод­но и посмот­рим, как рабо­та­ет XOR.

Текст:
Миша Поля­нин

Редак­тор:
Мак­сим Илья­хов

Кор­рек­тор:
Ира Михе­е­ва

Иллю­стра­тор:
Даня Бер­ков­ский

Вёрст­ка:
Маша Дро­но­ва

Достав­ка:
Олег Веш­кур­цев