**The Best Number in RSA**

In the realm of cryptography, particularly in RSA, there exists a number that stands out as particularly useful and efficient. This number is none other than 2^16 + 1, which just happens to be prime. The significance of this number lies in its mathematical properties, making it an ideal choice for public keys in RSA certificates.

**Mathematical Properties**

The binary representation of this number is a mere 20 bits long, but its simplicity belies its practical applications. In RSA, the primary goal is to verify signatures and ensure the authenticity of messages. To achieve this, one must calculate a hash or representation of the message raised to a power, specifically 65537 in this case. This process involves performing repeated squaring operations, followed by a final multiplication. The presence of hardly any ones in the binary representation makes this calculation remarkably efficient.

**Speed and Security**

The speed at which RSA verification can be performed is a significant advantage over other signature schemes. By leveraging the properties of this particular number, RSA becomes an attractive choice for applications where security and efficiency are paramount. Although elliptic curve signature schemes exist, they often fall short in terms of speed and convenience.

**Private Keys and Security Concerns**

In contrast to public keys, private keys tend to be much larger and more complex. This is due to the inherent need for security; if a private key were too small, it could potentially be guessed or compromised. As a result, private keys are often generated using large numbers of bits, making RSA verification significantly slower.

**The Challenge of Large Numbers**

One of the most significant challenges in RSA lies in dealing with large numbers, particularly when it comes to private keys. The sheer size and complexity of these keys can make calculations slow and cumbersome. However, the use of efficient algorithms and techniques, such as square-and-multiply methods, can mitigate this issue.

**Variants and Optimizations**

To address concerns about security and efficiency, various variants of RSA have been developed. One notable example is the square-and-multiply algorithm, which involves performing a fixed number of multiplications and additions to ensure constant-time complexity. This allows for more secure keys without compromising performance.

In conclusion, the number 2^16 + 1 plays a crucial role in the efficiency and security of RSA algorithms. Its unique properties make it an ideal choice for public keys, while private keys require larger numbers to maintain security. By understanding the intricacies of RSA and its variants, cryptographers can create more secure and efficient cryptographic systems.

**Security Concerns and Power Analysis**

One potential vulnerability in RSA lies in the power consumption of computers used to perform calculations. If an attacker has access to the exact power consumption patterns of a computer performing RSA operations, they may be able to infer information about the private key being used. This is known as power analysis attacks.

To mitigate this issue, RSA variants such as square-and-multiply algorithms have been developed. These algorithms ensure that every operation performed on the private key remains constant-time, regardless of its size or structure. Additionally, optimizing keys with fewer ones than zeros can help minimize exposure.

**The Importance of Key Management**

In conclusion, managing RSA keys effectively is crucial for maintaining security and efficiency in cryptographic systems. By understanding the properties of this particular number and developing optimized algorithms, cryptographers can create more secure and reliable cryptographic protocols.

To ensure optimal performance and security, it's essential to carefully consider the choice of key size, algorithm, and variants. This may involve weighing factors such as speed, security, and ease of use. Ultimately, a well-designed RSA system can provide robust protection for sensitive information and transactions.

