06 - Cryptography

Cryptography

Objectives: By the end of this topic, you will be able to…

• Apply encryption and decryption techniques with available tools
• Verify file integrity using hashes
• Understand differences between symmetric and asymmetric encryption
• Use public and private keys in a practical and secure manner
• Break a classical polyalphabetic cipher using frequency analysis and the Index of Coincidence
• Explain how salting and key derivation functions protect stored passwords

---

What is cryptography?

Cryptography is the discipline that studies techniques to protect information, ensuring its confidentiality, integrity, authenticity, and non-repudiation, even when transmitted over insecure channels.

Through mathematical algorithms, cryptography allows data to be encrypted (making it unreadable to unauthorized parties), integrity to be verified (detecting any alteration in transit), identities to be authenticated, and documents or messages to be digitally signed. It is a fundamental pillar of modern cybersecurity, used in HTTPS, encrypted emails, digital signatures, cryptocurrencies, VPNs, and secure storage.

These four goals connect back to the CIA triad from class 01: confidentiality and integrity are two of its three pillars, and authenticity and non-repudiation are the common extensions that pin down who produced a message and stop them denying it later. Cryptography is the main technical mechanism that enforces confidentiality and integrity in real systems.

Question

Cryptography protects confidentiality, integrity, authenticity, and non-repudiation, but not availability. If an attacker can neither read nor alter your encrypted traffic, what could they still do to disrupt a service that depends on it? Name one concrete example before continuing.

---

Classical cryptography (Caesar, Vigenere)

Classical methods serve as the foundation to understand substitution, transposition, and keys.

The Caesar Cipher replaces each letter with another shifted a fixed number of positions: with a shift of 3, A becomes D and B becomes E. Its simplicity is also its weakness: there are only 25 possible shifts, making it trivial to break by brute force.

The Vigenère Cipher improves on Caesar by using a keyword to define a different shift for each position in the plaintext, introducing the concept of a variable-length key. It is more resistant to brute force, and unlike Caesar it does not fall to a simple letter count, yet it is still classed as weak.

Both methods turn on the key, the value that controls encryption and decryption, and both aim for confusion, meaning the relationship between plaintext and ciphertext should be hard to unpick, though neither achieves much of it.

Question

A Caesar cipher has 25 possible keys; a Vigenère cipher with a six-letter key has more than 300 million. Brute force breaks the first instantly and the second not at all, yet Vigenère is still called weak. A single letter count fails against it because it interleaves several shifts. What property of the key defeats that defence, and what could you measure in the ciphertext to exploit it? If you cannot answer yet, the next section does.

---

Breaking classical ciphers: frequency analysis and the Index of Coincidence

Natural-language text is far from random. In English, E is about 12.7 percent of all letters, T about 9 percent, and A and O each around 8 percent, while J, Q, X and Z together account for under 1 percent. That uneven profile is a fingerprint of the language, and any cipher that replaces each letter with a single fixed substitute carries the fingerprint straight through to the ciphertext.

A Caesar cipher is exactly that kind of substitution. Adding a constant shift to every letter slides the whole frequency profile along the alphabet without changing its shape, so the most common letter in the ciphertext is still whatever E was mapped to. Count the letters in the ciphertext, take the most frequent one, and assume it came from E: if that letter sits at alphabet index i (with A = 0), the key is (i - 4) mod 26. This technique is called frequency analysis, and it turns a 25-key search into a single subtraction.

A Vigenère cipher resists a single letter-count because it rotates through several shifts, one per key position, blending several profiles together. The way in is that if the key length is k, then every k-th ciphertext letter was enciphered with the same shift. Collecting positions 0, k, 2k and so on into one group, positions 1, k+1, 2k+1 into the next, and so on, produces k groups that are each a plain Caesar cipher, breakable on their own. Splitting a polyalphabetic ciphertext by stride into several monoalphabetic ones is the core of the attack.

That leaves the problem of finding k. The Index of Coincidence solves it. The IoC of a text is the probability that two letters picked from it at random are the same letter; it is large when the letter distribution is lopsided and small when it is flat. English text sits near 0.065, while text with a uniform or random letter distribution sits near 0.038. When you split a Vigenère ciphertext by a candidate stride and the candidate matches the real key length, each group looks like ordinary English and its IoC rises toward 0.065; a wrong stride leaves the groups looking random near 0.038. Trying each candidate length and watching for the jump toward 0.065 is a dependable key-length estimator once the ciphertext runs to a few hundred letters.

