Реализация шифра ГОСТ 28147-89 на PHP

52 комментария

Вообщем на днях в универе задали курсовик. Нужно было реализовать на любом языке программу шифрующую по алогритму ГОСТ 28147-89.

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены.(определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки).

Я решил выбрать для этих целей PHP по следующим причинам:

  • Один из одногрупников мне сказал что на PHP такое реализовать не возможно. (Как бы не так :))
  • На PHP не было еще ни одной нормальной реализации
  • Ну и собственно говоря кроме PHP я знаю только C++ и то на уровне hello world

В итоге я написал класс работающий с шифром ГОСТ 28147-89 на PHP. Исходный код тут приводить не буду. А просто опишу как работать с классом:

include('ClassGost.php');
$data="Данные для шифрования";

//Ключ должен быть ровно 32байта (256бит). Обязательно! Требуется стандартом шифрования
$key="abababababababababababababababab";

$gost=new ClassGost;
$data_encoded=$gost->Encode($data, $key);

echo(base64_encode($data_encoded));

По окончании работы скрипта получим: «PcH96aNxSxTY7f024pD6V07zDKUhg+QF» (делаю вывод в бейс64 так как зашифрованная строка имеет непечатаемые символы)
Для расшифровки надо юзать такой код:

include('ClassGost.php');
$data_encoded=base64_decode('PcH96aNxSxTY7f024pD6V07zDKUhg+QF'); 

$key="abababababababababababababababab";

$gost=new ClassGost;
$data=$gost->Decode($data_encoded, $key);

echo($data);

На выходе получаем наш исходный текст: «Данные для шифрования».

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

//Таблица замен устанавливается третьим параметром в функциях Encode или Decode
$data_encoded=$gost->Encode($data, $key, $table);

Пример формата таблицы замен вы сможете найти в комментариях к функциям класса.

Скачать реализацию на PHP: Gost_PHP
UPD: Скачать реализацию на JS: Gost_JS (автор Никита)

