Учебный симметричный криптоалгоритм S-des, шифрование данных Опции

[klem4]

Теория.

СИММЕТРИЧНЫЕ КРИПТОАЛГОРИТМЫ.

Самый популярный и широко применяемый в системах защиты алгоритм
это DES (Data Encrypted Standart), принятый в 1977г Национальным
бюро стандартов США (NBS), ныне называемым Национальным институтом
стандартов и технологий (NIST). Официальное название стандарта
Federel Information Processing Standard 46 (FIPS PUB 46).

Шифруемые данные разбиваются на 64-битные блоки и шифруются
поблочно с использованием ключа 56 бит. Многошаговый (16 раундов)
алгоритм преобразует каждый исходный блок в 64-битный шифрованный
блок. Тот же алгоритм с тем же ключом используется для обратного
преобразования шифрованного блока в исходный вид.

В силу сложности алгоритма DES рассмотрим его суть на учебном
алгоритме S-DES, который разработан в учебных целях профессором
Эдвардом Шейфером (Edward Schaefer) из университета Санта-Клара и
опубликован в 1996г. По свойствам и структуре он подобен DES, но
имеет существенно меньшую размерность и потому проще в освоении,
но практической криптостойкостью не обладает.



Учебный симметричный криптоалгоритм S-DES.

На вход поступают исходные 8-битовые блоки, для шифрования
используется 10-битовый ключ, на основе ключа генерируется 2
подключа по 8 бит и производится 2 раунда шифрования, для дешифрования
используется тот же алгоритм и тот же ключ, но подключи используются
в обратном порядке. Пусть X - исходный блок, Y - результат шифрования,
тогда процесс шифрования:

Y = IP-1( fk2( SW( fk1( IP( X ) ) ) ) )

Процесс дешифрования:

X = IP-1( fk1( SW( fk2( IP( Y ) ) ) ) )



Рассмотрим теперь модули, используемые при шифровании и дешифровании
8-битного блока. Рассмотрим их работу на примере блока: 00001011 (11)

Исходный блок X = 00001011(2) = 11(10)

1. Модуль IP. Шифрование начинается с модуля начальной перестановки
IP , в котором 8 бит исходноо блока переставляются в соотвествии
с таблицей:

IP: (1, 5, 2, 0, 3, 7, 4, 6)

Для нашего примера IP( 00001011 ) = 00011001.

Здесь же укажем таблицу, задающую последний модуль преобразования,
перестановку, обратную начальной IP-1 :

IP-1: (3, 0, 2, 4, 6, 1, 7, 5)

Легко убедиться, что эта перестановка действительно является обратной
по отношению к первой, т.е. IP-1( IP ( X ) ) = X . Примените ее
к результату модуля IP нашего примера и получите исходный 8-битный блок.

2. Модуль fk - это самый сложный компонент, в этом модуле в
преобразовании, кроме 8-битового результата модуля 1, участвует
8-битовый подключ, обозначим его SK (в первом раунде это будет
K1, во втором - K2). Обозначим L и R - левую и правую половинки
(по 4 бита) входного блока, а F() - некоторое преобразование в
пространстве 4-х битовых строк, не обязательно взаимно-однозначное,
подключ SK является параметром этого преобразования. Тогда модуль
fk описывается следующим образом:

fk( L, R ) = ( L + F( R, SK ) , R )

где + -- обозначает побитовую операцию XOR

Правая половинка R без изменения передается на выход модуля и
параллельно - на вход нелинейной функции F, зависящей также от
подключа SK. Результат функции F(R,SK) складывается по операции XOR
со входной левой полвинкой и передается на выход в качастве левой
половинки. Итого на выходе опять 8-битовый блок.

Рассмотрим теперь нелинейную функцию F(R,SK). Она состоит из следующих
модулей:

2.1. Входной блок функции ( 4-х битная правая половинка R) расширяется
с перестановкой (модуль E/P) до 8 бит согласно следующей таблице:

E/P: (3, 0, 1, 2, 1, 2, 3, 0)

В нашем примере для правой половинки R (1001) на выходе модуля
E/P будет получен результат: (11000011)

2.2 8-битовый результат модуля 2.1 складывается по операции XOR
с 8-битовым подключом SK, 8-битовый результат представим в виде
таблицы из 2-х строк (левые 4 бита -- 0-я строка, следующие 4
бита - 1-я строка):

В нашем примере подключ К1: 00100001, результат модуля E/P:
11000011, результат операции XOR: 11100010, представим результат в
виде таблицы:

