Transposition, product ciphers and one-time pads

"""Rail fence and columnar transposition on the GTU 3161606 practical 10 cases, and the Handbook's Example 7.43."""


def rail_fence(text, rails, decrypt=False):
    """Write the letters in a zigzag over the rails and read the rails in order (or undo it)."""
    pattern, r, step = [], 0, 1
    for _ in text:  # the rail of each position: 0, 1, ..., rails - 1, then back
        pattern.append(r)
        if rails > 1:
            if r == 0:
                step = 1
            elif r == rails - 1:
                step = -1
            r += step
    order = sorted(range(len(text)), key=lambda i: (pattern[i], i))  # positions, rail by rail
    if not decrypt:
        return "".join(text[i] for i in order)
    out = [""] * len(text)
    for ch, i in zip(text, order):
        out[i] = ch
    return "".join(out)


def columnar(text, key, filler="XYZ", decrypt=False):
    """Write the text in rows under the key's digits; read the columns in the order the digits give."""
    width = len(key)
    order = sorted(range(width), key=lambda c: (key[c], c))  # the column labelled 1 first, then 2 ...
    if decrypt:
        rows = len(text) // width
        columns = {c: text[k * rows:(k + 1) * rows] for k, c in enumerate(order)}
        return "".join(columns[c][r] for r in range(rows) for c in range(width))
    text += filler[: -len(text) % width]
    rows = [text[i:i + width] for i in range(0, len(text), width)]
    for row in rows:
        print("   ", " ".join(row))
    return "".join(row[c] for c in order for row in rows)


print("rail fence, 2 rails: Meetme ->", rail_fence("MEETME", 2), "->", rail_fence(rail_fence("MEETME", 2), 2, True))
print("rail fence, 3 rails: MEETATNOON ->", rail_fence("MEETATNOON", 3))
print("columnar, key 4312567, rows under the key:")
secret = columnar("ATTACKPOSTPONEDUNTILTWOAM", "4312567")
print("ciphertext:", secret)
print("decrypted: ", columnar(secret, "4312567", decrypt=True))

# Handbook Example 7.43: a fixed permutation of 6 positions, e = (6 4 1 3 5 2).
e = (6, 4, 1, 3, 5, 2)
print("CAESAR under e = (6 4 1 3 5 2):", "".join("CAESAR"[i - 1] for i in e))

rail fence, 2 rails: Meetme -> MEMETE -> MEETME
rail fence, 3 rails: MEETATNOON -> MAOETTONEN
columnar, key 4312567, rows under the key:
    A T T A C K P
    O S T P O N E
    D U N T I L T
    W O A M X Y Z
ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ
decrypted:  ATTACKPOSTPONEDUNTILTWOAMXYZ
CAESAR under e = (6 4 1 3 5 2): RSCEAA

// Rail fence and columnar transposition in JavaScript, on the same GTU 3161606 practical 10 cases.

/** The rail of every position: 0, 1, ..., rails - 1, then back up, and again. */
function railPattern(length, rails) {
  const pattern = [];
  let r = 0;
  let step = 1;
  for (let i = 0; i < length; i++) {
    pattern.push(r);
    if (rails > 1) {
      if (r === 0) step = 1;
      else if (r === rails - 1) step = -1;
      r += step;
    }
  }
  return pattern;
}

function railFence(text, rails, decrypt = false) {
  const pattern = railPattern(text.length, rails);
  const order = [...text].map((_, i) => i).sort((a, b) => pattern[a] - pattern[b] || a - b);
  if (!decrypt) return order.map((i) => text[i]).join('');
  const out = new Array(text.length);
  order.forEach((i, k) => (out[i] = text[k]));
  return out.join('');
}

function columnar(text, key, filler = 'XYZ', decrypt = false) {
  const width = key.length;
  const order = [...key].map((_, c) => c).sort((a, b) => key[a].localeCompare(key[b]) || a - b);
  if (decrypt) {
    const rows = text.length / width;
    const columns = {};
    order.forEach((c, k) => (columns[c] = text.slice(k * rows, (k + 1) * rows)));
    let out = '';
    for (let r = 0; r < rows; r++) for (let c = 0; c < width; c++) out += columns[c][r];
    return out;
  }
  const padded = text + filler.slice(0, (width - (text.length % width)) % width);
  let out = '';
  for (const c of order) for (let r = 0; r < padded.length / width; r++) out += padded[r * width + c];
  return out;
}

