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"

Comments

I think my form of encryption is better

[Wigfield]

Ontday oyay inkthay osay?

Re:I think my form of encryption is better

[cgranade]

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

[Snoopy77]

Ontday oyay inkthay osay?

otgay otay dmitaay tiay siay rettypay oodgay.

Re:I think my form of encryption is better

[Anonymous Coward]

You missed a 'u' in the second word.

Unless, of course, that was meant to happen in an effort to throw off someone trying to crack the cypher. In that case, it's ingenious!!!

It wold be good to se the letter " " no frther.

Re:I think my form of encryption is better

[LeninZhiv]

V guvax gurer fubhyq or n fynfuqbg frpgvba jurer nyy cbfgf unir gb or va EBG13.
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

[Anonymous Coward]

it's so you can read the screen when you look at it over your shoulder with a mirror.

Re:I think my form of encryption is better

[the_argent]

Or my personal favorite....

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

[wurp]

Sure, all codes (except one time pads and equivalents) can be broken. The difference is whether it takes a day to crack the code or it can be proven that it requires either a centuries-sought breakthrough in mathematics or all the computers in the world working for ten thousand years.

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

[Anonymous Coward]

Amnday itway, ywhay oesday onay oneway earnlay otay useway igpay atinlay operlypray?

If the word starts with a vowel sound, you just append way.

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:I think my form of encryption is better

[Anonymous Coward]

Why can't one-time pads be cracked? I think I read somewhere that OTPs are as large as the data being sent with it, but still wouldn't that be crackable given an infinite number of monkeys?

The three of us slashdot regulars who aren't cryptographers are confused by most of this, and the site being slashdotted doesn't help either.

Re:I think my form of encryption is better

[Anonymous Coward]

I like my ROT at 26.

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:I think my form of encryption is better

[SpaceLifeForm]

qbznl fvugnl chnl!!!

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:I think my form of encryption is better

[Anonymous Coward]

ROT 104 baby, it's FOUR times safer than yours....

Re:I think my form of encryption is better

[Anonymous Coward]

Well, that shut me up.

Re:I think my form of encryption is better

[tuxfan]

You may be surprised at how ineffective that first one is:

$ ls -1 | rev | sort | rev
i.mp3
sex.c
a.tiff
girl.jpg
had.pl
never .iso
with.s
have.txt

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

[Anonymous Coward]

Exactly. And ever better:

ls -lX

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: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:I think my form of encryption is better

[Qrlx]

Wouldn't it work pretty well to establish a pre-determined OTP generator? like, the winning lottery numbers last night, the answer to 1 across and 3 down from yesterdays' crossword puzzle, and the third word from each story on the front page. Oh and the cards in East's hands from the bridge game. All information to be obtained from the daily newspaper.

You'd have a new OTP every day, and if your generating algorithm were sufficiently weird it would be essentially unbreakable, would it not? Provided of course that the communicators go to some length to not make it obvious that's why they buy the paper each morning.

Or what about something like SecurID, just use some funky algorigthm to generate new OTPs every sixty seconds. Every once in a while, twiddle the formula.

Re:I think my form of encryption is better

[Goldfinger7400]

Wouldn't it work pretty well to establish a pre-determined OTP generator? like, the winning lottery numbers last night

Yeah, but then the NSA would figure out how to systematically win the lottery every time in an effort to break the one time pad!

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:I think my form of encryption is better

[Fred Ferrigno]

Wouldn't it work pretty well to establish a pre-determined OTP generator? like, the winning lottery numbers last night, the answer to 1 across and 3 down from yesterdays' crossword puzzle, and the third word from each story on the front page. Oh and the cards in East's hands from the bridge game. All information to be obtained from the daily newspaper.

In any of these cases, if a third party discovered your scheme, it's worthless. In general, that's called security by obscurity, merely hoping the other side doesn't figure it out. People can be bribed, patterns can be recognized, and having a OTP that's an English sentence makes cracking your message several dozen orders of magnitude easier.

A OTP has to be completely random. Otherwise it's worthless. The Germans did basically what you propose during WWII, and yeah it did work for a while. But then some really smart people got at it, did the statistical analysis, recognized the patterns and broke it. With today's computers it'd be just that much easier.

That's why encryption schemes like RSA are so useful. It doesn't matter if the other side knows exactly how the encryption works; it doesn't matter if they know everything you know about the message; if they don't have the key, you can mathematically prove that you'll be long dead before they can break it.

Re:I think my form of encryption is better

[Anonymous Coward]

A pre-determined "OTP" generator (unless you're referring to a quantum key distribution system) is effectively equivalent to a stream cipher, which can be brute force cracked (or sometimes worse, if it's algorithmically flawed).

The key size for the cipher is, at most, the size of the internal state.

But note that brute forcing for large enough key sizes is not feasible. Modern block ciphers (which are more commonly used than stream ciphers because an initial-vector + cipher-block-chaining scheme allows some key-reuse, a stream cipher key can only be used as long as the stream can be kept in sync) have 128 or 256 bits keys, which can't be brute-forced using any amount of computing power available in the foreseeable future.

The fear with most symmetric ciphers is that they might have algorithmic flaws that make them susceptible to attacks significantly less expensive than brute force.

Brute force attacks are not a realistic concern for anyone using reasonable key lengths (the 56-bit keys of DES were known to be too short even back when the standard was introduced). If anyone chooses to use real one time pads, despite the extreme inconvenience, that probably means that they don't trust any ciphers algorithmically, not that they fear brute force attacks.

Re:I think my form of encryption is better

[fuck_this_shit]

OTPs can be cracked and have been due to the source of the "random" numbers not being random enough. A truly chaotic source of numbers isn't as easy to come by as it appears to be. Which is why you want to keep messages brief to not give out a pattern when the not-so-randomness strikes again. Yet in general most won't bother with intercepting and trying to decode the message as it's always easier to get a hold of the decoded message instead.

Re:I think my form of encryption is better

[Anonymous Coward]

Sure, all codes (except one time pads and equivalents) can be broken ... Your 2048 bit PGP key simply isn't crackable by any reasonable standard.

And 64K will be enough for anyone, ever. :)

Information that has been protected with the security of a one time pad or a 2048-bit RSA, or heck, even symmetric key, can be revealed, but perhaps not using the methods that you're expecting. Ultimately, information in the hands of humans is inherently insecure.

Consider that your key lengths or whether you used one time pads or not would be quite irrelevant if anyone who knew the information spent two years in isolation and undergoing psychological torture in a chain link box in Guantanamo Bay. Take that basic premise into account during your next information security design, and you may be able to make your data that much safer.

Re:I think my form of encryption is better

[JuggleGeek]

Double ROT13.

That was, quite possibly, the first highly modded "funny" post that I've ever seen on /. which was actually funny, and it's even on-topic! Pbatenghyngvbaf.

Re:I think my form of encryption is better

[Anonymous Coward]

> That's why encryption schemes like RSA are so useful. It doesn't matter if the other side knows
> exactly how the encryption works; it doesn't matter if they know everything you know about the
> message; if they don't have the key, you can mathematically prove that you'll be long dead before
> they can break it.

No, you can't. The complexity of the problem is yet to be proven.

Re:I think my form of encryption is better

[hugesmile]

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.

Why do people always assume that code-breakers will be White Guys?

Re:I think my form of encryption is better

[*weasel]

what you are referring to as quantum cryptography isn't really cryptography, it's a semi-convenient side effect of encoding messages at the quantum level. Physics guarantees that the first reader of such a message necessarily destroys the message. Trick is, you still need decent cryptography behind such a scheme, as it won't much matter to a cracker if you know he's there or not -- he'll still have your sensitive info if you didn't properly encrypt the actual message. in most applications you simply can't stop communicating and still remain relevant just because you know someone is eavesdropping.

convenient because you know for certain if you're being spied on? sure.
secure? hell no.

case in point: the US -knew- the japanese were spying on our wwII transmissions. just as the Japanese -knew- the US was spying. knowing that the enemy is listening didn't alleviate the problem - it still comes down to good crypto. one can't simply stop communicating and wait for the eavesdropper to leave.

truly secure quantum communication:

1. achieve quantum-entanglement of 2 particles
2. build com device to send messages via altering spin of one particle
3. give the second particle to your friend
4. build com device to read messages via observing the spin of the second particle
5. enjoy instant snoop-proof communications ...
6. profit?

(truly secure because there is no traditional transmission. still theoretcial of course ;p -- and it's one-way, you'd need a second pair of entangled particles to transmit back. but that second unit would be trivial if you could actually create the first functional unit.)

Re:I think my form of encryption is better

[WhiteDragon]

I think you're thinking of tac, that reverses it's input by lines instead of a line at a time. Eg.
echo -e hello\\nthere | tac yields:

