Project Euler/59 - Revision history

Unknown user: /* Shorter Direct Approach */

2025-04-14T22:06:29Z

Shorter Direct Approach

← Older revision		Revision as of 22:06, 14 April 2025
Line 49:		Line 49:


	~~<s>83912<~~/s>		===Shortest Brute Force Approach===

			Given that (a) the solution that the above approach yielded seemed correct, but slightly fishy (the plaintext obtained from the ciphertext had weird capitalization and punctuation issues), and (b) we know the size of the possible key space is only 26^3 = 17,576 (because the problem states the key consists of 3 lowercase letters), we can just use brute force to figure out which key is correct.

			Brute force approach:
			* Generate all possible 3-letter keys
			* Use the generated 3-letter key to convert the ciphertext to plaintext
			* Check if the resulting plaintext is English-like, add to list of possible secret keys
			* Review output by hand to identify the correct secret key

			==Code==

			See https://git.charlesreid1.com/cs/euler/src/branch/main/java/Problem059.java

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Shorter Direct Approach */

2025-04-14T21:34:03Z

Shorter Direct Approach

← Older revision		Revision as of 21:34, 14 April 2025
Line 47:		Line 47:
	* For each bigram data structure, for each most common English bigram, determine corresponding secret keys, add it to secret keys histogram		* For each bigram data structure, for each most common English bigram, determine corresponding secret keys, add it to secret keys histogram
	* List of most frequent bigrams: https://mathcenter.oxford.emory.edu/site/math125/englishLetterFreqs/		* List of most frequent bigrams: https://mathcenter.oxford.emory.edu/site/math125/englishLetterFreqs/


			<s>83912</s>

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Shorter Direct Approach */

2025-04-14T21:07:49Z

Shorter Direct Approach

← Older revision		Revision as of 21:07, 14 April 2025
Line 46:		Line 46:
	* Generate bigrams, keeping track of relative positions separately (1-2, 2-3, 3-1)		* Generate bigrams, keeping track of relative positions separately (1-2, 2-3, 3-1)
	* For each bigram data structure, for each most common English bigram, determine corresponding secret keys, add it to secret keys histogram		* For each bigram data structure, for each most common English bigram, determine corresponding secret keys, add it to secret keys histogram
			* List of most frequent bigrams: https://mathcenter.oxford.emory.edu/site/math125/englishLetterFreqs/

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Shorter Direct Approach */

2025-04-14T21:04:41Z

Shorter Direct Approach

← Older revision		Revision as of 21:04, 14 April 2025
Line 44:		Line 44:
	Attempting to short-circuit and simplify the problem:		Attempting to short-circuit and simplify the problem:
	* This problem uses the Vigenere cipher with a 3-letter key		* This problem uses the Vigenere cipher with a 3-letter key
	* Generate bigrams, keeping track of relative ~~position~~		* Generate bigrams, keeping track of relative positions separately (1-2, 2-3, 3-1)
	* Store bigrams from 1-2 ~~separate from~~ 2-3 ~~separate from~~ 3-1.		* For each bigram data structure, for each most common English bigram, determine corresponding secret keys, add it to secret keys histogram
	* For ~~the most common bigrams from 1-2~~, ~~run down the list of~~ most common ~~bigrams in~~ English, ~~figure out~~ corresponding secret ~~key. Make a~~ histogram ~~of possible keys~~

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Approach */

2025-04-14T21:00:03Z

Approach

← Older revision		Revision as of 21:00, 14 April 2025
Line 40:		Line 40:
	(Part 1 should be enough to get us a key...)		(Part 1 should be enough to get us a key...)

	~~Attempted~~ short-circuit:		===Shorter Direct Approach===

			Attempting to short-circuit and simplify the problem:
	* This problem uses the Vigenere cipher with a 3-letter key		* This problem uses the Vigenere cipher with a 3-letter key
	* ~~Chunk the message into 3s~~, ~~and line them up vertically. Generate~~ bigrams from 1-2 ~~and~~ 2-3.		* Generate bigrams, keeping track of relative position
	* ~~Treat histogram of~~ bigrams ~~for pos~~ 1-2 ~~separate from pos 2-3~~		* Store bigrams from 1-2 separate from 2-3 separate from 3-1.
			* For the most common bigrams from 1-2, run down the list of most common bigrams in English, figure out corresponding secret key. Make a histogram of possible keys

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Approach */