Vigenère is breakable only because its key is shorter than the message and repeats. A one-time pad removes that weakness by using a key as long as the message, chosen at random and never reused, which Claude Shannon proved in 1949 gives perfect secrecy that no amount of computing power can break; it is rarely practical because the key is as bulky as the data it protects and still has to be delivered secretly.

Example

Take this Caesar ciphertext: GHIHQVH LQ GHSWK PHDQV VHYHUDO ODBHUV SURWHFW WKH VBVWHP. Count the letters, ignoring spaces: H occurs 11 times, more than any other. Assume it decrypts to E. H is at index 7, so the key is (7 - 4) mod 26 = 3. Shift every letter back by 3 and read the plaintext. Then notice that because this is a pure shift, the ciphertext’s Index of Coincidence is unchanged from the plaintext’s and stays near 0.065; only a cipher that applies more than one shift drives it down toward 0.038.

Question

As a Vigenère key gets longer, each stride group holds fewer letters for the same ciphertext length. Explain what that does to the amount of ciphertext the Index of Coincidence method needs to stay reliable. Then name the one cipher construction that no quantity of ciphertext will break, and say which property of its key makes it immune.

---

Symmetric encryption (AES)

Symmetric encryption uses the same secret key to encrypt and decrypt information. It is fast and efficient for large volumes of data.

AES (Advanced Encryption Standard) is a block cipher that processes data in 128-bit blocks and supports key sizes of 128, 192, or 256 bits. It is the modern standard that replaced DES, applying several rounds of substitution and mixing to each block.

Common modes of operation: ECB (Electronic Codebook) is not recommended because identical plaintext blocks produce identical ciphertext blocks, revealing patterns. CBC (Cipher Block Chaining) is more secure because it XORs each block with the previous ciphertext block using a random initialization vector (IV), so identical plaintext produces different ciphertext. GCM (Galois/Counter Mode) goes further, providing both confidentiality and authenticated encryption in a single pass.

Three details matter in practice. The initialization vector that CBC uses is not secret and travels in the clear alongside the ciphertext, but it must be unpredictable and must never be reused under the same key; its job is to make each encryption of the same plaintext come out different. CBC also protects confidentiality only, not integrity: it does not detect a ciphertext that was altered in transit, and flipping one bit of a ciphertext block flips the same bit in the next decrypted block without raising any error. GCM closes that gap with an authentication tag that decryption checks before it releases any data. One number worth remembering: AES works on 128-bit blocks, which is 16 bytes, so any block-level pattern a weak mode leaves in the output repeats on a 16-byte boundary.

Typical uses: file encryption, secure communications (VPN, HTTPS), storage of sensitive data.

Question

If you encrypt the same file twice with AES-256-CBC and the same password, the two ciphertext files come out completely different. Before reading on, say which value causes that and whether it is secret. Then predict what you would see instead if the mode were ECB.

---

Asymmetric cryptography (RSA)

Asymmetric cryptography employs a key pair: one public (for encryption) and one private (for decryption). Based on hard mathematical problems like factoring large integers.

RSA (Rivest-Shamir-Adleman):

• Widely used asymmetric algorithm
• Security based on the difficulty of factoring the product of two large primes
• Enables encryption, decryption, and digital signing

How it is used in practice: anything encrypted with the public key can be decrypted only with the matching private key, and anything signed with the private key can be verified by anyone holding the public key. RSA is far slower than AES and is never used to encrypt bulk data directly. A protocol such as TLS generates a random symmetric key, encrypts the actual traffic with AES, and uses RSA (or a Diffie-Hellman exchange) only to establish that one short symmetric key.

Common uses: establishing secure connections (SSL/TLS), secure key exchange, digital signature and authentication.

Question

If RSA is slow and, in TLS, only ever used to protect a symmetric key, why not skip it and share the symmetric key directly? State the problem the public/private split solves that a single shared secret cannot.

---

Public-key distribution and GPG