UPD: Поддержка 64-битных систем!
UPD: В архив добавлена реализация одного из проверочных примеров из Приложения А к ГОСТ Р 34.11-94
UPD: Исправлен косяк с указанием ключа

    1. Дмитрий Амиров Автор

      В том классе во первых я лично нашел ошибку в шифровании, из — за которой данные шифровались можно сказать «по другому» алгоритму.

      Во вторых работа там ведется только со строками, т.е. данные преобразуются к строке из едениц и нулей типа «11010111…» и работа идет именно с этой строкой.

      В моем случае работа идет с напрямую битами, то есть как и должно быть по сути.

      1. Trololo

        Хм.. заглянул только что в ваш код. Неплохо. Действительно реализованна работа с числами/байтами/битами. Достойная реализация на PHP.

        До этого постоянно натыкался на реализации, где как вы сказали «работа там ведется только со строками», что по сути не правильно.

      2. Trololo

        Вы сказали что вы еще нашли ошибку в алгоритме шифрования. Уже битый час изучаю тот алгоритм не могу найти ничего необычного =(

        1. Дмитрий Амиров Автор

          Не буду разбирать и приводить все ошибки. Но возьму самый бросающийся в глаза участок. Взгляните на данный код:

          $C[0] = 0x1010101;
          $C[1] = 0x1010104;
          $C[0] = base_convert($C[0], 16, 10);
          $C[1] = base_convert($C[1], 16, 10);
          

          Ничего необычного не замечаете?

          1. Trololo

            Эм… Нет. А должен?

            Все вроде логично. Число задатеся в 16ричной системе счисления. Потом переводится в десятичную… Что здесь может быть не так?

            1. Дмитрий Амиров Автор

              Да, пожалуй должны) Все просто.

              Указание числа через 16ричную систему счисления это всего лишь способ представления числа , по сути нет разницы как указывать число, хранится и выводится оно будет в 10ной системе счисления (ну или если совсем точно то хранится оно в 2ной системе)

              То есть приведенный выше код берет, прошу заметить, уже нормальное число (в 10ной системе), преобразует его в строку, данную строку принимает как число в 16ной системе, и переводит его еще раз в 10ную. Вообщем бред да и только.

              Теперь надеюсь вы понимаете почему:

              $int=0xF;
              echo($int); //Выведет 15
              echo(base_convert($int, 16, 10)); //Выведет 21
              

              И почему весь тот скрипт фактически не рабочий?

              1. Trololo

                Мда, спасибо, теперь понятно.

                Сейчас просмотрел, тот код. Такие переводы чисел там чуть ли не на каждой строке. Удивительно как работает только…

    2. LadraGor

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

      1. Дмитрий Амиров Автор

        Да, действительно здесь реализован только алгоритм простой замены.

  1. Fenix

    Единственный огромный минус данного класса — это отсутствие поддержки 64-битных систем. Ибо на них не будет работать ваша функция сдвига по модулю 2 в степени 32…

    1. Дмитрий Амиров Автор

      Пофиксил. Теперь класс должен работать и на 64-битных системах.

  2. Дмитрий

    У себя в блоге отписался, тут тоже напишу. Спасибо за указание на ошибки в скрипте. Единственное, хочу заметить, что то, что у вас было задано как курсовик, у нас было одной из 4х лаб ;) Возможно из-за спешки, как следствие, наличие таких ошибок.

    1. Дмитрий Амиров Автор

      Спасибо, за ваш комментарий.

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

      Просто по окончании написании своего курсовика долго не мог понять почему ваш и мои скрипты выдают разные данные, хотя вроде бы у меня было написанно все правильно. Только потом понял почему.

  3. Русский

    Ваша реализация, к сожалению, не соответствует стандарту, о чём свидетельствует результат пропуска через неё проверочных векторов (взятых из стандарта ГОСТ Р 34.11-94).

    1. Дмитрий Амиров Автор

      Эм, поправте меня если я ошибаюсь. Но ведь ГОСТ Р 34.11-94 регламентирует вычисление хеш функции и никак не связан с шифром выше. Приведите пожалуйста пример ваших проверочных векторов.
      А также, возможно, вы забыли изменить таблицу замен?

      1. Русский

        Да, Вы правы, ГОСТ Р 34.11-94 описывает хэш-функцию. Но в своей основе эта функция имеет алгоритм ГОСТ 28147-89. Так что связан весьма. В тексте стандарта на хэш-функцию даётся проверочный пример, в составе которого имеется и зашифрование в режиме простой замены по ГОСТ 28147-89.

        Может быть, я не совсем правильно использую ваш класс, и в том противоречие? В таком случае предлагаю проверить Вам.

        Таблицу замен взял из того же примера:

        	protected $s_block=array(
        		array(4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3),
        		array(14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9),
        		array(5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11),
        		array(7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3),
        		array(6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 3, 11, 2),
        		array(4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14),
        		array(13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12),
        		array(1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12),
        
        	);

        Сами векторы можно взять в тексте стандарта(стр. 11). Элементы ключей, приведённых там, расположены в обратном порядке, то есть, от 7-го до 0-го.

        1. Дмитрий Амиров Автор

          Сейчас пробежался глазами по своему классу, оказалась при кодинге, допустил небольшую ошибку в синтаксисе метода SetKey (см 144 строку):

          $new_key=$val;

          А надо

          $new_key[]=$val;

          Из за этого неверно определялся ключ, и весь клас мог работать неправильно.

          Прогнал ваш пример, теперь все работает и соответствует ГОСТ-у. Обновил архив и приложил скрипт с данным тестом проверочного вектора.

          Спасибо Вам за то что указали на ошибку =)

  4. саша

    а ничего, что в основном шаге циклический сдвиг производится влево, а не вправо, как здесь??

    /** Функция цикличного побитового сдвига вправо
    	 *
    	 * @param integer $block
    	 * @param integer $bits количество битов для сдвига
    	 * @return integer
    	 */
    	protected function Global_BlockCycleShift($block, $bits){
    		if($bits>0){
    			$a=$bits;
    			$b=32-$a;
    			$block=(($block && $a) & ~(-pow(2,$b)))^($block >> $b);
    		}
    		return $block;
    	}
    

    и если я не ошибаюсь, то сдвигают на 11 бит, а тут вроде 21

    protected function Global_MainStep($block, $keys, $cnt_repeat=self::CNT_MAIN_STEP){
    		$this->Global_BlockExplode($block, $n1, $n2);
    
    		if(count($keys)>$cnt_repeat){
    			$cnt_repeat=count($keys);
    		}
    
    		for($i=0; $iGlobal_SummMod32($n1, $keys[$i]);
    
    			$val=$this->Global_BlockReplace($val);
    
    			$val=$this->Global_BlockCycleShift($val, 21);
    
    			$val=$val ^ $n2;
    
    			$n2=$n1;
    			$n1=$val;
    		}
    
    		$this->Global_BlockImplode($block, $n2, $n1);
    		return $block;
    	}
    
      1. Дмитрий Амиров Автор

        Поясню остальным. Циклический сдвиг влево на 11 шагов это тоже самое что и циклический сдвиг вправо на 21 шаг ;)

        1. саша

          ладно все равно кося к нашел)
          в методе setkey, когда ключ строкой задается

                  for($i=0; $i>32; $i+=4){
          	     $tmp=(int)hexdec(bin2hex(substr($key, ($i*4), 4)));
          	     $new_key[]=$tmp;
                  }
          

          тут надо либо $i+=4 оставлять, либо $i*4, а то массив после 2 го цикла нулями заполняется

            1. Наиль

              А так и не поправили в архиве=) долго бился с неправильным декодированием, пока не обратил внимания на этот комментарий. Тем не менее, спасибо за проделанную работу!

  5. Владимир

    Попробовал, как в примере, не работает раскодирует в кракозябры.
    Кодировка utf-8

    1. Дмитрий Амиров Автор

      Боюсь что проблема не в алгоритме. Проблема скорее всего в настройках кодировок скрипта, сервера и прочее.

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

  6. Алексей

    Intellect, отличная работа! А вы не планируете дополнить вашу реализацию шифра гаммированием с синхропоссылкой?

    1. Дмитрий Амиров Автор

      Спасибо! Честно говоря, нет, не планирую. Эту реализацию я делал давно и уже плохо помню что там к чему(

  7. Никита

    Пригодился ваш алгоритм. Только мне требовалась реализация на javascript, а ее не было ни где в интернете. Долго не стал думать, перевел ваш код.
    Если кому-то еще взбредет в голову использовать js, берите здесь:
    https://github.com/Craager/crypto.lab/blob/master/src/algos/GOST.js

    Приложенный в вашем архиве тест проходит. Тексты все шифрует/дешифрует, сколько проверял.
    В конце файла дописаны дополнительные функции bin2hex и sprintf.
    Пробовал как аналог sprintf использовать .toString(16), но отрицательные числа не так как надо вычисляет. Если кто-то знает в чем проблема, сообщите :)

    p.s. По желанию автора, можно внести в конец поста ссылку, либо сам js.
    p.s.s Спасибо ;)

    1. Дмитрий Амиров Автор

      Это круто и достойно уважения) Послал вам пулл реквест, приймите пожалуйста. Не стоит меня в авторы вписывать, ибо все же код ваш, не хочу присваивать себе чужой труд.

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

      PS: приятно что мои труды пригодились еще кому то)

      1. Никита

        Принял пул, но все-таки считаю, что основная работа здесь ваша. Я же раньше работал с php, а сейчас разрабатываю на js, так что, мне понадобилось только определенное количество времени, чтобы пройтись по алгоритму :)
        Файлик прикрепляйте, конечно.

  8. ded

    Интересно…
    У меня стоит задача синхронизировать библиотеки js и php эти между собой. Проблема в кодировке языков. Что php работает на ascii, а js на utf8.
    Если в php класс добавить функцияю

     
            function uchr ($codes) {
                        if (is_scalar($codes)) $codes= func_get_args();
                        $str= '';
                        foreach ($codes as $code) $str.= html_entity_decode('&#'.$code.';',ENT_NOQUOTES,'UTF-8');
                        return $str;
            }
    

    И модернизировать функцию Global_BlockImplode:

            protected function Global_BlockImplode(&$block, $left, $right){
    		$left =sprintf("%08x", $left );
    		$right=sprintf("%08x", $right);
    
    		$block='';
    
    		$arr=str_split($left, 2);
    		foreach($arr as $hex){
    			$block.=$this->uchr(hexdec($hex));
    		}
    
    		$arr=str_split($right, 2);
    		foreach($arr as $hex){
    			$block.=$this->uchr(hexdec($hex));
    		}
    	}
    

    То можно получить, что php сможет шифровать под js, жаль что научить php это правильно расшифровывать мне пока что не удалось.. Там начинается проблема в LoadData2Blocks, которая вызвана strlen($data), в котором неправильно считается длина блока… да и собирается потом он неправильно….

    Решил поделиться своими наработками..

    1. Дмитрий Амиров Автор

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

      1. ded

        Вина в таблицах символов 2х кодировок… =( И кстати js не пройдет тест гостовый =)

  9. GK

    Ребята объясните для чайника как запустить программу на php? (денвер стоит) А самое главное как запустить весь процесс алгоритма?
    Нужно ли создать отдельную html страницу для этого ?

    1. барибон

      А есть реализация самой Сети Фейстеля на яваскрипте? очень надо ,плиз

  10. Engineer

    Попытался воспользоваться вашей реализацией — шифрует через раз. Длинные тексты вообще не расшифровывает. Странная реакция на пробелы.
    Знакомлюсь с php второй месяц. Рассматриваю ваш код вторую неделю)

    1. Дмитрий Амиров Автор

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

      1. Engineer

        При вводе Shortpass шифрует в Dpischr0HhCXh а расшифровывает в ShortpashXCX00(0hhXh. Короткие слова шифрует на ура. В чем может быть дело? Помимо кода, разумеется, раз вы уверяете в его правильности. Сервер? Кодировка? Вставляю данные в test.php из приложенного архива.

      2. Engineer
        $code_key="qwe2gfdkgdfsfdjgj45skghfjkdskjlk";
        $code_table=array(
        		array(6,12,7,1,5,15,13,8,4,10,9,14,0,3,11,2),
        		array(14,11,4,12,6,13,15,10,2,3,8,1,0,7,5,9),
        		array(13,11,4,1,3,15,5,9,0,10,14,7,6,8,2,12),
        		array(7,13,10,1,0,8,9,15,14,4,6,12,11,2,5,3),
        		array(1,15,13,0,5,7,10,4,9,2,3,14,6,11,8,12),
        		array(4,10,9,2,13,8,0,14,6,11,1,12,7,15,5,3),
        		array(4,11,10,0,7,2,1,13,3,6,8,5,9,12,15,14),
        		array(5,8,1,13,10,3,4,2,14,15,12,7,6,0,9,11),
        	);
        

        С такими данными работает по-стабильнее, но длинный текст все равно некорректно расшифровывает.

  11. Оби-Ван Кеноби

    Привет и спасибо из 2018! Всегда верил, что php может многое — ваша работа тому доказательство.
    Да пребудет с Вами Сила!

Добавить комментарий

Прочли запись? Понравилась? Не стесняйтесь, оставьте, пожалуйста, свой комментарий. Мне очень интересно, что вы думаете об этом. Кстати в комментарии вы можете задать мне любой вопрос. Я обязательно отвечу.

Вы можете оставить коментарий анонимно, для этого можно не указывать Имя и email. Все комментарии проходят модерацию, поэтому ваш комментарий появится не сразу.