undefined reference to...

А посмотреть в /lib? (Увидишь там libcrypt.so).

По поводу того, почему не достаточно простого #include...
#include - это простая директива прекомпилятора, которая используется для того, чтобы прекомпилятор подготовил ссылки на заголовки функций и структуры для компилятора. Компилятор же, на основании этих ссылок, обращается в указанный .h файл и компилирует упомянутые заголовки функций и структуры в объектный код. Но, помимо заголовка функции еще нужно само тело функции для компиляции и это тело находится в самой библиотеке, которую нужно подключать. И это тело функции линкуется компоновциком в конечный (исполнимый или библиотечный файл) из подключенной библиотеки при статической линковке или указывается ссылка на расшаренный объект (.so) при динамической линковке.
Для того, чтобы узнать, в какой .so или .a находится тело функции надо сделать:
find /lib_directory/* | grep func_name ,
где
lib_directory - директория, где лежат библиотеки (обычно это /lib и /usr/lib), и func_name - имя функции, которую необходимо найти.
После этого на экране появятся имена файлов библиотек, где лежат данные функции...

Большое спасибо!

find найдет не имя функции, а имя либы. Делайте
nm --print-file-name `find /lib_dir/*` 2>&1 |grep func_name