A chave é (geralmente) gravada nos cabeçalhos das mensagens. Mas esse email (criptografado) não contém nenhuma informação sobre o remetente, se não estiver assinado. Vamos analisar o que está contido nas mensagens do OpenPGP.
Decompondo uma mensagem criptografada do OpenPGP
Você pode ver isso se listar os pacotes contidos em uma mensagem criptografada:
$ echo foo | gpg --encrypt --recipient 0xa4ff2279 | gpg --list-packets
A saída começa com os cabeçalhos "publicamente" visíveis e não criptografados, que contêm a subchave para a qual a mensagem é criptografada:
:pubkey enc packet: version 3, algo 1, keyid CC73B287A4388025
data: [4092 bits]
Após inserir a senha, o GnuPG também imprimirá os pacotes restantes:
:encrypted data packet:
length: 63
mdc_method: 2
gpg: encrypted with 4096-bit RSA key, ID A4388025, created 2014-03-26
"Jens Erat (born 1988-01-19 in Stuttgart, Germany)"
:compressed packet: algo=2
:literal data packet:
mode b (62), created 1402861918, name="",
raw data: 4 bytes
Decompondo uma mensagem assinada do OpenPGP
Uma mensagem signed contém o ID da chave de assinatura (sub) do remetente, veja a linha :signature packet
(quarto pacote).
$ echo foo | gpg --sign | gpg --list-packets
(o GnuPG pede senha, para assinar)
:compressed packet: algo=1
:onepass_sig packet: keyid 8E78E44DFB1B55E9
version 3, sigclass 0x00, digest 2, pubkey 1, last=1
:literal data packet:
mode b (62), created 1402862406, name="",
raw data: 4 bytes
:signature packet: algo 1, keyid 8E78E44DFB1B55E9
version 4, created 1402862406, md5len 0, sigclass 0x00
digest algo 2, begin of digest 9a d2
hashed subpkt 2 len 4 (sig created 2014-06-15)
subpkt 16 len 8 (issuer key ID 8E78E44DFB1B55E9)
data: [4095 bits]
Uma mensagem criptografada do OpenPGP também pode ser assinada. Estou deixando de compor os comandos para verificar isso como exercício para o leitor interessado.
Obtendo as chaves públicas
Usando o ID de chave obtido da mensagem assinado , pode-se buscar a chave nos servidores de chaves. A maioria dos clientes de e-mail (plug-ins) fará isso automaticamente para você:
$ gpg --recv-keys 0x8E78E44DFB1B55E9
gpg: requesting key FB1B55E9 from hkp server pool.sks-keyservers.net
gpg: key A4FF2279: "Jens Erat (born 1988-01-19 in Stuttgart, Germany)" not changed
gpg: Total number processed: 1
gpg: unchanged: 1
Se a mensagem não estiver assinada, você (ou seu cliente OpenPGP) poderá pesquisar os servidores de chave pelo endereço de e-mail do outro. O resultado é o mesmo, você ainda não pode ter certeza sobre a validade dessa chave.