XOR, bitwise operations, and the modular arithmetic that builds on the same algebra
XOR (^) is usually introduced as a bit trick, but it’s actually the smallest complete algebra a programming language hands you. Combined with the identity element, it has an inverse, it commutes, it’s associative — that’s a group in which every element is its own inverse. That one fact explains why XOR encrypts and decrypts with the same operation, why you can XOR things in any order, and where the edge cases hide. The rest of the bitwise family (AND, OR, NOT, shifts) is the tooling that implements it, and modular arithmetic is the multiplicative version of the same idea: a ring of residue classes where the coprime elements form a group, each with an inverse. That second structure is what RSA and friends are built on. This post checks each piece by running it.
XOR is its own inverse
The four properties worth knowing about any operator are: is there a do-nothing element? does the operation undo itself? does order matter? does grouping matter? XOR scores on all of them, and because the domain is small, we don’t have to take it on faith — we can check every pair:
# XOR's group properties, checked exhaustively over a small domain.
N = 16 # check all pairs in 0..15
# identity: x ^ 0 == x
identity = all((x ^ 0) == x for x in range(N))
# self-inverse: (x ^ k) ^ k == x
self_inverse = all(((x ^ k) ^ k) == x for x in range(N) for k in range(N))
# commutative: x ^ k == k ^ x
commutative = all((x ^ k) == (k ^ x) for x in range(N) for k in range(N))
# associative: (x ^ k) ^ m == x ^ (k ^ m)
associative = all(((x ^ k) ^ m) == (x ^ (k ^ m))
for x in range(N) for k in range(N) for m in range(N))
print("identity (x^0 == x) :", identity)
print("self-inverse :", self_inverse)
print("commutative :", commutative)
print("associative :", associative)
print()
# The payoff: encrypt with a key, decrypt by XORing with the same key again.
message = "the xor door opens and closes with the same key"
key = 0x5A
enc = [c ^ key for c in message.encode()]
dec = bytes(b ^ key for b in enc).decode()
print("plaintext :", message)
print("ciphertext (hex):", " ".join(f"{b:02x}" for b in enc))
print("decrypted :", dec)
print("roundtrip ok:", dec == message)
print()
# XOR-swap without a temporary -- and the edge case the self-inverse property creates.
a, b = 12, 42
print("before:", a, b)
a ^= b
b ^= a
a ^= b
print("after :", a, b)
x = 7
x ^= x # x is now 0: the same property that makes XOR undoable is what destroys the value
print("x ^= x turns", 7, "into", x)identity (x^0 == x) : True
self-inverse : True
commutative : True
associative : True
plaintext : the xor door opens and closes with the same key
ciphertext (hex): 2e 32 3f 7a 22 35 28 7a 3e 35 35 28 7a 35 2a 3f 34 29 7a 3b 34 3e 7a 39 36 35 29 3f 29 7a 2d 33 2e 32 7a 2e 32 3f 7a 29 3b 37 3f 7a 31 3f 23
decrypted : the xor door opens and closes with the same key
roundtrip ok: True
before: 12 42
after : 42 12
x ^= x turns 7 into 0The exhaustiveness is the point: with N = 16 that’s 16² = 256 pairs and 16³ = 4096 triples, so commutativity and associativity are verified for every value in the domain, not sampled. The roundtrip printout shows the practical consequence — the same key that produced the hex garbage is the one that recovers the sentence, and no bookkeeping is needed, because applying an operation twice is how you undo it.
That “apply twice to undo” idea has a sharp edge though. The classic three-line XOR swap works precisely because of self-inverse, but watch the last line of the output: x ^= x turned 7 into 0. The XOR-swap trick breaks if a and b are the same storage location, because the first a ^= b zeroes a before the second line can recover anything. The property that makes XOR safe to reuse is exactly the property that makes aliasing catastrophic — the same rule, two faces.
The bitwise family around it
XOR is one member of a small family of per-bit operators, and the rest behave like set operations on the bits: AND selects, OR adds, NOT complements, and shifts move bits — which is multiplication and division by powers of two. The idiomatic uses are building and editing a flags word:
# Bitwise operations: AND/OR as set operations, NOT as complement,
# shifts as multiply/divide by 2, XOR as per-bit toggle.
def show(x, width=8):
return format(x, f"0{width}b")
# --- building a flags word (think of a C-style option mask) ---
READ, WRITE, EXEC, APPEND = 0b0001, 0b0010, 0b0100, 0b1000
perm = READ | EXEC
print("READ | EXEC :", show(perm))
perm |= APPEND # add a bit
print("add APPEND (|=) :", show(perm))
perm &= ~EXEC # clear a bit
print("clear EXEC (&=~) :", show(perm))
perm ^= WRITE # toggle a bit
print("toggle WRITE (^=) :", show(perm))
perm ^= WRITE # toggle back
print("toggle again :", show(perm))
print("has EXEC? (perm & EXEC):", bool(perm & EXEC))
print()
# --- shifts: multiply/divide by powers of two, and pack fields into one int ---
age, score = 13, 55 # 5 bits, 6 bits
packed = (score << 5) | age
print("packed:", show(packed, 11))
print("age =", packed & 0b11111, " (mask low 5 bits)")
print("score=", (packed >> 5) & 0b111111, " (shift then mask 6 bits)")
print()
# --- XOR as a per-bit toggle: flip exactly the bits the mask says to ---
x = 0b11001001
mask = 0b11000110
print("x :", show(x))
print("mask :", show(mask))
print("x ^ m :", show(x ^ mask), " <- only the bits the mask raises get flipped")READ | EXEC : 00000101
add APPEND (|=) : 00001101
clear EXEC (&=~) : 00001001
toggle WRITE (^=) : 00001011
toggle again : 00001001
has EXEC? (perm & EXEC): False
packed: 11011101101
age = 13 (mask low 5 bits)
score= 55 (shift then mask 6 bits)
x : 11001001
mask : 11000110
x ^ m : 00001111 <- only the bits the mask raises get flippedRead the first block column by column and the pattern is simple: |= only ever sets bits, &= ~ only ever clears them, ^= flips exactly the masked bits. Toggling WRITE twice gets 00001001 back — the self-inverse property again, now applied to individual bit positions. XOR is the only one of the three because it’s the only one where the operation is symmetric about the current value: AND and OR know the current bit, XOR doesn’t care.
The packing example is shifts doing arithmetic’s job: (score << 5) | age lays the two fields end to end into one integer, and unpacking is shift-then-mask in the opposite direction. The masks (0b11111, 0b111111) have to be exactly as wide as the field they’re extracting — a mask that’s too narrow silently drops high bits instead of erroring, which is the kind of bug the fixed-width 00001111 formatting is good at exposing.
Modular arithmetic: the same algebra, multiplicatively
XOR gave us a situation where doing and undoing are the same operation. Modular arithmetic gives us that structure on multiplication: work with residues modulo n, and the values coprime to n form a group where every element has a multiplicative inverse. The pieces, in dependency order: primes, coprimality, Euler’s totient, Euler’s theorem, modular inverses, and fast exponentiation.
# Modular arithmetic: the algebra most later cryptography is built on.
def gcd(a, b):
while b:
a, b = b, a % b
return a
def is_prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
def phi(n):
# Euler's totient: how many of 1..n-1 are coprime to n
return sum(1 for k in range(1, n) if gcd(k, n) == 1)
def modinv(a, m):
# extended Euclidean: the x with a*x = 1 (mod m)
t, new_t = 0, 1
r, new_r = m, a % m
while new_r:
q = r // new_r
t, new_t = new_t, t - q * new_t
r, new_r = new_r, r - q * new_r
return t % m
def powmod(base, exp, mod):
# square-and-multiply
result, base = 1, base % mod
while exp:
if exp & 1:
result = (result * base) % mod
base = (base * base) % mod
exp >>= 1
return result
# --- primes and coprimality ---
primes = [n for n in range(2, 30) if is_prime(n)]
print("primes below 30 :", primes)
print("phi(17) :", phi(17), " (p is prime, so every k in 1..16 is coprime: phi(p) = p-1)")
print("phi(341) :", phi(341), " (341 = 11*31, composites lose coprimality)")
print()
# --- Euler's theorem: gcd(a, n) == 1 => a^phi(n) == 1 (mod n) ---
n, a = 341, 34
print("gcd(34, 341) :", gcd(a, n))
print("34^phi(341) mod 341 =", pow(a, phi(n), n), " <- Euler's theorem predicts 1")
print("34^340 mod 341 =", pow(a, n - 1, n), " <- Fermat's n-1 shortcut breaks: 341 is composite")
print()
# --- modular inverse ---
a, p = 3, 11
inv = modinv(a, p)
print("inverse of 3 mod 11 =", inv, " because 3 *", inv, "=", 3 * inv, "which is", 3 * inv % p, "mod 11")
print()
# --- modular exponentiation: our powmod vs the built-in, on a big exponent ---
print("123456789^1000 mod 1000003")
print(" powmod(): ", powmod(123456789, 1000, 1000003))
print(" built-in pow():", pow(123456789, 1000, 1000003))
print()
# --- mini RSA: primes -> phi -> coprime e -> modular inverse d -> exponents ---
p, q = 47, 59
n = p * q
m = phi(n)
e = 17
print("mini RSA: p =", p, " q =", q, " n =", n, " phi(n) =", m)
print("e =", e, " gcd(e, phi(n)) =", gcd(e, m))
d = modinv(e, m)
print("d = e^-1 mod phi(n) =", d, " check e*d mod phi(n) =", e * d % m)
pt = 5
ct = powmod(pt, e, n)
back = powmod(ct, d, n)
print("plaintext", pt, "-> ciphertext", ct, "-> decrypted", back, " ok:", back == pt)primes below 30 : [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
phi(17) : 16 (p is prime, so every k in 1..16 is coprime: phi(p) = p-1)
phi(341) : 300 (341 = 11*31, composites lose coprimality)
gcd(34, 341) : 1
34^phi(341) mod 341 = 1 <- Euler's theorem predicts 1
34^340 mod 341 = 56 <- Fermat's n-1 shortcut breaks: 341 is composite
inverse of 3 mod 11 = 4 because 3 * 4 = 12 which is 1 mod 11
123456789^1000 mod 1000003
powmod(): 592077
built-in pow(): 592077
mini RSA: p = 47 q = 59 n = 2773 phi(n) = 2668
e = 17 gcd(e, phi(n)) = 1
d = e^-1 mod phi(n) = 157 check e*d mod phi(n) = 1
plaintext 5 -> ciphertext 508 -> decrypted 5 ok: TrueThree things in that output deserve attention. First, phi(17) = 16 versus phi(341) = 300: for a prime every smaller positive integer is coprime to it, so the totient collapses to p - 1. For the composite 341 (= 11·31) the totient drops to 300 — the group is smaller, and that’s the number that drives the theorem, not n - 1.
Second, the Fermat comparison is a trap this run walks into deliberately. Euler’s theorem says a^phi(n) ≡ 1 (mod n) for any a coprime to n — prime or composite — and 34^300 mod 341 = 1 confirms it. The more familiar shortcut a^(n-1) ≡ 1 (mod n) only holds when n is prime (Fermat’s little theorem), and with n = 341 it gives 56, not 1. If you ever find yourself reaching for n - 1 as “the exponent that gets you back to 1”, that’s the failure mode.
Third, the final block strings the whole dependency chain together the way RSA does: pick primes p, q; form n = p·q and phi(n); choose e coprime to phi(n); compute d = e⁻¹ mod phi(n) (the 157, with 17·157 ≡ 1 (mod 2668)); then encryption is powmod(pt, e, n) and decryption is powmod(ct, d, n). The 5 → 508 → 5 roundtrip works for the same structural reason the XOR roundtrip did: the decryption operation is defined as the inverse of the encryption one, and the group guarantees that inverse exists. RSA just finds it with modinv instead of by applying the same operation twice.
Note that powmod and Python’s three-argument pow agree on 123456789^1000 mod 1000003 — both print 592077. The hand-written square-and-multiply loop is the algorithm; the built-in is what a real program calls.
Takeaway
Both halves of this post are the same algebra wearing different clothes. XOR over integers: identity is 0, every element is its own inverse, everything commutes and associates — so the operation undoes itself, in any order, no bookkeeping. Multiplication over residues coprime to n: identity is 1, every element has an inverse (Euler’s theorem guarantees it, modinv computes it), and raising to e is undone by raising to d. When you hit a construct later that seems to be “magic” — parity checksums, flag manipulation, a ciphertext that decrypts with a different-looking exponent — the first question worth asking is: what’s the group, what’s the inverse, and where’s the identity?