there
hello

Re:I think my form of encryption is better

[Steve B]

Trick is, you still need decent cryptography behind such a scheme, as it won't much matter to a cracker if you know he's there or not -- he'll still have your sensitive info if you didn't properly encrypt the actual message.

The way around this is to send a one-time pad over the quantum link, and to echo it back. That guarantees that there was no interception in the middle (the only remaining hole to plug is to confirm that an interloper hasn't completely replaced your intended correspondent at the other end of the line).

Re:I think my form of encryption is better

[Lehk228]

if you make the encryption rotate around itself (modulus 27 would be enough to encode letters and spaces) and determine whether to add or subtract each letter based on the starting letter and the previous encoded letter with the arraingement of letters in the encoded file moved using a second pad it would make decrypting it immensly difficult because there would no longer be a means of determining characters by their usage frequency, especially if the message is surrounded/ infiltrated with junk random values that would be impossible for a, algorythm to determine with any better probability than random what a message said, especially if the random junk was written to weight itself towards certain values each message

Re:I think my form of encryption is better

[Theaetetus]

Double ROT13.

As a really amusing side note, BBEdit, by Bare Bones Software, 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

Re:I think my form of encryption is better

[B3ryllium]

I do believe it would be "every possible permutation", not "combination". In a permutation, the order of things is important - this means that there are actually an even larger number of possibilities.

Like, lets say you have five letters, ABCDE. In a combination, the order is irrelevant, and so it doesn't matter how you arrange them.

In a permutation, order is highly important. For five letters, the number of possible permutations is 5! (factorial). This means there are 120 possible ways to arrange those five letters. (Try it: 1x2x3x4x5). Imagine if you have 50 characters? Most calculators refuse to calculate 100Factorial.

(I don't know if I really have a point, except to say that I think you should have used permutation instead of combination, because combination - despite the socially accepted meaning - actually makes it seem less impactful than it should be.)

*Disclaimer: IANAS. (I am not a statistician.)

Re:I think my form of encryption is better

[Anonymous Coward]

Wrong answer there clueless, modern crypto is based on known values to determine crackability. It's almost mathamatically trivial to determine how many possible keys exist, and so therefore how complex the problem is.

Re:I think my form of encryption is better

[Anonymous Coward]

Ug, this one has been around for almost more than a decade already...

Re:I think my form of encryption is better

[Anonymous Coward]

Oh, is that so? Would you care to show me your (or anybodies) proof of the lower bound for the factoring of large numbers (RSA)? (hint: there isn't one). Counting the number of keys means nothing as far as _proofs_ are concerned.

Re:I think my form of encryption is better

[Anonymous Coward]

>Like, lets say you have five letters, ABCDE. In a combination, the order is irrelevant, and so it doesn't matter how you arrange them.

That's not what he's talking about. What he IS saying is that if you xor the unencrypted data with a key of the same or greater length than the data then it's impossible to decrypt the data without the key.

He's NOT saying "how many different ways are there to choose five different letters from the alphabet" or "how many different sequences of letters containing A, B, C, D and E can I make".

I believe what you're saying about the difference between combinations and permutations is true but he was actually talking about combinations (as in "8 on/off switches can be arranged in 256 ways").

*Disclaimer: NAI. (Neither am I.)

Re:I think my form of encryption is better

[*weasel]

exactly, it all comes back to doing proper encryption. 'quantum' cryptography isn't going to change much in the security biz. it's a buzzword now, a far-off technology, and when it hits, it'll just be another flavor of the same game. it doesn't help much, it just has a convenient feature that only confirms the key assumption that all cryptographers start with.(that somebody is listening, but information needs to be exchanged)

you still need solid cryptography, and right now, that seems to be most effectively done through one-time pad and public/private key pairs.

Re:I think my form of encryption is better

[Wavicle]

It is a good thing you were paying some attention in your stats class, but... This problem is not a selection without replacement. This problem is a selection with replacement. Thus A, B, C, D or E can occur in any of the five positions with equal probability. Thus, the proper combinatorics in this case is 5^5, or in the general case b^n. For a 2048 bit message it's 2^2048.

So to get message b from encrypted message c, you must try all possible bit patterns in a. You will get message b out of it, but you'll also get all possible messages of length |b|... One of those patterns probably contains the DeCSS source code and is therefore banned under pain of death or something.

Re:I think my form of encryption is better

[DarthTaco]

It doesn't matter if the other side knows exactly how the encryption works; it doesn't matter if they know everything you know about the message; if they don't have the key, you can mathematically prove that you'll be long dead before they can break it

RSA is not mathematically proven to take a long time to hack in general. The only thing we know about it is right now we don't have a fast way cracking it. There is no proof (mathematical or otherwise) that says we won't discover something tomorrow that renders RSA of any bit length worthless.

Re:I think my form of encryption is better

[bolthole]

you just THINK quantum entanglement is secure. But science doesnt really understand quantum entanglement, so it has no idea whether it is possible to observe methods of communication with it.

Re:I think my form of encryption is better

[EvilSporkMan]

you can mathematically prove that you'll be long dead before they can break it.
Unless "they" get lucky, and THEN what do you do?

Re:I think my form of encryption is better

[Anonymous Coward]

JuggleQueer says something stupid irrelavent and assholic again. This stupidity is best shown in his own posted resume:

This is JuggleGeek's resume. I will rip it to shreds because he is viscous and very much an unskilled arrogant jerk that constantly makes paranoid statements, espouses half truths and makes arrogant comments on Slashdot. JuggleGeek: An NT 4.0 Lover. A bit behind the times, don't you think? His work is so cheap and unprofessional they use Win98. He claims to be a programmer. His "workstation" OS of choice: Win98. Nice.

HAND CODED HTML! WHO WOULD HAVE THUNK IT COULD STILL HAPPEN?
You mean "Thought it would happen," not thunk. Thunking is something a "programmer" should know about. Most people hand core or use code to generate HTML. Big fucking deal

WELL, IT'S MOSTLY HAND CODED. BUT TO BE FAIR, I HAVE USED
HOMESITE 2.5, AND IT IS PRETTY NICE.
So it is not hand coded. Make up your mind. Moron
MOSTLY, I LIKE HAVING A QUICK ONE-KEY METHOD OF SEEING HOW
THE PAGE LOOKS AT ANY GIVEN POINT.
HACKER : STEPHEN WHITIS
You cannot hack HTML. That is an amateurish, juvenile thing to say. You can author HTML, no more. Its as easy as using a typewriter

Stephen "JuggleGeek" Whitis's Resume Page (p1 of 3)
- Moron error. Possessive form of Whitis is Whitis'.

I am currently seeking employment.
Forgone conclusion. That is why resumes are written. Moron.

I am interested in Delphi programming, with an emphasis on internet related applications, user interfaces, and databases. Web design is not a specialty area, but I have basic skills and an interest in developing them further.
Interest in a subject is not a reason to hire you. No one cares what you like. It is about what you can do for other people. Moron. So, you want your next employer to teach you not to suck in web design?

I currently live in Dallas, and have no interest in moving.
I currently have a company "INSERT COMPANY NAME HERE" and have no interest in hiring you.

I am not looking for "traditional" work. Part time work would be considered, as well as telecomuting [SIC] work. The usual 9 to 5 job doesn't interest me, as I have an ongoing project which already takes up a certain amount of my time.
Translation: I'm a loser that cant keep a real job. I don't have the attention span or the responsibility to finish anything. I like to telecommute to further hide my ability to do nothing. I fail to mention the project because its probably killing small animals or fucking sheep.

If you have a project you need done, and the project interests me, I can be hired cheap.

You can be hired cheap because you suck
If you are looking for a full-time, long term, 9-5 kind of guy, then I'm not the one you're looking for. I'm a self taught programmer with 20 years of professional experience. I'm confident that I can be successful with any programming project I take on, but I will only accept offers where the project interests me and the working conditions meet with my non-standard lifestyle.
This isnt a resume. This is a stupid conversation you are having with no one. Self taught means you point out the fact most real programmers will rip you apart. 20 years? Doubtful. Most of your expoerience is more IT than programming. You have never contributed to an opensource project to prove you can submit code, you have no code portfolio. Non-standard lifestyle. FUCK YOU.

I get a lot of emails from headhunters wanting me to consider jobs out of state. I am not leaving Texas. (And I'm very unlikely to leave Dallas.) If your out of state company wants to hire me, then I'll need to telecommute.

Re:I think my form of encryption is better

[jjgm]

You'd have to be pretty far away and have bad eyesight, because that description is wrong. You've described what is called a "stream cipher", that is, an algorithm that uses a PRNG to generate a keystream. The most popular stream cipher is RC4.

Block ciphers do *not* directly combine a random number stream with the plaintext; they encrypt the plaintext with the key via a defined algorithm. Examples of block ciphers are DES and AES.

Now, it's true that the output of a block cipher can be constantly re-encrypted, thus generating a series of pseudo-random numbers suitable for XORing a plaintext stream; however, that's just a fancy PRNG for a stream cipher! You'd be wise not to equate the two.

As ever, Bruce Schneier's Applied Cryptography is the recommended tome to understand the difference in detail, without gloss.

- K

Re:I think my form of encryption is better

[bensagenius]

I for one appreciate the Douglas Adams reference.

Re:I think my form of encryption is better

[putaro]

You're correct, I should have said "many" instead of "any." Though, you could look at a block cipher as being a PRNG with the key + plaintext block as the seed.

Re:I think my form of encryption is better

[ross axe]

Of course, rev can be used for that as well.

Re:I think my form of encryption is better

[-brazil-]

Nope. By craptographic standards there's probably already a known attack that easily breaks such a cipher. If not, a good cryptoanalyst could come up with one in a couple of days.

Re:I think my form of encryption is better

[WhiteDragon]

how? I looked at the man page for rev, and I don't see any such option...

REV(1) BSD General Commands Manual REV(1)

NAME
rev - reverse lines of a file

SYNOPSIS
rev [file]

DESCRIPTION
The rev utility copies the specified files to the standard output,
reversing the order of characters in every line. If no files are speci-
fied, the standard input is read.

BSD March 21, 1992 BSD

Re:I think my form of encryption is better

[ross axe]

echo -e hello\\nworld | `echo cat | rev`
Easy

Re:I think my form of encryption is better

[NonSequor]

Unfortunately it doesn't work that way. It's more like a quantum key exchange and all it does is guarantee that two people have the same random string of bits. You have no control over what that string is. Also, if someone does eavesdrop, you won't have the same string as the person on the other side and so you can't send anything. So basically, a man in the middle attack won't work, but you still won't be able to send anything. You're out of luck until you can send an assassin to inspect the line or something like that.

Re:I think my form of encryption is better

[WhiteDragon]

nice! :-)

Well, that's just fantastic, isn't it

[mcc]

I think that composite numbers everywhere will sleep just a little bit less securely tonight, knowing that the Bundesamt fur Sicherheit in der Informationstechnik is out there, somewhere, waiting for them.

Yup.

Re:Well, that's just fantastic, isn't it

[janbjurstrom]

David Rees, is that you??

(Why aren't you updating GYWO anymore? I miss it man.)

Is 576bit big?

[The Real Chrisjc]

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?

Chris

Re:Is 576bit big?

[cgranade]

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.

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?

[Anonymous Coward]

The 128-bit encryption refers to secret-key encryption. This is very different from factoring a 576-bit number. Factoring corresponds to public-key encryption. Many more bits are required for a secure public-key than for a secure secret-key.

Re:Is 576bit big?

[Ageless]

When people talk about 128 bit encryption being hard to break they are talking about symmetric algorithms such as Blowfish. A 128 bit symmetric algorithm is still very, very tough to crack a key for.

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?

[Anonymous Coward]

When you refer to 128 bit, that gerearlly is symmetric key Encryption (as in session key), and yes its still very hard to break via brute force.

When you refer to 1024 bit, this is generally asymmetric (as in public/privite key)

Two very different scales. I assume the 576bit is also refering to the latter which means the key is about half as long as the current standard.

Note that half the key length does NOT mean half as hard - think binary

sorry for any spelling errors;-)

Re:Is 576bit big?

[mattjb0010]

Well, there is no uncrackable code

except for a correctly used one-time pad.

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?

[Anonymous Coward]

I think you're comparing apples to oranges.

When talking about 40-bit or 128-bit keys, it is usually for symmetric algorithms such as DES, AES... RSA is a public-key system that usually uses larger keys (512, 1024, etc.). The "breakability" of a certain size of keys cannot be compared between such different beasts.

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

Re:Is 576bit big?

[Anonymous Coward]

You can't compare the key sizes of symmetric key algorithms (like DES or AES or Blowfish) with the key sizes of public key algorithms (like RSA or ElGamal). 128 bits for symmetric key algorithms is still practically impossible to break but 128 bits for RSA is now pretty easy to break. The difficulty of breaking these algorithms is thought to be exponential so adding an extra bit doubles the amount of time it takes to break the algorithm -- if this is true, then 1024 bits should still be safe (it will take 2^448 times longer than 576 bits assuming the same hardware and software).

Re:Is 576bit big?

[FU_Fish]

You may be comparing two different types of encryption. For block algorithms such as DES and AES, 128 bit is still fairly reasonable, however not for RSA (and other public key algorithms). Currently, 1024 bit RSA is considered reasonably secure and 576 is, as we can clearly see, quite insecure. I won't go into the details of why different algorithms need such drastically different key sizes here, but if you'd like to know more, the Crypto-FAQ is a good place to start.

Re:Is 576bit big?

[I Be Hatin']

However, with Beowulf clusters and the new primability test, this is being offset

Woop! Woop! Woop! Bush-ism alert! Bush-ism alert!

Perhaps you meant primality?

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?)

Re:Is 576bit big?

[Anonymous Coward]

Did people use RSA for PGP encryption in those days? That does sound dodgy.

I knew there had to be a reason ElGamal is currently the default for encryption...

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:Is 576bit big?

[mattjb0010]

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.

Well even if they have part of the message, they still won't be able to decipher the rest of it with a one-time pad. You mention the limitations, but there are situations where those aren't problems, eg you give the other party the one-time pad in person, then communicate only a few messages at some distance.

Re:Is 576bit big?

[Anonymous Coward]

Absolutively not. I know exacterifically what I'm talkepating about.

Re:Is 576bit big?

[harlows_monkeys]

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?)

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?

[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?

[Anonymous Coward]

128-bit private-key encryption is virtually impossible to break, because you'd have to test every single 128-bit number.

Well, technically you'd only have to test numbers until you found the key...

It's not like you go and look under the couch once you've found your car keys, right? :P

Re:Is 576bit big?

[Bombcar]

The way a one time pad works means that if used correctly it is just as likely that a five meg message is the complete works of Shakespear as it is to be missle plans. Basically, it is like a furnace: you can hear whatever you want to hear because every sound is there.

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:Is 576bit big?

[NonSequor]

You can get away with much shorter key sizes using elliptic curve methods. Currently reccomended sizes are at least 80 bits for a symmetric key and 160 bits for an asymmetric key.

Re:Is 576bit big?

[Anonymous Coward]

Thank you. I'm tired, I guess. That was fucking stupid of me, huh?

Re:Is 576bit big?

[Ageless]

RSA has been the defacto standard for public key exchange since it came around. PGP was based on it, and if I remember correctly that's all it supported for a long time. RSA is still a very strong algorithm and has a few benefits over ElGamal. The main reason that people wanted to switch from RSA to something else was that until September of 2000 RSA was covered under a patent and required royalties to use.

Re:Is 576bit big?

[LnxAddct]

not too mention that currently factoring a 512 bit key will still take months, if not years. If someone is willing to put all that money and effort into cracking your key then you've got worse problems on your hands, I'd recommend buying a gun. My point is that just because one key was factored of that length, doesn't mean it is all the sudden faster or easier, it just means that a group of people put alot of effort, money, and thinking into one number and were able to factor that one number. They can't go around factoring 512 bit numbers at their whim now, these things still take time, and alot of it.

Re:Is 576bit big?

[Anonymous Coward]

RSA is an asymmetric algorithm. Those 128-bit keys are for symmetric algorithms like Rijndael or Twofish. You can't generally compare asymmetric key lengths to symmetric key lengths. You can't even compare asymmetric algorithm key lengths together, because they're based on different problems.

In short, AES-128 will still protect your data. This contest was just a measure of how long it'll take to break an RSA-576 key. It gauges the current state of hardware and factoring algorithms. You should've already stopped using RSA-576 a while ago, anyway, unless you're working on a very small platform where you don't have the computation for more.

Re:Is 576bit big?

[Anonymous Coward]

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?

[Dwonis]

primability test, eh? Is that like a probabilistic algorithm for testing primaility?

Re:Is 576bit big?

[ifwm]

Um, no. Every problem you discuss that has to do with the reliability of one time pads is actaully a problem UNRELATED to one time pads.

Re:Is 576bit big?

[Anonymous Coward]

anyone who can gain access to it has your 'unbreakable' code
of course, but isnt that with _any_ encryption? if you have access the teh decryption tools, of course you can decrypt it.

Re:Is 576bit big?

[Sage Gaspar]

Well, there's also the question of how easy to relate and keep hidden the decryption tool is.

For something like RSA encryption, the decryption tool (or rather, the piece of information necessary to enable the decryption tool) is small enough to be scratched out quickly on a piece of paper, passed on verbally or (albeit a bit harder) committed to memory, if necessary.

For one-times, the decryption tool in question is as large as the message itself. That means that the tool must be itself stored somewhere semi-permanent, which means that it's more susceptible to theft.

Re:Is 576bit big?

[akruppa]

RSA-576 2003 1881 C174=P87*P87 GNFS Bahr/Franke/Kleinjung/Montgomery/te Riele/Leclair/Leyland/Wackerworth

The last name should be Richard Wackerbarth I think, not Wackerworth.

Alex

Re:Is 576bit big?

[JuggleGeek]

Well, there is no uncrackable code.

No? Tell me what this means...

duiedl2aiaisadiieakeiawieaupqa

Re:Is 576bit big?

[N Monkey]

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?

You're confusing symetric key ciphers (eg AES (Rijndael), DES, Blowfish etc) with the public/private key ciphers (RSA, Diffie-Hellman). The former can use any "random" pattern of bits as the key, whereas the latter need a much larger key size because they rely on certain numeric properties of the key or algorithm.

Re:Is 576bit big?

[JamesP]

You can bet they spent the last couple of years (at least) to break it...

Re:Is 576bit big?

[Anonymous Coward]

1024 bit is "much more than twice as hard" than 576 bit? That's a bit of an understatement.

Re:Is 576bit big?

[mrtroy]

If you are worried about the security of your data, just pump up the bits of the RSA key, and it will exponentially increase the time it would take to crack it basically.

RSA is a nice little scheme, where you have a public key so that anyone can encrypt data for you, but you are the keeper of the private key. In Algebra, we learned how to actually encrypt and decrypt RSA with just a pencil and paper, and we quickly learned that computers are much quicker :P (i couldnt imagine doing a 128bit encryption using a pencil)

The tough part for breaking an RSA scheme is basically related to factoring theory. I imagine these programs are very efficient and well designed, but still there are soooooo many possible values that nobody could crack your data in a reasonable amount of time.

Re:Is 576bit big?

[Just Some Guy]

However, with Beowulf clusters and the new primability test, this is being offset quickly.

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?

[tx_mgm]

Well, there is no uncrackable code.
No? Tell me what this means...

duiedl2aiaisadiieakeiawieaupqa

I can do that. No complex mathematical algorithms needed, either!
I'll just need your home address and photos of any immediate family members....

joke. laugh.

Seriously, though, I think Mitnik (sp?) would have something to say about security vulnerabilities and human weakness. Which is why keys generated and used by computers (and usually unknown to the human using them) will ALWAYS be more secure than even the most obscure, cracked-out codes people can think of in their own heads.

Re:Is 576bit big?

[chochos]

when you hear about 128-bit encryption that is "almost impossible to break", they're talking about symmetric encryption keys.

the article talks about a 576-bit RSA key. RSA is an asymmetric algorithm, it needs much bigger keys to make it hard to crack. a 128-bit RSA key can be cracked a lot easier than a 128-bit AES key (AES is a symmetric algorithm).

Re:Is 576bit big?

[Anonymous Coward]

The difference is that the 128 bit key uses symmetric private key encryption, and the 1024 bit encryption uses asymmetric public key encryption.

The private key is unknown, the public key is a hard math problem with some known components.

Also, the originally difficulty was stating that 1025 bit keys were twice as hard to break as 1024 bit keys. This isn't the case because factoring numbers with new techniques is done with logarithmic increasing difficulty.

576 isn't 'big' because currently the minimum size public key is 768 bits, and average key sizes are 2048 bits.

It is theoretically possible for a well funded attacker to break 1150 bit keys in several months. Well funded = government or IBM for example.

Another thing to consider is that all public key encryption methods are not the same. RSA can be cracked with a discrete log or with factoring the composite number. You could also just guess the private part of the public key. Diffie Hellman is only possible to crack by knowing the discrete log - because that is the private key. El Gamal... well the list goes on and each method has its own shortcuts to attacking it.

RSA is susceptible to factoring primes, and advances in this field have consistently occurred. Other 'hard problems' have not easily attacked. The easiest to factor is based on a composite of the form a*b where a and b are primes of the form 2^number-1.

The attacks are the Number Field Sieve and the Quadratic Sieve.

That's Easy

[paul248]

Look! I did it too!

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

[silentbozo]

Does anyone know the relative computational difficulty of cracking RC5-72 vs. trying to factor one of the RSA numbers? Given the higher monetary payoff, I'm wondering if I wouldn't be better off implementing and running a prime factor sieve, rather than running the RC5 client (which only runs on my W2k workstation, because the distributed folks never rewrote the older cores that run on my pre-OSX Macs.)

Mersenne Primes

[penguinoid]

Mersenne primes 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:Mersenne Primes

[millette]

the 40th Mersenne prime has been discovered 2-3 weeks ago and just proven to be correct. See http://www.mersenne.org/history.htm for more info.

Re:Mersenne Primes

[jrockway]

2^4-1 = 15, for instance

Re:Mersenne Primes

[Anonymous Coward]

15 is not a prime

Re:Mersenne Primes

[penguinoid]

The exponent must be a prime as well, but it still won't guarantee you get another prime.

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:Mersenne Primes

[Anonymous Coward]

WTF? you off-topic non-sequiter spouting shit. someone mod parent properly... puleeez.

Re:Mersenne Primes

[Zork the Almighty]

You'd also NEVER want to use a Mersenne prime in RSA, which about the only way to bring this back on topic.

Re:Mersenne Primes

[nihilogos]

Algorithm for increasing karma:

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

[HappyFunnyFoo]

That's incorrect. The logic is as follows: 1. IF 2^P - 1 is prime, THEN 2. P is prime. Since 2^4 - 1 is not prime, 4 is not prime. The theorem is true as such. Please RTA before posting.

Re:Mersenne Primes

[millette]

Actually, my response was off-topic since the article only mentionned mersenne primes in passing. It certainly doesn't discuss any theorems. Instead of lashing at me gratuitously, maybe you should take a deep breath while reading the article yourself.

If I can bring your attention here, you'll see why I imposed my condition the way I did.

I say goodday!

Re:Mersenne Primes

[Alsee]

Algorithm

a precise rule (or set of rules) specifying how to solve some problem

-

Re:Mersenne Primes

[Alsee]

Oops, I forgot to use google last post!

Algorithm

A step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps.

-

Re:Mersenne Primes

[Anonymous Coward]

1. IF 2^P - 1 is prime, THEN 2. P is prime. Since 2^4 - 1 is not prime, 4 is not prime.

Then the following logic would work:
If I detonate an atomic bomb 2 feet away from me, then I will die.
Therefore, if I don't detonate an atomic bomb 2 feet away from me, then I won't die.

Mortal suckers!

Re:Mersenne Primes

[JuggleGeek]

2^4-1 = 15, for instance

Apparently you need a bit of education about mersenne primes.

A mersenne number is defined by 2^N-1 where N is prime. If N isn't prime, it isn't a mersenne number. (In your example, 2^4-1=15, you didn't have a prime in the N spot, so you aren't even looking at a mersenne number.) Not all mersenne numbers are prime. In fact, most are not. If they were, it would be incredibly easy to find large prime numbers.

2^N-1 is the basic math behind mersenne primes. It doesn't mean that you can plug any number into the N position and come up with a prime. However, if you go the other way, if 2^N-1 is prime, then N is prime, every time.

If N is prime, 2^N-1 is not always prime. However, the likelyhood that it *is* prime increases dramatically as compared to testing a random number with the same number of digits.

2^N-1 where N is not prime is meaningless, and has nothing to do with mersenne numbers.

The point of using mersenne numbers is that testing large numbers (in the millions of digits range) can-and-does take a long time. Mersenne numbers are more likely to be prime than other numbers. So instead of testing everything, if you test just mersenne numbers, you are more likely to find large primes. Testing only the mersenne numbers doesn't mean that you'll find every prime number. There are almost certainly a large number of unknown primes with less than 6.3 million digits - but finding that largest one was based on testing a large number of mersenne numbers.

http://www.mersenne.org/prime.htm will help if you want to know instead of spouting bullshit. There are links there which will explain the math, the history, etc. If you just want to talk without knowing what you are talking about, you are already on the right track.

Re:Mersenne Primes

[nihilogos]

hehe

Re:Mersenne Primes

[jea6]

Google searches for karma whoring are on their way out. Current best practices invole wikipedia.

Re:Mersenne Primes

[Anonymous Coward]

That's incorrect. The logic is as follows: 1. IF 2^P - 1 is prime, THEN 2. P is prime. Since 2^4 - 1 is not prime, 4 is not prime. The theorem is true as such. Please RTA before posting.

I agree with your statements 1. and 2., but your "Since ..." is wrong. The contrapositive of your original statement is "If p is not prime, then 2^p - 1 is not prime." That means that since 4 is not prime, 2^4 - 1 is not prime. The implication does not go the other way.

For example, 2047 is not prime, but 2047=2^11 - 1, and 11 is prime.

Re:Mersenne Primes

[jrockway]

Sorry, I made a mistake. Let it go :)

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.

Reaction

[Angram]

I think I speak for 99% of the population when I say...

"Oh."

Cheaters!

[Anonymous Coward]

They probably just looked in the back of the book.

Re:Cheaters!

[Anonymous Coward]

Maybe in the back of The Book

Re:Cheaters!

[Anonymous Coward]

Acually they couldn't. RSA-576 is an even numbered question, and there are only answers to odd numbered questions.

Re:Cheaters!

[endx7]

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.

Re:Cheaters!

[tatsu69]

No. Only odd numbered problems are in the back of the book not even problems.

Re:Cheaters!

[JoshWurzel]

Your book is a lot more predictable than mine. In my textbooks (graduate structural engineering), the only answers in the back of the book are the SHORT ones. So the first chapters have every 2nd or 3rd problem. The last chapters, where the problems are hard and you actually NEED the solutions, only have every 6th or 7th problem.

Geez, professors are lazy these days.

Re:Cheaters!

[HeghmoH]

Shit. I spent four days solving RSA-577, and now you're telling me it's in the back of the frigging book??

RSA Challenge Challenge

[Caractacus Potts]

Now there needs to be cash prize for discovering the discoverer when the challenge has been met. I just checked that site today.

Re:Umm..k?

[Snoopy77]

Soo......what does this mean? RSA-576 sounds like the name of a fighter plane.

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.

The Other One Percent

[handy_vandal]

I think I speak for 99% of the population when I say... "Oh."

I think I speak for the other 1% when I say ...

"Um."

-kgj

Re:The Other One Percent

[Anonymous Coward]

And i speak for the HTML nazis when i say "Close your fucking tags!"

Re:The Other One Percent

[Upphew]

An I speak for the HTML jews when I say: "Please don't kill me!"

Re:The Other One Percent

[Anonymous Coward]

And i speak for the HTML palestinians when i say: "Please stop taking our land!"

Re:The Other One Percent

[EvilSporkMan]

...and I speak for 99% of everyone when I say this has gone on too long.

Re:Well Mr Smartypants poster...

[Anonymous Coward]

It wasn't a) anti-Microsoft or b) anti-SCO, so no one on /. cares.

Re:Hmmm. Complexity vs. Cash

[TedCheshireAcad]

Well, the computational complexity of the General Number Field Sieve is:

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

[Ninja Programmer]

Factoring composite is probably somewhat easier in the sense that it doesn't require more hardware/brute force computational power, however, its probably harder in the sense that you need to be very famillar with the very latest in factoring algorithms and essentially be skilled and willing enough to implement the very leading edge known algorithms.

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 projections, RC5-72 will not fall for decades. Factoring something like RSA-574 requires that you be up on the latest in computational mathematics as it relates to number theory. If you think you can bone up on the latest in factoring techniques in less than 10 years, then you probably have a better shot at the RSA prizes.

Oh no...

[RSA-576]

How could they *factor* ME without *my* own knowledge?! Somebody call the doctor... -RSA-576

Re:Oh no...

[Anonymous Coward]

with that uid you probably made the account after the story was posted. how lame.

Re:Oh no...

[Anonymous Coward]

you probably made the account after the story was posted.

Yep, he did.

Re:Oh no...

[Anonymous Coward]

What good would it do to call the doctor RSA-576?

(sorry, I need to get out more...)

Re:Oh no...

[Anonymous Coward]

dumbass slashdot mods are easy to entertain. must be americans...

+5 funny my ass

Re:Oh no...

[monkease]

....sounds kinky....

Re:Oh no...

[Anonymous Coward]

In Soviet Rus..I mean... In Soviet Germany...

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.

Re:Notify RSA

[Anonymous Coward]

If you think that they're so stupid, why don't you go ahead and collect the $10,000? The factors are public:

3980750864240649373971255005503864911 99064362342526708406385189575946388957261768583317

4727721461074353025362230719730482246 32914695302097116459852171130520711256363590397527

Re:Notify RSA

[marko123]

One of these numbers is not prime. Check it out for yourself!

Re:Notify RSA

[buttahead]

hell, neither of them are numbers. window's calculator just coems up with "OE...barf".

Re:Notify RSA

[Zork the Almighty]

Maple says they are both prime. Granted, it's a probabilistic algorithms, but the chance of failure is extremely low. What were you using ?

Re:Notify RSA

[marko123]

I was using a failed attempt at humour :(

Why the fuck is this modded troll?

[Anonymous Coward]

If anything, it deserves a few more insightfuls. He has politely asked a number of important questions about RSA encryption. Obviously Chris doesn't understand how this "breakthrough" matters in the big scheme of internet security, and he damn well deserves a polite response or two to help teach him about the impact.

Asshole mod: I hope you're satisfied.

Chris: I hope some of the comments from the other users have been useful to you.

Re:The factors were

[TedCheshireAcad]

Your first factor is composite, slick.

This is a /. revolution, instead of spelling nazis, we now have composite number nazis.

Re:Is this what you're talking about?

[Anonymous Coward]

Oh my lord. Get up, walk away from your computer, go into the bathroom, and drown yourself in the toilet. Seriously, you'd be doing humanity a favor.

Germany?

[gr8_phk]

I'm not suprised that someone has done it. Even the RSA site suggested 576 would fall soon. What I do find interesting is that it took 4 days for word to get out, and that the factorization was done in Germany. More interesting would be knowing what algorithm was used - is it new, or just further refinement of GNFS or MPQS with faster hardware?

Re:Germany?

[anthony_dipierro]

Took 4 days for word to get to Slashdot, maybe. Mathpuzzle.com reported this 3 days ago.

Re:Germany?

[Anonymous Coward]

Why is it significant that a German group factorized this, rather than another nationality? I hear they use maths in Germany too these days.

If it was an Ethiopian group though, now THAT would be something.

Re:Germany?

[Anonymous Coward]

If it was an Ethiopian group, then i'd cast all my racism aside and claim negroes as my equal.

Re:Germany?

[RealityMogul]

read the article. They used a number seive. It sounds like they had some specialized hardware but the article doesn't give much detail.

Re:Germany?

[Anonymous Coward]

It was a variant of GNFS. For the hardware: They did have access to a home-built linux cluster at the scientific computing institute, but they don't have "specialized hardware" for factoring.
Actually, that should be not too surprising, as it they are pure mathematicians. The mathworld article seems a bit misleading, as Jens Franke is a professor at Bonn University, and not at BSI.
(I study mathematics at bonn, so I'd know.)

Re:Germany?

[akruppa]

Specifically, they very likely used the NFS lattice siever written by Prof. Jens Franke, Thorsten Kleinjung and Friedrich Bahr. It's the fastest siever I know of, partially thanks to decend assembler optimization for different cpu types. Oh, and it's distributed under the GPL! The latest version is not on the net as far as I am aware, but an older version, and MPQS code, can be found at ftp://ftp.math.uni-bonn.de/people/franke/mpqs4linu x

And Franke has worked with the BSI before, the RSA-160 announcement here
mentiones that the sieving was done at the BSI, while for RSA-576 apparantly only parts of the post-processing were (perhaps the linear algebra?)

Alex

4 days and no mention on RSA's website?

[product byproduct]

They're busy multiplying the two 87-digit factors by hand, just to be sure.

Awww

[JDWTopGuy]

Crap, there go my plans to factor it myself.

Re:Awww

[RealityMogul]

Seriously, I just started working on it last weekend. Oh well, I wanted the $200,000.00 prize anyways.

At least it confirms that my big number multiplication rountines really work.

Re:Awww

[Tired_Blood]

I know what you mean. A couple weeks ago I realized that my attempts wouldn't solve the problem fast enough. Looking at the answer, I figure it would've taken me ~10^74 years to get it on my own.

But on that note, there's no mention of how long it took them and how many computers were used.

I'm relieved that I semi gave up before learning of this news. Oh well, at least I learned a great deal in the process.

Re:Awww

[JDWTopGuy]

Man, I had no idea that was so funny... I was actually serious (okay, semi-serious), in fact I downloaded the text file of RSA-576 a few weeks ago. If you don't believe me, browse my journal... you'll see a reference to it. (I'm too lazy to provide a link.)

But now I have at least one clue: both factors were of equal length, and were both half the length of the full number... anybody got any other hints? RSA-640, here I come!

Re:A HIT OF HELIUM

[Anonymous Coward]

*POP*

...sorry...

Or RC5-72 could fall tomorow

[Veramocor]

......if you get lucky!

There is nothing that says you won't find the correct key in the 1st .1% of keyspace you search.

Re:Or RC5-72 could fall tomorow

[swillden]

There is nothing that says you won't find the correct key in the 1st .1% of keyspace you search.

For that matter, there is nothing that says you won't guess the key on your first try!

My Mom always told me it's better to be lucky than smart.

Re:Or RC5-72 could fall tomorow

[Anonymous Coward]

My Mom always told me it's better to be lucky than smart.

Did it smart when you found out I got lucky with your mom?

Actually

[Anonymous Coward]

They're all composites, einstein. The first, third and fourth are even numbers. The second is a multiple of 5. Joke is on you.

Re:Actually

[imyourfoot]

2 is prime, genius.

Re:Actually

[jrockway]

49561029139355845747971386346688559685802770654976 22183978317743925946576415078139905781369527613655
898568246775450799399763584829976638122052329279 42
9846895584179343292612 8 is composite, genius.

First means the first one. Not the second one.

Re:Umm..k?

[Shadwell]

one day you may even learn how to spell psycho properly.

Not a big Suicidal Tendencies fan are you? :P

Mod parent down!

[Anonymous Coward]

- Nasty
- Offtopic

Re:dammit!

[Anonymous Coward]

what the hell is that supposed to mean ? your carrying encrypted data in your suitcase which happened to use that same prime number ?

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:Symmetric vs. public-key cyphers...

[randombit]

There are no known ways to break currently acceptable symmetric cyphers (such as 3-DES and AES) faster than brute force

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.

Mod parent up!

[Anonymous Coward]

-- Funny
-- On topic

Re:Hmmm. Complexity vs. Cash

[Anonymous Coward]

I don't know the answer to your question, but I must show off some knowledge, so here's something I do know! But the answer to you question probably has nothing to do with what I just said.

Oh hell, that's very insightful! There's numbers after all!

Mine is 1024 too...

[Trejkaz]

My key is 1024 too... but it's ElGamal. Is the ElGamal algorithm inherently more or less secure than RSA?

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:Mine is 1024 too...

[Trejkaz]

RTFA.

ESB-2003.0820 -- GnuPG Security Advisory -- GnuPG's ElGamal signing keys compromised
...
Note that the standard keys as generated by GnuPG (DSA and ElGamal encryption) as well as RSA keys are NOT vulnerable.

Re:Mine is 1024 too...

[infolib]

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)

What is the logic here? I'd think that the more studied system would be considered most secure? Posters here seem to agree it's easy to pick an RSA key long enough to stop Eve - even when she has the spiffiest math and fastest computers. Then why not choose RSA when it's been attacked with some success but still holds up beautifully?

Hope you can clarify a bit - after all you're the Dr. rer.nat. :-)

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,)

Re:Mine is 1024 too...

[Stephan Schulz]

What is the logic here? I'd think that the more studied system would be considered most secure? Posters here seem to agree it's easy to pick an RSA key long enough to stop Eve - even when she has the spiffiest math and fastest computers. Then why not choose RSA when it's been attacked with some success but still holds up beautifully?

The more studied system is only more secure if no weaknesses turn up. For factoring, we do have had quite significant progress over the last years, and promises for more. Now, this is the kind of progress that moves breakbility from 10e26 processor years to 10e25 processor years or so, but still, it is there.

As somebody else already mentioned, there now seems to be similar progress for the discrete log problem used by ElGamal, so I don't know if my original statement still holds in the cryptographic community.

Hope you can clarify a bit - after all you're the Dr. rer.nat. :-)

Hey, not fair! I'm not an Austrian, after all ;-)

When my theorem prover is used in cryptographic applications, one of the assumptions is usually that the cypher is unbreakable and that the protocol is the weak part. And how either theorem proving or cryptography end up under "natural things" is anybody's guess.

RSA-576?

[sharkey]

RU-486 the Next Generation?

Re:RSA-576?

[Anonymous Coward]

RU-486 eliminated the Next Generation, therefore RSA-576 was created to try to reverse those effects.

Re:The factors were

[paul248]

Yeah, I noticed that after posting, but it's not trivial to generate a 173-digit prime, so I just faked it with rand(). On second thought, I should have at least made sure the last digit was 1, 3, 7, or 9. But what's done is done.

Re:Umm..k?

[Anonymous Coward]

No, not many are. Which band member are you related to?

Re:Hmmm. Complexity vs. Cash

[couchslayer]

I read this quickly and agreed that NFS does have exponential complexity, and is impossibly slow. Damn Network File System!

Re:Umm..k?

[Snoopy77]

The sad thing is that just like Axl Rose, they probably thought they were spelling it correctly.

Re:RC5-76, not 576!

[Bombcar]

Not So! Read 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

Is it me, or is this story...

[pr0ntab]

attracting only comments from old troll accounts?

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

[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 and source code by Paul Herman and Ami Fischman.

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

Re:Hmmm. Complexity vs. Cash

[mraymer]

I've been waiting for a moment when this was slightly on-topic. Has anyone else noticed that Norton flags the official distributed.net client for Windows as a trojan?

Granted, there are some dnet trojans out there, but I think Norton goes a little overboard on this one. I don't see how dnet is less legit than SETI or Folding. Why not call those trojans, too?

Easily Multiplied Numbers !!??

[Proudrooster]

And I quoth from the article:
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 !!??

[Zork the Almighty]

I think you were typing on one a minute ago.

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:Easily Multiplied Numbers !!??

[buford_tannen]

My apologies... slashcode appears to have put those spaces there.

Stupid slashcode.

Re:Easily Multiplied Numbers !!??

[Platinum Dragon]

Does anyone have a calculator that can "easily" multiply these two numbers...

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 !!??

[Ageless]

I'm sure Slashcode will eat this Java source for lunch, but here we go.

import java.math.*;

public class Calculator
{
public static void main(String[] args)
{
BigInteger x = new

BigInteger("398075086424064937397125500550386491 19 9064362342526708406385189575946388957261768583317" );
BigInteger y = new

BigInteger("472772146107435302536223071973048224 63 2914695302097116459852171130520711256363590397527" );
BigInteger z = x.multiply(y);
System.out.println(z.toString());
}
}

[c:\temp]\j2sdk1.4.2_01\bin\javac Calculator.java

[c:\temp]java Calculator
18819881292060796383869723946165043980 716356337941 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 221305168759307650257059

Re:Easily Multiplied Numbers !!??

[acermate433s]

heck! even excel cannot multiply this numbers.

Re:Easily Multiplied Numbers !!??

[wmspringer]

Try Maxima; it's a free, open source computer algebra system that can handle numbers of arbitrary length.

Coincidentally, I was just using it to factor a (much smaller) RSA-encrypted message last week for a class..

Re:Easily Multiplied Numbers !!??

[Krach42]

famine ~$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
3980750864240649373971255005503864911 9906436234252 6708406385189575946388957261768583317*472772146107 43530253622307197304822463291469530209711645985217 1130520711256363590397527
18819881292060796383869 723946165043980716356337941 738270076335642298\
88597152346654853190606065047 430453173880113033967 161996923212057340\
31879550656996221305168759307 650257059

It's all about finding the write language for the problem. I think I spent more time writing this paragraph than putting the problem into BC.

Re:Easily Multiplied Numbers !!??

[Krach42]

yeah, it plops in the spaces because people would abuse the system, and make links that would span across the entire page causing icky horizontal scroll bars.

Re:Easily Multiplied Numbers !!??

[SirHalcyon]

echo 39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317*472772146107 43530253622307197304822463291469530209711645985217 1130520711256363590397527 | bc

Re:Easily Multiplied Numbers !!??

[Hadlock]

aha - i was wondering why that happened on long urls, also. much thanks.

Re:Easily Multiplied Numbers !!??

[JohnPM]

In python:

print 39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * \
47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527

Re:Easily Multiplied Numbers !!??

[Ageless]

Oh sure, but my version Runs Everywhere! ;-)

Re:Easily Multiplied Numbers !!??

[Krach42]

Yeah, and it breaks & encoded HTML entities also, so in case you're wondering why you end up with some weird stuff sometimes... that's why.

Don't submit this as a bug though, since you'll get yelled and bitched at. (like I have at least a few times) They insist that breaking apart elements that will get rendered as a single character should still be considered to be the length of the sum of the lengths of the individual elements.

Re:Easily Multiplied Numbers !!??

[Krach42]

Oh now that's just not nice.

Re:Easily Multiplied Numbers !!??

[elmartinos]

Everybody here has. Just use the Google calculator. Well, at least the first few digits can be compared.

Probably the simplest solution is to use Ruby:
ruby -e "p 39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * 47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527"

which prints
18819881292060796383869723946165043980716356337941 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 221305168759307650257059

You have to remove the spaces, slashdot seems to automatically add them.

Re:Easily Multiplied Numbers !!??

[Anonymous Coward]

Holy shit. Compare the Java implementation to the python one.

The next time someone calls Java a high level language, I'm going to punch them in the face.

How long did it take them?

[ajiva]

I don't see anything about how long it took them! I do know that RSA-155 took 7 months of computation to break...

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 and is working with Norton to resove the issue.

Re:Umm..k?

[Night Goat]

Suicidal Tendencies spells it Cyco, not Syco. As in "Born to be Cyco." So the guy's still a bad speller.

Post Quantum Crypto

[Multics]

Perhaps I should submit this as an Ask Slashdot instead of a comment here, but what happens when the quantum computers make breaking these things easy? (I'll leave out the word trivial since I can't imagine quantum computing being trivial anytime soon.)

What will be the face of the next from of Crypto? Only one-time pads? That sounds way painful.

-- Multics

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.

Re:Post Quantum Crypto

[Nasarius]

Go read Bruce Schneier ("Applied Cryptography"). He basically proves that it would require insane amounts of energy at near-perfect efficiency to even iterate through every possible 256-bit number. No, your 256-bit symmetric keys and maybe 4096-bit asymmetric keys are quite safe from brute force attacks, forever. That's just the laws of physics.

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:Post Quantum Crypto

[wmspringer]

My guess would be whoever has access to the computer that can do it, claims a $625,000 reward for cracking the remaining codes...

But seriously, unbreakable quantum encryption is available now; it doesn't even require a quantum computer. It's just less convenient and more expensive than RSA since it requires special equipment.

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:Post Quantum Crypto

[Alsee]

21? No way! 21 is a seriously tough nut to crack. The latest breakthrough was cracking 15. Quantum factored

-

Re:Post Quantum Crypto

[Anonymous Coward]

It wouldn't be that bad. Or well. It would be bad for RSA or for cryptosystems based on the discrete logarithm problem. Hence, it would be a danger for public key cryptosystems. On the other hand, you could basically find out new ideas based on other problems which might not be easily solvable by QC. And another question is of course: we know QC solve the problem in polynomial time, but how fast will they then really be? (I mean, performing just ten operation pro second isn't that good even if the algorithm is polynomial)

Another point are standard symmetric ciphers, which aren't based on algebraic facts. Actually QC are not that better in brute force attacks (you can get at most a quadratic speedup), so just make keys longer to achieve the same security level.

On the other hand, as others argued, you have quantum cryptography. And people are also working hard on other key agreement protocols which are (even classically speaking) information theoretically secure. So yes, why not use one time pads, once secure key generation is fast enough?

QC are not the only problem in this directions. The fact that factoring is hard is really just an assumption (even though it is a well motivated one, it stays one assumption), so it could still be possible to see polynomial time algorithms for factoring on classical computers.

Remember that the fact that nobody comes out with an efficent solution to the factoring problem doesn't imply there is no one (even if maybe it's the case). Some theorems haven't been proved for years, while on the other hand people have been (strongly) interested in factoring for, say, 20 years (or less).

Re:Post Quantum Crypto

[Anonymous Coward]

Therefore, you can send one time pads until one gets through without being viewed.

Well, doing so, an Eavesdropper can always block you. The idea there, to be correct, is that it's enough if there are (qu)bits which are not seen by the eavesdropper. Or say, Alice and Bob share some information Eve does not have (the fact that Eve might have more information than Alice and Bob it's not a problem, this only reduces the rate at which both are generating the key). Advantage distillation, information reconciliation and privacy amplification techniques are then used to get the key. And these are all classical techniques.

