29 March 2006

Quasars as crypto key

In cryptography, it's important to have a key that's uncrackable. Any simple pattern can be cracked - simple monoalphabetic cyphers (one-for-one substitution, such as A=B, B=Q, C=F, etc.) are even used as puzzles in some newspapers, in which the reader is tasked with "translating" a quote from a famous book into normal English (anyone remember the name of these types of puzzles?). A polyalphabetic cypher (A=B if even, A=G if odd, etc.) can also be cracked. More complex patterns as well - other systems use matrix multiplication, large prime numbers, or computer-generated "random numbers." The problem with the latter is that the numbers are never truly random, so after enough digits in the message, it can be cracked.

But apparently quasars have unpredictable variabilities in (radio) brightness, and therefore could be ideal keys. If, of course, the person at the other end knew which quasar you were using, what time you started looking at it, and had a decent radio telescope...

6 comments:

Thomas Siefert said...

Really simple.....

zandperl said...

Actually, I wonder how much of that you can do with just a satellite dish and a PC. I'm not the sort who's inclined to do that sorta thing, but I bet it can be done.

Joshua O'Madadhain said...

If, of course, the person at the other end knew which quasar you were using, what time you started looking at it, and had a decent radio telescope...

I think that the proposal was to use them to create one-time pads, which actually depend for their security on the notion that no one else can generate them.

IANAA (i.e., I Am Not An Astronomer), but I'd also guess that even if you knew down to the picosecond when someone started recording their quasar data, you still wouldn't get the same bitstream unless you were in the same place. I don't know how fast quasar radio brightness varies, but I'd hazard a guess that atmospheric interference would play a role, and would differ enough to ruin the repeatability across a fairly short distance.

As a side note, I'm pretty sure that random noise derived from natural phenomena has been used for the creation of one-time pads for some time now. I don't know if quasar randomness is any better for this purpose or not.

zandperl said...

Joshua -
Good thinking, but your guess about atmospheric interference is not the case. If it were, then no astronomer would ever be able to accurately determine the brightness of anything. While the atmosphere does cause interference, it can be corrected for; the simplest way is to compare the object in question to a nearby object of known brightness.

I think that the proposal was to use them to create one-time pads, which actually depend for their security on the notion that no one else can generate them.

Except the person receiving the message. Traditional one-time pads I believe the key is separately sent to or agreed upon beforehand by the recipient; in this case the recipient would either be sent or agree to (a) which quasar, and (b) what time.

I don't know what actually causes quasar brightness fluctuations (not my sub-field), so I can't say how random it really is. :-P

Thanks for your thoughts!

Joshua O'Madadhain said...

your guess about atmospheric interference is not the case. If it were, then no astronomer would ever be able to accurately determine the brightness of anything. While the atmosphere does cause interference, it can be corrected for; the simplest way is to compare the object in question to a nearby object of known brightness.

I don't think that I expressed myself very well. For the sake of argument, let's say that you can measure the brightness of a quasar (or anything else) _reliably_ out to 2 decimal places. Past that point, then, I would assume that random noise (from factors such as atmospheric interference and EM interference) would, by definition of "reliable", start to dominate the random noise that you get from the quasar itself. So the question is whether the one-time pad would use only the quasar noise, or go out a few more decimal places.

Regardless, one-time pads (done right) depend on getting _all_ the bits right, so even slight variations will mean that your message is garbled (and statistically, of course, "reliable" just means that errors are rare, not nonexistent).

one-time pads, which actually depend for their security on the notion that no one else can generate them.

Except the person receiving the message. Traditional one-time pads I believe the key is separately sent to or agreed upon beforehand by the recipient


"Sent to", is my understanding. Algorithmically generated (or generated by anything else that involves a repeatable measurement) one-time pads are problematic from a security standpoint.

Anyway, I could still be off-base here, but I just wanted to clarify what I meant.

zandperl said...

Good point, that it can't be determined perfectly. I guess how many digits to use is another thing they'd have to agree upon. :-P