"WEBVTTKind: captionsLanguage: eni was watching a uh video on numberphile with matt in it on witness numbers and testing whether a number might or might not be a prime right super good video and at one point in the video they talk about the sum 23 to the power of 373 mods 747. that isn't something you can necessarily do on a pocket calculator so in the video you know they use wall from alpha i'm going to cheat and uh ask what from alpha yeah very reasonable i use wall from alpha all the time but actually there's a really really nice algorithm under here that i wanted to talk about today in a number file video this was about primarily testing and testing whether a number might or might not be a prime in this case actually where you you'll see this often used is in stuff like rsa public key cryptography and so actually the numbers get much much bigger than this right so you might have some number to the power of a 2000 bit number so let's say you know 600 or more digits modulo some other 2000 bit number and the mathematics is so extraordinarily vast that you can't comprehend how this could possibly be calculated the fact that we can reduce this modulo 747 so for those of you who aren't familiar with the modulus it means you divide by 747 and then find the remainder so it's a bit like a clock thing is it's exactly like a clock yeah you go all the way round to 12 when you start back at one two three it's that but obviously your numbers are bigger there's many more hours in a day even if you calculate this modulus this is still a difficult sum because you have to do 23 times 23 times 23 times 23 373 times that's that's not very fast right and it's 373 was a 600 digit number then even by taking mod there's no hope of doing this right so we need some kind of algorithm that calculates what we call an exponentiation much much faster and that is a square and multiply algorithm really neatly allowed with them i think fairly intuitive to understand um and it's used all the time in computer science whenever whenever you have a sum like this which is a lot of the time you can do it really really quickly using square and multiply now actually as it happens they picked a quite difficult sum right there there's reasons for this and we'll go into them but i'm going to pick a slightly easier sum perhaps the first thing to do is to look at how the square multiplier will work sort of an overview right and the idea is basically if we square a number we can get towards 2 23 to the 33 much more quickly right so for example suppose you were calculating 2 to the power of 8. that is 2 times 2 times 2 times 2 times 2 times 2 times 2. how many is that times 2 right now that took me a fair while to write out but actually you could save yourself a little bit of time because you could do two times two is two to the two that's two squared right then two squared times by 2 squared is 2 to the 4. it's 2 times 2 times 2 times 2 right and then if we do square this again we can go we can jump all the way up to 2 to the 4 2 to the 4 is 2 to the 8. and so we can actually do it in one two three operations we can get to two to the eight instead of this seven or eight operations if instead of multiplying by your original value every time you multiply by one of these much larger intermediate values you can much more quickly converge on the solution you want assuming it's a power of two right we haven't dealt with a slightly prickly subject of what happens if this isn't just a power of two which unfortunately cryptography is most of the time so in principle the idea is that we can sort of jump forward in powers of two or you know it's by squaring much more quickly but we need some kind of mechanism of what we do if we're not just going to get there by squaring every time what we actually do is we do something called um well in this case we're going to look at something called left to right square and multiply and the idea is we look at the exponent 373 or eight or some other number and we represent it in binary and work out what operations we're going to need to do to get to the right result i'm going to use a slightly smaller example on this otherwise we're going to have to bust out that pocket calculator so we're going to do a 3 to the power 45 mod 7. this is a strange sum because in some ways 3 to the 45 is an extremely large intermediate value so we want to reduce mod 7 as much as possible so that we keep it small otherwise we get a huge value and we end up at just a number between naught and six anyway what a waste of time that was but we can also use square and multiply to make this much faster so first thing we're going to do is work out what 45 is in binary and that's 1 0 1 0 i'm going to draw a line here so we can have some sort of delineation now a couple of things to think about is suppose we treat this exponent as binary so what we want you want to do is calculate 3 to the 101101 right whereas this is a decimal number and this is a binary number so that's slightly confusing i'm going to write a little two in here to show us it's base two but a couple of things to think about suppose you have x to the one times by x to the one that's in binary all right so x squared that's you're going to add these two ones together so you're going to get x to the one o right if you do x to the one o times x to the one o right so that's to the two times x to two you're getting x and four it's actually x to the one o o right so whenever you square a number your exponent shifts left one bit right it doubles in size and shifts left you just stick an o on the end of it a zero on the end of it right if you multiply by the original number so if you take for example x to the 100 right it's not 100 it's one zero zero if you take x to one zero zero and you multiply it by the original x that's actually just 101 so it's x to the 101. right so you've got two rules if you square a number you take its exponent and you add a zero if you multiply the original number by your intermediate result then you just add one to the exponent right and so using those two different square and multiplies we can recreate this exponent here in the minimum number of steps so it might be three squares and two multipliers exactly yeah and you have to do them in the right order as well right and so what we're going to do is we're going to build up this exponent here or this one here by doing repeated square multipliers in the correct order right so let's start with three to the one right which is three and what we want to do is now do three to the 45 mod 7. now i'm not going to calculate the actual values for a minute we can fill them in a moment right so the first thing we want to do is we want to go from 1 to 1 0 right we're going from left to right in this particular version of the algorithm so to do that we need to square it so we do three to the one times by three to the one is three to the one o right so that's actually three squared all right i'll tell you what i'll write in three squared here so we can keep a track of what the number is in decimal so this is our binary this is our decimal now we want to go from 1 0 to 101 we can't do that in one step we have to do a square first so we do 3 to 1 o 3 to the 1 0 is 3 to the 100 right that's three to the four so this is a square this is a square and now we're going to multiply and i've sort of not left myself a huge amount of room here but we won't worry about it so 3 to the 100 multiplied by 3 so the original value that we have at the top is 3 to the 101 that's 3 to the 5. all right now we know we're near 3 to the 45 yet but hopefully you can see we're sort of making some progress let's keep going so the next one we want to go from 3 to the 101 to 101 1 so we need to square again so square so that's going to be 3 to the 101 multiplied by 3 to the 101 is 3 101 0. that's 3 to the 10 right and if anyone's got their binary calculator out you can confirm my working here right let's keep going so we're going to multiply so 3 to the 101 0 multiplied by 3 is equal to three to the one oh one one so we've now built up the first four bits of our exponent we're not that far away i think so that's three to the eleven and you know 11's now we're near 45. you're talking nonsense we're nearly there right let's square that got us we've got to square it right so 3 to the 101. one multiplied by i should have just written squared but then i would have had a lot of little numbers floating about it would have got a bit confusing 101 1 is 3 to the 10110 which is 3 to the 22. we've now got the first five bits of our exponent and now we need one last bit so that's going to be a multiply um oh sorry no yeah yeah yeah my bad square skip that step we pretend that set didn't happen this is why you use libraries to do this like wall from alpha and you don't use my implementation so that's three to the one o one one o times three to the one oh one one o is three to the one oh one one o o which is 3 to the 44. now i think we're nearly there right looks pretty good we're just going to multiply one more time our intermediate value of 3 101 100 times by 3 to the 1 which is one there and that's going to be three to the one oh one one oh one which is three to the 45. just enough paper just enough paper hopefully i don't need to add to this i do actually i wanted to calculate the actual sums right but you know now so this is the this is the exact combination we want if we're doing this modular arithmetic then every time we do one of these sums we can reduce it modulo 7 and work out where it lands from 0 to 6 and that keeps our value very very small and we're also taking the exact minimum number of steps uh so it's okay to re-modular it yeah so so when you're taking modulo all of these numbers end up as equivalent and so if you take mod all the time or you take it once at the end or halfway through and then once at the end it doesn't make any difference it will just change the size of the numbers so in general it will be you do it as often as possible to keep your numbers as small as possible when you're multiplying numbers together that scales very poorly with the size of a number and so it's better to take to make them as small as possible so let's actually work through this so we can just fill them in here so if i just sort of created a little bit this is the actual number we're going to calculate here right so the first one is 3 to the 1 so that's that's our starting number here you could start at 1 and multiply by three for your first bit you know just unnecessary step right so the first thing i'm going to do is three times three which is nine mod seven is two right so that's two then this is going to be three this is going to be the intermediate value square so 2 times 2 is 4 mod 7 is also 4 right 4 times another 3 is 12 mod 7 is 5. right 5 times 5 is 25 but the next multiple of 7 below that is 21 so it's 4 is the answer right 4 mod 7 right this is not so interesting this one so this is another 4 times 3. we already did that it's 5. and when this is 5 squared we already did that it's 4. you don't usually cash your results like i'm doing here i'm cheating really finished so now 4 times 4 is 16 right the next multiple of 7 below that is 14 right so it's 2 right 2 times 3 is 6 and that's the answer so if you do 3 to the power of 45 you get some sort of quadrillion or some really large number if you take it mod 7 6 right and we've saved quite a lot of memory and quite a lot of time doing this we haven't had to do 45 multiplications we haven't had to do very large intermediate values this is super useful for cryptography let's look at 23 to the power of 373 mod 747. now i think they calculated the answer actually was 131. i've run through this just to see if it works and it does i can say that for sure wolfram alpha's code is correct on this but let's look at this 373 in binary right so that is 101 1 0 1 right which is quite long which is probably why i'm not going to run through it so we could actually i could tell you what steps we need to do so it's 23 to the 1 right that's gives us our first one then we're going to square then that will get us to here then we're going to square and multiply and that will get us the next one square and multiply that's the next one square and multiply square square and multiply square square and multiply are you starting to work out why it's called the square multiplier i think it's something to do with squaring maybe multiplication so we could run through this so so if you square 23 to the one you get 23 keep going so multiply 23 to the 23 square that 23 283 now it's getting a bit hairy for me 186 23 to the 186 square again 23 to the 200 360 72 372 uh that actually makes sense that would make sense i could have worked backwards right if only we could do that uh 23 to the 373 right so if you run through this on your calculator and calculate models time you will hopefully if you don't make a mistake end up at 131. this is actually quite a lot of steps let's see how many steps we've got here so we've got one two three four five six seven eight nine 10 11 12 13 steps and actually that makes sense because for every zero here we're going to need to do a square and for every one we're going to need to do a square followed by a multiply so it's 1 2 3 4 5 6 7 8 9 10 11 12 13. so you can see that even for sort of 2 000 bit numbers exactly how many squares and multipliers you're going to have to do is going to depend somewhat on the nature of this number and that leads us to our my last part which is i wanted to say that this is the best number that there is right so this is 6 5 5 3 7. right now i for a long time thought this is the best number now i haven't been on number file to explain why but there is no doubt in my mind this number is used as the public key which is a verification key most time in in the majority of rsa certificates right so on the web when you go anywhere and a server gives you a certificate the public key will be this number here and some large um semi-prime number n right now why is this this well if i write out the binary representation of this this is 2 to the 16 plus 1 which also happens to be prime now the reason it's useful but it's prime is because mathematically then it doesn't share any divisors with another number which perhaps we'll go into in a different video but from my point of view from this algorithm the reason this is interesting is that is the binary representation of that number in rsa if you want to verify a signature one of the things you'll do beyond checking padding and a lot of other stuff is you will calculate some message or some hash of a message or some representation of a message to the power of 655.37 right and that's going to be slow except it's not slow because there's hardly any ones in here all right it's just you start with one anyway you do a bunch of squares and then you do one final multiplication at the end and you can verify very very quickly and that's actually one of the reasons why rsa is so popular right um even though elliptic curve signature schemes and other signature schemes exist it's hard to beat the sheer speed of that verification process which is what you have to do every time you go on a website or anything like this so it's a super useful function from a verification point of view this is nice and efficient now unfortunately private keys tend to be much much bigger than this um because otherwise they wouldn't be very secure because you could guess them um so you are going to be doing something like your message to the power of or some message to the power of a 2000 bit number right but on average you're going to do what sort of 2000 bits so that's 2 000 squares and then maybe half of them on average of ones so it's maybe like one and a half the bit length so maybe it's about 3 000 squares or multiplies which on a modern computer is not so bad it's not it's not trivial right these are big big sums but it's not ridiculous to imagine you could do it consider it if you did it the naive way where you did the message times by the message times by the message two to the two thousand times you would never finish in the lifetime of the universe kind of kind of deal so um it's perhaps good that we have this um the only other thing i should mention by the way before uh someone corrects me in the comments is if you use this for a private key the problem you've got then is that the speed of your algorithm and indeed how you know even things like the power of your algorithm on the on the cpu is dependent on what the private key is right because you're going to be doing different amounts of square and multiply at different times depending on the key and so you leave yourself quite vulnerable to something like power analysis where you can look at how much power drain there is on the cpu and you can see it go up for a square minute from multiplying up to a square an upper model and actually just read off the key right and the other thing is that keys with lots of zeros will be quicker to use than keys with lots of ones in and we don't really want to give away whether your key has a lot of zeros or a lot of ones and so actually there are variants of this algorithm like the square always multiply where you do some sort of multiplication every time and it's restructured in such a way as to be constant time so that you don't have that issue of if someone accidentally has a key that has fewer ones than zeros or something you know it changes how long it takes but because we can mod it by n each time we're never going to have a number any point that's bigger than 747 so each time we multiply 23 by 23 by 23 by 23 we just keep modding by uh 747 and when that space what it's doing is it's looking for extra areas where it can add the nodes to build that graph upi was watching a uh video on numberphile with matt in it on witness numbers and testing whether a number might or might not be a prime right super good video and at one point in the video they talk about the sum 23 to the power of 373 mods 747. that isn't something you can necessarily do on a pocket calculator so in the video you know they use wall from alpha i'm going to cheat and uh ask what from alpha yeah very reasonable i use wall from alpha all the time but actually there's a really really nice algorithm under here that i wanted to talk about today in a number file video this was about primarily testing and testing whether a number might or might not be a prime in this case actually where you you'll see this often used is in stuff like rsa public key cryptography and so actually the numbers get much much bigger than this right so you might have some number to the power of a 2000 bit number so let's say you know 600 or more digits modulo some other 2000 bit number and the mathematics is so extraordinarily vast that you can't comprehend how this could possibly be calculated the fact that we can reduce this modulo 747 so for those of you who aren't familiar with the modulus it means you divide by 747 and then find the remainder so it's a bit like a clock thing is it's exactly like a clock yeah you go all the way round to 12 when you start back at one two three it's that but obviously your numbers are bigger there's many more hours in a day even if you calculate this modulus this is still a difficult sum because you have to do 23 times 23 times 23 times 23 373 times that's that's not very fast right and it's 373 was a 600 digit number then even by taking mod there's no hope of doing this right so we need some kind of algorithm that calculates what we call an exponentiation much much faster and that is a square and multiply algorithm really neatly allowed with them i think fairly intuitive to understand um and it's used all the time in computer science whenever whenever you have a sum like this which is a lot of the time you can do it really really quickly using square and multiply now actually as it happens they picked a quite difficult sum right there there's reasons for this and we'll go into them but i'm going to pick a slightly easier sum perhaps the first thing to do is to look at how the square multiplier will work sort of an overview right and the idea is basically if we square a number we can get towards 2 23 to the 33 much more quickly right so for example suppose you were calculating 2 to the power of 8. that is 2 times 2 times 2 times 2 times 2 times 2 times 2. how many is that times 2 right now that took me a fair while to write out but actually you could save yourself a little bit of time because you could do two times two is two to the two that's two squared right then two squared times by 2 squared is 2 to the 4. it's 2 times 2 times 2 times 2 right and then if we do square this again we can go we can jump all the way up to 2 to the 4 2 to the 4 is 2 to the 8. and so we can actually do it in one two three operations we can get to two to the eight instead of this seven or eight operations if instead of multiplying by your original value every time you multiply by one of these much larger intermediate values you can much more quickly converge on the solution you want assuming it's a power of two right we haven't dealt with a slightly prickly subject of what happens if this isn't just a power of two which unfortunately cryptography is most of the time so in principle the idea is that we can sort of jump forward in powers of two or you know it's by squaring much more quickly but we need some kind of mechanism of what we do if we're not just going to get there by squaring every time what we actually do is we do something called um well in this case we're going to look at something called left to right square and multiply and the idea is we look at the exponent 373 or eight or some other number and we represent it in binary and work out what operations we're going to need to do to get to the right result i'm going to use a slightly smaller example on this otherwise we're going to have to bust out that pocket calculator so we're going to do a 3 to the power 45 mod 7. this is a strange sum because in some ways 3 to the 45 is an extremely large intermediate value so we want to reduce mod 7 as much as possible so that we keep it small otherwise we get a huge value and we end up at just a number between naught and six anyway what a waste of time that was but we can also use square and multiply to make this much faster so first thing we're going to do is work out what 45 is in binary and that's 1 0 1 0 i'm going to draw a line here so we can have some sort of delineation now a couple of things to think about is suppose we treat this exponent as binary so what we want you want to do is calculate 3 to the 101101 right whereas this is a decimal number and this is a binary number so that's slightly confusing i'm going to write a little two in here to show us it's base two but a couple of things to think about suppose you have x to the one times by x to the one that's in binary all right so x squared that's you're going to add these two ones together so you're going to get x to the one o right if you do x to the one o times x to the one o right so that's to the two times x to two you're getting x and four it's actually x to the one o o right so whenever you square a number your exponent shifts left one bit right it doubles in size and shifts left you just stick an o on the end of it a zero on the end of it right if you multiply by the original number so if you take for example x to the 100 right it's not 100 it's one zero zero if you take x to one zero zero and you multiply it by the original x that's actually just 101 so it's x to the 101. right so you've got two rules if you square a number you take its exponent and you add a zero if you multiply the original number by your intermediate result then you just add one to the exponent right and so using those two different square and multiplies we can recreate this exponent here in the minimum number of steps so it might be three squares and two multipliers exactly yeah and you have to do them in the right order as well right and so what we're going to do is we're going to build up this exponent here or this one here by doing repeated square multipliers in the correct order right so let's start with three to the one right which is three and what we want to do is now do three to the 45 mod 7. now i'm not going to calculate the actual values for a minute we can fill them in a moment right so the first thing we want to do is we want to go from 1 to 1 0 right we're going from left to right in this particular version of the algorithm so to do that we need to square it so we do three to the one times by three to the one is three to the one o right so that's actually three squared all right i'll tell you what i'll write in three squared here so we can keep a track of what the number is in decimal so this is our binary this is our decimal now we want to go from 1 0 to 101 we can't do that in one step we have to do a square first so we do 3 to 1 o 3 to the 1 0 is 3 to the 100 right that's three to the four so this is a square this is a square and now we're going to multiply and i've sort of not left myself a huge amount of room here but we won't worry about it so 3 to the 100 multiplied by 3 so the original value that we have at the top is 3 to the 101 that's 3 to the 5. all right now we know we're near 3 to the 45 yet but hopefully you can see we're sort of making some progress let's keep going so the next one we want to go from 3 to the 101 to 101 1 so we need to square again so square so that's going to be 3 to the 101 multiplied by 3 to the 101 is 3 101 0. that's 3 to the 10 right and if anyone's got their binary calculator out you can confirm my working here right let's keep going so we're going to multiply so 3 to the 101 0 multiplied by 3 is equal to three to the one oh one one so we've now built up the first four bits of our exponent we're not that far away i think so that's three to the eleven and you know 11's now we're near 45. you're talking nonsense we're nearly there right let's square that got us we've got to square it right so 3 to the 101. one multiplied by i should have just written squared but then i would have had a lot of little numbers floating about it would have got a bit confusing 101 1 is 3 to the 10110 which is 3 to the 22. we've now got the first five bits of our exponent and now we need one last bit so that's going to be a multiply um oh sorry no yeah yeah yeah my bad square skip that step we pretend that set didn't happen this is why you use libraries to do this like wall from alpha and you don't use my implementation so that's three to the one o one one o times three to the one oh one one o is three to the one oh one one o o which is 3 to the 44. now i think we're nearly there right looks pretty good we're just going to multiply one more time our intermediate value of 3 101 100 times by 3 to the 1 which is one there and that's going to be three to the one oh one one oh one which is three to the 45. just enough paper just enough paper hopefully i don't need to add to this i do actually i wanted to calculate the actual sums right but you know now so this is the this is the exact combination we want if we're doing this modular arithmetic then every time we do one of these sums we can reduce it modulo 7 and work out where it lands from 0 to 6 and that keeps our value very very small and we're also taking the exact minimum number of steps uh so it's okay to re-modular it yeah so so when you're taking modulo all of these numbers end up as equivalent and so if you take mod all the time or you take it once at the end or halfway through and then once at the end it doesn't make any difference it will just change the size of the numbers so in general it will be you do it as often as possible to keep your numbers as small as possible when you're multiplying numbers together that scales very poorly with the size of a number and so it's better to take to make them as small as possible so let's actually work through this so we can just fill them in here so if i just sort of created a little bit this is the actual number we're going to calculate here right so the first one is 3 to the 1 so that's that's our starting number here you could start at 1 and multiply by three for your first bit you know just unnecessary step right so the first thing i'm going to do is three times three which is nine mod seven is two right so that's two then this is going to be three this is going to be the intermediate value square so 2 times 2 is 4 mod 7 is also 4 right 4 times another 3 is 12 mod 7 is 5. right 5 times 5 is 25 but the next multiple of 7 below that is 21 so it's 4 is the answer right 4 mod 7 right this is not so interesting this one so this is another 4 times 3. we already did that it's 5. and when this is 5 squared we already did that it's 4. you don't usually cash your results like i'm doing here i'm cheating really finished so now 4 times 4 is 16 right the next multiple of 7 below that is 14 right so it's 2 right 2 times 3 is 6 and that's the answer so if you do 3 to the power of 45 you get some sort of quadrillion or some really large number if you take it mod 7 6 right and we've saved quite a lot of memory and quite a lot of time doing this we haven't had to do 45 multiplications we haven't had to do very large intermediate values this is super useful for cryptography let's look at 23 to the power of 373 mod 747. now i think they calculated the answer actually was 131. i've run through this just to see if it works and it does i can say that for sure wolfram alpha's code is correct on this but let's look at this 373 in binary right so that is 101 1 0 1 right which is quite long which is probably why i'm not going to run through it so we could actually i could tell you what steps we need to do so it's 23 to the 1 right that's gives us our first one then we're going to square then that will get us to here then we're going to square and multiply and that will get us the next one square and multiply that's the next one square and multiply square square and multiply square square and multiply are you starting to work out why it's called the square multiplier i think it's something to do with squaring maybe multiplication so we could run through this so so if you square 23 to the one you get 23 keep going so multiply 23 to the 23 square that 23 283 now it's getting a bit hairy for me 186 23 to the 186 square again 23 to the 200 360 72 372 uh that actually makes sense that would make sense i could have worked backwards right if only we could do that uh 23 to the 373 right so if you run through this on your calculator and calculate models time you will hopefully if you don't make a mistake end up at 131. this is actually quite a lot of steps let's see how many steps we've got here so we've got one two three four five six seven eight nine 10 11 12 13 steps and actually that makes sense because for every zero here we're going to need to do a square and for every one we're going to need to do a square followed by a multiply so it's 1 2 3 4 5 6 7 8 9 10 11 12 13. so you can see that even for sort of 2 000 bit numbers exactly how many squares and multipliers you're going to have to do is going to depend somewhat on the nature of this number and that leads us to our my last part which is i wanted to say that this is the best number that there is right so this is 6 5 5 3 7. right now i for a long time thought this is the best number now i haven't been on number file to explain why but there is no doubt in my mind this number is used as the public key which is a verification key most time in in the majority of rsa certificates right so on the web when you go anywhere and a server gives you a certificate the public key will be this number here and some large um semi-prime number n right now why is this this well if i write out the binary representation of this this is 2 to the 16 plus 1 which also happens to be prime now the reason it's useful but it's prime is because mathematically then it doesn't share any divisors with another number which perhaps we'll go into in a different video but from my point of view from this algorithm the reason this is interesting is that is the binary representation of that number in rsa if you want to verify a signature one of the things you'll do beyond checking padding and a lot of other stuff is you will calculate some message or some hash of a message or some representation of a message to the power of 655.37 right and that's going to be slow except it's not slow because there's hardly any ones in here all right it's just you start with one anyway you do a bunch of squares and then you do one final multiplication at the end and you can verify very very quickly and that's actually one of the reasons why rsa is so popular right um even though elliptic curve signature schemes and other signature schemes exist it's hard to beat the sheer speed of that verification process which is what you have to do every time you go on a website or anything like this so it's a super useful function from a verification point of view this is nice and efficient now unfortunately private keys tend to be much much bigger than this um because otherwise they wouldn't be very secure because you could guess them um so you are going to be doing something like your message to the power of or some message to the power of a 2000 bit number right but on average you're going to do what sort of 2000 bits so that's 2 000 squares and then maybe half of them on average of ones so it's maybe like one and a half the bit length so maybe it's about 3 000 squares or multiplies which on a modern computer is not so bad it's not it's not trivial right these are big big sums but it's not ridiculous to imagine you could do it consider it if you did it the naive way where you did the message times by the message times by the message two to the two thousand times you would never finish in the lifetime of the universe kind of kind of deal so um it's perhaps good that we have this um the only other thing i should mention by the way before uh someone corrects me in the comments is if you use this for a private key the problem you've got then is that the speed of your algorithm and indeed how you know even things like the power of your algorithm on the on the cpu is dependent on what the private key is right because you're going to be doing different amounts of square and multiply at different times depending on the key and so you leave yourself quite vulnerable to something like power analysis where you can look at how much power drain there is on the cpu and you can see it go up for a square minute from multiplying up to a square an upper model and actually just read off the key right and the other thing is that keys with lots of zeros will be quicker to use than keys with lots of ones in and we don't really want to give away whether your key has a lot of zeros or a lot of ones and so actually there are variants of this algorithm like the square always multiply where you do some sort of multiplication every time and it's restructured in such a way as to be constant time so that you don't have that issue of if someone accidentally has a key that has fewer ones than zeros or something you know it changes how long it takes but because we can mod it by n each time we're never going to have a number any point that's bigger than 747 so each time we multiply 23 by 23 by 23 by 23 we just keep modding by uh 747 and when that space what it's doing is it's looking for extra areas where it can add the nodes to build that graph up\n"