RSA Released Into The Public Domain - Slashdot (original) (raw)
- Is ssh or apache ssl based on the RSA algorithm or the BSAFE software?
- 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.
- It sure is nice of them to officially release this to the public domain a whole two weeks before it would have automatically gone there anyway.
Edward Burr - OK, want to quantifify _when_ you tried ogg?
Cos right after the beta announcement, I got sound quality comparable to MP3, at the same encoding rate.
That's across my entire music collection, much of which is the 'nightmare' scenario - acappella, or simple acoustic perfromances.
Yes, it takes a long time. That is true. No one has ever tried to deny that. It takes about 10 times longer than MP3 to encode, and about twice as much porcessor power as MP3 to decode. Or, 6% in my case.
This is totally unoptimised code. The bleeding edge CVS is starting to optimise, so watch the processor use tumble. - First, RSA really was a major invention. Public-key cryptography was at first believed to be impossible. Even after the basic concept was developed, the first algorithm (the knapsack problem) turned out to be easily invertable and thus insecure. The advantage of RSA is that it exploits a problem, factoring the product of two primes, that's received considerable attention in the mathematical community without being cracked.
Second, RSA got their 17 years of exclusivity, and now it's public domain. That's how patents work. It took a long time to build a business on the technology. I visited RSA around ten years ago, when they had a tiny suite of offices in Redwood City, no significant customer base, and a hard-to-use product for DOS.
Third, now that it's finally out there, it's time for the open-source community to get it into standard electronic mail. Now that PGP has been discovered to have a backdoor, that's not the way to go. - AFAIK there's more than one LZW-related patent, with different expiration times. Can't remember the exact details, though.
But yes, I do expect similar moves from Unisys when their LZW patent(s) come close to expiring time. Maybe they'll force their managerial staff to cut out those ridiculous upward-pointing cones of hair from the side of their heads, too. - Rather than use the weird watermarking schemes I've read about, maybe they could now use 128-bit CAST and RSA in the "DVD 2.0" spec to encrypt the disks. The RSA Patent's expired, the US relaxed crypto export regulations, and AFAIK CAST's been royalty-free forever. Or they could use Triple-DES.
Hell, it worked for millions of PGP users, even with the ADK bug. - The whole point of a patent is that it is anti-competitive. It is there to protect you from competition so that you are encouraged to publicise the work.
- One such program was PuTTY, which is actually written, maintained and hosted by one man, in the United Kingdom. Same with a lot of other things. Nothing illegal about him writing it, but it was illegal for an American to download and use it within their national borders.
- It's the other way around. You already have primes p and q, and you just multiply to find n.
- Well disney wanted to coninue their revenue
stream for Donald Duck et al, and lobbyed
for an extension
... unfortunately succesfully
..
-- - I had the same problem, however a newer version has since been released - called oggenc rather than ogglame and this works correctly for me.
Still can't change details in Winamp but that is a plugin functionality thing rather than an ogg problem.
The only downer, for me, is that playback takes about 10%-15% processor time - my computer: Celeron 300a@450, W2K. OGG bitrate: VBR based around 192kbits. This is just enough of a hit to make Quake3 jerky
:(
<O O>
( \/ )
X X
- To encourage people to make public their inventions so that they eventually enter the public domain.
You were allowed to look at it. You were supposed to look at it. But you were not supposed to use it without paying RSA until the patent expires or they say you can.
They just said you can.
Cheers,
Ben - What about EL Gamal's problem with choosing the same 'k' twice?
...provided that I have creatively improved upon the original.
"Creative" has a very specific legal/wording meaning to the US Patent Office, which often seems to be much different than what a common, ordinary layperson would consider "creative".
I've been watching some companies get new patents solely by using feedback from the Patent Office about why a particular patent was not "creative" to change the wording of their patent so it became "creative" - all w/o actually attempting to even make a prototype or a design based on the ideas in the patent.- Sorry, I didn't realize you were being cute.
:) Well, it's simple - first you adjust the Heisenberg Compensators - then it's a simple matter of constructing an inverse tacheon field... - SSH uses RSA for the public/private keys and authentication, but other algorithms for the actual stream ciphers when the connection is open.
Some ciphers are free but weak, some are free, strong, and slow (Triple DES), while IDEA is faster, strong, but covered by it's own patent (Patent 5,214,703), no connection to RSA...
So the answer to your question is, NO, not if you include IDEA. Details (in german) [ascom.ch]. - This is good news for me indeed. I have
PGP key which was generated 5 years ago
with RSA algorithm. I am using it in several
places and do not really want to have new key
generated.
I hope this news will allow me to use my old
PGP key in GPG. - 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. - This move will some away from them. But most companies will stay with RSA because of the name value they give for security.
- Couldn't you just have said "the US patent system sucks donkey balls" and be done with it?
- One last poke in the eye of the community before the patent expires. It'd be kind of like unisys releasing LZW into public domain 14 days before the patent expires.
- "Does this mean that "A" has finally found a NP-space P-time inverse, and the whole algorithm becomes no more than a toy! "
If he did, he would win that million dollar prize that was posted on
/. a few months back. He probably could make much more moolah just using his P time algorithm... Reminds me of the movie Sneakers. I wonder what goes on behind our backs...
Plus, with quantum computing moving along, all (most) security will be obsolete.
Ed - RSA today announced that they have recruited some of the lawyers involved in defending the MPAA's CSS scheme.
They hope that with legal backing they can extend the patent on their algorithm indefinitely. Also they have found (looking back at their patent) that they own all public key cryptography patents and anyone infringing on them will be forced to pay up. Anyone refusing will be struck down - i'm told adi shamir is quite hot with a minigun
:) - Uhh, dude, that's what a patent is - when you patent it, you are forced to reveal it to the public.
Patents just make sure that no one else is allowed to make a product based on the idea unless you let them.
-- - Yea, but that is not important, because mp3's replacment is just around the corner, it is called vorbis, it is very open and it is way better than mp3
:) - When I first looked at the FAQ, I thought they were being very apostrophe shy, omitting them from words like "companys", "securitys" etc. However, looking at the page again in Netscape instead of Lynx shows that they're just just using Microsoft moronic HTML [fourmilab.ch]. Sigh.
- dont't make another licensig problem out of it, please! i haven't read the licensing info yet.
- Gosh...after almost 17 years, RSA (the company) decides to release RSA (the algorithm) into the public domain. And it's two whole weeks before the patent expires! Gosh! You guys are so swell! I'm going to use RSA in all my security products to support your selflessness and your generous to the world community!
Bah.
Setting aside one's beliefs on the idea behind being able to get a patent on math, there's the underlying assumption from RSA (the company) that we should be grateful because they've deigned to surrender their oh-so-valuable intellectual property after extracting only 99.77% of the life of the patent. Don't do me any favors, guys -- I'll find my own algorithms. - ...am I finally free to use that SSH client in the US now (which I've been using for years.. sssshhhhh....) or does RSA have some other means of bending me over a barrel if they find out?
- As a footnote, I believe this is also why C2Net was acquired by Red Hat. C2Net could no longer show a revenue model licensing their Stronghold software for a fee that is now available for free (as Apache/mod_ssl). Red Hat liked C2Net's management team and their technical expertise and chose to pick them up at the right price.
- Funny...I tried a comparison myself just this past weekend, using some freshly-ripped
.WAV files. I encoded them to MP3 with LAME 3.70, and to OGG format with oggenc -m2 (to get similar bitrates, approximately 128 Kbps). They sounded pretty much the same when played back over both XMMS and WinAmp (with appropriate Vorbis plugins installed in each case)...and I was listening over headphones to check them out. The file sizes were very similar, too.
Now, I'll grant you this is a bit unscientific (hell, it's not even in the same ballpark with "scientific"), but it seems to me that the Vorbis guys have done a hell of a job thusfar, even considering the format and tools are still "beta." If there were a little better support for comment tags in the player tools, I would probably be switching everything over from MP3 to OGG format right now...
Eric
-- - Yes, such corporate generosity is absolutely unprecedented. They release their patent to the public domain a whopping 2 weeks before it expires. Don't fall for this cheap publicity stunt. They're just trying to grab the headlines away from the RSA patent expiration parties. [slashdot.org]
- Just look at the first couple of lines of the press release:
RSA Security Releases RSA Encryption Algorithm into Public Domain
"c = me mod n" Made Available Two Weeks Early
This basically says "We patented this equation". The whole fiasco surrounding software and business patents is going to get really ugly. At some point the ridiculousness of these kinds of patents will become obvious, even to the many judges in the US that have their heads planted firmly up their rectums. If we could get the politicians to get their hands out of the lobyists' pockets things would move along even faster.
Oh, yeah, I almost forgot:
2 + 2 = 4
patent pending
And boy, are you all gonna pay for using that. Anyone who has ever said that without getting a license from me will be really sorry. - Actually, i was sucessful in being moderated as both a troll AND flamebait. Woohoo! This has got to be the best story ever. (My story, I got first post, karma whore, troll, and flaimbait). =^)
Well, it certainly made my day.
And your hypothesis about meta moderating seems to work. This post is interesting. ;^)
-legolas
i've looked at love from both sides now. from win and lose, and still somehow... - You're right; I had our company do the exact same thing.
I guess I can run Apache/SSL on our backup server now; this is excellent news, even though we all knew it was coming.
What happens to the RSA firm? Do they more or less go out of business now that they have nothing to sell?
D
---- - 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. - No. US patents are valid in the US only. In the UK there are hardly any software patents.
- (Background: you have to answer three questions to get a shirt.)
The first "question" is "The patent expiration will allow more developers to create secure applications, making the electronic world a more secure place?"
The only answers you can give are "True" and "False". What I want is a "That's neither a question nor a true/false statement!" link, ala Slashdot polls... - Now we'll have to quickly change the dates for the planned release parties. I've started by opening a large bottle of Domus beer and will proceed to get nothing done the rest of the day.
But this is good news that RSA isn't going to try any kind of tricks to extend their patent or somehow deny us this very valuable algorithm. Expect to see some good implementations of RSA being released into the wild in the next few hours/days.
the AC - My God Man, have you even *read* the UK's proposed Regulation of Investigatory Powers bill, the idea of 'guilty until you prove yourself innocent' seems a little inquisitorial for my liking. By far my favorite part, however, is that you get 2 years in prison if you can't prove you don't have the private key the police want, and another 5 years if you complain about it.
Now I'm all in favour of the 'contempt of court' laws, but hang on a minute here...
Further, and more in-depth commentary can be found at Stand.org.uk [stand.org.uk] for those who are interested.
Craig. - YES!
You know what this means don't you? I can compile in SSL support for commerical use into Apache and not have to pay C2 (the makers of stronghold) $1000 a license key! 45(orisit90?)fortheServercertandyouhaveacommericalproffesinalSSLserver.Ifyouwanttousebuzzwords"Ecommercesolutionfor45 (or is it 90?) for the Server cert and you have a commerical proffesinal SSL server. If you want to use buzzwords "Ecommerce solution for 45(orisit90?)fortheServercertandyouhaveacommericalproffesinalSSLserver.Ifyouwanttousebuzzwords"Ecommercesolutionfor45 a year"! - My question is, how long before this is incorporated into GPG? Of course, the obvious answer is 'as quickly as you can write it yourself' :-).
As far as I know, RSA is more secure than both El Gamal, and DSA, the algorithms currently used for encryption and signing in GPG. In fact, I believe El Gamal becomes horribly insecure if the same random number is used twice when running the algorithm. Also, RSA supports longer key lengths than DSA.
I want to create myself a big, 4-8k bit RSA root signing key scheduled to expire in 10 years, and then at 2 year intervals replace my main signing and encryption keys with new ones signed by the big RSA root key.
I know how RSA works, but not how to generate the large random primes that are required for a big key. - They freed up their patent two weeks before it expired, not a lot of guts in that!
At least they didn't try to extend the patent by tricking the patent office. For instance, "c = me mod n" is the formula for RSA. So they patented that formula back in 1983, then in 1985 they could have patented the formula "me = c mod n". Mathematically the same formula of course, but that's ok. The patent office will let you patent a formula or algorithm that has already been patented, as long as patent is worded differently enough that the monkey who rubber-stamps patents doesn't notice. The comp.compression FAQ has a section on patents [faqs.org], which has several patents for identical compression algorithms that the patent office rubber-stamp monkey didn't notice.
They could just make up a new patent every year. Like "Using RSA to exchange DES keys", then "Using RSA to exchange IDEA keys", "Using RSA to exchange keys over computers connected by telecommunication lines", "Using RSA to exchange keys over the internet", "Using RSA to exchange keys between web browsers". They could probably keep this up for as long as they wanted. - Actually it was just last week, and I actually thought it sounded much worse than MP3.
I will make the point that I'm listening with Sony MDR-V6 studio headphones, not tinny little speakers.
Perhaps it was just the implementation, like I said. But I want something good today, not in 3 years.
WMA takes about twice as long to encode as MP3 does, but one receives a benefit... it sounds much much better at lower bit rate. i.e. in my experience WMA at 160kbps is equivalant to MP3 at around 256kbps.
The inconvenience of spending $30 on a MP3 encoder is far less of a cost than spending 10 times the computing cycles trying to encode your CD's on a format which is free. I'd rather spend the money and get something that's quality and easy to use than frustrate myself with a freebie.
The inconvenience of a license is far less painful than poor quality software. - Wrong. The program was/is legal, using it without leave of the patent holder was not. I can write program after program using the 'patented' method, at any time, with no fear of being sued so long as I only use the program for personal educational purposes. Now I can give the program away or sell it without having to pay a fee to RSA.
"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- Is ssh or apache ssl based on the RSA algorithm or the BSAFE software?
Well, OpenSSL [openssl.org] and ModSSL are both based on SSLeay & both contain RSA algorithms. That's why it's recommended that if you're in the US and using OpenSSL, you disable RSA (and IDEA) ciphers during config. It's in the FAQ. [openssl.org] - Why not ignore .mp3 and use .ogg for your encoding?
Even though there is a common Winamp plugin (from vorbis.com) to play .ogg files of my band's music, the Napster client does not recognize .ogg. But there's a workaround [tripod.com], right?
<O
( \
XGNOME vs. KDE: the game! [8m.com]
- Most of the RSA implementations produced in the US use either RSA's RSAREF reference implementation for non-commercial use, or RSA's BSAFE toolkit. RSAREF is still copyrighted code, and says you need to follow RSA's license to use it.
Now that the RSA algorithm is no longer patented, anybody can write a compatible implementation that doesn't have the license restrictions (no export to foreigners, limited access to functions without special permission etc.)
I'd like to see a free software version - either public domain, Library GPL, BSD, Artistic license, whatever. Who's first? - 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] - Big deal. You don't need to send a working copy of your atomic particle-smasher to the Patent Office to get a patent on it. What difference does it make whether they've actually built one or not?
The patent is not on the manifestation of the idea. The patent is on the idea itself.
-----------
"You can't shake the Devil's hand and say you're only kidding."
- From http://www.homeoffice.gov.uk/ripa/ripa ct.htm [homeoffice.gov.uk]:
"The Regulation of Investigatory Powers (RIP) Bill was introduced in the House of Commons on 9th February 2000 and completed its Parliamentary passage on 26 July. The Bill received Royal Assent on 28 July. " - n's only factors are p and q. p and q are prime. In that case, phi(n) = (p-1)(q-1). That's all you really need to know for RSA.
- What are the odds of that? You're supposed to pick k at random and if you have a half decent generator then that's just not going to happen.
If you're paranoid about it then keep a list of used Ks and don't reuse them. Really, it's not a problem though, you're far far more likely to pick a poor IDEA or 3DES key if you're using something like GPG or PGP. - They are all based on Fermat, but yes, Miller's algorithm is just an application of Fermat.
It misses Carmicheal numbers. It does work correctly for Mersenne numbers, you should avoid those for other obvious reasons though. - If you'd been reading slashdot for the last couple days, you'd know that the correct procedure for legalizing past development is to ask RMS for forgiveness.
;-) - Why not ignore
.mp3 and use
.ogg for your encoding? It's free and free. Plugins are available for all popular plays on many platforms.
It's better (arguably) than mp3 anyway.
http://vorbis.com - Took me a second to switch gears. I initially read that as RMS released to the public.
And the sad thing was that it made sense, too. - Aside from the fact mentioned in the other reply (Patent Office _can_ request that you submit a working device), you're missing the point.
Said companies in my example isn't being REALLY creative - they're just juggling words in their patent until they meet the Patent Office's definition of "creative" (which has more to do with semantic minutea & overloaded claims inspectors than real creativity). - Obviously the moderators are on crack (and yes, I'm moderator myself quite often), but to first moderate the first one up, and then this one down. Exactly what was the troll part of that post? =) (If it wasn't meta-trolling that is. It's classified as troll because you say so? Can I get my post moderated up by saying they're insightful?)
- Nope, the concept of "strong encryption technique" is now the intellectual property of Digital:Convergence, as used in their Cue:Cat. The term "XOR" has been renamed "CCC"; details require a NDA.
Their encryption is so strong that typing "Digital:Convergence" into your browser's Address/Location field will fail to search for them. - 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.
IIRC, they also applied for patents in Great Britain, Germany, France and maybe another. Other countries were "off the hook", but products using the algorithm could not be exported to countries where the patent was in effect. - Patents are supposed to allow a time limited monopoly to exploit an invention, to give chance to recoupe development costs, in return for the inventor publishing details of the technique that makes their invention novel.
The details of RSA was published before it was patented, and it was not funded by RSA in the first place.
Also, it seems to me that it's a discovery and not an invention.
Sounds more like a classic abuse of the whole concept of patents to me.
To add insult to injury, they didn't even write a decent implementation of it. - 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<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
.. 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. - Well, it's nice to know they didn't fight it (they'll probably go down in the history books as having voluntarily released it!) with other patents and nonsense like that.
But now what am I going to be partying for on the 20th? The two-week anniversary? - Given that they weren't the first to discover the algorithm. The first discoverer was gagged by national security (that's GCHQ for you).
I still view it as mathematics, however, and thus not "a device" for anything.
Or...
Does this mean that "A" has finally found a NP-space P-time inverse, and the whole algorithm becomes no more than a toy!
FatPhil - FYI (fresh off the mailing list), RSA support will be built in RSN... in fact, if I read/remember right, it _is_ built in right now, at least in current CVS.
(Btw, moderators, as of while I'm writing this, it's not redundant AFAIK). - Making certain that your product continues to be the algorithm of choice and that your continued development efforts will be welcomed into the market. Sounds like a heads up play to me. Bravo!!
- I would think the number of people willing to buy a license to use RSA is dwindling down to almost no one as the expiration date rapidly approaches. This way they get a little bit of free press and hopefully a positive spin when the patent does expire.
- Now maybe I was using an older implementation, but...
I tried to encode something using the
.ogg format as presented in Media Jukebox or some such app.
What I found was:
- It took an incredibly long time.
- It sounded incredibly bad, even worse than MP3
Granted, it'll probably improve. But I'm a big fan of using stuff that works well today. The inconvenience to me of using a licensed format like MP3 or WMA is incredibly small. When compared to the inconvenience of using a pre-alpha poorly implemented format like OGG, what's the point? - 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... - Finally! Putty and Nifty-Telnet you are now mine!
:) - That's simply not true. Patent law encourages people to build upon the ideas of others. A mouse-trap may be patented, but the patent system we use in the US allows me to develop a new mouse-trap based on the original specs and patent my design, provided that I have creatively improved upon the original.
-----------
"You can't shake the Devil's hand and say you're only kidding."
- I would love it if a new legal finding was made that US Patent Law had to be reinterpreted because the original specification had a faded decimal point - that the intent was to provide patents for 1.7 years instead of 17 years.
Not likely. Back when the original patent law was passed setting the "limited times," decimal for years was not common. The patent law drafters would have written "one (1) year and 255 days" were that their intent.
"limited times" in the Constitutional clause authorizing patents and copyrights has a huge loophole [8m.com].
<O
( \
XGNOME vs. KDE: the game! [8m.com] - They probably just ordered way too many T-shirts, and needed a reason to give them away. Mine's in the mail!
- The primes don't actually need to be primes! Industrial strength pseudo-primes will do just as well.
http://www.utm.edu/research/primes/
has loads of info on primes and pseudo-primes.
I recommend "primeform" and its successor "pfgw" as a generator of strong pseudo-primes (SPRPs) as you can chose what form they have:
e.g. if I wawnted a 4000 bit key I could ask
For n=1 to 1000
For k=1 to 2^16-1 step 2
Is 2^4000 + 5614*n*n + k prime?
And just wait a few seconds.
You have pretty much absolute freedom over the expression you try, so you can even feed it a 1000bit random number and ask it top find the next SPRP after that number.
Primeform has its own forum on egroups:
http://www.egroups.com/group/primeform
FatPhil
(a top 20 producer of titanic primes) - GPG supports plugins and there has been one available for RSA for quite some time now. You can get it from here [ftp.guug.de] for example. Compilation instructions are included. Just ignore the legal shit at the beginning.
I've been using it already. I don't care about the patent: algorithms are not patentable in Europe, and RSA Security hasn't even tried to apply for it here. - "The RSA Algorithm Patent Expired, and All I Got Was This Lousy T-Shirt"
- 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. - Despite the fact that we were given it to analyse and devise methods of breaking when we were in high school maths.
Second year univeristy maths touched on it and it came into my computing course as well.
It's not like they are releasing the worlds best kept secret.
On the other hand they should be applauded for not behaving like complete twats with their algorithm, ala MPAA
:) - For the same reason that I bother to swat a fly; both trolls and flies eat shit and bother people
Trolls eat shit
You are feeding a troll
errr ..... you said it, brother, not me. - Certainly assuming a good RNG, the odds of repeating k within your lifetime are slim-to-none.
But suppose you have an evil adversary who can screw with your RNG, perhaps for only a limited time. If he compromises it for a few messages that encrypt a random session key with RSA, he's only cracked those few messages. If he compromises it for a couple of messages encrypted with ElGamal, he's got your private key for every message until you retire it.
A very remote possibility for most people, of course. But it makes me uneasy. - 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... - To generate large random primes (or actually pseudoprimes since they don't fully test them) look up Miller's algorithm or the Miller-Rabin algorithm. It works like this:
if p is prime them for some a You can prove that the reverse is usually true, if a**(p-1) mod p = 1 then p is prime "most, but not all of the time"
So you pick out 100 or 200 values for a. And if the second part is only 50% true (ie: if it equals one then there is a 50% chance the p is prime) then after doing this 100 or 200 times for a bunch of different values of a you end up with a pretty good odds that p is prime. 50% ** 100 (or 200) is your error and that's pretty small.
As for RSA being more secure than El Gamal, I believe is has been shown that ElGamal is at least as secure as RSA and a lot of people believe it to be more secure. DSA on the other hand is really just a way of applying ElGamal and so it has some key size restraints to comply with a standard. Don't use DSA if you're not happy with the key length, sign with ElGamal and pick as big a modulus as you want. - That's probably because the actual RSA algorithm is fairly easy to implement for anyone with a bit of training in maths.
Just shouting 'open source this' at everything won't necessarily get you moderated up...
the d00d - 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 - long may they reap the rewards from it.
How? - but my main one is: does the expiration of the patent mean that RSA will be retroactively included in systems such as GnuPG?
The central advantage of GnuPG and SSH protocol version 2 (as far as I can tell) is simply that they don't use patent-encumbered algorithms, and RSA is "the big one" in that category. Of necessity, the free world has moved on to DSA and ElGamal, but do they have any technical (non-political) advantage?
I'm particularly intrigued by the fact that if you're using ElGamal and for whatever dumb reason (bad RNG or just wild luck) you choose the same k twice, you give away your private key. Do any of the popular cryptosystems keep track of used _k_s to make sure they don't repeat, or do they just rely on probability? Does RSA have any comparable weakness? - Any conduct that makes, uses, sells or offers for sale (or imports into the US) of an infringing apparatus is infringing.
However, while the initial act of making might have infringed, acts occurring subequent to the date of expiration of the patent (or, as in this case, the date of dedication) making, using or selling is not actionable. The devil is in the details of course, but users subsequent to the term of the patent are not likely to be liable for infringement. 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...- The whole point is that you don't HAVE to license RSAREF to use RSA any more -- In other words, everybody can now use the international versions of pgp/gpg without looking over their shoulder.
- I never was too clear on the RSA licensing thing. My company paid for Stronghold for the sole purpose of avoiding such difficulties. Does this mean that I can scrap that and use Apache/OpenSSL for my B2B site? It looks to me like I can, but I'd like to keep the company 100% in the clear.
The real Threed's /. ID is lower than the real Bruce Perens'.
--Threed - RSA is just securing a little good PR on the back end of their patent.
What they hope to do is further establish their namebrand as the standard in encryption technology.
Of course, now openssh/openssl will get wrapped in so many open source projects it will get silly fast. For example, I bet it takes about 1 day for Mozilla to incorporate openssl in its default build.
This move marks a large step forward for open source secure products.