RSA-576 Factored

An anonymous reader writes "I thought Slashdot would have picked this up several days ago, but apparently not. Although you still won't see any mention of it on the RSA challenge site, Mathworld is carrying the news that a team at the German Bundesamt fur Sicherheit in der Informationstechnik submitted a factorization of RSA-576 on December 3. RSA-576 is the smallest challenge number that RSA Security offers a cash prize for, to the tune of $10,000"

Mersenne Primes

[penguinoid]

Mersenne primes [wikipedia.org] are a number of the form 2^n - 1, where n is some prime number. Mersenne primes are one of the easiest to find, and there is a quick (relatively) algorithm for checking whether it is prime. Not all Mersenne numbers are prime.

Re:Umm..k?

[TedCheshireAcad]

Not sure if this is a troll, but I may as well offer a simple explanation.

The RSA public-key cryptosystem takes advantage of the theory that factoring composite numbers is a computationally difficult problem. I'm not going to get into specifics, but the depth of the problem is in that the composite number acts more or less as a public key, and encoded within that composite number (as one of the factors) is the private key.

Being able to factor an RSA number is big news because it says that an RSA encoded message with a number of that size (576) can be defeated. Whether or not this is economical to defeat (i.e. time and resources put into the factoring effort) is really the key to this exercise, but one can now assume that a properly funded entity (most likely government) has the ability to defeat RSA-576.

Hope this helps.

Re:Is 576bit big?

[Sage Gaspar]

Well, there is no uncrackable code. The idea is to make it as hard as possible. For each message transmitted using one of those keys, a potential codebreaker would have to dedicate however much time this team of professional scientists on powerful computers would take.

As technology gets better, the level of encryption gets better with it. It's a constant battle. Of course, you're not going to want to make RSA your sole method of encryption and post the key all over the web if you're working on ridiculously top-secret government projects, but then again, you wouldn't want to rely solely on any type of encryption and you wouldn't be transmitting it openly over the Internet.

Re:Is 576bit big?

[damiam]

No. RSA encryption, and public-key encryption in general, uses significantly higher keysizes to attain the same security as private-key cryptosystems at lower keysizes. The difference is that, in a public-key cryptosystem, two parties can talk securely without already both knowing a secret key.

128-bit private-key encryption is virtually impossible to break, because you'd have to test every single 128-bit number. 576-bit public-key encryption is much easier, because you don't have to test every possible key. In this case, RSA uses prime numbers to generate keys. You have to factor the given 576-bit composite into its prime factors, which is much easier than testing every possible 576-bit key (or even every possible 128-bit key).

Re:Is 576bit big?

[Stephan Schulz]

Wow, I havn't really read in to it, but is that very big? I mean, they were talking about not too long ago that 128bit encryption is "almost impossiable" to break. If this is 576bit encryption, and they've broken it, doesn't this mean that 1024bit is looking slightly weak? Whats the 'difficulty' of breaking this key on a relative scale?

There is a different between keys for symmetric encryption algorithms like DES, 3DES, Blowfish, and keys for asymmetric (public key) algorithms like RSA and Diffie-Hellman. Symmetric 128 bit keys are still considered safe. 1024 bit asymetric keys are safe for the moment - I belive for long-term security sensitive applications, 2048 bit keys are recommended nowadays. Here [digitalenterprise.org] is a table comparing the cost of breaking (well, brute-forcing) symmetric and asymmetric cyphers for a given key lenght.

My PGP key is still 1024 bits, and I don't break a sweat.

Re:Is 576bit big?

[Fnkmaster]

128-bit encryption generally refers to key size in symmetric encryption algorithms, like 3DES, IDEA, etc. These encryption methods generally are broken by brute force searching a 128-bit space of keys - that means you have to check on the order of 2^128 different keys until you know if you've found the right one (obviously, this assumes that there are no fundamental cryptographic weaknesses in the algorithm, known-plaintext attacks or other stuff like that).