Re:Post Quantum Crypto

[Anonymous Coward]

Sorry, quantum computing and quantum cryptography are COMPLETELY ENTIRELY separate ideas. You can't perform one with the other.

Quantum cryptography relies ONLY on your ability to send single photons down a fiberoptic pipe, and knowing wich way they're polarized. The only way to test the polarization is to consume the photon. Anyone intercepting your data has roughly a 50% chance per bit of being detected.

Quantum computing is basically using the superposition of a molecule (the cat is both dead and not dead) to solve a problem. When you look at it, the molecule resolves to 1 state (Open the box, the cat is dead). It's great for problems that have a massive number of possible outcomes. You only have to do the calculation once to recieve the right answer, instead of testing true or false for each possible answer until you get the right one.

QCrypto - needs a reaaaallllyyy good fiber pipe.

QComp - needs a lot of little molecules and equipment to read them

Re:Post Quantum Crypto

[Andy_R]

I use LJ-5, which I believe to be sufficently safe.

No-one is going to wade through 5 pages of a Live Journal blog to find my secrets.

I was questioning the low IQ in the discussion...

[pr0ntab]

not the number factoring methods. I was speculating that most of the posters had no way of intelligently commenting on the story, as significant as it once. Thanks for the links, though.

Re:Umm..k?

