decrypting?

[FUTI]

Since this is subject I know absolutely nothing about...I had to come here in hope I will find somone who knows much about it. And I "wisely" choose water cooler to post this.:o

The old WWII or even before decrypting routine where somewhere on the lines of language analysis like finding frequency of a letter in some language, then look up enough encoded messages to find a frequency of a number/code that could be that one and through finding couple letters geting enough data to find an algoritam used for encryption and decrypt messages. I think I had some file with frequency of letters appearance in english words - I will check and post it when I find it. Structure of messages has usually certain structure (like to whom it is sent, where, when, message text body, from whom it originates etc.) that can also help. That is maybe the reason why using Navahoe indians as cryptographers where very good idea for US in WWII - who would try to decrypt it using that poorly known language. Recently I found this site that can bring up crunching of the coded messages one step closer - at least I saw it that way and if you think I'm wrong just hit me, I asked for it since I want to learn.:D
www.wordcount.org

Know I'm aware of the fact that there are ways to encode message in such way that won't give you one letter = one number relation but I'm not sure are they in common use. :confused:

Also there is a way to make you "enemy" life hard by adding trash portion between paragraphs that your decrypting machine just cut-off at site while you would have to work all of the message without knowing what part of it is just "bloody noise added to make your life miserable".:cool:

Some millitary systems like subs can't use the technics like the last one I described, because of the radio wavelength they use is restricting them for lenght of message in such way that they use three letter codes for whole commands. Now this message look easier to crunch, but result without interpreter look like Zulu language.:rolleyes:

Anyway I wanted to ask would it be possible with the help of the frequency of letters in english language, and its word count to crack the PGP encoded english text? :) Looking forward for your answers...this just spin-off the whole resistance/crackdown mania if you were asking ;).

[nbk2000]

PGP is, as far is know,, unbroken. This by experts with supercomputers and an alphabet worth of letters behind their names. So breaking a PGP'd message isn't something you need to worry about.

As for manual ciphers, the kind you can do by hand without the aid of a computer or other machine, those can be broken to varying degrees, given enough cipher text or guess of probable word content. But there are messages unbroken to this day that were done by hand, since there aren't either of these things to get a 'wedge' into the cipher to start working it open with.

I've scanned a book all about cryptanalysis of manual ciphers, current up till the late 40's, for the DVD (I know, I know...:rolleyes: ). Very useful for breaking your sisters diary code. :p

Google search term that you'll find very helpful:

cryptanalysis "frequency count" english alphabet

Copy/paste the entire above line.

Also:

http://members.aol.com/jpeschel/historical.htm

A listing of free cryptanalysis tools for your computer to help break manual ciphers.

[akinrog]

Dear Futi,
As for the cyphering algorithms like PGP which use public key, private key pairs, these systems are not symple algorithms where you replace certain characters with certain cypher characters to mingle the resulted encoded text for the purpose of rendering it illegible by the eavesdroppers.

Instead they are using computation-intensive mathematical algorithms which uses very (really very) large prime numbers and exponential calculations. Search for public key algorithms on Google to find leads about this. HTH.

[FUTI]

Thanks to both of you guys. I knew some of the facts you pointed me to, but some new have also appeared.

I had to ask this since I have a friend that is kind of computer guru, btu when it comes to privacy and computer programs his more paranoid then anyone on this forum. I knew for a fact that he is using some version of PGP that belongs to the museum of computer program codes for that reason and keep claiming that due to the pressure that goverment of USA used against the company that originaly made PGP all versions above some x.y are compromised in some way etc.

It is not directly linked with the way I proposed to crack the message of course, I just tried to heat the things up and see what will happend.;)

[Meawoppl]

I wouldn't worry about PGP's security. Lots of people, corporations, and governments put some very solid trust into it. I don't know who said it but good cryptography is like a balloon, no matter how cleverley you put a hole in it it still deflates. Not to mention I am sure that there are open source algorithims that you can look at. The first person who figures out how to break it stands to make a lot of money. . . :p

[akinrog]

Dear Futi,
Check the following link, it contains a lot of info about encryption (with C code samples too :) )

