I'm currently in the process of writing my master thesis. Here gos the subject:
Displacement of smooth integers in short intervals and their applications in cryptography
Ain't it the coolest thesis ever?
To be honest, I don't quite see it that way. Anything I want to do inevitably turns into something I have to do. So this post is party a pep talk to myself. I don't think it matters, however: most Fiona Apple's songs are pep talks to herself and boy, do I love them.
Okay, back to the thesis. I will be breaking the RSA cryptosystem. Calm down, your private communication is not in danger. I will not obtain significant results, only a small speed improvement over doing it "the dumb way".
How do you break RSA anyway? The whole idea, is that multiplying two big primes is easy, but having only that result, finding out what the primes were is hard. "The dumb way" is trying all the possible primes. There are some smarter ways, but they only work in specific cases, and the keys used in the real world are wisely chosen, so the tricks don't apply. There's an excellent publication about this called "Twenty years of attacks on the RSA cryptosystem". A great read, and you can skip the formulas if you're not that into maths.
So, I will be factoring big numbers into two big prime factors. To do that, I will be using smooth numbers, which are kinda the opposite of primes: they have plenty of small factors. That part is really easy, and is well explained by Pomerance in his paper "Smooth Numbers and the Quadratic Sieve". The first two pages have it all in elementary language, the later ones are hard even for me.
To find these smooth numbers, I will be comparing three different methods: sieving, the Bernstein method and finding them using error correcting codes based on the Chinese Remainder Theorem.
More on how it goes will (most probably) come.
No comments:
Post a Comment