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."

Comments

how RSA works

[pemerson]

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.

Symbolism and significance.

[ClayJar]

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.