Il problema che descrivi è come Alice sa che la chiave pubblica utilizzata per la firma appartiene effettivamente a Bob. Come hai capito correttamente, non funziona se Alice riceve la chiave pubblica solo insieme al messaggio firmato e non ha modo di verificare che la chiave appartenga a Bob, perché in questo caso Eve potrebbe semplicemente sostituire sia la chiave che la firma con la propria.
Un modo per affrontare il problema è quello di assicurarsi che Alice ottenga la chiave pubblica di Bob in modo affidabile, ad esempio durante alcuni incontri personali. Questo di solito è possibile solo in alcuni casi, quindi invece di avere questa fiducia diretta si può usare un trust derivato, cioè Carl ottiene la chiave da Bob, Alice ottiene la chiave da Carl e Alice si fida di Carl che questa è davvero la chiave di Bob. È possibile implementare tali relazioni di trust con le firme per ottenere una rete di fiducia più scalabile con più parti. Questa è la base per il Web of Trust usato da PGP ma anche per il più centralizzato Public Key Infrastructure utilizzato per S / MIME e anche per HTTPS.
Utilizzando tali reti di fiducia è anche possibile inviare la chiave pubblica insieme al messaggio fintanto che la chiave pubblica è firmata da una parte fidata. Ad esempio, Bob potrebbe chiedere a Carl di firmare la chiave di Bobs utilizzando la chiave Carls e quindi inviare un messaggio ad Alice firmato con questa chiave firmata. Se Alice si fida di Carl, cioè ha una chiave pubblica di Carl, allora Alice non solo può verificare che il messaggio sia stato effettivamente firmato dalla chiave di Bob, ma anche che questa chiave appartenga effettivamente a Bob perché può verificare la firma di Carls.