commit 03dd3fff2cc0dc99e3e1483b0da90134fe91d391
parent 40037995c712bf6989e25d68354f45bf22d1173d
Author: Jack Sangdahl <jack@pngu.org>
Date: Mon, 29 Sep 2025 09:53:01 -0600
challenge 2: fixed xor
Diffstat:
3 files changed, 121 insertions(+), 0 deletions(-)
diff --git a/lib/xor.c b/lib/xor.c
@@ -0,0 +1,64 @@
+#include "xor.h"
+
+int xor(const unsigned char *s1, const size_t s1_len, const unsigned char *s2,
+ const size_t s2_len, unsigned char **res) {
+ *res = (unsigned char *)malloc((s1_len + 1) * sizeof(char));
+ size_t i;
+ for (i = 0; i < s1_len; i++)
+ (*res)[i] = s1[i] ^ s2[i % s2_len];
+ (*res)[i] = 0;
+ return 0;
+}
+
+char find_single_byte_xor(const unsigned char *input, const size_t input_len,
+ int (*score_function)(const unsigned char *,
+ const size_t)) {
+ unsigned char *buf;
+ int curr_best_key = 0, best_score = 0, curr_score;
+ for (unsigned char i = 0; i < UINT8_MAX; i++) {
+ unsigned char key_table[] = {i};
+ xor(input, input_len, key_table, sizeof(char), &buf);
+ curr_score = score_function(buf, input_len);
+ if (curr_score > best_score) {
+ curr_best_key = i;
+ best_score = curr_score;
+ }
+ }
+ return curr_best_key;
+}
+
+int hamming_distance(const unsigned char *s1, const size_t s1_len,
+ const unsigned char *s2, const size_t s2_len) {
+ if (s1_len != s2_len)
+ return -1;
+ int score = 0, curr_xor = 0;
+ for (size_t i = 0; i < s1_len; i++) {
+ curr_xor = s1[i] ^ s2[i];
+ do
+ score += curr_xor & 1;
+ while (curr_xor >>= 1);
+ }
+ return score;
+}
+
+int find_xor_key_len(const unsigned char *input, const size_t input_len,
+ const size_t min_key_len, const size_t max_key_len) {
+ size_t dist_len = 0, best_key_len = 0, max_dist, best_dist = INT_MAX;
+ float dist = 0.0;
+ for (size_t key_len = min_key_len; key_len <= max_key_len; key_len++) {
+ dist = 0.0;
+ max_dist = (input_len / key_len) - 1;
+ for (dist_len = 0; dist_len < max_dist; dist_len++) {
+ int hamming =
+ hamming_distance(input + (key_len * dist_len), key_len,
+ input + (key_len * (dist_len + 1)), key_len);
+ dist += (float)hamming / key_len;
+ }
+ dist /= (float)max_dist;
+ if (dist < best_dist) {
+ best_dist = dist;
+ best_key_len = key_len;
+ }
+ }
+ return best_key_len;
+}
diff --git a/lib/xor.h b/lib/xor.h
@@ -0,0 +1,17 @@
+#pragma once
+
+#include <limits.h>
+#include <stdlib.h>
+
+int xor (const unsigned char *s1, const size_t s1_len, const unsigned char *s2,
+ const size_t s2_len, unsigned char **res);
+
+char find_single_byte_xor(const unsigned char *input, const size_t input_len,
+ int (*score_function)(const unsigned char *,
+ const size_t));
+
+int hamming_distance(const unsigned char *s1, const size_t s1_len,
+ const unsigned char *s2, const size_t s2_len);
+
+int find_xor_key_len(const unsigned char *input, const size_t input_len,
+ const size_t min_key_len, const size_t max_key_len);
diff --git a/src/02_fixed_xor.c b/src/02_fixed_xor.c
@@ -0,0 +1,40 @@
+// Fixed XOR
+#include "hex.h"
+#include "xor.h"
+#include <assert.h>
+#include <stdio.h>
+
+/*
+ * write a function that takes two equal-length buffers and produces their xor
+ * combination. if your functi-n works properly, then when you feed it the
+ * string: 1c0111001f010100061a024b53535009181c
+ * ... after hex decoding, and when XOR'd against:
+ * 686974207468652062756c6c277320657965
+ * ... should produce:
+ * 746865206b696420646f6e277420706c6179
+ */
+
+int main(void) {
+ static char *input1 = "1c0111001f010100061a024b53535009181c";
+ static char *input2 = "686974207468652062756c6c277320657965";
+ static char *output = "746865206b696420646f6e277420706c6179";
+ char *input1_ascii, *input2_ascii;
+ int input1_len = hex_to_ascii(input1, &input1_ascii);
+ int input2_len = hex_to_ascii(input2, &input2_ascii);
+ unsigned char *xord = NULL;
+ char *hex = NULL;
+ int res = xor((unsigned char *)input1_ascii, input1_len,
+ (unsigned char *)input2_ascii, input2_len, &xord);
+ if (res > -1) {
+ ascii_to_hex((char *)xord, &hex);
+ printf("Input: %s\n", xord);
+ printf("Output: %s\n", hex);
+ printf("Expected: %s\n", output);
+ assert(!strcmp(hex, output));
+ }
+ free(input1_ascii);
+ free(input2_ascii);
+ free(xord);
+ free(hex);
+ return 0;
+}
