 Tech


Tech
The gadgets, platforms, and software that make your digital life possible. if it bleeps, clicks or blinks, you’ll find it here.

Categories


Latest
 Facebook pushes back against moderators complaining about ‘Big Brother’ environment Saturday 12:46 PM
 Twitter hid post from an account linked to Iran’s Supreme Leader Saturday 10:17 AM
 Bug lets Twitter save your DMs—even after you delete them Friday 7:21 PM
 New website will endlessly generate fake faces thanks to AI Friday 3:41 PM
 FCC looks to tackle robocalls and spoofed texts Friday 2:57 PM



 Internet Culture


Internet Culture
There’s a community for everyone online.

Categories


Latest
 Man fakes getting stood up at Outback Steakhouse Friday 3:03 PM
 Trump Jr’s meme about his dad’s border wall doesn’t get how Congress works Friday 11:44 AM
 Dudes swallow AirPods in YouTube challenge video no one asked for Thursday 8:22 PM
 People are roasting this woman’s tips for avoiding a ‘manrepeller’ apartment Thursday 3:59 PM
 Valentine’s Day challenge dares you to message your crush Wednesday 2:29 PM



 Streaming


Streaming
You’ve cut the cord—now what?

Categories


Latest
 7yearold YouTuber to get his own show on Nickelodeon Saturday 5:30 PM
 How to stream Leo Santa Cruz vs. Rafael Rivera for free Saturday 8:00 AM
 ‘Larry Charles’ Dangerous World of Comedy’ finds the balance between tragedy and comedy Saturday 7:30 AM
 How to stream Michael ‘Venom’ Page vs. Paul Daley for free Saturday 7:00 AM
 How to watch the NBA Dunk Contest 2019 online for free Saturday 6:50 AM



 IRL


IRL
Where your off and online identities collide.

Categories


Latest
 ‘Hipster’ jobs are trending, and Indeed says the market is booming Saturday 3:33 PM
 Writers want this book canceled for misgendering its protagonist Friday 12:15 PM
 FBI reportedly looking into Ryan Adams’ communications with underage girl Friday 11:25 AM
 Chrissy Teigen throws shade at Logan PaulKaitlin Bennett pairing Friday 10:48 AM
 Women sue border patrol for detaining them for speaking Spanish Friday 10:20 AM



 Social


Social
If it happens online, it’s here.

Categories


Latest
 7yearold YouTuber to get his own show on Nickelodeon Saturday 5:30 PM
 ‘Hipster’ jobs are trending, and Indeed says the market is booming Saturday 3:33 PM
 Trump meme removed after copyright complaint Saturday 2:15 PM
 Facebook pushes back against moderators complaining about ‘Big Brother’ environment Saturday 12:46 PM
 Twitter hid post from an account linked to Iran’s Supreme Leader Saturday 10:17 AM



 Bazaar


Bazaar
The Bazaar specializes in the stuff you don’t actually need…but you really, really want.

Categories


Latest
 Play all your NES games in high def with the Hyperkin RetroN HD Tuesday 8:39 AM
 The Introvert Activity Book is perfect for those who find solace in alone time Monday 11:30 AM
 Essential tips and tools to make your sex life deeper Monday 9:29 AM
 How to watch your favorite classic ’90s anime online Thursday 11:53 AM
 17 Galentine’s Day gifts to give your favorite ladies Wednesday 10:33 AM



 More
 Search
See all Editor's Picks →
See all Popular →
Represented by Complex Media, Inc. for advertising sales.
Privacy Policy Terms & Conditions Ethics
Latest
 7yearold YouTuber to get his own show on Nickelodeon Saturday 5:30 PM
 ‘Hipster’ jobs are trending, and Indeed says the market is booming Saturday 3:33 PM
 Trump meme removed after copyright complaint Saturday 2:15 PM
 Facebook pushes back against moderators complaining about ‘Big Brother’ environment Saturday 12:46 PM
 Twitter hid post from an account linked to Iran’s Supreme Leader Saturday 10:17 AM
 How to stream Leo Santa Cruz vs. Rafael Rivera for free Saturday 8:00 AM
 ‘Larry Charles’ Dangerous World of Comedy’ finds the balance between tragedy and comedy Saturday 7:30 AM
 How to stream Michael ‘Venom’ Page vs. Paul Daley for free Saturday 7:00 AM
 How to watch the NBA Dunk Contest 2019 online for free Saturday 6:50 AM
 The best new TV shows to stream this weekend Saturday 6:00 AM
 Bug lets Twitter save your DMs—even after you delete them Friday 7:21 PM
 Guy mansplains song to Japanese Breakfast, the female artist who wrote the song Friday 6:38 PM
 Ann Coulter’s Twitter bio links to a vulgar parody account Friday 5:22 PM
 Popular YouTube music channel gets income yanked for ‘repetitious’ content Friday 4:14 PM
 New website will endlessly generate fake faces thanks to AI Friday 3:41 PM
