gcc es parte de build-essential paquete, que debe instalar antes que nada:
sudo apt-get install build-essential
ACTUALIZACIÓN: Siguiendo la sugerencia de @bosnjak, es posible que también deba instalar las herramientas de desarrollo de openssl:
sudo apt-get install libssl-dev
