Commit notes from Killer Queen CTF 2021

Signed-off-by: Malfurious <m@lfurio.us>

2 files changed, 98 insertions, 0 deletions

diff --git a/docs/crypto/rsa.txt b/docs/crypto/rsa.txt
new file mode 100644
index 0000000..a047f07
--- /dev/null
+++ b/docs/crypto/rsa.txt
@@ -0,0 +1,43 @@
+Brief summary of RSA algorithm / crypto system
+----------------------------------------------
+# https://www.cs.utexas.edu/~mitra/honors/soln.html
+
+Choose 2 large, random prime numbers, p and q.
+
+n = p * q
+phi = (p-1) * (q-1)
+
+Choose e, such that `1 < e < phi` and e and phi are coprime (*) (**) (***)
+Compute d, such that `e * d mod phi == 1` (****)
+
+Public key = (e, n)
+Private key = (d, n)
+
+cyphertext =  plaintext ^ e mod n
+plaintext  = cyphertext ^ d mod n
+
+
+(*) It is important for e and phi to be coprime, to prevent ambiguous
+    decryption.  See https://crypto.stackexchange.com/questions/12255/
+
+(**) A very common value for e is (the prime) 65537
+
+(***) RSA can become more vulnerable to cracking with low values of e.
+      See https://crypto.stackexchange.com/questions/6713/.
+      TODO: Explain the attack here.
+
+(****) Calculate d using modular inverse (see below...)
+
+
+
+Python tips
+-----------
+Implementations for fast modular exponentiation and modular inverse already
+exist in Python, via the pow() function.
+
+pow() supports a third argument, which is the modulus value: pow(b, e, n).
+
+To perform fast mod expo for encryption, use pow(plaintext,  e, n)
+                     ... for decryption, use pow(cyphertext, d, n)
+
+To calculate mod inverse, use pow(e, -1, phi).
diff --git a/templates/image_manip/png_crc.c b/templates/image_manip/png_crc.c
new file mode 100644
index 0000000..dfe9d44
--- /dev/null
+++ b/templates/image_manip/png_crc.c
@@ -0,0 +1,55 @@
+/* PNG Chunk layout:
+   4-byte: length (of data) // Excluded from CRC
+   4-byte: type (ASCII alphabetic)
+   ?-byte: chunk data
+   4-byte: crc (see below...)
+
+   References:
+   http://www.libpng.org/pub/png/spec/1.2/PNG-Structure.html
+   http://www.libpng.org/pub/png/spec/1.2/PNG-CRCAppendix.html */
+
+
+/* Table of CRCs of all 8-bit messages. */
+unsigned long crc_table[256];
+int crc_table_computed = 0;
+
+/* Make the table for a fast CRC. */
+void make_crc_table(void)
+{
+  unsigned long c;
+  int n, k;
+
+  for (n = 0; n < 256; n++) {
+    c = (unsigned long) n;
+    for (k = 0; k < 8; k++) {
+      if (c & 1)
+        c = 0xedb88320L ^ (c >> 1);
+      else
+        c = c >> 1;
+    }
+    crc_table[n] = c;
+  }
+  crc_table_computed = 1;
+}
+
+/* Update a running CRC with the bytes buf[0..len-1]--the CRC should be
+   initialized to all 1's, and the transmitted value is the 1's complement of
+   the final running CRC (see the crc() routine below). */
+unsigned long update_crc(unsigned long crc, const unsigned char *buf, int len)
+{
+  unsigned long c = crc;
+  int n;
+
+  if (!crc_table_computed)
+    make_crc_table();
+  for (n = 0; n < len; n++) {
+    c = crc_table[(c ^ buf[n]) & 0xff] ^ (c >> 8);
+  }
+  return c;
+}
+
+/* Return the CRC of the bytes buf[0..len-1]. */
+unsigned long crc(const unsigned char *buf, int len)
+{
+  return update_crc(0xffffffffL, buf, len) ^ 0xffffffffL;
+}