Alright, so let's take a look at an example of how we might use LLL, yes, and this hack on RSA. So to keep this example reasonably comprehensible, we'll use an exponent, public exponent of E equal to 3, and a public modulus of this number, and assume that our message is of the form 51, 80 plus x, where x is the number between 0 and 9, and suppose we've intercepted a ciphertext that looks like this. Again, you can think about our messages as being, well, in this case, it's a four-digit number, where you know the first three digits, and the only question is what that last digit is going to be. So the problem of recovering the original plaintext message corresponds to solving the congruent ciphertext, congruent to 51, 80 plus x, to power 3 mod that. And so if I were to expand and simplify, if I could solve this congruence, then I can recover what the value of x is. Well, again, if that were an equality, this would be no problem. The problem is that it's a congruent. So I'll hit this with a lattice method. So I have my congruence. I know that x has a maximum possible value of 9. I know the modulus. So what can I do here? Well, I'll take a look at the lattice that corresponds to this equation, congruent, and so that lattice is going to have basis. First vector is going to be the modulus n with all zeros after that. Second basis vector, zero maximum times the modulus, and then zeros in the remaining places. Third vector, again, we could think about this as constant coefficient, linear coefficient, square coefficient. So that's going to be m squared, maximum squared times our modulus, zero in the remaining possession. And our last vector is going to be the coefficients of our polynomial, multiplied by the appropriate power of our maximum value. So I have my constant term. I have my linear term times the maximum. I have my square term times the square of the maximum. And then I have my cubic term, cubic coefficient, times the cube of the maximum value. And so now I have a lattice that's going to be spanned by this set of four vectors. And the key here is that every point in this lattice corresponds to an equation that is associated with, not the same as because we've done the scaling, but is associated with this particular congruent. And some place in this lattice is an equation whose solution will also be the solution to this. Now, we can then try to apply the shortest vector problem, we can then try to solve the shortest vector problem for this lattice. And in that case, under the right conditions, we'll then be able to recover a solution to this. Now, we won't go into the details of what those right conditions are here, but notice that the maximum possible value of x is much smaller than any of the coefficients or components of our different vectors in our lattice basis. So I have my lattice basis. I apply LLL to get my new lattice basis of quasi-orthogonal vectors. And the only one I actually need, I get the entire set, but the only one I actually need is that first basis vector because that first basis vector is going to give us an approximate solution to the shortest vector problem. And if I find that my first lattice basis vector looks like this, and so from here I can reconstruct a polynomial whose roots will hopefully give me some insight into these solutions to the original congruence. So what does that polynomial look like? Well, again, we can think about this as linear component, linear coefficient, x coefficient, x squared coefficient, x cubed coefficient. Now, since we've scaled our equations by this factor m, 9, the maximum value of x, maximum possible value of x, we have to scale them back. So my actual coefficients are going to be cubic coefficient over m cubed, which we then reduced, and that's our cubic coefficient. So again, constant linear square coefficient. So that's our square coefficient over the square of our maximum value, our linear coefficient over the maximum value. Again, this is a scale factor that represents the largest possible value of x for our solution.  And I have this nice equation, and because it is an equation, not a congruence, I can solve this in any number of ways. The most useful is I can apply some numerical analysis to it, and I find three solutions which look like that. Now, remember that x has to be a positive integer in the interval 0 to 9. So the only one that none of these are integers, obviously, but my rounded value, this gives me an integer in this interval 0 to 9. And so I'm going to take x equals 8 as a potential solution to my original congruence. Now, some quick notes about this. Remember that while this v1 is an approximate solution to the shortest vector problem, it's not guaranteed to be a good solution, which means we have to verify our actual solution. What that translates to in this case is that we find that if x is 8, then this does in fact satisfy our congruence. So our candidate solution, x equals 8, is actually the correct solution because it gives us the correct encrypted value. Again, while we solve the polynomial equations, we might not get whole numbers, and this is not a problem. We'll use our rounded values as our potential solutions. And finally, one last note, the exponent e corresponds to the number of basis vectors for our lattice. And so that we can apply the approach any time that we can solve the corresponding shortest vector problem. Now, again, LLL works fairly effectively for lattices with up to about 100 basis vectors. So this will give us potential solutions for e less than about 100 or so, which is why this is known as a low exponent attack. If your exponent is low on the order of about 100 or so, then this could conceivably work against it. So what do you do with an RSA system? Well, you use a high exponent so you don't have to worry about this type of threat.