Asymmetric cryptography removes the need to share a secret key in advance, but it creates a new problem: you now have to obtain the other party’s public key, and you have to be sure it is really theirs. If an attacker who controls the channel replaces the public key you receive with their own, they can decrypt everything you send, read it, re-encrypt it with the real recipient’s key, and pass it along, with neither side noticing. This is a man-in-the-middle attack on key exchange, and it defeats the confidentiality that asymmetric encryption was supposed to provide.

The defence is to verify the key over a second, independent channel. Every public key has a fingerprint, a hash of the key short enough to read aloud or compare on screen. If you receive a key by email and then confirm its fingerprint with the owner in person or by phone, an attacker would have had to compromise both channels to substitute a key without being caught. Large systems automate this trust decision with certificate authorities (the model behind HTTPS) or a web of trust, but the underlying check never changes: bind a key to an identity through something the attacker does not control.

GPG (GNU Privacy Guard) is the standard command-line implementation of the OpenPGP standard. It maintains a keyring holding your own key pairs and the public keys of people you correspond with, and it performs encryption, decryption, signing, and signature verification against that keyring. When GPG reports a good signature on a message, it is asserting two things at once: the message has not changed since it was signed, and it was signed by the private key that matches a public key already in your keyring.

Question

You receive a correspondent’s public key as an email attachment, and their fingerprint in the text of the same email. Have you verified anything? If not, say what you would have to do instead, and why using a different channel is what makes the check meaningful.

---

Hash functions (MD5, SHA-1, SHA-256)

A hash function takes an input of any length and produces a fixed-length output (hash or digest), representing the “fingerprint” of the original content.

A cryptographic hash function is deterministic (the same input always gives the same digest) and fast to compute on any size of input. The two properties that carry the security weight are collision resistance, meaning it is computationally infeasible to find two different inputs with the same digest, and preimage resistance, meaning you cannot work backward from a digest to an input that produces it. A further behaviour, called the avalanche effect, follows from good design: changing a single bit of the input flips about half the bits of the output, and the two digests look entirely unrelated. This is why a hash detects tampering: there is no small change to a file that produces a small, plausible change to its digest.

The digest length is one of the most visible differences between algorithms. Running the same input through all three shows the output space growing with each generation:

import hashlib
 
data = b"hello"
print(hashlib.md5(data).hexdigest())     # 5d41402abc4b2a76b9719d911017c592
print(hashlib.sha1(data).hexdigest())    # aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
print(hashlib.sha256(data).hexdigest())  # 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

MD5 produces 32 hex characters (128 bits), SHA-1 produces 40 (160 bits), and SHA-256 produces 64 (256 bits). The larger the output space, the harder it is to find two inputs that collide.

Common algorithms:

Algorithm	Output	Status
MD5	128 bits	Obsolete, vulnerable to collisions
SHA-1	160 bits	Compromised
SHA-256	256 bits	Currently secure, widely used

Typical uses: file integrity verification, digital signatures, password storage (with salts and key derivation like bcrypt/scrypt/argon2).

Question

The table calls MD5 “obsolete, vulnerable to collisions” but does not call it preimage broken. If you are using a hash only to check that a file downloaded correctly, and not to defend against someone who deliberately crafted the file, does MD5’s collision weakness affect you? Explain the difference between the two threats before continuing.

---

Password storage: salting and key derivation

Storing a raw hash of a password looks safe, since a hash is not reversible, but two weaknesses make it fragile. First, identical passwords produce identical hashes, so an attacker who steals a password database immediately sees which users share a password, and can look every stolen hash up in a precomputed table of hash → password (a plain lookup table, or the more space-efficient rainbow table). Second, general-purpose hashes like SHA-256 are built to be fast, and fast is the wrong property here: a modern GPU computes billions of SHA-256 hashes per second, so trying every password up to a given length is cheap.

A salt fixes the first weakness. It is a random value, unique per password, mixed in before hashing and then stored in the clear next to the resulting hash. Because every stored hash used a different salt, a precomputed table is worthless (the attacker would need a separate table per salt), and identical passwords no longer collide in the database. The salt is not a secret and does not need to be; its only job is to be different every time.

A key derivation function fixes the second weakness. Algorithms such as PBKDF2, bcrypt, scrypt, and Argon2 take a password and a salt and deliberately run slowly, either by iterating an internal hash tens or hundreds of thousands of times or by demanding a large amount of memory. A delay of a fraction of a second is invisible to a legitimate login but multiplies the cost of a brute-force search by the same factor. The same construction turns a human-chosen passphrase into a full-strength key when you encrypt a file with a password: the tool runs a KDF over the passphrase and a stored salt, which is why a password-encrypted file carries a salt in its header.

