9 votes

Programming challenge: undo this "Caesar" cipher.

Posted May 28, 2018 by ruspaceni (edited May 28, 2018)

Disclaimer: I'm a novice and this is a half baked idea

Recap

The Caesar cipher is fairly straight forward as it just shifts letters along by a set amount. This means that it's quite easy to brute force. There's only 25 offsets, after all. Try to decode this to see what i mean:

Plqfh 3 foryhv ri jduolf, dqg frpelqh lq d vpdoo erzo zlwk pdbrqqdlvh, dqfkrylhv, 2 wdeohvsrrqv ri wkh Sduphvdq fkhhvh, Zrufhvwhuvkluh vdxfh, pxvwdug dqg ohprq mxlfh. Vhdvrq wr wdvwh zlwk vdow dqg eodfn shsshu. Uhiuljhudwh xqwlo uhdgb wr xvh. Khdw rlo lq d odujh iublqj sdq ryhu phglxp khdw. Fxw wkh uhpdlqlqj 3 foryhv ri jduolf lqwr txduwhuv, dqg dgg wr krw rlo. Frrn dqg vwlu xqwlo eurzq, dqg wkhq uhpryh jduolf iurp sdq. Dgg euhdg fxehv wr wkh krw rlo. Frrn, wxuqlqj iuhtxhqwob, xqwlo oljkwob eurzqhg. Uhpryh euhdg fxehv iurp rlo, dqg vhdvrq zlwk vdow dqg shsshu. Sodfh ohwwxfh lq d odujh erzo. Wrvv zlwk guhvvlqj, uhpdlqlqj Sduphvdq fkhhvh, dqg vhdvrqhg euhdg fxehv.
bonus points for a program that takes the above text and outputs the shift I used without any human input

My dumb idea (didn't work, my bad. They're in normal Caeser cipher now)

I like the simplicity of the shifting characters but having it always be in one direction, and always being the same offset makes it easy to notice the pattern and decode.

If we have the shift value determined by the length of the current word, and the direction of it dependent on if it's a vowel or a consonant.
a pirate is nothing without his ship becomes
b jolgnk kq gvmapgz ppmavbm elp odml so we still have a visibly Caesar-y cipher, but we'll know it's not a true Caesar cipher.
The offset changes for every word and then is applied based on each letter in the word. If it's a vowel, then the encoded value is shifted upwards but if not, it slides down.

For the purposes of the below tomfoolery; prime numbers are consonants and the rest are vowels.

A Valley Without Wind 1 and 2 Steam Key:
B qjsbuf jt opuijoh xjuipvu ijt tijq
FWR0H-GQM7B-5344H

Aces Wild: Manic Brawling Action:
C rktcvg ku pqvjkpi ykvjqwv jku ujkr
K5R0H-29NPM-A3OTE

Age of Empires Legacy Bundle:
D sludwh lv qrwklqj zlwkrxw klv vkls
69PQW-UY3H7-7SQWT

AI War + 4 DLC packs & Tidalis Steam Key:
E tmvexi mw rsxlmrk amxlsyx lmw wlmt
KO99D-73JZ2-XNIK3

AI War: Vengeance Steam Key:
F unwfyj nx stymnsl bnymtzy mnx xmnu
7M2I8-I99N9-6E9F2

Alan Wake Collector's Edition Steam Key:
G voxgzk oy tuznotm coznuaz noy ynov
6ZNJ5-BIVFN-6ZSDZ

Alan Wake's American Nightmare Steam Key:
H wpyhal pz uvaopun dpaovba opz zopw
7RERD-4ACYN-TCDQ2

Amnesia: Dark Descent Steam Key:
I xqzibm qa vwbpqvo eqbpwcb pqa apqx
VGEO8-OU48X-MU7BL

Anachronox:
J yrajcn rb wxcqrwp frcqxdc qrb bqry
3589L-YGF9V-NKGW0

Anodyne:
K zsbkdo sc xydrsxq gsdryed rsc crsz
9HW7H-7Z73Z-6302D

Anomaly Defenders:
L atclep td yzestyr hteszfe std dsta
ICPIB-M63TI-9Y96V