1 1 1 0
0 0 1 0

2.3. Матрицы кодирования (S-матрицы). Каждая строка результата
п.2.2. подвергается преобразованию по своей S-матрице (матрица
S0 служит для сжатия 0-й строки, а матрица S1 - для сжатия 1-й
строки). В алгоритма S-DES всего 2 S-матрицы (S0 и S1). На вход
каждой S-матрицы подаются по 4 бита, на выходе получается по 2
бита.



S0:

1 0 3 2
3 2 1 0
0 2 1 3
3 1 0 2

S1:

2 3 1 0
1 0 2 3
0 1 3 2
3 0 2 1



Эти S-модули работают следующим образом. последний и предпоследний
биты входной последовательности рассматриваются как 2-битовое
число, определяющее номер строки S-матрицы, а первый и нулевой
как число, определяющее номер столбца. На пересечении соотвествующих
строки и столбца находится число, задаюшее 2-битовое выходное
значение.

В нашем примере на вход матрицы S0 поступает последовательность 1110.
последний и предпоследний биты дают число 11, т.е. номер строки -- 3.
Первый и нулевой биты дают число 10, т.е. номер столбца -- 2.
В матрице S0 на пересечении строки 3 и столбца 2 стоит число 0,
в битовом представлении это 00 . Таким образом входная 4-битовая
последовательность 1110 преобразовалась в выходную 2-битовую
последовательность 00.

На вход матрицы S1 поступает последовательность 0010. На пересечении
строки 0 и столбца 2 матрицы S1 стоит число 1 (в битовом представлении
01). Таким образом входная последовательность 0010 преобразовалась
в выходную 01.

Сцепляя (concatenation) результаты на выходе S-матриц получаем
итоговый результат модуля 2.3: 0001. Итак 8-битовая
последовательность на входе модуля S-матриц (2.3) 11100010
преобразована в 4-х битовую последовательность 0001.

2.4. Перестановка P4 задается таблицей:

P4: (0, 1, 2, 3)

Т.е. 4-му биту присваивается значение 0-го, 3-му - значение первого и т.д.

В нашем примере последовательность 0001 превращается в
последовательность 1000 . Это и есть результат функции F( R, SK ).


2.5. Полученный результат функции F( R, SK ) складывается с
помощью побитовой операции XOR с левой половинкой битовой
последовательности на входе модуля fk (п.2). Полученный результат
операции XOR cцепляется (concatenation) с правой половинкой
входной последовательности модуля fk (п.2).

В нашем примере входная последовательность модуля fk (п.2)
00011001, отделим левую и правую половинки: 0001 1001.
Результат L + F( R, SK ) = 0001 XOR 1000 = 1001.

Сцепляем этот результат с правой половинкой и получаем итоговый
результат модуля fk в первом раунде алгоритма:

1001 1001 = 10011001.


3. Модуль SW -- это перестановка левой и правой половинок входной
8-битовой последовательности.

Для нашего примера входная последовательность 10011001,
на выходе получаем 10011001. Это результат первого раунда алгоритма.

Во втором раунде входная последовательность на модуле fk:

       L     R
      1001 1001
 E/P( R ) = 11000011
  + K2      00100001
	=   11001001
	    1100  1001
  1100 --> S0[ 3,0 ] = 3 --> 11
  1001 --> S1[ 2,1 ] = 1 --> 01
              1101
 P4( 1101 ) = 1011
   + L        1001
	    = 0010

  ,R        = 1001

IP-1( 00101001 ) = 10000011

шифрованный блок Y = 10000011



Дешифрование проводится по тому же самому алгоритму, что и шифрование,
но порядок подачи подключей в раунды обратный (в первом раунде - последний
подключ, а в последнем раунде - первый подключ).

генерация ключей и общая схема алгоритма:

первый раунд S-DES:

второй раунда S-DES:

Программа разбита на 3 модуля

* unit uBits -- модуль для работы с двоичным представлением числа
* unit uKeys -- модуль содержащий подпрограммы генерации подключей K1 и K2
* unit uSDES -- модуль содержащий подпрограммы кодирования данных

UNIT uBits

unit uBits;

interface

