Yesterday I was solving an interesting question that has been used on the Swedish Computer Science contest – a programming contest, in 2010, which probably is simple, but interesting because it emphasises sequences, et cetera.
The question introduced the Vigenére cipher in a classical way, with two disks containing letters of the English alphabet. In the beginning, we know several things about the encrypted text, which are to help us when we are going to crack the message.
- The disks might have different number configurations, i.e. there is still a shift, which is unknown.
- In order to “make it harder” for the enemy, each time we have obtained a letter, we continue by using a new shift, and this shift is increased by a constant value.
- Fortunately, we get to know that each message contains the word “HEJ” – a Swedish word for “hello”, which might be used as “bye”, I think.
Also, we get some examples as well, for instance:
Example 1:
Encrypted text: LRIJOUZRIYAQIRAG
Message: HEJVITARENFIKANU – means let’s take a “fika”
Example 2:
Encrypted text: GCGDJJI
Message: HEJHOPP – hello in an optimistic manner
There is also an example of this sequence,in Example 1, which is tells us that the difference is 9, 12, 15, 18… (common difference 3).
I’m solving this using a recurrence, and I’m not simplifying this arithmetic progression in any way, I just add d all the time.
The code below has passed all their tests, which are located at the end of this post.
static void Main(string[] args)
{
/*
* Copyright (C) 2013 Artem Los,
* All rights reserved.
*
* This code-snippet can be found at:
* http://clizware.net/
*/
string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
Console.Write("Enter the message: ");
string message = Console.ReadLine();
int H = alphabet.IndexOf("H");
int E = alphabet.IndexOf("E");
int J = alphabet.IndexOf("J");
int dA = mod(alphabet.IndexOf(message[0]) - H, alphabet.Length);
int dB = mod(alphabet.IndexOf(message[1]) - E, alphabet.Length);
int dC = mod(alphabet.IndexOf(message[2]) - J, alphabet.Length);
int init1 = dB - dA;
int init2 = dC - dB;
int dConst = init2 - init1;
int dPrev = dC;
Console.Write("Output message: HEJ");
for (int i = 3; i < message.Length; i++)
{
init2 += dConst;
dPrev = mod(dPrev + init2, alphabet.Length);
int X = alphabet.IndexOf(message[i]);
Console.Write(alphabet[mod(X - dPrev, alphabet.Length)]);
}
Console.ReadLine();
}
static int mod(int n, int b)
{
return n - b * (int)Math.Floor((double)n / b);
}
}
Example 1
RIPIWDUXRS
HEJSOVERNI
Example 2
IGNUFAKPXYVSF
HEJNUKOMMERDE
Example 3
PAJESQBIPOOPKAP
HEJKOMHITGENAST
Reference:
http://www.progolymp.se/Oldpage/arkiv/kval10.pdf
http://www.progolymp.se/Oldpage/arkiv/kvalsvar10.pdf