Welcome Guest [Log In] [Register]
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:

Username:   Password:
Add Reply
Impractical-1; A known Plaintext Challenge
Topic Started: Nov 22 2005, 08:42 PM (1,391 Views)
Donald
NSA worthy
[ *  *  *  *  *  * ]
I've been VERY busy at work for a while, BUT this particular cryptography problem has been running through my head for a few weeks now. If you guys remember, way back in This thread we were discussing a very impractical cipher I was playing with. Well, I've refined the design some sense then, but it's still impractical, so I decided to name it that. :)

This is the current version of Impractical-1:
Code:
 

To use this cipher you need two keywords.  For our example, lets use:
keyword 1=Rudolph
keyword 2=Stinky
(Of course, you should pick keywords that aren't in the dictionary, but thats unimportant for this example)

Use keyword 1 to create a scrambled alphabet in a matrix.  Write the keyword down.  Underneath it write the rest of alphabet, starting with the first letter after the last letter of the keyword, skipping all of the letters that are in the keyword, and skipping J.  (If J is in the keyword, drop it there)

RUDOLPH
IKMNQST
VWXYZAB
CEFG

Now take the letters off by columns to obtain:
RIVCUKWEDMXFONYGLQZPSAHTB
and place into a 5/5 matrix like this:

    1 2 3 4 5  <-Keyword #1 matrix
    ---------
1 | R I V C U
2 | K W E D M
3 | X F O N Y
4 | G L Q Z P
5 | S A H T B

Now use the keyword #1 matrix to encrypt your plain text.  Find each character from your message in the keyword #1 matrix and write down its column and row (in that order x,y)

S  E  N  D  H  E  L  P  A  T  O  N  C  E
15 32 43 42 35 32 24 54 25 45 33 43 41 32

Now we write those numbers under keyword 2:

4 5 1 3 2 6  <-alphabetical order of keyword #2
S T I N K Y  <-keyword #2
-----------
1 5 3 2 4 3  <-our encrypted message from the previous step
4 2 3 5 3 2
2 4 5 4 2 5
4 5 3 3 4 3
4 1 3 2


Pull the message off by columns, by alphabetical order of the keyword.  Repeat letters should count from left to right.  (so if you have two R's,the R to the left goes first, then the r to the right)

3353343242543214244524513253 <- The new scrambled encrypted message.

Split this up into pairs and now use key #1 matrix again to DECRYPT back from pairs into ordinary characters.

    1 2 3 4 5  <-Keyword #1 matrix
    ---------
1 | R I V C U
2 | K W E D M
3 | X F O N Y
4 | G L Q Z P
5 | S A H T B

33 53 34 32 42 54 32 14 24 45 24 51 32 53 <-from previous step
O  Y  Q  E  D  P  E  G  L  T  L  U  E  Y  <-our new result

split result into 5 letter groups and there you go!
OYQED PEGLT  LUEY  <-The fully encrypted message!


To decrypt, reverse the entire process.

Use the key #3 matrix to translate into row/column numbers
O  Y  Q  E  D  P  E  G  L  T  L  U  E  Y  <-crypt text
33 53 34 32 42 54 32 14 24 45 24 51 32 53 <-decrypt with key 3 matrix

Then count the total number of characters and divide by the number of letters in your second keyword.  From this you can figure out how many letters should be in each column, and how many columns will be short one letter.  Put the numbers under the keyword in the order of the letters.

4 5 1 3 2 6
S T I N K Y
-----------
1 5 3 2 4 3
4 2 3 5 3 2
2 4 5 4 2 5
4 5 3 3 4 3
4 1 3 2

yank back off by rows.  split into pairs and use the key #1 matrix to translate back into the original message!

    1 2 3 4 5  <-Keyboard #1 matrix
    ---------
1 | R I V C U
2 | K W E D M
3 | X F O N Y
4 | G L Q Z P
5 | S A H T B

15 32 43 42 35 32 24 54 25 45 33 43 41 32
S  E  N  D  H  E  L  P  A  T  O  N  C  E

And there is our message: send help at once!!!!!

You will note that i've eliminated the numbers and reduced it to a 5x5 matrix. The numbers were really just adding complexity to no benefit. Also, I eliminated the 3rd keyword and matrix. I did that because I realized that the result was equivalent to using the same keyword 1 matrix twice, and then doing a monosub on the final result with keyword 3. That was adding more complexity than security.

So, why am I bringing this back up? It's because I KNOW this cipher can't really be that secure. BUT, I can't for the life of me come up with an attack.

For example, assume the attack is shotgun hill climbing or simulated annealing or such. The problem is, that with each guess of the matrix, you then have to try an enormous number of transpositions before you can measure how "succesful" this combination was.

UNLESS there is some way to analyze the frequency of the 1 to 5 digits and get information about the accuracy of the decrypt that way? I did find some interesting patterns, but I'm not certain how to exploit them.

So, what it boils down to is, this cipher seem impregnable to me, and that is just HIGHLY unlikely. For years people couldn't see a way into the Vigenere, and we all know how easy THAT is once the cracks in the system were discovered.

So, I'm presenting a challenge to you guys, a challenge with the cipher at its most vulnerable. A known plaintext attack. I have encrypted Genesis 1:1 (KJV) ("In the beginning God created the heaven and the earth") in Impractical-1 using two fairly strong keywords.

Code:
 
Impractical-1 kwd1=? kwd2=?
BHBAADRAHGQNSXWEWPTTNDHRPWLKBTABRSECLTEUBSBP


Can you recover the keys? Well, obviously we don't actually need the keys themselves, for keyword 1 we must reconstruct the matrix (or an equivalent), and for keyword 2 we just need to know it's size and alphabetic sequence. With a complete known plaintext, and exact description of the method, can you recover the "keys" needed to decipher other messages encrypted with the same keys?

And, to help you test your results, here is another, unspecified text, encrypted with Impractical-1 using the same keywords as the above:
Code:
 
Impractical-1 kwd1=? kwd2=?
BYBOGBRPARBSGERXOKLBORWIUTFWPRXWCLEEEABUEELDZUROLDANP


Now these were encrypted with a program, and the program has been tested by hand just to confirm that it was working correctly. BUT, just to ensure all of you that everything is ok, this is the SAME text (Gen 1:1) encrypted by the same program using the Impractical-1 cipher, but with keyword1=DOG and keyword2=CAT
Code:
 
Impractical-1 kwd1=dog kwd2=cat
encrypt=WCQMSNMKIMPHIVTUOOCXSQQUXQMCQCIFLBHLOUOOCUQU


Good luck folks, cause I am stumped. BUT I'm paranoid enough to believe that someone ELSE can probably see a way in where I can not.

Donald

(P.S. For the curious, Impractical-2 is, of course, even MORE impractical than impractical-1. It follows all of the steps of impractical-1, then uses the keyword 1 matrix to do a playfair on the final result. It requires an optional doubling rule for the playfair. Too many steps, WAY to many steps. I'm not even going to CONSIDER looking for a break on THAT one)
Offline Profile Quote Post Goto Top
 
rot13
Elite member
[ *  *  *  *  * ]
I hate fractionating systems. Off the top of my head, I think one approach would be to first label the incoming CT by column and row:

BHBA becomes:
Bc Br Hc Hr Bc Br Ac Ar

then have to try various combinations in the transposition, but what you are looking for is a lot of coincidences of columns and rows. In this system, the column of B can be the same number as the column of 4 other characters. With a significant amount of text, though, I think you will see an above-average occurrence of matches, especially for the SENORITA letters, where the column and row for a letter are adjacent.

If you have a crib, you also fractionate the crib the same way. Then when you are in the transposition stage, you look for natural matches against the crib letters. Once you think you have the transposition licked, you can use the crib to help reconstruct which letters have matching rows and columns. For example, you might end up with the column of R and the row of B. If that is supposed to match up with Ac Ar, then you know that A and R are in the same column, and A and B are in the same row.

Maybe I'll get time to try this out with the texts you have provided. I have been spending a lot of time working my way through the ciphers in sept-oct issue of The Cryptogram, trying to solve the entire Cipher Exchange section, so I haven't had much time to spend on challenges.
Offline Profile Quote Post Goto Top
 
Donald
NSA worthy
[ *  *  *  *  *  * ]
"rot13"
 
one approach would be to first label the incoming CT by column and row:

I just KNEW there had to be a hole into this somewhere. I don't fully understand all the implications of this approach yet, but at least it's a starting point and a plan!

Quote:
 
Maybe I'll get time to try this out with the texts you have provided.

You've already helped me with just this. Thanks!

Donald
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · Challenges · Next Topic »
Add Reply