She could even place them on the local billboard if she wanted to. Let’s suppose Alice chooses e=5.ģ) Alice then gives the numbers N=493 and e=5 to Bob. Then e is just any number which, when broken down into primes, does not possess a 2 or a 7 as a factor. To see what I mean, we can break 448 into a bunch of prime numbers multiplied together: The number e is allowed to be any number, which has no factors in common with this new number 448.
This gives her:Īlice then multiplies these two together to get: She creates this number first by subtracting 1 off of each of her prime numbers p and q. Let’s say she picks p=17 and q=29 (though in reality they would be much larger so as to ensure better security).Īlice then multiplies p and q together to get the number N:Ģ) Alice also needs to generate another number e. Of course, the RSA algorithm deals with sending numbers, but seeing as any text can be converted to digits in a variety of ways, we can securely transmit information of any type.Īlso, I will use small prime numbers in this example, just to ease the calculations.ġ) Alice knows that Bob wants to send her a message, so she selects two prime numbers. To illustrate this beautiful piece of mathematics, we can return to our fictional lovers.īob wants to encrypt and send Alice his age – 42. It turns out the numbers N and e can be used by people to encrypt a message to send to me, which I can use my secret primes p and q to decrypt. I publish these two numbers (N,e) as my “public key”, with the knowledge that there is enormous difficulty with even the world’s fastest computers breaking N into its constituent prime atoms p and q. I also combine p and q in a different way to generate another number e (details of this below). Crunching the numbersįirst, I find two huge (at least 100 digits each!) prime numbers p and q, and then I multiply them together to get the even bigger number N. The mathematical difficulty of the above problem is what ensures the strength of our encryption (or lock). Which two prime numbers did I multiply together to get 194477? A computer can probably unlock this number easily, but not if the prime numbers I use are much larger. This is called a trapdoor, meaning it’s easy to go one way, but very hard to go the other. It’s easy for a computer to multiply two large prime numbers together (Google will do this without breaking a sweat).īut let’s say you multiply two large prime numbers together to get a resulting number: if you gave this new number to a computer and asked it to tell you what prime numbers you multiplied to construct it, the computer would struggle. The algorithm’s design and strength are the work of historic results in number theory, and its security is guaranteed by the following fact: Now we get into the RSA algorithm, which is the strongest possible way to encrypt and decrypt information online. So how do we know Alice and Bob’s online communications aren’t being monitored by Eve? These days, of course, more people opt for email rather than snail mail.
This will be a safe transmission, seeing as Bob is the only one with the key.īut what a complicated way of securing information: for people to receive secret messages, they need to have public padlocks available to everybody!
If Alice wants to send Bob a secret message, she simply needs to go to Bunnings and get one of these open padlocks, then use it on the box she wants to send Bob. Bob unlocks all of these padlocks and makes them available at, say, Bunnings. One solution to this problem runs in parallel with the RSA algorithm.īob knows people (Alice, in particular) want to send him secret messages, so he goes out and buys a stack of identical padlocks, all of which open with a single key he keeps hidden in his left shoe.
0 kommentar(er)
