Slashdot Mirror
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."
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.
Cypherpunks: Civil Liberty Through Complex Mathematics. Those who live by the sword die by the arrow.
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.
I don't know, maybe we should ask Bill Gates?
e s.html:
From http://www.vi s.caltech.edu/~pz/letters-from-the-front/bill-gat
"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.)
--
Someone you trust is one of us.
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.
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
What's that smell? Ah, that's my karma burning...
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
Here's a somewhat simplified taste of how RSA works, for those of you who are curious.
.. z=25. Encrypt in blocks of three like this:
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<b<phi(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
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.
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...
That's not fair! I had this huge RSA party planned. What am I going to do with all of these crackers and fish?
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.
Hey, Teach?
Refresh my memory, how do you factor n into p and q again?
:)
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
-----BEGIN GEEK CODE BLOCK----- Version: 3.12 GAT d-- a? C++ UX+ L++ P++ E--- W+++$ N++ o-- !K !w O---- M++$ !V PS++