Any cryptographic protocol must have:
- Some (public) algorithm which explains what to do. (Depending on secret algorithms would be called "security by obscurity" and can usually be discarded as inherently insecure.)
- Some secret information (i.e., one or several keys).
To be of any practical use, the key space needs to be large enough to make brute force attacks (especially when knowing the complete algorithm) infeasible.
It is important to keep in mind that when thinking about a cryptosystem like this, the problem of "losing the secret" is out of scope. I.e., the secret is supposed to be really secret, you can and must assume that the attacker does not know the secret before starting his attack.
The arguably most secure and at the same time trivial algorithm would be the usage of a one-time-pad; i.e. the secret is a (possibly very large) integer; and the algorithm simply is to XOR the secret and the plaintext for encryption, and to XOR the secret and the ciphertext for decryption.
This could be used thusly with celestial objects:
- The key is the ID of a star.
- The algorithm:
- There is a constant-bandwith stream of ciphertext being transmitted all the time, in fixed-size blocks. Assume that this transfer works reasonably well, i.e. no significant pauses, and roughly known latency.
- Both the sender and receiver constantly monitor the star and draw random bits from it in some form or fashion. I do not know if there are any practical measurements that actually work today, but one could imagine that the brightness of certain stars "flickers" enough to draw something from it.
- The sender keeps XORing their next plaintext block, checksummed and padded to the required length, with the current batch of realtime random bits (i.e., one-time-pad) and sends it.
- The receiver decodes this using the same XOR operation. To be a bit more safe against timing issues, it can keep the last N one-time-pads around and just try to decode with all of them; with the checksum and considering how fast the XOR is, it is feasible to have a sliding window of pads to find the correct one.
The strength of the algorithm depends on whether there are enough possible stars to pick from, and that the measurement is hard enough so that it is infeasible for an attacker to scan very many stars at a time.
There you have a basic idea of how you could use celestial objects in cryptography. At the end of the day it boils down to generating truly random bits, and you don't even need the time if you are able to have a constant connection. You can refine this as necessary; i.e. you could avoid having to constantly send ciphertext if you have some kind of shared time source (and it only needs to be roughly in sync, depending on how much buffer space you will want to use for your bits). There are plenty of practical problems to solve (e.g. how to generate the bits reproducible in the first place, avoiding phase shifting due to minute divergences and thus), but not unsolvable in principle.