Sí, primero debe firmar su mensaje (con su clave privada) y luego cifrarlo con la clave pública de Bob. De esta manera solo él puede descifrar el mensaje con su clave privada y luego verificar la firma con su clave pública para saber realmente que el mensaje era suyo.
Sobre la potencia de cálculo. El cifrado GPG, que es el sistema más extendido para cifrar y firmar mensajes utilizando el cifrado de clave pública, en realidad utiliza el cifrado simétrico (es decir, AES) para los mensajes. En este sentido, lo que realmente hace es generar una clave aleatoria para el cifrado simétrico, cifrar el mensaje con esa clave y luego cifrar esa clave con la clave pública del receptor. Para la firma, GPG calcula un hash del mensaje (por ejemplo, SHA256) y cifra ese resultado con la clave privada del remitente.
Esto resulta ser mucho más eficaz para mensajes grandes, ya que el cifrado simétrico y los cálculos de hash son bastante rápidos y, en algunos casos como AES, están optimizados para realizarse en hardware en lugar de en software. Además, este mecanismo permite que un mensaje se entregue a múltiples partes, para esto, la clave simétrica debe cifrarse una vez para cada receptor, pero el mensaje y la firma permanecen igual