I sistemi crittografici a chiave pubblica possono essere utilizzati anche per risolvere problemi inerenti l'autenticazione degli utenti, ovvero per garantire che chi trasmette e chi riceve siano esattamente chi dichiarano di essere. Questo tipo di metodica è alla base della firma digitale e dei certificati.
Se A vuole inviare un messaggio a B e vuole provare a B che il messaggio è effettivamente suo (di A), allora A può criptarlo con la sua chiave privata. B riceverà il messaggio e tenterà di decriptarlo con la chiave pubblica di A. Se l'operazione riesce, allora il messaggio è effettivamente di A, altrimenti B si accorge dell'abuso di identità e può segnalarlo ad A.
Un algoritmo molto diffuso di codifica a chiave pubblica, basato sulla scomposizione in fattori primi di un numero intero, è RSA (dal nome dei suoi creatori Rivest, Shamir e Adleman) reso noto nel 1978.