const                          {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}  { биты       }
  P10: array [0..9]  of Byte = (2, 4, 1, 6, 3, 9, 0, 8, 7, 5); { модуль P10 }
   P8: array [0..7]  of Byte =       (5, 2, 6, 3, 7, 4, 9, 8); { модуль P8  }
   P4: array [0..3]  of Byte =                   (0, 1, 2, 3); { модуль P4 (в этом примере просто переворот)}

                              {0, 1, 2, 3, 4, 5, 6, 7} { биты }
   { модуль IP  }
   IP: array [0..7] of Byte = (1, 5, 2, 0, 3, 7, 4, 6);
   { модуль IP_ }
  IP_: array [0..7] of Byte = (3, 0, 2, 4, 6, 1, 7, 5);

   { модуль EP }              {0, 1, 2, 3, 4, 5, 6, 7} { биты }
  EP: array [0..7] of Byte =  (3, 0, 1, 2, 1, 2, 3, 0);

   { матрица кодирования S0 }
  S0: array [0..3, 0..3] of Byte = (
    (1, 0, 3, 2),
    (3, 2, 1, 0),
    (0, 2, 1, 3),
    (3, 1, 0, 2)
  );

  { матрица кодирования S1 }
  S1: array [0..3, 0..3] of Byte = (
    (2, 3, 1, 0),
    (1, 0, 2, 3),
    (0, 1, 3, 2),
    (3, 0, 2, 1)
  );

type
  TBit   = 0..1;
  TBit2  = array [0..1] of TBit;
  TBit4  = array [0..3] of TBit;
  TBit8  = array [0..7] of TBit;
  TBit10 = array [0..9] of TBit;

  { ф-я вернет бит bit_num числа value }
  function get_bit(const value: Integer; const bit_num: Byte): TBit;

  { пр-а установит бит bit_num числа value в значение bit_value }
  procedure set_bit(var value: Integer; const bit_num: Byte; const bit_value: TBit);

  { печать массива бит, длиной bits_count }
  procedure print_bits(const bits: array of TBit; const bits_count: Byte);

  { пр-а сохранит в массив bits биты числа value, нулевой бит = bits[0] }
  procedure int2bits(const value: Integer; var bits: array of TBit; const bits_count: Byte);

  { ф-я вернет десятичное значение, соотв. двоичному числу, хранящемуся в bits }
  function bits2int(const bits: array of TBit; const bits_count: Byte): Integer;

  { пр-а разбивает массив битов source длиной source_len
   на две части part1 и part1,
   пример:
          (* 0,1,2,3,4,5,6,7 *) -- индексы в массиве

   source = (1,1,0,0,1,0,1,0) = 01010011(2)

   part1 = (1, 0, 1, 0) = 0101(2)
   part2 = (1, 1, 0, 0) = 0011(2)
  }
  procedure cat_bits (
    const source: array of TBit;
    var part1, part2: array of TBit;
    const source_len: Byte
  );

  { пр-а "склеивает" 2 последовательности бит part1 и part2,
   длины которых равны part_len в одну последовательность destination,
   пример:

    part1 = (1, 1, 1, 0) = 0111(2)
    +
    part2 = (0, 0, 0, 1) = 1000(2)
    =
    destination = (0, 0, 0, 1, 1, 1, 1, 0) = 01111000
  }
  procedure concat_bits (
    const part1, part2: array of TBit;
    var destination: array of TBit;
    const part_len: Byte
  );

implementation

function get_bit(const value: Integer; const bit_num: Byte): TBit;
var
  buffer: array[0 .. 15] of TBit;
  i: integer;
begin
  fillchar(buffer, 16, 0);
  for i := 0 to pred(sizeof(value) * 8) do begin
    buffer[pred(sizeof(value) * 8) - i] := (value shr i) and $1;
  end;
  get_bit := buffer[pred(sizeof(value) * 8) - bit_num];
end;

procedure set_bit(var value: Integer; const bit_num: Byte;
 const bit_value: TBit);
var
  tmp: Integer;
begin
  tmp := round(exp(bit_num * ln(2)));

  if bit_value = 1 then
    value := value or tmp
  else if (value and tmp) = tmp then
    value := value xor tmp
end;

procedure print_bits(const bits: array of TBit; const bits_count: Byte);
var
  i: Byte;
begin
  writeln;
  for i := bits_count - 1 downto 0 do
    write(bits[i]);
end;

procedure int2bits(const value: Integer; var bits: array of TBit;
 const bits_count: Byte);
var
  i: Byte;
begin
  for i := 0 to bits_count - 1 do
    bits[i] := get_bit(value, i);
end;

function bits2int(const bits: array of TBit; const bits_count: Byte): Integer;
var
  i: Byte;
  value: Integer;
