I like how the final payment didn't account for inflation. Let alone did the reward have enough years for inflation to have had a significant effect anyways.
It's worth mentioning that the RSA algorithm (under a different name) was known to the US/UK governments close to 10 years before RSA discovered it. Cliff Cocks was technically the "first" person to discover public key using prime numbers (though RSA discovered it independently as well).
oh my goodness this is the first time I've seen a live video from "the R" from "RSA"... every student or former student of computer science has run into RSA sooner or later. This is just great. Thank you!
When you learn about these guys in books and powerpoints in uni, which you pay a shitload for, and then get a lecture by the guy himself for free on the Internet. Praise kek
Back in the day in university learning about cryptography I would never have dreamed about one day seeing the 'R' in RSA talking in a youtube video about how they came up with those famous numbers. It feels like witnessing an important part of computing history. I'm so excited about this, thank you very much for doing this, I love your video 💙😭
Some years ago I wrote a novel based on the idea that in the 13th Century, Roger Bacon devised a method for quick factorization, and when this method was rediscovered in the present day, it threatened to break RSA. Couldn't sell it to a publisher though. Too much maths :(
Brady: How much prep do you do before interviewing people like Professor Ron Rivest? I enjoy how you ask "simple" questions to get things rolling, then dive in a bit deeper on the follow-up. Well done!
Hi Numberphile, french fan here! I wondered if you guys would be interested in having someone to translate some of your subtitles in french (particularely this one, but others too). You have a lot of interesting videos I'd love to share with my high school students, unfortunately their english level isn't always enough to understand everything (or anything for some ^^). Thanks for reading me, I hope to hear from you soon. Bye!
I wonder how many viewers have never actually heard hardware making the modem sound that starts around 4:20 into the video. Ahh, the joys of dial-up connections. Those were the good-old days ... NOT!
Second question: Can we use Dr. Tokieda's ruler-method to generate factor pairs? Find the square root of your large product of primes. Find the primes to either side, multiply. If too big, move the smaller one down the list of primes. If too small, move the larger up the list of primes...
It has been said that HP-50g is a computer as it can handle as large number as the memory can hold. But on the other hand it is a calculator as it is allowed to be used in school tests.
Oh one of the RSA here !! Mr. Rivest ! :) I always was fascinated by his team's work ! very interesting topic ... then would such algorithm in the few coming years be substituted ?! technology actually advances in a way totally unexpected and unpredictable @_@
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577 × 32769132993266709549961988190834461413177642967992942539798288533 It was factored in 1994 using ~1600 computers
In case anyone's curious, here's the message that RSA-129 encrypted: "The magic words are squeamish ossifrage." Also, Brady et al. -- have you ever touched on the seeming paradox of one to the power of infinity being undefined? Logically it should be 1, but...
Infinity is not a number, so no numerical operation on infinity is defined. Infinity implies the absence of a limit to a process. Saying that "the sum of (1/2)^n for n from 1 to infinity = 1" simply says that as n increases without limit the sum becomes arbitrarily close to 1.
The indeterminate form 1^infinity is actually to represent functions such as (1+1/t)^t as lim t -> infinity. Technically speaking in that function, where the limit approaches depends on if 1+1/t gets to 1 faster than it being multiplied by itself infinitely many times.
i remember the part of the challenge that had integer partition generated numbers, hundreds of them i believe from 100 digits to 1000 digits. I was someone that even got published for factoring one of those, a really small number times a really large one.
I remember stumbling on an article by Helleman in the August 1979 issue of Scientific American called "The Mathematics of Public-Key Cryptography" as a young trainee programmer in the early 1980's. I used that article to implement a (fairly amateurish) public key encryption system in IBM Basic Assembler Language that ran (really slowly!) on an IBM 3031 mainframe. I still have the source code, but unfortunately it is on 9-track 6250 bpi round magnetic tape - and I have no way to read it to find out just how amateurish my effort was! Of course, at the time I had no idea how important public key cryptography would become, and so it is kind of annoying to not have proof that I once dabbled in leading edge technology
Phoe Nix I know in the bible it says that the earth is 6000 years old but I wasn't sure if it was a sarcastic comment on that, or if it's about the fact that the description makes it seem as though it was 17 quadrillion years as opposed to the 17 that it's implied to be.
Wow, this is one of the people who I can thank for RSA keys for my frequent SSH work! I knew the very basics of the RSA keys, but this is a great background. Thank you for this video. How long would it take to factor RSA129 with a modern top of the line single system? would AVX 2.0 make this far easier?
Why is it easy to determine that p and q are prime but difficult to find the factors of pq? Seems like you would need to find the factors of p and q individually to know whether they are prime... Is it just that pq is much bigger?
Can we create a candidate list of all likely primes (with a certain number of digits), and then just multiply the last few (3-ish) digits until a combination works to find the last few digits of the target number? Then once the candidate list is complete, double the number of digits that we care about, and rinse & repeat until there is only one possible combination? It seems like this would be much faster than trying to multiply out the whole prime values...
Without seeing the answer Id solve by using a computer to iteratively converge down to the solution, i.e. multiply large primes if the product is too small try larger ones, if the product is too large then try smaller, basically it would require some computer programming skills to write the correct program
3:11 If you were Brady, we would only need to break into his house, get to his computer desk and then find the notebook where he keeps this sort of stuff.
Since the primes become significantly less densely represented the larger integers get, doesn't that directly act to reduce the difficulty of finding p and q as the final number gets larger and larger? Are p and q supposed to be very close to each other in length? If so, doesn't that make it much easier to find them as you can just start with the square root and test around there? If they can differ substantially in length, are there advised minimums for each?
I'm 6 years late, but you shouldn't start at the square root at search close to there. See Computerphile's more recent "breaking RSA" video for the explanation - basically that an attacker could do the same thing
What if you multiplied 100 prime numbers together. Then you randomly picked 2 factors of that number. The cracking of the code would become harder because not only would you have to factorise the number into it's primes, you'd also have to find the unique combination of the 100 primes. There are approximately 2^99 ways to split the number into two factors.
Jarah Fluxman the point of encyption is usually to be able to decrypt it yourself? if youre just choosing 2 primes from a set of 100 large primes thats less secure than choosing two from the set of natural numbers
I wrote a little prime factoring program back in the 90’s. You put in the number of your choice and it spits out a list of the prime factors. So in essence that is what is needed to find the factors of your number. The program couldn't digest that many digits though. Fun! I'm nowhere to being in your league though. Of course.
I am Brazil, factoring the prime number is taking the number multiplied by all the odds before it, from top to bottom, there will only be 1 that is prime and another is the rest that is a prime number.
Is RSA-129 a method/postulation, by which 128BIT OS's can be used as a 'Virtual-129Bit-OS' on naturally-limited occasions, by creating '1-Virtual-Bite' from all other 128Bits, on uncompressing the data? To throw off all 128Bit-And-Less-Malware and All-128Bit-And-Less-Hacks?
the question is there more then one answer. Well, if you look at the number and product. Solution should of been more apparent. 129 digit answer. 66 digit * 64 digit prime if I counted it right then its aprox. Take into account the rule of zero's a given answer, you can rule out swaths of numbers. Also useless combinations, relating to "end" and "start" product of the number. Such as How many numbers multiplied give 1. 1*1, 1*7, 3*7 9*9... etc of course all even combinaions are thrown out because its not a prime. that along eliminates the req considerable. working backwards one can narrow how 541 is created from a small number set simply be seeing the reverse operation. If product end is 541. Say if 9*9 was used, 81 1 is the result carry the eight want result is 4. We find that even less numbers exist to create it, and possibly a non combination later. So in doing chunks of the product backwards, with remainder carries, one could find the digits that comprise the p and q. Although one might not know the p and q. doing this method would eliminate many possibilities. What you have.. after sometime is end up with a few variants.. but like password it eliminates itself, because of its product and those multiplied are its prime. So 533 and 577. would appear as one of those variants of course one can verify and eliminate primes that are not part of the variants which intern isolate the and q further. Not sure a computer was needed for the solution... Since a list of primes exist. the law of zeros is that and since its primes multiplied. Its not 1 digit *129 digits, or 11 digits * 119 digits. the result was 66 digits*64 digits to give us the 129 digits needed. IN this case digits are added, but written out they would be multiples of 10's. 66+64 =130 digits.. now did I add wrong.. Who knows... anyways cool problems thats my thoughts.
Brady, you really need a mic on you, if you are to be heard when asking questions from behind the camera. Apart from that, another really interesting video.
see you created a critical table also known as the payment table where you restrict a one Pacific or large number then you'll end up going down the actual chart which indicates a permit wants it spread out these particular numbers in this chart have you tried a reverse technique of this chart by turning the chart upside down and working from a small number tours a big number multiplying or dividing or taking away
Wait, so i can just create a 300 digit P and Q number by adding 1 or other tests to find the closest prime number and then multiply the 2 and get a massive number that not even supercomputers can figure out the original numbers that generated that number?
For a given key size (in this case 129 decimal digits) two primes are always optimal. The more factors, the easier they are to find. If I attack a key of length 129, I know that at least one of the factors will be less than the square root of the key. The number of primes less than the square root of RSA-129 is 7.3040e+061. If you use three primes, one must be less than the cube root, so the number of such primes is about 4.9900e+040. This problem is 21 orders of magnitude easier. Once I have that factor, I will have reduced the remaining complexity by whatever the size of the quotient is. It is *much* easier to solve two problems of order 1e40 than one problem of order 1e61, more than a thousand billion billion times easier. For any key length, always select two primes.
Fantastic content thanks for sharing . What does he mean by 'rolling the dice' ? Obviously it's a metaphor but I'd like to understand what they did exactly .
so what does that mean???? if the product can be factorized doesn't it mean the RSA mechanism is broken? i know we use much bigger number today but still... the entire RSA mechanism is based on a sole assumption the factorizing huge number to their primes is an extremely difficult task. but what if we can make it a less difficult task (by improving the algorithms and increasing compute power)??
Every single cipher is breakable in principle whenever the message length is longer than the key. (Think of the German Enigma which did not employ this technique.) The RSA-129 challenge put an upper bound on the level of effort required. Experience tells us that data breaches come from disloyalty and carelessness, not from cryptological attacks. One time pads actually offer an encryption method that is unbreakable in principle, but they are expensive to implement. One famous case where "one time pads" (a better term would be "some time pads") were broken was the infamous Venona decrypts. Remember that carelessness thingy? The Soviets re-used pages in their one-time pad books. Since they always send messages using a new first page and the messages all contained stereotyped preambles, it was not hard for American cryptographers to spot messages sent with the same one time pad and hence to reconstruct the pad. (The length of the two messages was twice the length of the pad, which was the encryption key.)
Who else thinks Numberphile should make a video showing how they make their videos and how you can do the same and submit them to a specific website in which they can of videos on? Or at least to have a channel of your own like this one?
I KNOW I KNEW THAT PHOTO WITH 3 GUYS AND "P = NP"! IT IS RSA!! How could I not have noticed? An absurdly large integer as the product of two huge primes together with a smaller number...
I tried writing a python script for this, but it only works for smaller primes. I can't get it to work with large primes. Any thoughts? def prime_finder(num): x=2 while x
king joe It's really the only big channel about maths... in contrast to channels dedicated to phisics, biology and science in general, which are a lot more.
what I do not understand is that you have to chose 2 prime numbers first to generate public key . the message can be decoded only when you do the factorisation which is hard. but instead of doing factorisation I take the database of prime numbers from internet and generate all possible combinations and just try to match with public key. since public key is multiple of 2 primes there no other combination possible to generate same key. please explain
You underestimate just how many primes there are. Quoting _Rosen, Elementary Number Theory 5th pg 81_, the number of primes with less than 22 digits is 783,964,159,847,056,303,858. RSA uses ~64 digit primes. If you checked 1 prime pair per second for 22 digits, it would take about 15 years to check all those primes. It would thus take about 15,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years to check all the primes usable by RSA. Even if you check a million primes per second, it would still take 15,000,000,000,000,000,000,000,000,000,000,000,000 years to brute-force the problem. Good luck with that.
The trick is to make the numbers so large that it's impossible to build that database you're imagining. (Not in the sense of mathematically impossible, but in the sense that there aren't enough computers in the world to compute or store it.) When creating a cryptographic key, you mustn't use primes you found on the internet. That would be insecure for the same reason it's insecure to set your computer's password to something that can be found online.
understood. is there any agency which allocate prime numbers to banks etc so that combination is always unique. otherwise it is possible that a bank may same key as any other bank. essentially what i am asking is that whether selection of prime start randomly or in sequence
The primes are the secret one must know to decrypt a message that was encrypted with the product of the primes, which is public. Therefore, they must be chosen as randomly as possible. Any sort of predictable sequence would make it easier to guess the secret, so this isn't done. Similarly, a central repository of secret keys would be a horrible security risk. It's not necessary anyway, you can just compare the public keys for uniqueness instead. When your computer generates a key, it simply finds some 'fresh' primes on its own. It is theoretically possible that it randomly happens to make a key that someone else has already made before. However, this is so astronomically unlikely that you simply don't have to worry about it. Consider this: when an attacker tries to break your encryption by guessing your secret, it is theoretically possible that they get it right on the first try. Possible, but so unlikely that no sane hacker would actually try getting money from a bank that way. Getting money by guessing numbers is way, way, WAY more easily done by just playing the lottery. And that isn't even illegal ;)
could you please make a video on why e^(i*2*PI*x) = (e^(i*2*PI) )^x = 1^x = 1 is a false statement? why does a^(bc) = (a^b)^c seem to not apply here? thanks in advance :)
only if you assume that x is an integer for example if x = 1/2, then you get: e^(2iπx) = e^(iπ) = -1 which contradicts the statement that i made earlier how e^(2iπx) should always be 1 if regular laws of powers apply which tells me that a^(bc) = (a^b)^c is not true for e^(2iπx) to begin with
I dont get it. Why do you need the factors to be able to decrypt it if you could use the product to encrypt it? How does that work? Why cant you use the same key to decrypt it?
When quantum computing becomes more prevalent, this kind of encryption would become obsolete right? Because it would become more likely for a computer to decode this kind of encryption, mathematically, unless you have billions of circuits all with their own RSA style encryption because at some point even if a computer can decode the math, at some point the time limitation makes it impossible. But the way to decode this would be to first determine all possible factors of RSA129 and then have the quantum computer test all possible combinations for each new factor it discovers. Eventually it will find the correct answer.
Yeah, the real value is in being awarded the prize (which may enhance one's professional reputation). Donald Knuth has been giving out checks for finding errors in his "Art of Computer Programming" books, starting at something like $1 for the first error reported, $2 for the second, etc. I may be the only Knuth-error-award recipient who went ahead and deposited my check.
he says," randomly Generated primes ( p x q) = 114381625...........541 how can prime be multiple of these 'p' and 'q' ,if it really is a prime number ?
The number you get isn't a prime, that's why you can factor it. Both P and Q are primes, and when you multiply them together you get a number whose only factors are p and q. For example, if p were 3 and q were 7 3*7=21 the only factors to 21 are 3 and 7. However when you have really large numbers (hundreds of digits) trying to find which 2 prime numbers multiply into that 1 number is extremely time-consuming, making them usable for encryption.
This man is "R" in "RSA"? Wow, thank you, numberphile!
Антоша Пушкин Finally! No one in the contents seems to be appreciating what an honor this is!
When they said who he was I was like "holy sh*t!"
same
+Chris Knowles I totally do, this is amazing. I work with RSA daily.
Привет соотечественникам, если ты из России, конечно)
$100 for 40 quadrillion years' work. Flipping heck, that's nowhere near a living wage.
I like how the final payment didn't account for inflation. Let alone did the reward have enough years for inflation to have had a significant effect anyways.
🤣
It's worth mentioning that the RSA algorithm (under a different name) was known to the US/UK governments close to 10 years before RSA discovered it. Cliff Cocks was technically the "first" person to discover public key using prime numbers (though RSA discovered it independently as well).
Super. Do you have a link or the name of the algorithm to read about it ?
oh my goodness this is the first time I've seen a live video from "the R" from "RSA"... every student or former student of computer science has run into RSA sooner or later. This is just great. Thank you!
When you learn about these guys in books and powerpoints in uni, which you pay a shitload for, and then get a lecture by the guy himself for free on the Internet.
Praise kek
*PRAISE KEK* 🐸🐸🐸
Key Encryption Key?
Thanks Brady for once again getting a great interview with yet another legend!
Who else imediately spotted the P = NP on the blackboard at 1:20?
Be sure to check out the extra footage at Numberphile2
th-cam.com/video/tX7e7CgWrvM/w-d-xo.html
Numberphile notice me senpai
Numberphile Good video :)
P vs NP I declare genocide
It's P=NP, and this is one of the major unsolved problems in mathematics. Wikipedia has a short introduction to this concept.
"$100 for that much computer time was really quite a coup" That gave me a good laugh haha
Back in the day in university learning about cryptography I would never have dreamed about one day seeing the 'R' in RSA talking in a youtube video about how they came up with those famous numbers.
It feels like witnessing an important part of computing history.
I'm so excited about this, thank you very much for doing this, I love your video 💙😭
Typo at 5:24 - unless ScienTITific American is a real journal?
oops, can get a 129-digit number right, but not the word Scientific...
Alex Evans That was just their Swimsuit Edition.
Numberphile You just have to release a risqué reproductive biology edition…
Numberphile Welcome to the Nerd Internet.
The official misspelling of the Numberphile TH-cam channel
I grew up playing with this guy's RC4 algorithm. Neat to see him interviewed. Thank you Numberphile!
There also a sum who caracterise this number, rsa-129= a+2sqrt(ab+1)+b with ab+1 is a perfect square and 0
1:19 The famous RSA trio had already proven P = NP on a classroom chalkboard decades before it became a millennium prize problem.
1 = 1 * 1
0 = 0 * 0
Look mom I solved it!
P=NP
P/P=N
P/P=1
N=1
Thanks for returning to Numberphile Ron! Please come back! We want to know more about the other mathematics you do!
Some years ago I wrote a novel based on the idea that in the 13th Century, Roger Bacon devised a method for quick factorization, and when this method was rediscovered in the present day, it threatened to break RSA. Couldn't sell it to a publisher though. Too much maths :(
This guy is Ron Rivest. The R in RSA. Wow. This is such an honor.
Brady: How much prep do you do before interviewing people like Professor Ron Rivest?
I enjoy how you ask "simple" questions to get things rolling, then dive in a bit deeper on the follow-up. Well done!
This Channel is gold for CS and Math Students. Lots of love from India
I believe there's already a number called "one twenty nine"! I can't remember which one though...
A. Lenstra is actually one of my professor
what's the feeling of attending his lecture?
@@andeslam7370 He's a brilliant person, and an excellent teacher; I only had one class with him but his lectures were really a lot of fun to attend.
Watching this exactly a year after it was posted! Clicked on it out of pure interest!
I have seen this man in previous Numberphile videos but had no idea he was Ron Rivest from RSA! Amazing!
Arjen Lenstra was my professor at EPFL, it was such an honour to attend his lectures!
Hi Numberphile, french fan here! I wondered if you guys would be interested in having someone to translate some of your subtitles in french (particularely this one, but others too). You have a lot of interesting videos I'd love to share with my high school students, unfortunately their english level isn't always enough to understand everything (or anything for some ^^). Thanks for reading me, I hope to hear from you soon. Bye!
I'm watching this with spare time in my math class haha
11438(etc) : Number of tweets using the word "tremendous".
Oh my goodness, an inventor of RSA, RC*, MD* and randomised partial checking? This man is a god!
one of the better numberphile videos in recent history
I'm happy because for once I realized that I already knew something.
what a warm and smiley cryptographer
I wonder how many viewers have never actually heard hardware making the modem sound that starts around 4:20 into the video.
Ahh, the joys of dial-up connections. Those were the good-old days ... NOT!
in 100 years viewers will assume it was an Enigma cipher machine warming up 🤣
Nice
I'm studying at infosec faculty and I'm pretty sure we actually were told about this number and people and story behind it.
Awesome.
If you're reading this, have a Great day! 😄😄😄
Thanks, have a great life!
CyanGaming | ᴹᶦᶰᵉᶜʳᵃᶠᵗ ⁻ ᴳᵃᵐᵉᴾᶫᵃʸ you forgot "- from small youtuber"
OML the cancer has spread from Mumbo Jumbo
I don't know what to think about the P = NP in the background at 1:18
Justifer14 P =N...ot P
Second question: Can we use Dr. Tokieda's ruler-method to generate factor pairs?
Find the square root of your large product of primes. Find the primes to either side, multiply. If too big, move the smaller one down the list of primes. If too small, move the larger up the list of primes...
what a great insight into the early development of a method almost everybody uses when connecting to the internet today! Do more on cryptography :)
Hey random people reading comments, have a great day!
I'm not random, I'm specific and I specifically hope your day is at least satisfactory.
Junior Matsuda thanks, you too!
Junior Matsuda You too!
You too!
Happy birthday, Tim!
The legends! Learnt these guys from my cryptography course!
What a humble genius!
It has been said that HP-50g is a computer as it can handle as large number as the memory can hold. But on the other hand it is a calculator as it is allowed to be used in school tests.
Intriguing way of attracting people's minds towards maths reality
Oh one of the RSA here !! Mr. Rivest ! :)
I always was fascinated by his team's work !
very interesting topic ... then would such algorithm in the few coming years be substituted ?!
technology actually advances in a way totally unexpected and unpredictable @_@
for all primes numbers p above 1 and below RSA-129(r), if r/p is in primes: return (r,p)
it should take around number of primes*n time to work, which is very fast.
AP gonna try that.. don't think it's gonna be that fast.. plus you only need to check till sqrt(RSA129)
AP But now you need to find all the 64 digit prime numbers, which is even more difficult.
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
× 32769132993266709549961988190834461413177642967992942539798288533
It was factored in 1994 using ~1600 computers
but easier than random chance by far :)
In case anyone's curious, here's the message that RSA-129 encrypted: "The magic words are squeamish ossifrage."
Also, Brady et al. -- have you ever touched on the seeming paradox of one to the power of infinity being undefined? Logically it should be 1, but...
But what?
But 1^infinity is undefined, much as 1/infinity is.
Infinity is not a number, so no numerical operation on infinity is defined. Infinity implies the absence of a limit to a process. Saying that "the sum of (1/2)^n for n from 1 to infinity = 1" simply says that as n increases without limit the sum becomes arbitrarily close to 1.
The indeterminate form 1^infinity is actually to represent functions such as (1+1/t)^t as lim t -> infinity. Technically speaking in that function, where the limit approaches depends on if 1+1/t gets to 1 faster than it being multiplied by itself infinitely many times.
Fermat's method of factorization generalizes to all figurate numbers.
i remember the part of the challenge that had integer partition generated numbers, hundreds of them i believe from 100 digits to 1000 digits. I was someone that even got published for factoring one of those, a really small number times a really large one.
I remember stumbling on an article by Helleman in the August 1979 issue of Scientific American called "The Mathematics of Public-Key Cryptography" as a young trainee programmer in the early 1980's. I used that article to implement a (fairly amateurish) public key encryption system in IBM Basic Assembler Language that ran (really slowly!) on an IBM 3031 mainframe. I still have the source code, but unfortunately it is on 9-track 6250 bpi round magnetic tape - and I have no way to read it to find out just how amateurish my effort was! Of course, at the time I had no idea how important public key cryptography would become, and so it is kind of annoying to not have proof that I once dabbled in leading edge technology
Just read the description... You reckon it took 17 quadrillion years to solve?
doubt it, Earth is only 6000 years old.
Nik Conlon a joke?
Harry Ward facts, read your bible dude
That joke went over about as well as a brick of lead.
Phoe Nix I know in the bible it says that the earth is 6000 years old but I wasn't sure if it was a sarcastic comment on that, or if it's about the fact that the description makes it seem as though it was 17 quadrillion years as opposed to the 17 that it's implied to be.
Phoe Nix I don't have one
Excellent video from the creator!
Wow, this is one of the people who I can thank for RSA keys for my frequent SSH work! I knew the very basics of the RSA keys, but this is a great background. Thank you for this video.
How long would it take to factor RSA129 with a modern top of the line single system? would AVX 2.0 make this far easier?
Why is it easy to determine that p and q are prime but difficult to find the factors of pq? Seems like you would need to find the factors of p and q individually to know whether they are prime... Is it just that pq is much bigger?
Please more videos on cryptography! !!!!!! encryption, etc! Thanks. He puts the R in RSA.
I love how happy he is talking about this =P
f(x)=(x^2) +-2x +-[3-cos(x.pi)]/2
Any value for x (except 0 which gives 1)atleast 1of the 4 equation will generate a prime.
Why this happens?
You independently reinvented the algorithm. It was developed at GCHQ by Clifford Cocks. Deleting if mentioned later.
Can we create a candidate list of all likely primes (with a certain number of digits), and then just multiply the last few (3-ish) digits until a combination works to find the last few digits of the target number?
Then once the candidate list is complete, double the number of digits that we care about, and rinse & repeat until there is only one possible combination? It seems like this would be much faster than trying to multiply out the whole prime values...
That list would be larger than the observable universe
Without seeing the answer Id solve by using a computer to iteratively converge down to the solution, i.e. multiply large primes if the product is too small try larger ones, if the product is too large then try smaller, basically it would require some computer programming skills to write the correct program
3:11 If you were Brady, we would only need to break into his house, get to his computer desk and then find the notebook where he keeps this sort of stuff.
Since the primes become significantly less densely represented the larger integers get, doesn't that directly act to reduce the difficulty of finding p and q as the final number gets larger and larger? Are p and q supposed to be very close to each other in length? If so, doesn't that make it much easier to find them as you can just start with the square root and test around there? If they can differ substantially in length, are there advised minimums for each?
I'm 6 years late, but you shouldn't start at the square root at search close to there. See Computerphile's more recent "breaking RSA" video for the explanation - basically that an attacker could do the same thing
What if you multiplied 100 prime numbers together. Then you randomly picked 2 factors of that number. The cracking of the code would become harder because not only would you have to factorise the number into it's primes, you'd also have to find the unique combination of the 100 primes. There are approximately 2^99 ways to split the number into two factors.
Jarah Fluxman the point of encyption is usually to be able to decrypt it yourself? if youre just choosing 2 primes from a set of 100 large primes thats less secure than choosing two from the set of natural numbers
Ron Rivest is a genius.
I wrote a little prime factoring program back in the 90’s. You put in the number of your choice and it spits out a list of the prime factors. So in essence that is what is needed to find the factors of your number. The program couldn't digest that many digits though.
Fun! I'm nowhere to being in your league though. Of course.
I am Brazil, factoring the prime number is taking the number multiplied by all the odds before it, from top to bottom, there will only be 1 that is prime and another is the rest that is a prime number.
Is RSA-129 a method/postulation, by which 128BIT OS's can be used as a 'Virtual-129Bit-OS' on naturally-limited occasions, by creating '1-Virtual-Bite' from all other 128Bits, on uncompressing the data? To throw off all 128Bit-And-Less-Malware and All-128Bit-And-Less-Hacks?
Was the cheque ever cashed? or kept for sentimental reasons?
the question is there more then one answer. Well, if you look at the number and product. Solution should of been more apparent. 129 digit answer. 66 digit * 64 digit prime if I counted it right then its aprox. Take into account the rule of zero's a given answer, you can rule out swaths of numbers. Also useless combinations, relating to "end" and "start" product of the number. Such as How many numbers multiplied give 1. 1*1, 1*7, 3*7 9*9... etc of course all even combinaions are thrown out because its not a prime. that along eliminates the req considerable. working backwards one can narrow how 541 is created from a small number set simply be seeing the reverse operation. If product end is 541. Say if 9*9 was used, 81 1 is the result carry the eight want result is 4. We find that even less numbers exist to create it, and possibly a non combination later. So in doing chunks of the product backwards, with remainder carries, one could find the digits that comprise the p and q. Although one might not know the p and q. doing this method would eliminate many possibilities. What you have.. after sometime is end up with a few variants.. but like password it eliminates itself, because of its product and those multiplied are its prime. So 533 and 577. would appear as one of those variants of course one can verify and eliminate primes that are not part of the variants which intern isolate the and q further. Not sure a computer was needed for the solution... Since a list of primes exist. the law of zeros is that and since its primes multiplied. Its not 1 digit *129 digits, or 11 digits * 119 digits. the result was 66 digits*64 digits to give us the 129 digits needed. IN this case digits are added, but written out they would be multiples of 10's. 66+64 =130 digits.. now did I add wrong.. Who knows... anyways cool problems thats my thoughts.
Wonder why they chose their initials to be in that specific order, instead of alphabetical order...
Brady, you really need a mic on you, if you are to be heard when asking questions from behind the camera.
Apart from that, another really interesting video.
see you created a critical table also known as the payment table where you restrict a one Pacific or large number then you'll end up going down the actual chart which indicates a permit wants it spread out these particular numbers in this chart
have you tried a reverse technique of this chart by turning the chart upside down and working from a small number tours a big number multiplying or dividing or taking away
Wait, so i can just create a 300 digit P and Q number by adding 1 or other tests to find the closest prime number and then multiply the 2 and get a massive number that not even supercomputers can figure out the original numbers that generated that number?
Is there a reason why you couldn't use three primes to increase security?
For a given key size (in this case 129 decimal digits) two primes are always optimal. The more factors, the easier they are to find. If I attack a key of length 129, I know that at least one of the factors will be less than the square root of the key. The number of primes less than the square root of RSA-129 is 7.3040e+061. If you use three primes, one must be less than the cube root, so the number of such primes is about 4.9900e+040. This problem is 21 orders of magnitude easier. Once I have that factor, I will have reduced the remaining complexity by whatever the size of the quotient is. It is *much* easier to solve two problems of order 1e40 than one problem of order 1e61, more than a thousand billion billion times easier.
For any key length, always select two primes.
"...the cheapest purchase of lots and lots of computer time." Well played.
this guy is a legend
Fantastic content thanks for sharing . What does he mean by 'rolling the dice' ? Obviously it's a metaphor but I'd like to understand what they did exactly .
I was thinking that I could write code in an hour or so to solve this (but the time taken to execute said code would be a bit larger.)
About 15,000,000,000,000,000,000,000,000,000,000,000,000 years, assuming you check a million ps and qs per second. :)
so what does that mean????
if the product can be factorized doesn't it mean the RSA mechanism is broken?
i know we use much bigger number today but still... the entire RSA mechanism is based on a sole assumption the factorizing huge number to their primes is an extremely difficult task. but what if we can make it a less difficult task (by improving the algorithms and increasing compute power)??
Every single cipher is breakable in principle whenever the message length is longer than the key. (Think of the German Enigma which did not employ this technique.) The RSA-129 challenge put an upper bound on the level of effort required. Experience tells us that data breaches come from disloyalty and carelessness, not from cryptological attacks.
One time pads actually offer an encryption method that is unbreakable in principle, but they are expensive to implement. One famous case where "one time pads" (a better term would be "some time pads") were broken was the infamous Venona decrypts. Remember that carelessness thingy? The Soviets re-used pages in their one-time pad books. Since they always send messages using a new first page and the messages all contained stereotyped preambles, it was not hard for American cryptographers to spot messages sent with the same one time pad and hence to reconstruct the pad. (The length of the two messages was twice the length of the pad, which was the encryption key.)
Who else thinks Numberphile should make a video showing how they make their videos and how you can do the same and submit them to a specific website in which they can of videos on? Or at least to have a channel of your own like this one?
why is the number of digits of the generators (p,q) disclosed?
@Eli Suryana 5:29 "p is 64 digit long and q is 65...."
Nice Mighty Black Stump cameo
I KNOW I KNEW THAT PHOTO WITH 3 GUYS AND "P = NP"! IT IS RSA!! How could I not have noticed? An absurdly large integer as the product of two huge primes together with a smaller number...
I tried writing a python script for this, but it only works for smaller primes. I can't get it to work with large primes. Any thoughts?
def prime_finder(num):
x=2
while x
I like how numberphile can make an interesting video out of algebraic math.
king joe It's really the only big channel about maths... in contrast to channels dedicated to phisics, biology and science in general, which are a lot more.
The Commentator Yes I know, but the thing is that this topic has a very advanced background, methods that couldn't be found until a few decades ago.
could you do a video about infinity factorial?
Shas, Infiniy is really not a number to which you can apply a function such factorial(x)... it's more of a concept.
There is an infinite amount of ways of arranging infinite objects
What does BSA 1 mean? It's the letters in the background of the caption ?!
what I do not understand is that you have to chose 2 prime numbers first to generate public key . the message can be decoded only when you do the factorisation which is hard. but instead of doing factorisation I take the database of prime numbers from internet and generate all possible combinations and just try to match with public key. since public key is multiple of 2 primes there no other combination possible to generate same key. please explain
You underestimate just how many primes there are. Quoting _Rosen, Elementary Number Theory 5th pg 81_, the number of primes with less than 22 digits is 783,964,159,847,056,303,858. RSA uses ~64 digit primes. If you checked 1 prime pair per second for 22 digits, it would take about 15 years to check all those primes. It would thus take about 15,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years to check all the primes usable by RSA. Even if you check a million primes per second, it would still take 15,000,000,000,000,000,000,000,000,000,000,000,000 years to brute-force the problem. Good luck with that.
The trick is to make the numbers so large that it's impossible to build that database you're imagining. (Not in the sense of mathematically impossible, but in the sense that there aren't enough computers in the world to compute or store it.)
When creating a cryptographic key, you mustn't use primes you found on the internet. That would be insecure for the same reason it's insecure to set your computer's password to something that can be found online.
understood. is there any agency which allocate prime numbers to banks etc so that combination is always unique. otherwise it is possible that a bank may same key as any other bank. essentially what i am asking is that whether selection of prime start randomly or in sequence
The primes are the secret one must know to decrypt a message that was encrypted with the product of the primes, which is public. Therefore, they must be chosen as randomly as possible. Any sort of predictable sequence would make it easier to guess the secret, so this isn't done. Similarly, a central repository of secret keys would be a horrible security risk. It's not necessary anyway, you can just compare the public keys for uniqueness instead.
When your computer generates a key, it simply finds some 'fresh' primes on its own. It is theoretically possible that it randomly happens to make a key that someone else has already made before. However, this is so astronomically unlikely that you simply don't have to worry about it.
Consider this: when an attacker tries to break your encryption by guessing your secret, it is theoretically possible that they get it right on the first try. Possible, but so unlikely that no sane hacker would actually try getting money from a bank that way. Getting money by guessing numbers is way, way, WAY more easily done by just playing the lottery. And that isn't even illegal ;)
But isn't the symbol for a random prime number capital pi?
that must be the most satified 100$ ever recieved.
0:35 - that's numberwang
8:41The date on the check is the day Richard Nixon died. He was the 12th prime president, number 37.
could you please make a video on why
e^(i*2*PI*x) = (e^(i*2*PI) )^x = 1^x = 1
is a false statement? why does a^(bc) = (a^b)^c seem to not apply here?
thanks in advance :)
Max Well e^(2iπx) actually equals 1
only if you assume that x is an integer
for example if x = 1/2, then you get:
e^(2iπx) = e^(iπ) = -1
which contradicts the statement that i made earlier how e^(2iπx) should always be 1 if regular laws of powers apply
which tells me that a^(bc) = (a^b)^c is not true for e^(2iπx) to begin with
a^(bc) = (a^b)^c works for real numbers, but not for complex numbers.
u should touch on digital rooting and the vedic square. 9!!
I dont get it. Why do you need the factors to be able to decrypt it if you could use the product to encrypt it? How does that work? Why cant you use the same key to decrypt it?
I suggest you watch the khanacademy videos on RSA. I can't link since I'm on mobile, but they give a more in-depth explanation of how RSA works.
When quantum computing becomes more prevalent, this kind of encryption would become obsolete right? Because it would become more likely for a computer to decode this kind of encryption, mathematically, unless you have billions of circuits all with their own RSA style encryption because at some point even if a computer can decode the math, at some point the time limitation makes it impossible. But the way to decode this would be to first determine all possible factors of RSA129 and then have the quantum computer test all possible combinations for each new factor it discovers. Eventually it will find the correct answer.
Are Shamir or Adleman still working in the industry?
Think I'm missing something - looks like the encoded message would be solvable by frequency analysis.
Only if the message length was significantly longer than 10^64 characters.
Definitely missed something then!
Awesome Video!!
Why did they offer a $100 prize for the factorization? Seems kind of pointless.
Khan Singh
An incentive that wouldn't break the bank.
+Khan Singh $100 prizes for math problems is kind of a tradition and nod to Erdös
Well, for a cashier's check the money is still gone, it's withdrawn when the check is issued
Yeah, the real value is in being awarded the prize (which may enhance one's professional reputation). Donald Knuth has been giving out checks for finding errors in his "Art of Computer Programming" books, starting at something like $1 for the first error reported, $2 for the second, etc. I may be the only Knuth-error-award recipient who went ahead and deposited my check.
So what? You can cash it and keep it too.
I have one of this guy's textbooks on my desk right now :)
Ok, but R is from his first or his last name?
he says," randomly Generated primes ( p x q) = 114381625...........541 how can prime be multiple of these 'p' and 'q' ,if it really is a prime number ?
The number you get isn't a prime, that's why you can factor it.
Both P and Q are primes, and when you multiply them together you get a number whose only factors are p and q.
For example, if p were 3 and q were 7
3*7=21
the only factors to 21 are 3 and 7.
However when you have really large numbers (hundreds of digits) trying to find which 2 prime numbers multiply into that 1 number is extremely time-consuming, making them usable for encryption.