Question

A salt is stored in plain text right next to the hash it protects, so stealing the database steals every salt too. Explain why the scheme still works. State exactly what the salt stops the attacker from doing, and what it does not stop.

---

Applications

Integrity verification

You already used SHA-256 to fingerprint evidence in class 03. The same mechanism secures software distribution: a project publishes the hash of a release next to the download, and anyone can recompute the hash of the file they received and compare. By the avalanche effect, any corruption or tampering changes the hash and is caught. Package managers apply this check automatically to every package they install.

Digital signature

A digital signature combines asymmetric cryptography and hash functions. The sender hashes the document and encrypts that hash with their private key, producing the signature. The receiver decrypts the signature with the sender’s public key, recomputes the hash independently, and confirms they match, proving both that the content was not altered and that it came from the claimed sender.

Basic obfuscation

Lightweight encryption or encoding is also used to hide recognizable strings such as credentials or command patterns inside binaries and scripts, a technique covered further in class 07.

Question

A digital signature proves who signed a document and that it has not changed since, but it does not keep the document secret. If you need both secrecy and proof of origin, what do you have to do, and does the order (sign then encrypt, or encrypt then sign) matter?

---

Hands-on lab

Requirements: Kali Linux, openssl, gpg, sha256sum, Python 3

Roles. Work in a pair. One of you is the Cryptographer: you create the protected artifacts (a checksummed document, the AES ciphertexts, a signed and encrypted message, the Vigenère cipher and one ciphertext). The other is the Cryptanalyst: you verify, inspect and attack those artifacts (check and break checksums, dump and compare ciphertexts, identify which mode leaks, verify signatures and fingerprints, break the Vigenère ciphertext). Each part below says which role runs which steps and names the artifact that crosses between you. In Part 3 you swap roles for a second round so both of you practise both sides. Every artifact one role hands the other must be listed in the submission.

Part 1: Data integrity with hash functions

The Cryptographer creates and protects the document; the Cryptanalyst verifies it and tests detection.

1. (Cryptographer) Create a file with known content. printf writes the text as given and cat prints a file back to the screen:

printf "This is a confidential document.\nAuthor: $(whoami)\nDate: $(date)\n" > document.txt
cat document.txt

2. (Cryptographer) Compute the SHA-256 hash and save it to a checksum file. sha256sum computes the digest of a file, and given a checksum file with -c it re-checks that the file still matches. This is how software distributors ship verified downloads:

sha256sum document.txt
sha256sum document.txt > document.txt.sha256
cat document.txt.sha256

Handoff. Send document.txt and document.txt.sha256 to the Cryptanalyst. Steps 3, 4 and 6 run on the Cryptanalyst’s received copy.

3. (Cryptanalyst) Verify integrity using the checksum file:

sha256sum -c document.txt.sha256

4. (Cryptanalyst) Compare the three most common hash algorithms side by side. md5sum and sha1sum work like sha256sum but produce shorter digests. Note the different digest lengths:

md5sum document.txt
sha1sum document.txt
sha256sum document.txt

The outputs are 32 hex characters (128 bits) for MD5, 40 for SHA-1, and 64 for SHA-256. Longer digests mean a larger output space, making collisions exponentially harder to find.

5. (Cryptographer) On your own copy, demonstrate the avalanche effect: change a single character with sed, the stream editor, and recompute all three digests:

sed 's/confidential/Confidential/' document.txt > document_modified.txt
md5sum document.txt document_modified.txt
sha1sum document.txt document_modified.txt
sha256sum document.txt document_modified.txt

Question

How significant was the change in the hash after modifying just one character? What property of hash functions does this demonstrate?

6. (Cryptanalyst) Simulate a tampered download. Keep a pristine copy first with cp, which copies a file, then append a line with echo and re-verify against the original checksum:

cp document.txt document_pristine.txt
echo "Injected malicious line." >> document.txt
sha256sum -c document.txt.sha256

Record the exact error message. Submit document_pristine.txt as the untampered file and document.txt as the tampered one. This is the detection mechanism that package managers like apt use to catch corrupted or tampered packages.

