Un problema estructural con el uso de la criptografía de clave simétrica para las firmas digitales es que todos tienen que estar de acuerdo en confiar en el Gran Hermano. Es más, el Gran Hermano puede leer todos los mensajes firmados. Los candidatos más lógicos para operar el servidor del Gran Hermano son: el gobierno, los bancos, los contadores y los abogados. Por desgracia, ninguna de estas organizaciones inspira una total confianza a todos los ciudadanos. Por tanto, sería bueno si la firma de documentos no requiriera una autoridad de confianza. Por fortuna, la criptografía de clave pública puede hacer una contribución importante en esta área. Vamos a suponer que los algoritmos de encriptación y desencriptación de clave pública tienen la propiedad de que E(D (P)) =P, además (desde luego) de la propiedad normal de que D (E(P)) =P. (RSA tiene esta propiedad, por lo que el supuesto es razonable.) Suponiendo que éste sea el caso, Alice puede enviar un mensaje de texto plano firmado (P) a Bob al transmitir EB(DA(P)). Observe bien que Alice conoce su propia clave (privada), DA, así como la clave pública de Bob, EB, por lo que Alice puede elaborar este mensaje. Para ver cómo funciona la propiedad de firma, suponga que más tarde Alice niega haber enviado el mensaje P a Bob. Cuando el caso llega a la corte, Bob puede presentar tanto P como DA(P). El juez puede comprobar fácilmente que Bob tiene un mensaje válido encriptado por DA con sólo aplicarle EA. Puesto que Bob no conoce la clave privada de Alice, la única forma en que Bob pudo haber adquirido un mensaje encriptado por esa clave sería que Alice en efecto lo hubiera enviado. Mientras esté en la cárcel por perjurio y fraude, Alice tendrá tiempo suficiente para diseñar algoritmos de clave pública nuevos e interesantes.Aunque el uso de la criptografía de clave pública para las firmas digitales es un esquema elegante, hay problemas relacionados con el entorno en el que operan más que con el algoritmo básico. Por una parte, Bob puede demostrar que Alice envió un mensaje siempre y cuando DA permanezca en secreto. Si Alice divulga su clave secreta, el argumento ya no es válido, puesto que cualquiera pudo haber enviado el mensaje, incluido el mismo Bob.