begin
  value := 0;
  for i := 0 to bits_count - 1 do
   set_bit(value, i, bits[i]);
  bits2int := value;
end;

procedure cat_bits (
    const source: array of TBit;
    var part1, part2: array of TBit;
    const source_len: Byte
);

var
  i, middle: Byte;
begin
  middle := source_len div 2 - 1;

  for i := middle + 1 to source_len - 1 do
    part1[i - middle - 1] := source[i];

  for i := 0 to middle do
    part2[i] := source[i];
end;

procedure concat_bits (
    const part1, part2: array of TBit;
    var destination: array of TBit;
    const part_len: Byte
);

var
  i: Byte;
begin
  for i := 0 to part_len - 1 do
    destination[i] := part2[i];

  for i := part_len to 2 * part_len - 1 do
    destination[i] := part1[i - part_len];
end;
end.

UNIT uKeys

unit uKeys;

interface
  uses uBits;

const
  KEY1: Integer = 0; { в этой переменной будет храниться первый ключ }
  KEY2: Integer = 0; { в этой переменной будет храниться второй ключ }

  { пр-а генераципи 2-х 8бит ключей из 1-го 10бит ключа }
  procedure generate_keys(const key: Integer);


implementation

procedure generate_keys(const key: Integer);

  procedure shift(var bits: TBit10);
  var
    i: Byte;
    tmp: TBit;
  begin
    tmp := bits[9];
    for i := 9 downto 6 do
      bits[i] := bits[i - 1];
    bits[5] := tmp;

    tmp := bits[4];
    for i := 4 downto 1 do
      bits[i] := bits[i - 1];
    bits[0] := tmp
  end;

  procedure module_P8(var bits8: TBit8; const bits10: TBit10);
  var
    i: Byte;
  begin
    for i := 0 to 7 do
      bits8[i] := bits10[ P8[7 - i] ];
  end;

  procedure module_P10(var bits10: TBit10);
  var
    i: Byte;
  begin
    for i := 0 to 9 do
      bits10[i] := get_bit(key, P10[9 - i]);
  end;

var
  i: Byte;

  buff8: TBit8;
  buff10: TBit10;

begin
  { сохраняем в buff10 перестановку бит числа key по модулю p10 }
  module_P10(buff10);

  { модуль SHIFT1 }
  shift(buff10);

  { для получения ключа Key1 выполним перестановку по
   модулю P8 для "buff10" }

  module_P8(buff8, buff10);

  KEY1 := bits2int(buff8, 8); { ------- KEY1 -------- }

  { для получения ключа Key2 выполним сдвиг SHIFT2 и
   перестановку получившейся последовательности бит
    по модулю P8
  }

  shift(buff10);

  module_P8(buff8, buff10);

  KEY2 := bits2int(buff8, 8); { ------- KEY2 -------- }
end;

end.

UNIT uSDES

unit uSDES;

interface
  uses uBits, uKeys;

  type
    TCryptType = (ctCrypt, ctDecrypt);

  { шифрация текстового файла }
  procedure crypt_file(const file_in, file_out: String);
  procedure decrypt_file(const file_in, file_out: String);

implementation

 { перестановка массива бит bits по модулю IP }
procedure module_IP(var bits: TBit8);
var
  i: Byte;
  temp: TBit8;
begin
  for i := 0 to 7 do
    temp[i] := bits[ IP[i] ];

  move(temp, bits, sizeof(temp));
end;

 { перестановка массива бит nits по модулю IP_ }
procedure module_IP_(var bits: TBit8);
var
  i: Byte;
  temp: TBit8;
begin
  for i := 0 to 7 do
    temp[i] := bits[ IP_[i] ];

  move(temp, bits, sizeof(temp));
end;

 { расширение 4-х битовой последователности до 8-ми бит, с
  использованием модуля EP }
procedure module_EP(const bits4: TBit4; var bits8: TBit8);
var
  i: Byte;
begin
  for i := 0 to 7 do
    bits8[i] := bits4[ EP[7 - i] ];
end;

 { преобразование 4-битовой последователности по
  матрице кодирования S0
 }
procedure module_S0(const bits4: TBit4; var bits2: TBit2);
var
  row, col: TBit2;
begin
  move(bits4[0], col, 2 * sizeof(TBit));
  move(bits4[2], row, 2 * sizeof(TBit));

  int2bits(S0[ bits2int(row, 2), bits2int(col, 2) ], bits2, 2);
