Can we develop a working asymmetric crypto message protocol without an asymmetric encryption algorithm? Our crypto libraries have:


DSA (4096, 512)
DH (4096)
AES (256)
SHA (512)


Let us say these are implemented directly in hardware so that trying to pull the pieces out is not possible, and the CPU isn't really fast enough to implement crypto itself.

Can we develop a protocol that permits us to exchange public keys, and at some later date send messages by courier or some means that does not assume live communication. That is, DH won't work directly because message round-trip time is intolerably long.

This question is far more interesting on a theoretical basis than any practical means by which I might have gotten here.
Use DLIES, which is essentially Diffie-Hellman with an ephemeral sender key. Assuming you know the receiver's public key, that will cost no extra round trips.

The sender does:

(eph_sender_private, eph_sender_public) = Generate_Key_Pair()
shared_key = SHA-512(Diffie-Hellman(receiver_public, eph_sender_private))
ciphertext = Encrypt(shared_key, message)
encrypted_message = (eph_sender_public, ciphertext)


The receiver does:

(eph_sender_public, ciphertext) = encrypted_message
shared_key = SHA-512(Diffie-Hellman(eph_sender_public, receiver_private))
message = Decrypt(shared_key, ciphertext)


Where Encrypt is authenticated encryption build from AES and SHA-512. For example you could follow the RFC Draft Authenticated Encryption with AES-CBC and HMAC-SHA which includes test vectors to minimize the risk of your messing it up.

If you feel fancy, replace the simply hashing in the shared key derivation by a proper KDF, such as HKDF-SHA-512.

To authenticate the sender, sign the message using a long term DSA key, which should be distinct from the long term DH key.