7. Compare notes (both). The Cryptographer reads out the three digests from the avalanche demo in step 5. The Cryptanalyst reads out the FAILED line from step 6. Together, write one sentence explaining why the checksum flags the appended line in step 6 as tampering even though the single-character edit in step 5 was also a deliberate change. A hash records that a file changed; it cannot record why, so both are detected identically.

Part 2: Symmetric encryption with AES and openssl

The Cryptographer encrypts; the Cryptanalyst inspects and attacks. openssl is a general-purpose cryptography toolkit, and openssl enc encrypts and decrypts files with a chosen cipher.

1. (Cryptographer) Create a file with highly repetitive, structured content, using python3 to print one line twenty times. This makes the difference between CBC and ECB visible later:

python3 -c "print('SECRET: password=hunter2\n' * 20)" > secret.txt
cat secret.txt

2. (Cryptographer) Encrypt with AES-256-CBC. The -pbkdf2 flag derives the key from the password with a modern key derivation function, and -salt mixes in a random salt so the same password yields a different key each run:

openssl enc -aes-256-cbc -salt -pbkdf2 -in secret.txt -out secret_cbc.enc

Handoff. As the Cryptographer produces each encrypted file (secret_cbc.enc, secret_cbc2.enc, secret_ecb.enc), pass it to the Cryptanalyst along with a copy of secret.txt. The Cryptographer speaks the password aloud rather than writing it in any shared file or the submission. Sending the password over a separate channel is itself part of the lesson.

3. (Cryptanalyst) Inspect the encrypted file. file reports what kind of data a file holds, xxd prints a hex-and-ASCII dump of its raw bytes, and head limits that dump to the first few lines:

file secret_cbc.enc
xxd secret_cbc.enc | head -8

4. (Cryptographer) Encrypt the same file a second time with the same password and compare the two outputs:

openssl enc -aes-256-cbc -salt -pbkdf2 -in secret.txt -out secret_cbc2.enc
sha256sum secret_cbc.enc secret_cbc2.enc

Are the two CBC-encrypted files identical? Why or why not? Both the random IV and the per-run salt change between the two encryptions, and either alone is enough to make the outputs differ. What does the IV specifically contribute?

5. (Cryptanalyst) Decrypt the first file and verify it is a perfect copy of the original. You need secret.txt and the password from the Cryptographer. diff reports any difference between two files:

openssl enc -aes-256-cbc -d -pbkdf2 -in secret_cbc.enc -out secret_decrypted.txt
sha256sum secret.txt secret_decrypted.txt
diff secret.txt secret_decrypted.txt

6. (Cryptanalyst) Try decrypting with the wrong password and observe the result.

7. (Cryptographer) Now encrypt the same file once using ECB mode:

openssl enc -aes-256-ecb -salt -pbkdf2 -in secret.txt -out secret_ecb.enc

Do not compare two ECB runs by file hash. The -salt flag re-derives the key from a new random salt each time, so two runs always differ, mode aside. ECB’s weakness shows up within a single file, which you inspect next.

8. (Cryptanalyst) Use xxd to examine both outputs and look for repeating 16-byte block patterns. The files are only about 512 bytes, so dump them in full:

xxd secret_cbc.enc
xxd secret_ecb.enc

Question

What behavioral difference did you observe when switching from CBC to ECB mode? Why is ECB considered insecure for encrypting structured or repetitive data?

9. Read the dumps together (both). Sit with both xxd outputs open. The Cryptographer describes the plaintext structure (identical lines repeated). The Cryptanalyst points to where two identical 16-byte lines appear in the ECB dump and confirms no such repetition exists in the CBC dump. Together, write the chain of reasoning: identical plaintext blocks produce identical ECB ciphertext blocks, which is visible structure an attacker can exploit, while CBC’s per-block chaining destroys it. This paragraph is the Part 2 deliverable.

Part 3: Asymmetric encryption with GPG

gpg (GNU Privacy Guard) is the command-line OpenPGP implementation: it generates key pairs, encrypts and decrypts files, and creates and verifies signatures against a local keyring.

Both students run steps 1 and 2, because both need a key pair. The workflow then splits into a sender and a recipient, and you run it twice with the roles swapped so each of you plays both sides.