end;

procedure module_S1(const bits4: TBit4; var bits2: TBit2);
var
  row, col: TBit2;
begin
  move(bits4[0], col, 2 * sizeof(TBit));
  move(bits4[2], row, 2 * sizeof(TBit));

  int2bits(S1[ bits2int(row, 2), bits2int(col, 2) ], bits2, 2);
end;

procedure module_P4(const part1, part2: TBit2; var bits: TBit4);
var
  i: Byte;
  buff4: TBit4;
begin
  concat_bits(part1, part2, bits, 2);

  for i := 0 to 3 do
    buff4[i] := bits[ P4[3 - i] ];
  move(buff4, bits, sizeof(buff4));
end;

procedure s_des(
    const left_in, right_in: TBit4;
    var left_out, right_out: TBit4;
    const key: Integer
);

var
  buff8A: TBit8;
  s0In, s1In, p4Out: TBit4;
  s0Out, s1Out: TBit2;
  temp: Integer;
begin

  module_EP(right_in, buff8A);

  temp := bits2int(buff8A, 8) xor key;

  int2bits(temp, buff8A, 8);

  cat_bits(buff8A, s0In, s1In, 8);

  module_s0(s0In, s0Out);
  module_s1(s1In, s1Out);

  module_p4(s0Out, s1Out, p4Out);

  int2bits(bits2int(left_in, 4) xor bits2int(p4Out, 4), left_out, 4);

  move(right_in, right_out, sizeof(right_in));
end;

function crypt_byte(const _byte: Byte; const ct: TCryptType): Byte;
var
  K1, K2: Integer;

  left_in, right_in, left_out, right_out: TBit4;
  buff8: TBit8;

begin

  if ct = ctCrypt then begin
    K1 := KEY1;
    K2 := KEY2;
  end else begin
    K1 := KEY2;
    K2 := KEY1;
  end;

  int2bits(_byte, buff8, 8);

  module_IP(buff8);

  cat_bits(buff8, left_in, right_in, 8);

  s_des(left_in, right_in, left_out, right_out, K1);

  s_des(right_out, left_out, left_in, right_in, K2);

  concat_bits(left_in, left_out, buff8, 4);

  module_IP_(buff8);

  crypt_byte := Byte(bits2int(buff8, 8));
end;

procedure crypt_file(const file_in, file_out: String);
var
  f_in, f_out: file of byte;

  s: String;
  i, iEnc: Byte;
begin
  assign(f_in, file_in);
  reset(f_in);

  assign(f_out, file_out);
  rewrite(f_out);

  while not eof( f_in ) do begin
    read(f_in, i);
    iEnc := crypt_byte(i, ctCrypt);
    write(f_out, iEnc);
  end;

  close(f_in);
  close(f_out)
end;

procedure decrypt_file(const file_in, file_out: String);
var
  f_in, f_out: file of byte;
  s: string;
  i, iDec: Byte;
begin
  assign(f_in, file_in);
  reset(f_in);
  assign(f_out, file_out);
  rewrite(f_out);

  while not eof ( f_in ) do begin
    read(f_in, i);
    iDec := crypt_byte(i, ctDecrypt);
    write(f_out, iDec);
  end;

  close(f_in);
  close(f_out);
end;

end.

тестовая программа:

uses crt, uBits, uKeys, uSDES;

var
  key: Integer;

begin
  clrscr;

  write('input key: '); readln(key);

  if ( key < 0 ) or ( key > 1023 ) then begin
    writeln('bad key');
    readln;
    halt(1);
  end;

  generate_keys(key);

  writeln('encoding -- start ...');

  crypt_file('c:\my_file.txt', 'c:\crypt_file.des');
  decrypt_file('c:\crypt_file.des', 'c:\decrypt_file.txt');

  writeln('encoding -- complete.');
  readln; 
end.

[volvo]

В процессе тестирования были немного подправлены процедуры crypt_file и decrypt_file из модуля uSDES, благодаря чему программа стала работоспособной не только при использовании Free Pascal-я, но и для Турбо Паскаля 7.0.

Внимание: при использовании FPC убедитесь, что программа собирается в режиме совместимости с TP (либо в настройках компилятора: Options->Compiler->Compiler mode установить переключатель в "Turbo Pascal compatible", либо самой первой строкой каждого файла в проекте добавить {$mode TP}).

Сообщение отредактировано: volvo - 25.01.2009 21:49