Шифровка данных заменой. Борьба с избыточностью
Здравствуйте, читатели блога программистов, сегодня снова возвращаюсь к теме шифрования данных. В этой небольшой статье я расскажу, как можно избавиться от основного недостатка метода шифрования, о котором я рассказывал в этой статье про шифрование данных заменой. Описанный в той статье метод шифрования обладает очень большим недостатком – избыточностью, а именно, размер данных удваивается. Ниже я расскажу, как решить эту проблему.
Сам по себе алгоритм шифрования, поименованный мною как RDC, обладает почти непробиваемой стойкостью, возможно, это очень сильно сказано, но тем не менее это так. Во-первых, зашифрованный поток данных полностью случайный, и почти никак не зависит от оригинального потока, даже если, а оригинальном потоке одинаковые байты (в этом случае шифрование бессмысленно), тем не менее выходной поток всё равно будет случайным. Во-вторых, для этой шифровки тупой перебор просто-напросто неприменим. Это факты и с этим невозможно спорить. Поэтому если забыть о том, что размер выходных данных в два раза больше, то этот алгоритм идеален для организации защищённых каналов связи. Также этот алгоритм шифрования удобно было бы применять при передаче важных файлов. Тем не менее, алгоритм легко взламывается, если известны исходные данные, тогда легко сопоставить исходные и зашифрованные данные и восстановить книгу кодов.
Итак, основная проблема это избыточность. Как с ней бороться? У нас имеется 256 кодовых страниц, в каждой их которых по 256 байт. Каждый байт исходных данных мы заменяем на номер кодовой страницы и байт замену согласно этой кодовой страницы. Т.е. один байт заменяется двумя. Требование №1: надо заменять один байт одним. Требование №2: кодовые таблицы всегда должны быть разными и должны постоянно меняться. Моё решение заключается в создании дополнительного массива, в котором будет указана последовательность использования кодовых страниц из книги кодов. Размер этого массива произвольный. Этот массив назовем, как CPSeq (Code Page Sequence), а его размер будет равен CPSS. Массив будет содержать однобайтовые элементы диапазон каждого из которых 0-255.
Как всё будет работать? При шифровке очередного байта сначала будет вычисляться номер используемой кодовой страницы. Номер кодовой страницы будет равен следующему значению:
cpi = CPSeq [ i ]
где cpi – номер используемой кодовой страницы, а i – это остаток от деления адреса байта в исходном файле (потоке) на CPSS.
После чего исходный байт будет заменяться на байт-замену полученного из выбранной кодовой страницы. Таким образом, один байт будет заменяться одним. Избыточность будет фиксированной, с исходным данным будет прибавляться размер массива содержащего последовательность номеров кодовых страниц, чтобы расшифровщик знал в каком порядке использовать кодовые страницы из книги кодов.
К преимуществам можно отнести то что этот ключ может быть какой угодно длины и чем больше длина тем больше защищённость. Если длина массива CPSeq будет равна длине файла защищённость будет точно такая же как и у первоначальной версии этого алгоритма.
Массив CPSeq можно использовать как дополнительный ключ, т.е. не генерировать его каждый раз при шифровке, а заранее договориться об используемой последовательности. Но при этом конечно пострадает защищённость, но зависит от области применения и конкретной ситуации. Всевозможных вариаций масса! Но в любом случае возникает возможность использовать дополнительный уровень защиты в виде ещё одного ключа без которого данные не расшифровать.
Также описанный мною алгоритм (первоначальная и новая версия) имеет ещё одно преимущество, заключающееся в том, что алгоритм имеет очень высокую скорость расшифровки данных. Но в первоначальной версии алгоритма из-за его избыточности шифрование больших порций данных становиться неприемлемым, так как размер данных удваивается (например, нельзя будет зашифровать целый жёсткий диск или раздел диска, также например, при передаче данных по медленному каналу скорость передачи удвоится). В новой версии алгоритма становится возможным шифрование любых блоков и потоков данных.
Вот собственно и всё что я хотел сказать.
Реализация алгоритма в виде библиотеки rclib.dll и программа-пример (Delphi) использующая эту библиотеку. Обсуждение на форуме
ну в общем-то зная характер данных, можно применить частотный анализ и практически налету декриптовать подобные методы.. кстати можно генерировать один ключ для всего шифруемого массива, единственная проблема в скрытной передаче негативного ключа (шифрование заменой несиметричное поэтому дешифрование происходит с применением негативного ключа) пару лет назад я использовал подобный метод в крипторе.. и не какой избыточности нет..
вот соорудил «наколенный» пример подобного шифрования.. Коряво конечно, но что поделать, не хочу сильно отвлекаться от основной программы.
Принцип такой:
1)Создаем ключ шифрования и дешифрования
2)Читаем себя в буфер
3)Шифруем первым ключем считанный буфер (позитивным)
4)Записываем зашифрованный буфер в первый файл
5)Читаем содержимое первого файла в буфер
6)Расшифровываем буфер вторым ключем (негативным)
7)Пишем буфер во второй файл
После отработки кода в каталоге с программой программой появляется 2 файла:
1)crypt256.exe.tmp1 — зашифрованный crypt256.exe
2)crypt256.exe.tmp2 — зашифрованный crypt256.exe.tmp1
Убедиться в том что все пашет можно сравнив файлы)))
[code]program crypt256;
type
TKey = array [0..$FF] of byte;
var
KeyPositiv : TKey;//Позитивный ключ (для шифровки)
KeyNegativ : TKey;//Негативный ключ (для дешифровки)
procedure Gen_Rand_256byte_Keys;
label Promah;
var
i : integer;
k : integer;
r : integer;
begin
randomize;
//Очистка буферов
FillChar(KeyPositiv,$100,#0);
FillChar(KeyNegativ,$100,#0);
//Создание случайного 256 байтного ключа
for i:=0 to $FF do
begin
Promah:
r:=random($FF);
if KeyPositiv[r]=0
then KeyPositiv[r]:=i
else goto Promah;
//Да знаю, метки - не хорошо, не красиво
//но сделайте скидку на то что пишу почти на коленках))
end;
//Создание негативного ключа
k:=0;
for i:=0 to $FF do
begin
while true do
begin
if KeyPositiv[k]=i then break;
inc(k);
end;
KeyNegativ[i]:=k;
k:=0;
end;
end;
var
f : file;
i : integer;
FM : byte;
fs : integer;
Buf : array [1..$FFFF] of byte;
begin
FM:=FileMode;
Gen_Rand_256byte_Keys;//Генерация ключей
//Читаем себя в буфер
//Почему себя? Да по привычке)))
FileMode:=0;
AssignFile(f,ParamStr(0));
Reset(f,1);
fs:=FileSize(f);
BlockRead(f,Buf,fs);
CloseFile(f);
//Шифруем данные считаеные из себя позитивным ключем
for i:=1 to fs do Buf[i]:=KeyPositiv[Buf[i]];
//Пишем зашифрованную копию себя в первый файл
FileMode:=2;
AssignFile(f,ParamStr(0)+'.tmp1');
ReWrite(f,1);
BlockWrite(f,Buf,fs);
CloseFile(f);
//Читаем данные из первого файла
FileMode:=0;
AssignFile(f,ParamStr(0)+'.tmp1');
Reset(f,1);
BlockRead(f,Buf,fs);
CloseFile(f);
//Дешифруем данные считаеные из первого файла негативным ключем
for i:=1 to fs do Buf[i]:=KeyNegativ[Buf[i]];
//Пишем расшифрованную копию себя во второй файл
FileMode:=2;
AssignFile(f,ParamStr(0)+'.tmp2');
ReWrite(f,1);
BlockWrite(f,Buf,fs);
CloseFile(f);
FileMode:=FM;
end.[/code]
то что описано выше, является всего лишь упрощённой версией моего алгоритма. ты используешь два ключа, у меня вместо твоих двух ключей один ключ (одна кодовая страница), просто при использовании одного ключа скорость шифрования увеличивается, скорость расшифровки не меняется. Разумеется шифрование с использование одной кодовой страницы очень удобно, так как энтропия не меняется.
в моём алгоритме 256 кодовых страниц (которые объединяются в книгу кодов), и эти кодовые страницы постоянно меняются в случайном порядке. таким образом, данные на выходе у меня получаются ПОЛНОСТЬЮ СЛУЧАЙНЫЕ, т.е. энтропия максимальная (стремится к 8). Поэтому никакой частотный анализ не подходит.
ну вообще генерация если использовать мой метод генерации 256 случайного массива:
//Создание случайного 256 байтного ключа
for i:=0 to $FF do
begin
Promah:
r:=random($FF);
if KeyPositiv[r]=0
then KeyPositiv[r]:=i
else goto Promah;
//Да знаю, метки — не хорошо, не красиво
//но сделайте скидку на то что пишу почти на коленках))
end;
то на генерацию каждого байта цикл выполняется примерно 6,09 раз (проверено на 10 милионах циклах) соответственно для генерации одной книги 256*256 уйдет примерно 400000 циклов.. даже при реализации на ассемблере меньше 15 тактов на цикл трудно реализовать, т.о. выходит 6 миллионов тактов, а с поправкой на то что больше 50% процессорного времени система не даст, выходит достаточно ресурсоёмкая операция.. Если применять одну и туже книгу постоянно, то передавать её совсем необязательно, просто хранить как константу, если же будет происходить смена книг, то придется постоянно отправлять новую книгу (256*256 = 65536 байт), что может значительно повысить избыточность.. Можно конечно отключить randomize и тогда и генерировать на приёмной и передающей стороне ключи одновременно, но оба метода не дают стопроцентной защиты, т.к. имея алгоритм а скрыть его не получится если применять метод не в штучной системе, а сделать публичным.. В общем-то замена есть замена и с md5, RSA и тому подобными методами ей некогда не тягаться..акфеша
execom, а зачем это вообще? 😯
>>для генерации одной книги 256*256 уйдет примерно 400000 циклов.. даже при реализации на ассемблере меньше 15 тактов на цикл трудно реализовать, т.о. выходит 6 миллионов тактов
да пусть хоть миллиард тактов, какое это имеет значение? пусть она генерируется хоть полчаса, какая разница? книгу кодов «один раз сгенерировал и забыл». В реальности же, это происходит менее чем за секунду
>>а с поправкой на то что больше 50% процессорного времени система не даст
без обид, ерунда какая-то. если нет другой задачи с более высоким приоритетом, что программа будет расходовать все 100% процессорного времени. вопрос только в том сколько процессоров? если процессоров два, то конечно в совокупности задача будет расходовать только 50% системного времени (именно системного, а не процессорного)
>>то придется постоянно отправлять новую книгу (256*256 = 65536 байт), что может значительно повысить избыточность
сейчас сетевой траффик конкретно взятого пользователя измеряется гигабайтами, жёсткие диски уже измеряются терабайтами, а ты говоришь о каких-то 64КБ. да и при нынешних скоростях передачи информации по сети, передача 64 КБ не прочувствует это даже USB-модем находящийся в зоне неуверенного приёма сигнала
как я уже говорил перестановка в любом случае не дает 100% результат, если просто знать алгоритм, в таком случае к чему все танцы с бубном и борьба с избыточностью?? проще применять хорошие качества этого метода — быстрота и простота, чем делать на основе этого что-то сложное тупящее и в любом случае менее надежное чем стандартное md5)) Хотя я тебя понимаю.. очень хочется что бы именно из под твоего пера вышло что-то новое, но поверь Руслан, в этом огороде я уже все сучки, да задоринки изучил.. Но все-таки я буду ждать твою работу и обязательно постестю, надеюсь сорци будут открытыми??
>>проще применять хорошие качества этого метода – быстрота и простота, чем делать на основе этого что-то сложное тупящее
а где именно я усложнил алгоритм? первоначальная версия моего алгоритма не намного сложнее
>>в любом случае менее надежное чем стандартное md5
md5 это не шифрование, это хеширование или ты что-то другое имел ввиду?
>>Но все-таки я буду ждать твою работу и обязательно постестю, надеюсь сорци будут открытыми??
непременно напишу и выложу через пару дней
>>а где именно я усложнил алгоритм? первоначальная версия моего алгоритма не намного сложнее
ну в общем-то шифрование заменой это как бы один из старейших методом шифрования.. еще старина Шеркол Холмс юзал))
>>md5 это не шифрование, это хеширование или ты что-то другое имел ввиду?
сори имел ввиду RSA
Программа-пример на Delphi и библиотека rclib.dll
http://programmersforum.ru/showthread.php?p=853596
Главная радиостанция страны ищет программиста, либо компанию для создания сайта для радиопередачи.
Мы готовы заплатить Вам 30 000 руб.
Наше предложение это – отличный проект для портфолео фрилансера, возможность заработать бабла;), а для компаний — еще и информационная и рекламная поддержка на ГЛАВНОЙ РАДИОСТАНЦИИ РОССИИ!!!
Пишите на ящик: pravdoha@mail.ru