1. (Both) Generate a key pair. When prompted, choose RSA and RSA with a 4096-bit key size:

gpg --full-generate-key

2. (Both) List your keyring to confirm the key was created. Record the key ID and fingerprint:

gpg --list-keys
gpg --fingerprint "your name"

Round 1: the Cryptographer sends, the Cryptanalyst receives.

3. (Cryptographer) Export your public key to share with your partner:

gpg --export -a "your name" > yourname.pub
cat yourname.pub

4. (Cryptanalyst) Import your partner’s public key into your keyring:

gpg --import partnername.pub
gpg --list-keys

5. (Cryptanalyst) Verify the imported fingerprint out of band. The Cryptographer reads their 40-character fingerprint aloud in groups of four characters. The Cryptanalyst checks each group against the output of gpg --fingerprint "partner's name". If any group does not match, stop: the key you imported is not the one your partner generated, and you must not trust it. Only once every group matches do you continue. This step defends against a man-in-the-middle who swaps the public key in transit.

gpg --fingerprint "partner's name"

6. (Cryptographer) Create a message, encrypt it for your partner, and sign it with your private key so they can confirm it came from you. The -o flag sets the output filename; naming it after yourself stops the two partners’ files from colliding on exchange:

echo "This is a secret, authenticated message." > message.txt
gpg -se -r "partner's name" -o message_from_yourname.txt.gpg message.txt

This produces message_from_yourname.txt.gpg, encrypted with your partner’s public key and signed with your private key.

7. (Cryptanalyst) Decrypt and verify the signature of the message your partner sent you:

gpg -d message_from_partnername.txt.gpg

GPG automatically verifies the signature and reports whether it is valid. A Good signature message means the content was not tampered with and came from the expected sender.

Round 2: swap roles and repeat steps 3 to 7. The former Cryptanalyst now exports, signs and encrypts a reply; the former Cryptographer imports it, verifies the fingerprint, decrypts and checks the signature. This round is mandatory: at the end both of you have run every GPG step once.

Handoffs. Round 1: yourname.pub crosses to the Cryptanalyst before step 4; the fingerprint crosses by voice or screen at step 5; message_from_yourname.txt.gpg crosses before step 7. Round 2: the same artifacts in the other direction.

Question

What would happen if someone intercepted the encrypted message but did not have the recipient’s private key? What property of asymmetric encryption ensures the message remains confidential?

Part 4: Classical cryptography — Vigenère

This part is the model handoff: the Cryptographer builds the cipher and encrypts a text, and the Cryptanalyst breaks it with no knowledge of the key. Only the key is secret; the algorithm itself is shared, which is how real cryptographic systems are designed.

Step 1: Implement the cipher

(Cryptographer) Write vigenere.py in Python with three functions: encrypt(plaintext, key), decrypt(ciphertext, key), and a main block that reads mode, text, and key from command-line arguments.

Algorithm:

• Normalize text and key to uppercase; ignore non-alphabetic characters in the key
• Walk through the text one character at a time. For each alphabetic character, shift it by the current key character’s value (A=0, B=1, ..., Z=25), then advance to the next key character, wrapping back to the start of the key at its end. Non-alphabetic characters are copied through unchanged and do not advance the key.

Expected behavior:

$ python3 vigenere.py encrypt "Hello, World!" KEY
Rijvs, Uyvjn!

$ python3 vigenere.py decrypt "Rijvs, Uyvjn!" KEY
Hello, World!

Verify that decrypt(encrypt(text, key), key) returns the original text for at least 3 different keys and messages of varying length.

Step 2: Encrypt a long text for your partner

(Cryptographer) Choose a paragraph of at least 300 alphabetic characters of English text (a Wikipedia introduction, a news article excerpt, etc.). Choose a key of 4–8 letters that you keep secret from your partner.

python3 vigenere.py encrypt "$(cat plaintext.txt)" YOURKEY > ciphertext.txt

Handoff. Send vigenere.py and ciphertext.txt to the Cryptanalyst. Do not send the key or plaintext.txt.

Step 3: Implement the cracker

(Cryptanalyst) Write crack_vigenere.py to break your partner’s ciphertext. The attack works in two stages.

Stage 1 — Key length estimation with the Index of Coincidence (IoC)

