#123672 - 2004-07-24 09:15 PM
KiXgolf: Vigenere Cipher - Private coding
|
Sealeopard
KiX Master
Registered: 2001-04-25
Posts: 11164
Loc: Boston, MA, USA
|
=============
The Challenge
=============
You are to write a UDF that encrypts and decrypts alphanumeric text based on a modified Vigenere Cipher using a cipher table consisting of a group of uppercase alpha letters, lowercase alpha letters, and numbers. The three groups are ordered as follows: 0-9, Z-A, a-z. Thus, the cipher table would consist of the blocks 0-9, Z-A, a-z ordered as "0123456789ZYX ... CBAabc ... xyz" plus the appropriate shifting.
Important rule change!
The modified Vigenere cipher is defined by the following rules:
- Whitespace, punctuation marks and other non-alphanumeric characters will not be encrypted or decrypted but passed through from the input to the output without alteration. If the cipher key contains such characters, they are to be discarded prior to building the cipher table.
- By default, a Vigenere cipher is using a simple Caesar shift. The modifed Vigenere cipher will add an offset to the encrypted characters on a per-word basis corresponding to the wordnumber in the sentence. Thus, the first word is using an offset of one, the second word is using an offset of two, and so on. For example encrypted character 'A' with word-offset '1' (first word) results in 'B', and encrypted letter 'b' with word-offset '2' (second word) results in 'C'.
- The lower-case cipher block will only be used if lower-case characters are present in the plain, crypto, or cipher text. The numeric and upper-case block will always be used.
A download is available at http://people.bu.edu/jenmeyer/kixtart/kixgolf_vigenere.zip
=============
Specification
=============
The Vigenere Cipher -- A Polyalphabetic Cipher
One of the main problems with simple substitution ciphers is that they are so vulnerable to frequency analysis. Given a sufficiently large ciphertext, it can easily be broken by mapping the frequency of its letters to the know frequencies of, say, English text. Therefore, to make ciphers more secure, cryptographers have long been interested in developing enciphering techniques that are immune to frequency analysis. One of the most common approaches is to suppress the normal frequency data by using more than one alphabet to encrypt the message. A polyalphabetic substitution cipher involves the use of two or more cipher alphabets. Instead of there being a one-to-one relationship between each letter and its substitute, there is a one-to-many relationship between each letter and its substitutes.
The Vigenere Tableau
The Vigenere Cipher , proposed by Blaise de Vigenere from the court of Henry III of France in the sixteenth century, is a polyalphabetic substitution based on the following tableau:
Code:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Note that each row of the table corresponds to a Caesar Cipher. The first row is a shift of 0; the second is a shift of 1; and the last is a shift of 25.
The Vigenere cipher uses this table together with a keyword to encipher a message. For example, suppose we wish to encipher the plaintext message:
TO BE OR NOT TO BE THAT IS THE QUESTION
using the keyword RELATIONS. We begin by writing the keyword, repeated as many times as necessary, above the plaintext message. To derive the ciphertext using the tableau, for each letter in the plaintext, one finds the intersection of the row given by the corresponding keyword letter and the column given by the plaintext letter itself to pick out the ciphertext letter.
Code:
Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL
Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION
Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
Decipherment of an encrypted message is equally straightforward. One writes the keyword repeatedly above the message:
Code:
Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL
Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION
This time one uses the keyword letter to pick a column of the table and then traces down the column to the row containing the ciphertext letter. The index of that row is the plaintext letter.
The strength of the Vigenere cipher against frequency analysis can be seen by examining the above ciphertext. Note that there are 7 'T's in the plaintext message and that they have been encrypted by 'H,' 'L,' 'K,' 'M,' 'G,' 'X,' and 'L' respectively. This successfully masks the frequency characteristics of the English 'T.' One way of looking at this is to notice that each letter of our keyword RELATIONS picks out 1 of the 26 possible substitution alphabets given in the Vigenere tableau. Thus, any message encrypted by a Vigenere cipher is a collection of as many simple substitution ciphers as there are letters in the keyword.
Although the Vigenere cipher has all the features of a useful field cipher -- i.e., easily transportable key and tableau, requires no special apparatus, easy to apply, etc. -- it did not catch on in its day. A variation of it, known as the Gronsfeld cipher, did catch on in Germany and was widely used in Central Europe. The Gronsfeld variant used the digits of a keynumber instead of a the letters of keyword, but remained unchanged in all other respects. So in fact the Gronsfeld is a weaker technique than Vigenere since it only uses 10 substitute alphabets (one per digit 0..9) instead of the 26 used by Vigenere.
=============
Inputs & Outputs
=============
The Vigenere UDF accepts two to three parameters. The first parameter is a string containing the text to be encrypted or decrypted. The second parameter contains the cipher key. The optional thirs parameter, if set to true, indicates that the first string is to be decrypted using the provided cipher key.
=======
Scoring
=======
All ten provided samples must be correctly encrypted or decrypted to have a valid Vigenere UDF and to have the KiXgolf score count.
=============
General rules
=============
- The UDF must be written as one or more lines.
- The UDF is expected to finish in a reasonable time, e.g. if it gets started when the challenge opens, it's expected to be finished by the time the challenge closes even on a somewhat slow computer. The UDF has to be valid during the period that the challenge runs.
- You can submit scores as often as you want until the deadline, there's no reason to wait until the last minute for a score submission. In fact, other people want to see the score to beat. So don't be a spoilsport by hoarding your score. Submit early and often.
- The UDF may only use the KiXtart/KiXforms commands/functions/macros, no other code fragments are allowed. Calls to cOM components that are part part of a standard default Windows installation are allowed.
- Calls to other executables, as long as they are part of a standard default Windows installation are allowed.
- The use of the KiXforms DLL is also permitted as the KiXforms DLL can now be considered an integral part of KiXtart scripting.
- The UDF should be self-contained (except for any I/O mentioned in the challenge). In particular, you may not do things like fetching extra data from a remote site or file.
- You may assume ASCII as character set.
- You are not allowed to use additional code that is external to the KiXgolf UDF Collection. All code must be contained within the KiXgolf UDF Collection.
- You are allowed to only use publicly available versions of KiXtart and KiXforms, private builds or alpha builds are NOT allowed
- Your submitted score must include the KiXart/KiXforms version used.
When posting KiXtart Golf Scores, please include the KIXGOLF_*.TXT file that is created in the script directory. It contains some basic information about the computer that the script is run on and the resulting scores.
========
Deadlines
========
Private coding starts Saturday, July 24, 3pm EST
Private coding ends Friday, July 30, 8pm EST
Public coding start Friday, July 30, 8pm EST
Public coding ends Sunday, August 8, 9pm EST
============
Test program
============
A test program is provided to help screen entries and to provide the Golf Score.
Any program that passes the test program can be submitted. If you are surprised that your solution passed the test program, please submit it anyway! That will help me identify bugs in the test program.
================================================================
KiXtart GOLF - How To Play
================================================================
Most importantly, anybody can play, no age restrictions, no penalties, no handicap!
The object in "real" golf is to hit the ball in the hole in the fewest strokes. The object in KiXtart Golf is to get from input (tee) to target (hole) in the fewest keystrokes.
Example: How many positive elements are in array $a?
Array $a could be of structure $a=[1, 2 ,-3, 4, -5, -7, 8, 9]
One approach:
[CODE]for $b=0 to ubound($a)
if $a[$b]>0
$c=$c+1
endif
next[/CODE]for a score of 45.
Another solution is:
[CODE]DO
$b=$b+1
if $a[$b]>0
$c=$c+1
endif
UNTIL $b>(UBOUND($a)+1)[/CODE]for a score of 53.
Better approach: Code sample 1
================================================================
KiXtart GOLF - The Rules
================================================================
1) The goal of KiXtart Golf is to score the lowest strokes.
2) Strokes are all characters in a piece of code except whitespace characters, unless the whitespace character is necessary for the line of code to work. Therefore, carriage returns and line feeds do not count or spaces in between the '=' sign when assigning variables, e.g. '$a = $b' scores 5.
3) Code can be constructed any way you like, as long as it is syntactically correct with KiXtart.
4) The final solution MUST pass all test scripts that accompagny the KiXtart golf challenge.
5) The use of '$' as a variable is allowed.
6) In case of questions about a particular way to count the KiXtart Golf Challenge organizer has the last call.
7) During the private coding phase, no code is allowed to be posted. Violations result in disqualification of said player.
8) During the public coding phase, code should be posted, reused, and borrowed from other players.
9) The test script contains the official KiXgolf scoring engine
================================================================
KiXtart GOLF - The Duration of the Competition
================================================================
1) Private coding phase: From date/time of posting the tournament challenge to Friday, July 30, 8pm EST (BBS+6 time)
2) Public coding phase: From Friday, July 30, 8pm EST (BBS+6 time) to Sunday, August 8, 9pm EST (BBS+6 time)
3) Final results: Sunday, August 8, 9pm EST (BBS+6 time)
You will need the complete package from http://people.bu.edu/jenmeyer/kixtart/kixgolf_vigenere.zip.
Edited by sealeopard (2004-07-25 05:02 PM)
_________________________
There are two types of vessels, submarines and targets.
|
|
Top
|
|
|
|
|
#123679 - 2004-07-24 11:12 PM
Re: KiXgolf: Vigenere Cipher - Private coding
|
Howard Bullock
KiX Supporter
Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
|
I guess that is part of the challenge. 
|
|
Top
|
|
|
|
Moderator: Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Ruud van Velsen, Mart
|
1 registered
(Allen)
and 628 anonymous users online.
|
|
|
