No site do cartão do cidadão não existe (à data deste artigo)  o pacote deb para esta versão (12.04) mas sim para a versão 11 do Ubuntu, que dá erro ao tentar instala-lo e por isso resolvi alterar o ficheiro. Podem puxa-lo aqui (64 bits).
Para funcionar corretamente também têm de instalar o pacote libssl0.9.8:

sudo apt-get install libssl0.9.8