Криптография: Шифр Вернама и его программная реализация.
В криптографии шифр Вернама известен также как «схема одноразовых блокнотов». Решение является системой симметричного шифрования, которая была изобретена в 1917 году сотрудниками AT&T Мейджором Джозефом Моборном и Гильбертом Вернамом.
В 1949 годах была опубликована работа Клода Шеннона, где Шеннон доказал абсолютную стойкость шифра Вернама. В этой работе Шеннон показал, что не существует других шифров с подобными свойствами и его выводом стало следующее утверждение: шифр Вернама – самая безопасная криптосистема из всех имеющихся.
Однако, следует заметить, что для того, чтобы шифр действительно был стойким, необходимо выполнение следующих трех правил:
- Ключ для шифрования выбирается случайным образом.
- Длина ключа должна быть равна длине открытого текста.
- Ключ должен использоваться ТОЛЬКО один раз.
А теперь поподробней о самом шифре и процессе шифрования. Так как этот шифр был придуман для компьютерных систем, то следует заметить, что базируется он на двоичной арифметике. Надеюсь что вы знакомы с ней ;). Основным объектом рассмотрения в данном методе шифрования является логическая операция XOR (взаимоисключающее ИЛИ). Таким образом, так как у нас двоичная арифметика, то все операции будут осуществляется над нулем (0) и единицей (1). Логическая операция XOR, в отличие от операции OR, при логическом сравнении 0 и 1 дает 1, при сравнении 1 с 1 дает 0, а при 0 с 0 дает 0. Следовательно, если мы выполним операцию XOR над числами 10110 и 11010, то получим: 10110 xor 11010 = 01100. Надеюсь что принцип работы операции XOR понятен.
Далее, так как шифр работает с двоичной системой исчисления, необходимо понимать, что буквы — это всего лишь некоторая интерпретация числа, то есть число является кодом символа некоторой таблицы кодировок. К примеру, наиболее популярные таблицы кодировок это: ANSI, ASCII и UTF(unicode). Естественно, что в каждой таблице один и тот же символ может иметь разный код, поэтому, во избежании путаницы, имейте это ввиду и используйте одну и ту же кодировку при шифровании и дешифровании. Замечу, что использовать можно и свою (придуманную) кодировку. Кроме того, данный шифр может использоваться не только на компьютерах. Его можно применить и к тексту написанному на бумаге. Только перед применением надо сделать некие преобразования.
Таким образом, перед тем, как осуществить шифрование, необходимо перевести все символы в их однозначную числовую интерпретацию. Если Вы решили применить шифр в компьютерных системах, то для вас уже существуют соответствующие кодировки и язык программирования, выбранный Вами, скорее всего поддерживает явное или неявное преобразование. И вам остается только произвести над каждой парой операцию XOR. В различных языках это операция определяется по разному, приведу пример: для pasсal/Delphi/Assembler — xor, C/C++ — ^. Однако, если же Вы решили применить шифр Вернама к письменному тексту, то, к примеру, дайте каждой букве используемого вами алфавита, соответствующий ей порядковый номер в двоичной системе исчисления. Например, если вы используете русский алфавит (без учета буквы Ё) то это будет выглядеть так: а -> 00000, б -> 00001, в -> 00010, г -> 00011, … я -> 111111. Тем самым мы определили свою таблицу кодировки. После этого, написав сообщение и придумав ключ, преобразуйте каждый символ в их числовое значение, соответствующее вашей таблице кодировки, и после этого осуществляйте операцию XOR над каждой соответствующей парой. Так как данный метод шифрования является симметричным, следовательно, применив операцию XOR к каждой паре символов шифр-текста (шифрограммы) и ключа, мы получим открытый текст.
Программная реализация шифра Вернама.
На основе изученного материала я покажу как реализовать шифр Вернам на С/С++ и pascal/Delphi. Программу целиком писать нет надобности, поэтому будем рассматривать блочную структуру, для того, чтобы каждый мог без особого труда заточить ее под свои надобности. А теперь от слов к делу ;).
Допустим, что у нас есть строка или массив символов — oStr. Это будет открытый текст, который надо зашифровать. Теперь нам надо определить случайный ключ длиной равной длине открытого текста. Для простоты понимания, мы воспользуемся стандартной функцией генерации случайных чисел: random для pascal/Delphi и rand для C/C++. Но замечу сразу что это не лучший вариант в случае, если вы хотите реализовать действительно стойкий шифр. Данный пример выбран из соображения простоты. Теперь покажем как это будет выглядеть в исходном коде:
pascal/DelphiC/C++var oStr, key:string; i:integer; begin oStr:='Holo word!'; //определяем открытый текст randomize; //Необходимая функция для функции random, чтобы последняя каждый раз выдавала случайные значения //генерируем случайный ключ длиной равной длине открытого текста for i:=1 to length(oStr) do key[i]:=Chr(random(255)); //генерируем случайное число из диапозона от 0 до 255 и полученое число переводим в символ; end;int i,len; //Определяем необходимые переменные len = strlen("Holo word!");// определяем длину строки открытого текста char *oStr = new char[len]; //объявляем динамический массив указанной длины для открытого текста char *key = new char[len]; //точно такой же массив объявляем для ключа oStr="Holo word!"; //помещаем в массив открытый текст // определяем ключ случайным образом for(i = 0; i < len; i++) key[i]=(char)rand()%255;
Так, самое основное мы сделали. Теперь нам осталось лишь реализовать шифрование, для этого мы опишем цикл, в котором мы будем посимвольно осуществлять операцию XOR. Но для этого нам понадобится еще объявить массив приемник, в который мы поместим зашифрованный текст. Смотрим:
pascal/DelphiC/C++procedure shifr_Vernam; var oStr, key, shStr :string; i:integer; begin oStr:='Holo word!'; //определяем открытый текст randomize; //Необходимая функция для функции random, чтобы последняя каждый раз выдавала случайные значения //генерируем случайный ключ длиной равной длине открытого текста for i:=1 to length(oStr) do key[i]:=Chr(random(255)); //генерируем случайное число из диапозона от 0 до 255 и полученное число переводим в символ; //собственно само шифрование for i:=1 to length(oStr) do shStr[i]:=oStr[i] xor key[i]; //для наглядности выведем на экран результат работы writeLn('Otkrytyi text: ',oStr); writeLn('Zashifrovanyi text: ',shStr); end;void shifr_Vernam { int i,len; //Определяем необходимые переменные len = strlen("Holo word!");// определяем длину строки открытого текста char *oStr = new char[len]; //объявляем динамический массив указанной длины для открытого текста char *key = new char[len]; //точно такой же массив объявляем для ключа char *shStr = new char[len]; //массив-приемник для зашифрованного текста oStr="Holo word!"; //помещаем в массив открытый текст // определяем ключ случайным образом for(i = 0; i < len; i++) key[i]=(char)rand()%255; //собственно само шифрование for(i = 0; i < len; i++) shStr[i]=oStr[i]^key[i]; //для наглядности выведем на экран результат работы printf("\nOtkrytyi text: %s", oStr); printf("\nZashifrovanyi text: %s", shStr); }
На этом все, реализация шифрования закончена. Надеюсь, что вы догадаетесь как реализовать дешифровку(Подсказка: те же действия нужно провести для шифрованного текста ;) ). Спасибо за внимание.
(20 голосов, средний: 4,50 из 5)
Loading ...
Считаю что стоит больше уделить внимание криптографии
На Delphi само шифрование выглядит так:
shStr[i]:=chr(ord(oStr[i]) xor ord(key[i]));
Иначе не работает! Это во первых.
Во вторых, если oStr[i]=key[i], то будет «0″ и шифровка будет неточной!
Необходимо защитить программу от таких случаев!
метод Вернама принадлежит типу зеркального шифрования ;)
Вы имеете ввиду ситуацию, когда открытый текст совпадает с ключом? Естественно, в таком случае мы получим «нули», это не неточность, а такой шифр (1 xor 1 == 0).
Афтар, кончай разводить дилетантство! Баламутит тут народ… Если бы шифр Вернама так легко реализовывался, его бы использовали везде, и не придумывали другие шифры. Вы правильно сказали «ключ должен быть абсолютно случайным», вот только автомату ПСЕВДОслучайных чисел, который вы использовали до такой характеристики как до Луны пешком! Функция random() (в разных языках она может называться по-разному) генерирует линейную рекуррентную последовательность от исходных 32 бит, в которые функция randomize() кидает 32 посдених бита времени аптайма в наносекундах. Ключ у вас получился 32-битный. Шифр вместо абсолютно стойкого получился «учебным».
К тому же, ваша реализация еще и нерабочая: где вы ключ сохраняете? Или расшифровывать вы хотите на другом ключе? Удачи!
Что касается нулевой последовательности на выходе — то чем она вас не устраивает? 000000000000000000000000 — попробуй взломай! Да и вероятность такого события — 1/2^n, где n — длина сообщения (и ключа) в битах. Куда более вероятны и опасны длинные однородно нулевые или единичные последовательности в ключе, которые появятся с куда большей вероятностью. Но только в настоящем шифре Вернама, в выше приведенном коде их точно не будет xD
@Crypton
Позволю не согласится, шифр Вернама — один из простейших в реализации, проблема генерации и передачи ключа уже к этому не относится.
> Вы правильно сказали «ключ должен быть абсолютно случайным»,
> вот только автомату ПСЕВДОслучайных чисел, который вы использовали
> до такой характеристики как до Луны пешком!
Для оценки алгоритмов генерации псевдослучайных чисел тоже существуют свои алгоритмы. И вообще, что Вы подразумеваете под абсолютной случайностью, может её и нет вовсе? ;) Сидите и бросайте монетку, будете побитово генерировать свой ключ, абсолютно случайно (или нет?).
> Что касается нулевой последовательности на выходе – то чем она вас не
> устраивает?
Кто сказал что она кого-то не устраивает?
> Куда более вероятны и опасны длинные однородно нулевые или единичные
> последовательности в ключе
С чего это они более вероятны и уж тем более более опасны (если положить «длинные» == длина ключа)?
> Но только в настоящем шифре Вернама, в выше приведенном коде их точно
> не будет
Т.е. взяв во внимание термин *абсолютно случайной последовательность* Вы берётесь утверждать, что каких-то подпоследовательностей в ней нет с вероятностью равной 1? Объяснитесь, пожалуйста, или Вы решили просто потроллить?
P.S. Да, насчёт того, что ключ не выводится и не сохраняется — полностью согласен, недочёт, стоит поправить.
@lizz
1) С каких это пор ключевое расписание не является частью реализации?! Это одна из самых важных ее частей.
2) Под абсолютно слуцайной последовательностью бит я имел в виду последовательность независимых случайных величин, имеющих распределение Бернулли с параметром 1/2. Подкидывание монетки — это как раз пример такового. Но есть и другие источники. Я как раз занимаюсь сборкой аппаратного генератора на шумящих диодах. Это конечно не генераторы на ядерном распаде, но такие дома не поставишь…
3) Зачем анализировать качество линейной рекуррентной последовательности как случайной, если она порождается линейной функцией? О чем можно еще оворить?
4) Чем опасны длинные нулевые последовательности в гамме? А то, что в шифротексте будут очевыдны куски открытого текста — это по-вашему не уязвимость? То же самое и для единичных последовательностей. Что касается вероятности их появления, то для аппаратных генераторов она крайне высока. Поэтому внедряют системы контроля за такими последовательностями. Длинные — это не значит, что на весь ключ, это куски примерно по полкилобайта.
@lizz
Позвольте не согласится с высказыванием:
Т.е. взяв во внимание термин *абсолютно случайной последовательность* Вы берётесь утверждать, что каких-то подпоследовательностей в ней нет с вероятностью равной 1?
Это действительно так, ибо тот факт что событие произойдёт с вероятностью 0 не означает невозможность данного события.(Например вероятность попадания пылинки в точку с определёнными координатами равна 0 но это не означает что пылинка это квантовый обект)
Действительно в истинно случайной последовательности есть элементы даже линейных последовательностей но вся соль закльчается в их расстановке. Именно этот факт и делает последовательность абсолютно случайной
П.С. Админам: возможность писать html-теги — это грубая уязвимость.
@crypton
> 1) С каких это пор ключевое расписание не является частью реализации?!
> Это одна из самых важных ее частей.
Перечитайте пожалуйста абзац где сказано про генерацию ключа, надеюсь он прояснит ситуацию.
> Подкидывание монетки – это как раз пример такового.
Всё идеализировано. Ведь если на монетку действуют каждый раз одни и те же законы, постоянные силы, приложен один и тот же вектор силы в одну и ту же точку для броска, не должна ли она каждый раз падать на одну сторону? А если не всё так постоянно, то уже есть зависимость от чего-то, так что вся эта абсолютность так же условна. Впрочем, любая мат. модель — идеализация реальности, но это всё наверное ближе уже к метафизике.
> А то, что в шифротексте будут очевыдны куски открытого текста – это
> по-вашему не уязвимость?
Нет, т.к. сказать что это часть соответствует части открытого текста можно только зная ключ, ведь с таким же успехом можно встретить и похожую на открытый текст часть, в зависимости от ключа.
> П.С. Админам: возможность писать html-теги – это грубая уязвимость.
Спасибо, но не думаю что настолько грубая, от пары br’ов и параграфов не станет кому-то хуже. В обработке остальных тэгов я доверился целиком и полностью разработчикам wordpress, на это есть свои причины.
@lizz
> Перечитайте пожалуйста абзац где сказано про генерацию ключа,
> надеюсь он прояснит ситуацию.
Да, вы тут ушли от ответственности, вроде как не при делах. Тем не менее, вы приводите пример как раз того, как не надо делать. А ведь многое читатели просто возьмут да и передерут. А потом будут надеяться на «абсолютно стойкий шифр».
Во-вторых, вы решили не уделять должного внимания ключевому расписанию при том, что это практически основная задача реализации шифра Вернама. Сложить по модулю и обезъяна сможет.
Про подкидывание монетки — вы правы, не строит строить идеальных моделей. Например, одинаковые векторы силы и точки попадания. В реальной модели распределение орлов и решек близко к 1/2 на 1/2, и уж тем более независимо. Лучше б вы эту модель привели в пример для программной реализации.
Что каксается длинных нулевых кусков: представьте, что вы перехватчик. Вы видите в шифротексте большой кусок (порядка килобайта) осмысленного текста. Вы поверите, что это так просто совпало, или все-таки спишите это не дилетанство разработчика.
Кстати, тока щас заметил… вот 2 цитаты из статьи выше:
1) «В 1949 годах была опубликована работа Клода Шеннона, где Шеннон доказал абсолютную стойкость шифра Вернама.» (что, собственно, верно).
2) «так как этот шифр был придуман для компьютерных систем…»
Хотелось бы посмотреть на компьютерные системы 1949 года…
Изначально гамма накладывалась по модулю m, где m — размер алфавита. И никаких преобразований текст не требовал. В компьютере удобно использовать модуль 256 (байт) или 2 (побитовое сложение, XOR).
П.С. может, потенциально опасные html-теги здесь и блокируются, но грамотно это делается по принципу «белого списка».
@crypton
> Да, вы тут ушли от ответственности, вроде как не при делах. Тем не
> менее, вы приводите пример как раз того, как не надо делать. А ведь
> многое читатели просто возьмут да и передерут. А потом будут надеяться > на «абсолютно стойкий шифр».
Мне кажется Вы раздуваете из мухи слона. Для учебных целей данная реализация вполне годна, а профессионально изучать криптографию по блогам… хмм, имхо, это плохой вариант. Безусловно, в качестве дополнительного материала сгодится что угодно, но любой профессионал должен не бездумно читать и удивляться «до чего наука дошла», но так же и анализировать информацию.
> П.С. может, потенциально опасные html-теги здесь и блокируются, но
> грамотно это делается по принципу «белого списка».
Уверен, что настолько банальную уязвимость быстро прикрыли бы, wordpress не первый год существует, имеет открытый исходный текст и своё сообщество разработчиков. Думаю на этом можно прекратить оффтопик, смотреть исходники и выяснять действительно ли всё так сейчас времени нет :).
> Мне кажется Вы раздуваете из мухи слона. Для учебных целей
> данная реализация вполне годна,…
Чему же тогда учит данная статья? Как правильно складывать по модулю 2? Т.е. как использовать XOR? Тогда как-то много буков в связи с оффтопом в криптографическом направлении…
@crypton
Уверен, 99.9% студентам, которые ищут готовую реализацию шифра Вернама, предоставленных материалов вполне хватит. Про остальных, я уже писал. И да, умение складывать по модулю 2 так же не является врождённым.
Извините, если статья не оправдала Ваших ожиданий, если хотите более подробного раскрытия темы, то можете попросить автора об этом или, если Вам и так всё хорошо известно, то поделиться с читателями информацией, которую, как Вы считаете, знать необходимо.
У меня на потоке за такую реализацию поставили бы 2 без права пересдачи =) Все, что я хотел донести до читателя по данной теме, изложено в выше сказаных замечаниях. Да и студентов, ищущих реализацию шифра Вернама скорее будет интересовать реализация ключевого расписания, нежели сложения по модулю 2.
@crypton
> У меня на потоке за такую реализацию поставили бы 2
Это у Вас, а у нас — нет ;).
> Да и студентов, ищущих реализацию шифра Вернама скорее будет интересовать
> реализация ключевого расписания
За 1,5 года, судя по комментам, заинтересовало пока только Вас, следовательно большинству всё же нужно сложение по модулю 2. Переоцениваете нашу систему образования ;).
эээ…
товарищ, а где сами страницы случайных чисел??
они дорлжны быть и у получателя и у отправителя
база данных на худой конец, заполненная аппаратным гсч…
да и самое главное:
страницы должны быть _одноразовыми_!