Public-key authenticated encryption: crypto_box

where is the key exchange algorithm?

The crypto_box is simply crypto_box_curve25519xsalsa20poly1305 and it has two parts;

Part 1: Packet independent pre-computation;

• Party $A$ has 32-byte secret key $sk_A$ and public key $pk_A$ where $pk_A = [sk_A]G$

• Party $B$ has 32-byte secret key $sk_B$ and public key $pk_B$ where $pk_B = [sk_B]G$ and $G$ is the base point of X25519.

  here $[a]G$ is scalar multiplication and it means add $G$ to itself $a$-times.

• Party $A$ uses $sk_A$ and $pk_B$ to derive a key using X25519;

  $$k = Hash(x([sk_A]pk_B))$$ note that $pk_B$ is a point on the curve and X25519 uses only the $x$ coordinate of the points for ECDH ( noted wiht $x(\cdot)$.

As you can see, once $A$ can get the public key of $B$ the key $k$ can be constructed immediately and it is similar for $B$, too. This is the Elliptic Curve Diffie-Hellman Key Exchange (ECDH).

Part 2: per-packet computation

• $A$ selects 24-byte nonce $n$ ( must be unique ) and should never reoccur again while communicating with $B$. The 24-byte nonce is safe to generate randomly.
• $A$ expand the key $k$ with the nonce into a keystream with xsalsa20
• The message is encrypted with the stream (just x-or) where the first 32-byte is reserved.
• The first 32-byte is used to authenticate the encrypted message with Poly1305.

why do they need to key exchange algorithm

If they don't have a key exchange mechanism then they need an symmetric key distribution mechanism that was the burden of the symmetric encryption before the public key encryption is invented.

The public keys need verification. Sometimes they have been used as TOFU (Trust on the First Usage) and then verified with some mechanisms like Signal does. In some more secure communications first, verify the public keys.

For more details read

• Cryptography in NaCl