Applications in Cryptography and Security

Match the algorithm to the cryptographic assumption

Quantum algorithms affect different security mechanisms in different ways. Shor-type algorithms address factoring and discrete logarithms. Grover-type search changes a generic exhaustive-search query scale. Quantum key distribution uses physical protocols with a different security model. Post-quantum cryptography is designed to run on classical systems while resisting known quantum attacks. These categories should not be merged into a claim that “quantum breaks encryption.”

Prerequisites: oracles, complexity and the Shor/Grover chapters. This lesson explains algorithmic relationships; an operational cryptographic migration must follow current standards, implementation guidance and an organisation’s threat model.

WORKED DIAGRAM · A33Toy factor recovery

This small arithmetic example explains the period-to-factor mechanism; it is not a resource estimate for RSA-2048 or a completed cryptographic attack.

The security-task contract

Specify the primitive, parameter set, attacker goal and access model. Factoring an RSA modulus is not the same task as searching a symmetric key, forging a signature, finding a hash collision or distinguishing a protocol transcript. State whether an attacker has classical examples, a coherent verification oracle or physical access to quantum states. Different access assumptions produce different bounds.

Also distinguish mathematical algorithm cost from a feasible attack implementation. A logical circuit count excludes error correction, routing, resource-state preparation and control unless those are explicitly added. A conditional resource study is neither a completed break nor a prediction of the date at which one will occur.

Worked example: toy RSA arithmetic

Use the small modulus 15 only to understand the algebra. Choose base two. Its powers modulo 15 cycle through two, four, eight and one, so the order is four. Half that order is two, giving two squared equal to four. The greatest common divisors of four minus one and four plus one with 15 are three and five.

This is the classical postprocessing used after an order-finding result. The tiny example is easy by hand and does not model the physical resources needed for RSA-2048. Its purpose is to explain why a period can reveal factors. A scalable attack requires coherent modular arithmetic, sufficient precision and a reliable full computation. Shor’s primary algorithm paper.

For dated resource context, use the noise and hardware lesson and the resource-estimation chapter. They compare primary architecture studies through their error, timing, connectivity and reliability assumptions. The correctness of the factoring algorithm and the engineering feasibility of a cryptographic-scale implementation are separate questions.

Generic search is a different advantage

In an ideal one-marked-item black-box model, a key space of size two to the power k has a Grover query scale of two to the power half k. This is a quadratic query improvement, not the polynomial-time factoring behaviour associated with Shor. The oracle must implement the relevant encryption and verification coherently, with its reversible-workspace and gate costs.

For a toy eight-bit key space, there are 256 candidates and a square-root scale of 16. This illustrates the exponent change but is not an attack estimate for a deployed cipher. Multiple matching keys, limited known plaintext, parallelisation, depth limits and fault-tolerant costs can all affect the concrete analysis. Grover’s primary search paper.

Hash preimages and hash collisions are different problems with different quantum algorithms and bounds. Do not apply a square-root rule to every security property by analogy. Identify the attacker’s actual success condition before choosing a resource model or interpreting a nominal security-bit count.

Post-quantum standards run on classical computers

NIST’s ML-KEM standard specifies a module-lattice-based key-encapsulation mechanism. It establishes shared-secret material under its security assumptions; it is not a digital signature or a quantum communication protocol. FIPS 203.

ML-DSA and SLH-DSA are digital-signature standards with different underlying constructions and trade-offs. FIPS 204, FIPS 205. Naming their roles correctly matters: replacing an RSA use requires understanding whether it supplies key establishment, authentication or another protocol function. Standard pages and their errata should be checked when implementing current systems.

Quantum key distribution is another task

In a simplified BB84 experiment, random preparation and measurement bases create a sifted subset of shared bits. Errors can indicate noise or an adversary, but an error statistic alone does not identify their cause. A full secure protocol needs authenticated classical communication, parameter estimation, error reconciliation, privacy amplification and a finite-key analysis.

The book’s BB84 lab is a statistical teaching model and does not generate a secure key. Quantum transmission does not remove endpoint compromise, authentication requirements or implementation vulnerabilities. Keep the theorem’s physical and adversarial assumptions attached to any security statement.

A practical reasoning workflow

Inventory the security function and its parameters. Identify the best relevant classical and quantum algorithmic attacks. Translate their abstract access models into a plausible implementation, including physical resources and uncertainty. Separate long-lived confidentiality risks from immediate attack capability. Consult current standardisation and implementation sources before choosing replacements.

For education, compare one factoring example, one generic-search example and one key-establishment/signature classification exercise. This gives students a concrete map of the field without implying that all primitives share one failure mechanism or one migration action.

Separate a resource update from a security conclusion

A lower qubit estimate changes one part of a conditional attack analysis. It does not establish that the necessary qubits, gates, connectivity, timing and control have all been demonstrated together. Conversely, uncertainty about hardware arrival does not make mathematical vulnerabilities disappear. Security planning and hardware forecasting answer different questions and should use different evidence.

A student can practise this distinction by writing two sentences about the same resource paper. The first states its target, assumptions and estimated resources. The second states what was actually demonstrated or calculated. If those sentences become identical without an experimental basis, the explanation has probably promoted a design estimate into a hardware claim.

For a protocol inventory exercise, record whether each cryptographic use protects long-lived confidentiality, authenticates messages or establishes session material. That role classification comes before selecting a replacement. It also reveals why one post-quantum algorithm cannot be substituted blindly at every location where an older public-key primitive appears.

Exercises and worked answers

Exercise 1. For modulus 15 and base four, find the order and test the factor-recovery step.

Check the worked answer

Four squared is one modulo 15, so the order is two. Half-order power is four. The greatest common divisors of three and five with 15 give three and five. A valid order result still requires checking the standard factor-recovery conditions.

Exercise 2. Can ML-KEM directly replace a digital-signature verification function?

Check the worked answer

No. A KEM establishes secret material, while a signature authenticates a signed message under its verification model. Protocol roles must be matched before selecting a replacement. The fact that both are post-quantum standards does not make their interfaces interchangeable.

Check your understanding

PAUSE & THINK

Can a key-encapsulation mechanism directly replace a digital-signature verifier?

Choose your answer

Yes, because both are cryptographicNo; their protocol functions differOnly if it uses quantum transmission

Check my answer

Answer: No; their protocol functions differ. A KEM establishes shared-secret material. A signature authenticates a signed message under its verification model. Match the protocol role before selecting a replacement.