Загадка: у меня 3 головы, 10 рук и 4 ноги. Кто я?
Ответ: 3,14здун

+--------------------------------------------------------------------------------------------------------------------------[release: 01.03.05]----+
|
|
|
|
|
|
|
  _|_|  _|      _|  _|      _|_|      _|_|    _|_|_|  _|_|_|  _|    _|      _|  _|    _|_|_|
_|      _|          _|      _|  _|    _|  _|  _|  _|  _|  _|  _|_|  _|    _|_|_|_|_|  _|  _|
_|      _|_|_|  _|  _|      _|  _|    _|_|    _|  _|  _|_|    _|  _|_|      _|  _|    _|  _|
_|      _|  _|  _|  _|      _|  _|    _|      _|  _|  _|  _|  _|   |_|    _|_|_|_|_|  _|  _|
  _|_|  _|  _|  _|  _|_|_|  _|_|      _|      _|_|_|  _|  _|  _|    _|      _|  _|    _|_|_|
|
|
|
|
|
|
|
+-------------------------------------------------------------------------------------------------------------------------------------------------------+
+--------------------------------------------------------[0x08: Crypt(3). Реализация]-------------------------------------------------------+
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|

crypt(3): Принцип

Сразу скажу, что не стоит кричать, мол подобной информации полно в интернете. На самом деле (Google, Yahoo, Altavista, Yandex, Rambler не дадут соврать), информации о принципе работы никсовой функции crypt практически нет. Если брать рунет, то тут все ограничивается косвенными намеками на программерских форумах и архиве FIDO. Рассматривать мы будем "старый добрый" DES, несмотря на то, что от его использования уже многие отказались.


1. Кратко о DES

Если что будет непонятного по этой части, огромная просьба _читать_ FIPS-46-3 в оригинале или переводе, благо этого добра навалом.
Итак, DES (точнее, DEA - алгоритм, а не DES - стандарт) выполняет операции над блоком данных размером 64 бит. Также необходимо задать ключ того же размера. Во входных данных сначала производится перестановка разрядов в соответствии с таблицей IP. Затем 16 раз выполняется следующая последовательность операций: данные делятся на 2 равные части; левая часть и i-е преобразование ключа (i-номер итерации, 1..16) обрабатываются функцией f; затем результат функции f поразрядно складывается по модулю 2 (xor) с правой частью и становится правой частью на следующую итерацию; левой частью на следующую итерацию становится правая часть текущей итерации. После этого производится инверсная перестановка разрядов по таблице FP (IP^-1). И voila!
Дальше нам понадобится знать внутреннее устройство функции f. Данные (та самая левая часть) расширяются до 48 бит с помощью вектора E; расширенные данные и i-е преобразование ключа xor'ируются; полученные 48 бит пропускаются через 8 S-матриц (результат будет иметь размер 32 бита); и, уже привычная, перестановка разрядов. В принципе, этого достаточно знать, чтобы понять, в чем разница между DEA и crypt().


2. Сам crypt(pass,salt)

Во многих мануалах написано, что хэш DES является всего лишь применением DEA к конкатенации строк salt и pass. На самом деле, все немного иначе. По значению salt изменяется вектор E, который используется в функции f. Сам процесс изменения проще привести в виде фрагмента кода. особенность реализации состоит в том, что вместо обработки битового поля производится обработка массива из 64 значений, что гораздо более удобно для восприятия.
/*begin code*/
    for(i = 0; i < 2; i++)
    {
        /* store salt at beginning of results */
        c = *salt++;
        iobuf[i] = c;

        if(c > 'Z')
            c -= 6;

        if(c > '9')
            c -= 7;

        c -= '.';

        /* use salt to effect the E-bit selection */
        for(j = 0; j < 6; j++)
        {
            if((c >> j) & 01)
            {
                temp = E[6 * i + j];
                E[6 * i +j] = E[6 * i + j + 24];
                E[6 * i + j + 24] = temp;
            }
        }
    }

/*end code*/
Пароль становится ключом, а зашифровке подвергается пустой информационный блок (64 бита, равных 0). Причем шифрование производится итеративно, 25 раз, т.е. к результату предыдущей итерации опять применяется шифрование (всего 25 вызовов des_encrypt).

Далее формируется стандартный 13-символьный вывод. Причем, правила формирования внешне напоминают base64 с измененным алфавитом. Так получаются 11 символов хеша, а перед ними дописывается salt.

/files/crypt3.c - исходник (автор: Michael Dipperstein) с независимой от операционной системы реализацией функции crypt.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+-----[content]-----------------------------------------------------------------------------------------------------------------------[mail us]-----+