| Welcome to Crypto. We hope you enjoy your visit. You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free. Join our community! If you're already a member please log in to your account to access all of our features: |
- Pages:
- 1
- 2
| Transposition Cipher Cracker (c++) | |
|---|---|
| Topic Started: Dec 17 2007, 08:42 PM (1,526 Views) | |
| jdege | Jul 6 2009, 01:12 AM Post #16 |
Elite member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
First, no, having a crib does not always make it easy. If the crib is short, and contains no rare characters, it may not be of any real help. Knowing that a text contains the trigram "ARE" rarely helps you much. But generally, if you can place a crib, you've pretty much cracked a columnar. Second, it doesn't take all that much text for basic statistics to come through. Testing digram and trigram frequencies can identify a successful trial decrypt for a transposition with a fairly shallow depth. Third, my answer was in the context of a brute-force attack. There are, as you say, much more effective methods for attacking the problem. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
 |
 
|
| osric | Jul 6 2009, 07:54 AM Post #17 |
|
Advanced Member
|
Revelation, Could you give us a few of the columnar ciphertexts you have solved with your program and the cribs you have used in the solving? Could you also tell us the solving time for each ciphertext, and the speed of your computer processor(s)? Perhaps you could also give a brief description of the columnar enciphering process and the way your Brute deciphering algorithm works. The reason for asking is to give members of the Forum something interesting to play with, and also to see what other ideas members will come up with for solving columnar ciphers. I am thinking particularly here of members to whom the columnar cipher may be novel. For those experienced with columnars, you might like to throw in a few ciphertexts that your program is unable to solve. |
|
|
| Revelation | Jul 9 2009, 11:55 AM Post #18 |
Administrator
|
Well, I have tried the hardcoded one: irtyhockeibtdaamoelatcnsronhoniirttcacdeiunsihaioarnndgpruphahirgtoarnmclspstwe with crib "computer" and some others texts which I haven't got anymore  My computer is a quad core 2.20 ghz, but since this application runs single core, the speed is 2.20 ghz. The way my brute forcer tries to decipher a text is by going through all the possible key combinations for a chosen cipherlength. It then decrypts the text on the fly, by using an algorithm that finds the correct character for the n-th position. It immediately checks if that letter is completing the crib. Some problems with this method are false hits. This will happen at large keys (>10), because in my example "computer" will be the outcome of multiple keys. Also, if your crib is small, like "are", you are going to find very many false hits. False hits aren't always a problem. If you find one with a decent crib like computer, you can probably read the text, because your brain can unmangle the rest of the text itself. The advantage is that you can stop the application and solve it yourself or use a much longer crib, now you've seen the text. Currently, I am unaware of texts that can't be solved. I guess that is the beauty of brute forcing. The main disadvantage is that with long keys (13+) cracking will take very long. Edited by Revelation, Jul 9 2009, 11:56 AM.
|
|
RRRREJMEEEEEPVKLWENFNVJKEEEEEAOLKAFKLXCFZAASDJXZTTTTTTTLSIOWJXMOKLAFJNNKFNXN RAGRBAQEMHIGDJVDSEOXVIYCELFHWLELJFIENXLRATALSJFSLCYTKLASJDKMHGOVOKAJDNMNUITN RRRRLJVEEEEECLYVYHNVPFTAEEEEEMWLMEIRNGLARWJAKJDFLWNTIERJMIPQWOTZEOCXKNUBNXCN RJIRPOWEANFUSNCZVDVZNMSFEKLOEPZLDKDJWSAAAAAAAOERHJCTNCKFRIMVKSOFOMKMANREWNBN RZUDRGXEEEEENFQIDVLQNCKNEEEEEDGLLLLLLAWIOSNCDARLODMTOEJXMILDFJROTKJSDNLVCZNN | |
|
|
|
| osric | Jul 11 2009, 03:58 PM Post #19 |
|
Advanced Member
|
I had fun solving your Columnar using 11 columns and the key: 10 8 2 3 1 0 6 9 7 5 4. "CRACKINGACOLUMNERSTRANSPOSITIONCIPHERBYHANDISALOTHARDERTHANDOINGITWITHACOMPUTER" I used a brute method like your own but I didn't use the crib. Instead I scored the plaintext from each perm with log tetragraphs. My method takes 45 seconds to go through all the 11! perms of a period 11 Columnar. The solution to your cipher showed up after 1.5 seconds, because the correct key was near the first perm generated of 10 9 8........ My computer is a Mac with two Intel 2.7GHz dual core processors. From your comments you may be interested in a more intelligent and faster way of solving Columnars than generating all the perms in a brute force approach. This solves your 11 column cipher in less than a second and solves a 29 column cipher in 14 seconds. The principle is that there is a limited number of starting positions for each column. It's obvious that the first column of cipher text always begins with the first ciphertext letter. The second column has just two possible starting positions, dependant on whether the first column is short or long, and both are definable. For example in your cipher of 11 columns and 79 letters, the long columns have 8 letters and the short columns 7. So the second column of ciphertext begins at letter number 7 (zero based) or number 8. Here are the starting positions of all the columns of your cipher: col=0 : 0 col=1 : 7 8 col=2 : 14 15 16 col=3 : 21 22 23 col=4 : 28 29 30 col=5 : 35 36 37 col=6 : 42 43 44 col=7 : 49 50 51 col=8 : 56 57 58 col=9 : 63 64 65 col=10: 71 72 Now you put together all the possible combinations of 4 columns, score each with log tetragraphs and select the highest scoring. You've then got 4 correct columns of plaintext. Then you take the 4th column so found and put it with all combinations of remaining columns and, scoring with log tets, choose the highest scoring combination. You have added another 3 correct columns. You keep going until you have all the columns in the correct order, and thus the solution. Though the programming is more difficult than brute force, the solving time is very quick – especially for the columnars with many columns. This makes solving possible where brute force would take too long. This technique is an example of what I call 'solving by parts' (you will remember in calculus 'differentiating by parts' which made it possible to differentiate complex functions by breaking them down into parts and dealing with those). It is often useful for diagnosing and solving ciphers which have an encipherment block – Vigenere family, Cadenus and so on. |
|
|
|
| nullsole | Aug 12 2009, 02:59 PM Post #20 |
Just registered
|
My first Python program is going to be a Transposition solver -- a Route Transposition solver! At least the 48 basic routes. I get so frustrated with the trial and error hand solving of these. I decided it would be my first Python program.  At least with the full columnars you can do statistics (was reading Friedman Vol 4) and experimented with E-2 in the MJ Cm and found it worked! But the Route Tramps --- ugg. I know you can do vowel checks etc ... but by the time you get a good score you found the route anyway - at least with the short ones in the Cm. |
|
|
|
| osric | Aug 27 2009, 02:24 PM Post #21 |
|
Advanced Member
|
For your Route project, you may find the ACA Computer Columns of July-August and September-October 2002, written by AAHJU, of interest |
|
|
|
| nullsole | Aug 29 2009, 08:04 PM Post #22 |
|
Just registered
|
Thanks! Now I don't have to reinvent the wheel -- just translate it!  The articles help me approach / setup the project. Thanks for pointing me in the right direction. Am working on it right now. |
|
|
|
| 1 user reading this topic (1 Guest and 0 Anonymous) | |
| « Previous Topic · General · Next Topic » |
- Pages:
- 1
- 2
4:35 PM Nov 23
