Slashdot Mirror
Is the RSAs Loss Everyone's Gain?
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.
← Back to Stories (view on slashdot.org)
Being vaguely familiar with how patents work, I did a search at the IBM Patent server (http://www.patents.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?
What part of "gestalt" don't you understand?
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.
If you're not part of the solution, you're part of the precipitate.
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 you're not part of the solution, you're part of the precipitate.
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.
If you're not part of the solution, you're part of the precipitate.
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.
We call it art because we have names for the things we understand.
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.
We call it art because we have names for the things we understand.
For all P & Q greater than 3, one of the following is always true:
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.
-- Slashdot sucks.
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.
-- Slashdot sucks.
Do you have a source for your assertion that a large percentage of the flat earth society are in the south? Just curious.
-- Slashdot sucks.
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.
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.
"Cause there's 40 different shades of black, so many fortresses and ways to attack, so why you complainin'?"
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)
/* The beatings will continue until morale improves. */
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)
US businesses that currently accept chip and PIN/signature
"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.
-- I can't think of anything witty to put here. Sorry.
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 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
--
-=DaveHowe=-
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...)
The real irony is that I can't then E-Mail it back to Finnland without facing prosecution.
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
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.
- 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.
-- "This is the Space Age, and we are Here To Go" - W.S.Burroughs
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.
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) 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.
----
----
Open mind, insert foot.
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.
Remember that what's inside of you doesn't matter because nobody can see it.
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...
If you're not part of the solution, you're part of the precipitate.
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.
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.
According to *The Code Book* by Simon Singh, the folks at Bletchley Park independently invented public key encryption before RSA did. Unfortunately it could not be publicised or patented, as it was a military secret.
Great Windows SFTP Server!
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?
*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.)
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
Read the very informative page Opposing Copyright Extension.
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.
--
"L'IT c'est moi!"
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!
-- Slashdot sucks.
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.
Because RSA was patented, replacement algorithms were developed and used instead. GNU Privacy Guard as well as PGP 5.0 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.