console.log('rail fence, 2 rails:', railFence('MEETME', 2), '->', railFence(railFence('MEETME', 2), 2, true));
const secret = columnar('ATTACKPOSTPONEDUNTILTWOAM', '4312567');
console.log('columnar, key 4312567:', secret);
console.log('decrypted:', columnar(secret, '4312567', 'XYZ', true));

rail fence, 2 rails: MEMETE -> MEETME
columnar, key 4312567: TTNAAPTMTSUOAODWCOIXKNLYPETZ
decrypted: ATTACKPOSTPONEDUNTILTWOAMXYZ

"""Telling transposition from substitution by two numbers, then finding a rail-fence key by common letter pairs."""
from collections import Counter

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ENGLISH = [8.04, 1.54, 3.06, 3.99, 12.51, 2.30, 1.96, 5.49, 7.26, 0.16, 0.67, 4.14, 2.53,
           7.09, 7.60, 2.00, 0.11, 6.12, 6.54, 9.25, 2.71, 0.99, 1.92, 0.19, 1.73, 0.09]  # Handbook, Figure 7.5
COMMON_PAIRS = {"AN", "AT", "ED", "EN", "ER", "ES", "HE", "IN", "ON", "OR", "RE", "ST", "TE", "TH", "TI"}  # Figure 7.6
PASSAGE = (
    "When the first heavy rain reached the coast, the old bridge by the station was closed, "
    "and every bus on the morning route had to wait. The driver of the last bus told his "
    "passengers about his grandfather, who built fishing boats in a village south of the river "
    "and never once let water into a hull. He described how the wood was chosen, how the planks "
    "were bent over a slow fire and how the seams were packed with cotton and oil. By the time "
    "the bridge opened again, the children at the back could name every part of a boat, and "
    "nobody on the bus minded the delay. Their parents had missed the start of work, but they "
    "agreed that it was the most useful hour the route had ever given them. That evening, a few "
    "of them walked down to the river to watch the boats come in."
)
PLAIN = "".join(ch for ch in PASSAGE.upper() if ch in UPPER)


def rail_fence(text, rails, decrypt=False):
    pattern, r, step = [], 0, 1
    for _ in text:
        pattern.append(r)
        if r == 0:
            step = 1
        elif r == rails - 1:
            step = -1
        r += step
    order = sorted(range(len(text)), key=lambda i: (pattern[i], i))
    if not decrypt:
        return "".join(text[i] for i in order)
    out = [""] * len(text)
    for ch, i in zip(text, order):
        out[i] = ch
    return "".join(out)


def columnar(text, key):
    order = sorted(range(len(key)), key=lambda c: (key[c], c))
    text += "X" * (-len(text) % len(key))  # fill the last row
    return "".join(text[r + c] for c in order for r in range(0, len(text), len(key)))


def shift(text, k):
    return "".join(UPPER[(UPPER.index(ch) + k) % 26] for ch in text)


def substitute(text, alphabet):
    return "".join(alphabet[UPPER.index(ch)] for ch in text)


def vigenere(text, key):
    return "".join(UPPER[(UPPER.index(ch) + UPPER.index(key[i % len(key)])) % 26] for i, ch in enumerate(text))


def index_of_coincidence(text):
    counts = Counter(text)
    return sum(f * (f - 1) for f in counts.values()) / (len(text) * (len(text) - 1))


def chi_squared(text):
    """Distance from English letter counts, as the text stands: small means the letters are English letters."""
    counts = Counter(text)
    n = len(text)
    return sum((counts[ch] - n * f / 100) ** 2 / (n * f / 100) for ch, f in zip(UPPER, ENGLISH))


def common_pair_share(text):
    return sum(text[i:i + 2] in COMMON_PAIRS for i in range(len(text) - 1)) / (len(text) - 1)


