I recently finished reading The Code Book by Simon Singh (ISBN:
0-385-49532-3) and it explains the math behind the RSA encryption
scheme.

I started asking myself why, if we have the public key, we can?t use
it to decrypt the cipher. Then I looked at the math and read up on
modular arithmetic and answered my own damn question. Simply speaking, it's
mathematically impossible. That is, according to the book and many
other sources I've looked into.

My question is this: if I found a SIMPLE way to crack RSA regardless
of the length of the key, would it be a violation of the Digital
Millenium Copyright Act? Mind you, I'm not saying that I *did* crack
RSA. I'm simply asking if I should bother following up on something,
should I discover it.

Yes, it is legal to crack RSA. Indeed, RSA Laboratories itself has
regularly encouraged people to break its encryption by issuing
factoring challenges, complete with cash rewards for so doing. They
even give suggestions. The most recent number factored was 512 bits
(155 digits) in length (1999). They expect the next largest challenge
number (576 bits) to be factored within a year. If someone can find a
simple technique to factor that and larger numbers, then RSA would be
obliged to pay the respective rewards.



The RSA Factoring Challenge FAQ
http://www.rsasecurity.com/rsalabs/challenges/factoring/faq.html

"What is the RSA Factoring Challenge?

The RSA Factoring challenge is an effort, sponsored by RSA
Laboratories, to learn about the actual difficulty of factoring large
numbers of the type used in RSA keys. A set of eight challenge
numbers, ranging in size from 576 bits to 2048 bits is posted here
<http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html>.
Each number is the product of two large primes, similar to the modulus
of an RSA key pair."


The RSA Challenge Numbers
http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html

"A link to each of the eight RSA challenge numbers is listed below.
The numbers are designated "RSA-XXXX", where XXXX is the number's
length, in bits. The values are presented as decimal strings, with the
most significant digit first. Also listed are the number of digits,
the decimal sum of the digits and the dollar amount to be awarded for
a successful factorization.

Each challenge number may be downloaded as an ASCII text file. The
entire challenge list may be downloaded, in ASCII text format, using
the link below. Challenge Number Prize ($US) Status Submission Date
Submitter(s)
RSA-576 <#RSA576> $10,000 Not Factored    
RSA-640 <#RSA640> $20,000 Not Factored    
RSA-704 <#RSA704> $30,000 Not Factored    
RSA-768 <#RSA768> $50,000 Not Factored    
RSA-896 <#RSA896> $75,000 Not Factored    
RSA-1024 <#RSA1024> $100,000 Not Factored    
RSA-1536 <#RSA1536> $150,000 Not Factored    
RSA-2048 <#RSA2048> $200,000 Not Factored"


Factorization of RSA-155
http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html

"On August 22, 1999,  a group of researchers completed the
factorization of the 155 digit (512 bit) RSA Challenge Number.  The
work was accomplished with the General Number Field Sieve."


SERACH TERMS

Searched the RSA Web site for "challenge."

http://www.rsasecurity.com

hlabadie-ga

---

Request for Answer Clarification by thegreatjackschitt-ga on 06 Dec 2003 21:08 PST

I was asking more along the line of if I had found a flaw in the algorythm itself.

I would assume factoring is legal. I'm talking about finding a
different way to easily decrypt an RSA encrypted message.

I believe I found something, but I'm not going to post any information
on it until I have a way to permenantly attach my name to it. (Like
Newtonian Physics, or the Doppler Effect).

Once I've attached my name to it, I'll post it here and ask somebody
to prove it wrong.

---

Clarification of Answer by hlabadie-ga on 06 Dec 2003 21:27 PST

The algorithm is not secret, having been disclosed in the original
patent, and is available for inspection and deconstruction. In
addition, the patent has expired, and RSA Laboratories has
relinquished its rights.


RSA Labs' FAQ 4.1
6.3.1 Is RSA patented?
http://www.rsasecurity.com/rsalabs/faq/6-3-1.html

"On September 6, 2000, RSA Security made the RSA algorithm publicly
available and waived its rights to enforce the RSA patent for any
development activities that include the algorithm occurring after
September 6, 2000. From this date forward, companies are able to
develop products that incorporate their own implementation of the RSA
algorithm and sell these products in the U.S."


If you can find a flaw in it, then you can certainly publish it as your own work.

hlabadie-ga

Dear thegreatjackschitt-ga !

I made some research and found that early as 1997 a student managed to
crack the 40bit RSA encryption:
http://www.ecst.csuchico.edu/~atman/Crypto/misc/rsa40-crack.html

"Yesterday (1/28) RSA Data Security Inc. challenged the world to
decipher a message encrypted with its RC5 symmetric stream cipher,
using a 40-bit key, the longest keysize allowed for export. RSA
offered a $1,000 reward, designed to stimulate research and practical
experience with the security of today's codes. "

As the RSA challenged the world by a nice reward , I deduct that the
tries are legal.

I hope that this helps,

Yours

Yoavd-ga

DMCA is only enforceable within the jurisdiction(s) to which it
applies therefore, even it may be illegal in some places, it can't
possibly be illegal everywhere.

DISCLAIMER: I am not a lawyer and who's to say what the men in black suits might do?