1cloud
» Шифровка данных заменой с++ и с #. . . Блог программистов


Блог программистов




201017 Apr

Шифровка данных заменой

Здравствуйте, читатели блога программистов, сегодня я расскажу вам о недавно придуманном мною алгоритме шифрования данных при использовании, которого зашифрованные данные каждый раз получаются разными, при этом они никак не зависят от текущей даты, времени и других факторов. Изложенный в данной статье алгоритм идеально подходит для создания конфиденциальных каналов связи, при использовании которых критически важно, чтобы передаваемую информацию не мог узнать злоумышленник. Предупреждаю сразу: изложенный в данной статье алгоритм не претендует на звание самого лучшего, это всего лишь очередная вариация на тему шифрования данных, не исключено что он уже был придуман кем-то раньше.

  Итак, приступим! Первое что приходит в голову при шифровании данных это простая замена символов согласно некоторой таблице соответствия, а саму таблицу соответствия можно генерировать случайным образом. Недостаток этого метода очевиден: при относительно длинном размере зашифрованных данных, можно найти соответствие между исходными символами и замененными.
  Итак, простая замена символов не подходит. Вспоминается старый метод шифрования данных, которым наверно пользовались наши прадедушки. Например, есть два человека, которые хотят вести конфиденциальную переписку. У них есть две одинаковые книги. Каждый символ в передаваемом сообщении кодируется следующим образом: номер страницы, номер строки и номер символа в строке.
Таким образом, одна и та же буква может быть заменена несколькими разными цифровыми последовательностями. При правильном использовании такого метода шифрования возможность расшифровки передаваемых данных без искомой книги почти невозможна.
  А теперь вспомним первый алгоритм и сделаем выводы: таблиц соответствия должно быть несколько (не несколько, а много!). А заменять один символ мы будем не одним символом, а двумя: номером таблицы соответствия и номером заменяемого символа в таблице соответствия.
  Теперь перенесём алгоритм в проблематику информатики. Символом сообщения у нас будет байт. Байт может принимать значение 0-255, и заменён он может быть любым значением от нуля до 255. Таблицу соответствия будем называть кодовой страницей. Кодовых страниц у нас будет 256. Набор из 256 кодовых страниц будем называть книгой кодов. В результате при шифровке данных один байт исходных данных будет заменяться двумя: номером кодовой страницы и байтом соответствия на этой кодовой странице. При шифровке кодовая страница будет выбираться случайным образом, таким образом, каждый раз при шифровке один и тех же данных мы будем получать разные данные.
  Кодовая страница будет представлять собой массив из 256 байт. Чтобы получить байт-замену необходимо найти заменяемый байт в этом массиве. Индекс заменяемого байта и будет байтом-заменой. Например, у нас есть байт со значением 125, в кодовой странице он находится на 239 месте, следовательно, байт со значением 125 будет заменён байтом со значением 239. Поиск символа в 256 байтовом массиве это не очень быстрая операция, но зато операция расшифровки будет иметь довольно-таки высокую скорость.
  Как видно при использовании данного алгоритма размер данных увеличивается в два раза. При обеспечении конфиденциальности данных этот фактор не является решающим.
  Теория изложена, осталось написать программу, которая производит шифровку данных согласно вышеизложенному алгоритму.
  Для начала напишем функции, которые случайным образом будут генерировать кодовые страницы и книгу кодов.
  Функция CreateCodePage генерирует случайным образом кодовую страницу. Функция принимает один параметр – указатель на буфер.


void CreateCodePage(BYTE *Page)
{
    for (int i=1;i<256;i++)
    {
        int pos = rand()%256;
        if (Page[pos])
        {
            while ((Page[pos]) and (pos<255)) pos++;
            if (Page[pos])
            {
                pos=0;
                while ((Page[pos]) and (pos<255)) pos++;
            }
            Page[pos] = i;
        } else
        Page[pos]=i;
    }
}

Функция CreateCodeBookInBuffer создаёт 256 кодовых страниц, которые располагаются последовательно в буфере, указатель на который передаётся через единственный параметр.


void CreateCodeBookInBuffer(BYTE *Buffer)
{
    for (int i=0;i<256;i++)
    {
        CreateCodePage(Buffer+(i<<8));
    }
}

