I think the answers are different for reversible physics versus irreversible physics. Reversible stuff like Newton's laws applied to astronomy should be easy enough over short enough time periods, and there would be some long-solved particle physics that is similar.

In larger systems a model using the reversible physics would be intractable to simulate or record in complete detail.

Now that I think about it, there are two types of irreversibility of models I was thinking of: The ones where information is lost over time, for example differences in temperature being lost once they have evened out, and the ones where apparently random "information" is gained, for example when immeasurably small initial conditions in a chaotic system have a measurably large effect later, or when something outside the modelled system perturbs it.

This basically corresponds to deleting bits or randomising bits.

Another building block for crypto is mixing information up together without losing or gaining bits - this doesn't require irreversibility.

In cryptography, you need to leave enough information in the message so the receiver can decode it with the private key, and in such a way that it can be done efficiently. This constraint doesn't apply to nature.

One thing I wonder about is whether there's a natural equivalent to cryptographic hashes - a class of system where two people who know the initial state will end up with the same final state, but you can't easily compute the initial state from a final state, or find two different initial states that end in the same final state.