Anomaly Korea:
M budmfq ue zaftuzs iuftagf tue etub
QMPZ2-JUK8B-JRK3V

Anomaly Korea:
N cvengr vf abguvat jvgubhg uvf fuvc
30R9T-C02AA-7DQLG

Anomaly Warzone Earth:
O dwfohs wg bchvwbu kwhvcih vwg gvwd
38UM9-Z26PH-Q4VAU

Anomaly Warzone Earth Mobile Campaign:
P exgpit xh cdiwxcv lxiwdji wxh hwxe
54TYN-AU26Q-5AGGY

Aquaria Steam key:
Q fyhqju yi dejxydw myjxekj xyi ixyf
3853A-YSB4J-6243A

Awesomenauts:
R gzirkv zj efkyzex nzkyflk yzj jyzg
DH9T5-BWOQC-KB6TB

Awesomenauts:
S hajslw ak fglzafy oalzgml zak kzah
RNRJ0-CPT4O-S9UHE

Awesomenauts Cluck Costume:
T ibktmx bl ghmabgz pbmahnm abl labi
VOWWW-QTR3Q-EAS9J

These are encoded using a Caeser shift. The line under the title is a fixed phrase (a pirate is nothing without his ship) for aid in the bonus points

I can post my code if it turns out to be unsolvable (like a bug https://trinket.io/python/dabf2b61f9), but if not; I can also keep going from letters A to Y (sans U) over the weeks with my humble bundle reserves (plaintext or not). I've had these keys for far too long and I'm never going to actually use them, but I also noticed a surge of keys being donated here so figured I might as well change it up.

Have fun

7 comments

[3]
Elusive
May 28, 2018
Link
Doing the bonus challenge is only going to be possible with some hard-coded data like an expected letter frequency for the expected language or some kind of dictionary to check against known words...

Doing the bonus challenge is only going to be possible with some hard-coded data like an expected letter frequency for the expected language or some kind of dictionary to check against known words with. Even then it could only go for a probable match. It could even decode to several valid solutions in theory. It would be hard to do this even semi-concisely in a language that does not have this data built-in.

Edit: I appreciate the giveaway though!

2 votes
1. [2]
  ruspaceni (OP)
  May 28, 2018
  Link Parent
  My little gimmicky idea failed so i just fell back to encoding them in a normal Caeser shift. Also, to aid the bonus challenge; I've put a phrase in each ciphertext now
  
  My little gimmicky idea failed so i just fell back to encoding them in a normal Caeser shift. Also, to aid the bonus challenge; I've put a phrase in each ciphertext now
  1. Elusive
    May 28, 2018
    Link Parent
    I've taken the liberty of grabbing the Age of Empires key. Thank you very much! Here is my code in C/C++, reusing my caesar function from here: #include <stdio.h> #include <string.h> void...
    
    I've taken the liberty of grabbing the Age of Empires key. Thank you very much!
    
    Here is my code in C/C++, reusing my caesar function from here:
    
    #include <stdio.h> #include <string.h> void caesar(char* message, int shift) { while (*message) { char base = 0; if (*message >= 'A' && *message <= 'Z') base = 'A'; if (*message >= 'a' && *message <= 'z') base = 'a'; if (base) *message = ((*message - base + shift) % 26 + 26) % 26 + base; ++message; } } int main() { const char expected_key_phrase[] = "A pirate is nothing without his ship"; char encoded_key_phrase[] = "D sludwh lv qrwklqj zlwkrxw klv vkls"; int detected_shift = 0; while (strcmp(encoded_key_phrase, expected_key_phrase) != 0) { caesar(encoded_key_phrase, 1); ++detected_shift; } printf("Detected shift: %d\n", detected_shift); char encoded_value[] = "69PQW-UY3H7-7SQWT"; caesar(encoded_value, detected_shift); printf("Decoded value: %s\n", encoded_value); return 0; }
    
    1 vote
[4]
xiretza
May 28, 2018 (edited May 28, 2018)
Link
Well, it's not solvable with 100% certainty (just look at the encoded without in your example - both w and i encode to p). Edit: also, what is a word? Only space-delimited or also with...

Well, it's not solvable with 100% certainty (just look at the encoded without in your example - both w and i encode to p).

Edit: also, what is a word? Only space-delimited or also with hyphens/colons?

Edit 2: yeeeeah I'm gonna stop this until I have some more info or I'll get my account timed out. Code so far: https://bpaste.net/show/6c6fd4391e89

1 vote
1. [3]
  ruspaceni (OP)
  May 28, 2018
  Link Parent
  Oh yeah it's not bidirectional perfectly since there are collisions like that. Silly of me to actually overlook that. Words are just space separated, yeah. So the way to get the steam key out on...
  
  Oh yeah it's not bidirectional perfectly since there are collisions like that. Silly of me to actually overlook that. Words are just space separated, yeah.
  
  So the way to get the steam key out on the other end would be to have a cipher key. And that key is essentially a list of the Vowels,Consonants,101010101 and whatnot. So if give you a number, and you represent it as binary, and then use that to tell which direction you need to go in decoding, then it should be gucci, right?
  
  I'll get started on encoding all the cipherkeys
  
  2 votes
  1. [2]
    xiretza
    May 28, 2018 (edited May 28, 2018)
    Link Parent
    Honestly not sure what you mean there. Anyway, I decoded the caesar paragraph: Mince 6 cloves of garlic, and combine in a small bowl with mayonnaise, anchovies, 5 tablespoons of the Parmesan...
    
    Honestly not sure what you mean there. Anyway, I decoded the caesar paragraph:
    
    Mince 6 cloves of garlic, and combine in a small bowl with mayonnaise, anchovies, 5 tablespoons of the Parmesan cheese, Worcestershire sauce, mustard and lemon juice. Season to taste with salt and black pepper. Refrigerate until ready to use. Heat oil in a large frying pan over medium heat. Cut the remaining 6 cloves of garlic into quarters, and add to hot oil. Cook and stir until brown, and then remove garlic from pan. Add bread cubes to the hot oil. Cook, turning frequently, until lightly browned. Remove bread cubes from oil, and season with salt and pepper. Place lettuce in a large bowl. Toss with dressing, remaining Parmesan cheese, and seasoned bread cubes.
    
    program used: https://bpaste.net/show/9f612d1c0b24 (could use some list comprehensions but I'm lazy)
    
    edit: now with improved pythonics. https://bpaste.net/show/f2db6241041b
    
    1 vote
    
    ruspaceni (OP)
    May 28, 2018 (edited May 28, 2018)
    Link Parent
    Oh nice. I've got something like this which i actually made a long time ago (and used to encode the steam keys) https://trinket.io/python/dabf2b61f9 There's a magic number in there already for the...
    
    Oh nice. I've got something like this which i actually made a long time ago (and used to encode the steam keys)
    https://trinket.io/python/dabf2b61f9
    There's a magic number in there already for the current phrase.
    
    it worked for just alphabets and spaces, but for the keys I had to add numbers. I fear that i might have messed something up though, as I can't seem to get the keys out the other side perfectly anymore ;/
    
    But basically, because we know the underlying rules of which direction it shifts in response to vowels or consonants we can decode it if we had a list of the vowels and consonants in the origional text to serve as a key.
    even if there's 2 p's, there might not be 2 C's next to eachother in the key, so they'll go back to their intended values.
    since it's just 2 things, we can use binary for it. 1429662941 is the compact and encoded version for 1010101001101101110110011011101 which is in-turn the encoded version of Vowel,Consonant,V,C...
    
    not entire sure what the issue is right now but the cipherkey that seems to be correct is subtly wrong still ;c
    
    edit: oh i'm a massive dummy..... the way i was doing my lookup tables for the char values is to blame I think.
    
    I have an array set up like a:1,b:2, and whatnot, but it also goes 1:a, 2:b, because that was easier for me at the time. But now that numbers are in my alphabet it's messing completely.
    
    The steam keys i posted are probably corrupt then, so i'll just post them in the standard ceaser shift then