print("cipher                   index  chi-squared  common pairs")
for name, text in [
    ("none, the plaintext", PLAIN),
    ("rail fence, 5 rails", rail_fence(PLAIN, 5)),
    ("columnar, key 4312567", columnar(PLAIN, "4312567")),
    ("Caesar, key 3", shift(PLAIN, 3)),
    ("keyword, KRYPTOS", substitute(PLAIN, "KRYPTOSABCDEFGHIJLMNQUVWXZ")),
    ("Vigenere, MONSOON", vigenere(PLAIN, "MONSOON")),
]:
    print(f"{name:23} {index_of_coincidence(text):.4f} {chi_squared(text):10.1f} {100 * common_pair_share(text):9.1f} %")

# The rail fence has one small key: try every rail count and keep the decryption richest in common pairs.
secret = rail_fence(PLAIN, 5)
for rails in range(2, 11):
    share = common_pair_share(rail_fence(secret, rails, decrypt=True))
    print(f"  decrypted with {rails:2} rails: {100 * share:4.1f} % of adjacent pairs are common English pairs")

cipher                   index  chi-squared  common pairs
none, the plaintext     0.0692       51.5      26.7 %
rail fence, 5 rails     0.0692       51.5      10.1 %
columnar, key 4312567   0.0683       57.0       9.5 %
Caesar, key 3           0.0692     4050.3       2.8 %
keyword, KRYPTOS        0.0692     1207.2       8.4 %
Vigenere, MONSOON       0.0483     3364.1       1.3 %
  decrypted with  2 rails: 11.1 % of adjacent pairs are common English pairs
  decrypted with  3 rails: 11.3 % of adjacent pairs are common English pairs
  decrypted with  4 rails: 12.1 % of adjacent pairs are common English pairs
  decrypted with  5 rails: 26.7 % of adjacent pairs are common English pairs
  decrypted with  6 rails: 13.6 % of adjacent pairs are common English pairs
  decrypted with  7 rails: 12.6 % of adjacent pairs are common English pairs
  decrypted with  8 rails: 11.4 % of adjacent pairs are common English pairs
  decrypted with  9 rails: 11.3 % of adjacent pairs are common English pairs
  decrypted with 10 rails:  9.6 % of adjacent pairs are common English pairs

"""A classical product cipher: a Caesar shift (substitution), then a columnar transposition. Two weak steps make a
cipher that still keeps every letter count, and one changed plaintext letter changes one ciphertext letter."""
from collections import Counter

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
KEY = "4312567"


def shift(text, k):
    return "".join(UPPER[(UPPER.index(ch) + k) % 26] for ch in text)


def columnar(text, key):
    order = sorted(range(len(key)), key=lambda c: (key[c], c))
    text += "X" * (-len(text) % len(key))
    return "".join(text[r + c] for c in order for r in range(0, len(text), len(key)))


def product(text):
    return columnar(shift(text, 3), KEY)


def index_of_coincidence(text):
    counts = Counter(text)
    return sum(f * (f - 1) for f in counts.values()) / (len(text) * (len(text) - 1))


plain = "ATTACKPOSTPONEDUNTILTWOAMXYZ"
secret = product(plain)
print("plaintext: ", plain)
print("ciphertext:", secret)
print(f"index of coincidence: {index_of_coincidence(plain):.4f} before, {index_of_coincidence(secret):.4f} after")

# Diffusion: change one plaintext letter at a time and count the ciphertext letters that change.
changed = []
for i in range(len(plain)):
    other = plain[:i] + UPPER[(UPPER.index(plain[i]) + 1) % 26] + plain[i + 1:]
    changed.append(sum(a != b for a, b in zip(product(other), secret)))
print(f"one plaintext letter changed: {min(changed)} to {max(changed)} ciphertext letters change, of {len(secret)}")

plaintext:  ATTACKPOSTPONEDUNTILTWOAMXYZ
ciphertext: WWQDDSWPWVXRDRGZFRLANQOBSHWC
index of coincidence: 0.0476 before, 0.0476 after
one plaintext letter changed: 1 to 1 ciphertext letters change, of 28

