I had to add to NEWLISP_DIR/modules/crypto.lsp :
"/usr/lib/x86_64-linux-gnu/libcrypto.so.1.0.0" ; Debian jessie
There is an already existing path, if libssl-dev has been installed, but not without (which I noticed after a fresh OS install).
Now added: http://www.newlisp.org/code/modules/crypto.lsp.html