You’ll need mkpasswd, on Debian 6 and Ubuntu 12.04 you can install this using:

sudo apt-get install whois

It is pretty weird that it comes with the whois package though…

And then run

mkpasswd -m sha-512