[Dwonis]

but one can now assume that a properly funded entity (most likely government) has the ability to defeat RSA-576. [Emphasis added]

The authors of Microsoft-product-exploiting worms might have more computing resources available than any government by now.

Quick, call the MPAA!

[rock_climbing_guy]

Alrighty, let's have Hilary Rosen and Jack Valenti sue them for violating the DMCA.

Linkage

[Nasarius]

Dunno if this is authorized, but: Appropriate Link

Re:Linkage

[jrockway]

Just curious, is that a warez'd copy of the book? It seems strange for that to be online in its entirety.

Re:Linkage

[rimmon]

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

Python

[Quixotic137]

Python can do this, and any arithmetic with arbitrarily large numbers (up to the limit of available memory).

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.

Just some perspective...

[Anonymous Coward]

MD5 has been breakable for ages. There are tons of tools out there (john the ripper and such). It's still an industry standard (forum encryption for passwords, hell, even the /etc/shadow). It's just a matter of whether or not it's economically reasonable to break these passwords...(i.e., most people cant reverse a password like 'a2430234234mfxmiff' since they lack the power to brute force it).

Distributed Computing

[anaphora]

This looks like a prime job for distributed computing. Code a program that does this distributed, offer people xxx dollars per work calculation with a $1000 bonus if their calculation is correct. Deduct a few thousand for yourself, and voila. Crack the hardest code.

