|
|
|
|
|
|
by JPLeRouzic
2552 days ago
|
|
|
I am not a scientist, but in my team 15 years ago, many people much more talented than me were in love with public cryptography.
For them encryption with a 1024 key was perfect, impossible to break. They did not even considered that several RSA challenges had already been found. Even if I had no education in mathematics I tried to show that in fact it was feasible to factor some enough large numbers with "bc" (using square root and a few other simple tricks) so the risk of having encryption broken by professionals was quite serious. My boss asked to another guy for its advice, which was essentially that for a start he would not try to break any encryption scheme anyway. And that was the end of the story. The unstated lesson was probably that there were no reason to expect a career boost by working on such topics. |
|
|
At the time when 1024-bit numbers used in RSA were 'perfect', it was infeasible to factor the number in a reasonable amount of time. The most straightforward approach is just to iterate over integers from 2 to your target number (call it n), and see if anything divides evenly. Now, you start looking for shortcuts. First, you can test only half the numbers, because the second half will give identical results (e.g. n=20, n/2 = 10; later, n/10 = 2; no need to even test the second half of the range.) Next, it becomes obvious that we only care about odd numbers (if it's divisible by an even number, it's divisible by two); but really, when it comes down do it, we only care about prime factors (for one thing, all non-primes can be decomposed into prime factors; for another, we used prime numbers to get n.) And lastly, for the simple shortcuts, you really only have to get to int(sqrt(n)) + 1 or so. So we've cut down the number of integers we have to divide with.
Did we find the two prime factors of our n in a "reasonable" time? If so, just double the bit length to get a problem twice as hard. Every publicly-known shortcut to factoring large numbers just means you need to make your n larger to increase the workload on an attacker.
The question then becomes: has anyone found a shortcut that will factor any number within a "reasonable" time? We don't know.
As to your career-related comments, I read cluelessness from your boss, and carelessness from the 'other guy' - if OG "would not try to break any encryption scheme," then he's not the person whose advice you want about the strength of cryptosystems. Your boss just lacked critical thinking skills.