While a science fiction television show may seem like a strange place to learn about cryptography, an episode of Stargate: Universe hides lessons in plain sight. I know, because I was the backstage professor.
Top image: Just what does Dr. Rush scribble on all those chalkboards, whiteboards, and notebooks throughout Stargate: Universe, "Human"? Credit: MGM
This is not my usual perspective when teaching in this classroom. Image credit: MGM
I am a scientist for fiction, consulting in the entertainment industry to bring real-life science to scripts and sets in a creative-yet-plausible manner. I was scheduled to be at HawaiiCon this weekend until they cancelled, chatting about the science I slipped into Stargate. For those disappointed by the schedule change, anyone craving a Stargate fix, and everyone who loves a bit of clandestine education, this is the cryptography woven throughout the Stargate: Universe episode "Human." If it's been loitering in your To Watch queue for the past several years, this contains a very mild spoiler in the second-to-last paragraph.
The premise of the episode is machiavellian mathematician Dr. Rush trying to crack a code within the context of a memory-flashback. During the io9 recap when the episode first aired in 2010, Meredith confessed, "I loved Rush's crazy scribbles of nonsense and the light code imagery." But it wasn't crazy nonsense scribbles: it was real cryptography with consistent, breakable codes leading up to the big reveal.
Quantum waveforms are too simple to work with; let's add in a bit of alien notation from the Ancients! Image credit: Mika McKinnon
Cryptography is a mathematical tool used to encode messages so even if the message is intercepted, its meaning is preserved as a secret between the sender and recipient. One of the most basic codes is simple numerical substitution: number every letter in the alphabet sequentially so that 1 = A, 2 = B, 3 = C and so on throughout the alphabet to create messages like this: 18 21 19 8 9 19 19 15 3 12 5 22 5 18. Now, this is obviously pretty easy for someone else to figure out, so it isn't very secure.
Brody encrypts all communications to prevent unintended ears hearing the secrets of his latest distilling project. Image credit: MGM
If two people — let's say spaceship Destiny's trusty scientist-duo Adam Brody and Dale Volker — meet in advance or have some other form of secure communication, they can agree on an offset to increase the code's complexity. An offset of +4 where 5 = A, 6 = B, 7 = C... would be readily apparent at the tail end of the alphabet as numbers climbed about 26 (V = 26, W = 27, X = 28...) and numbers 1 through 4 never appear in the coded text. To camouflage the offset, the numbers are wrapped around so the tail end of the alphabet to the beginning of the number sequence: W = 1, X = 2, Y = 3, and Z = 4. Messages encrypted with numerical mapping offset +4 wrapping as necessary looks the same as before, yet maps out to nonsense messages if an interceptor tries basic decryption: 8 9 23 24 13 18 3 22 19 7 15 23!
But these simple codes are still pretty easy to crack: do frequency analysis on how often particular numbers show up and match them to standard letter frequency in the assumed language, or even just brute-force try all possible combinations of linear mapping with the starting at each of the 26 possible letters. Sure, Brody could throw in slang or abbreviations to make cracking the code more challenging, but if he really wants to lock down secure communications, it's time to involve more mathematics.
Encrypt, transmit, decrypt, and the evil interceptor is left without a clue. Stick figures make everything approachable! Image credit: Mika McKinnon
As long as the end coded message can be uniquely transformed back into the original content, the sender and recipient can do all sorts of mathematical tricks to make the code more complicated and difficult to brute force. For example, the Blowfish cipher takes an entry key ("stargate") and a specified modulus (32) in combination with digits of pi as a random number, and uses them in an encryption function. The message is iterated through the encryption function several times, scrambling pesky decryption clues like letter frequency. As long as the key is kept private and reasonably long, the message is rendered into complete gibberish to anyone who lacks the key, yet is instantly decipherable to anyone with it: 07FE00BF6D27F07749C0CCACA324CFD9 D79CD7E5083A7ED2D480F419B40FD8BE AB67C00CADCE2EC98E2A2656F2D89E74
All of this is symmetrical-key encryption: both the sender and the receiver at some point have secure communications where they agree how the messages are going to be encrypted, and then either use the same key to encrypt and decrypt, or else keys that are clearly related so that if you knew one you could infer the other. This has two problems:
- You need to have a secure meeting before you can have secure communication; and
- You need a different pair of keys for every person you want to communicate with.
Valker refuses to decrypt his incoming mail while under the prying eyes of Rush. Image credit: MGM
Returning to Brody and Valker, how does this apply to their hypothetical desire to send secure messages? First, they need to meet, and both get identical keys to a padlock. Later, Brody puts his message in a box, and locks the padlock with his key. He sends the box to Volker, who unlocks the box with his identical key. If they never met securely first to trade keys, they couldn't send messages later.
In 1976, this changed with the invention of asymmetrical public-key decryption. To work with the earlier analogy, Brody and Volker each have their own padlock with their own key. When Brody wants to send a message about the new bar he's set up on Destiny, Volker mails Brody his open, unlocked padlock. Brody uses Volker's lock to close the box and sends it to him: only he can open it with his key. Volker can use Brody open, unlocked padlock to close the box to send him a reply. Stepping away from the analogy and into computer science, anyone can encrypt messages using a public key, which only the recipient's private key can decrypt.
Okay, maybe honours high school math. Image credit: Mika McKinnon
From here, it's time to delve into the dark recesses of half-forgotten high school math classes. Factors are the numbers you multiple together to get a specific number. The factors of 6 are: 1, 2, 3, and 6 because you can multiply 1 x 6 = 6, and 2 x 3 = 6. Prime numbers have a scarcity of factors, where the only factors are one and itself: 3, 7, or 11.The bigger a number is, the harder it is to figure out what the factors are: this is the secret to bringing factoring to cryptography.
If Brody picks a very large number, and multiplies it by another very large number, he produces an incredibly large number. The complexity of determining its factors is disproportionate complex for recalling hazy memories of factoring slotted between half-recollections of lugging book between lockers and classrooms, school spirit pep rallies, and songs now playing on the classic rock station. Yet for Brody, the situation is dead easy as he's the one who picked the factors that created the numbers in the first place! The massive number is used to generate the public key used to encrypt messages, which can be easily decrypted by the private key of the original factors.
Just what was Rush scribbling in those notebooks? That looks like bra-ket notation...
When this episode originally aired, cryptography was in the news with debates about the security Julian Assange's encrypted "insurance file" on wikileaks. The consensus on how to break the 256-bit encryption came down to:
- dedicating the computational power of the entire planet for millions of years to brute-force the problem; or
- physically torture the key out of the human who knows it, gruesomely known as rubber hose cryptanalysis.
Eli contemplates how much of Destiny's computing power could be redirected to brute-force decrypting an intercepted message. Chloe considers a more physical approach. Image credit: MGM
For classical encryption, not much has changed since then: encryption will protect your data from casual or even dedicated decryption attempts, unless you're faced with physical or legal coercion. It's a major component of the steps you can take to reduce internet surveillance, and you can explore it right now with GPG (or its commercial equivalent, PGP). Just make sure you don't lose your key!
Encryption security depends on factoring the large number (say, a number N digits long) taking a very, very long time. The fastest factoring technique available on a classical computer is the Number Field Sieve. This is formally stated as: O(e1.9 (log N)1/3 (log log N)2/3), where Big O notation is shorthand for describing the worst-case scenario for how long it will take to run an algorithm.
Wait a minute, those variables aren't from an Earthly alphabet! Is this going to be on the exam? Image credit: MGM
This all starts going haywire with quantum computing, where suddenly problems like factoring huge numbers are theoretically feasible. During Rush's flashbacks, the scientist faces a classroom of his graduate students. He's mid-lecture discussing Shor's Algorithm, a technique for factoring extremely large numbers using quantum computers in a fraction of the time: O((log N)3).
In technical terms, instead of the time needed to factor a large number increasing in exponential time, it would increase in polynomial time. In human terms, it's a fast shortcut that if it works in practice, will render the factorization technique of encryption vulnerable. Since the episode aired, another technique, adiabatic quantum computation, or AQC, has shown promise at evolving the Hamiltonian in a liquid-crystal nuclear magnetic resonance system to factor large numbers. It will be an interesting future of cryptography when large integers can be factored quickly, but that time is not now.
"Tech support? Something is wrong with the lighting in this lecture hall. My grad students are coated in glowing equations, and they're still entranced by academia..." Image credit: MGM
Returning to Rush and his endless scribbling with chalk, pencils, and white board markers, just what is he getting into with all those numbers, symbols, and equations? Cryptography. As this whole flashback is a symbolic visualization of how he's approaching the core problem of understanding Destiny's coding, his attempts to build a functional mental framework are expressed as various decryption techniques.
The first rule of solving puzzles is to get really good at writing while walking. Image credit: MGM
Exactly what type of technique Rush attempts is tied to what's going on in the rest of the fashback. Violin lesson? He tries using the frequencies of musical notes as a decryption key. Struggling with the inevitability of his wife's death? He's delving into quantum entanglement and waveform collapse with painfully tidy handwriting. Getting angry? Time for frustrated iterations of brute-force attacks.
The first act of the episode features mostly standard terrestrial symbols and mathematics; it's chock full of classic approaches and patterns familiar to cryptography junkies. But Destiny isn't a terrestrial ship, and this isn't a pure memory of Earth. The alien symbols from the starship work their way into the endless equations, with more and more creeping in as the episode progresses. Which concepts those symbols represent is left as an exercise to the viewer: their usage is consistent throughout every episode of the show.
You know what this scene needs? More math.
(Added for clarification:) Actual plot-relevant messages are embedded in the codes Rush is trying to break throughout the episode. While the audience gets to explicitly see his big breakthrough moment at the end — a single number — the rest are left unsolved. If you like puzzles, see if you can identify which bits are breakable-codes (instead of conceptual abstract techniques, like the Shor's algorithm lecture notes), and give decrypting them a whirl. The encoded messages rely on security through obscurity: finding them should be harder than cracking them. Get in touch with me here, on Twitter, or at a convention if you think you have it figured out!
An earlier version of this post originally appeared on SpaceMika. You may also be interested in the atmospheric science of Stargate: Atlantis's "Brain Storm." For more on the history of cryptography along with practical techniques and at-home cryptography games, check out Neal Stephenson's Cryptonomicon, or this story from the io9 archives.