Difference between revisions of "Codebusters"

From Scioly.org
Jump to: navigation, search
(Added large equations warning)
m (Removed extra space at start of page.)
(18 intermediate revisions by 8 users not shown)
Line 5: Line 5:
 
|2018thread=[https://scioly.org/forums/viewtopic.php?f=264&t=11553 2018 (Trial)]
 
|2018thread=[https://scioly.org/forums/viewtopic.php?f=264&t=11553 2018 (Trial)]
 
|2019thread=[https://scioly.org/forums/viewtopic.php?f=284&t=12237 2019]
 
|2019thread=[https://scioly.org/forums/viewtopic.php?f=284&t=12237 2019]
 +
|2020thread=[https://scioly.org/forums/viewtopic.php?f=285&t=15384 2020]
 
|2019tests=2019
 
|2019tests=2019
 
|testsArchive=
 
|testsArchive=
 
|2019questions=[https://scioly.org/forums/viewtopic.php?f=297&t=12398 2019]
 
|2019questions=[https://scioly.org/forums/viewtopic.php?f=297&t=12398 2019]
 +
|2020questions=[https://scioly.org/forums/viewtopic.php?f=297&t=15736 2020]
 
|type=Nature Of Science
 
|type=Nature Of Science
 
|cat=Lab
 
|cat=Lab
|C Champion=[[Thomas Jefferson High School for Science and Technology]]
+
|1stCName=North Carolina School of Science and Mathematics
 +
|2ndCName=Brookwood High School
 +
|3rdCName=Northville Enloe High School
 +
|Website=https://www.soinc.org/codebusters-c
 
}}
 
}}
 +
[[Codebusters]] is an event in [[Division C]] for the [[2020]] season and was held as trial event at both the [[University of Wisconsin 2016|2016 National Tournament]] and the [[Colorado State University 2018| 2018 National Tournament]]. It was last held as an official event in [[2019]]. It is also being held as a trial event for [[Division B]] at the [[North Carolina State University 2020|2020 National Tournament]]. In this event, ''up to 3'' participants must decode encrypted messages, or they may be required to encode messages with certain advanced ciphers. Competitors are not allowed to bring any resources to this event, but can bring a 4 or 5 function calculator - '''no scientific or graphing calculators allowed.'''
  
[[Codebusters]] is an event in [[Division C]] for the [[2019]] season and was held as trial event at both the [[University of Wisconsin 2016|2016 National Tournament]] and the [[Colorado State University 2018| 2018 National Tournament]]. In this event, ''up to 3'' participants must decode encrypted messages, or they may be required to encode messages with certain advanced ciphers. Competitors are not allowed to bring any resources to this event, but can bring a 4 or 5 function calculator - '''no scientific or graphing calculators allowed.'''
+
==Test Format==
 +
 
 +
===Format and Scoring===
 +
Tests are composed of a variety of questions where teams will encrypt or decrypt various code types. The number of questions on a given test is variable, but tests often contain anywhere from 6-24 questions, depending on the difficulty of the questions. The first question of a test is timed, and a time bonus is given for the question based on how quickly it is completed. Points may be deducted from questions based on the number of mistakes found in the answer given. If the answer differs from the solution by only one or two letters, then no points are removed, despite the answer having errors. Each additional error after two errors will result in a deduction of 100 points. The number of points removed from a question through deductions will not exceed the value of the question (meaning that deductions will never result in a question score below 0).
 +
 
 +
====The First Question====
 +
The very first question is timed - when solved, a team member should signal the event supervisor that they have finished the question, such as raising their hand, shouting "bingo!", or another method determined by the supervisor before the event begins. The first question will be an Aristocrat with or without a hint. Teams will receive bonus points depending on their time, and they may make as many attempts as they want to break the code without any penalties. The timing bonus will be calculated from the start of the event until the question is answered successfully, or until 10 minutes have elapsed, and is calculated with the formula: 4*(600-number of '''seconds''' taken). Teams may still answer the question after 10 minutes; however, the timing bonus is 0. The first cryptogram may also be used as a tiebreaker. Solutions are given full points only if the solution is an exact match or differs by '''only''' one or two letters. Deductions for inconsistencies in the answer to the first question are treated the same as deductions for a non-timed question.
 +
 
 +
===Question Point Distribution===
 +
The amount of points each question is worth will be distributed by the following:
 +
*An easy question: 100-150 points
 +
*A medium question: 200-300 points
 +
*A hard question: 350-500 points
 +
*A very hard question: 550-700 points
  
==Test Description==
+
In the case of a tie, select questions predetermined by the event supervisor will serve as a tiebreaker. The tie is broken using the following criteria in this order: score, degree of correctness, and number attempted.
 +
 
 +
===Code types that may be used at the Invitational and Regional Competitions===
 +
*[[Codebusters#Atbash Cipher|Atbash Cipher]]
 +
*[[Codebusters#Caesar Cipher|Caesar Cipher (shift cipher)]]
 +
*[[Codebusters#Mono-alphabetic Substitution|Mono-alphabetic substitution]] (can use K1, K2, or random alphabets)
 +
**[[Codebusters#Messages with Spaces and a Hint|Aristocrats with a hint, spaces, and no spelling errors]] - messages with spaces included, and with a hint
 +
**[[Codebusters#Messages with Spaces|Aristocrats with no hint, spaces, and no spelling errors]] - messages with spaces included, but without a hint
 +
**[[Codebusters#Messages with Spaces and Spelling Errors|Aristocrats with a hint, spaces, and spelling errors]]- messages with spaces and hints, but including spelling/grammar errors
 +
**[[Codebusters#Messages with Spaces and Spelling Errors|Aristocrats with no hint, spaces, and spelling errors]]- messages with spaces and including spelling/grammar errors but no hints
 +
**[[Codebusters#Messages without Spaces|Patristocrats with a hint]] - messages with spaces removed, and with a hint
 +
**[[Codebusters#Messages without Spaces or Hints|Patristocrats without a hint]] - messages with spaces removed, but without a hint
 +
*[[Codebusters#Affine Cipher and Modular Arithmetic|Affine Cipher]] - '''encryption only'''
 +
*[[Codebusters#Vigenère Cipher|Vigenère Cipher]] - encryption/decryption only, not cryptanalysis
 +
*[[Codebusters#Baconian Cipher|Baconian cipher and its variants]]
 +
*[[Codebusters#Xenocrypt|Xenocrypt]] (no more than one)
 +
*[[Codebusters#Hill Cipher|Mathematical Cryptanalysis of the Hill Cipher]] - either producing a decryption matrix given a 2x2 encryption matrix or computing a decryption matrix given 4 plaintext-ciphertext letter pairs.
  
===Format and Scoring===
+
===Code types that may be used at the State and National Competitions===
 +
*All Invitational and Regional code types
 +
*[[Codebusters#Running Key Cipher|Running Key Cipher]]
 +
*[[Codebusters#Vigenère Cipher|Cryptanalysis of the Vigenère cipher with a 'crib' (a known plaintext attack)]]
 +
*[[Codebusters#RSA Cipher|RSA Cipher]]
 +
*[[Codebusters#Hill Cipher|The Hill Cipher]] - encrypting or decryption with a provided 2x2 or 3x3 matrix.
 +
*[[Codebusters#Xenocrypt|Xenocrypt]] - '''at least one''' cryptogram will be in spanish
 +
*[[Codebusters#Affine Cipher and Modular Arithmetic|Mathematical Cryptanalysis of the Affine Cipher]]
  
The very first cryptogram is timed - when solved, a team member should raise their hand/shout "bingo!"/etc to alert the supervisor. The first question will be an Aristocrat with or without a hint. Teams will receive bonus points depending on their time, but they may make as many attempts as they want to break the code without any penalties. The first cryptogram may also be used as a tiebreaker. The timing bonus will be calculated from the start of the event until the question is answered successfully, or until 10 minutes have elapsed. Teams may still answer the question after 10 minutes; however, the timing bonus is 0. The time bonus for the first question is 4*(600-number of '''seconds''' taken). Solutions are given full points only if the solution is an exact match or differs by '''only''' one or two letters. Each additional error after the first 2 will result in a deduction of 100 points. These deductions will not exceed the value of question (can not go below 0). Questions with answers as numbers, the answer is either correct or incorrect (no partial points).
+
==Code Types==
  
===Caesar Cipher===
+
===Atbash Cipher===
One example of a mono-alphabetic substitution is Caesar shift cipher, where each letter is replaced by one shifted by a certain amount. For example, the following table has each letter shifted three positions to the right.  
+
The Atbash Cipher is a variant of the affine cipher (see above) in which both a and b equal 25. This results in the alphabet essentially becoming a mirror (A corresponds to Z, B corresponds to Y, C corresponds to X, etc.).  
{|class="wikitable"
+
<div style="overflow:auto">
|+Caesar Shift Example Table
+
{| class="wikitable" style="margin-bottom: 0px"
 +
|+Atbash Cipher
 
!Original Alphabet
 
!Original Alphabet
 
|A
 
|A
Line 53: Line 96:
 
|Z
 
|Z
 
|-
 
|-
!Shifted Alphabet (to the right 3)
+
!Ciphertext Alphabet
|D
+
|Z
|E
+
|Y
|F
+
|X
|G
+
|W
|H
+
|V
 +
|U
 +
|T
 +
|S
 +
|R
 +
|Q
 +
|P
 +
|O
 +
|N
 +
|M
 +
|L
 +
|K
 +
|J
 
|I
 
|I
|J
+
|H
|K
+
|G
|L
+
|F
|M
+
|E
|N
+
|D
|O
+
|C
|P
+
|B
|Q
 
|R
 
|S
 
|T
 
|U
 
|V
 
|W
 
|X
 
|Y
 
|Z
 
 
|A
 
|A
|B
 
|C
 
 
|-
 
|-
 
|}
 
|}
 +
</div>
 +
 +
Following the affine cipher, the encryption formula would be:
 +
 +
[math]E(x) = (25x + 25) \mod 26[/math]
 +
 +
However, observing the mirror like alphabet yields a much simpler equation of:
 +
 +
[math]E(x) = D(x) = 25 - x[/math]
 +
 +
Since the alphabet is like a mirror, encryption is the same as decryption.
  
From this table, it is clear that each shifted letter is the same as the original letter three spaces from it (A becomes D, B becomes E, etc). Thus, a message like "Science Olympiad is cool" would become "Vflhqfh Robpsldg lv frro" using a Caesar shift of 3. The alphabet can be shifted any number of times. This type of cryptogram can be solved through brute force, by taking a section of the message and writing out all 26 possible shifts below it, upon which the message is easily revealed.
 
  
 
====Encryption Example====
 
====Encryption Example====
Encode "example" with a shift of 7.
+
Encode "encrypt" with the Atbash Cipher.
 
 
By shifting each letter 7 times, we can encrypt the text.
 
  
 
{|class="wikitable"
 
{|class="wikitable"
|+Example Encoding
+
!Plaintext
!Encryption Shift
+
|E
!Possible Plaintext
+
|N
 +
|C
 +
|R
 +
|Y
 +
|P
 +
|T
 
|-
 
|-
|0
+
!Numeric Component
|example
+
|4
 +
|13
 +
|2
 +
|17
 +
|24
 +
|15
 +
|19
 
|-
 
|-
 +
![math]25 - x[/math]
 +
|21
 +
|12
 +
|23
 +
|8
 
|1
 
|1
|fybnqmf
+
|10
|-
+
|6
|2
 
|gzcorng
 
|-
 
|3
 
|hadpsoh
 
|-
 
|4
 
|ibeqtpi
 
|-
 
|5
 
|jcfruqj
 
|-
 
|6
 
|kdgsvrk
 
|-
 
|7
 
|lehtwsl
 
 
|-
 
|-
 +
!Ciphertext
 +
|V
 +
|M
 +
|X
 +
|I
 +
|B
 +
|K
 +
|G
 
|}
 
|}
  
The encrypted text is '''lehtwsl'''.
+
The cipher text is "vmxibkg."
  
 
====Decryption Example====
 
====Decryption Example====
Decode "xhntqd".  
+
Decode "decrypt" with the Atbash Cipher.
  
We must test all possible shifts of our text to solve this prompt, since we do not know the shift. By repeatedly testing different shifts, we will eventually arrive at our answer.
+
{|class="wikitable"
 
+
!Plaintext
{|class="wikitable"
+
|Z
|+Example Decoding
+
|M
!Decryption Shift
+
|H
!Possible Plaintext
+
|D
 +
|V
 +
|I
 +
|-
 +
!Numeric Component
 +
|25
 +
|12
 +
|7
 +
|3
 +
|21
 +
|8
 
|-
 
|-
 +
![math]25 - x[/math]
 
|0
 
|0
|xhntqd
+
|13
|-
+
|18
|1
+
|22
|wgmspc
+
|4
|-
+
|17
|2
 
|vflrob
 
|-
 
|3
 
|uekqna
 
|-
 
|4
 
|tdjpmz
 
|-
 
|5
 
|scioly
 
 
|-
 
|-
 +
!Ciphertext
 +
|A
 +
|N
 +
|S
 +
|W
 +
|E
 +
|R
 
|}
 
|}
  
After shifting "xhntqd" five times, the plaintext is revealed to be '''scioly''', and no further shifts need to be tested.
+
The plaintext is "answer."
 
 
===Mono-alphabetic Substitution===
 
  
A mono-alphabetic substitution is one where the same plaintext letters are replaced by the same ciphertext letters. Since specific encryption/decryption methods are not mentioned in the rules, a variety of ways will be covered in the following section. Mono-alphabetic ciphers may contain spaces (Aristocrats) or may have spaces removed (Patristocrats). Mono-alphabetic ciphers may use K1,  K2, or random alphabets as defined by the [http://www.cryptogram.org/ ACA].
+
===Caesar Cipher===
====Solving a mono-alphabetic substitution cipher using patterns====
+
One example of a mono-alphabetic substitution is Caesar shift cipher, where each letter is replaced by one shifted by a certain amount. For example, the following table has each letter shifted three positions to the right.  
[[Image:Frequency.jpg|400px|thumb|Table of letter frequency in English.]]
+
<div style="overflow:auto">
This may be the most common way to solve a cipher on a Code Busters test, because the supervisor may not write that a Caesar cipher etc. was used to encrypt.
+
{| class="wikitable" style="margin-bottom: 0px"
 
+
|+Caesar Shift Example Table
First, find the corresponding letter for a few cipher letter by:
+
!Original Alphabet
#Look for words that are only one letter long. These will almost always be A or I, unless the cryptogram is a poem, in which case O may be used. I usually appears at the start of the sentence, while A is usually more common.
+
|A
#Look for repeated blocks of three. The block is often THE: THE is the most common english word, used almost twice as often as the second most common, BE.
+
|B
#Look for frequency of letters. The 12 most frequent letters in the English alphabet are ETAOIN SHRDLU, with E being the most common by a significant margin.
+
|C
#Look for contractions. If an apostrophe is seen in the ciphertext, it can be an easy way to start deciphering using the table below.
+
|D
#Look for double letters. They're often LL, followed in frequency by EE, SS, OO and TT.
+
|E
 
+
|F
Two clues may give different substitution, in which case experimenting may be helpful.
+
|G
 
+
|H
Then, substitute the known letters, and gradually decode more words using the word fragments. Starting with two or three-letter words are often easier, because of the limited possibilities.
+
|I
 
+
|J
{|class="wikitable"
+
|K
|+Contractions
+
|L
!Endings
+
|M
!Examples
+
|N
 +
|O
 +
|P
 +
|Q
 +
|R
 +
|S
 +
|T
 +
|U
 +
|V
 +
|W
 +
|X
 +
|Y
 +
|Z
 
|-
 
|-
|'T
+
!Shifted Alphabet (to the right 3)
|Won't, Don't, Isn't, Aren't, Weren't, Shouldn't, Couldn't, Didn't, Can't
+
|D
|-
+
|E
|'S
+
|F
|He's, She's, It's, Who's, There's, That's
+
|G
 +
|H
 +
|I
 +
|J
 +
|K
 +
|L
 +
|M
 +
|N
 +
|O
 +
|P
 +
|Q
 +
|R
 +
|S
 +
|T
 +
|U
 +
|V
 +
|W
 +
|X
 +
|Y
 +
|Z
 +
|A
 +
|B
 +
|C
 
|-
 
|-
|'D
+
|}
|I'd, He'd, She'd, We'd, They'd, You'd
+
</div>
|-
+
From this table, it is clear that each shifted letter is the same as the original letter three spaces from it (A becomes D, B becomes E, etc). Thus, a message like "Science Olympiad is cool" would become "Vflhqfh Robpsldg lv frro" using a Caesar shift of 3. The alphabet can be shifted any number of times. This type of cryptogram can be solved through brute force, by taking a section of the message and writing out all 26 possible shifts below it, upon which the message is easily revealed.
|'M
+
 
|I'm
+
====Encryption Example====
 +
Encode "example" with a shift of 7.
 +
 
 +
By shifting each letter 7 times, we can encrypt the text.
 +
 
 +
{|class="wikitable"
 +
|+Example Encoding
 +
!Encryption Shift
 +
!Possible Plaintext
 +
|-
 +
|0
 +
|example
 
|-
 
|-
|'RE
+
|1
|You're, They're, We're
+
|fybnqmf
 
|-
 
|-
|'VE
+
|2
|They've, You've, We've
+
|gzcorng
 
|-
 
|-
|'LL
+
|3
|I'll, He'll, She'll, We'll, They'll, It'll, Who'll
+
|hadpsoh
 
|-
 
|-
|}
+
|4
Common word patterns include
+
|ibeqtpi
#axx- all or too
+
|-
#abxcx- there (most common) where or these
+
|5
#xabx- that (most common) high or dead
+
|jcfruqj
#axbcx- which
+
|-
#xyaxby- people
+
|6
#xayybxx- success (abcddxxyxy- succeeded).
+
|kdgsvrk
Keep in mind less common words may occupy these frequencies. For example  xyaxby could be "indian."
+
|-
 +
|7
 +
|lehtwsl
 +
|-
 +
|}
  
====Messages with Spaces and a Hint====
+
The encrypted text is '''lehtwsl'''.
These cryptograms are similar to those published in 20th century newspapers. These are usually solved using patterns, as described above, with the hint providing additional information to assist the decryption.
 
  
====Messages with Spaces====
+
====Decryption Example====
These cryptograms are similar to NSA and diplomatic messages, and '''do not have a hint'''. These are usually solved using patterns, as described above.
+
Decode "xhntqd".  
  
====Messages with Spaces and Spelling Errors====
+
We must test all possible shifts of our text to solve this prompt, since we do not know the shift. By repeatedly testing different shifts, we will eventually arrive at our answer.
These cryptograms are similar to FBI and organized crime messages. These are often solved by patterns, with additional care:
 
 
 
* The letter frequencies likely do not change, and can be applied.
 
* THE and many of the most common words are seldom misspelled, unless intentionally. OF may be unintentionally misspelled as UV.
 
* Piecing together words with word fragments may be more difficult. Misspelled words often sound the same as the actual word, which can be used to check the decrypted message.
 
 
 
====Messages without Spaces====
 
These cryptograms are similar to NSA and espionage messages, and '''have a hint'''. An example is: "UVYNYGUSZYSBZBULAPIAZUACAZZAMLGFALPERAJZNYGUUAFBR". Students are told that the last word is TODAY, and the cipher begins with a three-letter word, followed by a four-letter word.
 
 
 
#Begin by writing in TODAY. UVYNYGUSZYSBZBULAPIAZUACAZZAMLGFALPERAJZNYGU'''TODAY'''. From this, we can see that U represents T, A represents O, F represents D, B represents A, and R represents Y.
 
#Replace the cipher text with the decrypted letters. '''T'''VYNYG'''T'''SZYSBZ'''AT'''L'''O'''PI'''O'''Z'''TO'''C'''O'''ZZ'''O'''MLG'''DO'''LPE'''YO'''JZNYG'''TTODAY'''
 
#The first word is a 3 letter word beginning with T, which we can guess decrypts to THE. Replace Vs with H and Y with E. '''THE'''N'''E'''G'''T'''SZ'''E'''S'''A'''Z'''AT'''L'''O'''PI'''O'''Z'''TO'''C'''O'''ZZ'''O'''MLG'''DO'''LPE'''YO'''JZN'''E'''G'''TTODAY'''
 
#In this cipher, we can see the phrase "'''TO'''C'''O'''ZZ'''O'''M". Because of the double Z in the middle, it can be inferred that this decrypts to TOMORROW. Replace Z with R, C with M, and M with W. '''THE'''N'''E'''G'''T'''S'''RE'''S'''ARAT'''L'''O'''PI'''ORTOMORROW'''LG'''DO'''LPE'''YO'''J'''R'''N'''E'''G'''TTODAY'''.
 
#We can see the letters '''YO'''J'''R'''. This is probably YOUR. Replace J with U. '''THE'''N'''E'''G'''T'''S'''RE'''S'''ARAT'''L'''O'''PI'''ORTOMORROW'''LG'''DO'''LPE'''YOUR'''N'''E'''G'''TTODAY'''.
 
#The letters LG after the noun TOMORROW likely decrypt to IS. Replace L with I and G with S. '''THE'''N'''EST'''S'''RE'''S'''ARATIO'''PI'''ORTOMORROWISDOI'''PE'''YOUR'''N'''ESTTODAY'''.
 
#N'''EST''' probably decrypts to B, as that is the only word that makes sense in this context. '''THEBEST'''S'''RE'''S'''ARATIO'''PI'''ORTOMORROWISDOI'''PE'''YOURBESTTODAY'''.
 
#At this point, the cipher is able to be solved using common sense. S'''RE'''S'''ARATIO'''P likely means PREPARATION. I'''OR''' probably means FOR. DOI'''PE''' probably means DOING. Thus, the message is THE BEST PREPARATION FOR TOMORROW IS DOING YOUR BEST TODAY.
 
 
 
====Messages without Spaces or Hints====
 
These cryptograms are extremely difficult and may not be tested very frequently. In the event that a test does contain one, the best method is using the patterns listed above, especially finding repeated three letter "phrases" or double letters.
 
 
 
===Xenocrypt===
 
At the invitational/Regional level, '''one''' cryptogram may be in Spanish as a challenge. At the state level, there will be '''at least one'''. It may be helpful if one of the partners is fluent in or has a few years of knowledge in Spanish.
 
 
 
For Spanish cryptograms, n and ñ are treated as different letters. However, letters with accents are treated the same as without (a and á are the same). This means that, when working with cryptograms, accent marks do not factor in. Also, ch, ll, and rr are NOT considered distinct letters. Thus, "churro" would have 6 letters: c-h-u-r-r-o. The Spanish alphabet used for cryptograms is as follows:
 
  
 
{|class="wikitable"
 
{|class="wikitable"
|+Spanish Alphabet
+
|+Example Decoding
 +
!Decryption Shift
 +
!Possible Plaintext
 +
|-
 +
|0
 +
|xhntqd
 +
|-
 +
|1
 +
|wgmspc
 +
|-
 +
|2
 +
|vflrob
 +
|-
 +
|3
 +
|uekqna
 
|-
 
|-
|A
+
|4
|B
+
|tdjpmz
|C
+
|-
|D
+
|5
|E
+
|scioly
|F
 
|G
 
|H
 
|I
 
|J
 
|K
 
|L
 
|M
 
|N
 
 
|O
 
|P
 
|Q
 
|R
 
|S
 
|T
 
|U
 
|V
 
|W
 
|X
 
|Y
 
|Z
 
 
|-
 
|-
 
|}
 
|}
  
The frequency table of Spanish letters is as follows, from most to least frequent:
+
After shifting "xhntqd" five times, the plaintext is revealed to be '''scioly''', and no further shifts need to be tested.
 +
 
 +
===Mono-alphabetic Substitution===
  
{|class="wikitable"
+
A mono-alphabetic substitution is one where the same plaintext letters are replaced by the same ciphertext letters. Since specific encryption/decryption methods are not mentioned in the rules, a variety of ways will be covered in the following section. Mono-alphabetic ciphers may contain spaces (Aristocrats) or may have spaces removed (Patristocrats). Mono-alphabetic ciphers may use K1,  K2, or random alphabets as defined by the [http://www.cryptogram.org/ ACA].
|+Spanish Letter Frequency Table
+
====Solving a mono-alphabetic substitution cipher using patterns====
|-
+
[[Image:Frequency.jpg|400px|thumb|Table of letter frequency in English.]]
!Letter
+
This may be the most common way to solve a cipher on a Code Busters test, because the supervisor may not write that a Caesar cipher etc. was used to encrypt.
|E
+
 
|A
+
First, find the corresponding letter for a few cipher letter by:
|O
+
#Look for words that are only one letter long. These will almost always be A or I, unless the cryptogram is a poem, in which case O may be used. I usually appears at the start of the sentence, while A is usually more common.
|S
+
#Look for repeated blocks of three. The block is often THE: THE is the most common english word, used almost twice as often as the second most common, BE.
|N
+
#Look for frequency of letters. The 12 most frequent letters in the English alphabet are ETAOIN SHRDLU, with E being the most common by a significant margin.
|R
+
#Look for contractions. If an apostrophe is seen in the ciphertext, it can be an easy way to start deciphering using the table below.
|I
+
#Look for double letters. They're often LL, followed in frequency by EE, SS, OO and TT.
|L
+
 
|D
+
Two clues may give different substitution, in which case experimenting may be helpful.
|T
+
 
|U
+
Then, substitute the known letters, and gradually decode more words using the word fragments. Starting with two or three-letter words are often easier, because of the limited possibilities.
|C
+
 
|M
+
{|class="wikitable"
|P
+
|+Contractions
 +
!Endings
 +
!Examples
 +
|-
 +
|'T
 +
|Won't, Don't, Isn't, Aren't, Weren't, Shouldn't, Couldn't, Didn't, Can't
 
|-
 
|-
!Frequency
+
|'S
|14.08%
+
|He's, She's, It's, Who's, There's, That's
|12.16%
 
|9.20%
 
|7.20%
 
|6.83%
 
|6.41%
 
|5.98%
 
|5.24%
 
|4.67%
 
|4.60%
 
|4.69%
 
|3.87%
 
|3.08%
 
|2.89%
 
 
|-
 
|-
!Letter
+
|'D
|B
+
|I'd, He'd, She'd, We'd, They'd, You'd
|H
 
|Q
 
|Y
 
|V
 
|G
 
|F
 
|J
 
|Z
 
 
|X
 
|K
 
|W
 
 
|-
 
|-
!Frequency
+
|'M
|1.49%
+
|I'm
|1.18%
+
|-
|1.11%
+
|'RE
|1.09%
+
|You're, They're, We're
|1.05%
+
|-
|1.00%
+
|'VE
|0.69%
+
|They've, You've, We've
|0.52%
+
|-
|0.47%
+
|'LL
|0.17%
+
|I'll, He'll, She'll, We'll, They'll, It'll, Who'll
|0.14%
 
|0.11%
 
|0.04%
 
 
|-
 
|-
 
|}
 
|}
 +
Common word patterns include
 +
#axx- all or too
 +
#abxcx- there (most common) where or these
 +
#xabx- that (most common) high or dead
 +
#axbcx- which
 +
#xyaxby- people
 +
#xayybxx- success (abcddxxyxy- succeeded).
 +
Keep in mind less common words may occupy these frequencies. For example  xyaxby could be "indian."
  
Spanish cryptograms are often solved with patterns as well, with a few differences:
+
====Messages with Spaces and a Hint====
* Look for the two most common letters, instead of the most common letters: E and A have relatively close frequency, and are much higher than the rest.
+
These cryptograms are similar to those published in 20th century newspapers. These are usually solved using patterns, as described above, with the hint providing additional information to assist the decryption.
* The most common spanish words are DE, LA, QUE, EL, EN. Since Spanish has far more two-letter words, it is helpful to decrypt them, using the placement of the letter E. QUE is the most common three-letter word, almost twice as common as the next ones.
 
* Decrypting words using word fragments are much more difficult for teams without fluency in Spanish.
 
  
===Affine Cipher and Modular Arithmetic===
+
====Messages with Spaces====
 +
These cryptograms are similar to NSA and diplomatic messages, and '''do not have a hint'''. These are usually solved using patterns, as described above.
  
The Affine cipher uses an alphabet of size [math]m[/math] with keys [math]a[/math] and [math]b[/math] such that [math]a,b[/math] are integers, and [math]a[/math] and [math]m[/math] are coprime (there is no positive divisor for both of them besides 1). Assuming the alphabet is of size 26, [math]a[/math] can be 1, 3, 5, 7, 9, 11 ,15, 17, 19, 21, 23 and 25. Each letter in the alphabet corresponds to a number from [math]0[/math] to [math]m-1[/math]. The most common correspondence for the English alphabet is shown below.
+
====Messages with Spaces and Spelling Errors====
 +
These cryptograms are similar to FBI and organized crime messages. These are often solved by patterns, with additional care:
 +
 
 +
* The letter frequencies likely do not change, and can be applied.
 +
* THE and many of the most common words are seldom misspelled, unless intentionally. OF may be unintentionally misspelled as UV.
 +
* Piecing together words with word fragments may be more difficult. Misspelled words often sound the same as the actual word, which can be used to check the decrypted message.
 +
 
 +
====Messages without Spaces====
 +
These cryptograms are similar to NSA and espionage messages, and '''have a hint'''. An example is: "UVYNYGUSZYSBZBULAPIAZUACAZZAMLGFALPERAJZNYGUUAFBR". Students are told that the last word is TODAY, and the cipher begins with a three-letter word, followed by a four-letter word.
 +
 
 +
#Begin by writing in TODAY. UVYNYGUSZYSBZBULAPIAZUACAZZAMLGFALPERAJZNYGU'''TODAY'''. From this, we can see that U represents T, A represents O, F represents D, B represents A, and R represents Y.
 +
#Replace the cipher text with the decrypted letters. '''T'''VYNYG'''T'''SZYSBZ'''AT'''L'''O'''PI'''O'''Z'''TO'''C'''O'''ZZ'''O'''MLG'''DO'''LPE'''YO'''JZNYG'''TTODAY'''
 +
#The first word is a 3 letter word beginning with T, which we can guess decrypts to THE. Replace Vs with H and Y with E. '''THE'''N'''E'''G'''T'''SZ'''E'''S'''A'''Z'''AT'''L'''O'''PI'''O'''Z'''TO'''C'''O'''ZZ'''O'''MLG'''DO'''LPE'''YO'''JZN'''E'''G'''TTODAY'''
 +
#In this cipher, we can see the phrase "'''TO'''C'''O'''ZZ'''O'''M". Because of the double Z in the middle, it can be inferred that this decrypts to TOMORROW. Replace Z with R, C with M, and M with W. '''THE'''N'''E'''G'''T'''S'''RE'''S'''ARAT'''L'''O'''PI'''ORTOMORROW'''LG'''DO'''LPE'''YO'''J'''R'''N'''E'''G'''TTODAY'''.
 +
#We can see the letters '''YO'''J'''R'''. This is probably YOUR. Replace J with U. '''THE'''N'''E'''G'''T'''S'''RE'''S'''ARAT'''L'''O'''PI'''ORTOMORROW'''LG'''DO'''LPE'''YOUR'''N'''E'''G'''TTODAY'''.
 +
#The letters LG after the noun TOMORROW likely decrypt to IS. Replace L with I and G with S. '''THE'''N'''EST'''S'''RE'''S'''ARATIO'''PI'''ORTOMORROWISDOI'''PE'''YOUR'''N'''ESTTODAY'''.
 +
#N'''EST''' probably decrypts to B, as that is the only word that makes sense in this context. '''THEBEST'''S'''RE'''S'''ARATIO'''PI'''ORTOMORROWISDOI'''PE'''YOURBESTTODAY'''.
 +
#At this point, the cipher is able to be solved using common sense. S'''RE'''S'''ARATIO'''P likely means PREPARATION. I'''OR''' probably means FOR. DOI'''PE''' probably means DOING. Thus, the message is THE BEST PREPARATION FOR TOMORROW IS DOING YOUR BEST TODAY.
 +
 
 +
====Messages without Spaces or Hints====
 +
These cryptograms are extremely difficult and may not be tested very frequently. In the event that a test does contain one, the best method is using the patterns listed above, especially finding repeated three letter "phrases" or double letters.
 +
 
 +
===Affine Cipher and Modular Arithmetic===
 +
 
 +
The Affine cipher uses an alphabet of size [math]m[/math] with keys [math]a[/math] and [math]b[/math] such that [math]a,b[/math] are integers, and [math]a[/math] and [math]m[/math] are coprime (there is no positive divisor for both of them besides 1). Assuming the alphabet is of size 26, [math]a[/math] can be 1, 3, 5, 7, 9, 11 ,15, 17, 19, 21, 23 and 25. Each letter in the alphabet corresponds to a number from [math]0[/math] to [math]m-1[/math]. The most common correspondence for the English alphabet is shown below.
  
<div align="center">
+
<div align="center" style="overflow:auto">
{|class="wikitable"
+
{| class="wikitable" style="margin-bottom: 0px"
 
|+Alphabet
 
|+Alphabet
 
|-
 
|-
Line 504: Line 592:
 
In this case, [math]a^{-1}[/math] is the multiplicative inverse of [math]a[/math] modulo [math]m[/math] ([math]aa^{-1}\bmod m=1[/math]). Because there are only 26 values, one can brute force it to find the value of [math]t[/math] where [math]ta \bmod m=1[/math]. [math]t[/math] represents [math]a^{-1}[/math].  
 
In this case, [math]a^{-1}[/math] is the multiplicative inverse of [math]a[/math] modulo [math]m[/math] ([math]aa^{-1}\bmod m=1[/math]). Because there are only 26 values, one can brute force it to find the value of [math]t[/math] where [math]ta \bmod m=1[/math]. [math]t[/math] represents [math]a^{-1}[/math].  
  
<div align="center">
+
<div align="center" style="overflow:auto">
{|class="wikitable"
+
{| class="wikitable" style="margin-bottom: 0px"
 
|+Brute Force Table
 
|+Brute Force Table
 
|-
 
|-
Line 736: Line 824:
 
</div>
 
</div>
  
===Atbash Cipher===
 
The Atbash Cipher is a variant of the affine cipher (see above) in which both a and b equal 25. This results in the alphabet essentially becoming a mirror (A corresponds to Z, B corresponds to Y, C corresponds to X, etc.).  Following the affine cipher, the encryption formula would be:
 
  
[math]E(x) = (25x + 25)mod 26[/math]
 
  
However, observing the mirror like alphabet yields a much simpler equation of:
+
===Vigenère Cipher===
  
[math]E(x) = D(x) = 25 - x[/math]
+
The Vigenère cipher, invented by Blaise de Vigenère in the 16th century, is a polyalphabetic cipher. This means that each letter is shifted by a different amount. According to the rules, students will probably be asked to encrypt rather than decrypt Vigenère ciphers. Encrypting is a fairly straightforward procedure.
  
Since the alphabet is like a mirror, encryption is the same as decryption.
+
====Encryption/Decryption With a Table====
===Hill Cipher===
+
First, write out the message with the key under it, repeating the key as many times as necessary. An example is shown.
 
 
'''''NOTE:''' These cryptograms will be matrix based, and only use 2x2 or 3x3 matrices.''
 
 
 
The alphabet for the Hill cipher has corresponding numbers as follows: 
 
  
 
<div align="center">
 
<div align="center">
 
{|class="wikitable"
 
{|class="wikitable"
|+Hill Cipher Alphabet
+
|+Message with Key
 
|-
 
|-
!Letter
+
!Message
|A
+
|S
|B
+
|C
 +
|I
 +
|E
 +
|N
 
|C
 
|C
|D
 
 
|E
 
|E
|F
+
|O
|G
 
|H
 
|I
 
|J
 
|K
 
 
|L
 
|L
 +
|Y
 
|M
 
|M
|N
 
|O
 
 
|P
 
|P
|Q
+
|I
|R
+
|A
 +
|D
 +
|I
 
|S
 
|S
|T
+
|C
|U
+
|O
|V
+
|O
|W
+
|L
|X
 
|Y
 
|Z
 
 
|-
 
|-
!Number
+
!Key
|0
+
|S
|1
+
|C
|2
+
|I
|3
+
|O
|4
+
|L
|5
+
|Y
|6
+
|S
|7
+
|C
|8
+
|I
|9
+
|O
|10
+
|L
|11
+
|Y
|12
+
|S
|13
+
|C
|14
+
|I
|15
+
|O
|16
+
|L
|17
+
|Y
|18
+
|S
|19
+
|C
|20
+
|I
|21
 
|22
 
|23
 
|24
 
|25
 
 
|-
 
|-
 
|}
 
|}
 
</div>
 
</div>
Begin by picking a key matrix of either 2x2 or 3x3. These could be a 4 letter word or three 3 letter words. For this example, the key will be WIKI (2x2 matrix). Then, break the message into groups of two. This example will use the message SCIENCE OLYMPIAD, which would be split up into SC IE NC EO LY MP IA D'''Z'''. Notice that a '''Z''' is added in order to make the last group a group of two. Write the message and the key as matrices.
+
Then, take out the alphabet square, as shown below. This will typically be provided on the test.
 +
 
 +
[[File:vig_table.png|thumb|500px|center|Vigenère Alphabet Table]]
 +
 
 +
Using the alphabet square, encode the plaintext. The first message letter is S and the first key letter is S, therefore, look at the table to see where row S and column S intersect. It is clear that they intersect at K, so write down K as the first letter of the ciphertext. Repeat this with the rest of the message. Thus, the encrypted text is "KEQSYAW QTMXNACL WD AGQT"
  
<div align="center">
+
If the key and ciphertext are both given, decoding is also possible. This is done by taking a letter of the '''key''' and finding its '''row''', finding the corresponding letter of '''ciphertext''' in that row, and seeing what column that letter falls in. The letter in the column is the letter of the plaintext. In the previous example, the first letter is decoded by going to row S and finding K, which is located in column S. Thus, the plaintext letter is S.
[math]
+
 
\begin{pmatrix}
+
====Encryption/Decryption Without a Table====
W & I \\
+
Tables are typically given on the test, but in the event they are not, the following strategy may be more helpful.
K & I
+
 
\end{pmatrix}*\begin{pmatrix}
+
Remember or recreate the correspondence between letter and number like in Affine and Hill Cipher, with A being 0 and Z being 25. Then, for each letter, convert the plain text and key to a sequence of numbers, and add the numbers modulo 26. Then, convert the number back to letter.
S \\
 
C
 
\end{pmatrix}=\begin{pmatrix}
 
22 & 8 \\
 
10 & 8
 
\end{pmatrix}*\begin{pmatrix}
 
18 \\
 
2
 
\end{pmatrix}=\begin{pmatrix}
 
412 \\
 
196
 
\end{pmatrix}\bmod 26=\begin{pmatrix}
 
22 \\
 
14
 
\end{pmatrix}=\begin{pmatrix}
 
W \\
 
O
 
\end{pmatrix}[/math]
 
</div>
 
  
In the second step of the above equation, the matrices are multiplied. Although it may seem complicated, matrix multiplication is fairly straightforward.
+
For example, if we encode the message "SCIENCEOLYMPIADISCOOL" using the key SCIOLY, we get
<div align="center">
 
[math]\begin{pmatrix}
 
A & B \\
 
C & D
 
\end{pmatrix}*\begin{pmatrix}
 
E \\
 
F
 
\end{pmatrix}[/math]
 
</div>
 
  
The matrices are multiplied as follows: [math]A[/math] and [math]E[/math] are multiplied, then added to the product of [math]B[/math] and [math]F[/math]. [math]C[/math] and [math]E[/math] are multiplied and added to the product of [math]D[/math] and [math]F[/math]. Thus, the product of the matrices is:
+
[[Image:VigenereExample.png|500px|center]]
<div align="center">
 
[math]\begin{pmatrix}
 
AE + BF \\
 
CE + DF
 
\end{pmatrix}[/math]
 
</div>
 
  
Matrix multiplication for 3x3 matrices is very similar.
+
To decode a message using this method, subtract instead of add the key's corresponding number: The cipher text K with the corresponding key letter S gives plain text [math]10-18=-8\equiv18\pmod{26}\to \text{S}[/math].
<div align="center">
 
[math]\begin{pmatrix}
 
A & B & C \\
 
D & E & F \\
 
G & H & I \\
 
\end{pmatrix}*\begin{pmatrix}
 
J & K & L \\
 
M & N & O \\
 
P & Q & R \\
 
\end{pmatrix}[/math]
 
</div>
 
Just like in a 2x2 matrix, the row of the first matrix is multiplied by the column of the second matrix, giving the following product.
 
  
<div align="center">
+
===Baconian Cipher===
[math]\begin{pmatrix}
+
The Baconian cipher replaces each letter of the plaintext with a 5 letter combination of 'A' and 'B'. This replacement is a binary form of encoding, in which 'A' may be considered as 0 and 'B' as 1. One variant of the Baconian Cipher uses a 24 letter alphabet with the letters 'I' and 'J' having the same code, as well as 'U' and 'V'.  
AJ+BM+CP & AK+BN+CQ & AL+BO+CR \\
+
<div style="overflow:auto">
DJ+EM+FP & DK+EN+FQ & DL+EO+FR \\
+
{| class="wikitable" style="margin-bottom: 0px"
GJ+HM+IP & GK+HN+IQ & GL+HO+IR \\
+
|+Baconian Alphabet (24-Letter Variant)
\end{pmatrix}[/math]
+
|-
</div>
+
!Letter
It is important to note that in order to multiply matrices, the number of columns in the first matrix MUST equal the number of rows in the second matrix. The size of the product matrix is the number of rows in the first matrix x the number of columns in the second matrix.  
+
|A
 
+
|B
The "mod" operation is also fairly straightforward. Essentially, it finds the remainder after dividing. For example, [math]153 \bmod 26 [/math] is equal to the remainder of [math]153 / 26[/math], which is 23. On a scientific calculator, this is found by dividing the two numbers, subtracting the integer value from the answer, and multiplying the decimals by the number after "mod" (in this case, 26). Therefore, the process would be:
+
|C
 
+
|D
<div align="center">
+
|E
[math]153/26=5.884615385[/math]
+
|F
</div>
+
|G
<div align="center">
+
|H
[math]5.884615385-5=0.884615385[/math]
+
|style="background: #FFFF00;"|I
</div>
+
|style="background: #FFFF00;"|J
<div align="center">
+
|K
[math]0.884615385*26=23[/math]
+
|L
</div>
+
|M
 
+
|N
The rest of the encoding of the message is shown below.
+
|O
<div align="center">
+
|P
[math]
+
|Q
\begin{pmatrix}
+
|R
W & I \\
+
|S
K & I
+
|T
\end{pmatrix}*\begin{pmatrix}
+
|style="background: #FFFF00;"|U
S \\
+
|style="background: #FFFF00;"|V
C
+
|W
\end{pmatrix}=\begin{pmatrix}
+
|X
22 & 8 \\
+
|Y
10 & 8
+
|Z
\end{pmatrix}*\begin{pmatrix}
+
|-
18 \\
+
!Code
2
+
|aaaaa
\end{pmatrix}=\begin{pmatrix}
+
|aaaab
412 \\
+
|aaaba
196
+
|aaabb
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|aabaa
22 \\
+
|aabab
14
+
|aabba
\end{pmatrix}=\begin{pmatrix}
+
|aabbb
W \\
+
|style="background: #FFFF00;"|abaaa
O
+
|style="background: #FFFF00;"|abaaa
\end{pmatrix}[/math]
+
|abaab
</div>
+
|ababa
 
+
|ababb
<div align="center">
+
|abbaa
[math]
+
|abbab
\begin{pmatrix}
+
|abbba
W & I \\
+
|abbbb
K & I
+
|baaaa
\end{pmatrix}*\begin{pmatrix}
+
|baaab
I \\
+
|baaba
E
+
|style="background: #FFFF00;"|baabb
\end{pmatrix}=\begin{pmatrix}
+
|style="background: #FFFF00;"|baabb
22 & 8 \\
+
|babaa
10 & 8
+
|babab
\end{pmatrix}*\begin{pmatrix}
+
|babba
8 \\
+
|babbb
4
+
|-
\end{pmatrix}=\begin{pmatrix}
+
!Binary
208 \\
+
|00000
112
+
|00001
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|00010
0 \\
+
|00011
8
+
|00100
\end{pmatrix}=\begin{pmatrix}
+
|00101
A \\
+
|00110
I
+
|00111
\end{pmatrix}[/math]
+
|style="background: #FFFF00;"|01000
 +
|style="background: #FFFF00;"|01000
 +
|01001
 +
|01010
 +
|01011
 +
|01100
 +
|01101
 +
|01110
 +
|01111
 +
|10000
 +
|10001
 +
|10010
 +
|style="background: #FFFF00;"|10011
 +
|style="background: #FFFF00;"|10011
 +
|10100
 +
|10101
 +
|10110
 +
|10111
 +
|-
 +
|}
 
</div>
 
</div>
 
+
Another variant of this cipher uses a unique code for each letter (26 letter alphabet). However, in a [https://www.soinc.org/what-type-baconian-cipher-being-tested-one-which-v-and-j-do-not-have-unique-code-or-one-where-all rule clarification], only the 24 letter variation is to be used on Codebusters tests for the 2019 season.
<div align="center">
+
<div style="overflow: auto">
[math]
+
{| class="wikitable" style="margin-bottom: 0px"
\begin{pmatrix}
+
|+Baconian Alphabet (26-Letter Variant)
W & I \\
+
|-
K & I
+
!Letter
\end{pmatrix}*\begin{pmatrix}
+
|A
N \\
+
|B
C
+
|C
\end{pmatrix}=\begin{pmatrix}
+
|D
22 & 8 \\
+
|E
10 & 8
+
|F
\end{pmatrix}*\begin{pmatrix}
+
|G
13 \\
+
|H
2
+
|I
\end{pmatrix}=\begin{pmatrix}
+
|J
302 \\
+
|K
146
+
|L
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|M
16 \\
+
|N
16
+
|O
\end{pmatrix}=\begin{pmatrix}
+
|P
Q \\
+
|Q
Q
+
|R
\end{pmatrix}[/math]
+
|S
</div>
+
|T
<div align="center">
+
|U
[math]
+
|V
\begin{pmatrix}
+
|W
W & I \\
+
|X
K & I
+
|Y
\end{pmatrix}*\begin{pmatrix}
+
|Z
E \\
+
|-
O
+
!Code
\end{pmatrix}=\begin{pmatrix}
+
|aaaaa
22 & 8 \\
+
|aaaab
10 & 8
+
|aaaba
\end{pmatrix}*\begin{pmatrix}
+
|aaabb
4 \\
+
|aabaa
14
+
|aabab
\end{pmatrix}=\begin{pmatrix}
+
|aabba
200 \\
+
|aabbb
152
+
|abaaa
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|abaab
18 \\
+
|ababa
22
+
|ababb
\end{pmatrix}=\begin{pmatrix}
+
|abbaa
S \\
+
|abbab
W
+
|abbba
\end{pmatrix}[/math]
+
|abbbb
</div>
+
|baaaa
<div align="center">
+
|baaab
[math]
+
|baaba
\begin{pmatrix}
+
|baabb
W & I \\
+
|babaa
K & I
+
|babab
\end{pmatrix}*\begin{pmatrix}
+
|babba
L \\
+
|babbb
Y
+
|bbaaa
\end{pmatrix}=\begin{pmatrix}
+
|bbaab
22 & 8 \\
+
|-
10 & 8
+
!Binary
\end{pmatrix}*\begin{pmatrix}
+
|00000
11 \\
+
|00001
24
+
|00010
\end{pmatrix}=\begin{pmatrix}
+
|00011
434 \\
+
|00100
302
+
|00101
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|00110
18 \\
+
|00111
16
+
|01000
\end{pmatrix}=\begin{pmatrix}
+
|01001
S \\
+
|01010
Q
+
|01011
\end{pmatrix}[/math]
+
|01100
 +
|01101
 +
|01110
 +
|01111
 +
|10000
 +
|10001
 +
|10010
 +
|10011
 +
|10100
 +
|10101
 +
|10110
 +
|10111
 +
|11000
 +
|11001
 +
|-
 +
|}
 
</div>
 
</div>
<div align="center">
+
Standard numbering systems use a base 10 method of counting (ones place, tens place, hundreds place, etc). What this means is that normally for example 24 = (2*10 + 4*1). The Baconian Cipher uses a base 2 system. The following is an example of base 2 converted to standard base 10: 01001 (base 2) = (0*16 + 1*8 + 0*4 + 0*2 + 1*1) = (1*8 + 1*1) = 9 (base 10). As seen in the chart above, 01001 corresponds to J, which is the 9th letter in the alphabet (assuming A = 0). When the first variant is shown, the numbering system will be off by 1 from J to U and off by 2 from V to Z. For example, 10100 = W, even though 10100 = 20 (base 10) which corresponds to U on the alphabet chart when A = 0.
[math]
+
 
\begin{pmatrix}
+
When solving a question encoded with the Baconian Cipher, it is very likely that they won't explicitly give you "A" and "B" to use to find the corresponding letters. Most of the time, they'll have certain symbols or letters that are meant to represent "A" and "B". One example of this would be using all of of the even letters in the alphabet to represent "A" while all the odd letters represent "B". There are many different variants of this, including symbols on a keyboard and vowel/consonants. To solve a Baconian, try to group the different symbols/letters into two groups based on their properties, and assign one group "A" and the other group "B". If it doesn't work the first time, then switch the groups so that the previous "A" group is now the "B" group. If even then it doesn't seem to be working, then start over again and find a different characteristic to base the groups off of. For this reason, the Baconian Cipher can take longer than some of the other ciphers.
W & I \\
+
 
K & I
+
===Xenocrypt===
\end{pmatrix}*\begin{pmatrix}
+
At the invitational/Regional level, '''one''' cryptogram may be in Spanish as a challenge. At the state level, there will be '''at least one'''. It may be helpful if one of the partners is fluent in or has a few years of knowledge in Spanish.
M \\
+
 
P
+
For Spanish cryptograms, n and ñ are treated as different letters. However, letters with accents are treated the same as without (a and á are the same). This means that, when working with cryptograms, accent marks do not factor in. Also, ch, ll, and rr are NOT considered distinct letters. Thus, "churro" would have 6 letters: c-h-u-r-r-o. The Spanish alphabet used for cryptograms is as follows:
\end{pmatrix}=\begin{pmatrix}
+
 
22 & 8 \\
+
{|class="wikitable"
10 & 8
+
|+Spanish Alphabet
\end{pmatrix}*\begin{pmatrix}
+
|-
12 \\
+
|A
15
+
|B
\end{pmatrix}=\begin{pmatrix}
+
|C
384 \\
+
|D
240
+
|E
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|F
20 \\
+
|G
6
+
|H
\end{pmatrix}=\begin{pmatrix}
+
|I
U \\
+
|J
G
+
|K
\end{pmatrix}[/math]
+
|L
</div>
+
|M
<div align="center">
+
|N
[math]
+
\begin{pmatrix}
+
|O
W & I \\
+
|P
K & I
+
|Q
\end{pmatrix}*\begin{pmatrix}
+
|R
I \\
+
|S
A
+
|T
\end{pmatrix}=\begin{pmatrix}
+
|U
22 & 8 \\
+
|V
10 & 8
+
|W
\end{pmatrix}*\begin{pmatrix}
+
|X
8 \\
+
|Y
0
+
|Z
\end{pmatrix}=\begin{pmatrix}
+
|-
176 \\
+
|}
80
+
 
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
The frequency table of Spanish letters is as follows, from most to least frequent:
20 \\
+
 
2
+
<div style="overflow:auto">
\end{pmatrix}=\begin{pmatrix}
+
{| class="wikitable" style="margin-bottom: 0px"
U \\
+
|+Spanish Letter Frequency Table
C
+
|-
\end{pmatrix}[/math]
+
!Letter
</div>
+
|E
<div align="center">
+
|A
[math]
+
|O
\begin{pmatrix}
+
|S
W & I \\
+
|N
K & I
+
|R
\end{pmatrix}*\begin{pmatrix}
+
|I
D \\
+
|L
Z
+
|U
\end{pmatrix}=\begin{pmatrix}
+
|D
22 & 8 \\
+
|T
10 & 8
+
|C
\end{pmatrix}*\begin{pmatrix}
+
|M
3 \\
+
|P
25
+
|-
\end{pmatrix}=\begin{pmatrix}
+
!Frequency
226 \\
+
|14.08%
230
+
|12.16%
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|9.20%
18 \\
+
|7.20%
22
+
|6.83%
\end{pmatrix}=\begin{pmatrix}
+
|6.41%
S \\
+
|5.98%
W
+
|5.24%
\end{pmatrix}[/math]
+
|4.69%
</div>
+
|4.67%
 
+
|4.60%
The encoded message is WOAIQQSWSQUGUCSW.
+
|3.87%
 
+
|3.08%
3x3 matrix encryption works in the same way. This example will encrypt "EDIT THE WIKI" using the key "BEE FLY BUG". First, split up the plaintext into groups of three, which becomes EDI TTH EWI KIZ. Once again, the last group has a Z added to make it a group of three.  
+
|2.89%
 
+
|-
<div align="center">
+
!Letter
[math]
+
|B
\begin{pmatrix}
+
|H
B & E & E \\
+
|Q
F & L & Y \\
+
|Y
B & U & G
+
|V
\end{pmatrix}*\begin{pmatrix}
+
|G
E \\
+
|F
D \\
+
|J
I \\
+
|Z
\end{pmatrix}=\begin{pmatrix}
+
1 & 4 & 4 \\
+
|X
5 & 11 & 24 \\
+
|K
1 & 20 & 6
+
|W
\end{pmatrix}*\begin{pmatrix}
+
|-
4 \\
+
!Frequency
3 \\
+
|1.49%
8
+
|1.18%
\end{pmatrix}=\begin{pmatrix}
+
|1.11%
48 \\
+
|1.09%
245 \\
+
|1.05%
112
+
|1.00%
\end{pmatrix}\bmod 26=\begin{pmatrix}
+
|0.69%
22 \\
+
|0.52%
11 \\
+
|0.47%
8
+
|0.17%
\end{pmatrix}=\begin{pmatrix}
+
|0.14%
W \\
+
|0.11%
L \\
+
|0.04%
I
+
|-
\end{pmatrix}[/math]
+
|}
 
</div>
 
</div>
 +
 +
Spanish cryptograms are often solved with patterns as well, with a few differences:
 +
* Look for the two most common letters, instead of the most common letters: E and A have relatively close frequency, and are much higher than the rest.
 +
* The most common spanish words are DE, LA, QUE, EL, EN. Since Spanish has far more two-letter words, it is helpful to decrypt them, using the placement of the letter E. QUE is the most common three-letter word, almost twice as common as the next ones.
 +
* Decrypting words using word fragments are much more difficult for teams without fluency in Spanish.
 +
 +
===Hill Cipher===
 +
 +
'''''NOTE:''' These cryptograms will be matrix based, and only use 2x2 or 3x3 matrices.''
 +
 +
The alphabet for the Hill cipher has corresponding numbers as follows: 
 +
 +
<div align="center" style="overflow:auto">
 +
{| class="wikitable" style="margin-bottom: 0px"
 +
|+Hill Cipher Alphabet
 +
|-
 +
!Letter
 +
|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
 +
|-
 +
!Number
 +
|0
 +
|1
 +
|2
 +
|3
 +
|4
 +
|5
 +
|6
 +
|7
 +
|8
 +
|9
 +
|10
 +
|11
 +
|12
 +
|13
 +
|14
 +
|15
 +
|16
 +
|17
 +
|18
 +
|19
 +
|20
 +
|21
 +
|22
 +
|23
 +
|24
 +
|25
 +
|-
 +
|}
 +
</div>
 +
Begin by picking a key matrix of either 2x2 or 3x3. These could be a 4 letter word or three 3 letter words. For this example, the key will be WIKI (2x2 matrix). Then, break the message into groups of two. This example will use the message SCIENCE OLYMPIAD, which would be split up into SC IE NC EO LY MP IA D'''Z'''. Notice that a '''Z''' is added in order to make the last group a group of two. Write the message and the key as matrices.
  
 
<div align="center">
 
<div align="center">
 
[math]
 
[math]
 
\begin{pmatrix}
 
\begin{pmatrix}
B & E & E \\
+
W & I \\
F & L & Y \\
+
K & I
B & U & G
 
\end{pmatrix}*\begin{pmatrix}
 
T \\
 
T \\
 
H \\
 
\end{pmatrix}=\begin{pmatrix}
 
1 & 4 & 4 \\
 
5 & 11 & 24 \\
 
1 & 20 & 6
 
\end{pmatrix}*\begin{pmatrix}
 
19 \\
 
19 \\
 
7
 
\end{pmatrix}=\begin{pmatrix}
 
123 \\
 
472 \\
 
441
 
\end{pmatrix}\bmod 26=\begin{pmatrix}
 
19 \\
 
4 \\
 
25
 
\end{pmatrix}=\begin{pmatrix}
 
T \\
 
E \\
 
Z
 
\end{pmatrix}[/math]
 
</div>
 
<div align="center">
 
[math]
 
\begin{pmatrix}
 
B & E & E \\
 
F & L & Y \\
 
B & U & G
 
\end{pmatrix}*\begin{pmatrix}
 
E \\
 
W \\
 
I \\
 
\end{pmatrix}=\begin{pmatrix}
 
1 & 4 & 4 \\
 
5 & 11 & 24 \\
 
1 & 20 & 6
 
\end{pmatrix}*\begin{pmatrix}
 
4 \\
 
22 \\
 
8
 
\end{pmatrix}=\begin{pmatrix}
 
124 \\
 
454 \\
 
492
 
\end{pmatrix}\bmod 26=\begin{pmatrix}
 
20 \\
 
12 \\
 
24
 
\end{pmatrix}=\begin{pmatrix}
 
U \\
 
M \\
 
Y
 
\end{pmatrix}[/math]
 
</div>
 
<div align="center">
 
[math]
 
\begin{pmatrix}
 
B & E & E \\
 
F & L & Y \\
 
B & U & G
 
 
\end{pmatrix}*\begin{pmatrix}
 
\end{pmatrix}*\begin{pmatrix}
K \\
+
S \\
I \\
+
C
Z \\
 
 
\end{pmatrix}=\begin{pmatrix}
 
\end{pmatrix}=\begin{pmatrix}
1 & 4 & 4 \\
+
22 & 8 \\
5 & 11 & 24 \\
+
10 & 8
1 & 20 & 6
 
 
\end{pmatrix}*\begin{pmatrix}
 
\end{pmatrix}*\begin{pmatrix}
10 \\
+
18 \\
8 \\
+
2
25
 
 
\end{pmatrix}=\begin{pmatrix}
 
\end{pmatrix}=\begin{pmatrix}
142 \\
+
412 \\
738 \\
+
196
320
 
 
\end{pmatrix}\bmod 26=\begin{pmatrix}
 
\end{pmatrix}\bmod 26=\begin{pmatrix}
12 \\
+
22 \\
10 \\
+
14
8
 
 
\end{pmatrix}=\begin{pmatrix}
 
\end{pmatrix}=\begin{pmatrix}
M \\
+
W \\
K \\
+
O
I
 
 
\end{pmatrix}[/math]
 
\end{pmatrix}[/math]
 
</div>
 
</div>
  
The encoded message is WLITEZUMYMKI.
+
In the second step of the above equation, the matrices are multiplied. Although it may seem complicated, matrix multiplication is fairly straightforward.  
 
+
<div align="center">
When given 4 corresponding plaintext and ciphertext create two sets of equations and solve them. For example if ABCD plaintext corresponds to DCBA and you have to find the encryption key
 
 
[math]\begin{pmatrix}
 
[math]\begin{pmatrix}
 
A & B \\
 
A & B \\
C & D \\
+
C & D
 +
\end{pmatrix}*\begin{pmatrix}
 +
E \\
 +
F
 
\end{pmatrix}[/math]
 
\end{pmatrix}[/math]
create 2 matrices with AB and CD
+
</div>
 +
 
 +
The matrices are multiplied as follows: [math]A[/math] and [math]E[/math] are multiplied, then added to the product of [math]B[/math] and [math]F[/math]. [math]C[/math] and [math]E[/math] are multiplied and added to the product of [math]D[/math] and [math]F[/math]. Thus, the product of the matrices is:
 +
<div align="center">
 
[math]\begin{pmatrix}
 
[math]\begin{pmatrix}
0\\
+
AE + BF \\
1\\
+
CE + DF
 
\end{pmatrix}[/math]
 
\end{pmatrix}[/math]
 +
</div>
 +
 +
Matrix multiplication for 3x3 matrices is very similar.
 +
<div align="center">
 
[math]\begin{pmatrix}
 
[math]\begin{pmatrix}
2\\
+
A & B & C \\
3\\
+
D & E & F \\
 +
G & H & I \\
 +
\end{pmatrix}*\begin{pmatrix}
 +
J & K & L \\
 +
M & N & O \\
 +
P & Q & R \\
 
\end{pmatrix}[/math]
 
\end{pmatrix}[/math]
You get 0A plus 1B = 3 and 0C plus 1D = 2
+
</div>
2A plus 3B = 1 and 2C plus 3D = 0
+
Just like in a 2x2 matrix, the row of the first matrix is multiplied by the column of the second matrix, giving the following product.
With 0A plus 1B = 3 times 3 is 0A plus 3B = 9
+
 
2A plus 3B = 3 minus (0A plus 3B = 9
+
<div align="center">
2A = -6 mod 26 or 2A=20
+
[math]\begin{pmatrix}
A value = 10
+
AJ+BM+CP & AK+BN+CQ & AL+BO+CR \\
Repeat for other values
+
DJ+EM+FP & DK+EN+FQ & DL+EO+FR \\
 +
GJ+HM+IP & GK+HN+IQ & GL+HO+IR \\
 +
\end{pmatrix}[/math]
 +
</div>
 +
It is important to note that in order to multiply matrices, the number of columns in the first matrix MUST equal the number of rows in the second matrix. The size of the product matrix is the number of rows in the first matrix x the number of columns in the second matrix.
  
===Vigenère Cipher===
+
The "mod" operation is also fairly straightforward. Essentially, it finds the remainder after dividing. For example, [math]153 \bmod 26 [/math] is equal to the remainder of [math]153 / 26[/math], which is 23. On a scientific calculator, this is found by dividing the two numbers, subtracting the integer value from the answer, and multiplying the decimals by the number after "mod" (in this case, 26). Therefore, the process would be:
  
The Vigenère cipher, invented by Blaise de Vigenère in the 16th century, is a polyalphabetic cipher. This means that each letter is shifted by a different amount. According to the rules, students will probably be asked to encrypt rather than decrypt Vigenère ciphers. Encrypting is a fairly straightforward procedure.  
+
<div align="center">
 
+
[math]153/26=5.884615385[/math]
First, write out the message with the key under it, repeating the key as many times as necessary. An example is shown.  
+
</div>
 +
<div align="center">
 +
[math]5.884615385-5=0.884615385[/math]
 +
</div>
 +
<div align="center">
 +
[math]0.884615385*26=23[/math]
 +
</div>
  
 +
The rest of the encoding of the message is shown below.
 
<div align="center">
 
<div align="center">
{|class="wikitable"
+
[math]
|+Message with Key
+
\begin{pmatrix}
|-
+
W & I \\
!Message
+
K & I
|S
+
\end{pmatrix}*\begin{pmatrix}
|C
+
S \\
|I
+
C
|E
+
\end{pmatrix}=\begin{pmatrix}
|N
+
22 & 8 \\
|C
+
10 & 8
|E
+
\end{pmatrix}*\begin{pmatrix}
|O
+
18 \\
|L
+
2
|Y
+
\end{pmatrix}=\begin{pmatrix}
|M
+
412 \\
|P
+
196
|I
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
|A
+
22 \\
|D
+
14
|I
+
\end{pmatrix}=\begin{pmatrix}
|S
+
W \\
|C
+
O
|O
+
\end{pmatrix}[/math]
|O
+
</div>
|L
+
 
|-
+
<div align="center">
!Key
+
[math]
|S
+
\begin{pmatrix}
|C
+
W & I \\
|I
+
K & I
|O
+
\end{pmatrix}*\begin{pmatrix}
|L
+
I \\
|Y
+
E
|S
+
\end{pmatrix}=\begin{pmatrix}
|C
+
22 & 8 \\
|I
+
10 & 8
|O
+
\end{pmatrix}*\begin{pmatrix}
|L
+
8 \\
|Y
+
4
|S
+
\end{pmatrix}=\begin{pmatrix}
|C
+
208 \\
|I
+
112
|O
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
|L
+
0 \\
|Y
+
8
|S
+
\end{pmatrix}=\begin{pmatrix}
|C
+
A \\
|I
+
I
|-
+
\end{pmatrix}[/math]
|}
 
 
</div>
 
</div>
Then, take out the alphabet square, as shown below. This will typically be provided on the test.
 
  
[[File:vig_table.png|thumb|500px|center|Vigenère Alphabet Table]]
+
<div align="center">
 
+
[math]
Using the alphabet square, encode the plaintext. The first message letter is S and the first key letter is S, therefore, look at the table to see where row S and column S intersect. It is clear that they intersect at K, so write down K as the first letter of the ciphertext. Repeat this with the rest of the message. Thus, the encrypted text is "KEQSYAW QTMXNACL WD AGQT"
+
\begin{pmatrix}
 
+
W & I \\
If the key and ciphertext are both given, decoding is also possible. This is done by taking a letter of the '''key''' and finding its '''row''', finding the corresponding letter of '''ciphertext''' in that row, and seeing what column that letter falls in. The letter in the column is the letter of the plaintext. In the previous example, the first letter is decoded by going to row S and finding K, which is located in column S. Thus, the plaintext letter is S.
+
K & I
 
+
\end{pmatrix}*\begin{pmatrix}
====Encoding without table====
+
N \\
Tables are typically given on the test, but in the event they are not, the following strategy may be more helpful.
+
C
 
+
\end{pmatrix}=\begin{pmatrix}
Remember or recreate the correspondence between letter and number like in Affine and Hill Cipher, with A being 0 and Z being 25. Then, for each letter, convert the plain text and key to a sequence of numbers, and add the numbers modulo 26. Then, convert the number back to letter.
+
22 & 8 \\
 
+
10 & 8
For example, if we encode the message "SCIENCEOLYMPIADISCOOL" using the key SCIOLY, we get
+
\end{pmatrix}*\begin{pmatrix}
 
+
13 \\
[[Image:VingereExample.png|500px|center]]
+
2
 
+
\end{pmatrix}=\begin{pmatrix}
To decode a message using this method, subtract instead of add the key's corresponding number: The cipher text K with the corresponding key letter S gives plain text [math]10-18=-8\equiv18\pmod{26}\to \text{S}[/math].
+
302 \\
 
+
146
===Running Key Cipher===
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
The running key cipher is a variant of the Vigenère Cipher. Rather than using a word as a key, a sentence/paragraph is used as the key. Essentially, instead of repeating a word multiple times as the key, a sentence/paragraph constitutes as the key and is used continuously. If the test was made with Toebes, then the four standard documents used to create a question using the Running Key Cipher are the Gettysburg Address, the Declaration of Independence, the United States Consitution, and the Magna Carta (in latin), so make sure to familiarize yourself on doing running key questions especially with those documents.
+
16 \\
In the event that a question encoded with the running key cipher asks you to decode the phrase but does not give  the key for it, then one  has to use one of the documents given on the reference sheet (if applicable) and plug them all in to determine which of the documents is the key. If they give the key but do not give the text of the key (ex. "a famous quote by George Washington"), then it is probably best to skip the question.
+
16
 
+
\end{pmatrix}=\begin{pmatrix}
===Baconian Cipher===
+
Q \\
The Baconian cipher replaces each letter of the plaintext with a 5 letter combination of 'A' and 'B'. This replacement is a binary form of encoding, in which 'A' may be considered as 0 and 'B' as 1. One variant of the Baconian Cipher uses a 24 letter alphabet with the letters 'I' and 'J' having the same code, as well as 'U' and 'V'.
+
Q
{| class="wikitable"
+
\end{pmatrix}[/math]
|+Baconian Alphabet (24-Letter Variant)
+
</div>
|-
+
<div align="center">
!Letter
+
[math]
|A
+
\begin{pmatrix}
|B
+
W & I \\
|C
+
K & I
|D
+
\end{pmatrix}*\begin{pmatrix}
|E
+
E \\
|F
+
O
|G
+
\end{pmatrix}=\begin{pmatrix}
|H
+
22 & 8 \\
|style="background: #FFFF00;"|I
+
10 & 8
|style="background: #FFFF00;"|J
+
\end{pmatrix}*\begin{pmatrix}
|K
+
4 \\
|L
+
14
|M
+
\end{pmatrix}=\begin{pmatrix}
|N
+
200 \\
|O
+
152
|P
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
|Q
+
18 \\
|R
+
22
|S
+
\end{pmatrix}=\begin{pmatrix}
|T
+
S \\
|style="background: #FFFF00;"|U
+
W
|style="background: #FFFF00;"|V
+
\end{pmatrix}[/math]
|W
+
</div>
|X
+
<div align="center">
|Y
+
[math]
|Z
+
\begin{pmatrix}
|-
+
W & I \\
!Code
+
K & I
|aaaaa
+
\end{pmatrix}*\begin{pmatrix}
|aaaab
+
L \\
|aaaba
+
Y
|aaabb
+
\end{pmatrix}=\begin{pmatrix}
|aabaa
+
22 & 8 \\
|aabab
+
10 & 8
|aabba
+
\end{pmatrix}*\begin{pmatrix}
|aabbb
+
11 \\
|style="background: #FFFF00;"|abaaa
+
24
|style="background: #FFFF00;"|abaaa
+
\end{pmatrix}=\begin{pmatrix}
|abaab
+
434 \\
|ababa
+
302
|ababb
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
|abbaa
+
18 \\
|abbab
+
16
|abbba
+
\end{pmatrix}=\begin{pmatrix}
|abbbb
+
S \\
|baaaa
+
Q
|baaab
+
\end{pmatrix}[/math]
|baaba
+
</div>
|style="background: #FFFF00;"|baabb
+
<div align="center">
|style="background: #FFFF00;"|baabb
+
[math]
|babaa
+
\begin{pmatrix}
|babab
+
W & I \\
|babba
+
K & I
|babbb
+
\end{pmatrix}*\begin{pmatrix}
|-
+
M \\
!Binary
+
P
|00000
+
\end{pmatrix}=\begin{pmatrix}
|00001
+
22 & 8 \\
|00010
+
10 & 8
|00011
+
\end{pmatrix}*\begin{pmatrix}
|00100
+
12 \\
|00101
+
15
|00110
+
\end{pmatrix}=\begin{pmatrix}
|00111
+
384 \\
|style="background: #FFFF00;"|01000
+
240
|style="background: #FFFF00;"|01000
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
|01001
+
20 \\
|01010
+
6
|01011
+
\end{pmatrix}=\begin{pmatrix}
|01100
+
U \\
|01101
+
G
|01110
+
\end{pmatrix}[/math]
|01111
+
</div>
|10000
+
<div align="center">
|10001
+
[math]
|10010
+
\begin{pmatrix}
|style="background: #FFFF00;"|10011
+
W & I \\
|style="background: #FFFF00;"|10011
+
K & I
|10100
+
\end{pmatrix}*\begin{pmatrix}
|10101
+
I \\
|10110
+
A
|10111
+
\end{pmatrix}=\begin{pmatrix}
|-
+
22 & 8 \\
|}
+
10 & 8
Another variant of this cipher uses a unique code for each letter (26 letter alphabet). However, in a [https://www.soinc.org/what-type-baconian-cipher-being-tested-one-which-v-and-j-do-not-have-unique-code-or-one-where-all rule clarification], only the 24 letter variation is to be used on Codebusters tests for the 2019 season.
+
\end{pmatrix}*\begin{pmatrix}
{| class="wikitable"
+
8 \\
|+Baconian Alphabet (26-Letter Variant)
+
0
|-
+
\end{pmatrix}=\begin{pmatrix}
!Letter
+
176 \\
|A
+
80
|B
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
|C
+
20 \\
|D
+
2
|E
+
\end{pmatrix}=\begin{pmatrix}
|F
+
U \\
|G
+
C
|H
+
\end{pmatrix}[/math]
|I
+
</div>
|J
+
<div align="center">
|K
+
[math]
|L
+
\begin{pmatrix}
|M
+
W & I \\
|N
+
K & I
|O
+
\end{pmatrix}*\begin{pmatrix}
|P
+
D \\
|Q
+
Z
|R
+
\end{pmatrix}=\begin{pmatrix}
|S
+
22 & 8 \\
|T
+
10 & 8
|U
+
\end{pmatrix}*\begin{pmatrix}
|V
+
3 \\
|W
+
25
|X
+
\end{pmatrix}=\begin{pmatrix}
|Y
+
226 \\
|Z
+
230
|-
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
!Code
+
18 \\
|aaaaa
+
22
|aaaab
+
\end{pmatrix}=\begin{pmatrix}
|aaaba
+
S \\
|aaabb
+
W
|aabaa
+
\end{pmatrix}[/math]
|aabab
+
</div>
|aabba
+
 
|aabbb
+
The encoded message is WOAIQQSWSQUGUCSW.
|abaaa
+
 
|abaab
+
3x3 matrix encryption works in the same way. This example will encrypt "EDIT THE WIKI" using the key "BEE FLY BUG". First, split up the plaintext into groups of three, which becomes EDI TTH EWI KIZ. Once again, the last group has a Z added to make it a group of three.  
|ababa
+
 
|ababb
+
<div align="center">
|abbaa
+
[math]
|abbab
+
\begin{pmatrix}
|abbba
+
B & E & E \\
|abbbb
+
F & L & Y \\
|baaaa
+
B & U & G
|baaab
+
\end{pmatrix}*\begin{pmatrix}
|baaba
+
E \\
|baabb
+
D \\
|babaa
+
I \\
|babab
+
\end{pmatrix}=\begin{pmatrix}
|babba
+
1 & 4 & 4 \\
|babbb
+
5 & 11 & 24 \\
|bbaaa
+
1 & 20 & 6
|bbaab
+
\end{pmatrix}*\begin{pmatrix}
|-
+
4 \\
!Binary
+
3 \\
|00000
+
8
|00001
+
\end{pmatrix}=\begin{pmatrix}
|00010
+
48 \\
|00011
+
245 \\
|00100
+
112
|00101
+
\end{pmatrix}\bmod 26=\begin{pmatrix}
|00110
+
22 \\
|00111
+
11 \\
|01000
+
8
|01001
+
\end{pmatrix}=\begin{pmatrix}
|01010
+
W \\
|01011
+
L \\
|01100
+
I
|01101
+
\end{pmatrix}[/math]
|01110
+
</div>
|01111
+
 
|10000
+
<div align="center">
|10001
+
[math]
|10010
+
\begin{pmatrix}
|10011
+
B & E & E \\
|10100
+
F & L & Y \\
|10101
+
B & U & G
|10110
+
\end{pmatrix}*\begin{pmatrix}
|10111
+
T \\
|11000
+
T \\
|11001
+
H \\
|-
+
\end{pmatrix}=\begin{pmatrix}
|}
+
1 & 4 & 4 \\
Standard numbering systems use a base 10 method of counting (ones place, tens place, hundreds place, etc). What this means is that normally for example 24 = (2*10 + 4*1). The Baconian Cipher uses a base 2 system. The following is an example of base 2 converted to standard base 10: 01001 (base 2) = (0*16 + 1*8 + 0*4 + 0*2 + 1*1) = (1*8 + 1*1) = 9 (base 10). As seen in the chart above, 01001 corresponds to J, which is the 9th letter in the alphabet (assuming A = 0). When the first variant is shown, the numbering system will be off by 1 from J to U and off by 2 from V to Z. For example, 10100 = W, even though 10100 = 20 (base 10) which corresponds to U on the alphabet chart when A = 0.
+
5 & 11 & 24 \\
 
+
1 & 20 & 6
When solving a question encoded with the Baconian Cipher, it is very likely that they won't explicitly give you "A" and "B" to use to find the corresponding letters. Most of the time, they'll have certain symbols or letters that are meant to represent "A" and "B". One example of this would be using all of of the even letters in the alphabet to represent "A" while all the odd letters represent "B". There are many different variants of this, including symbols on a keyboard and vowel/consonants. To solve a Baconian, try to group the different symbols/letters into two groups based on their properties, and assign one group "A" and the other group "B". If it doesn't work the first time, then switch the groups so that the previous "A" group is now the "B" group. If even then it doesn't seem to be working, then start over again and find a different characteristic to base the groups off of. For this reason, the Baconian Cipher can take longer than some of the other ciphers.
+
\end{pmatrix}*\begin{pmatrix}
 +
19 \\
 +
19 \\
 +
7
 +
\end{pmatrix}=\begin{pmatrix}
 +
123 \\
 +
472 \\
 +
441
 +
\end{pmatrix}\bmod 26=\begin{pmatrix}
 +
19 \\
 +
4 \\
 +
25
 +
\end{pmatrix}=\begin{pmatrix}
 +
T \\
 +
E \\
 +
Z
 +
\end{pmatrix}[/math]
 +
</div>
 +
<div align="center">
 +
[math]
 +
\begin{pmatrix}
 +
B & E & E \\
 +
F & L & Y \\
 +
B & U & G
 +
\end{pmatrix}*\begin{pmatrix}
 +
E \\
 +
W \\
 +
I \\
 +
\end{pmatrix}=\begin{pmatrix}
 +
1 & 4 & 4 \\
 +
5 & 11 & 24 \\
 +
1 & 20 & 6
 +
\end{pmatrix}*\begin{pmatrix}
 +
4 \\
 +
22 \\
 +
8
 +
\end{pmatrix}=\begin{pmatrix}
 +
124 \\
 +
454 \\
 +
492
 +
\end{pmatrix}\bmod 26=\begin{pmatrix}
 +
20 \\
 +
12 \\
 +
24
 +
\end{pmatrix}=\begin{pmatrix}
 +
U \\
 +
M \\
 +
Y
 +
\end{pmatrix}[/math]
 +
</div>
 +
<div align="center">
 +
[math]
 +
\begin{pmatrix}
 +
B & E & E \\
 +
F & L & Y \\
 +
B & U & G
 +
\end{pmatrix}*\begin{pmatrix}
 +
K \\
 +
I \\
 +
Z \\
 +
\end{pmatrix}=\begin{pmatrix}
 +
1 & 4 & 4 \\
 +
5 & 11 & 24 \\
 +
1 & 20 & 6
 +
\end{pmatrix}*\begin{pmatrix}
 +
10 \\
 +
8 \\
 +
25
 +
\end{pmatrix}=\begin{pmatrix}
 +
142 \\
 +
738 \\
 +
320
 +
\end{pmatrix}\bmod 26=\begin{pmatrix}
 +
12 \\
 +
10 \\
 +
8
 +
\end{pmatrix}=\begin{pmatrix}
 +
M \\
 +
K \\
 +
I
 +
\end{pmatrix}[/math]
 +
</div>
 +
 
 +
The encoded message is WLITEZUMYMKI.
 +
 
 +
When given 4 corresponding plaintext and ciphertext create two sets of equations and solve them. For example if ABCD plaintext corresponds to DCBA and you have to find the encryption key
 +
[math]\begin{pmatrix}
 +
A & B \\
 +
C & D \\
 +
\end{pmatrix}[/math]
 +
create 2 matrices with AB and CD
 +
[math]\begin{pmatrix}
 +
0\\
 +
1\\
 +
\end{pmatrix}[/math]
 +
[math]\begin{pmatrix}
 +
2\\
 +
3\\
 +
\end{pmatrix}[/math]
 +
You get 0A plus 1B = 3 and 0C plus 1D = 2
 +
2A plus 3B = 1 and 2C plus 3D = 0
 +
With 0A plus 1B = 3 times 3 is 0A plus 3B = 9
 +
2A plus 3B = 3 minus (0A plus 3B = 9
 +
2A = -6 mod 26 or 2A=20
 +
A value = 10
 +
Repeat for other values
 +
 
 +
===Running Key Cipher===
 +
The running key cipher is a variant of the Vigenère Cipher. Rather than using a word as a key, a sentence/paragraph is used as the key. Essentially, instead of repeating a word multiple times as the key, a sentence/paragraph constitutes as the key and is used continuously. If the test was made with [https://toebes.com/codebusters Toebes], then the four standard documents used to create a question using the Running Key Cipher are:
 +
 
 +
* The first line of the Gettysburg Address
 +
* The first line/paragraph of the Declaration of Independence
 +
* The first line of the United States Consitution
 +
* The first line of the Magna Carta (in Latin)
 +
 
 +
In the event that a question encoded with the running key cipher asks you to decode the phrase but does not give  the key for it, then one  has to use one of the documents given on the reference sheet (if applicable) and plug them all in to determine which of the documents is the key. If they give the key but do not give the text of the key (ex. "a famous quote by George Washington"), then it is probably best to skip the question.  
  
 
===RSA Cipher===
 
===RSA Cipher===
Line 1,549: Line 1,754:
 
Note: The Dancing Men cipher is not included in 2019 rules. However, it is a common part of tests from past years' trial events.
 
Note: The Dancing Men cipher is not included in 2019 rules. However, it is a common part of tests from past years' trial events.
  
==Test Format==
 
===Question Point Distribution===
 
The amount of points each question is worth will be distributed by the following:
 
*An easy question: 100-150 points
 
*A medium question: 200-300 points
 
*A hard question: 350-500 points
 
*A very hard question: 550-700 points
 
 
In the case of a tie, select questions predetermined by the event supervisor will serve as a tiebreaker. The tie is broken using the following criteria in this order: score, degree of correctness, and number attempted.
 
 
===Code types that may be used at the Invitational and Regional Competitions===
 
*Atbash Cipher
 
*The Caesar Cipher (shift cipher)
 
*Mono-alphabetic substitution (can use K1, K2, or random alphabets)
 
**Aristocrats with a hint - messages with spaces included, and with a hint
 
**Aristocrats - messages with spaces included, but without a hint
 
**Aristocrats - messages with spaces and hints, but including spelling/grammar errors
 
**Aristocrats - messages with spaces and including spelling/grammar errors but no hints
 
**Patristocrats with a hint - messages with spaces removed, and with a hint
 
**Patristocrats - messages with spaces removed, but without a hint
 
*Affine Cipher - '''encryption only'''
 
*Vigenère Cipher - encryption/decryption only, not cryptanalysis
 
*Baconian cipher and its variants
 
*Xenocrypt (no more than one)
 
*Mathematical Cryptanalysis of the Hill Cipher - either producing a decryption matrix given a 2x2
 
encryption matrix or computing a decryption matrix given 4 plaintext-ciphertext letter pairs.
 
 
===Code types that may be used at the State and National Competitions===
 
*All Invitational and Regional code types
 
*The running key cipher
 
*Cryptanalysis of the Vigenère cipher with a 'crib' (a known plaintext attack)
 
*The RSA Cipher
 
*The Hill Cipher - encrypting or decryption with a provided 2x2 or 3x3 matrix.
 
*Xenocrypt - '''at least one''' cryptogram will be in spanish
 
*Mathematical Cryptanalysis of the Affine Cipher
 
 
==External Links==
 
==External Links==
 
:Trial event rules
 
:Trial event rules
Line 1,622: Line 1,792:
 
{{2016 National Trials}}
 
{{2016 National Trials}}
  
 +
{{2020 National Trials}}
 +
{{Inquiry Event}}
 +
{{2021Events}}
 +
[[Category:Inquiry and Nature of Science Events]]
 
[[Category: Event Pages]]
 
[[Category: Event Pages]]
 
[[Category: Lab Event Pages]]
 
[[Category: Lab Event Pages]]
 +
[[Category:Trial Event Pages]]

Revision as of 06:25, 6 August 2020

This page contains a large number of equations and mathematical symbols, which may take some time to load.

Codebusters is an event in Division C for the 2020 season and was held as trial event at both the 2016 National Tournament and the 2018 National Tournament. It was last held as an official event in 2019. It is also being held as a trial event for Division B at the 2020 National Tournament. In this event, up to 3 participants must decode encrypted messages, or they may be required to encode messages with certain advanced ciphers. Competitors are not allowed to bring any resources to this event, but can bring a 4 or 5 function calculator - no scientific or graphing calculators allowed.

Test Format

Format and Scoring

Tests are composed of a variety of questions where teams will encrypt or decrypt various code types. The number of questions on a given test is variable, but tests often contain anywhere from 6-24 questions, depending on the difficulty of the questions. The first question of a test is timed, and a time bonus is given for the question based on how quickly it is completed. Points may be deducted from questions based on the number of mistakes found in the answer given. If the answer differs from the solution by only one or two letters, then no points are removed, despite the answer having errors. Each additional error after two errors will result in a deduction of 100 points. The number of points removed from a question through deductions will not exceed the value of the question (meaning that deductions will never result in a question score below 0).

The First Question

The very first question is timed - when solved, a team member should signal the event supervisor that they have finished the question, such as raising their hand, shouting "bingo!", or another method determined by the supervisor before the event begins. The first question will be an Aristocrat with or without a hint. Teams will receive bonus points depending on their time, and they may make as many attempts as they want to break the code without any penalties. The timing bonus will be calculated from the start of the event until the question is answered successfully, or until 10 minutes have elapsed, and is calculated with the formula: 4*(600-number of seconds taken). Teams may still answer the question after 10 minutes; however, the timing bonus is 0. The first cryptogram may also be used as a tiebreaker. Solutions are given full points only if the solution is an exact match or differs by only one or two letters. Deductions for inconsistencies in the answer to the first question are treated the same as deductions for a non-timed question.

Question Point Distribution

The amount of points each question is worth will be distributed by the following:

  • An easy question: 100-150 points
  • A medium question: 200-300 points
  • A hard question: 350-500 points
  • A very hard question: 550-700 points

In the case of a tie, select questions predetermined by the event supervisor will serve as a tiebreaker. The tie is broken using the following criteria in this order: score, degree of correctness, and number attempted.

Code types that may be used at the Invitational and Regional Competitions

Code types that may be used at the State and National Competitions

Code Types

Atbash Cipher

The Atbash Cipher is a variant of the affine cipher (see above) in which both a and b equal 25. This results in the alphabet essentially becoming a mirror (A corresponds to Z, B corresponds to Y, C corresponds to X, etc.).

Atbash Cipher
Original Alphabet 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
Ciphertext Alphabet Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Following the affine cipher, the encryption formula would be:

[math]E(x) = (25x + 25) \mod 26[/math]

However, observing the mirror like alphabet yields a much simpler equation of:

[math]E(x) = D(x) = 25 - x[/math]

Since the alphabet is like a mirror, encryption is the same as decryption.


Encryption Example

Encode "encrypt" with the Atbash Cipher.

Plaintext E N C R Y P T
Numeric Component 4 13 2 17 24 15 19
[math]25 - x[/math] 21 12 23 8 1 10 6
Ciphertext V M X I B K G

The cipher text is "vmxibkg."

Decryption Example

Decode "decrypt" with the Atbash Cipher.

Plaintext Z M H D V I
Numeric Component 25 12 7 3 21 8
[math]25 - x[/math] 0 13 18 22 4 17
Ciphertext A N S W E R

The plaintext is "answer."

Caesar Cipher

One example of a mono-alphabetic substitution is Caesar shift cipher, where each letter is replaced by one shifted by a certain amount. For example, the following table has each letter shifted three positions to the right.

Caesar Shift Example Table
Original Alphabet 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
Shifted Alphabet (to the right 3) 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

From this table, it is clear that each shifted letter is the same as the original letter three spaces from it (A becomes D, B becomes E, etc). Thus, a message like "Science Olympiad is cool" would become "Vflhqfh Robpsldg lv frro" using a Caesar shift of 3. The alphabet can be shifted any number of times. This type of cryptogram can be solved through brute force, by taking a section of the message and writing out all 26 possible shifts below it, upon which the message is easily revealed.

Encryption Example

Encode "example" with a shift of 7.

By shifting each letter 7 times, we can encrypt the text.

Example Encoding
Encryption Shift Possible Plaintext
0 example
1 fybnqmf
2 gzcorng
3 hadpsoh
4 ibeqtpi
5 jcfruqj
6 kdgsvrk
7 lehtwsl

The encrypted text is lehtwsl.

Decryption Example

Decode "xhntqd".

We must test all possible shifts of our text to solve this prompt, since we do not know the shift. By repeatedly testing different shifts, we will eventually arrive at our answer.

Example Decoding
Decryption Shift Possible Plaintext
0 xhntqd
1 wgmspc
2 vflrob
3 uekqna
4 tdjpmz
5 scioly

After shifting "xhntqd" five times, the plaintext is revealed to be scioly, and no further shifts need to be tested.

Mono-alphabetic Substitution

A mono-alphabetic substitution is one where the same plaintext letters are replaced by the same ciphertext letters. Since specific encryption/decryption methods are not mentioned in the rules, a variety of ways will be covered in the following section. Mono-alphabetic ciphers may contain spaces (Aristocrats) or may have spaces removed (Patristocrats). Mono-alphabetic ciphers may use K1, K2, or random alphabets as defined by the ACA.

Solving a mono-alphabetic substitution cipher using patterns

Table of letter frequency in English.

This may be the most common way to solve a cipher on a Code Busters test, because the supervisor may not write that a Caesar cipher etc. was used to encrypt.

First, find the corresponding letter for a few cipher letter by:

  1. Look for words that are only one letter long. These will almost always be A or I, unless the cryptogram is a poem, in which case O may be used. I usually appears at the start of the sentence, while A is usually more common.
  2. Look for repeated blocks of three. The block is often THE: THE is the most common english word, used almost twice as often as the second most common, BE.
  3. Look for frequency of letters. The 12 most frequent letters in the English alphabet are ETAOIN SHRDLU, with E being the most common by a significant margin.
  4. Look for contractions. If an apostrophe is seen in the ciphertext, it can be an easy way to start deciphering using the table below.
  5. Look for double letters. They're often LL, followed in frequency by EE, SS, OO and TT.

Two clues may give different substitution, in which case experimenting may be helpful.

Then, substitute the known letters, and gradually decode more words using the word fragments. Starting with two or three-letter words are often easier, because of the limited possibilities.

Contractions
Endings Examples
'T Won't, Don't, Isn't, Aren't, Weren't, Shouldn't, Couldn't, Didn't, Can't
'S He's, She's, It's, Who's, There's, That's
'D I'd, He'd, She'd, We'd, They'd, You'd
'M I'm
'RE You're, They're, We're
'VE They've, You've, We've
'LL I'll, He'll, She'll, We'll, They'll, It'll, Who'll

Common word patterns include

  1. axx- all or too
  2. abxcx- there (most common) where or these
  3. xabx- that (most common) high or dead
  4. axbcx- which
  5. xyaxby- people
  6. xayybxx- success (abcddxxyxy- succeeded).

Keep in mind less common words may occupy these frequencies. For example xyaxby could be "indian."

Messages with Spaces and a Hint

These cryptograms are similar to those published in 20th century newspapers. These are usually solved using patterns, as described above, with the hint providing additional information to assist the decryption.

Messages with Spaces

These cryptograms are similar to NSA and diplomatic messages, and do not have a hint. These are usually solved using patterns, as described above.

Messages with Spaces and Spelling Errors

These cryptograms are similar to FBI and organized crime messages. These are often solved by patterns, with additional care:

  • The letter frequencies likely do not change, and can be applied.
  • THE and many of the most common words are seldom misspelled, unless intentionally. OF may be unintentionally misspelled as UV.
  • Piecing together words with word fragments may be more difficult. Misspelled words often sound the same as the actual word, which can be used to check the decrypted message.

Messages without Spaces

These cryptograms are similar to NSA and espionage messages, and have a hint. An example is: "UVYNYGUSZYSBZBULAPIAZUACAZZAMLGFALPERAJZNYGUUAFBR". Students are told that the last word is TODAY, and the cipher begins with a three-letter word, followed by a four-letter word.

  1. Begin by writing in TODAY. UVYNYGUSZYSBZBULAPIAZUACAZZAMLGFALPERAJZNYGUTODAY. From this, we can see that U represents T, A represents O, F represents D, B represents A, and R represents Y.
  2. Replace the cipher text with the decrypted letters. TVYNYGTSZYSBZATLOPIOZTOCOZZOMLGDOLPEYOJZNYGTTODAY
  3. The first word is a 3 letter word beginning with T, which we can guess decrypts to THE. Replace Vs with H and Y with E. THENEGTSZESAZATLOPIOZTOCOZZOMLGDOLPEYOJZNEGTTODAY
  4. In this cipher, we can see the phrase "TOCOZZOM". Because of the double Z in the middle, it can be inferred that this decrypts to TOMORROW. Replace Z with R, C with M, and M with W. THENEGTSRESARATLOPIORTOMORROWLGDOLPEYOJRNEGTTODAY.
  5. We can see the letters YOJR. This is probably YOUR. Replace J with U. THENEGTSRESARATLOPIORTOMORROWLGDOLPEYOURNEGTTODAY.
  6. The letters LG after the noun TOMORROW likely decrypt to IS. Replace L with I and G with S. THENESTSRESARATIOPIORTOMORROWISDOIPEYOURNESTTODAY.
  7. NEST probably decrypts to B, as that is the only word that makes sense in this context. THEBESTSRESARATIOPIORTOMORROWISDOIPEYOURBESTTODAY.
  8. At this point, the cipher is able to be solved using common sense. SRESARATIOP likely means PREPARATION. IOR probably means FOR. DOIPE probably means DOING. Thus, the message is THE BEST PREPARATION FOR TOMORROW IS DOING YOUR BEST TODAY.

Messages without Spaces or Hints

These cryptograms are extremely difficult and may not be tested very frequently. In the event that a test does contain one, the best method is using the patterns listed above, especially finding repeated three letter "phrases" or double letters.

Affine Cipher and Modular Arithmetic

The Affine cipher uses an alphabet of size [math]m[/math] with keys [math]a[/math] and [math]b[/math] such that [math]a,b[/math] are integers, and [math]a[/math] and [math]m[/math] are coprime (there is no positive divisor for both of them besides 1). Assuming the alphabet is of size 26, [math]a[/math] can be 1, 3, 5, 7, 9, 11 ,15, 17, 19, 21, 23 and 25. Each letter in the alphabet corresponds to a number from [math]0[/math] to [math]m-1[/math]. The most common correspondence for the English alphabet is shown below.

Alphabet
Letter 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
Number 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

The encryption formula for an Affine cipher is:

[math]E(x)=(ax+b)\bmod m.[/math]

In the formula, [math]x[/math] is the corresponding number of plaintext. For example, if encrypting N, [math]x[/math] would be 13. Essentially, numbers are plugged into the formula and the resulting number corresponds to the encrypted letter.

For this example, we encode the message CODEBUSTERS using [math]a=9[/math] and [math]b=42[/math]. To slightly speed up the process, use the fact from modular arithmetic that the function [math]ax+b[/math] does not change if we also take [math]a, b[/math] modulo 26: the function [math]9x+42[/math] is equivalent to the function [math]9x+16[/math] or [math]9x-10[/math].

Affine Cipher Encryption
Plaintext C O D E B U S T E R S
[math]x[/math] 2 14 3 4 1 20 18 19 4 17 18
[math]9x+42[/math] 60 168 69 78 51 222 204 213 78 195 204
[math](9x+42)\bmod 26[/math] 8 12 17 0 25 14 22 5 0 13 22
Ciphertext I M R A Z O W F A N W

The encrypted message is IMRAZOWFANW.

To decrypt the message given the key, use the decryption formula:

[math]D(x)=a^{-1}(x-b)\bmod 26[/math]

In this case, [math]a^{-1}[/math] is the multiplicative inverse of [math]a[/math] modulo [math]m[/math] ([math]aa^{-1}\bmod m=1[/math]). Because there are only 26 values, one can brute force it to find the value of [math]t[/math] where [math]ta \bmod m=1[/math]. [math]t[/math] represents [math]a^{-1}[/math].

Brute Force Table
[math]t[/math] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
[math]9t \bmod 26[/math] 9 18 1 10 19 2 11 20 3 12 21 4 13 22 5 12 14 23 6 15 24 7 16 25 8 17

The table reveals that [math]a^{-1}=3[/math]. Below is a table of [math]a^{-1}[/math] for [math]m=26[/math]:

Inverse Table ([math]m=26[/math])
[math]a[/math] 1 3 5 7 9 11 15 17 19 21 23 25
[math]a^{-1}[/math] 1 9 21 15 3 19 7 23 11 5 17 25

Decrypting then becomes a task of plugging into the formula.

Decryption Table
Ciphertext I M R A Z O W F A N W
[math]x[/math] 8 12 17 0 25 14 22 5 0 13 22
[math]3(x-42)[/math] -102 -90 -75 -126 -51 -84 -60 -111 -126 -87 -60
[math]3(x-42) \bmod 26[/math] 2 14 3 4 1 20 18 19 4 17 18
Plaintext C O D E B U S T E R S

Sometimes, some characters are given, which makes decryption much easier. For example, one might be given the ciphertext "CXWZ ZRC OWGW" and told that the first word is "EDIT". Thus, the characters are mapped as:

Plaintext Ciphertext
E (4) C (2)
D(3) X (23)
I (8) W (22)
T (19) Z (25)

Write out two equations using the first two values and the equation [math]Output=ax+b \bmod 26[/math] in order to solve for [math]b[/math].

[math]a\cdot4+b\bmod 26=2[/math]

[math]a\cdot3+b\bmod 26=23[/math]

Cancel out the [math]a[/math] by multiplying to get the same value (same process as solving a system of equations).

[math]12a+3b\bmod 26=6[/math]

[math]12a+4b\bmod 26=92[/math]

Subtract the equations.

[math]b\bmod 26=86[/math]

Take the mod of the right side.

[math]b\bmod 26=8[/math]

Compute the modulus values to see which works. In this case, 8 works. Now, substitute [math]b[/math] into the equation and repeat the process.

[math]a\cdot3+8\bmod 26=23[/math]

[math]a\cdot3\bmod 26=15[/math]

[math]a=5[/math]


Vigenère Cipher

The Vigenère cipher, invented by Blaise de Vigenère in the 16th century, is a polyalphabetic cipher. This means that each letter is shifted by a different amount. According to the rules, students will probably be asked to encrypt rather than decrypt Vigenère ciphers. Encrypting is a fairly straightforward procedure.

Encryption/Decryption With a Table

First, write out the message with the key under it, repeating the key as many times as necessary. An example is shown.

Message with Key
Message S C I E N C E O L Y M P I A D I S C O O L
Key S C I O L Y S C I O L Y S C I O L Y S C I

Then, take out the alphabet square, as shown below. This will typically be provided on the test.

Vigenère Alphabet Table

Using the alphabet square, encode the plaintext. The first message letter is S and the first key letter is S, therefore, look at the table to see where row S and column S intersect. It is clear that they intersect at K, so write down K as the first letter of the ciphertext. Repeat this with the rest of the message. Thus, the encrypted text is "KEQSYAW QTMXNACL WD AGQT"

If the key and ciphertext are both given, decoding is also possible. This is done by taking a letter of the key and finding its row, finding the corresponding letter of ciphertext in that row, and seeing what column that letter falls in. The letter in the column is the letter of the plaintext. In the previous example, the first letter is decoded by going to row S and finding K, which is located in column S. Thus, the plaintext letter is S.

Encryption/Decryption Without a Table

Tables are typically given on the test, but in the event they are not, the following strategy may be more helpful.

Remember or recreate the correspondence between letter and number like in Affine and Hill Cipher, with A being 0 and Z being 25. Then, for each letter, convert the plain text and key to a sequence of numbers, and add the numbers modulo 26. Then, convert the number back to letter.

For example, if we encode the message "SCIENCEOLYMPIADISCOOL" using the key SCIOLY, we get

VigenereExample.png

To decode a message using this method, subtract instead of add the key's corresponding number: The cipher text K with the corresponding key letter S gives plain text [math]10-18=-8\equiv18\pmod{26}\to \text{S}[/math].

Baconian Cipher

The Baconian cipher replaces each letter of the plaintext with a 5 letter combination of 'A' and 'B'. This replacement is a binary form of encoding, in which 'A' may be considered as 0 and 'B' as 1. One variant of the Baconian Cipher uses a 24 letter alphabet with the letters 'I' and 'J' having the same code, as well as 'U' and 'V'.

Baconian Alphabet (24-Letter Variant)
Letter 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
Code aaaaa aaaab aaaba aaabb aabaa aabab aabba aabbb abaaa abaaa abaab ababa ababb abbaa abbab abbba abbbb baaaa baaab baaba baabb baabb babaa babab babba babbb
Binary 00000 00001 00010 00011 00100 00101 00110 00111 01000 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10011 10100 10101 10110 10111

Another variant of this cipher uses a unique code for each letter (26 letter alphabet). However, in a rule clarification, only the 24 letter variation is to be used on Codebusters tests for the 2019 season.

Baconian Alphabet (26-Letter Variant)
Letter 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
Code aaaaa aaaab aaaba aaabb aabaa aabab aabba aabbb abaaa abaab ababa ababb abbaa abbab abbba abbbb baaaa baaab baaba baabb babaa babab babba babbb bbaaa bbaab
Binary 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001

Standard numbering systems use a base 10 method of counting (ones place, tens place, hundreds place, etc). What this means is that normally for example 24 = (2*10 + 4*1). The Baconian Cipher uses a base 2 system. The following is an example of base 2 converted to standard base 10: 01001 (base 2) = (0*16 + 1*8 + 0*4 + 0*2 + 1*1) = (1*8 + 1*1) = 9 (base 10). As seen in the chart above, 01001 corresponds to J, which is the 9th letter in the alphabet (assuming A = 0). When the first variant is shown, the numbering system will be off by 1 from J to U and off by 2 from V to Z. For example, 10100 = W, even though 10100 = 20 (base 10) which corresponds to U on the alphabet chart when A = 0.

When solving a question encoded with the Baconian Cipher, it is very likely that they won't explicitly give you "A" and "B" to use to find the corresponding letters. Most of the time, they'll have certain symbols or letters that are meant to represent "A" and "B". One example of this would be using all of of the even letters in the alphabet to represent "A" while all the odd letters represent "B". There are many different variants of this, including symbols on a keyboard and vowel/consonants. To solve a Baconian, try to group the different symbols/letters into two groups based on their properties, and assign one group "A" and the other group "B". If it doesn't work the first time, then switch the groups so that the previous "A" group is now the "B" group. If even then it doesn't seem to be working, then start over again and find a different characteristic to base the groups off of. For this reason, the Baconian Cipher can take longer than some of the other ciphers.

Xenocrypt

At the invitational/Regional level, one cryptogram may be in Spanish as a challenge. At the state level, there will be at least one. It may be helpful if one of the partners is fluent in or has a few years of knowledge in Spanish.

For Spanish cryptograms, n and ñ are treated as different letters. However, letters with accents are treated the same as without (a and á are the same). This means that, when working with cryptograms, accent marks do not factor in. Also, ch, ll, and rr are NOT considered distinct letters. Thus, "churro" would have 6 letters: c-h-u-r-r-o. The Spanish alphabet used for cryptograms is as follows:

Spanish Alphabet
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

The frequency table of Spanish letters is as follows, from most to least frequent:

Spanish Letter Frequency Table
Letter E A O S N R I L U D T C M P
Frequency 14.08% 12.16% 9.20% 7.20% 6.83% 6.41% 5.98% 5.24% 4.69% 4.67% 4.60% 3.87% 3.08% 2.89%
Letter B H Q Y V G F J Z Ñ X K W
Frequency 1.49% 1.18% 1.11% 1.09% 1.05% 1.00% 0.69% 0.52% 0.47% 0.17% 0.14% 0.11% 0.04%

Spanish cryptograms are often solved with patterns as well, with a few differences:

  • Look for the two most common letters, instead of the most common letters: E and A have relatively close frequency, and are much higher than the rest.
  • The most common spanish words are DE, LA, QUE, EL, EN. Since Spanish has far more two-letter words, it is helpful to decrypt them, using the placement of the letter E. QUE is the most common three-letter word, almost twice as common as the next ones.
  • Decrypting words using word fragments are much more difficult for teams without fluency in Spanish.

Hill Cipher

NOTE: These cryptograms will be matrix based, and only use 2x2 or 3x3 matrices.

The alphabet for the Hill cipher has corresponding numbers as follows:

Hill Cipher Alphabet
Letter 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
Number 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Begin by picking a key matrix of either 2x2 or 3x3. These could be a 4 letter word or three 3 letter words. For this example, the key will be WIKI (2x2 matrix). Then, break the message into groups of two. This example will use the message SCIENCE OLYMPIAD, which would be split up into SC IE NC EO LY MP IA DZ. Notice that a Z is added in order to make the last group a group of two. Write the message and the key as matrices.

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} S \\ C \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 18 \\ 2 \end{pmatrix}=\begin{pmatrix} 412 \\ 196 \end{pmatrix}\bmod 26=\begin{pmatrix} 22 \\ 14 \end{pmatrix}=\begin{pmatrix} W \\ O \end{pmatrix}[/math]

In the second step of the above equation, the matrices are multiplied. Although it may seem complicated, matrix multiplication is fairly straightforward.

[math]\begin{pmatrix} A & B \\ C & D \end{pmatrix}*\begin{pmatrix} E \\ F \end{pmatrix}[/math]

The matrices are multiplied as follows: [math]A[/math] and [math]E[/math] are multiplied, then added to the product of [math]B[/math] and [math]F[/math]. [math]C[/math] and [math]E[/math] are multiplied and added to the product of [math]D[/math] and [math]F[/math]. Thus, the product of the matrices is:

[math]\begin{pmatrix} AE + BF \\ CE + DF \end{pmatrix}[/math]

Matrix multiplication for 3x3 matrices is very similar.

[math]\begin{pmatrix} A & B & C \\ D & E & F \\ G & H & I \\ \end{pmatrix}*\begin{pmatrix} J & K & L \\ M & N & O \\ P & Q & R \\ \end{pmatrix}[/math]

Just like in a 2x2 matrix, the row of the first matrix is multiplied by the column of the second matrix, giving the following product.

[math]\begin{pmatrix} AJ+BM+CP & AK+BN+CQ & AL+BO+CR \\ DJ+EM+FP & DK+EN+FQ & DL+EO+FR \\ GJ+HM+IP & GK+HN+IQ & GL+HO+IR \\ \end{pmatrix}[/math]

It is important to note that in order to multiply matrices, the number of columns in the first matrix MUST equal the number of rows in the second matrix. The size of the product matrix is the number of rows in the first matrix x the number of columns in the second matrix.

The "mod" operation is also fairly straightforward. Essentially, it finds the remainder after dividing. For example, [math]153 \bmod 26 [/math] is equal to the remainder of [math]153 / 26[/math], which is 23. On a scientific calculator, this is found by dividing the two numbers, subtracting the integer value from the answer, and multiplying the decimals by the number after "mod" (in this case, 26). Therefore, the process would be:

[math]153/26=5.884615385[/math]

[math]5.884615385-5=0.884615385[/math]

[math]0.884615385*26=23[/math]

The rest of the encoding of the message is shown below.

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} S \\ C \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 18 \\ 2 \end{pmatrix}=\begin{pmatrix} 412 \\ 196 \end{pmatrix}\bmod 26=\begin{pmatrix} 22 \\ 14 \end{pmatrix}=\begin{pmatrix} W \\ O \end{pmatrix}[/math]

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} I \\ E \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 8 \\ 4 \end{pmatrix}=\begin{pmatrix} 208 \\ 112 \end{pmatrix}\bmod 26=\begin{pmatrix} 0 \\ 8 \end{pmatrix}=\begin{pmatrix} A \\ I \end{pmatrix}[/math]

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} N \\ C \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 13 \\ 2 \end{pmatrix}=\begin{pmatrix} 302 \\ 146 \end{pmatrix}\bmod 26=\begin{pmatrix} 16 \\ 16 \end{pmatrix}=\begin{pmatrix} Q \\ Q \end{pmatrix}[/math]

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} E \\ O \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 4 \\ 14 \end{pmatrix}=\begin{pmatrix} 200 \\ 152 \end{pmatrix}\bmod 26=\begin{pmatrix} 18 \\ 22 \end{pmatrix}=\begin{pmatrix} S \\ W \end{pmatrix}[/math]

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} L \\ Y \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 11 \\ 24 \end{pmatrix}=\begin{pmatrix} 434 \\ 302 \end{pmatrix}\bmod 26=\begin{pmatrix} 18 \\ 16 \end{pmatrix}=\begin{pmatrix} S \\ Q \end{pmatrix}[/math]

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} M \\ P \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 12 \\ 15 \end{pmatrix}=\begin{pmatrix} 384 \\ 240 \end{pmatrix}\bmod 26=\begin{pmatrix} 20 \\ 6 \end{pmatrix}=\begin{pmatrix} U \\ G \end{pmatrix}[/math]

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} I \\ A \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 8 \\ 0 \end{pmatrix}=\begin{pmatrix} 176 \\ 80 \end{pmatrix}\bmod 26=\begin{pmatrix} 20 \\ 2 \end{pmatrix}=\begin{pmatrix} U \\ C \end{pmatrix}[/math]

[math] \begin{pmatrix} W & I \\ K & I \end{pmatrix}*\begin{pmatrix} D \\ Z \end{pmatrix}=\begin{pmatrix} 22 & 8 \\ 10 & 8 \end{pmatrix}*\begin{pmatrix} 3 \\ 25 \end{pmatrix}=\begin{pmatrix} 226 \\ 230 \end{pmatrix}\bmod 26=\begin{pmatrix} 18 \\ 22 \end{pmatrix}=\begin{pmatrix} S \\ W \end{pmatrix}[/math]

The encoded message is WOAIQQSWSQUGUCSW.

3x3 matrix encryption works in the same way. This example will encrypt "EDIT THE WIKI" using the key "BEE FLY BUG". First, split up the plaintext into groups of three, which becomes EDI TTH EWI KIZ. Once again, the last group has a Z added to make it a group of three.

[math] \begin{pmatrix} B & E & E \\ F & L & Y \\ B & U & G \end{pmatrix}*\begin{pmatrix} E \\ D \\ I \\ \end{pmatrix}=\begin{pmatrix} 1 & 4 & 4 \\ 5 & 11 & 24 \\ 1 & 20 & 6 \end{pmatrix}*\begin{pmatrix} 4 \\ 3 \\ 8 \end{pmatrix}=\begin{pmatrix} 48 \\ 245 \\ 112 \end{pmatrix}\bmod 26=\begin{pmatrix} 22 \\ 11 \\ 8 \end{pmatrix}=\begin{pmatrix} W \\ L \\ I \end{pmatrix}[/math]

[math] \begin{pmatrix} B & E & E \\ F & L & Y \\ B & U & G \end{pmatrix}*\begin{pmatrix} T \\ T \\ H \\ \end{pmatrix}=\begin{pmatrix} 1 & 4 & 4 \\ 5 & 11 & 24 \\ 1 & 20 & 6 \end{pmatrix}*\begin{pmatrix} 19 \\ 19 \\ 7 \end{pmatrix}=\begin{pmatrix} 123 \\ 472 \\ 441 \end{pmatrix}\bmod 26=\begin{pmatrix} 19 \\ 4 \\ 25 \end{pmatrix}=\begin{pmatrix} T \\ E \\ Z \end{pmatrix}[/math]

[math] \begin{pmatrix} B & E & E \\ F & L & Y \\ B & U & G \end{pmatrix}*\begin{pmatrix} E \\ W \\ I \\ \end{pmatrix}=\begin{pmatrix} 1 & 4 & 4 \\ 5 & 11 & 24 \\ 1 & 20 & 6 \end{pmatrix}*\begin{pmatrix} 4 \\ 22 \\ 8 \end{pmatrix}=\begin{pmatrix} 124 \\ 454 \\ 492 \end{pmatrix}\bmod 26=\begin{pmatrix} 20 \\ 12 \\ 24 \end{pmatrix}=\begin{pmatrix} U \\ M \\ Y \end{pmatrix}[/math]

[math] \begin{pmatrix} B & E & E \\ F & L & Y \\ B & U & G \end{pmatrix}*\begin{pmatrix} K \\ I \\ Z \\ \end{pmatrix}=\begin{pmatrix} 1 & 4 & 4 \\ 5 & 11 & 24 \\ 1 & 20 & 6 \end{pmatrix}*\begin{pmatrix} 10 \\ 8 \\ 25 \end{pmatrix}=\begin{pmatrix} 142 \\ 738 \\ 320 \end{pmatrix}\bmod 26=\begin{pmatrix} 12 \\ 10 \\ 8 \end{pmatrix}=\begin{pmatrix} M \\ K \\ I \end{pmatrix}[/math]

The encoded message is WLITEZUMYMKI.

When given 4 corresponding plaintext and ciphertext create two sets of equations and solve them. For example if ABCD plaintext corresponds to DCBA and you have to find the encryption key [math]\begin{pmatrix} A & B \\ C & D \\ \end{pmatrix}[/math] create 2 matrices with AB and CD [math]\begin{pmatrix} 0\\ 1\\ \end{pmatrix}[/math] [math]\begin{pmatrix} 2\\ 3\\ \end{pmatrix}[/math] You get 0A plus 1B = 3 and 0C plus 1D = 2 2A plus 3B = 1 and 2C plus 3D = 0 With 0A plus 1B = 3 times 3 is 0A plus 3B = 9 2A plus 3B = 3 minus (0A plus 3B = 9 2A = -6 mod 26 or 2A=20 A value = 10 Repeat for other values

Running Key Cipher

The running key cipher is a variant of the Vigenère Cipher. Rather than using a word as a key, a sentence/paragraph is used as the key. Essentially, instead of repeating a word multiple times as the key, a sentence/paragraph constitutes as the key and is used continuously. If the test was made with Toebes, then the four standard documents used to create a question using the Running Key Cipher are:

  • The first line of the Gettysburg Address
  • The first line/paragraph of the Declaration of Independence
  • The first line of the United States Consitution
  • The first line of the Magna Carta (in Latin)

In the event that a question encoded with the running key cipher asks you to decode the phrase but does not give the key for it, then one has to use one of the documents given on the reference sheet (if applicable) and plug them all in to determine which of the documents is the key. If they give the key but do not give the text of the key (ex. "a famous quote by George Washington"), then it is probably best to skip the question.

RSA Cipher

Choose two primes [math]p[/math] and [math]q[/math].

Compute [math]n = pq[/math].

Compute the least common multiple of [math]p-1[/math] and [math]q-1[/math], and call it [math]\lambda(n)[/math].

Choose an integer [math]e[/math] coprime to [math]\lambda(n)[/math].

Compute the inverse [math]d[/math] of [math]e[/math] modulo [math]\lambda(n)[/math].

Now, say that Alice wants to receive from Bob a message. Alice sends Bob her public key (n, e) through a reliable channel. Bob translates his message M to an integer m, and then converts it to ciphertext using [math]c \equiv m^e mod n[/math].

Alice decodes it using [math]m \equiv c^d mod n[/math].


Sir Arthur Conan Doyle's Cipher from The Adventure of the Dancing Men

While not explicitly stated in the rules, the Dancing Men cipher has appeared in previous tests and possibly may appear as a bonus question in future tests. The Dancing Men cipher is a monoalphabetic substitution cipher with spaces where each letter is represented by a dancing man. A man holding a flag indicates the end of a word. In the story, messages encrypted with this cipher were sent to a woman named Elsie, Sherlock Holmes solved the cipher using that E is the most common letter, and that Elsie's name would likely appear. Since the cipher may be easily decrypted if all the dancing men are memorized, there are a few patterns to help remember them. O and A, R and I, and T and E are flipped. T and E are symmetrical about a vertical axis. N and S have the same legs and right arm. The substitution chart is found below.

Dancing Men Cipher

An example of the Dancing Men cipher is listed below.

DancingMenCipherExample.png contains the message "NOTARIES", which conveniently shows the patterns listed above.

Note: The Dancing Men cipher is not included in 2019 rules. However, it is a common part of tests from past years' trial events.

External Links

Trial event rules
2016 Nationals
2018 trial rules
Cryptogram Workbook (lots of practice problems, 139 pages)
Mono-alphabetic Substitution Cipher Practice
Game-like Cryptogram Practice
Cipher Tools and Practice Tests
Cipher Solver. Can be used to find common words for specific patters.