Assymmetric encryption algorithms, like RSA, rely on a hard problem with two parts needed to reconstruct the solution. In the case of RSA, those two parts are a large composite number with precisely two prime factors, and one of the prime factors (without one of the prime factors, finding out the other prime factor is deucedly difficult). Basically to "crack" RSA you have to factor the large composite number into its two prime factors. With RSA, the keysize refers to the size, in bits, of the composite and prime numbers you're working with. The thing is that you don't have to search an entire 512-bit keyspace to crack a 512-bit RSA key, you just have to try every reasonably possible _prime_ number that might be a factor of that 512-bit composite. And actually, you don't even really have to do that, since there are substantially better techniques for factoring numbers than brute force, requiring less computational effort.

So that, my friend, is why comparing "128-bit" encryption to "512-bit" or "1024-bit" RSA or other assymmetric encryption techniques (which are similar but rely on numerical problems other than factoring large numbers) isn't terribly meaningful.

Notify RSA

[TheRedHorse]

In order to win the prize, you must submit your result to RSA, they don't actively seek out winners. That's why RSA's page hasn't been updated.

They can submit their answer here [rsasecurity.com].

Re:Mersenne Primes

[millette]

and 4 isn't either... so really 2^4-1 is a terrible example.

• 2^5-1 = 31 is prime
• 2^9-1 = 511 isn't prime since 9 isn't
• 2^11-1 = 2047 isn't prime: 23 x 89

Re:Is 576bit big?

[Chmcginn]

except for a correctly used one-time pad.

That depends on the message size - with a sufficiently large message, with any portion of it being known by the interceptor, you can eventually reverse engineer the encryption method used.

Regardless, a "correctly used" one time pad is pretty much useless. You'd need to have an entire library of them in order to have any kind of two-way communication. And that's a big hole in and of itself - if your library is a digital object, anyone who can gain access to it has your 'unbreakable' code. More importantly, you still have to get the one-time pad to your compadre in the first place - and who's to stop someone intercepting it there, unless you hand it to them? (In which case, why aren't you just telling them face to face?)

Symmetric vs. public-key cyphers...

[Goonie]

I'm not an expert, but IIRC you're talking about apples and oranges here.

When 128-bit cyphers are described as "secure", they're almost certainly talking about symmetriccyphers - that is, the key you use to encrypt the message is the same as the key you use to decrypt the message. There are no known ways to break currently acceptable symmetric cyphers (such as 3-DES and AES) faster than brute force - that is, trying each key one at a time. If you have a 128-bit key, this will on average take (2^128 / 2 = 2^127 ~= 10^38) tries before you get the key. This will take billions of years to do, even using a massively parallel computer.

The other sort of encryption, the sort we are talking about here, is public-key encryption, where you use two different keys to scramable and descramble the message. The advantage of this method is you can create a key pair, and give one key to everyone who wants to send you a message (the public key), and while they can send you message securely, it is very difficult for them to figure out your private key (and thhus read messages other people have sent you).

The bad news with public-key encryption is that the algorithms are considerably weaker than with secret-key cyphers. You can mount considerably quicker attacks than just brute-forcing the keyspace. Therefore, you need longer keys for equivalent levels of security. With RSA, the most common method, figuring out your private key from your public key is done by trying to figure out the factor of a very, very large number that is the product of two very large prime numbers. This is still very difficult to do, but it is a simpler problem than brute-forcing an entire keyspace. These Germans have just demonstrated the ability to factor a larger such number than anyone else has done before.

Whilst this is interesting, from what (little) I understand of cryptography it's still a very long way from here to cracking 1024 bit RSA keys. In any case, as the hardware makes it easier for the attackers, it makes it practical to go with longer encryption keys, so faster hardware is neither a help nor hindrance to attackers. The one proviso is, of course, the security of data encrypted by older cyphers.

Re:Is 576bit big?

[tang]

"with a sufficiently large message,.... you can eventually reverse engineer the encryption method used."