Link (http://rapidshare.de/files/8919742/Applied_Cryptography.pdf.html.html)
Regards

[Jacks Complete]

I'm sure that there are some really, really massive parallel processing systems using FPGAs that are used to bust PGP codes open. If you do the maths, you can work out that they would do it in a few years. However, none of us are likely to draw that much heat down on himself, and such evidence would never be released at any normal trial due to the "if you know they can read it you won't write it in public" factor. They have hundreds of thousands of PGP things to try to break every day, so they aren't likely to have hammered your key open yet.

I would say that PGP does have a security "hole" (of a sort) in it. The commercial version allows your bosses to add a key so that they can also decrypt what you have written without your key, so if you refuse to tell them stuff, they can still get it. This is, however, by design, and as long as you have control over your system, this won't be an issue for you.

Going back to the OP, the first cyphers were simple substitution. A became C for example, and this was the "Caesar shift" cypher.

cdefghijklmnopqrstuvwxyzab
abcdefghijklmnopqrstuvwxyz

Simple to break even on a few hundred letters, especially when the whitespace and punctuation was left in! Just find a "the" or "A" or "I" and you are halfway there. (I invented a non-alphanumeric version of it years ago with a grid, but it was no more secure, looking back.)

Later came the better idea of adding a keyword or some secret key to scramble the alphabet, rather than such a simple shift.

secrtkywodabfghijlmnpquvxz
abcdefghijklmnopqrstuvwxyz

This needs a little more work to break, since getting the first letters wouldn't give the whole story. The start could, of course, be offset too, but that wouldn't help much.

The next big innovation was to scroll the offset. This was a big deal, and for a while it meant that crypto was ahead of the breakers. What you did was have an array of alphabets to choose from, rather than just one other. The offset changed with each encoding step, which meant that there was (effectively) a different cypher key alphabet for *every* letter! However, letter frequency analysis got this one too, in the end, because the patterns weren't long enough for there to be no loops in the writing. Today, you could make it massive with an infinite key, and hence secure, but you would still be stuck due to the key distribution problem.

Public Key (PK) crypto solved the key distribution issue. The key distribution issue is that I have to send you a key for you to encrypt the message. You need to share a secret. That is great if I can have you pop round and pick up a disc or something, but if we have never met, and we assume someone is watching your email, how can I email you a key to encrypt something without you (and hence anyone) being able to decrypt the message? Well, I could encrypt it, but that brings us back to the initial issue...

The answer (partly) is to use a non-returnable function, like modulus. If we use mod 10, we get a cute one way function. If the answer is 5, did I add 10, 20, 30, etc. to 5, or did I add 1, 11, 21, etc. to 4? If the original number was 4, you can't know by working backwards from the answer. The other part of the answer is to use a massive prime number, and the factorisation of it. Finding primes takes a while, and there are log(n) primes in n number space, so you never run out. If I give you a huge number, you can either factorise it to find said primes, or look on a table. But you don't know what the big number is, nor one of the factors. You can't work backwards, you don't know enough! So, you have an answer of 5, but you don't even know what modulus the answer was found out from, giving you no way back to the plaintext.

The most secure system is still the one-time pad. However, the re-use of a one-time pad makes it simple to break, as the two messages are subtracted to reveal the answer, which is then removed from both messages. This reveals the answers in short order. It also leaves you with the distribution issue, which is huge for modern systems where you might want to send 50k words every day, or 650Mb, and so need a 650Mb long one-time pad. Every day! (And you have to keep them all for decryption too!)

:-) I hope no-one's upset by my terrible descriptions! Add clarifications and corrections as needed.

Oh, I should also have added that there were many tricks used to make these things harder, like using another language first, hiding "of" as "v", removing whitespace, regrouping the letters into 5's (or 4's, etc.), etc. but they just made it a bit harder, rather than actually stopping the attacks. There were also things like the "railfence" which simply used maths to re-order the letters, scrambling them that way, and, of course, sometimes they were encoded once with one cypher then again with another!

Go play with http://members.aon.at/cipherclerk/CipherClerk.html and try breaking even some of the cleverer cyphers by using AAAAAAAAAAAAAAAAAA as the input, then BBBBBBBBBBBBBBBBBBBBB, etc. and you can see the weaknesses right away on many of them. Try that with PGP and you get nowhere! (However, a girl in the far east has recently broken MD5 and a few other modern cyphers by doing exactly this trick!)

[nbk2000]

Kryptos is a sculpture located on the grounds of CIA Headquarters in Langley, Virginia. Installed in 1990, its thousands of characters contain encrypted messages, of which three have been solved (so far). There is still a fourth section at the bottom consisting of 97 or 98 characters which remains uncracked.


An interesting real-world application of cryptanalysis against competently enciphered messages.

http://www.elonka.com/kryptos/ (at the bottom)

[FUTI]

WOW!
Hats down to NBK for great link.
Special thanks to akinrog for a good book.
And to Jacks my deepest gratitude for deep analysis and explanation. I'm reading Harris's book Enigma just now so this thread created the atmosphere just fine...:D