Bit commitment 2026-10-13
A bit commitment allows a sender to fix a bit while concealing it from the receiver until an opening phase. Binding prevents a sender from opening the same commitment as either bit; hiding prevents the receiver from learning the bit prematurely. With a one-way permutation and a hard-core predicate , a commitment can consist of and the masked bit . Opening reveals . Injectivity gives binding, while unpredictability of the hard-core predicate gives computational hiding. For an RSA cryptosystem, the receiver must not possess the inverse trapdoor.
Chosen-ciphertext attack 2026-10-05
An attack in which an adversary obtains decryptions of selected ciphertexts, subject to the protocol’s restrictions. The multiplicative structure of textbook RSA cryptosystem permits blinding an intercepted ciphertext by a known invertible factor.
Homomorphism attack Created 2026-10-05 Updated 2026-10-31
An attack exploiting preservation of an algebraic operation by encryption or signing. The textbook RSA cryptosystem has , so unprotected ciphertexts can be modified multiplicatively. Authentication must be verified before accepting a modified message.
Integer factorization Created 2026-10-13 Updated 2026-10-20
Integer factorization seeks the prime factorization of a positive integer . For , this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor is useful progress, but need not finish the job: factor and further until all factors are prime numbers.
For example, is a semiprime, whereas has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of with a specially constructed integer.
The beautiful trick in congruence of squares is that two integers with equal squares modulo can reveal different factors through their sum and difference. In the worked example, gives and . Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. [ref]
https://crypto.stanford.edu/pbc/notes/crypto/factoring.html. Ben Lynn, Factoring and Discrete Logarithms: congruent squares and the linear-algebra step
.This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.
Modular arithmetic Created 2026-10-03 Updated 2026-10-18
Modular arithmetic performs addition and multiplication on integers while remembering only their remainders for a fixed positive integer modulus . The relation means that divides : the two integers lie in the same congruence class. For example, , and represent one class modulo . Choosing the least nonnegative residue gives exactly representatives, , even though each congruence class contains infinitely many integers.
A clock supplies a familiar example. Represent the twelve positions by , with at the position usually labelled twelve. Starting at ten and moving seven positions givesThe integer congruence records the final position; it discards the number of complete revolutions. Adding another twelve changes the elapsed count while preserving the position. The picture also shows a single congruence class modulo five spread along the number line.
The useful surprise is that discarding this information still preserves the arithmetic. If and modulo , then and modulo . Thus a large calculation can reduce its intermediate integers after every step. For instance,Replacing by gives the same answers with smaller intermediate values. The congruence classes with these operations form the quotient ring ; their addition alone forms a cyclic group. This passage from integers to a finite arithmetic system is the setting for modular exponentiation, primality testing and the RSA cryptosystem. [ref]
https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf. Ankur Moitra, MIT 18.200, Lecture 15, modular arithmetic and its applications
Multiplicative cancellation needs extra care. Modulo six, , but : multiplication by two has merged distinct congruence classes. Cancelling a factor while retaining the integer modulus is justified when that factor has a modular multiplicative inverse, equivalently when it is coprime to the integer modulus. A linear congruence can consequently have no solutions, one solution class, or several solution classes. The Chinese remainder theorem supplies a complementary operation: splitting a calculation across coprime integer moduli and reconstructing its class modulo their product.
Small remainders can also certify impossibility. A perfect square has residue zero or one modulo four, as checking the four congruence classes shows. Therefore an integer equation has no solution. The converse direction needs care: a permitted residue does not guarantee an integer solution, since but five is not a perfect square. Such local tests provide necessary conditions for Diophantine equations without replacing the full problem.
In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines integer congruence in article 1 and adopts the symbol in article 2. Article 12 derives divisibility tests from powers of ten and explains checking arithmetic by its remainders. These passages show a systematic treatment of the same idea; they are not a claim that remainders were first used in 1801. [ref]
https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_prima. Gauss, Disquisitiones arithmeticae, section I, articles 1–2 and 12; text from the 1870 collected edition
One-way function Created 2026-10-13 Updated 2026-10-20
A one-way function is efficiently computable but computationally infeasible to invert on a randomly sampled input with nonnegligible success probability, under its stated security assumption. An RSA cryptosystem supplies the candidate map on units modulo . Inversion hardness is an assumption; it is not a proved consequence of merely choosing large primes.
For distinct prime numbers , compute the Euler totient functionThe RSA cryptosystem private exponent is a modular multiplicative inverse of the public exponent:Use the extended Euclidean algorithm on and . It produces integers with , and reducing modulo gives a suitable positive . Searching through possible exponents is unnecessary.
To see correctness even for a plaintext sharing a factor with , write . Modulo , either or Fermat's little theorem gives ; the same holds modulo . The Chinese remainder theorem then gives . One may alternatively invert modulo , but inversion modulo is sufficient for this paper.
For each candidate nonzero offset , expansion givesConsequently, if is invertible, the candidate isCompute the modular multiplicative inverse using the extended Euclidean algorithm, then verify both and . The RSA cryptosystem cubing map is a bijection, so an accepted candidate cannot be a different plaintext with the same first ciphertext. This costs fewer than trials, each involving polynomially many operations in the bit length of .
There is a useful way to handle every denominator exception for a correct nonzero . Compute . If , this greatest common divisor factors , allowing ordinary RSA cryptosystem decryption. If , then . The permitted prime numbers are and much larger than , so is invertible modulo each. The equation would make a nontrivial cube root of one, impossible in a group of order coprime to three. Thus cannot occur for the correct nonzero offset under these hypotheses.
If the bound in the question is read as also allowing , then and there is no additional information: the problem reduces to inverting a single ordinary RSA cryptosystem ciphertext. The small-offset attack requires a nonzero difference; that is the natural reading of distinct related messages.
The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo and need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.
If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.
Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.
Past exam of the mathematics course of the University of Cambridge 2006 ii Paper 3 12G Solution Created 2026-09-24 Updated 2026-10-14
In the RSA cryptosystem, choose distinct large primes , put , choose coprime to , and choose with . Publish and keep the factorization and private. Encrypt a properly encoded message as and decrypt as . The Chinese remainder theorem proves correctness even for nonunits: modulo either prime, the message is either zero or satisfies Fermat's little theorem.
The public exponent has few nonzero binary digits, so exponentiation needs only sixteen squarings and one extra multiplication. It is an efficient conventional choice, subject to the required coprimality and secure randomized message encoding. The same numerical choice for the private exponent would speed decryption, but for large moduli with balanced prime factors it is disastrously small: the continued-fraction attack on a small RSA private exponent recovers when, for example, and . A small public exponent and a small private exponent have very different security implications.
To factor from , write with odd. Choose random modulo . If is nontrivial, factoring is already done. Otherwise compute and repeatedly square; the final value is one. If a value immediately preceding the first one is neither nor modulo , then andIndeed, the signs of modulo and differ. Restart if the chain begins at one or reaches first. The Chinese remainder theorem makes the two prime components independent for a uniformly chosen unit. Their two-primary orders differ with probability at least one half: if the two exponents of two in are equal, the probability of equal orders is at most one half, and if unequal it is smaller. Since odd preserves these orders, this gives a randomized factoring procedure with bounded expected repetitions.
A bit commitment must be hiding before opening and binding after it. A concrete RSA construction uses a valid public RSA permutation whose inverse is unavailable to the receiver. Choose a random unit and a random bit vector , and set to their binary inner product modulo two. Send , , and . To open, reveal ; the receiver checks and recovers . Injectivity makes the opening bit unique. The hard-core predicate theorem applied to gives computational hiding under the RSA inversion assumption. The setup must ensure a valid modulus and exponent without giving the receiver the private exponent; otherwise hiding fails. Merely encrypting or would not hide a bit, since both ciphertexts could be computed publicly.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 3G Solution Created 2026-09-24 Updated 2026-10-05
In the RSA cryptosystem, choose distinct large prime numbers , set , and choose coprime to . Choose with . A plaintext residue class is encrypted as and decrypted as . Fermat's little theorem modulo and , followed by the Chinese remainder theorem, proves correctness even when is not coprime to .
Textbook RSA cryptosystem is multiplicative: . For a chosen-ciphertext attack, multiply an intercepted by for a known invertible . A decryption oracle returns , from which multiplication by recovers . Likewise, multiplying two textbook RSA signatures produces a signature of their product. These are homomorphism attacks, exploiting algebra rather than factoring .
For an ElGamal signature, choose a prime , a primitive root modulo , a private exponent , and public . To sign a message digest , choose a fresh secret coprime to and setVerification checks and , which follows because . Authenticating the ciphertext and its context with such a digital signature, before decryption, prevents the simple multiplicative modification from being accepted without a fresh valid signature. One needs an appropriate cryptographic hash function and fresh secret cryptographic nonces: this is not a claim that every algebraic attack is impossible. In particular, the unhashed historical ElGamal signature scheme admits existential forgeries of specially chosen message exponents; mere multiplication of encrypted messages is not an authentication mechanism.
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 2 12H Solution Created 2026-09-24 Updated 2026-10-03
In the RSA cryptosystem, choose distinct primes , set , and choose with . The public key is ; the private exponent satisfiesA message is encrypted and decrypted by
Suppose , where is odd. For a unit modulo , both and are powers of two dividing . If these orders differ, assume without loss of generality thatTaking givesand hencea nontrivial factor.
To count successful , write and with odd. Raising to the odd power , which is divisible by the odd parts, maps a uniformly chosen element of each cyclic multiplicative group uniformly onto its Sylow two-subgroup. In a cyclic group of order , the probability of order is and that of order is for . If , the probability that the two resulting orders agree isThus at least half of the units satisfy .
Knowing reveals the multiple of . Writing with odd and trying random units therefore yields a factor with probability at least one half per trial; nonunits already reveal a factor by taking their greatest common divisor with . Conversely, factoring gives and hence . This proves that recovering the private key is computationally equivalent, up to randomized polynomial-time work, to factoring the RSA modulus, as summarized by RSA private exponent reveals the factorization.
Finally, is odd because it is coprime to the even integer . If , thenThus fixed points occur in complementary pairs , which is the Complementary RSA fixed points property.
Past exam of the mathematics course of the University of Cambridge 2020 ia Paper 2 7D c Solution Created 2026-09-24 Updated 2026-09-29
In the RSA cryptosystem, choose distinct large primes , put , and choose coprime toThe decryption exponent is the modular multiplicative inverseThus . For a message with , the Fermat-Euler theorem givesFor , . The extended Euclidean algorithm givesso
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 4 3K Solution Created 2026-09-23 Updated 2026-09-25
For Rabin cryptosystem, choose primes , publish , and encrypt as . The factors let the receiver take square roots modulo and and combine them using the Chinese remainder theorem; redundancy identifies the intended one of four roots.
Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 2 12K b i Solution Created 2026-09-24 Updated 2026-09-25
For the RSA cryptosystem, choose and a public exponent coprime to . The public key is , while the private exponent satisfiesEncryption sends to , and decryption computes .
Euler's totient function isEuler's theorem states that implies . For , let be the invertible residue classes modulo . Multiplication by permutes these classes, since it has an inverse modulo . Multiplying the resulting congruences givesEvery factor is a unit, so the product can be cancelled, proving the theorem. The case is immediate. For distinct prime numbers , removing multiples of either prime from gives
For the RSA cryptosystem, choose distinct large primes , put , and choose coprime to . Compute with . The public key is ; the private exponent is retained secretly. Represent a message by , encrypt by , and decrypt by .
To prove correct decryption even for messages not coprime to , write . Modulo , if then ; otherwise Fermat's little theorem gives . The same reasoning holds modulo . The Chinese remainder theorem therefore gives , and the chosen representative recovers . Thus decryption works for every message residue, not merely the units.
Euler's totient function isEuler's theorem states that implies . For , let be the invertible residue classes modulo . Multiplication by permutes these classes, since it has an inverse modulo . Multiplying the resulting congruences givesEvery factor is a unit, so the product can be cancelled, proving the theorem. The case is immediate. For distinct prime numbers , removing multiples of either prime from gives
For the RSA cryptosystem, choose distinct large primes , put , and choose coprime to . Compute with . The public key is ; the private exponent is retained secretly. Represent a message by , encrypt by , and decrypt by .
To prove correct decryption even for messages not coprime to , write . Modulo , if then ; otherwise Fermat's little theorem gives . The same reasoning holds modulo . The Chinese remainder theorem therefore gives , and the chosen representative recovers . Thus decryption works for every message residue, not merely the units.
Paul C. van Oorschot 2026-11-05
Paul C. van Oorschot coauthored the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Its treatment connects cryptographic constructions with explicit mathematical algorithms and stated assumptions, rather than describing encryption only as a black box. The number-theoretic chapter includes algorithms for modular square roots, while the public-key chapter gives RSA cryptosystem and Rabin cryptosystem constructions.[ref]
For a concrete special case, if is prime and is a nonzero square modulo , a square root is . This illustrates how assumptions on an integer modulus determine which algorithm and correctness argument apply.
Private key 2026-10-05
The secret member of a public-key cryptographic key pair, used for decryption or signing according to the scheme. In the RSA cryptosystem the private exponent is not interchangeable with a security proof for textbook signing.
RSA cycling attack 2026-10-31
Repeatedly apply the public RSA cryptosystem encryption map to a ciphertext. A return to that ciphertext reveals its preceding iterate as the plaintext. A nontrivial greatest common divisor between an iterate-minus-start and the modulus instead enables integer factorization. Eventual return alone supplies no useful running-time bound.