В данной функции непосвящённого программиста может сбить с толку битовый сдвиг влево на 8 бит. На месте битового сдвига должна стоять операция умножения на 256. Битовый сдвиг влево на 1 бит равносильно умножения на 2, на 2 бита равносильно умножению на 4, а сдвиг на 8 бит равносилен умножения на 256. Причина использования сдвига очень проста: операция битового сдвига производится быстрее, чем операция умножения, это знает любой, кто имеет опыт программирования на ассемблере.
  Функция CreateCodeBook создаёт книгу кодов и сохраняет её в файл.


bool CreateCodeBook(LPCTSTR FileName)
{
    BYTE* MemCodeBook = (BYTE*)VirtualAlloc(0, 0x10000, MEM_COMMIT + MEM_RESERVE, PAGE_READWRITE);
    CreateCodeBookInBuffer(MemCodeBook);

    HANDLE FH = CreateFile(FileName, GENERIC_WRITE, FILE_SHARE_READ, 0, CREATE_ALWAYS,0,0);
    if (FH==INVALID_HANDLE_VALUE) return false;
    DWORD Writed;
    WriteFile(FH,(void*)MemCodeBook,0x10000,&Writed,0);
    CloseHandle(FH);
    VirtualFree(MemCodeBook,0,MEM_RELEASE);
    return (Writed==0x10000);
}

  Итак, книгу кодов мы создали теперь надо написать функции, которые производят шифровку и расшифровку данных.


void CryptData(BYTE* CodeBook, BYTE *SourceBuff, int BuffSize, BYTE *DestBuff)
{
    BYTE CB, CCB;
    int CP;
    for(int i=0;i<BuffSize;i++)
    {
        CB = SourceBuff;
        CP = rand()%256;
        CCB =GetBytePos(CodeBook+(CP<<8),CB);
        DestBuff=CP;
        DestBuff[(i<<1)+1]=CCB;
    }
}

Функция элементарна: мы берём байт из исходных данных, генерируем случайным образом номер кодовой страницы, получаем индекс исходного байта на выбранной кодовой странице и записываем в результирующий буфер номер кодовой страницы и байт-замену на этой кодовой странице. Функция GetBytePos производит поиск байт в указанном буфере.
  Осталось написать функцию расшифровки, она ещё проще:


void DeCryptData(BYTE* CodeBook, BYTE *SourceBuff, BYTE *DestBuff, int BuffSize)
{
    BYTE CB, CCB;
    int CP;
    for(int i=0;i<BuffSize;i++)
    {
        CP=SourceBuff;
        CCB=SourceBuff[(i<<1)+1];
        CB = CodeBook[(CP<<8)+CCB];
        DestBuff=CB;
    }
}

Здесь тоже всё очень просто: извлекается два байта из исходных (зашифрованных) данных, первый байт это номер кодовой страницы второй это индекс на этой кодовой странице, в результирующий буфер заносится байт, находящийся на указанной кодовой странице по указанному индексу.
  Следующим шагом будет написание функций производящих шифрование файлов. Код функции, осуществляющий шифрование файлов тривиальный: считывается в память книга кодов, считывается в память исходный файл, зашифрованный данные записываются в результирующий файл.


bool CryptFile(LPCTSTR SourceFile, LPCTSTR DestFile, LPCTSTR CodeBookFile)
{
    HANDLE CBFH = CreateFile(CodeBookFile, GENERIC_READ, FILE_SHARE_READ,0,OPEN_EXISTING,0,0);
    if (CBFH==INVALID_HANDLE_VALUE) return false;
    int CBFS = GetFileSize(CBFH,0);
    if (CBFS!=0x10000)
    {
        CloseHandle(CBFH);
        return false;
    }

    HANDLE SFH = CreateFile(SourceFile, GENERIC_READ, FILE_SHARE_READ,0,OPEN_EXISTING,0,0);
    if (SFH==INVALID_HANDLE_VALUE) return false;
    HANDLE DFH = CreateFile(DestFile, GENERIC_WRITE, FILE_SHARE_READ,0,CREATE_ALWAYS,0,0);
    if (DFH==INVALID_HANDLE_VALUE) return false;

    BYTE* SourceBuff = (BYTE*)VirtualAlloc(0,BufferSize,MEM_COMMIT+MEM_RESERVE,PAGE_READWRITE);
    BYTE* DestBuff = (BYTE*)VirtualAlloc(0,BufferSize*2,MEM_COMMIT+MEM_RESERVE,PAGE_READWRITE);
    BYTE* CodeBook = (BYTE*)VirtualAlloc(0,0x10000,MEM_COMMIT+MEM_RESERVE,PAGE_READWRITE);

    DWORD Readed = 0;
    ReadFile(CBFH,CodeBook,0x10000,&Readed,0);
    CloseHandle(CBFH);

    DWORD Writed = 0;
    do
    {
        ReadFile(SFH,SourceBuff,BufferSize,&Readed,0);
        CryptData(CodeBook,SourceBuff,Readed,DestBuff);
        WriteFile(DFH,DestBuff,Readed*2,&Writed,0);

    }
    while (Readed==BufferSize);

    CloseHandle(SFH);
    CloseHandle(DFH);

    VirtualFree(SourceBuff,0,MEM_RELEASE);
    VirtualFree(DestBuff,0,MEM_RELEASE);
    VirtualFree(CodeBook,0,MEM_RELEASE);

    return true;
}