Nope! If your one pad key is the same size as the message you are sending, it is unbreakable. Knowing any portion of the message would not help you one bit. Except of course, that you know the part of the message that you know...but you already knew that, so it doesn't help with what you don't know...nevermind:)

Re:I think my form of encryption is better

[hank]

They also set the bar at your "reasonable standard" - the factorization of a 2048-bit number brings in $200,000 USD.

http://www.rsasecurity.com/rsalabs/challenges/fa ct oring/numbers.html

Re:Mine is 1024 too...

[Stephan Schulz]

Is the ElGamal algorithm inherently more or less secure than RSA?

RSA is based on the factorization of large numbers. El Gamal is based on the discrete log problem in a cyclic group. We don't know polynomial solutions for either problem, but we also do not have a strong lower bound for the complexity of either problem. I think currently El Gamal is regarded as slightly more secure, if only because more progress has been made with factorization (probably because its better known and easier accessible/explainable). In practice, it should not matter until some real mathematical breakthrough.

Re:Mine is 1024 too...

[macmouse]

Yes!
Especially, if you are using gnupg.

There has been an big compromise found using elgamel keys and GnuPG!

http://www.auscert.org.au/render.html?it=3648&ci d= 1

Re:Is 576bit big?

[dirtydamo]

It should go up exponentially, so that 1024 is much more than twice as hard. However, with Beowulf clusters and the new primability test, this is being offset quickly.


For the n-th time...

The new primality test has little practical value, because the previous testing algorithms, although probabilistic, are vastly faster in practice.

Primality testing also has little to do with factorization algorithms.

Re:Is 576bit big?

[Kwil]

A correctly used one-time pad can not be reverse engineered, because, if used correctly, it's creation is done in a completely true random format. Since true randomness by definition cannot be engineered, only found, then it is impossible to reverse engineer it.

Now, to do two way communication, you'd need only two pads of sufficient size, one for encoding on each end. You would of course need a duplicate of each side's pad on the other side for decoding and passing these pads is indeed the main weakness.

However, you can, as you say, hand it to them. The reason you might not be telling them the information to be encoded face to face is because you don't have that information yet. The beauty of one-time pads is that they never expire. Someone might find some way to factor primes instantly via quantum computing, and your one-time pad would not be affected.

I suppose if an interceptor somehow found the source of randomness that you used, and somehow managed to find records as to what time-period/portion of it you used, they could then use that information to crack your one-time pad, essentially by recreating it.

But in essence, a correctly created/used one time pad can be very useful, especially with high-density storage media like DVDs where you could store gigabytes of numbers for your OTP creation.

Re:Is 576bit big?

[mage_naes]

This represents a significant improvement on the previous factorization record. I show the following as the current top 10 hardest factorizations:

RSA-576 2003 1881 C174=P87*P87 GNFS Bahr/Franke/Kleinjung/Montgomery/te Riele/Leclair/Leyland/Wackerworth
RSA-160 2003 2152 C160=P80*P80 GNFS Bahr/Franke/Kleinjung/Lochter/Bohm
2^953+1 2002 3950 C158=P73*P86 GNFS Bahr/Franke/Kleinjung
RSA-155 1999 1094 C155=P78*P78 GNFS te Riele/CWI et al.
Code Book 2000 1074 C155=P78*P78 GNFS Almgren/Andersson/Granlund/Ivansson/Ulfberg
HP49( 95) 2003 2651 C153=P68*P85 GNFS Kruppa/Leyland
HP49(97) 2003 1268 C151=P55*P96 GNFS Kruppa/Leyland
2^1064+1 2002 5473 C143=P70*P73 GNFS Franke/Kleinjung
92!+1 2001 1243 C143=P60*P83 GNFS Franke/Kleinjung
2^779-1 2001 7468 C142=P57*P86 GNFS Dodson/CWI/Lenstra/Edick/Leyland

