How to Break Cryptography | Infinite Series

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
about modular arithmetic, exponentiation, and
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
have to do some algebra. Let’s start with
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
of the comments on our episode about exchanging the
digits of e and pi. First, Joel David Hamkins,
one of the mathematicians whose work is featured
in the original episode, asked a follow up question. He asked, what if
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
and lots of folks asked about combining
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.


100 thoughts on “How to Break Cryptography | Infinite Series”

  • 3:00 Actually, the modulo applies to both sides: "A ≡ X (mod N)" reads "A and X are equivalent, modulo N", i.e. "the remainder of A/N is equal to the remainder of X/N" (and not just equal to X), or (likewise and less ambiguous) "the difference A-X of both sides is a multiple of N". For example, "22 ≡ 7 (mod 5)" is true and implies that 5|22-7 (i.e. 22-7=15 is divisible by 5), but it does not imply that the remainder of 22/5 must be equal to 7.

  • Дмитрий Веселов says:

    Can someone explain where does 3Mod10 sequence (3.46) comes from? What is the full operation? Do we divide 3 to the power of K by 10 and the sequence is the remainder?

  • Vincent-Olivier Roch says:

    at 3:06 a == x mod n doesn't mean that x is the remainder of a divided by n, but they do have the same remainder. so the right thing to say would be that n divides (a-x). so we could say in that logic that for all integers x y z n, x == y mod n implies that x == y + zn mod n.
    For example, 5 == 8 mod 3, but 8 is not the remainder of 5 divided by 3

  • I wish I was smart enough to understand any of this…. or that I would pay any attention to math class is high school 😔

  • I don't see how the period-finding step could have a higher complexity than O(n). The period cannot be more than n, so why isn't it simply a matter of checking a^1 through a^n for a power that results in 1 mod n?

  • Kaustubh Kendurkar says:

    If N = p * q then you could create a rectangle using p as length and q as breadth and N as area using computer, you could extend the rectangle until area of rectangle is N and know p and q.

  • Miles McGrew says:

    All this has taught me, is that while our methods of torture may be inconsistent, it is certainly going to be easier in the long run to just torture whoever we believe has the key. Even from a basic cost benefit analysis, the price of a quantum computer vs a few simple torture tools and someone who is really good with them, is a no brainer, torture wins again.

  • you know ive followed pbs spacetime for about a year or so and always felt i understood it but this i struggle with sooooooooo much more , even by the end of the first minute im like ok back to the start for you .

  • Step 1: Check if N is divisible by 2 or 3.
    Step 2: Check every odd number greater than 3 to see if it divides N.
    Step ~10^50: Profit?

  • xCa7+0VGs93gtELETim2keluYmqfLLx8bmqo7d0f62MQoUxlQiD6DUVX/gEpEn//A

  • mathew shoobert says:

    When Explaining MOD 5 it counts 0-1-2-3-4-0 ect is that Wrong??? wouldnt it go 1-2-3-4-5-1-2- ect I mean when doing the powers of 2 mod 7 it goes 2-4-1-2-4-1 Ect but thinking about the mod 5 ….. ahhh dam i think i just answerd my own question… dang… mod 7 only goes to 6 then 0 like 0-1-2-3-4-5-6-0-1 ect so 0 is a possible remainder ….. Yeah … sorry but i typed it so im posting it

  • gcd(a,n) = 1 are called co primes. Surprised she didn't actually say it. The Affine Cipher is a classic example of this where it only works with co primes.

  • Nice video i knew this but i thought about another question pertaining to this video on cracking RSA. It is what happens if we load a precalculated database of the periods then just do a look up we could also presort the database. Would this have any major breaking abilities on average for the 512 RSA and other commonly used RSA primes used currently.

  • This is sort of like rainbow tables for hashed passwords and other things that use dictionary based attacks.. Your really not using this dictionary method as a brute force your just using it to get by the complexity of finding a^r-1 =0 mod n or another words getting around the inverse discrete log problem…Unfortunately i don't currently have the computing power and computer space to test any of these results locally but it sounds plausible that the RSA guys just made the current RSA primes big enough to not be broken by anybody but themselves or companies with huge supercomputers/ databases

  • How many large prime numbers are there in the keyspace? With computers all around the world finding them, is a dictionary of large primes being created?

  • Answer: Use AES… it does not rely on prime numbers at all. It’s quite hard to crack, because it’s addition is mod 2 which ends up being XOR and it’s hard to guess input bits if you know the result of an XOR.

  • Can you please explain this encrypted message
    The decrypted message is
    Probably you are the right person to get the right explanation.

  • TwinnedSilver43 On Xbox one says:

    i just want to know how to make a table from a cryptography in a grid i can't do i. CAN SOMEONE HELP ME PLZ !!!!!!!!!!!!!!!

  • Abdullah Algurashi says:

    after research about (a) value in shor algorithem I found it come from this equation:
    if N = 5*7 = 35 then (a) value will be: (5-1)/2 = 2
    So I started with a=2 I found r=12.
    2^12 mod 35 = 1
    in the video (a) value was 8 and (r) value was 4 and this is mean
    8^4 = (2^3)^4 and its equal first value 2^12.
    you can try with any example for N U will find (a) value come from (q-1)/2.✌

  • Ends with "way too many for me to acknowledge, thanks guys". Two points here. One is that she can't count a simple number. Maths, nah. Arithmetic, not even that. She can't count! Second Point. Note her outfit and the word 'Guys'. Conclusion is this: 'Ok boys, come round to my place, I wont count how many 'guys' cum round'.

  • Came here a few months later.. I am surprised that I understood it this time..
    Now I can truly say that shor is a genius, and this video is great!

  • Alright, I'm back. I kinda don't understand the explanation at 9:52 – 10:06. I don't really see the logic there. I see why it has to be like that, so that we don't up with 1*N = p*q.
    Is it a^(r/2) =/= 0 mod N because we can't get a^(r/2) = 0 mod N from a^r = 1 mod N ?

  • I studied discrete math in high school and regretted not being math or compsci major in uni. I understand about 40% of this. Shor’s algorithm was new to me. I knew Euclidean algorithm. Thank you for this! I will now study number theory for RSA to fully solidify my understanding! Thanks so much PBS giving me direction on where to study next.

  • Great explanation. And what a surprise to learn this is Shor's algorithm, which I first heard of in an episode of Big Bang Theory.

  • Being a musician, modular arithmetic is like crack to me, and it is rare when one of these math videos on youtube actually say something interesting about it and feed my addiction.

    so… yeah I need some more please

  • Martin Verrisin says:

    what do I not get?
    – If we already have both a and r and can solve for k… why not just do that?
    — Then we will have:
    p = k
    q = N / k

    …why are the last 2 steps needed? This seems easier, fast and I don't see why it doesn't work…

  • Drexler Altarejos says:

    I was kinda confuse with 3^k to the congruence of 3 mod 10

    they must have used 3^k mod 10 to avoid the confusion

  • Michael Sanders says:

    wouldn't the period of any decimal number have a ceiling of 10? i don't understand why that is the Schor's bottleneck. seems finding gcd would have larger complexity.

  • question:
    101 to 119 digits first primes
    i find last day this funy link:
    press 'only evaluate'
    left number 1 and repated 000000 is eliminated
    000267 (101 digits)
    000003 (102 digits)
    000117 (103 digits)
    000129 (104 digits)
    000267 (105 digits)
    000003 (106 digits)
    000079 (107 digits)
    000003 (108 digits)
    000019 (109 digits)
    000457 (110digits)
    000007 (111 digits)
    000139 (112 digits)
    000207 (113 digits)
    000099 (114 digits)
    000271 (115 digits)
    000079 (116 digits)
    000093 (117 digits)
    000279 (118 digits)
    000709 (119 digits)
    19 number list 101 to 119 digits first primes only 1 second
    if 1001 to 1019 digits first primes:
    only a few minutes displayed
    if x=1;x=n(10^(c+10^12-1));c<=20;x
    not calculte on arround the world, any semi conductor super computer or parellel billion computers!
    not calculate quantum computer this question!
    halogram reader easily!
    left 1 and repeat 000000 is eliminated, only meanfull last 36 digits!

    trillion+1 to trillion+19 digits first primes ?
    if you are a good math man or good math girl, please show me 19 * 36 digits!

  • nonameforyouok PeterRodney says:

    The solution to factoring any composite integer is equivalent to determining the non-trivial, positive real-value of a variable (k) I call the 'Coefficient of factorization' used in a unique, integer-factorization expression of mine which I've termed the 'Transformula'.

  • nonameforyouok PeterRodney says:

    If you can figure out a way to determine the non-trivial, positive real-value of a variable (k) I call the 'Coefficient of factorization' utilized in the aforementioned formula, we do not need a Quantum Computer implementing Shor's Algorithm to factor large composite integers! This could settle once and for all the P vs NP question regarding Integer Factorization!

  • nonameforyouok PeterRodney says:

    Here are 2 mathematical expressions:
    1. P= round(.25*(((3+(2*sqrt(2)))^n)+((3-(2*sqrt(2)))^n))^2)-2 (n=positive integer >=1)
    2. Factors = sqrt(((1+T(sqrt(P)))^2)+P) +/- T(sqrt(P)) +/- 1 (P=composite integer,T=truncation operator)

    The 1st expression above generates Composite integers whose size (no. of digits) grows at an exponential rate with increasing n. The amazing thing about the 1st expression above is that it produces composites that is factorable by the 2nd expression above! Try it! but remember to set the precision for calculation high enough so that the 2 expressions above produce integers as output!

  • nonameforyouok PeterRodney says:

    For you 'MAPLE' users, here's the code: – (substitute other positive integer values for n!)

    > restart:
    > Digits:=500:
    > n:=50:
    > P := round(evalf(.25*((3+2*sqrt(2))^(n)+(3-2*sqrt(2))^(n))^2-2));
    > F1 := trunc(convert((sqrt((1+trunc(sqrt(P)))^2+P)-trunc(sqrt(P))-1),rational));
    > F2 := trunc(convert((sqrt((1+trunc(sqrt(P)))^2+P)+trunc(sqrt(P))+1),rational));

  • This video travels the path of a rigorous proof with the casual nature of sightseeing.

    By watching it you are seeing more than you are aware of.

    Thank you for your thoughtfulness!

    PS, I love you!

  • Thank you for making a non-mathematician understand a complicated subject such as breaking cryptography 👍 Also is prime number product the only way to make reliable cryptography?

  • a mod x = b means if you divide a by x you get b. a congruent b mod x means a and b have the same remainder when dividing by x.

  • Beyoond shweret. Tackling all of the obstacles. Just as it has been done for the e pie video. Great. 👍🏻👏🏻👏🏻👏🏻

  • Please see my new Riverside Confession letter hidden message decryption that shows a possible 3 character nickname for the Zodiac Killer. Conventional coding methodology unconventionally applied! Please click on the abstract round humanoid icon to see a short video on my new LoFi YT channel. Also a proposed geometric algorithm for the previously unsolved Ebeorietemethhpiti remainder of the D&B Harden solution to Zodiac's 408 cipher. Thanks.
    (Adult true crime content)

  • Jakob Michelizzi says:

    when you explained modular counting I am confused because in one example you included 0 and in another you didn't. does modular counting include 0 or not?

  • ⵉⵜⵔⵓⵏⴰⵓⵜ says:

    So the only thing keeping RSA cryptography from collapsing is the assumption that computational power won't exceed a certain level.

  • K1naku5ana3R1ka says:

    1:27 Actually, you only need to check the primes up to the square root of the number being factored; if there were any factors larger than that, then the other factors must all be smaller, and would have been discovered earlier, so you could divide them out and continue to get the full factorization.

  • K1naku5ana3R1ka says:

    You keep talking about two prime numbers being multiplied together and somehow used as a key, but never explain exactly how that works. I admit that would take a while, but do you have another video explaining how RSA cryptography works?

  • Alright, I will try to be clever and summarize my lack of understanding of the majority of the video in this way: I+am•a^dummy!

  • emjackson81989 says:

    So, here's a question that may or may not be covered in the next episode: Does Shor's Factorization Algorithm hold even for large numbers that are multiples of n large numbers where n > 2? That is, does it hold for N of the form p*q*r…*z?

  • Hi…

    May someone explain me ?

    I found this explanation highly interesting… So, i wrote some C for curiosity… Code works, but…

    …Finding"r" is waaaaaay longer than brute force factoring…

    For example:

    Factoring 21583 into 113 and 191 using 8 for "a" required 2660 iterations to find "r" while BF needs 57 iterations for a complete factor,

    Another example:

    factoring 4661 into 59 and 79 using 19 for "a" required 1131 iterations to find "r" while brute force needs only 30.

    What did i do wrong ???ffff

  • Swapnil Wankhede says:

    Very intersting, I am in 12 class and i am really looking forward to learn this kind of stuff about hacking and cryptography where should i start learing from please suggest and one more thing i really like your english speaking

  • I wrote an encryption method for messages that quantum computers can’t break.
    It doesn’t use keys and doesn’t allow you to know exactly when a encoded message stops or starts in the output.

Leave a Reply

Your email address will not be published. Required fields are marked *