// Diffusion in a modern block cipher: AES-128 on one block, the first block of NIST SP 800-38A's example F.1.1.
// ECB here only calls the block cipher once on one 16-byte block, to measure it; never encrypt data with ECB
// (ASVS 5.0, requirement 11.3.1). The key is the published test key of the example, not a secret.
import { createCipheriv } from 'node:crypto';

const KEY = Buffer.from('2b7e151628aed2a6abf7158809cf4f3c', 'hex');
const PLAINTEXT = Buffer.from('6bc1bee22e409f96e93d7e117393172a', 'hex');

function aesBlock(key, block) {
  const cipher = createCipheriv('aes-128-ecb', key, null);
  cipher.setAutoPadding(false);
  return Buffer.concat([cipher.update(block), cipher.final()]);
}

function bitsDifferent(a, b) {
  let n = 0;
  for (let i = 0; i < a.length; i++) {
    for (let x = a[i] ^ b[i]; x; x >>= 1) n += x & 1;
  }
  return n;
}

const ciphertext = aesBlock(KEY, PLAINTEXT);
console.log('ciphertext:', ciphertext.toString('hex'));
console.log('matches SP 800-38A F.1.1:', ciphertext.toString('hex') === '3ad77bb40d7a3660a89ecaf32466ef97');

// Flip each of the 128 plaintext bits in turn and count the ciphertext bits that change.
const changed = [];
for (let bit = 0; bit < 128; bit++) {
  const block = Buffer.from(PLAINTEXT);
  block[bit >> 3] ^= 0x80 >> (bit & 7);
  changed.push(bitsDifferent(aesBlock(KEY, block), ciphertext));
}
const mean = changed.reduce((a, b) => a + b, 0) / changed.length;
console.log(`one plaintext bit flipped: ${Math.min(...changed)} to ${Math.max(...changed)} of 128 ciphertext bits change, ${mean.toFixed(2)} on average`);

ciphertext: 3ad77bb40d7a3660a89ecaf32466ef97
matches SP 800-38A F.1.1: true
one plaintext bit flipped: 49 to 77 of 128 ciphertext bits change, 63.83 on average

"""The one-time pad on bytes: perfect secrecy when the pad is random, as long as the message and used once, and
what leaks when a pad is used twice. The pads are fresh random bytes on every run, so only facts about them print."""
import secrets


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b, strict=True))


message = b"ATTACK AT DAWN"
pad = secrets.token_bytes(len(message))  # from the operating system's secure random generator
ciphertext = xor(message, pad)
print("the ciphertext is", len(ciphertext), "bytes, the length of the message, and decrypts back:", xor(ciphertext, pad) == message)

# Perfect secrecy: for any other message of the same length there is a pad that turns this ciphertext into it.
other = b"RETREAT AT TEN"
other_pad = xor(ciphertext, other)
print("another pad, just as likely as the real one, turns the same ciphertext into", xor(ciphertext, other_pad).decode())

# A pad used twice: the two ciphertexts XORed together give the two messages XORed together, with no pad left.
first, second = b"PAY 500 TO ACCOUNT 1111", b"PAY 900 TO ACCOUNT 2222"
pad = secrets.token_bytes(len(first))
c1, c2 = xor(first, pad), xor(second, pad)
leak = xor(c1, c2)
print("c1 XOR c2 equals p1 XOR p2:", leak == xor(first, second))
print("c1 XOR c2:", leak.hex(" "))
print("zero bytes, where the two messages agree:", leak.count(0), "of", len(leak))

the ciphertext is 14 bytes, the length of the message, and decrypts back: True
another pad, just as likely as the real one, turns the same ciphertext into RETREAT AT TEN
c1 XOR c2 equals p1 XOR p2: True
c1 XOR c2: 00 00 00 00 0c 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 03 03 03
zero bytes, where the two messages agree: 18 of 23

// AES-CTR, the one-time pad made practical: a keystream from a key and a counter. NIST SP 800-38A's example F.5.1
// first, then a reused counter, the test that catches it and the fix that passes the test. The key and counters of
// part 2 are fresh random values, so the printed results are the test's verdicts.

const hex = (bytes) => Buffer.from(bytes).toString('hex');
const fromHex = (text) => Uint8Array.from(Buffer.from(text, 'hex'));
const encode = (text) => new TextEncoder().encode(text);
const xor = (a, b) => a.map((x, i) => x ^ b[i]);