Please note that in most cases it is a cofactor of the indicated number which
was factored; that is, smaller factors may have been extracted using trial
division, the elliptic curve method, etc. The third column gives the first
four digits of the composite number.

Re:RC5-76, not 576!

[Bombcar]

Not So! Read [rsasecurity.com] the site! A 76 bit number is not 174 decimal digits!

RSA-576

Prize: $10,000

Status: Not Factored

Decimal Digits: 174

188198812920607963838697239461650439807163563379 41
738270076335642298885971523466548531906060650474 30
453173880113033967161996923212057340318795506569 96
221305168759307650257059

Digit Sum: 785

Re:I think my form of encryption is better

[Zork the Almighty]

A one-time-pad ciphertext of length n decodes to all 2^n possible messages with equal probability. This situation can not occur if the message being encrypted is larger than the key being used.

Re:I think my form of encryption is better

[LnxAddct]

No because if you take a xor b where b is your message and a is the key then if all the person had was c (the output) then inorder to find b, they would have to xor it with every possible value of a. This would result in every possible combination of bits(do it on paper and you'll see). So the cracker would be left with a list of every possible way of representing a 2048(just an example) bit number essentially going from 0 to 2^2048. Convert this to ascii and you've got every possible combination of characters that can fit in 2048 bits. That means that any sentence that can be written in 2048 bits would appear in the cracker's lsit and therefore there would be too many logical outcomes and noway too tell which is right.i.e. you could have "The ships will attack on the east coast", "The ships will attack on the west coast", "The plane will attack on the west coast", "We made coffee for the Germans." ... or literally every posible combination.

Re:I think my form of encryption is better

[AnotherBlackHat]

Sort by extension;
ls -l | rev | sort | rev

Sort by domain;
rev address_list | sort | rev

Re:Easily Multiplied Numbers !!??

[buford_tannen]

Try GNU bc:

39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * 47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527

188198812 92060796383869723946165043980716356337941738270076 33564229888597152346654853190606065047430453173880 11303396716199692321205734031879550656996221305168 759307650257059

See? That was easy enough. And it would have been even easier if i hadn't had to remove all those spaces you put in there! :)

Re:I think my form of encryption is better

[HuguesT]

OTP can't be cracked even with brute force, because there is no pattern in the encrypted result and each letter is coded independently of all the others.

To give you an example, think of a one-word message:

'GO' (= 0x47 Ox4F)

Here is a two-byte one-time pad:

Ox5E9C

Here is the result of the encryption:

0x474f xor 0x5E9H = 0x19d3

Now the OTP gives you back the unencrypted text if you have it:

0x19d3 xor 0x5E9C = 0x474f = 'GO'

Now, if you don't know the OTP and all you have is the encrypted text, then your only recourse is to try all the possibles OTPs with brute force. The problem is that amongst all the results, you will indeed have 'GO', but also 'NO', 'IT', '42', etc. All the possible two-letter words will be there, and there will be no way to find out which is the correct one.

This result trivially extends to messages of any length. Using brute force with OTPs only generates all the possible messages of a given lengths, giving no clue as to which is the correct one.

Re:Is it me, or is this story...

[plcurechax]

attracting only comments from old troll accounts?

No one knows anything about how you go about factoring huge composite numbers...

Mathematics has the problem that the general population has listened to claims that "math is hard" and has learnt to ignore any attempt at understanding mathematics beyond useless trivia and professional sports statistics.

To help make some sense of what they are discussing:

Some factoring theory [frenchfries.net] and source code [frenchfries.net] by Paul Herman and Ami Fischman.

From RSA Labs' FAQ - What are the best factoring methods in use today? [rsasecurity.com] a fairly technical but readable description of advanced factoring algorithms, and What improvements are likely in factoring capability? [rsasecurity.com]

Worried about your keys?

[Anonymous Coward]

not being the math wiz that most /.ers are I was wondering what this meant for me...I found the below statement on RSA's FAQs and it answered my question that I'm sure many here like me have..
***************
What does it mean when a Challenge Number is factored?

Users of the RSA public-key cryptosystem may wonder what the factoring of a challenge number implies about the security of their keys. Should they immediately replace their keys with larger ones? Should they stop using RSA altogether?

Clearly, the factoring of a challenge-number of specific length does not mean that the RSA cryptosystem is "broken." It does not even mean, necessarily, that keys of the same length as the factored challenge number must be discarded. It simply gives us an idea of the amount of work required to factor a modulus of a given size. This can be translated into an estimate of the cost of breaking a particular RSA key pair.

Suppose, for example, that in the year 2010 a factorization of RSA-768 is announced that requires 6 months of effort on 100,000 workstations. In this hypothetical situation, would all 768-bit RSA keys need to be replaced? The answer is no. If the data being protected needs security for significantly less than six months, and its value is considerably less than the cost of running 100,000 workstations for that period, then 768-bit keys may continue to be used.

Applications that require longer-term security or have data with a high financial value should migrate to longer keys before the factoring of the corresponding challenge number is announced. In either case, the results of the Factoring Challenge provide real data to help the cryptosystem user choose the appropriate key size.

RSA Laboratories' Frequently Asked Questions About Today's Cryptography provides more information on choosing RSA key lengths for various applications. RSA Laboratories Bulletin #13 discusses key length requirements for various cryptosystems.
***********************
And honsetly I think for most people the idea of someone devoting a cluster of computers just so they can read some documents you may have on your hard drive kindof egotistical for the end user...but hey we all know that the NSA breaks every key they can right?...even ones from people just trying to protect their data from average joe hackers...

dnetc as trojan

[rwade]

Norton AV's flagging of dnetc is fully in error. The distributed.net staff is aware of the situation [distributed.net] and is working with Norton to resove the issue.

Re:Post Quantum Crypto

[freuddot]

> but what happens when the quantum computers
> make breaking these things easy?

People start using quantum cryptography. There already are commercial products offering you unconditial security, based on quantum computing, whereas the quantum computer is not ready to factor anything larger than 21...

J.

Linkage

[Nasarius]

Dunno if this is authorized, but: Appropriate Link [friedo.szm.sk]

Re:Hmmm. Complexity vs. Cash

[swillden]

I don't know the complexity of RC5, but I can imagine it's not exponential like the NFS.

The complexity of RC5 is O(n). Encryption time is constant but key setup time is linear, so the whole process is linear.

However, that's not relevant. What you need to compare is the complexity of a brute-force search of an n-bit keyspace, which is O(2^n). Definitely exponential.

Re:I think my form of encryption is better

[spectral]

that'd certainly group by extension/domain, but not sort (At least, not the way people usually want things sorted)

address_list:
microsoft.com
slashdot.org
bing hamton.edu
somethingpositive.net

reverse:
moc.tfosorcim
gro.todhsals
ude.notma hgnib
ten.evitisopgnihtemos

sort:
gro.todhsals
moc.tfosorcim
ten.evitisop gnihtemos
ude.notmahgnib

reverse:
slashdot.org
microsoft.com
something positive.net
binghamton.edu

a proper sort (not group) by domain/extension would be (ascending):
microsoft.com
binghamton.edu
somet hingpositive.net
slashdot.org

it's useful, but your examples need work.

Re:I think my form of encryption is better

[mystran]

For people that think they are now going to generalize this into some kind of general purpose encryption scheme, I'd like to add that OTP works ONLY when it's "one time" pad. That is, once you try to reuse any or all of the pad in any way, you lose the property of uncrackability and it becomes a statistical problem to solve the message.

In plain english, this means that OTP must be unique and truly random and have the same length as the message. While the encryption is uncrackable, the problem of transmitting proper OTPs remains.

Not to say that it couldn't be useful for some special cases, but for general purpose encryption, no.

Re:Post Quantum Crypto

[billstewart]

Quantum computers are too speculative at the moment, but they're the main new threat to near-exponentially-strong crypto algorithms. (Moore's law is theoretically a problem, but it can only continue for so long, and theoretical breakthroughs in the mathematics of factoring or a constructive proof of P=NP don't sound likely but could happen.) But they need to have a really high resolution to be any real threat at all - the Heisenberg limit of ~10**-47 only gets you ~150 bits, so you need to have large numbers of separate qubits coupled together to a be useful, rather than one highly-precise device.

For symmetric algorithms, like the DES family, at most they're expected to cut the number of bits of algorithm strength in half, so instead of 3-DES you might need to use 5-DES or 7-DES, which is only a minor annoyance. For key distribution, it does mean returning to systems based on key distribution centers, like Kerberos. That's a big loss of functionality, unless we find asymmetric algorithms that quantum computing can't break. I'm not aware of any results on whether elliptic curve algorithms are susceptible to Quantum Computers, though it's possible that that could also happen.

Re:I think my form of encryption is better

[NonSequor]

The problem of course is that you can't reuse one-time pads (thus the name) otherwise they are subject to certain attacks. So basically, if you deliver a one-time pad to someone, you are using some sort of secure delivery at one point in time to guarantee the ability to send a secure message at some time in the future.

However, quantum cryptography may be able to render the problems of delivering one-time pads obsolete (well, at least for applications where you can get a fiber link between two points or where you have a line-of-sight with the other party). Quantum cryptography is really just a means of giving Alice and Bob the same random string along with a method of detecting eavesdropping (basically, it won't work if someone eavesdrops).

But I don't believe in any of this quantum voodoo. I'm working on the ultimate in security. Curses. Just put a curse on your message so that it kills anyone other than its intended recipient and you can be as insecure in the transmission as you like. Remember, dead men tell no tales.

Man, have I really been rambling on for this long? Sorry, I've been drinking a bit.

Re:Post Quantum Crypto

[Ibag]

Actually, if you assume that quantum computing becomes main stream and people have enough qbits to factor large numbers (It was only like a year ago that IBM built a 7 qbit computer and implemented Shor's algorithm to factor 15), then you have one time pads being very possible.

One of the nice things about quantum computing is that you can send a message to someone and tell if anybody intercepted it. Therefore, you can send one time pads until one gets through without being viewed. Once you have a one time pad, you can encrypt your message and send it fairly easaily using conventional means.

Of course, I don't know what will happen with things like authentication which rely on public key schemes. I don't believe that eliptic curve encryption methods have an easy attack from quantum computing, but I don't know enough to say that they can be used for anything but encryption.

Re:I think my form of encryption is better

[putaro]

Congratulations - you've invented symmetric key cryptography! Looked at from a far enough distance, any symmetric key crypto algorithm is basically a pseudo-random number generator that combines the pseudo-random number stream with the plaintext and the key is the seed to the random number generator.

Re:Linkage

[rimmon]

http://www.cacr.math.uwaterloo.ca/hac/ It's legal :-)

Re:Easily Multiplied Numbers !!??

[JohnPM]

In python:

print 39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * \
47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527

Re:Mine is 1024 too...

[joeblarnystone]

There is an Index Calculus Algorithm for computing Discrete Logarithms that is analogous to the Quadratic Sieve method for factoring integers. Similarly there are variants that will solve the discrete logarithm problem over the integers modulo n in time comparable to the Number Field Sieve, which is what was used to factor this particular number from RSA. The only reason we don't hear about ElGamal Keys being broken is that there aren't big rewards for such an accomplishment, and because ElGamal another other Discrete Log based systems are not as widely used in practice. Certicom does have a contest to compute discrete logarithms over the group found by taking points on an elliptical curve. These problems aren't as popular to solve it seems, in part I imagine because there is no good way to solve the problem when your group is the points on an elliptical curve. (So an interesting result of this is that the keys for discrete log systems over elliptical curves are MUCH smaller,)