RSA-576 Factored 321
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"
I think my form of encryption is better (Score:3, Funny)
Re:I think my form of encryption is better (Score:5, Insightful)
I don't know... maybe...
u sib;r jbiq (shifted all the keys to the left.)
Seriously, though, all of these ciphers can be broken. It's just a task of minimizing the value to the cracker by making it take as long as possible to get the data, under the thought that it just won't be worth the time.
Re:I think my form of encryption is better (Score:5, Insightful)
I don't know how you feel about it, but quantitative differences on those scales qualify as qualitative differences to me. Your 2048 bit PGP key simply isn't crackable by any reasonable standard. The reason people succeed at these challenges is because the bar has been set intentionally low.
Re:I think my form of encryption is better (Score:5, Informative)
http://www.rsasecurity.com/rsalabs/challenges/f
Re:I think my form of encryption is better (Score:3, Informative)
Re:I think my form of encryption is better (Score:5, Informative)
Re:I think my form of encryption is better (Score:5, Informative)
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:I think my form of encryption is better (Score:5, Informative)
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:I think my form of encryption is better (Score:5, Informative)
Re:I think my form of encryption is better (Score:5, Informative)
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:I think my form of encryption is better (Score:3, Insightful)
Why do people always assume that code-breakers will be White Guys?
Re:I think my form of encryption is better (Score:2)
otgay otay dmitaay tiay siay rettypay oodgay.
Re:I think my form of encryption is better (Score:2)
Guvf fvgr qbrfa'g yrg zr jnfgr rabhtu gvzr nf vg vf!
And while we're on this kind of thing, does anyone know what the point of the UNIX command "rev" is? (as in "$ echo This is pointless | rev" -> sseltniop si sihT)? Why on earth does that come installed on Debian, and does every distro and UNIX variant use it?
Re:I think my form of encryption is better (Score:5, Funny)
Re:I think my form of encryption is better (Score:3, Informative)
ls -l | rev | sort | rev
Sort by domain;
rev address_list | sort | rev
Re:I think my form of encryption is better (Score:3, Informative)
address_list:
microsoft.com
slashdot.org
bin g 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.ne
Re:I think my form of encryption is better (Score:5, Funny)
Double ROT13.
Which incidently, is hereby covered under the DMCA, if you manage to decipher it will be fully procecutable under the fullest extent of the law.
Re:I think my form of encryption is better (Score:3, Funny)
As a really amusing side note, BBEdit, by Bare Bones Software [barebones.com], a really great programmer's tool for the Mac, has a ROT13 tool...
When you select text and use the tool, a warning pops up on the screen:
"Warning: This operation is not undoable."
-T
Well, that's just fantastic, isn't it (Score:5, Funny)
Yup.
Is 576bit big? (Score:3, Interesting)
Chris
Re:Is 576bit big? (Score:5, Interesting)
Re:Is 576bit big? (Score:5, Funny)
Woop! Woop! Woop! Bush-ism alert! Bush-ism alert!
Perhaps you meant primality?
Re:Is 576bit big? (Score:2)
Re:Is 576bit big? (Score:5, Informative)
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.
Shamir's TWINKLE and TWIRL machines (Score:3, Interesting)
The real threat is Shamir's TWIRL and TWINKLE optical factorization-assistance gadgets. They aren't necessarily a threat to 1024-bit keys, but they're a definite threat to 768-bit keys, and
Re:Is 576bit big? (Score:3, Interesting)
No, the biggest Beowulf won't put a dent in the bit length. Consider a 1024-bit prime being tested by a gigantic 65536- (2^16) node cluster. You've now reduced the problem so that each machine has a mere 1008-bit (1024-16) search space. Put another way, parallelization is relatively useless against exponential algorithms.
Re:Is 576bit big? (Score:4, Informative)
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? (Score:3, Insightful)
except for a correctly used one-time pad.
Re:Is 576bit big? (Score:3, Informative)
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:Is 576bit big? (Score:2)
There are many situations in which you know that you will in the future need to send secure messages to someone you are meeting with now (diplomats, for example, or military units). One time pads are quite useful for this (and are in fact widely used).
Re:Is 576bit big? (Score:3, Informative)
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.
H
Re:Is 576bit big? (Score:4, Funny)
Someone might find some way to factor primes instantly via quantum computing, and your one-time pad would not be affected.
That's definitely a good thing, because that instant prime-factorization algorithm has been around for centuries! Given a prime p, its factors are 1 and p.
Still, for some reason, it seems like there's a Microsoft conspiracy to keep this knowledge from reaching the masses. What do they have to hide?
"The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers." Bill Gates, The Road Ahead, Viking Penguin (1995)
Re:Is 576bit big? (Score:2)
Re:Is 576bit big? (Score:5, Interesting)
This particular challenge is for the RSA algorithm which is an asymmetric algorithm. They require much longer keys to be secure. Right now most people recommend at least a 2048 bit key for RSA and plenty of people are using 4096 bit keys.
Comparativly, it should be a long, long time before anyone is worried about their current keys. Back in the day when PGP came out, it was fairly common for people to use a 512 bit key with RSA, but most used 1024. Those people could be concerned at this point that their old messages could be cracked.
Re:Is 576bit big? (Score:2, Insightful)
Cracking old messages? Come on... (Score:3, Funny)
> their old messages could be cracked.
Who would want to spend zillions of hours of computer time to read some geek's old messages?
"Great news, today I have finally managed to install the latest 0.99.1 kernel and boy is it great! I'm so glad I picked SLS instead of slackware, whose installer sucks big time. With my beloved SLS all I had to do was swap four floppies in and out and everything works beautifully! No crashes yet. I never realized how muc
Re:Is 576bit big? (Score:5, Interesting)
Re:Is 576bit big? (Score:3, Informative)
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
Re:Is 576bit big? (Score:5, Informative)
My PGP key is still 1024 bits, and I don't break a sweat.
Re:Is 576bit big? (Score:2)
Re:Mine is 1024 too... (Score:5, Informative)
Re:Mine is 1024 too... (Score:2, Informative)
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&c
Re:Is 576bit big? (Score:5, Informative)
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.
Re:Is 576bit big? (Score:2, Interesting)
Symmetric vs. public-key cyphers... (Score:5, Informative)
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:Symmetric vs. public-key cyphers... (Score:4, Interesting)
Just a quibble: you can actually break both 3DES and AES faster than brute force. In the cast of 3DES, there is a time/memory tradeoff, and AES has some key schedule weaknesses (though in the case of AES, you need to collect nearly the entire codebook before you can proceed with the attack (at least the one I'm thinking of)). Basically, you're right in practice, just not in theory; none of the (publicly known) attacks on 3DES or AES are remotely close to being practical in any sense of the word.
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.
Actually, the win is probably for the defenders. Double the length of an RSA key, the encryptor has to do 3-4 times as much work, but the person trying to factor it faces an increase that is much, much larger.
Re:Is 576bit big? (Score:3, Informative)
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 Almgre
Re:RC5-76, not 576! (Score:4, Informative)
That's Easy (Score:4, Funny)
1 2 3 4 6 8 9 12 16 18 24 32 36 48 64 72 96 144 192 288 576
Hmmm. Complexity vs. Cash (Score:5, Interesting)
Re:Hmmm. Complexity vs. Cash (Score:5, Insightful)
O(exp(c*log(n)^(1/3)*log(log(n))^(2/3)))
where the value of c is reflected by the specific flavor of the NFS you're using, but in each case c>1
I don't know the complexity of RC5, but I can imagine it's not exponential like the NFS.
Re:Hmmm. Complexity vs. Cash (Score:2, Funny)
Re:Hmmm. Complexity vs. Cash (Score:5, Informative)
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:Hmmm. Complexity vs. Cash (Score:3, Interesting)
In other words, factoring RC5-72 requires Moore's law, plus a massively growing audience of people willing to participate. But even with the most optimistic pr
dnetc as trojan (Score:2, Informative)
Mersenne Primes (Score:2, Informative)
Re:Mersenne Primes (Score:5, Interesting)
Re:Mersenne Primes (Score:2)
Re:Mersenne Primes (Score:5, Insightful)
1. Read first paragraph of article.
2. Find first occurence of technical term.
3. Look up definition of said technical term on google.
4. Cut and paste definition then post on relevent slashdot forum.
The best part is, you can do all this without actually knowing anything about the topic!
Re:Mersenne Primes (Score:5, Funny)
a precise rule (or set of rules) specifying how to solve some problem [onelook.com]
-
Re:Mersenne Primes (Score:5, Informative)
Reaction (Score:5, Funny)
"Oh."
The Other One Percent (Score:5, Funny)
I think I speak for the other 1% when I say
"Um."
-kgj
Cheaters! (Score:3, Funny)
Re:Cheaters! (Score:5, Funny)
They probably just looked in the back of the book.
No, that was an even problem. Only odd problems are in the back of the book.
RSA Challenge Challenge (Score:2)
Oh no... (Score:5, Funny)
Notify RSA (Score:5, Informative)
They can submit their answer here [rsasecurity.com].
Re:Notify RSA (Score:2, Funny)
Re:Notify RSA (Score:2)
Re:Notify RSA (Score:2)
Re:Notify RSA (Score:2)
Germany? (Score:5, Interesting)
Re:Germany? (Score:2)
Re:Germany? (Score:3, Interesting)
And Franke has worked with the BSI before, the RSA-160 announcement
4 days and no mention on RSA's website? (Score:5, Funny)
Awww (Score:5, Funny)
Easily Multiplied Numbers !!?? (Score:5, Funny)
3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317
x
4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527
which can easily be multiplied to verify that they do indeed give the original number.
Does anyone have a calculator that can "easily" multiply these two numbers... Holy Cow!
Re:Easily Multiplied Numbers !!?? (Score:2)
Re:Easily Multiplied Numbers !!?? (Score:3, Informative)
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:Easily Multiplied Numbers !!?? (Score:2, Funny)
A pencil and paper seem to do a great job at storing the values for calculation. As for actually carrying out the calculation, that's what your brain cells are for.
They said "easily". They didn't say "quickly".
Re:Easily Multiplied Numbers !!?? (Score:5, Interesting)
import java.math.*;
public class Calculator
{
public static void main(String[] args)
{
BigInteger x = new
BigInteger("39807508642406493739712550055038649
BigInteger y = new
BigInteger("47277214610743530253622307197304822
BigInteger z = x.multiply(y);
System.out.println(z.toString());
}
}
[c:\temp]\j2sdk1.4.2_01\bin\javac Calculator.java
[c:\temp]java Calculator
1881988129206079638386972394616504398
Re:Easily Multiplied Numbers !!?? (Score:3, Informative)
print 3980750864240649373971255005503864911990643623425
4727721461074353025362230719730482246329146953020
How long did it take them? (Score:2)
Worried about your keys? (Score:5, Informative)
***************
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...
Post Quantum Crypto (Score:3, Insightful)
What will be the face of the next from of Crypto? Only one-time pads? That sounds way painful.
-- Multics
Re:Post Quantum Crypto (Score:3, Informative)
> 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.
Re:Post Quantum Crypto (Score:4, Informative)
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:Post Quantum Crypto (Score:5, Informative)
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:Post Quantum Crypto (Score:3, Funny)
No-one is going to wade through 5 pages of a Live Journal blog to find my secrets.
Re:Umm..k? (Score:5, Informative)
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:Umm..k? (Score:5, Funny)
Well i_am_syco, articles are there for reading. They can even increase your knowledge, and one day you may even learn how to spell psycho properly.
Re:Umm..k? (Score:2)
Re:Umm..k? (Score:2)
Re:The factors were (Score:4, Funny)
This is a
Is it me, or is this story... (Score:2, Offtopic)
No one knows anything about how you go about factoring huge composite numbers, or can read German, or even knows the difference between breaking RSA-576 and breaking RC5-72.
So all that's left are people trying to find clever ways of linking to the prime number shitting goatse, and a surprising dearth of posts by abandoned troll accounts.
Care to explain?
Re:Is it me, or is this story... (Score:5, Informative)
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]
I was questioning the low IQ in the discussion... (Score:2)
Re:Distributed Computing (Score:3)
Re:Global Warming (Score:3, Funny)
I hate to be the one to tell you this, but most of your homework problems didn't actually happen in real life. For example, there probably isn't a train leaving san franciso and denver at the same time at different speed