MATH3411 Chap.7 Classical Ciphers to Public-Key Cryptography
Classical Ciphers to Public-Key Cryptography
The cryptography chapter moves from classical substitution and transposition systems to modern trapdoor constructions. Frequency analysis attacks monoalphabetic structure, while repeated spacings and index of coincidence expose polyalphabetic periods. Hash and one-way ideas motivate public-key systems.
RSA then combines factoring, Euler's totient, modular inverses and fast exponentiation to separate public encryption from private decryption. Classical attacks are evidence chains: repeated-fragment spacings suggest periods, coincidence statistics compare those candidates, and frequency profiles propose shifts for each column.
No single statistic guarantees the key, so a recovered fragment should be checked against more ciphertext. Public-key calculations instead establish a modular construction. RSA requires coprime key exponents, an inverse relation modulo the totient, and efficient powering with reduction after each step. A round trip supports mathematical correctness but says nothing by itself about the security of small classroom parameters.
Explanations should name whether they concern correctness, leaked language structure, computational hardness or an information-theoretic estimate such as unicity distance.
What this chapter covers
- 01
Classical substitution systems
- 02
Frequency analysis
- 03
Kasiski's method
- 04
Index of coincidence
- 05
One-way and trapdoor functions
- 06
RSA key construction
- 07
Entropy and unicity distance
Worked example · free
Construct the RSA Round Trip
- +1Compute n=187 and phi(n)=160.
- +1Find d=23 because 7(23) is congruent to one modulo 160.
- +1Use repeated squaring to reduce 8^7 modulo 187 to 134.
- +1Verify that 134^23 reduces to 8.
Key terms
- Kasiski method
- A repeated-spacing technique for proposing the period of a polyalphabetic cipher.
- Index of coincidence
- The probability that two sampled letters from a text are equal.
- RSA modulus
- The product of two primes used as the public modular arithmetic base.
Classical Ciphers to Public-Key Cryptography FAQ
How does Kasiski analysis suggest a key length?
Repeated ciphertext fragments create spacings whose common factors are candidates for the repeated-key period. Test those candidates with coincidence statistics because accidental repetitions can produce misleading spacings.
Why must an RSA exponent be coprime to the totient?
The private exponent is its modular inverse, which exists exactly when the gcd is one. Without that inverse, the proposed public exponent cannot support the required RSA decryption relation.
What does unicity distance describe?
It estimates how much ciphertext is needed before language redundancy can isolate one plausible key under a model. It is an information-theoretic threshold estimate, not a guarantee that a particular attack immediately succeeds.
Exam move
Divide cryptography revision into attack evidence and construction algebra. For a Caesar or affine substitution, count ciphertext symbols, compare the uneven distribution with expected language frequencies and score several candidate shifts rather than trusting one guessed letter. Re-encrypt a short recovered fragment to confirm the mapping.
For a repeated-key system, list distances between repeated fragments, factor the spacings and rank plausible periods. Treat common factors as hypotheses only. Split the ciphertext into columns for each candidate period, calculate or compare their indices of coincidence and prefer a period whose columns consistently recover language-like unevenness.
Short columns can fluctuate, so combine statistical evidence with the amount of data available. Once a period is credible, solve each column as a shifted monoalphabetic sample and test the assembled key on multiple fragments. For RSA, begin by checking that the proposed public exponent is coprime to the totient. Use extended Euclid to produce the private exponent and multiply back to verify the inverse relation.
Convert encryption and decryption exponents to binary, build a repeated-squaring table and reduce after every product. A complete classroom calculation ends with the original message after decryption. Keep that correctness claim separate from security: small worked moduli are intentionally factorable, while practical security depends on large parameters, safe padding and implementation choices beyond the toy arithmetic.
When explaining unicity distance, connect ciphertext length with accumulated language redundancy and describe the result as a model-based estimate rather than an automatic attack threshold.
Maintain an error ledger for accepting an unsupported key period, using coincidence as an exact oracle, choosing a noninvertible RSA exponent, calculating the wrong totient, expanding a huge power without modular reduction or calling an algebraically correct toy system secure. A timed mixed set should include one spacing diagnosis, one frequency or coincidence argument, one key-validity check and one modular round trip.
State the purpose of every tool: spacings generate period candidates, coincidence compares them, frequency analysis proposes shifts, Euclid constructs an inverse and repeated squaring evaluates the public-key map. This separation makes longer answers coherent and prevents methods from being applied merely because they appeared nearby in the notes.
Working through Classical Ciphers to Public-Key Cryptography in MATH3411? Sia is AskSia’s AI Mathematics tutor — ask any MATH3411 Classical Ciphers to Public-Key Cryptography question and get a clear, step-by-step explanation grounded in how MATH3411 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
