How come this isnt a problem with modern cryptography? What did we invent?

You add a random number to the encryption key, and also send that random number (seed) as part of the message.

Boiled down to the very essence modern cryptography is: Using a secret seed plus a public seed, generate a long random number (of the same length as the message), then XOR that number with the message.

The hard part is generating that random number in such a way that you can not reverse the process and reclaim the secret seed.

Lookup "initialization vector" for more.

In short: cipher modes, IVs, nonces, and random padding.