The latest leak from Edward Snowden seems to suggest the NSA secretly made a major math breakthrough.
In a recent story about the U.S. National Security Agency’s controversial Internet surveillance operations, the New York Times reported that “the agency has circumvented or cracked much of the encryption, or digital scrambling, that guards global commerce and banking systems.”
The bolding is mine, because if in fact the agency did crack the encryption schemes used for bank transactions (the Times is somewhat unclear on that point), then in doing so it may have solved a math problem that has long puzzled cryptographers and number theorists alike.
The problem in question is that of integer factorization. It has been shown that every integer (e.g. 1, 2, 3, 4, 5…) can be written as the product of prime numbers. To review, a number is said to be prime if it is divisible only by itself and 1. (The first 10 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.)
That means if we pick a number, say 50, we should be able to write it as a product of primes: In this case, it would be 5 x 5 x 2. For small numbers like 50, determining prime factors is within reach of any middle schooler. However, take a sufficiently large number—one that is hundreds of digits long—and the problem quickly becomes intractable, not only for humans but even for modern computers.
To date, there is no known shortcut to quickly factor large integers into primes. It has never been proven that no such shortcut exists. We’ve just never found one.
If the unfactorable nature of these large integers doesn’t interest you, consider that it has been the reason many of your most personal messages are kept private as they move across the Internet.
But the Times report about how the NSA penetrated banking encryption seems to suggest the agency may have cracked the problem. Here’s why (and this is going to take some explaining):
In the most basic sense, encryption works like this: Say Alice wants to send Bob a piece of sensitive information. Her computer first asks his to generate two keys: a “public key” and a “private key.” The public key can encrypt the message, and the private key can decrypt it. (Note that the public key cannot decrypt the messages after encrypting it.)
So Bob’s computer creates the two keys and sends Alice the public key. He keeps the private key for himself. Alice then encrypts her message with the public key and sends it to Bob’s computer. Once Bob has the message, he uses his private key (which he has shared with no one) to decipher the encryption.
So, the essence of an encryption algorithm is to create a public key and a private key such that only the private key can decode the messages.
One popular technique is the RSA algorithm, which gets its name from the three students who invented it. Here is how the algorithm accomplishes the task of generating a public and private key.
First, the public key:
 The algorithm randomly selects two prime numbers, let’s call them p and q.
 Next, the algorithm computes p x q. Call that result n. (So, n = p x q).
 Then, it calculates a number z, where z = (p – 1)(q – 1).
 Finally, the algorithm picks an odd number k such that z is larger than k and z is not divisible by k. (For example, if z were 20, we could pick k to be 11, since 20 is not divisible by 11.)
 The public key–the one Alice sends to Bob–is the two numbers n and k.
Now for the private key:

We need to find a number, call it j, such that (k x j) divided by z will give a number with a remainder of 1. Note, that it doesn’t matter what number we choose, as long as it has a remainder of 1.
Note here that “remainder” refers to the remainders computed in long division. So, for example, if you took 30 and divided it by 9 using long division you would get 3 with a remainder of 3, because 9 goes into 30 3 times, leaving a remainder of 3.
Here’s a concrete example: If, say, k = 7 and z = 20, then we need to pick a number j such that (7 x j) / 20 = some number with a remainder of 1. So, j could be 3 because (7 x 3) / 20 = 21/20 = 1 with a remainder of 1. Or we could choose j to be 23, since (7 x 23) / 20 = (161 / 20) = 8 with a remainder of 1. Whatever j we chose, that along with n becomes our private key.
So, returning to the Alice example: Alice has a confidential message she wants to give Bob. Let’s call it M. Before sending it, she asks Bob to generate a public and private key. Using the RSA algorithm, Bob’s computer generates the public key (n,k) and the private is (n,j). Bob then sends Alice the public key and she encrypts her message this way:
 First she computes (M^k) / n.
 The remainder of the resulting number is her encrypted message E. She sends E to Bob. We won’t get into how exactly Bob’s private key decrypts the message because his key would never be intercepted by a hacker. The important point here is why a hacker can’t decrypt Alice’s message with the public key–that is, the numbers (n,k).
Imagine you intercepted the public key and the encrypted message. So, you have k, n and E. The question is, can you solve for M?
(M^k) / n = some number with a remainder of E
In short, the problem is that the encrypted message E is the remainder of some number—but you don’t know which one. When you are dealing with huge numbers, as RSA does, there are a ton of possibilities for M that, plugged into that equation, would have a remainer of E.
(If that doesn’t make sense, consider the two long division calculations 10 / 9 and 19 / 9. The first yields 1 with a remainder of 1. The second gives you 2 with a remainder of 1. So, you can’t definitely determine what number divided by 9 was used to calculate the remainder of 1, since clearly both 10 and 19 satisfy that requirement.)
And here, at last, is where we come to the possibility that the NSA figured out how to crack the RSA algorithm. It turns out if, in the above public key equation, you know the prime factors of n—that is, the p and q we started with, then it is rather easy to solve for the original message.
As I mentioned above, as far as the academic world knows, when n is large, factoring it into the product of prime numbers is all but impossible. But, if the NSA cracked the RSA algorithm, they likely figured out a way to do it. That would be a serious mathematical accomplishment, far beyond being just Internet security.
So how likely is it that the NSA actually solved this longstanding problem?
It’s hard to say. Presumably for security reasons, the Times was quite vague about the NSA’s specific capabilities. In some cases, the NSA got around encryption through partnerships with companies. Other times, they apparently cracked the encryptions with supercomputers.
It is possible the NSA simply partnered with banks to find a backdoor through their encryption schemes. Furthermore, security expert Bruce Schneier, who worked with the Guardian on the same story, said, based on the documents he saw, that the “math is good.” That would seem to imply that he wasn’t shown anything to indicate the NSA figured out a prime factorization shortcut.
That said, if anyone could crack it, it’s the U.S. government. The Department of Defense spends $11 billion a year on cryptanalysis, employing some 35,000 people full time to the task—easily one of the most powerful mathematical armies in the world.
If nothing else, the incident stands as a reminder that in many case, our most private transactions on the Internet hinge on simple mathematical problems like prime factorization that, on a small scale, can be solved by a child. Whether or not that simplicity scales up to the large integers that secure online communications, no one knows—except, perhaps, the NSA.
Illustration by Niek Sprakel/Flickr
Joe Kloc
Joe Kloc is a former Daily Dot contributor who covered technology and policy. He's contributed to Newsweek and Mother Jones, discussed his reporting on air with WNYC, and written Weekly Reviews for Harper's Magazine.