Running Key Cipher

Herrkutt · 11-15-2006, 10:15 PM

Running Key Cipher:

Text: "SEE SPOT RUN"
Key: "SPOT RUN SEE"
Crypt: "H76tsDFD@G<5"

What I did here was add the ASCII values of the top and bottom mod 26 and add 32, then convert back to letters.

Anyone have any ideas on how this could be decrypted given a much larger encrypted piece of text (38,000 Characters)?
I was thinking using some sort of patter or frequence analysis but im stuck.
Thanks in advance
_________________
-------------------
~HerrKutt

matthewg42 · 11-16-2006, 03:55 PM

The operation you described doesn't match your results. e.g. the first character:

Text = S, Key = S.
ASCII S = 83
((83 + 83) mod 26) + 32 == 42 == '*'

Or did you mean
83 + (83 mod 26) + 32 == 120 == 'x'

Can you show your working?

Herrkutt · 11-17-2006, 02:17 PM

Yeah I noticed I did the wrong calculation.

But thats not really what I was trying to ask.
My main point that I wanted to show is that the two E's in the plain text can be 2 different letters in the encrypted text.

So Im stuck at trying to decipher the crytp text to find the key AND the plain text, since im only give the encrypted as input (38,000 characters from ASCII 32-126).

I hope that clears up my question a bit more.
Thanks

matthewg42 · 11-17-2006, 03:16 PM

Yes, using mods can erase information. There's no accurate way to reverse a mod operation like this. Consider the letters A..Z having values 0..25, and using mod 3 (never mind the addition of the key value for now).

Code:

Cleartext, value     value mod 3     Ciphertext
A, 0                 0               A
B, 1                 1               B
C, 2                 2               C
D, 3                 0               A
E, 4                 1               B
F, 5                 2               C
G, 6                 0               A
...

Given a cipher text character A, you can't tell which letter was the cleartext, it could have been A, D, G, ...
Now if there's only a few cases where you have an ambiguous reverse, and you know more or less what to expect, you can do some statistical analysis and make an educated guess as to the result.

For example, imagine some scheme which when decrypted, results in "HEL?O WORLD", the ? being possibly an L or a B... you can guess that it should be an L... but you are assuming the cleartext was English and didn't have spelling mistakes in it.

Whether or not information loss occurs depends on the exact algorithm, hence my request for clarification of yours. I suspect it does.

ta0kira · 11-17-2006, 08:13 PM

Quote:

Originally Posted by matthewg42

The operation you described doesn't match your results.

OP didn't say anything about ASCII. Besides, most widespread encryption algorithms aren't expressed in an ASCII way.

In order for it to work, however, OP will have to project between ASCII and letters (if using a compiled language, that is.) The easiest way to do this is subtract the character 'A' or 'a' from each letter. The problem with OP's method is the space character, and possibly commas or periods. This makes the finite field greater than 26 values. So (Herrkutt); you need to decide what the set of characters you want are.

Once you project from ASCII to your 26 or so character field, just perform all operations modulo the size (e.g. 26), then reverse the projection back to ASCII. Example:

Code:

char data[128];
char code[128];

//...

for (int i = 0; i < 128; i++)
{
  data[i] -= 'A';

  data[i] += code[i] + 32;
  data[i] %= 26;

  data[i] += 'A';
}

ta0kira

Herrkutt · 11-20-2006, 10:07 PM

Thanks guys so far for your help.
Anyway Ive been given some more information on the key.
Its actually a Vigenere Cipher but the key is really long.
The text file is about 38000 characters long and the key file is at least 50%.
So what I was thinking is finding out first the length of the key and then possibly doing a comparison from where the key starts again and the beginning of the message.

Now the algorithm im using doesnt actually use mod (that was my mistake)

Text: "SEE SPOT RUN"
Key: "SPOT RUN SEE"
Crypt: "H76tsDFD@G<5"

What I did was take the ASCII of S in the Text (call that T(S)) and then Ascii of the S in Key (K(S)) and added the two together subtracted 126 and added 32 (min value)

so T(S) + K(S) = 83+83= 166
-126 = 40
+32 = 72 = H

Ive defined the character set to go from ASCII 32-122 for the key and plaintext but from 32-126 for the encrypted key.
Once again any help would be awesome.

matthewg42 · 11-21-2006, 05:33 AM

When you say the key file is at least 50%, do you mean it's at least half as long as the cleartext? One wonders why the person who enciphered the message didn't just go the whole hog and use a one time patch

Do you know the exact key length?

The standard method of attacking a Vigenere cipher is to determine the key length by looking for the distance between bigrams & trigrams (candidate key lengths being factors of common seps), and then splitting the ciphertext up bu taking a character every [keylength], and doing regular freq analysis on that set, and then the next set etc. However, if the key length is half as long as the cleartext, this will be a limited use... I wouldn't know how to go about it in that case.