Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

Is the RSAs Loss Everyone's Gain? 136

Posted by CmdrTaco from the encrypt-this dept.
Rafael sent us a story over at ZD Net about RSAs Patents Expiring later this year. It talks about what it is likely to mean to us. Among other things, cheaper and more common encryption.
This discussion has been archived. No new comments can be posted.

Is the RSAs Loss Everyone's Gain? More

Is the RSAs Loss Everyone's Gain?

Comments Filter:
  • ...is that RSA is used in SSL protected web servers. Anyone running Apache-SSL commercially without an RSA license is in violation. Period. There is no alternative.

  • Good riddance- I respect R S and A, but.. (Score:1)

    by Anonymous Coward
    But their ubrella corporation that licenses their patent is a giant leech. When I tried to license the algorithm, they tried to charge me $20g up front and then some percentage of every sale- about 5% or so. Then the marketroid I was on the line with had the nerve to brag about all the patent fences that they had set up to stop people from using RSA even after their patent expires. As an aside, I wonder if they will be able to lock it up with patent fences? The RSA is pretty simple as algorithms go, so I'm guessing they won't.

  • Re:Flat Earth [was: Why cheaper?] (Score:1)

    by Anonymous Coward
    I think the other poster is very likely to be completely wrong, actually ... This link [talkorigins.org] indicates that the flat earth society has its headquarters (big surprise) in lancaster california.

  • Re:A remarkable expiry (Score:1)

    by Anonymous Coward
    It may be that we need to start looking at elliptical algorithms, although it is unfortunate that the level of math required to understand it is greatly more daunting.

    Another unfortunate thing is, that the field of ECC is also littered with patents.

    See e.g. US patent 5146500 and those which reference this one.

    Peeter

  • Re:Proof? Here's a little proof! (Score:1)

    by Anonymous Coward
    It's actually trivial to prove this using modular arithmetic:

    Any number times 2 will be either 0, 2, or 4 modulo 6.

    Any number times 3 will be either 0 or 3 modulo 6.

    So any number that equates to 0, 2, 3, or 4 modulo 6 will of necessity be a composite number, which means that any possible primes will be either 1 or 5 modulo 6, q.e.d.

    This unfortunately doesn't tell you WHICH numbers in that series will be prime -- only that those are the only ones you need to look at.

    Posting anonymously today because I'm moderating, and this thread looks like it could have some interesting stuff.

  • Re:Proof? (Score:1)

    by Anonymous Coward
    Where would one post code here on slashdot? Mixed amongst the posts? OH! I know... He could talk to Rob and post it with the Slash 0.4 tarball!!!

    :)
  • It's true! If someone manages to factor 13, we've had it! People will be able to decode our messages instantly!

  • Is there a higher cost associated with using these products? i.e. now your email client can have RSA built in but the cost of the security is passed on to the consumer.

    It was free (using existing free libraries), and it will remain free (using the same free libraries). It only changes one thing -- now every individual had to download them from abroad because RSA had no resources to prosecute against users but could prosecute against distributors. When patents will expire distributors will include everything in their CDs/ FTP sites/whatever, so users will get everything from them.

    As for commercial software -- what commercial software? Who in his right mind will use encryption products that don't pass through scrutiny that only open source makes possible?

  • Please note that factoring into primes is not an NP-complete problem. It is in NP and there does not exist any known deterministic polynomial algorithm for it (so it is not known to be in P).

    It is one of the very few candidates for problems neither in P nor in NPC, but proving it to be in P will not collapse NP to P. Proving that there is no problem in (NP\NPC)\P, however, will show that P==NP.

    Unfortunately, this does not seem to be easy.

  • Uh, if we can solve problems in NP as if they were all in P, that's bad news for users of discrete one-way functions like modular exponentiation. . . .

    Not necessarily. If the lower complexity bound for a given NP problem turns out to be O(P(n)^2012) instead of O(2^Q(n)) (for some poynomials P and Q), most problems will still be "hard" to crack in the practical sense.

  • I was replying in the context of free software, not commercial software.

    I would expect that Red Hat and Covalent did the same thing that Stronghold did -- obtain a license from RSAData for the RSA patent. I couldn't find much information on Red Hat's New & Improved website about the Red Hat Secure Web Server, other than it's included with Red Hat Linux 6.1 Professional.

  • It's simple, if I get an encrypted trival email from somebody I educate them first, if it happens again I bit bucket them based on the sending address. This simple algorithm works well for all forms of communication (I highly recommend it for nit pickers)
  • If you read the openssl-users mail archive, especially the thread "Is it legal?" it seems that you still have to license the RSA algorithm if you plan on using OpenSSL commercially.

    That's why I bought a copy of RedHat 6.1, which includes a single RSA license for use with Apache.

    Jeff
  • Where does that place Red Hat Secure Web Server and Covalent's Raven SSL for Apache?
  • I know personally that if people started sending me trivial things encrypted it'd probably hit the bit bucket unread.

    Then again, if it was encrypted how would you determine the trivalness of the message without unencrypting and reading it?

    Perhaps you have a function T(c) = x, 0 = x = 1, which produces a scalar value of trivialness for a given ciphertext. If so, would this provide a potential attack exist against RSA based on spam and Usenet top 10 lists?

  • wow, do you even know what you're talking about here? diffie hellmen is conjectured to be at least as difficult as rsa, just as the discrete logarithm problem is thought to be at least as difficult as the integer factorization problem. most likely, if one is broken, so is the other. in fact, i would probably bet on the DLP simply because of the *incredible* discoveries as of late which have let to quicker and quicker factoring.
  • > I like to think I have a concept of what I'm talking about.

    urgh, sorry. sometimes i type faster than i think. my apologies for that comment...

    i see what you're saying about RSA. there are a lot of reasons a free RSA is a good thing. i do agree that it will help spread the use of strong encryption, and i really can't argue with that. however, DH is just as good a solution -- arguably better. i think RSA is strong today, but is rapidly becoming weaker. if the only use of RSA is legacy systems, then it's great. i just don't think it is a wise idea to continue using it for mission critical needs.

    this whole discussion is probably academic, though. personally, i think that ECC is going to be come a defacto standard in the next few years, after it has had more analysis. it eliminates the need for the mammoth keys required for RSA and DH. unfortunately, ECC seems to have just as many patent problems as RSA, so we're back to square one. woops.

    later,
    ian
  • If the cost barrier is lowered for commercial software to include RSA is there a higher risk associated with implementation?

    Is there a higher cost associated with using these products? i.e. now your email client can have RSA built in but the cost of the security is passed on to the consumer.

    I wonder who will make the most money on the pre-fab tool kits and libraries for this stuff...

    Also, is RSA still considered an acceptable level of safety? Or is it just going to be the latest way to jack up the price on software?
    http://www.mp3.com/fudge/ [mp3.com]

  • You're right that I should provide proof [...] I don't know how and where to publish the source code

    Post it to the sci.crypt [sci.crypt] USENET group.
    --

  • Take any product P*Q = N(P and Q both prime)
    This is always true:
    (N+1) MOD 6 == 0 or
    (N-1) MOD 6 == 0

    Trivial counterexample: P=2, Q=3, giving N=6.

    Neither 7 MOD 6 == 0, nor 5 MOD 6 == 0.

    Q.E.D.


    --
  • You could create a product with "legacy" support for DH. Encourage all users to switch to the RSA version in 9 months, but even if some did, some didn't, they'ed still be communicatable with one another. End of problem.
  • Or is it for idealogical reasons?

    Either way, if it were up to me, I'd definetly choose an RSA/Triple DES combo. They're to two most widely used algorithms, which would seem to mean that they're the largest targest, and they've stood pretty strongly.

    I'm partially disappointed that I even have to have a Diffie Hellman key, but according to the PGP docs, that's about the only way to communicate with users of other products, thanks to that patent.

    I'd strongly encourage everyone to upgrade to PGP 6.5 now, and a free alternative later, if you don't like giving your money to evil software companies that only care about profits (Me, I gladly for it over). In 8 months, unless a weakness is found, there really will seem to be no reason to use anything but RSA in PKI products.
  • I like to think I have a concept of what I'm talking about.

    RSA is much more widely used in commercial apps than DH. From what I've read, most, if not all of, the largest financial institutions depend on RSA, not DH. Therefore, RSA's presented a much larger target for a much longer period and is still standing. With encryption products, I've always heard that the best theory is "If it's not broken, don't fix it."

    There's been much grumbling around here about RSA's patent interfereing with product development, etc. On one hand people say it sucks, and on the other, they want to use it in their products. If RSA did suck, no one would care that the patent is expiring. But they do. Why discourage people from using it once it passes into the public domain?

    People can factor quicker and quicker, (or actually, computers can), but RSA's simply been increasing it's key length as time goes by. Unless a real breakthrough occurs that nullifies key lengths altogether, RSA appears rather safe.

    That's my two cents.
  • Hi -- quick question about the RSA patent, as this topic is particularly relevant to me right now. I just finished moving a development system from c2net's Apache/Stronghold server to a Apache/mod_ssl/openSSL server, and I am now considering moving it into production.

    From what I can tell, the openSSL version is going to be a better choice -- especially considering how much easier it is to build heavily modified versions of apache if one stays with exclusively open source/GPL'd components.

    However, I'm a little worried that the openSSL version is using the RSA algorithm and that we could be violating their patent if we start using this commercially. It seems that all c2net Stronghold offers is the fact that they went through the hassle of licensing the RSA code.

    My question is do we need it anyway, or are we fine using mod_ssl/openSSL?

  • ...and 871 % 6 = 1.

  • I sincerely hope, although I realize it's extremely unlikely, that situations like this will illustrate to the "powers that be" that software patents are inherently BAD for consumers. Software patents violate some of the most basic fundamentals behind the patent system. I've worked on a couple projects where we REALLY needed to make use of RSA encryption algorithms not because they were the best suited for the job, but simply because the commercial webserver and browsers available REQUIRED it. That stiffles innovation, it doesn't promote it. Patenting software algorithms and then forcing a monopoly arrangement in that area of the market can not possibly be good for competition. It completely BLOCKS competition. How short-sighted.
  • So?

    If it is an important matter of National Security, then they are more likely to take the patent away, than allow a single entity to control it.

    Why on earth would 'national security' (a bogus term usally interpreted as serving the needs of the power/wealth elite) rely on RSA owning the patent.

  • I would imagine those counter-examples work because P or Q=2 or 3 stops it. By frequency analysis, given the product of two primes is odd, the number 'above' or 'below' must be divisible by two (i.e., even). Since you are considering products of primes other than 2 or 3, pq must therefore not be factorable by three. Since numbers that are factorable by three occur every 3 numbers (obvious), and n%3!==0, therefore ((n-1)%3==0)||((n+1)%3==0)). I think?!
  • Hmm, little vague: what I meant to say, was, he's saying the relationship ( ((n+1)%3==0)&&((n+1)%2==0)) || ((n-1)%3==0)&&((n-1)%2==0)) ) holds... I don't if this gives you any extra info though.
  • Really? I thought the benefit of RSA was that it allowed public Key encryption, that could not usefully be broken even if you knew the algorithm and decryption key.
    The whole idea of public key encryption was revolutionary at the time, and it took a long time to progress from the theory to an actual algorithm that worked.
  • Yeah, the British spooks did invent Diffie-Helman and RSA in the '70s, but at GCHQ (Government Communication Headquarters), not Bletchley Park.
    oops. sorry, you're right.
  • But trying to make sure your enemies don't have strong encryption by just not telling them about it doesn't work. As many people know, intelligencia around the world tend to get onto the same ideas at the same time, and develop them in parrallel (if not in communication).

    In the end, it comes down to trust and fear. Using a balance of terror, and not trusting people (ie: by making sure it's easy to read their email, etc) leads to more trouble than it is worth..
    ---
  • Not a proof, but I did check it for all combinations of the first 10,000 primes (up to 104729), and it holds true so far. Don't have the computer power and/or time to optimize code to go beyond this right now, however.

    Not sure how this helps crack the RSA's prime encryption technique, though. Doesn't cracking the scheme (if N*M=P) force you to find N and M, if given P (N and M prime, here)? Knowing that N*M +/- 1 mod 6 is 0, how does that help? I know nothing about these encryption methods, though.

  • Duh, you forgot ROT-13!

    and be sure to use ROT-13 twice--using it more than once will increase the number of times your attacker will have to attempt a crack, and thus increase its strength!

    *ducks*
  • That probably wasn't really for Dummies...

    Oh yes it was. I'm a big dummy, and I basically understood all that.

    A big thanks for posting that BTW. You deserve some serious karma points, unlike all the retards (including myself) posting replies to this story.

  • Show us some proof and post the code here. Otherwise, you're just trolling for Karma points. If you post it here, News.com will pick up the story and you'll still get your glory.
  • This is yet another example where the general public in benefits once patents expire. Capitalism takes control and multiple companies can compete to provide the consumer with a better product for less money or for free. The set of laws that govern IP in the USA severely need to be reformed to work properly in the internet age. The RSA patent is one of few examples of a computer-related patent that still has usefulness after it expires. 17 years is too long for a government granted and subsidized monoply.

    - Mike Roberto
    -- roberto@apk.net
    --- AOL IM: MicroBerto

  • No, the purpose of copyright in the constitution is to protect artists. Science and technology are protected by the limited monopolies covered by patents, but artists are provided with a very long monopoly because of the durability of their works and the likelihood that their opportunity cost of producing them will not usually be recovered in a few years. The original copyright was for around 50 years.

    Software has now presented us with a problem, where it would be more efficient if software lost its copyright within a few years, like 5 or 6. I think that, in many cases, people would have preferred to modify FoxPro 2.6 to suit their needs rather than figure out what to do as dos gets slower and less reliable on their windows-only machines. Software companies either make an economic profit within a few years or they do not make it at all; Moore's law dictates this.

    Instead of telling us about H1-B visas and protecting monopolies, the "technology savvy" presidential candidates should be trying to win votes by emending copyright and patent law for the software industry.

  • Followers of Richard Stallman often condemn software patents as universally bad. But the advent of "RSA Day" shows at least one way in which they may be beneficial. Due to the expiration of the patent, RSA is being tested as never before by the very best experts in the industry, who will be strongly motivated to break it. And if any chinks are found in the armor, they're certain to be publicized and not held as precious secrets, since the cryptographers only stand to gain by revealing their discoveries. This is very good news. If RSA holds up, we can be more sure than ever that it's a strong algorithm. See Twinkle, Twinkle, Little Prime [internet.com] at http://boardwatch.internet.com /mag/99/dec/bwm62.html [internet.com].
  • How about this then:

    Take any product P*Q = N(P and Q both prime)

    This is always true:

    (N+1) MOD 6 == 0 or

    (N-1) MOD 6 == 0

    -- check it, and keep yer karma points!

    YOU CAN USE THIS FOR A NUMMERICAL DETERMINATION!

  • ah, okay, it doesnt work for 2 and 3, but it does work for all other primes:

    17*11 = 187

    187-1 = 186 ==> 186 / 6 = 31... 186 MOD 6 == 0

    voila!

  • Yes, I can prove it!!!!

    And that's exactly wat this is all about!!!

    And if you now the whole story, you can think of an algorithmn which solves the prime-number problem in RSA!!!

  • I haven't shown anything yet... but that 1 and 5 is a very important propperty
  • Tell you what:

    The numbers:

    a0 a1 a2 a3 a4 a5 a6

    a1 = a0+1, a2=a0+2 etc.

    a0 - divisible by 6

    a1 - odd

    a2 - divisible by 2

    a3 - divisible by 3

    a4 - divisible by 2

    a5 - odd

    a6 - divisible by 6

    a1 and a5 are either composite prime numbers, or they're prime.

    so any P*Q = N ===> all P,Q and N are either any a1 or a5...

    I'll maybe post some more later, I'm now going home from work...

  • Ah, I'm at home, I've got time now.

    Take P and Q being prime, the product is N.

    From previous posts in this thread we see that all of these numbers have a neighbour divisible by 6.

    This can either be P-1 or P+1, Q-1 or Q+1 and N-1 or N+1

    Taking the square root of N we get a number which is between P and Q, and closest to the lower of the two

    So how do we find out which primes P and Q are? The mathematical problem here is that we can't build a numerical method which is designed to reduce certain difference.

    So we're not directly going to look for P and Q, we're going to look for the 6-neighbours.

    Suppose we'd have 17 * 11, we have the neighbours 18 and 12, dividing by 6 we get 3 and 2.

    3*2 = 6, so the idea is to find 6 as a starting point.

    6 * 36 = 216, 18*12 = 216, 17*11 = 187. 180 is the first factor of 36 smaller than 187.

    In this case, 180 is our first starting point. We divide by 36 to get 5, we then try to find two factors making 5 (which we don't find)

    If we desing this function propperly we do get a minimum and a maximum closest to 187.

    Next we must determine our new starting point, which is in this case 180+36 = 216. We then found the neighbours, we then found the primes.

    Determining the starting point is the part I'm still stuck with but hey, I'm not spending all my time on this thing.

    Only thing I know is that the difference by the first and final start points is caused by the distance between P and Q!

    The routine which looks for two factors of the starting point / 36 can be speeded up because we're looking for neighbours, so if we don't find the neighbours, we will find a difference.

    Suppose starting point x (already divided by 36):

    suppose f1 * f2 == x.

    for the difference we determine the closest to the prime by (( f1 +/- 1 ) * 6) * (( f2 +/- 1) * 6)

    If we have this minimal diffrence m and maximum difference M, the looping factor (i.e.) can be lowered by (M - m) / 36.

    I have tried more like lowering with m / 36, sqrt(m) etc.

    This decreasion number speeds up finding of the neighbours, so we're not stuck with the same PQ-problem in a different outfit!

    Because the function is designed to do a numerical determination of P and Q, the function can be made very fast.

    In one of my test cases, My program only needed 6 iterations to determine 641 * 13 (or something like that).

  • My English skills aren't that bad, but I was at work and had little time. Read my newest post to get an idea of how I'm looking for the primes
  • You're right that I should provide proof, and I'm not doing slashdot for Karma, but for fun. I have previously posted a story on prime-numbers before on slashdot, but the article was rejected.

    I'm now trying to find contacts in the mathematical world, and at this moment, I don't know how and where to publish the source code, I don't have a home-page right now, I should make one because explaining the algorithmn needs some more information.

  • Speaking of patents and leeches,

    The judge dismissed the Imatec patent lawsuit against Apple saying Imatec didn't own the patents and ColorSync didn't infringe on them anyway.
  • Wow amazing. Not.

    Take any number x not divisible by two or three.

    x mod 6 cannot be 0 or 2 or 4 (divisible by 2) or 3. It must be 1 or 5. Regardless of how many prime numbers make up x. QED

    This has of course nothing to do with RSA. You fail to show how you make the factorization of N anything less than a O(sqrt(N)) problem

    - Alex

  • See my reply above yours to see why the proof of that claim is trivial, yet has nothing to do with N=P*Q, where P and Q are prime. The only important property is that N isn't divisible by 2 or 3.

    RSA would never use a prime number so small as 2 or 3.

    That is just plain wrong. You can freely multiply your modulo with 2^n to conveniently align it for easier modulo-multiplication (E.g. w/ Barrett's algorithm). The number you need to know to decrypt is the product of all (prime factors - 1) so multiplying by two changes nothing. (Not even the space of originial data where encryption is bijective)

    - Alex

  • IMHO, it's a mistake to rely on a "proven solution" in preference to looking ahead.

    With crptographic algorithms, older is better, because with an old algorithm, more people have had more time to find holes in it, and if they haven't then that means that the probability of someone finding a hole in the future is lower.

    If anyone cracks the primes problem, RSA is dead in the water. Instantly. No matter how "robust" it's been.

    There are many more ways in which one specific crypto algorithm can have weaknesses.

    And if someone actually found a fast way to factorize large numbers, then not only is RSA "dead in the water" but also pretty much every single other widely-used crypto algorithm.

  • > And if someone actually found a fast way to factorize large numbers, then not only is RSA "dead in the water" but also pretty much every single other widely-used crypto algorithm.

    Actually, no. It wouldn't affect symmetric algorithms or elliptic curve public-key algorithms at all, and it would (probably) only affect Diffie-Hellman if the technique also solved discrete logarithms quickly.

    j

    "It's not whether or not you're paranoid. It's whether or not you're paranoid enough."
  • *A large percentage of the Flat Earth Society are in the Southern states of the US. umm ok, sure. But what does this have to do with anything *Yes, it does mean RSA can be used "freely" in the US, but that's about the limits of the benefit. One small continent, amongst many. Well i hope u meant country not continent. But either way but that is significant. The US has much more Demand for product like these than many other (not all) countries. I would suspect demand for these products is much higher in the US than like in Sudan or Guatemala making the opening of RSA in the US more significant.
  • What is this garbage? This makes absolutely no sense at all; please present your algorithm in a coherent fashion using standard mathematical notation or at the very least, some decent pseudocode. "Decreasion number," "looping factor", "6 neighbor," and "numerical method which is designed to reduce certain difference" have no meaning whatsoever. Your method seems to be a variation of Fermat's factoring method which starts from sqrt(n) and sieves downward based on congruences; this is dreadfully inefficient compared to modern factoring methods. The time complexity of Fermat's method is fully exponential and the O(0) factor is quite high for classical techniques; it is not even competitive with the Pollard/Brent rho method or the Pollard p+/-1 method.

    Drnomad appears to be a crank; it's not worth any more of my time to wade through the stuff he pours out.
  • Really? I thought the benefit of RSA was that it allowed public Key encryption, that could not usefully be broken even if you knew the algorithm and decryption key.

    Bletchley Park of all people should know not to rely on the secrecy of the algorithm.

  • Being vaguely familiar with how patents work, I did a search at the IBM Patent server (http://www.patents.ibm.com/ [ibm.com]) under the Boolean search tool for "public & key & encryption". This matched 266 items, including items for:

    ...etc. I'm not saying that each of these is a relevant or blocking patent, but the search space here is huge. It's also possible that there are relevant patents which don't contain the keywords used in my search.

    Granted that the search tools are primitive, but is anyone aware of any key patents covering public key encryption as related to web servers, e-commerce, business models, or any related type applications which could still effectively limit access to RSA PKI security for practical purposes?

    What part of "Gestalt" don't you understand?

  • I have some understanding of the math of RSA (hit it in first year algebra way back when working on my Bachelor of Mathematics degree); the point is that there have now been years of "numerous attempts to break it."

    Consider that the use of the Knapsack Problem for encrypting messages was arrived at around the same time, and it turned out to be vulnerable to attack.

    With lots of people working on factoring, it would not be overly peculiar for vulnerabilities to have turned up by this time.

  • Um. If the polynomial is of sufficiently high degree, this means that the complexity is in P but is still impractical to solve.

    I suspect that you are mistaking Not in NP for meaning easy to solve.

    Not in NP appears to be a necessary condition for something to be an "easy solve." It is not a sufficient condition for that purpose.

  • If he had merely invoked the "magic of quantum computers," I'd agree that this was likely to be an ignorant resort to deus ex machina, and would say the same about invoking What if P = NP ?

    However, he also suggested the possibility of a substantial result in number theory in the area of factorization. That is another unpredictable possibility that is as "likely" to result in an RSA crack. And while it's not a new insight, the combination is reasonably sound.

  • One word: Interoperability

    In the commercial workplace environment (ie: large corporations) there's only one standard for encryption: RSA. If you're using encrypted email, you're using S/MIME, which depends upon RSA (and their whole PKCS toolkit). If you're using secure web servers, you're using SSL2, which depends upon RSA. When you get an encryption-enabled web browser (be it Netscape or Internet Exploder) you depend upon RSA. Period.

    If you want to develop software that plays in a commercial environment, first you have to be interoperable with the existing standards, then you can think about branching out and establishing new standards. Look at Samba -- much as I dislike Microsoft's SMB network protocol, it's a de facto standard -- and Unix computers couldn't easily participate in a Microsoft network without Samba. It's the same problem for encryption -- you have to be interoperable with what already exists in the organization, and that's RSA.

    Don't get me wrong -- PGP/GPG is good technology -- but using PGP/GPG in conjuction with a seperate email package is a lot harder than using a mail client with built-in encryption, and people want email to be simple, and they want it to act the same across all platforms. The biggest advantage Netscape's Communicator has/had was that no matter how lame the email client, it worked the same for Windows, Unix, and Macs ... and all of them used RSA encryption.

    The good thing about the patent expiring is that packages like OpenSSL will be able to be used universally, instead of just outside of the US. It also means that the open software community can have secure encryption without the security holes that are introduced by the RSA reference implementation (RSAREF) -- see BugTrak for details.

  • IANAL, but my understanding is that...

    In the United States...
    between now and September 20, 2000...
    if you use mod_ssl/openSSL...
    and it wasn't built using the RSAREF toolkit,
    Then you'll be in violation of the RSA patent, and subject to legal action, and should use Stronghold instead.

    In the United States...
    between now and September 20, 2000...
    if you use mod_ssl/openSSL...
    and it was built using the RSAREF toolkit...
    and you're using it for commercial activities...
    Then you'll be in violation of the RSA patent, and subject to legal action, and should use Stronghold instead.

    Otherwise, you're OK.

  • Allow me to restate this (since DrNomad seems to have much better mathematical skill than written english skill).

    For all P & Q greater than 3, one of the following is always true:

    ((P*Q) + 1) % 6 = 0

    ((P*Q) - 1) % 6 = 0
    RSA (and most other public key algorithms) depend on the difficulty of factoring sums of large prime numbers. So, if you can come up with a convenient, low cost way to factor these sums, you can in theory crack RSA.

    It is perfectly conceivable that the above numerical relationship could be used to come up with an easy way to factor these sums. Does that mean RSA is cracked? Hardly. It just means that what DrNomad is saying makes /some/ sense. And the counterexamples that people have posted are irrelevant since RSA would never use a prime number so small as 2 or 3.

  • Of course, here are some counterexamples (from my handy-dandy perl script I wrote to check this): 42139:104579 42139:104593 42139:104597 42139:104623 42139:104639 42139:104651 42139:104659 42139:104677 42139:104681 42139:104683 42139:104693 42139:104701 42139:104707 42139:104711 42139:104717 42139:104723 42139:104729 42157:101891 42157:101917 42157:101921 42157:101929 42157:101939 42157:101957 42157:101963 Nice try slick.
  • Do you have a source for your assertion that a large percentage of the flat earth society are in the south? Just curious.
  • Or maybe there is a weakness but they've been holding out on saying? When Shamir talked about his device for factoring Primes earlier this year, it was on my mind that it was him and Rivest (in other examples) that have gone the furthest in trying to show the theoretical vulnerabilities of RSA encryption.

    I guess we'll see... It'd be scary if September 21st they announced that even 4096 bit keys were vulnerable, but their new patented algorithm, RSA2, did not have those vulnerabilities.
  • Actually I've never read "The Code Book" ( I've actually never heard of it actually), but have been following quantum computing in the mainstream science press (Science News, NPR, etc). Currently there are demonstrated algorithms for factoring small numbers (five bits has been done and 11 bits might have been by now). The base algorithms are in place and extensions to them due to the inherent parallelism of qubits for problems like this makes the factoring of larger number just a matter of being able to handle more qubits.

    There are people out there using all sorts of esoteric machines to make quantum gates. At the moment a hundred gates is a large infrastructure, but with advances like the quantum resivor from Lucent these could be done in a LSI type circuit in the not to distant future.

    Fortunatly no one has shown equivalent work for Fiestel (sp?) networks that most symmetric block ciphers are based on, and stream ciphers tend also be safe if used properly. I just haven't seen a PKI that doesn't have something on the horizon that break it.
  • Judging from the advances in quantum computing and the algorithms for factoring using qubits (sp?) I can see it expiring and then just as people are adopting it wholesale we see a set of factoring breakthroughs. It not like you can increase the key length all that much either. How long would it take to encrypt a session key with a 65535 RSA key :-)?

    Maybe we should start looking at that IBM algorithm that they claim is provably difficult.
  • This means that Rivest, et. al. will have a great incentive to discredit RSA encryption in favor of their later technologies. They're clearly among the best of the private sector in the encryption field, so if a weakness can be found, they're likely to find it. Note that they've already found a minor weakness, so they're clearly looking to push people to newer patented technologies.
  • And yes, I know full well that IPSec and other ciphers could be used, but not for all the applications I need, unless I am severely mistaken and/or really dumb.

    Actually, IPsec is a protocol and not a cipher. It provides means for doing "secure" IP and may use a wide range of ciphers and hashes to provide various services. I don't really see IPsec providing services similar to SSL anytime soon, but the comparison is more of an apples-oranges comparison.

  • RSA officials also expect companies to release competitors to RSA's BSafe encryption tool kits, which include the RSA algorithm, promising newer, more affordable RSA implementations. Crypto-savvy ISVs won't even have to do that; they'll be able to build their own from the RSA source code.

    'RSA source code'? Any source code developed by RSA Security is still their property regardless of the status of the algorithm patent. We will not suddenly be able to copy BSAFE just because the patent on the mathematical process has expired.

    If you're reimplementing BSAFE you'd better be careful NOT to look at the 'RSA source code' or you could find yourself in court.

    (I don't work for or even LIKE RSA Security)
  • If I'm not mistaken I believe that even though the RSA patents expire later this year, the US export restrictions are still in effect. (However they did change them a month ago)
  • "Take any product P*Q = N(P and Q both prime)
    This is always true:
    (N+1) MOD 6 == 0 or
    (N-1) MOD 6 == 0"

    P = 13
    Q = 67
    N = 13 * 67 = 817

    (N - 1) mod 6 = 816 mod 6 = 0
    (N + 1) mod 6 = 818 mod 6 = 2

    Uh oh. Back to the drawing board.

    I didn't, BTW, make a Perl script to check this, nor did I intuit this counterexample. I just chose the first two prime numbers I could think of.
  • RSA is an important algorithm to expire, mostly due to the "original" copies of PGP (most of which are still more trusted than the more modern, "gui" versions recently released by NAI). However, RSA's patent ONLY applies within the united states - european and eastern countries have been using more efficient, less bug-ridden implimentations for some years than the standard "RSAREF" implimentation forced upon users in the us. So the immediate benefit will be that the original PGP version of the RSA library can be restored, with increases in speed and in security (as source is available to be checked) over the current us usage.
    However, the other cornerstone of "classic" PGP (the IDEA symmetric algorithm, which does most of the work - the RSA key is merely used to encrypt an IDEA key) will not have it's patent expire until 2010 [ascom.ch] at the earliest.
    What is really needed is a usable, DOS command-line version of PGP (or GPG) to replace the existing batch-mode use of the RSA/IDEA standard with the more modern (but equally secure) DH/CAST base used in more recent implementations, which is patent-free (or expired :+)
    --
  • Oh, you stupid people. You really kill me. The particular method employed by PGP was a tradeoff because encrypting the entire message via RSA would take way too much time. Zimmerman was smart enough to come up with this compromise.
    I'm obviously one of those stupid people - I have absolutely no idea what difference this makes to my point. yes, a new, pure-rsa package could be written that didn't touch symmetric encryption with a bargepole, but then you would have the following:
    1. no-one using pgp could decode your messages AT ALL - everyone would have to replace their software with your new version
    2. Encrypting to twenty people would involve encrypting the entire file twenty times - with the space, processing and bandwidth costs this implies
    3. vunerabilities in RSA with certain plaintexts (easy to avoid in generating IDEA keys, but awkward to impose on plaintext) would become viable attacks
    4. older hardware currently more than usable as a standalone decryption "soak" become unusable, forcing people to either replace them with modern machines or do decryption on their general-purpose machine
    I could list more, but can't see the point.

    IDEA, as a symmetric algorithm, is much faster than RSA.
    Yep, still true today - just with larger files in the picture

    Without RSA in the process, we're back to square one for all ciphers which is distributing the keys. RSA does away with that problem.
    Ah, now I understand. you haven't grasped the difference between PKI algorithms as a whole (the current unburdened example of which is DH/Egmal) and RSA, which is merely one example of it - and obviously not the first to be discovered, given that the patent on DH expired some months ago. PGP can (and does!) use DH as a replacement to RSA, just as it can (and does!) use CAST as a replacement to IDEA. problem is, there are no stable DOS command line releases currently available. 5.0i for DOS is untrustworthy and (as far as I know - I stand to be corrected) no longer being worked on, and GPG for Dos is *listed* as an unstable alpha not to be trusted for anything but sig verification.
    If you want a target to flame, might I suggest one of the "petrified girl" posts? No-one really cares if you fail to understand their content before you reply to them.
    --

  • I thought that the problem of efficient factorization & finding discrete logarithms was mathematically proven to be equivalent (at least, that's what I thought I read in some of the "quantum computing" papers I browsed...)
  • Here in the states I find it easier to download GPG from Finnland or somewhere since it's very difficult to find a copy on a US FTP Server.

    The real irony is that I can't then E-Mail it back to Finnland without facing prosecution.

  • This won't mean much for the average (l)user, but I'm glad RSA will not continue to exist soley on the profits of taking advantage of a US monopoly (aka selling BSAFE, RSA licenses, and suing people who violate their patent). Also, it will finally allow people to use RSA within the US, which doesn't mean shit for someone anywhere else, but I happen to like it. And it will allow legal SSL use in the US without a RSA license (unless you want to use the horribly crappy RSAref library - and yes, I have looked at the code, it's an abomination).

    Cheaper crypto? Probably not. ElGamal, DSA, Diffie-Hellman and ECC have been and remain alternatives for PK.
  • Diffie-Hellmann uses prime numbers[*]. It wouldn't be touched by efficient factorization, though, as it relies on the hardness of finding a discrete logarithm.

    - Alex

    [*] Diffie-Hellmann is a method to generate a session key while the bad guy is listening.

  • Yeah, the British spooks did invent Diffie-Helman and RSA in the '70s, but at GCHQ (Government Communication Headquarters), not Bletchley Park.

  • No guarantee (Score:3)

    by Anonymous Coward on Monday January 24, 2000 @05:14AM (#1343943)
    Don't hold your breath waiting for the patent to expire. The US government still has plenty of time to illegally and retroactively increase the term of patents. After all, they did it with copyrights. It wouldn't take much to convince the congresscritters that the RSA patent is an important matter of national security.

  • Re:Why cheaper? (Score:3)

    by Gleef ( 86 ) on Monday January 24, 2000 @05:13AM (#1343944) Homepage
    jd wrote:

    Despite what many in the US think, the East coast does not mark the edge of the world, and people who sail beyond the horizon don't fall off.
    RSA encryption has been used, freely, throughout Europe, for a considerable period of time. International versions of PGP, for example, can be found in many University FTP archives, and are widely used.
    Yes, it does mean RSA can be used "freely" in the US, but that's about the limits of the benefit. One small continent, amongst many.

    The facts here are certainly true, but that's not the whole story. A LOT of software development takes place in the US; all surveys I've seen have ranked the US as the largest software producer in the world (most of them rank India second). Key commercial products are developed in the US, and many key Free software projects (including the entire GNU project [gnu.org]) are hosted in the US. All this software needs to care about the RSA patent, or risk lawsuits.

    After the patent expires, none of this software need worry. European users will no longer have to use patches and alternate versions of American software, RSA code can be in the main code tree. RSA software developed outside the US will no longer feel like they need to offer an American version, since the rules will be closer together. This will make development easier across the board.


    Besides, RSA isn't cutting-edge, by a long way. Yes, it's proved very resistant to attacks, and it's one of the best public-key encryption algorithms out there, but there's a lot of much newer stuff that looks like it could be more attractive in the long-term.

    It may not be cutting edge, but it is the defacto standard protocol for encrypted internet communications. I wish more software would support DH/DSS, but they just don't. So-called "cutting edge" solutions generally have not been around long enough to be trusted, much less standard.


    (IMHO, it's a mistake to rely on a "proven solution" in preference to looking ahead. If anyone cracks the primes problem, RSA is dead in the water. Instantly. No matter how "robust" it's been.)

    Both needs to happen, you always need to be looking ahead to find new technologies. On the other hand, when implementing a real world system, you need proven, robust technology to rely upon. RSA is currently the tool used by most organizations to implement their PKI for this very reason.

    In the future RSA may die, then they need to move to something else, but can you point them at a PKI technology: available right now, with a reliable track record spanning many years, with open cryptographic review spanning at least as long, that isn't succeptable to the "if anyone cracks the primes problem" vulnerability? Regardless, it's not a major vulerability, since that problem has been attacked from many different angles for centuries with no better solutions than the slow ones we have now.

    ----
  • There is a need for RSA because it's the standard implementation cipher for SSL under IE and NS. Not all users for all applications are willing to use a command line, but I can line up all the people that want more assurance that their web-based security is up to snuff. It's what I do for a living when I'm not kicking naughty servers.

    The expiration of the RSA patent will be a wonderful relief for many of us who have tried to negotiate a license for some sane SSL package -- Red Hat is currently your only salvation if you want to use a modern solution like mod_ssl with openssl to create your own apps. And yes, I know full well that IPSec and other ciphers could be used, but not for all the applications I need, unless I am severely mistaken and/or really dumb.
    I have been accused of being otherwise, and more to the point, looked around for a while before giving in to the sad truth.

  • A remarkable expiry (Score:3)

    by Christopher B. Brown ( 1267 ) <cbbrowne@gmail.com> on Monday January 24, 2000 @04:32AM (#1343946) Homepage
    It is fairly remarkable that RSA is still considered useful after lo these many years.

    There has been a tendancy for patents on computer-related stuff to block developments for so long that the patented matter to be an irrelevant obsolete technology by the time it becomes publicly available.

    It may be that we need to start looking at elliptical algorithms, although it is unfortunate that the level of math required to understand it is greatly more daunting.

    Hopefully there are a few years of "reasonable security" left in RSA...

  • Only applies to US (Score:3)

    by Oneflower ( 7827 ) on Monday January 24, 2000 @04:21AM (#1343947)
    AFAIK the RSA patents are only valid in the USA,
    and this will have little affect on code that
    uses RSA. After all PGP and GNUPG are pretty
    widespread inside and outside the USA.

    The only affect should be on commercial (closed
    source) code within the USA.

    Now there should be no reason for RSA to be preferred key exchange, et al., alg.

  • Patents (Score:3)

    by larz ( 23116 ) on Monday January 24, 2000 @04:30AM (#1343948) Homepage
    This is yet another example where the general public in benefits once patents expire. Capitalism takes control and multiple companies can compete to provide the consumer with a better product for less money or for free. The set of laws that govern IP in the USA severely need to be reformed to work properly in the internet age. The RSA patent is one of few examples of a computer-related patent that still has usefulness after it expires. 17 years is too long for a government granted and subsidized monoply.

  • RSA first invented by the British (Score:3)

    by bigbird ( 40392 ) on Monday January 24, 2000 @04:48AM (#1343949) Homepage
    According to *The Code Book* by Simon Singh, the folks at Bletchley Park [bletchleypark.org.uk] independently invented public key encryption before RSA did. Unfortunately it could not be publicised or patented, as it was a military secret.
  • > The only affect should be on commercial
    > (closed source) code within the USA

    Not exactly. Linux distributors in the USA will finally be allowed to add stuff using RSA (ssh, ...) to the distributions.
    Along with the slightly improved export restrictions, this can be a real gain.

  • RSA for Dummies (Score:3)

    by Lexel ( 110539 ) on Monday January 24, 2000 @06:46AM (#1343951)
    Seeing many comments from people who hardly know anything about the underlying math, I decided to post them

    Euler said:
    For any number m,
    x^{\Phi(m)} mod m == 1
    where \Phi(m) is the number of n<m for which gcd(n,m) == 1
    If m has the prime factors p_1,p_2...p_k, then \Phi(m) equals the product of the (factors minus one), \prod_i (p_i-1)
    RSA uses that property. I construct a m = p*q, where I know the prime numbers p and q. These are very hard to find out for you. I therefore know that \Phi(m) = (p-1)(q-1). I give you m and e, you give me y=x^e (mod m), I calculate d, such that (d*e) mod \Phi(m) = 1 and do
    y^d = x^(d*e) = x^1 = x (mod m).

    That probably wasn't really for Dummies...
    - Alex
    PS Can you tell I'm doing LaTeX lately? ;-)

  • Re:A remarkable expiry (Score:3)

    by a_n_d_e_r_s ( 136412 ) on Monday January 24, 2000 @04:55AM (#1343952) Homepage Journal
    Its nothing strange with RSA still being useable.

    RSA is based on math, and the old greek math is still valid so why should not RSA ? RSA is easy to implement and has withstand years of numerous attempts to break. A downfall with new crypto is the the fact that there migh exist a easy way to break it - that is non-obvois at start but might be uncovered by years of research. RSA is still considered secure - if used correctly.

    RSA good point is that its easy to use and as secure as one can get.

  • Why cheaper? (Score:4)

    by jd ( 1658 ) <imipak AT yahoo DOT com> on Monday January 24, 2000 @04:26AM (#1343953) Homepage Journal
    Despite what many* in the US think, the East coast does not mark the edge of the world, and people who sail beyond the horizon don't fall off.

    *A large percentage of the Flat Earth Society are in the Southern states of the US.

    RSA encryption has been used, freely, throughout Europe, for a considerable period of time. International versions of PGP, for example, can be found in many University FTP archives, and are widely used.

    Yes, it does mean RSA can be used "freely" in the US, but that's about the limits of the benefit. One small continent, amongst many.

    Besides, RSA isn't cutting-edge, by a long way. Yes, it's proved very resistant to attacks, and it's one of the best public-key encryption algorithms out there, but there's a lot of much newer stuff that looks like it could be more attractive in the long-term.

    (IMHO, it's a mistake to rely on a "proven solution" in preference to looking ahead. If anyone cracks the primes problem, RSA is dead in the water. Instantly. No matter how "robust" it's been.)

  • More than you wanted to know about copyright terms (Score:4)

    by copito ( 1846 ) on Monday January 24, 2000 @09:20AM (#1343954)
    Read the very informative page Opposing Copyright Extension [asu.edu].

    Copyrights have been extended an average of about 1 year per year since 1962. The latest extension, the Sonny Bono Copyright Extension act of 1998 extends corporate copyrights to 95 years, retroactively. Since the stated purpose of copyrights in the constitution is to encourage the production of art and science by giving a monopoly for a limited time, retroactive extensions are IMHO unconstitutional. The current extension madness seems designed to make sure that Mickey never enters the public domain.
    --

  • Hmm... (Score:4)

    by Amphigory ( 2375 ) on Monday January 24, 2000 @04:32AM (#1343955) Homepage
    Last time I looked, BSAFE sucked.

    Look guys... RSA was formed for the specific purpose of cornering the encryption market and they have been screwing the entire industry with their draconian licensing costs. Their patents are expiring -- do they really think that I, as a developer that has been putting up with their bugware and outrageouse prices for year, am going continue to license their bugware when there are numerous free, high quality implementations?

    I think not. Ding, dong the witch is dead! The witch is dead! Hail to a new era when lions and hyenas can communicate securely! Death to RSA!

  • It probably will make no noticable difference (Score:4)

    by substrate ( 2628 ) on Monday January 24, 2000 @04:40AM (#1343956)
    I'm not sure of the actual numbers anymore, with the popularity of Linux and the renewed interest in the Macintosh, but the percentage of Microsoft desktops is still probably over 80%. Microsoft already licensed the technology (and from what the article said for much cheaper than the average company could) and apparently uses it.

    Encryption is for most people invisible, they go to an online shop and buy stuff. Maybe they notice that the little lock in the lower left corner is closed and maybe they don't. If RSA is a part of the protocol then its already there.

    Most people don't care about pervasive encryption. When they're forwarding the latest joke they received to their friends and families they don't worry about encryption or digital signatures. People don't even bother encrypting email to their mistresses, their mistress probably can't be bothered to remember a private key.

    The difference it will make is to people who sell the technology, it'll be a bit cheaper to them which might be important since for good or bad the current cost model for Internet Explorer and Netscape Communicator etc. is to be free (like beer, not speech)

    I don't see that RSA patents has hampered the widespread deployment of PGP. Apathy on the part of the public has hampered the widespread deployment of PGP. I know personally that if people started sending me trivial things encrypted it'd probably hit the bit bucket unread.

  • There's no need to use RSA (Score:5)

    by Greg W. ( 15623 ) on Monday January 24, 2000 @04:32AM (#1343957) Homepage

    Because RSA was patented, replacement algorithms were developed and used instead. GNU Privacy Guard [gnupg.org] as well as PGP 5.0 [pgpi.org] and later use Diffie-Hellman, DSA and/or ElGamal instead of RSA.

    Besides, PGP doesn't use public-key encryption for the whole message. It uses RSA (or equivalent) only to encrypt a random "session key", which is then applied to the whole message using a symmetric cipher. PGP 2.x uses the IDEA cipher, which is also patented, and which is patented more widely than in just the USA.

    Because of all the patent nonsense, I urge everyone who still uses PGP 2.x to upgrade to PGP 5.0 or higher, or to switch to GnuPG.

    If you don't use any encryption tools yet, I recommend GnuPG [gnupg.org].

Slashdot Top Deals

It is clear that the individual who persecutes a man, his brother, because he is not of the same opinion, is a monster. - Voltaire

Close