I was sitting on the couch in the basement, scrolling mindlessly through the endless library of context on Netflix. When the text came, it had been sent from an unknown number and read, Whatever you do, don't leave the basement. Lock the door, turn off the lights, you are in grave danger. Do not leave the basement. At first, I thought it was a prank text, some punk texting numbers at random, hoping to scare someone. But at the same time, it was a little strange how they knew I was in my basement. After all, someone who was texting this to random numbers wouldn't be able to tell if the person they were pranking even had a basement. I inadvertently shot a quick glance at the small basement window. Nothing, not a soul in sight. I decided to ignore the message, figuring whoever it was had simply gotten lucky and it texted someone who happened to be in their basement. However, less than a minute later, I got another text. It is urgent that you heed this warning, close and lock the door, turn off all lights and silence all electronics. And whatever you do, don't leave your basement. I swallowed.  I was beginning to feel worried, but a quick glance at the window proved that no one was watching me, or at least that no one was there now. I stood up, turned off the big screen and stretched. I decided to get a little sleep in before I had to go in for work that night. As I walked up the stairs, however, the text started. My phone began vibrating nonstop, receiving text after text after text. As I reached the top step, I pulled out my phone to see who they were from. The text had all come from that same unknown number, saying things like, do not leave your basement. It is imperative that you stop moving right now and turn off the lights. Your life is in danger, don't move. Please, this is for your own good, do not leave the basement.  The basement doorway loomed in front of me, showing the dark expanse of my kitchen. I hadn't realized that the sky had become overcast. I cautiously took a step into the kitchen. My phone buzzed again, but I ignored it. Whoever was texting had to be playing some sort of prank, though I wasn't finding it very funny. The floorboard creaked beneath my foot as I stepped out into the kitchen. Suddenly, a flash of lightning lit up the gray sky, and almost immediately, the rumble of thunder followed. I shivered, but continued to walk. Then, I heard a loud creak. However, this time, it didn't come from under my foot. In fact, it didn't come from a floorboard at all. This creak came from my door. The sound was the unmistakable noise of the front door opening slowly, as if whoever was opening it was attempting to do it quietly. As soon as the door opened, I got another text. I didn't bother to get out my phone, just leap down into my basement and close the door. I locked it, then strung the chain, and even carried a heavy chair up to barricade the door, but I still didn't feel safe. I carefully crept down the stairs and sat down on an old chair, pulling my phone out of my pocket to read the last few messages. The first one read, For God's sake, please don't leave. The most recent one read, Now you have been chosen. Do not trust anyone, and don't leave the basement. I have been chosen.  Finally, I did what I should have done in the first place. I texted the unknown number back. Listen, I don't know what's going on and I'm not sure that I want to find out.  I don't want to be any part of this. They didn't respond. Suddenly, I heard a sound coming from behind the basement door, a creak, the sound of pressure being placed upon a floorboard. Then I heard the sound of the doorknob being jiggled. I froze, it jiggled again and again. Every small noise coming from beyond the locked door of the basement filled me with terror paralyzing me. I looked around the small basement for anything that could remotely be considered a weapon. The room was, unfortunately, mostly empty, with the closest thing to a self-defense tool being the remote for the TV. I grabbed it and crouched down in the corner of the room. My breathing felt too loud.  The cold basement seemed to close in around me. I started imagining sounds, at least I thought I was imagining them. I began hearing footsteps, voices, whispers. They echoed around me. I heard yells coming from outside my house, then screams, then silence. After what felt like an hour, the sound stopped. I breathed a sigh of relief, maybe it was all in my head after all. Then I heard a knock on the basement window. As previously mentioned, the basement window is small, in fact I could barely see out of it. However, I was able to catch a glimpse of something outside darting past it. I mustered up every last drop of courage in me and weakly yelled, Who's there? A few moments of silence followed, then a voice replied, Oh, just a traveler seeking shelter from the storm. The voice sounded male and somewhat strained like he was speaking through gritted teeth. Who the hell would be out here in the middle of the rain? I live in a rural area in the middle of nowhere. I don't have any neighbors and the nearest grocery store is half an hour's drive away. Something was wrong. I'm sorry, but I can't let you in. Oh, why not? The voice replied, I didn't answer. The text and the sounds in my house seemed a little too real to be part of some elaborate prank. Instead, I shifted a little to my right just out of view from the window for anyone looking inside the house from the yard. God, I did that because a few seconds after I did, something leaned over and peered into the dark basement. It's impossible to describe the thing in the window simply because I could hardly see it. The dust and dirt combined with the size of the window made it difficult to make out what was staring at me. All that I could see were two solid red eyes looking around inside my basement. Two small black pupils glanced around, attempting to find me. I placed my head between my knees and tried to steady my breathing. It's been 48 hours since then. I've been living off potato chips and energy drinks down in my basement. I'm running out and I know soon I'll have to leave to get more food. I've spent the past couple of days sitting in the dark listening to the sounds of footsteps and knocking on my doors. It's maddening, but there's nothing I can do. I've tried calling the cops and I've tried calling the place I work at. I have a signal, but for some reason it never works.  I'm terrified and I don't know what to do. If anyone's out there and you can hear this, please, please, if you receive an odd message from an unknown number, listen to what it says.