Not surprising that they originate from an RSA paper on public key cryptography. This site has way more than the early history, though, explaining how the set of notional actors has been expanded and adopted in other example narratives.
h/t Boing Boing
A History of Alice and Bob, by Quinn DuPont and Alana Cattapan (created 2017).
Source: Alice and Bob: The World’s Most Famous Cryptographic Couple