O GnuPG é pré-instalado no Debian (e para assumir, todos os seus lançamentos descendentes). O GnuPG é uma parte muito importante do sistema operacional, pois é usado para verificar as listas de repositórios e fontes de pacotes.
Ele já deve estar disponível como gpg (GnuPG 1, versão "clássica") ou gpg2 (GnuPG 2.0 ou 2.1, versões "estáveis" ou "modernas"). Se você tiver apenas um desses e quiser instalar o outro, os pacotes serão denominados gnupg e gnupg2 . Se você não vê-los, talvez seja necessário executar apt-get update antes.