Re:Distributed Computing

[Anonymous Coward]

Gee, that's a great idea. I wonder why nobody has thought of that.

Re:Distributed Computing

[HeghmoH]

This would be an amazing idea if somebody hadn't already been doing it for the past six years.

Re:Distributed Computing

[alehmann]

The General Number Field Sieve has four different stages, and only the first is very parallelizable. http://www.nfsnet.org/ is a distributed computing project that distributes the first stage of GNFS. The last 3 are run in-house (at Microsoft, in fact).

Latest Cryptography Breakthrough

[Anonymous Coward]

Here is the latest cipher with perfect secrecy, with an added assumption on the memory limits of the adversary.

Shamir's TWINKLE and TWIRL machines

[billstewart]

Beowulf clusters aren't any threat to 1024-bit RSA - you're not going to put enough machines in a room to do the job, nor are you likely to put enough on the continent. On the other hand, for smart cards and cash machines and "export-approved" software with 512-bit keys in them, they're starting to really kick ass.

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 it's time to start thinking seriously about threat models before embedding 1024-bit limitations in hardware. That's probably big enough that only national governments are likely to be funding, rather than bank robbers and other Mafiosi.

Re:Shamir's TWINKLE and TWIRL machines

[tomstdenis]

Actually you'd be surprised. RSA-1024 will require [at least] 2^43 bits of ram and roughly 2^87 time to complete. There is enough room in my bedroom to put such a computer.