2025-04-14T20:51:52Z

Approach

← Older revision		Revision as of 20:51, 14 April 2025
Line 16:		Line 16:

	==Approach==		==Approach==

	~~Attempted short-circuit:~~
	* This uses the Vigenere cipher with a 3-letter key
	* Should be simple/short enough that we can crack it manually
	* To do this, chunk into 3s, and line up vertically. Look for any patterns that repeat.

	Part 1:		Part 1:
Line 44:		Line 39:

	(Part 1 should be enough to get us a key...)		(Part 1 should be enough to get us a key...)

			Attempted short-circuit:
			* This problem uses the Vigenere cipher with a 3-letter key
			* Chunk the message into 3s, and line them up vertically. Generate bigrams from 1-2 and 2-3.
			* Treat histogram of bigrams for pos 1-2 separate from pos 2-3

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Approach */

2025-04-14T20:46:37Z

Approach

← Older revision		Revision as of 20:46, 14 April 2025
Line 16:		Line 16:

	==Approach==		==Approach==

			Attempted short-circuit:
			* This uses the Vigenere cipher with a 3-letter key
			* Should be simple/short enough that we can crack it manually
			* To do this, chunk into 3s, and line up vertically. Look for any patterns that repeat.

	Part 1:		Part 1:

Unknown user: /* Approach */

2025-04-14T20:25:35Z

Approach

← Older revision		Revision as of 20:25, 14 April 2025
Line 17:		Line 17:
	==Approach==		==Approach==

	~~Create list of most common bigrams in English language~~		Part 1:

	Sliding window of 2 letters at a time		* Create list of most common bigrams in English language
			* Sliding window of 2 letters at a time
	For each pair of letters in the ciphertext, for each most common bigram, find the corresponding secret key at that position that would cause this bigram to become the most common bigram		* For each pair of letters in the ciphertext, for each most common bigram, find the corresponding secret key at that position that would cause this bigram to become the most common bigram
			* Keep track of weights too - not just which secret key value would lead to the given bigram, but how common that bigram is
	~~Can weight each~~ secret key by how common ~~the~~ bigram is		* Keep track of potential secret key values and weights in 3 data structures, one for each potential secret key character; we know which one to use based on character position

	<s>		<s>
	Part 2:		Part 2:
			* Create list of most common trigrams in English language
	Create list of most common trigrams in English language		* Sliding window of 3 letters at a time
			* For each triplet of letters, for each most common trigram, find the corresponding secret key at that position that would cause this trigram to become the most common trigram
	Sliding window of 3 letters at a time

	For each triplet of letters, for each most common trigram, find the corresponding secret key at that position that would cause this trigram to become the most common trigram
	</s>		</s>

	<s>		<s>
	Part 3;		Part 3:
			* Create list of most common letters in English language, plus weights
	Create list of most common letters in English language, plus weights		* For each "letter" in the ciphertext, for each most common letter, find the corresponding secret key at that position that would cause the ciphertext to become the most common letter
			</s>

	~~For each "letter" in the ciphertext, for each most common letter, find the corresponding secret~~ key ~~at that position that would cause the ciphertext to become the most common letter~~		(Part 1 should be enough to get us a key...)
	~~</s>~~

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

Unknown user: /* Approach */

2025-04-14T20:23:04Z

Approach

@@ Line 16: / Line 16: @@
 ==Approach==
 ==Flags==
 {{ProjectEulerFlag}}

Unknown user: /* Problem Statement */

2025-04-14T17:57:44Z

Problem Statement

← Older revision		Revision as of 17:57, 14 April 2025
Line 1:		Line 1:
	==Problem Statement==		==Problem Statement==

			This question is about a method of encrypting ASCII text.

			Each character in ASCII has some representation (e.g., A=65, *=42, k=107)

			Encryption technique is to take text file, convert bytes to ASCII, and XOR each byte with a character from a secret key

			Password method: use a password in place of a secret one-time pad; shorter than message, so repeated cyclically throughout method.

			You are given a file with encrypted ascii codes, knowledge that plain text must contain common English words, and told encryption key consists of 3 lowercase characters. Decrypt message, find sum of ascii values in original text.

			Sample file looks like this: <code>36,22,80,0,0,4,23,...</code>

	Link: https://projecteuler.net/problem=59		Link: https://projecteuler.net/problem=59

			==Approach==

	==Flags==		==Flags==

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}