RSA Released Into The Public Domain

Legolas-Greenleaf writes "According to the this news release on RSA Security's website, the RSA algorithm was released into the public domain today (September 6th, 2000). This is in advance of their US patent expiring on the 20th. There is some more information in their RSA FAQ."

Re:big deal

The big deal is that you can now in the US use apps based off of it legally. This *is* a big deal for those of us trying to do security work in the states. It means I can now give my clients the really neat toys.

Re:So many questions...

A single RSA key can be used for both signing and encryption (thought he wisdom of this is debatable).

RSA keys are far smaller than DH-EG ones.

RSA signature verification (the most commonly performed operation in the real world) is far faster than DSA.

RSA is far more widely deployed than DSA and especially DH-EG.

Re: you left something out ...

I don't know, maybe we should ask Bill Gates?

From http://www.vi s.caltech.edu/~pz/letters-from-the-front/bill-gate s.html [caltech.edu]:

"The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers." (Bill Gates, The Road Ahead, Viking Penguin (1995), p. 265.)

--

RSA vs El Gamal

RSA is built on the integer factorization problem; El Gamal is built on the discrete logarithm problem. If you can get a general solution for the discrete logarithm problem, then you're also going to get a solution for the integer factorization problem--but knowing how to factor arbitrarily large numbers doesn't help you with discrete logs.

Insofar as keysize goes, 2048 bits is plenty sufficient for every attack we can foresee. If you want to be truly paranoid, go for 3072 bits; even with quantum computation, it's still as hard as RSA-1536.

Personally, I don't think RSA is ever going to be cracked by brute force--so this trend among the cryptoparanoid towards larger and larger keys is somewhat silly. I think it's far more likely that either (a) a general solution to the factorization problem will be discovered which runs in polynomial time, utterly destroying RSA, or (b) an attack against RSA will be discovered which does not depend on factorization.

Remember that the integer factorization problem has never been proven to be difficult, only conjectured to be so--and as time goes on, it gets less and less difficult. More than that, while RSA is built on the integer factorization problem, nobody has ever proved that you need to factor very large numbers in order to break RSA.

My money is on El Gamal--it seems to be built on stronger mathematical foundations.

This is what patents are for!

"RSA Security's commercialization of the RSA patent helped create an entire industry of highly secure, interoperable products that are the foundation of the worldwide online economy. Releasing the RSA algorithm into the public domain now is a symbolic next step in the evolution of this market, as we believe it will cement the position of RSA encryption as the standard in all categories of wired and wireless applications and devices."

There has been so much discussion against the issuing and abuse of patent and trademark law; occasionally we should applaud those who do it right. The RSA has handled their patent beautifully while making good business decisions.

My hat is off to them.

Coincidence is the Superstition of Science

factoring n into p and q

Factoring n into p and q is necessary for breaking the RSA code. If you factor n into p and q, you can generate the inverse of a. RSA relies on the fact that factoring the product of two primes is extremely "difficult" while multiplying p and q to get n is "easy".
For more info on what easy and difficult really mean, read up on Big-O notation (i.e. O(n) is linear running time, O(2^n) is exponential growth) and NP completeness. :)
Factoring:
Well, of course, you can brute force p and check to see whether you get an integer q. If you're using large primes (300 digits or so) for p and q, prepare to be long dead before you get q with our current computing.

I won't go into detail, but here are some popular factoring methods for you to look for, and a link:
Pollard Rho method
Pollard P-1 method
ECM (Elliptic Curve method)
Multiple Polynomial Quadratic Sieve (MPQS)
According to the link below, "The best general-purpose factoring algorithm today is the Number Field Sieve"(NFS)

For more info including Big-O notation (i.e. an idea of how fast the algorithms work as the size of n increases), check out:
http://www.rsasecurity.com/rsalab s/faq/2-3-4.html [rsasecurity.com]

how RSA works

Here's a somewhat simplified taste of how RSA works, for those of you who are curious.

Note: I took this from a document that I wrote for my students, so this is how I personally had them implement RSA, NOT how RSA is really done in real life. But the basic premise of key generation is the same.
Background math: gcd is greatest common divisor. mod means modular arithmetic.

To generate your personal key:
1. Generate two prime numbers, p and q.
2. Calculate n = p*q.
2. Calculate phi(n) = (p-1)(q-1).
3. Pick a public key b where 0&#60b&#60phi(n) and gcd(b,phi(n))=1.
4. Calculate the private key a such that a=b^-1 mod phi(n) (multiplicative inverse). Make sure pub is less than phi(n), gcd(phi(n),b)=1, and a>0.
5. n and the public key can be published in a directory. Keep the private key secret.