The problem is the 2^87 time [oh and the insane heat it would make...!] [for those out of a clue 2^43 bits is 1TB of memory]

Tom

Re:Umm..k?

[Pinball Wizard]

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.

Just a clarification...I know you probably know what you meant, but a casual reader may not...this is not a 576 digit number, but a 576 bit number - the value is on the order of 2^576 - a f*'in big number to factor.

Re:RC5-76, not 576!

[Anonymous Coward]

Yeah, but
RSA-576=
18819881292060796383869723946165043 980716356337941 73827007633564229888\
597152346654853190606065047 43045317388011303396716 19969232120573403187\
955065699622130516875930765 0257059
=
39807508642406493739712550055038649119 906436234252 67084063851895759463\
88957261768583317
x
47277 214610743530253622307197304822463291469530209 71164598521711305207\
11256363590397527

What if one day...

[tangent3]

What if one day someone discovers an miraculous way to easily factorizes a large number in no time. Would it be outlawed by the DMCA?

Re:What if one day...

[Anonymous Coward]

What if you stopped posting asanine trollish comments?

Both are questions that need not be answered since neither has a chance in hell of happening within your lifetime.

Global Warming

[Anonymous Coward]

Factoring RSA-2048 might considerably contribute to global warming due to computer activity. Got anybody an idea how big the temperature rise will be assuming the efficiency given by the RSA-576 challenge?