The IoC measures how unevenly distributed the letters in a text are. For a string with N letters and letter counts f_i (for each of the 26 letters):

IoC = Σ f_i × (f_i − 1) / (N × (N − 1))

English plaintext has IoC ≈ 0.065. Random or well-mixed ciphertext has IoC ≈ 0.038. The key insight: if you split a Vigenère ciphertext into k groups by stride (group 0 = positions 0, k, 2k, …; group 1 = positions 1, k+1, 2k+1, …; etc.), and k matches the true key length, each group becomes a simple Caesar cipher — and its IoC will be close to 0.065.

For each candidate key length from 1 to 20:

1. Split the ciphertext (letters only) into k groups by stride
2. Compute the IoC of each group using the formula above
3. Average the IoCs across all k groups
4. Print the candidate length and its average IoC

The length whose average IoC is highest and closest to 0.065 is your best guess for the key length.

Stage 2 — Recover each key letter with frequency analysis

Once you have the key length k:

1. Split the ciphertext into k groups using the same stride method
2. For each group, count how often each of the 26 letters appears
3. Find the most frequent letter in the group. Assume it decrypts to E — the most common letter in English. The key letter for that position is then (index_of_most_frequent − 4) % 26, where A=0, B=1, …, E=4, …
4. Build the full candidate key from all k recovered letters

Decrypt the ciphertext with your candidate key using the Cryptographer’s vigenere.py. If the output is readable English, you have broken the cipher. If a few words look wrong, try swapping one key letter at a time with the second or third most frequent letter in that group, since short texts do not always have E as the most frequent letter in every column.

Question

At what key length does the IoC method start to require much longer ciphertexts to work reliably? What is the theoretical upper limit of Vigenère security, and what cipher design eventually solved it?

Step 4: Compare against ground truth

(Both) The Cryptanalyst hands over the recovered key and decrypted text. The Cryptographer now reveals the real key and the original plaintext. Together, work out: how many of the k key letters did Stage 2’s frequency analysis get right on the first guess? For each letter it missed, was the true plaintext-E column actually the second or third most frequent letter rather than the first? These two numbers go in the write-up.

Submission

One compressed folder per pair, containing:

From the Cryptographer:

• document.txt.sha256 and document_modified.txt, plus the avalanche-demo output (md5sum, sha1sum, sha256sum on the original versus the modified file) from Part 1 step 5
• secret.txt, secret_cbc.enc, secret_cbc2.enc, secret_ecb.enc, and the sha256sum comparison output from Part 2 steps 4 and 7
• <name>.pub and message_from_<name>.txt.gpg from each Part 3 round
• vigenere.py, plaintext.txt, ciphertext.txt, and the real Vigenère key (state it in the write-up, not as a separate file)

From the Cryptanalyst:

• document_pristine.txt and the tampered document.txt from Part 1 step 6
• Screenshots of the sha256sum -c verification (Part 1 step 3) and the tampered-file FAILED output (Part 1 step 6)
• Screenshots of the file and xxd inspection (Part 2 step 3), the CBC-vs-ECB xxd comparison (Part 2 step 8), the successful decrypt and diff (Part 2 step 5), and the wrong-password failure (Part 2 step 6)
• Screenshot of the gpg -d output showing Good signature for each Part 3 round
• crack_vigenere.py with sample output, the recovered key and key length, and the decrypted version of the partner’s ciphertext

Joint:

• The one-sentence note from Part 1 step 7
• The reasoning paragraph from Part 2 step 9
• A short document (1–2 pages) explaining: what the avalanche effect showed; why the two CBC outputs differed between runs; which mode leaked the plaintext structure in the xxd dump and why; what the Good signature message asserts and what the out-of-band fingerprint check defends against; and, from Part 4 step 4, the recovered key length and how many key letters needed a second-guess correction

---

Key concepts

Term	Definition
AES	Standard symmetric encryption algorithm with 128-bit blocks
Symmetric encryption	System that uses the same key to encrypt and decrypt
Asymmetric encryption	System that uses a key pair: public and private
RSA	Asymmetric algorithm based on prime number factorization
SHA-256	256-bit hash function, currently secure and widely used
Hash	Function that converts data into a fixed-length string
GPG	Free implementation of OpenPGP for encryption and digital signatures

---

Navigation: ← Previous | Home | Next →