std::gcd and std::lcm

Use case

Detect cipher block size, find XOR key period.

Explanation

std::gcd and std::lcm compute greatest common divisor and least common multiple. GCD of ciphertext lengths suggests the block size. LCM of XOR key lengths reveals when the combined keystream repeats (might be useful for breaking multi-key XOR).

Code

#include <iostream>
#include <numeric>

int main() {
  size_t len1 = 48;
  size_t len2 = 64;
  size_t len3 = 80;

  auto blockSize = std::gcd(std::gcd(len1, len2), len3);
  std::cout << "Block size: " << blockSize << " bytes.\n";

  size_t key1Len = 7;
  size_t key2Len = 5;

  auto period = std::lcm(key1Len, key2Len);
  std::cout << "Pattern repeats every " << period << " bytes.\n";

  return 0;
}

View on GitHub.

Output

$ ./src/c++17/build/std-gcd-std-lcm
Block size: 16 bytes.
Pattern repeats every 35 bytes.