I still remember homework about a driver being stopped because he ignored a red traffic light. He claimed the light was green because of Doppler shift caused by high speed of the car. The amount of fuel required to reach this speed was by far higher than the total consumption by mankind.

Re:Global Warming

[Gannoc]

I still remember homework about a driver being stopped because he ignored a red traffic light. He claimed the light was green because of Doppler shift caused by high speed of the car. The amount of fuel required to reach this speed was by far higher than the total consumption by mankind.

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 speeds heading towards each other on parallel tracks.

digits

[Anonymous Coward]

It's still a 576-digit number, binary digits, to be precise, not decimal digits ;-)
And: 2^576 is somewhat smaller than 10^576 would have been.

Use Google!

[Maddog Batty]

Google accepts the sum but only gives 9 sig figs in the answer. Oh well.

NSA is watching

[Anonymous Coward]

I'm certain that NSA is following the news from RSA competition pretty closely. I wonder how long RSA keys they can crack?...

Use Ruby!

[DB_researcher]

The Ruby will help you.
This is an OO interpreter which can multiply big integers without any additional modules.

RSA and pseudo primes

[thogard]

RSA's security is based on there being only two primes that make up the magic numbers. The RSA contests are about the difficult problem of factoring primes however that isn't the only hard problem that RSA encryption depends on. Another problem is the Euclidian algorithm which I feel is the main weakness. The problem is that there isn't a 1:1 ratio of public keys to private keys and there may be a very large number of private keys that will decrypt a given public key.

