PDA

View Full Version : A couple of questions that someone might know the answer to...



Finchie_88
04-14-2005, 03:13 PM
Please note, I am not doing this to steal bank details, just for academic interest and a challenge, so please don't look at these questions in the wrong light. I have no interest in use of this on the internet, its just me setting myself a challenge. :D

I thought of a really interesting idea when reading about RSA encryption. I've tried it out with a small key value, and using a very perculiar technique, managed to get the values of the primes that made it up (starting only with the public key). I've tried the same technique with a few other key values, and have been successful 100% of the time. I thought that if the technique worked with small numbers, then maybe it would work with larger numbers.

Here are my questions:

1. Other than using brute force, has anyone managed to break the RSA encryption cipher yet?
2. What is the maximum number of digits that a number can consist of before calculations on that number can't occur (in terms of a computer program, providing that the computer has no special hardware on it)?

MadCow257
04-14-2005, 03:18 PM
I thought of a really interesting idea when reading about RSA encryption. I've tried it out with a small key value, and using a very perculiar technique, managed to get the values of the primes that made it up (starting only with the public key). I've tried the same technique with a few other key values, and have been successful 100% of the time. I thought that if the technique worked with small numbers, then maybe it would work with larger numbers.

I'm always interested in things like that. Would you care to post your idea? Sadly, we'll most likely find a flaw quickly :)




1. Other than using brute force, has anyone managed to break the RSA encryption cipher yet?

We can do a whole lot better than brute force with things like the Number Field Sieve



2. What is the maximum number of digits that a number can consist of before calculations on that number can't occur (in terms of a computer program, providing that the computer has no special hardware on it)?

Depends on the system, but in general, it really doesn't matter. The time it takes to perform the calculations is going to limit you before you run out of RAM or whatever.

Finchie_88
04-14-2005, 03:25 PM
lol, like the idea bout posting it, but for now, I think i'll keep it to myself, that is until I get a patent on the idea (lol, only joking). Anyway, its only in the development stage, and with numbers in the region of 10^300, there is a big chance it won't work.
2. How does that number sieve thing work, and by how much does that improve the code breaking process?

MadCow257
04-14-2005, 03:34 PM
How does that number sieve thing work

Too hard to explain, sorry, and to be honest, I don't even fully understand it myself :)
Too get kind of an idea of how it works read http://www.std.org/~msm/common/nfspaper.pdf



and by how much does that improve the code breaking process?

Tons, I think brute force would likely take longer than the universe has been around (according to the theory of evolution) while the nfs might be able to complete it in less than a year (with enough machines working at it that is).

Sang-drax
04-15-2005, 03:04 AM
I think it has been proven that factorizing primes is 'computationally hard', to some extent.

Post your idea, otherwise this discussion is pointless.

Salem
04-15-2005, 07:46 AM
Mmm, so much which could have been answered by simply typing a few words into google.

> then maybe it would work with larger numbers.
Of course it would "work", if your algorithm is correct.
Whether it is "practical" or not (like doesn't take all the energy in the universe to complete) is another matter.

joshdick
04-15-2005, 08:26 AM
I personally recommend An Introduction to Cryptography (http://www.amazon.com/exec/obidos/tg/detail/-/1584881275/qid=1113575017/sr=1-1/ref=sr_1_1/104-2412105-6023957?v=glance&s=books). It was my textbook for a cryptography course, and I thought it was pretty good -- not too hard and not too easy.

Not only would it be a good idea to really read up on RSA and other public-key cryptosystems, but you'd probably also be interested in other topics covered in the book.