To crack a key given n and the public key b:
1. Factor n into p and q.
2. Calculate phi(n) = (p-1)(q-1).
3. Calculate the private key; it's a=b^-1 mod phi(n).

To encrypt code, translate from an array of characters to numbers.
let a=0 .. z=25. Encrypt in blocks of three like this:
abc = 0*26*26 + 1*26 + 2 = 28
dog = 3*26*26 + 14*26 + 6 = 2398
cat = 2*26*26 + 0*26 + 19 = 1371
zzz = 25*26*26 + 25*26 + 25 = 17575

Call chunks of text converted to numbers m (for message). Compute m^b mod n. Each of these numbers go on separate lines in the file.
To decrypt code, do the process in reverse. Call the encrypted message m. Compute m^a mod n. Then you can convert from unencrypted numbers back into plaintext.
You can also do a double encryption (digital signature) by taking already encrypted code and encrypting those numbers. Suppose Alice wants to send a message to Bob which only Bob can decrypt and Bob knows can only have come from Alice. Alice uses her own private key to encrypt the message. Then she applies Bob's public key and gives the file to Bob. Bob takes the file and applies his private key to it, and then Alice's public key, leaving him with the plaintext. This ensures that Alice sent the message and only Bob can decode it.

Re:Public Domain? What's the angle here?

Why did RSA Security release the RSA algorithm into the public domain early?
So much misinformation has been spread recently regarding the expiration of the RSA algorithm patent that the company wanted to create an opportunity to state the facts. RSA Security's commercialization of the RSA patent helped create an entire industry of highly secure, interoperable products that are the foundation of the worldwide online economy. Releasing the RSA algorithm into the public domain now is a symbolic next step in the evolution of this market, as it will help cement the position of RSA encryption as the standard in all categories of wired and wireless applications and devices. RSA Security intends to continue to offer the world's premier implementation of the RSA algorithm and all other relevant encryption technologies in our RSA BSAFE software solutions and remains confident in our leadership in the encryption market.

That's why they made an FAQ. For Frequently Asked Questions.
-legolas

i've looked at love from both sides now. from win and lose, and still somehow...

Wait!

That's not fair! I had this huge RSA party planned. What am I going to do with all of these crackers and fish?

Symbolism and significance.

It might be relatively insignificant from a practical standpoint (it's what, two weeks), but I respect the symbolism of releasing RSA to the public domain just ever so slightly early.

This means that I can now legally use a little SSH program I found for Windows, and I needn't have any qualms about infringement. While I may not have been too concerned for myself at home, I haven't used the program at work (a public school system), since companies love finding licensing problems in public institutions.

Anyway, to me, releasing RSA early is like getting one of those little gold stars on the poster in grade school. It may not have any significant impact on anything at all, but it does make you feel like there's just a little good in there.

Re:Wait!

What am I going to do with all of these crackers and fish?
You can feed the fish to the crackers, and then tell them:
"Dudes, sorry about this, now go home and crack the NASA site or something".

Oh, you meant crackers as in cookies! Silly me...

you left something out ...

Hey, Teach?

Refresh my memory, how do you factor n into p and q again?

:)

Public domain is better than expired

My guess is that RSA did this to avoid someone else re-patenting a twist on the RSA algorithm. It's much safer in the public-domain than it is as an expired patent.

In any case, my guess is that RSA has patented *around* the original patent, covering such twists as public key encryption over e-mail, etc. and those patents will most likely extend for the next couple of years.

Karen

So how will this affect us?

As I understand it, this only has a direct effect in the US - the various products that we in the rest of the world have been using for ages haven't been subject to this patent because it's a US-only patent.

I'm not going to open the can of worms that would result from me flaming the US Patent Office...

So, what this means is that it will now be possible for non-US companies like Baltimore (Irish company) to sell RSA-based products in the US without having to worry about having to licence the PSA algorithm from the RSA company.

There's a point - I wonder if a patent could be contested on the basis that it is anti-competitive.

Anyway, getting back to the point, the other advantage will be that open source products which use the RSA algorithm and which, until now could not be used for commercial purposes in the U.S., can now be deployed by companies.

Considering that a large percentage of open source developers and projects are based in the United States, is this likely to lead to more widespread and better integration of cryptography with open source software packages?

D.
..is for Downloading PGP from a US host instead of being forced to put up with the International version...