Следует подметить, что шифровка файла производится по порциям размером в 1 МБ, это обусловлено тем что при шифровке файлов большого размера (более 600 МБ), реальна ситуация нехватки виртуальной памяти. Функция расшифровки файлов аналогична вышеприведённой, приводить её здесь не имеет никакого смысла.
  Все вышеприведённые функции и вынесены в заголовочный файл (RDC.h), который вы можете подключить в своём проекте на С++. Также мною была создана DLL содержащая функции из RDC.h. Созданную DLL можно использовать в программах написанных на других языках. В качестве примера я написал программу на Delphi, которая производит шифрование файлов с использованием функций из RDC.DLL.
  Исходники RDC.DLL и программы производящей шифрование файлов с использованием RDC.DLL находятся в архиве, прилагающемся к данной статье.

Скачать исходники
1. Исходники RDC.DLL на С++ (CodeBlocks+MinGW)
2. Исходники программы использующей RDC.DLL (Delphi 7)

Вместо первого комментария:
Аббревиатура RDC расшифровывается следующим образом: Replace Data Crypt.

Комментарии

  1. сергей
    April 24th, 2010 | 18:05

    Уважаю таких ПАРНЕЙ !!! Сам 10 лет назад закончил, в силу обстоятельств, заниматься программированием, но иногда до дрожи в руках пытаюсь чего нибудь “черкануть”… Завидую я ВАМ.

  2. Александр
    June 14th, 2010 | 14:02

    Нормальный алгоритм. Предлагаю модификацию для сохранения размера передаваемой информации – сделать таблицы символов размером 128 байт и сделать их 128 штук фактически их будет 64. кодировать символ по этому же алгоритму в первые 4 бита номер таблицы в последние 4 бита номер символа причём порядок(код таблицы, код символа) можно тоже задавать динамически.

  3. dan
    June 25th, 2010 | 20:03

    У этого алгоритма много недостатков:
    1)Он мне не нравится!!!
    2)Используется ОЧЕНЬ много памяти на хранение таблиц соответвия и получившихся данных.
    3)Тратится очень много времени на обработку.
    4)Всего 256 возможных вариантов шифровок( а надо не менее 2^120).
    5)Есть алгоритм и по лучше:
    а)будем считать все символы числами 0-255.
    б)берем случайную бесконечную строку и “складываем” с исходным текстом: первый символ с первым, второй со вторым,… ( result:=(x+y)mod 256).
    в)При дешифрации “вычитаем” туже самую строку.
    Проблемы:
    1)Где взять случайную бесконечную строку? Random(256) без Randomize выдаст то, что надо – осталось только “промотать” первые N символов.
    2)Некоторые символы могу быть плохие (например #26 = EOF). Создать массив хороших символов и работать в нем так же, как и в алфавите на 256 символов. Или писать сложную функцию, которая их обойдет (я сделал именно так).

  4. rpy3uH
    June 30th, 2010 | 13:26

    >>4)Всего 256 возможных вариантов шифровок( а надо не менее 2^120).
    нет, их намного-много больше чем 256!

    >>б)берем случайную бесконечную строку и “складываем” с исходным текстом: первый символ с первым, второй со вторым,… ( result:=(x+y)mod 256).
    этот алгоритм не намного лучше чем мой. в твоём случае размер “книги кодов” равен размеру шифруемого файла (а допустим мы шифруем файл размеров 5 ГБ, слишком много накладных расходов), а в моём алгоритме всегда равен 64 КБ.

    >>2)Некоторые символы могу быть плохие (например #26 = EOF). Создать массив хороших символов и работать в нем так же, как и в алфавите на 256 символов. Или писать сложную функцию, которая их обойдет (я сделал именно так).
    не понимаю зачем это надо, это вообще бесполезная работа. При щифровани на выходе мы получаем бинарный файл и плевать какие там символы “плохие” или нормальные.

  5. dan
    July 27th, 2010 | 23:26

    После шифрации моим способом передается закрытый текст, равный по объему исходному, и число-ключ.
    Для тех, кто не понял:

    Program test1
    var
    i:integer;
    begin
    for i:=1 to 10 do
    writeln(random(100));
    end.

    Эта программа всегда выведет один и тот же столбик двузначных чисел, и он будет “случайным”, то есть числа будут равномерно размазаны по всей длине.

    Program test2
    var
    i:integer;
    key:integer;
    begin
    readln(key);

    for i:=1 to key do;

    for i:=1 to 10 do
    writeln(random(100));
    end.

    А эта программа для каждого значения key выведет свой особый столбик чисел, который можно использовать для шифрации.

  6. rpy3uH
    July 29th, 2010 | 16:35

    Такой алгоритм генерации столбика двузначных чисел – детский! (без обид)
    Во-первых, надеяться на то что random без randomize всегда даёт одни и те же значения ГЛУПО! Если в новой версии Delphi что-то изменится то программа перестанет расшифровывать.
    Во-вторых, зная особенность этого алгоритма очень легко расшифровать данные НЕ зная ключа расшифровки просто-напросто перебирая варианты ключей (если ключ число integer, то вариантов всего 2^32), в моём алгоритме без книги кодов расшифровка перебором будет длиться очень-очень долго

  7. dan
    August 3rd, 2010 | 23:30

    Вы, безусловно, правы, но:

    С точки зрения программирования:
    1)Вы сможете перебрать 2^32 вариантов? (Распознаватели текста – вещь не надежная)
    2)А 2^64?
    3)А например в java встроена длинная арифметика.
    4)Random вполне меня устраивает, но если хочется – можно написать свою функцию случайных чисел.

    С точки зрения математики:
    1)У вас каждому символу сопоставляется 256 других символов, и не обязательно различных. А у меня с равной вероятностью может выпасть любой символ.
    2)64 Kb – это слишком много для ключа. Представьте, что вам надо защитить канал связи для передачи пароля! Размер предаваемых данных вырастет на 3-4 порядка!
    3)Тот алгоритм, который я защищаю в основном и используется в промышленности при “шифровании данных с закрытым ключом”.

  8. September 2nd, 2010 | 16:30

    Спасибо за статью, взял на заметку!

  9. Hav4ik
    September 5th, 2010 | 10:29

    Спасибо за статью ! :grin: Алгоритм , конечно , довольно проста для воспринимании , даже для новичка как я :lol: . Но , кажется , не слышком много памятизанимает расшифрованный файл ?
    зато интерестное использование алгоритма наших прадедушек :razz:

  10. rpy3uH
    September 10th, 2010 | 08:54

    Размер файла удваивается. Шифровка файла происходит порциями по 1 МБ, поэтому расход памяти на файл не должна превышать 3 МБ (1 МБ на исходные данные+2МБ на зашифрованные).

    Спасибо за подсказку об утечке памяти, в функциях шифровки и расшифровки выделенная память не освобождается.

  11. Asdprom
    March 10th, 2011 | 22:35

    Алгоритм интересный.Но идея не нова.
    и к стати вместо кодовых страниц лучше брать случайные числа. Для этого использовать генераторы псевдослучайных чисел(ГПСЧ).Причем ГПСЧ должен быть криптостойким.

  12. Vitaliy_progC++
    August 26th, 2014 | 13:30

    Я начинающий программист, хочу найти людей которые профессионально пишут на с ++. Хотел бы спросить какие книги вы посоветуете прочитать чтобы хорошо усвоить программирования на С ++ … Спасибо.

Ответить

 


1cloud