Quantum majiggers

[Anonymous Coward]

Haven't you guys heard of those new quantum code-majiggers? Apparently it's impossible to crack because when you look at a photon it is different (I dunno where they come in). Saw it in the paper.

OK - but how much force does this actually take?

[jpellino]

So far they seem give you the dates of the completions, but not the time / cpu hours taken.
Even the distributed.net doesn't seem to have seti-like stats on cpu hours used.
This seems to take more than a single cpu and workaday time.
Without those numbers on actual cpu time needed, this seems like flagpole-sitting.
The public perception would be that anyone with a workstation and some time on their hands might do this if the methods are 'just math' and made public.

When I win the lottery...

[Overzeetop]

...I'm going back to school to study cryptography. It's just too damned cool (and I used to be a rocket scientist, a cool vocation itself).

Re:When I win the lottery...

[bhima]

On you sig, my theory is that total IQ available to the world is a constant.

Cracking old messages? Come on...

[Chemisor]

> Those people could be concerned at this point that
> 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 much of a pain DOS was! I just finished getting my printer to work (sure was tough, see attached comments on my 7551 hack) and am bored stiff. Do you know if there are any games for Linux? Moria just doesn't cut it after King's Quest."

Covered by the factoring challenge

[Anonymous Coward]

Umm no. By choosing a public exponent that is relatively prime to (p-1)*(q-1), (as is currently done), the private exponent will be unique, making the private key unique.

Math problem of the 21st century

[Anonymous Coward]

4 * 13 = ?

Re:Mersenne Primes tsarkon hates jugglefag

[Anonymous Coward]

you just fucking regurgitate a webpage to seem smart. you know shit. you know nothing about math or computer science and you have to come to /. to flex that muscle in your skull.

what. a. fucking. loser.

Re:Is 576bit big? tsarkon hates jugglefag

[Anonymous Coward]

hey fag. that isnt very funny is it. no it isnt.

i think what they guy meant is this:

if you publish an algorithm that is strong so that other people can use it to produce a fairly strong encryption, no matter what you publish, the algorithm will be crackable.

so you stupid fag, what did you use to come up with that line of text?

you are such a mouthy little fag loser with no life that gets no pussy. shut the fuck up.

Re:Is 576bit big? dr weird rules tsarkon

[Anonymous Coward]

just to let you know, Dr Weird rules, as does about 50% of the episodes in the first and second season, with revenge of the mooninites (the BELT) being the best. the third season has had a tinge of gayness, i would say that only 15-20% are very good, with the rest being sawdust.

but ATHF rules. GENTLEMAN. BEHOLD.

obligatory perl version

[djtack]

perl -Mbigint -e 'print 39807508642406493739712550055038649119906436234252 6708406385189575946388957261768583317 * 47277214610743530253622307197304822463291469530209 7116459852171130520711256363590397527'

Re:Hmmm. Complexity vs. Cash

[Morgo]

which only runs on my W2k workstation, because the distributed folks never rewrote the older cores that run on my pre-OSX Macs.

Have you tried mailing d.net about porting the clients to older Macs? They should be able to find someone willing to do it, although I admit the latest clients on their download page are very old.

I know for a fact that RC5-72 cores for PPC were made, because I wrote some of them :-)

Here's a couple.

[Tired_Blood]

Man, I had no idea that was so funny...
It is funny. Or at least, I'd rather laugh than cry. (note: I'm trying to be funny here).

But now I have at least one clue: both factors were of equal length, and were both half the length of the full number
The length of a product is equal to the sum of the lengths of it's factors (1/3 of the time it's less one). That part shouldn't be a surprise. Of the 45 different single digit multiplications (I'm excluding the use of 0), 30 produce a double digit product. 1*anything results in a single digit product, 2*2,3,4 also and 3*3. The sum_of_lengths idea for multiplication applies to all bases, not just decimal.
When I read their faq, I got the impression that the factors will be approximately of equal length (when read in binary). They also want to make it 'impossible' to crack it brute-force using a prime number list. If one factor is much smaller, then it'll be less effort using the bottom-up approach we all used in 3rd grade (x/2, x/3, x/5, x/7, etc).

I put a lot of time into the project so I won't just give it all away (see *NOTE* below). But I'll provide a couple ideas:
1. The two factors are prime. Being that both are odd values, their average will always be a whole number.
2. The average is always greater-than or equal-to the square-root of the product.
Now look up Fermat's method. It's the basis for most/all factoring algos. Here's a link. I don't necessarily like the way they describe it (there are easier ways), but it's a hint - just like you asked.

I regularly get new ideas on how to improve my approach, but each one shaves (on average) half the time. Half of ~10^74 years is still ~10^74 years. I am only using one computer, so that's one hinderence...

Here's another hint: don't use bottom-up as your main approach, it's a bigger waste of time than 10^74 years since you're guaranteed that the lower value is not small. Recall that RSA implements the use of two LARGE factors. 'Large' is definitely subjective but is relative to the given value.

I looked at your journal. The hints above help provide ways to skip large sections. 'Large' is again subjective.

Since I mentioned the journal, sorry - I'm not a fan of Descent. I just couldn't get used to the controls and navigating upside-down/sideways and so forth.

I'm sorry if this disappoints you, but I'm sure there's some quick and dirty way to find the answer without brute force. My opinion is that you just have to REALLY think different (like rejecting division or something just as radical), since no one's done better with the tools available. A historical analogy would be something like the introduction of polar coordinates or logarithmic scales - departures from conventional techniques to simplify a particular difficulty.
... hmmm ....


NOTE: I need to feel that it's actually worth something even though it's probably not.

Re:Here's a couple.

[JDWTopGuy]

Thanks! I'm going to save this somewhere so I don't lose it.

I had already figured that starting at the bottom would be an idiotic thing to do. I was thinking of setting up a distributed system, starting smack-dab in the middle of the "likely" range, and moving in both directions. That way there's no need to specify a range; simply continue until you find what you're looking for.

And yes, I know that it requires either lots of time, or incredible luck. I have the CPU-time, and friends who may donate CPU-time. (Who wouldn't donate CPU-time for potential cashola?)

Which specific project are you talking about? An attempt at RSA-576, or another number?

Re:Here's a couple.

[Tired_Blood]

I was talking about RSA-576. That's how I could estimate the time-to-answer.

I'd still like to know the amount of resources and time expended for their project. Knowing that info would tell me how my solo attempt compares.

Also, you just know that they're working on the next ones too.

Re:ut_radio 9 8

[bobbozzo]

you made this name just to grab karma, didn't you?

Too bad then that there's no karma bonuses on ++funny