| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
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.
|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |