mersenneforum.org Does it worth it?
 Register FAQ Search Today's Posts Mark Forums Read

 2009-03-14, 12:06 #2 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 3·1,423 Posts I'm sure other people are more qualified to answer this better than me, but no matter how good factoring algorithms get, you can always simply make the numbers larger and so harder to crack. e.g. we currently usually use 128- or 256-bit encryption, and even if an algorithm to easily crack 1024-bit encryption is discovered, we can just go to 4096-bit and make it that much harder; for comparison, the largest RSA number that's been factored is 200 decimal digits, (663-bit) but that was in '05. Also, the first two reasons in this list of why to find large primes could probably be applied to factoring large numbers: http://primes.utm.edu/notes/faq/why.html Happy Pi Day! Last fiddled with by Mini-Geek on 2009-03-14 at 12:11
 2009-03-14, 12:36 #3 alpertron     Aug 2002 Buenos Aires, Argentina 5×277 Posts Well, the RSA algorithm is based on the ignorance of algorithms to factor big numbers quickly. Since there is no proof that such an algorithm does not exist the people who uses RSA (almost everybody on Internet) do that at their own risk.
 2009-03-14, 14:39 #4 CRGreathouse     Aug 2006 3·1,993 Posts There are other encryption schemes beside RSA, most of which don't rely on factoring.
2009-03-14, 16:29   #5

"Richard B. Woods"
Aug 2002
Wisconsin USA

769210 Posts

Quote:
 Originally Posted by victor Back to the point, there may be a way to easily factor numbers, but what are the consequences of the solution? From what I have wained speaking to my friend Victor about the potential results of such a finding, the only thing he could think of at the time as practical application of this solution was the destruction of the strongest encryption systems available.
But not everyone would follow-up discovery of such a flaw the same way. Some folks would use that knowledge to strengthen the schemes.

Quote:
 Are these not what keep the electronic world safe from massive cyber-terrorism? Firstly, I completely understand the potential good of fundamental research, as it may in time hold answers to questions that will lead towards the general improvement of the human condition and of our position in the world around us; however, in this particular case, the only practical application seems at the very least, troubling. Upon hearing the question, does anyone else find this disquieting? Does anyone have a better idea?
I think it might be more useful to view the search for faster factoring methods as being, partly, an ongoing test-probe of current encryption methods, by persons of good will, with the purpose of finding any flaws before the "bad guys" do.

If one depends on simply a lack of knowledge about flaws for insuring the strength of a security system, one is likely to be very rudely awakened someday to find that someone else, not satisfied with ignorance, searched for flaws anyway. A reliance on ignorance to prevent penetration of a security system is rightly scorned as "security through obscurity".

Instead, proper security includes an ongoing search for flaws in what has been set up so far. If those who are interested in preserving security diligently engage in that search, they are more likely to find such a flaw before those whose interests oppose theirs. One should always assume that people who are interested in penetrating a security system are actively looking for flaws in that system, and will eventually find one if one exists -- that is, if that flaw is not first found by folks who will use that knowledge to devise a way to strengthen the system and eliminate the flaw before anyone else takes advantage of it.

Quote:
 Secondly, does it seem reasonable that any person carrying out fundamental research do a moral and ethical assessment of the applications of a solution before one is found?
Yes, it does ... but don't forget that such an assessment may find "good" applications as well as "bad" ones. The pessimistic view is not necessarily the only or best view.

 2009-03-17, 16:03 #6 jasonp Tribal Bullet     Oct 2004 354310 Posts The ethical implications are something that everyone who works in the field should think about carefully. Nonetheless, there are a few things to realize: - finding a factoring algorithm that breaks RSA will not destroy electronic commerce. Bruce Schneier writes in his older book Secrets and Lies that paying for stuff on the internet with credit cards is something people will do whether it's protected or not, and in fact E-commerce has flourished even in the absence of good crypto. PKI specifically requires E-commerce, but the reverse is definitely untrue. Credit cards get stolen today even if protected by RSA, and in fact you should assume your credit cards are already stolen but there are so many other stolen ones ahead of yours that you can use yours without fear (and limited liability anyway) - the same applies to banking transactions. It's ridiculous how much of the banking system basically relies on trusting everyone, even with things like SSL involved. Anybody who receives a check from you can basically help themselves to the contents of your bank account. Once again, people don't do business with banks because the encryption is there, but because people aren't responsible for losses due to fraud. - somewhat more worrisome is the effect breaking RSA will have on the ability of authoritarian regimes to spy on their citizens' communications. However, even today when things like VOIP products have essentially unbreakable encryption, there are commercial products that anyone can buy which will simply drop encrypted traffic. The end result is the same: if you were hoping for privacy, you're not going to get it, and that's irrespective of number theory research. - finally, military stuff does rely on security through obscurity, in addition to being good crypto. The algorithms that protect soldiers' lives, and classified information, are themselves classified. Basically, the factoring field is just like other branches of computational number theory except that it happens to have a very high-profile application. But nobody who works in that field is seriously courting electronic disaster. If our world was that fragile, why hasn't an accident somewhere destroyed everything?
2009-03-18, 21:24   #7

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by jasonp in fact you should assume your credit cards are already stolen but there are so many other stolen ones ahead of yours
Hmmm... interesting view.

Quote:
 military stuff does rely on security through obscurity, in addition to being good crypto. The algorithms that protect soldiers' lives, and classified information, are themselves classified.
I'd quibble that they rely on more than just obscurity. Proactively hiding something is more than just hoping someone won't notice. Also, there's perhaps two layers to breaking there -- (1) determining the algorithm, and (2) finding the particular key.

So I wouldn't apply the "security through obscurity" epithet to the military AFAIK. But I could be naive.

 2009-03-18, 23:26 #8 victor     Oct 2005 Fribourg, Switzerlan 22·32·7 Posts Justin told me to tell you all that you are missing the fundamental question, and focusing only on the specific question, would anyone like to comment on that?
2009-03-19, 05:58   #9

"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts

Quote:
 Originally Posted by victor Justin told me to tell you all that you are missing the fundamental question,
Even posts #5 and #6? If those are misses, then we need a clearer statement of the fundamental question from Justin.

If Justin simply doesn't like our nonagreement with his view ... well, we wrote what we honestly think about the matter.

If Justin wants research into factoring methods to cease, exactly how does he propose to prevent the people who want to crack encryption methods for "bad" reasons from continuing to conduct such research? Can he cite any historical example of such a ban on research that is applicable to this case and was effective?

Last fiddled with by cheesehead on 2009-03-19 at 06:17

 2009-03-19, 15:41 #10 jasonp Tribal Bullet     Oct 2004 3×1,181 Posts The 'fundamental question' seems to be 'why would you want to work on something that potentially can hurt people'. And the answer in my mind is twofold: - it's harder to hurt people than you think - 3M still makes duct tape with a clear conscience, despite the use of duct tape in crimes (more background here)
2009-03-19, 19:57   #11
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

24×13×53 Posts

Quote:
 Originally Posted by victor Hi everybody and happy Pi-day btw! I was talking about the great prime problem (finding a factoring algorithm within a N complexity/time) to my friend Justin, and he had a question that perplexed me: Now this is Justin, [...] because it is simply the correct answer. Back to the point, there may be a way to easily factor numbers, but what are the consequences of the solution? From what I have wained speaking to my friend Victor about the potential results of such a finding, the only thing he could think of at the time as practical application of this solution was the destruction of the strongest encryption systems available. Are these not what keep the electronic world safe from massive cyber-terrorism?
This premise is arguably false. There are many cryptosystems. RSA and others which can be broken by fast integer factorization algorithms are not necessarily the "strongest".

Leaving aside the observation that there are many cryptosystems more suitable than RSA for, say, bulk encryption, RSA is still not the "strongest" by many metrics. It may be the strongest as measured by the number of fielded implementations, but there are other public key cryptosystems which are stronger by other metrics. For instance, ECC is stronger (by which I mean computationally more expensive by known algorithms) than RSA for a given key length.

Summary: state carefully what you mean by the adjective "strongest" and we may be able to have a conversation which contains more than generalizations.

Paul

P.S. I've been breaking RSA for many years now. Some years ago I was asked by the Bank of England to visit them and to advise on the security of RSA-protected financial transactions. Although I'm not an "expert", whatever that means, I consider myself at least somewhat aware of the environment.

 Similar Threads Thread Thread Starter Forum Replies Last Post stebbo Hardware 6 2017-05-27 04:05 fivemack GPU Computing 25 2016-03-01 01:02 fivemack Factoring 2 2013-05-19 18:40 NBtarheel_33 PrimeNet 5 2010-06-17 00:17 db597 Hardware 8 2009-01-28 09:45

All times are UTC. The time now is 18:37.

Mon Nov 29 18:37:11 UTC 2021 up 129 days, 13:06, 0 users, load averages: 1.32, 1.31, 1.27