summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorsiddharth <s@ricketyspace.net>2021-06-06 15:33:57 -0400
committersiddharth <s@ricketyspace.net>2021-06-06 15:33:57 -0400
commit6bedba61ee5cf5309111d7e0b69177c7be499ec7 (patch)
tree55c4c0396165baeb5d3346c363aae5326e857e4c
parent4af3ded113719f61b7249a33358af01568098c5c (diff)
challenge: do challenge 19
-rw-r--r--challenge/c19.go216
-rw-r--r--cryptopals.go2
2 files changed, 218 insertions, 0 deletions
diff --git a/challenge/c19.go b/challenge/c19.go
new file mode 100644
index 0000000..84ff57b
--- /dev/null
+++ b/challenge/c19.go
@@ -0,0 +1,216 @@
+// Copyright © 2021 rsiddharth <s@ricketyspace.net>
+// SPDX-License-Identifier: ISC
+
+package challenge
+
+import (
+ "fmt"
+
+ "ricketyspace.net/cryptopals/lib"
+)
+
+func C19() {
+ texts := []string{
+ "SSBoYXZlIG1ldCB0aGVtIGF0IGNsb3NlIG9mIGRheQ==",
+ "Q29taW5nIHdpdGggdml2aWQgZmFjZXM=",
+ "RnJvbSBjb3VudGVyIG9yIGRlc2sgYW1vbmcgZ3JleQ==",
+ "RWlnaHRlZW50aC1jZW50dXJ5IGhvdXNlcy4=",
+ "SSBoYXZlIHBhc3NlZCB3aXRoIGEgbm9kIG9mIHRoZSBoZWFk",
+ "T3IgcG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==",
+ "T3IgaGF2ZSBsaW5nZXJlZCBhd2hpbGUgYW5kIHNhaWQ=",
+ "UG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==",
+ "QW5kIHRob3VnaHQgYmVmb3JlIEkgaGFkIGRvbmU=",
+ "T2YgYSBtb2NraW5nIHRhbGUgb3IgYSBnaWJl",
+ "VG8gcGxlYXNlIGEgY29tcGFuaW9u",
+ "QXJvdW5kIHRoZSBmaXJlIGF0IHRoZSBjbHViLA==",
+ "QmVpbmcgY2VydGFpbiB0aGF0IHRoZXkgYW5kIEk=",
+ "QnV0IGxpdmVkIHdoZXJlIG1vdGxleSBpcyB3b3JuOg==",
+ "QWxsIGNoYW5nZWQsIGNoYW5nZWQgdXR0ZXJseTo=",
+ "QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=",
+ "VGhhdCB3b21hbidzIGRheXMgd2VyZSBzcGVudA==",
+ "SW4gaWdub3JhbnQgZ29vZCB3aWxsLA==",
+ "SGVyIG5pZ2h0cyBpbiBhcmd1bWVudA==",
+ "VW50aWwgaGVyIHZvaWNlIGdyZXcgc2hyaWxsLg==",
+ "V2hhdCB2b2ljZSBtb3JlIHN3ZWV0IHRoYW4gaGVycw==",
+ "V2hlbiB5b3VuZyBhbmQgYmVhdXRpZnVsLA==",
+ "U2hlIHJvZGUgdG8gaGFycmllcnM/",
+ "VGhpcyBtYW4gaGFkIGtlcHQgYSBzY2hvb2w=",
+ "QW5kIHJvZGUgb3VyIHdpbmdlZCBob3JzZS4=",
+ "VGhpcyBvdGhlciBoaXMgaGVscGVyIGFuZCBmcmllbmQ=",
+ "V2FzIGNvbWluZyBpbnRvIGhpcyBmb3JjZTs=",
+ "SGUgbWlnaHQgaGF2ZSB3b24gZmFtZSBpbiB0aGUgZW5kLA==",
+ "U28gc2Vuc2l0aXZlIGhpcyBuYXR1cmUgc2VlbWVkLA==",
+ "U28gZGFyaW5nIGFuZCBzd2VldCBoaXMgdGhvdWdodC4=",
+ "VGhpcyBvdGhlciBtYW4gSSBoYWQgZHJlYW1lZA==",
+ "QSBkcnVua2VuLCB2YWluLWdsb3Jpb3VzIGxvdXQu",
+ "SGUgaGFkIGRvbmUgbW9zdCBiaXR0ZXIgd3Jvbmc=",
+ "VG8gc29tZSB3aG8gYXJlIG5lYXIgbXkgaGVhcnQs",
+ "WWV0IEkgbnVtYmVyIGhpbSBpbiB0aGUgc29uZzs=",
+ "SGUsIHRvbywgaGFzIHJlc2lnbmVkIGhpcyBwYXJ0",
+ "SW4gdGhlIGNhc3VhbCBjb21lZHk7",
+ "SGUsIHRvbywgaGFzIGJlZW4gY2hhbmdlZCBpbiBoaXMgdHVybiw=",
+ "VHJhbnNmb3JtZWQgdXR0ZXJseTo=",
+ "QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=",
+ }
+ // English alphabets ordered by frequency
+ // (https://mdickens.me/typing/letter_frequency.html)
+ ascii := []byte{
+ ' ', 'e', 't', 'a', 'o', 'i', 'n', 's', 'r', 'h', 'l', 'd',
+ 'c', 'u', 'm', 'f', 'g', 'p', 'y', 'w', 'b', ',', '.',
+ 'v', 'k', '-', '"', '_', '\'', 'x', ')', '(', ';', '0', 'j',
+ '1', 'q', '=', '2', ':', 'z', '/', '*', '!', '?', '$', '3',
+ '5', '>', '{', '}', '4', '9', '[', ']', '8', '6', '7', '\\',
+ '+', '|', '&', '<', '%', '@', '#', '^', '`', '~',
+ }
+ // Key: ASCII character; Value: score
+ asciiScores := make(map[byte]int, 0)
+ for pos, a := range ascii {
+ asciiScores[a] = 255 - pos
+ // Also add the uppercase version of ascii
+ // character if it exists.
+ au := lib.ByteToUpper(a)
+ if a != au {
+ asciiScores[au] = 255 - pos
+ }
+ }
+
+ // Utility functions.
+ cipherStreamByteGroups := func(ciphers [][]byte) map[int][]byte {
+ kbg := make(map[int][]byte, 0)
+ for i := 0; i < len(ciphers); i++ {
+ for j := 0; j < len(ciphers[i]); j++ {
+ if _, ok := kbg[j]; !ok {
+ kbg[j] = make([]byte, 0)
+ }
+ kbg[j] = append(kbg[j], ciphers[i][j])
+ }
+ }
+ return kbg
+ }
+ crackOutputBlockByteForGroup := func(pos int, g []byte) byte {
+ po := make([][]byte, len(g)) // Potential Output block bytes
+ for i, c := range g {
+ po[i] = make([]byte, 0)
+ for _, a := range ascii {
+ o := c ^ a
+ po[i] = append(po[i], o)
+
+ // Also try the uppercase version of ascii
+ // character if it exists.
+ au := lib.ByteToUpper(a)
+ if a != au {
+ o := c ^ au
+ po[i] = append(po[i], o)
+ }
+ }
+ }
+ co := lib.BytesInCommon(po) // Common Output Block bytes.
+ if len(co) < 1 {
+ return 0 // NUL
+ }
+ if len(co) == 1 {
+ return co[0]
+ }
+ tob := byte(0) // The Output Block byte.
+ bscr := 0 // Best score.
+ for _, o := range co {
+ scr := 0
+ for _, c := range g {
+ p := c ^ o
+ if s, ok := asciiScores[p]; ok {
+ scr += s
+ }
+ if pos == 0 && lib.ByteIsUpper(p) {
+ scr += 1
+ }
+ }
+ if scr > bscr {
+ bscr = scr
+ tob = o
+ }
+ }
+ return tob
+ }
+
+ // Make ciphers from plain text data.
+ ciphers := make([][]byte, len(texts))
+ key, err := lib.RandomBytes(16)
+ if err != nil {
+ fmt.Printf("Error generating key %v", err)
+ return
+ }
+ nonce := uint64(lib.RandomInt(0, 10))
+ for i, b64 := range texts {
+ text := lib.Base64ToBytes(b64)
+ ciphers[i], err = lib.AESEncryptCTR(text, key, lib.AESGenCTRFunc(nonce))
+ if err != nil {
+ fmt.Printf("Error encrypting text:%d: %v", i, err)
+ return
+ }
+ }
+
+ // Group the cipher streams into groups by position of the cipher
+ // byte in the stream.
+ cbg := cipherStreamByteGroups(ciphers)
+
+ // Try get crack and get the output block stream.
+ obs := make(map[int]byte, 0) // Output Block Stream map.
+ for pos, cgrp := range cbg {
+ obs[pos] = crackOutputBlockByteForGroup(pos, cgrp)
+ }
+
+ // Decipher cipher using the output block stream.
+ for _, cipher := range ciphers {
+ for i, c := range cipher {
+ p := c ^ obs[i]
+ fmt.Printf("%c", p)
+ }
+ fmt.Printf("\n")
+ }
+}
+
+// Output:
+// I have met them at close of day
+// Coming with vivid faces
+// From counter or desk among grey
+// Eighteenth-century houses.
+// I have passed with a nod of the heae
+// Or polite meaningless words,
+// Or have lingered awhile and said
+// Polite meaningless words,
+// And thought before I had done
+// Of a mocking tale or a gibe
+// To please a companion
+// Around the fire at the club,
+// Being certain that they and I
+// But lived where motley is worn:
+// All changed, changed utterly:
+// A terrible beauty is born.
+// That woman's days were spent
+// In ignorant good will,
+// Her nights in argument
+// Until her voice grew shrill.
+// What voice more sweet than hers
+// When young and beautiful,
+// She rode to harriers?
+// This man had kept a school
+// And rode our winged horse.
+// This other his helper and friend
+// Was coming into his force;
+// He might have won fame in the end,
+// So sensitive his nature seemed,
+// So daring and sweet his thought.
+// This other man I had dreamed
+// A drunken, vain-glorious lout.
+// He had done most bitter wrong
+// To some who are near my heart,
+// Yet I number him in the song;
+// He, too, has resigned his part
+// In the casual comedy;
+// He, too, has been changed in his tus
+// Transformed utterly:
+// A terrible beauty is born.
+
+// Stuff the program did not get correctly:
+// 1. On the 5th line, 'heae' -> 'head'
+// 2. On the 38th line, 'tus ' -> 'turn'
diff --git a/cryptopals.go b/cryptopals.go
index 222923d..4448d7e 100644
--- a/cryptopals.go
+++ b/cryptopals.go
@@ -55,5 +55,7 @@ func main() {
challenge.C17()
case 18:
challenge.C18()
+ case 19:
+ challenge.C19()
}
}