Page 1 of 8 12345>Last »
Topic Options
#123672 - 2004-07-24 09:15 PM KiXgolf: Vigenere Cipher - Private coding
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
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
#123673 - 2004-07-24 09:56 PM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
Quote:

The modifed Vigenere cipher will use a unique Caesar shift on a per-word basis corresponding to the wordnumber in the sentence




does this mean that we should look for dots?

also:
Quote:

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




in english, lower case is only used if lower-case letters are found in input.
_________________________
!

download KiXnet

Top
#123674 - 2004-07-24 10:06 PM Re: KiXgolf: Vigenere Cipher - Private coding
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
Loc: Boston, MA, USA
Quote:

does this mean that we should look for dots?



I don't know what you look for ;-) However, the rules specify how non-alphanumeric characters in the input streams are to be handled.
Quote:

n english, lower case is only used if lower-case letters are found in input.



Yes, that is correct.
_________________________
There are two types of vessels, submarines and targets.

Top
#123675 - 2004-07-24 10:10 PM Re: KiXgolf: Vigenere Cipher - Private coding
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
Loc: Boston, MA, USA
BTW, for those of you who like to analyze the strenghts and weaknesses of the modified Vigenere cipher. The modifications introduce one major flaw which can result in the encrypted text not being decrypted correctly. Special recognition to the person who can name and explain this weakness.

However, this flaw will not affect the examples provided in this challenge and you are not required to code around this flaw.
_________________________
There are two types of vessels, submarines and targets.

Top
#123676 - 2004-07-24 10:37 PM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
I mean, that your rules says "sentence"
does this mean the whole input string, or blocks separated with dots in it.
_________________________
!

download KiXnet

Top
#123677 - 2004-07-24 10:47 PM Re: KiXgolf: Vigenere Cipher - Private coding
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
Loc: Boston, MA, USA
Generally, a dot '.' is used to separate sentences. However, a dot between two numbers would not indicate a sentence separation but a decimal point.
_________________________
There are two types of vessels, submarines and targets.

Top
#123678 - 2004-07-24 11:11 PM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
so, how do we separate the sentences in input text?
after all, in your rules it says that the sentences word index has a meaning.
_________________________
!

download KiXnet

Top
#123679 - 2004-07-24 11:12 PM Re: KiXgolf: Vigenere Cipher - Private coding
Howard Bullock Offline
KiX Supporter
*****

Registered: 2000-09-15
Posts: 5809
Loc: Harrisburg, PA USA
I guess that is part of the challenge.
_________________________
Home page: http://www.kixhelp.com/hb/

Top
#123680 - 2004-07-24 11:24 PM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
to understand the rules?
so, we fall back to the old debate should the rules and goals be clear for everyone to understand or should we have some quessing also included to make it little bit harder.
_________________________
!

download KiXnet

Top
#123681 - 2004-07-24 11:32 PM Re: KiXgolf: Vigenere Cipher - Private coding
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
Loc: Boston, MA, USA
I don't really see the problem. At least in the English language, the full stop (dot, '.'), exclamation mark '!', and question mark '?' indicates the end of a sentence, while a space indicates a separation between words. Therefore, having this text fragment "This is sentence one. And this is sentence 2" it is quiet obvious that the dot after the word "one" indicates a full stop and therefore the end of a sentence.
_________________________
There are two types of vessels, submarines and targets.

Top
#123682 - 2004-07-24 11:44 PM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
damn.
now, this clarified a lot.
and, we need to also not search for those characters, we need to separate them from decimal stuff and so on...

k, thanks.
_________________________
!

download KiXnet

Top
#123683 - 2004-07-25 02:30 AM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
next Q.
what does mean "word is using shift"?
in the vigenere characters are shifted.
should we instead shift words (like the rules seems to say)?
or should we apply some compination of the real vig and word shifting?
_________________________
!

download KiXnet

Top
#123684 - 2004-07-25 02:46 AM Re: KiXgolf: Vigenere Cipher - Private coding
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
Loc: Boston, MA, USA
Where did you find "word is using shift" in the rules?

In the standard Vigenere cipher, you're using the ciphers that are shifted by one character when you go down the cipher tableu. This is illustrated in the rules. One of the required modifications is that this character shift is based on the position of the word to be encrypted inside it's sentence. Thus the first word's cipher tableau starts with
Code:

ABC...
BCD...
CDE...


In case of the second word, the shift would now be two characters, thus
Code:

ABCDEF...
CDEFGH...
EFGHIJ...


In effect each word inside a sentence to be encrypted is using it's own distinct cipher tableau.
_________________________
There are two types of vessels, submarines and targets.

Top
#123685 - 2004-07-25 03:33 AM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
Quote:

Thus, the first word is using a Caesar shift of one, the second word is using a Caesar shift of two, and so on.





that reads word is using shift.
you must remember that my english didn't come from mothers milk.

but, this thing now understood...
going forward.
got the idea already drafted but no full code yet.
_________________________
!

download KiXnet

Top
#123686 - 2004-07-25 04:09 AM Re: KiXgolf: Vigenere Cipher - Private coding
Sealeopard Offline
KiX Master
*****

Registered: 2001-04-25
Posts: 11162
Loc: Boston, MA, USA
Quote:

my english didn't come from mothers milk



I know, I believe it's vodka-infused, right? ;-)

I'm pretty sure, a couple of people spied on you already and are working on code as we speak :-) So, hurry up!
_________________________
There are two types of vessels, submarines and targets.

Top
#123687 - 2004-07-25 04:38 AM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
I know ppl did.
and the code already found on the board is half way there.
problem now is, how to make that word related shifting happen.

the boundaries of my head is again tested.
_________________________
!

download KiXnet

Top
#123688 - 2004-07-25 04:41 AM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
hmm... not sure of english but doesn't ":" mean end of sentence?
heh, should read somewhere the meaning of word "sentence"
_________________________
!

download KiXnet

Top
#123689 - 2004-07-25 04:43 AM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
also, I wonder why you didn't include any crypted texts to your example.
this way the working would have proved easier.
now I just need to code a script that does encrypt&decrypt the same way.
doesn't still mean it's correct...
_________________________
!

download KiXnet

Top
#123690 - 2004-07-25 06:03 AM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
k, I'm 90% sure I got the encryption right although validator says success 0%.
but that's purely because it does not test neither encryption nor decryption correctness.

with encryption only, the size is 591.

_________________________
!

download KiXnet

Top
#123691 - 2004-07-25 06:10 AM Re: KiXgolf: Vigenere Cipher - Private coding
Lonkero Administrator Offline
KiX Master Guru
*****

Registered: 2001-06-05
Posts: 22339
Loc: OK
hey, is the flaw the fact that you can end up with no small letters in your output even if the original text had them?
thus, using wrong decryption "character-set"
_________________________
!

download KiXnet

Top
Page 1 of 8 12345>Last »


Moderator:  Arend_, Allen, Jochen, Radimus, Glenn Barnas, ShaneEP, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 161 anonymous users online.
Newest Members
diefnet, Arogya, gkustra, emnipetro, Hirze
17644 Registered Users

Generated in 0.059 seconds in which 0.019 seconds were spent on a total of 14 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org