// 1. The published vector: key, initial counter block and two plaintext blocks of SP 800-38A F.5.1.
const vectorKey = await crypto.subtle.importKey('raw', fromHex('2b7e151628aed2a6abf7158809cf4f3c'), 'AES-CTR', false, ['encrypt']);
const vector = await crypto.subtle.encrypt(
  { name: 'AES-CTR', counter: fromHex('f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff'), length: 64 },
  vectorKey,
  fromHex('6bc1bee22e409f96e93d7e117393172aae2d8a571e03ac9c9eb76fac45af8e51'),
);
console.log('first block:', hex(vector).slice(0, 32));
console.log('SP 800-38A F.5.1, both blocks match:', hex(vector) === '874d6191b620e3261bef6864990db6ce9806f66b7970fdff8617187bb9fffdff');

// 2. A counter used for two messages. The test: XOR the two ciphertexts. Under one keystream that gives the XOR of
// two texts, whose bytes are all below 0x80; under different keystreams about half the bytes are 0x80 or above.
const reuseSuspected = (c1, c2) => xor(c1, c2).filter((b) => b >= 0x80).length / c1.length < 0.1;
const key = await crypto.subtle.generateKey({ name: 'AES-CTR', length: 128 }, false, ['encrypt']);
const ctr = async (counter, data) => new Uint8Array(await crypto.subtle.encrypt({ name: 'AES-CTR', counter, length: 64 }, key, data));
const p1 = encode('PAY 500 TO ACCOUNT 1111 BY 5 PM');
const p2 = encode('PAY 900 TO ACCOUNT 2222 BY 6 PM');
const counter = crypto.getRandomValues(new Uint8Array(16));
const c1 = await ctr(counter, p1);
const c2 = await ctr(counter, p2);
console.log('same counter: c1 XOR c2 equals p1 XOR p2:', hex(xor(c1, c2)) === hex(xor(p1, p2)), '| reuse suspected:', reuseSuspected(c1, c2));
const c2Fresh = await ctr(crypto.getRandomValues(new Uint8Array(16)), p2);
console.log('a fresh counter block for the second message: reuse suspected:', reuseSuspected(c1, c2Fresh));

first block: 874d6191b620e3261bef6864990db6ce
SP 800-38A F.5.1, both blocks match: true
same counter: c1 XOR c2 equals p1 XOR p2: true | reuse suspected: true
a fresh counter block for the second message: reuse suspected: false

// A keystream hides a message but does not protect it: flipping a ciphertext bit flips the same plaintext bit. The
// test flips one bit and expects decryption to fail. AES-CTR fails the test; AES-GCM, which adds a 16-byte tag,
// passes it. Keys and nonces are fresh random values on every run.

const encode = (text) => new TextEncoder().encode(text);
const message = encode('PAY 500 TO ACCOUNT 1111 BY 5 PM');

async function tamperTest(name, algorithm, params) {
  const key = await crypto.subtle.generateKey({ name: algorithm, length: 128 }, false, ['encrypt', 'decrypt']);
  const ciphertext = new Uint8Array(await crypto.subtle.encrypt(params, key, message));
  ciphertext[4] ^= 0x01; // one bit of byte 4, the digit 5, flipped in transit
  try {
    const opened = new TextDecoder().decode(await crypto.subtle.decrypt(params, key, ciphertext));
    console.log(`${name}: FAIL, the changed ciphertext decrypts to "${opened}"`);
  } catch (error) {
    console.log(`${name}: pass, decryption refused (${error.name})`);
  }
}

await tamperTest('AES-CTR', 'AES-CTR', { name: 'AES-CTR', counter: crypto.getRandomValues(new Uint8Array(16)), length: 64 });
await tamperTest('AES-GCM', 'AES-GCM', { name: 'AES-GCM', iv: crypto.getRandomValues(new Uint8Array(12)) });

AES-CTR: FAIL, the changed ciphertext decrypts to "PAY 400 TO ACCOUNT 1111 BY 5 PM"
AES-GCM: pass, decryption refused (OperationError)