 # How to Break Cryptography | Infinite Series

Cracking open secure
messages would be easy if only you knew how
to factor huge numbers. In this episode, we’ll
show you how with a twist. One of the main methods
of cryptography, the encoding and decoding
secure communications, uses really big prime numbers. For a detailed
description, check out some of the great videos we’ve
linked to in the description, but for now, here’s
the distilled version. It’s pretty easy for a computer
to find big prime numbers and multiply them together, but
it’s really hard for a computer to do the opposite– find the prime factors
of a really big number. The prime factors of a number
are all the prime numbers that evenly divide it. Normally, RSA cryptography uses
these prime factors like keys to decrypt messages. So if you want to
eavesdrop, you’ll need to find one of
these keys to hack in– that is, you’ll need to find the
prime factors of a big number, and we’re talking really big,
as in hundreds of digits long. Let’s try a small example. What are the prime
factors of 35? Well, they’re 5 and 7. How did you figure that out? Probably just by
looking at it, but even if you had forgotten
that fact, you could have just checked all the
prime numbers smaller than 35. Does two divide it? No. Does 3? No. Does 5? Yes. And so on. How boring. And more importantly for a
computer, how time consuming. We’ll need to do something
more strategic to factor really big numbers. Enter one of the great
math heroes, Euler. Along with many,
many other things Euler thought a lot
about prime numbers, relatively prime numbers,
and modular arithmetic, which is basically all the math
underlying RSA cryptography. So it makes sense that
we’d use similar math to break the algorithm. Modular arithmetic
is what happens when you count in a circle. Counting modulo 5,
or mod 5 for short, goes 0, 1, 2, 3 4, 0, 1,
2, 3 4, 0, 1, 2, and so on. We just use the numbers
less than 5 on repeat. We tell time mod 12 or mod 24
depending on your convention. This cyclical counting extends
to the arithmetic operations. So 1 plus 2 mod 5 is still just
3, but 2 plus 3 mod 5 is 0, and 2 times 3 is 1 mod 5. Another way to think
about modular asthmatic is in terms of the remainder
when dividing numbers. So here’s a slightly
more formal definition. a is congruent to x mod n means
that when we divide a by n the remainder is x. So 2 times 3 is 6, but
when we divide 6 by 5, the remainder is 1. So 2 times 3 mod 5 is 1. Euler noticed something
about modular arithmetic and exponentiation. Let’s look at the powers of 3– 3, 9, 27, 81, 243, and so on. And let’s look at
them all mod 10. It’s easy to figure out
what things are mod 10 because it’s just the
remainder when you divide by 10, which is the ones digit. So mod 10 our sequence is 3,
9, 7, 1, 3, 9,7, 1, and so on. Let’s repeat the
same experiment, but instead of looking at
the powers of 3 mod 10, let’s look at the
powers of 2 mod 7. The powers of 2 are 2, 4,
8, 16, 32, 64, and so on. And mod 7 we get 2, 4,
1, 2, 4, 1, and so on. What do you observe? The sequence of powers just
gets bigger and bigger, but the modular versions
of the sequence cycle. They repeat the same
pattern over and over again, and the last digit of
that pattern is always 1. As long as x and n
are relatively prime, meaning they share no prime
factors, the sequence x mod N, x squared mod N, x cubed mod
N, x to the fourth mod N, and so on will always
have this property. We call the length of the
repeating pattern the period. So the period of 3 mod 10 is 4,
and the period of 2 mod 7 is 3. Here’s why the
period is important. If the period of x mod
N is some number r, then r is the smallest
number such that x to the r is congruent to 1 mod n. For example, 3 to the fourth
is congruent to 1 mod 10, but 3 for the first, 3 squared,
and 3 cubed are not 1 mod 10, but let’s get back
to our original goal. What does all this stuff
periods have to do with factoring large numbers? Let’s say I give you a number n. I tell you n equals p times q
for two prime numbers p and q, but I don’t tell you
anything about those primes. Your job is to find them. Here’s how you’ll do it. Step one– pick any
number smaller than n. Let’s call the number
you selected a. Check to make sure
that a and n are relatively prime by
computing the greatest common divisor of a and n. The greatest common
divisor of two numbers is the biggest integer
that divides them both, so it’s 1 if the two numbers
are relatively prime. The Euclidean algorithm is
a quick and standard way to find the GCD of two numbers. If they have a
divisor in common, that’s a factor of n, which is
what you’ve been looking for, and you’ve saved yourself
the rest of the steps. Step two– compute the period
of a mod N. Let’s call it r. For the sake of
example, let’s say you’re trying to find
the factors of 35. So n equals 35, and
you pick a equals 8 since it’s relatively
prime to 35. Then with a little computation
we can see that r equals 4. To make all the
arithmetic work out, we’re going to need
to divide r by 2. So we need to know
that r is even. Later on, we’ll also need to
know that a to the r over 2 plus 1 is not congruent to 0
mod N. If either of these things fail, we need to pick a
different a in step one. Luckily, there’s at
least a 50% chance you’ll pick a good value for a. So on average, you won’t
have to try too many times. For step three, we’ll
the fact we know. a to the r is congruent to 1
mod N, which, subtracting 1, gives the a to the r minus
1 is congruent to 0 mod N. Saying that something is 0 mod N
is the same as saying that it’s a multiple of N. So there
must exist some integer k such that a to the r minus
1 equals k times N. Since we assumed
r is an even number, we can rewrite it as a to the r
over 2 minus 1 times a to the r over 2 plus 1 equals kN. And since N equals pq,
we’ll replace it with pq. OK, that was kind
of a lot of algebra. I often find it easier to
work through computations like that on my own instead of
watching someone else do it. You’re welcome to pause
here and check the steps. Here’s what happens with the
example where we are trying to find the factors of 35. Since the period of 8 mod 35
is 4, we have 8 to the fourth is congruent to 1 mod 35. So 8 to the fourth minus 1
is congruent to 0 mod 35. Actually, 8 to the
fourth minus 1 is 4,095, but we only care about
its value mod 35. We could rewrite this as
8 to the fourth minus 1 equals k times 35
for some integer k. Again, we could solve for k in
this case, but it’s irrelevant, so I’ll leave it as a variable. Rewrite this as 8 squared
minus 1 times 8 squared plus 1 equals k times p times q where
p and q are the prime factors of 35 that we’re searching for. Step four is the grand finale. I claim that the
greatest common divisor of a to the r over 2 minus 1 and
N is one of the prime factors. Let’s call it p, and the
greatest common divisor of a to the r over 2 plus 1 and
N is the other prime factor. Let’s call it q. Why? The equation a to the r over 2
minus 1 times a to the r over 2 plus 1 equals kpq means that p
must divide one of the factors on the left and q must divide
one of the factors on the left, but they cannot divide the same
factor since that factor would be divisible by N. Why is neither factor
divisible by N? For one, we assumed
a to the r over 2 plus 1 is not congruent
to 0 mod N. For the other, we know r is the minimum value
of x such that a to the x is congruent to 1 mod N. So
a to the r over 2 minus 1 is not congruent to 0 mod
N. Since p and q divide separate factors on the
left side of the equation, we can assume p divides
a to the r of 2 minus 1 and q divides a to
the r over 2 plus 1. So our formulas work. Again, that part contains
some weird algebra arguments. Go ahead and pause to think
about it or rewatch it. So in our example, p is
the greatest common divisor of 63 and 35, which is 7. And q is the greatest
common divisor of 65 and 35, which is 5, which
fortunately is correct. In summary, here’s our steps. Step one– pick a less
than N. Step two– find the period of a
mod N. Step three– well, we don’t need to do all
of the algebra of step three every time since
we know it works. So instead, we’ll use step
three to check that r is even and a to the r over
2 plus 1 is not congruent to 0 mod N. If
either of these things fail, we need to go back to step
one and pick a new value of a. Finally, step four–
let p equal the GCD of a to the r over 2 minus
1 and N. And let q equal the GCD of a to the
r over 2 plus 1 and N. And you’re done. You’ve destroyed
information security. OK, but obviously
there’s a catch since RSA cryptography
still works. Here it is. Step two, finding the
period, takes a long time– in fact, an
exponentially long time. That might make it
seem like we haven’t done a lot by constructing
these four steps, but actually we did. All the steps besides
two are pretty fast. Instead of looking for
a needle in a haystack, we reduced the hard
part to one step– finding the period. And– here’s the big twist– period finding is
precisely the kind of thing a quantum computer is good
at, and on the next episode, we’re going to dive into that. The four steps we just
reviewed are the outline of Shor’s algorithm,
and next time we’ll finish up by learning
how to use a quantum computer to dramatically
speed up step two. Then RSA cryptography
and your bank statements will really be in trouble. See you next time on
“Infinite Series.” Hello, I want to address some
digits of e and pi. First, Joel David Hamkins,
one of the mathematicians whose work is featured
we do not insist that the digits being swapped
come from the same digit place? So you can swap a digit
from anywhere in e with a digit from
anywhere in pi. Well, in this case, you
can make a rational number, and he proves that
in a blog post, which is linked to in the comments. All right, lots
the digits of e and pi algebraically instead
of literally swapping their digits. So can you add, subtract,
multiply, divide the number e and the number pi to
get a rational number? There’s a couple cool famous
examples like e to the pi i plus 1 is equal to 0. That’s Euler’s identity, and
there’s some really silly examples, like e times
pi divided by e times pi is equal to 1, but there’s
also a lot of things we don’t know about when
you multiply and divide e and pi whether you get
rational or irrational numbers. Some of my favorite examples
are these funny almost integers. So for example, pi to the ninth
divided by e to the eighth is really, really, really
close to 10, but it’s not. It’s not the number 10. It just kind of looks like that
if you do the computation out by hand. Also, e to the sixth minus
pi to the fifth minus pi to the fourth is really
close to 0, but it’s not 0. It just kind of looks like it. Finally, Reddles won
the challenge t-shirt for a very complete
answer to the question. If e and pi differ at
infinitely many digits, why is the list of
numbers produced by swapping infinitely many of
their digits uncountably long. Here’s the answer. For each digit that is
different between e and pi, you can either swap it or don’t. Therefore, we can label
a given permutation by listing whether or not
we swapped each digit. If we use 0 to represent doing
nothing and 1 to represent swapping the digit,
then each one of these corresponds to a list
and zeros and ones. Now, they mentioned two
proofs that this list of zeros and ones is uncountable. The first is that it’s in
bijection with the interval 0, 1 written in binary,
and the second is that you can use
Cantor’s diagonalization argument directly on it. Great answer. There were also a lot
of other great answers– way too many for
me to acknowledge. So thanks, guys. They were fantastic. See you next week. 