I've been wrestling in my head about which parts are physics and which parts are mathematics.

Especially from an epistemological perspective: Can we know, for example, that encryption becomes easier / cheaper more quickly than brute-force decryption because, in some sense, the physics of the universe have it that way?