Motivation
A sender and recipient who have never met may still wish to communicate privately. Public-key encryption separates the information needed to encrypt from the information needed to decrypt. RSA uses modular exponentiation for both operations. Its elementary arithmetic can be proved exactly; deciding whether a real implementation is secure requires substantially more than that proof. We develop the arithmetic first, using small numbers only for transparent calculation.
Definitions
Definition 4.1.1
(Congruence and modular inverse)
For integers and positive , write when divides . The residue class of is its set of congruent integers. Addition, multiplication and nonnegative powers respect congruence: replacing an integer by a congruent one does not change the resulting residue. An integer is invertible modulo when some satisfies . Bézout's identity shows this happens exactly when .
Definition 4.1.2
(Textbook RSA)
Choose distinct primes and put , . For this key-generation recipe assume ; then is an available choice. Choose with and . Bézout gives an integer with ; use its positive representative. The public key is and the private exponent is . A message is represented here by a residue modulo . The raw RSA operations are
This algebraic description is often called textbook RSA. It is a deterministic map on residues, not yet a secure message-encryption scheme.
Theorem/proposition
Theorem 4.1.3
(RSA correctness for every residue)
For distinct primes and positive integer exponents satisfying , decrypting gives for every integer , including those divisible by or .
Theorem 4.1.4
(Chinese remainder uniqueness)
If distinct primes divide an integer , then divides . Consequently, two integers congruent modulo both and are congruent modulo .
Proof sketch or proof idea
Proof
(Prime by prime, then combine)
Write . Modulo , if , then both and are zero. Otherwise Fermat's little theorem gives , and hence
The same reasoning holds modulo , switching the roles of the primes. The second theorem then gives congruence modulo . Its proof uses Euclid's lemma: gives ; since and , , so . This argument does not assume the message is coprime to .
Proof X-ray
The prime-by-prime proof covers non-units
The hypothesis modulo is used twice, through two factorizations of the same exponent: at and at . Positivity of and makes and gives a meaning when is not invertible.
The key move is to work one prime at a time and to split into the cases and . Modulo a prime the only non-unit is zero, which is trivially fixed; this is how the proof avoids Euler's theorem, which would need . Distinctness of and enters only at the end, through Euclid's lemma in the Chinese remainder step, which closes the argument by turning two congruences into one modulo .
For completeness, Fermat's theorem follows by multiplication: when , the nonzero residues are permuted by multiplication by . Multiplying them and canceling their nonzero product modulo gives . Cancellation is valid because every nonzero residue modulo a prime is invertible. For a composite modulus, an arbitrary nonzero residue need not be invertible.
Counterexample mode
A repeated prime breaks correctness
If were allowed, the recipe would use with the exponent condition modulo . Take , so and , and choose , since . The message gives , because , and even the unit gives . Neither returns the message. The prime-by-prime step still holds modulo , but the combination step fails: modulo , a congruence modulo does not determine the residue. Distinct primes are a genuine hypothesis of the theorem.
Worked examples
Worked example 4.1.5
(Derive a small key)
Take , , so and . Choose , which is coprime to 40. Since , a private exponent is . This key is tiny and serves only to make the calculation visible.
Worked example 4.1.6
(Encrypt and decrypt)
With that key and , encryption gives . Repeated squaring gives , , and . As ,
The intermediate products reduce to , , and . The exponents used in repeated squaring come from the binary representation of 27.
Worked example 4.1.7
(A non-unit message)
Let , which shares a factor with . Encryption yields . The all-residue theorem still guarantees . In fact and , , , ; hence powers repeat with period five from exponent one, and . Applying Euler's theorem directly to modulo 55 would be invalid because 5 is not invertible modulo 55.
Common mistakes
Common mistake
(Correctness is not security)
Knowing and is intended to permit encryption, not to reveal the factors by definition. If the factors are known, computing and then by the extended Euclidean algorithm is straightforward. The converse security claim is subtler: a proof that RSA inversion is equivalent to factoring has not been supplied here. Correctness alone gives no security guarantee.
Common mistake
(Deterministic encryption allows guess-and-compare)
Raw RSA is deterministic: equal messages produce equal ciphertexts under the same public key. An attacker who can guess a message can compute its ciphertext and compare it with the observed one. Small plaintext spaces therefore make this equality test especially direct. Practical schemes use standardized randomized encoding and implementation protections; this note does not specify or implement such a scheme. Never interpret the toy parameters or bare exponentiation above as a secure protocol.
Summary
The modular proof separates two cases at each prime: a divisible message is handled directly, and an invertible one by Fermat. Combining the two congruences proves correctness for every residue modulo the product. Key generation requires the exponent to be invertible modulo the chosen group-order multiple. The size and representation of the message, randomness in encoding, and resistance to implementation attacks belong to a separate security analysis.
Exercises
Quick check
(For , , and , find , and a valid .)
Solution · Answer
, , and , so is valid.
Quick check
(With that key, encrypt and decrypt the result.)
Solution · Answer
. Because , . The same result follows from the theorem.
Quick check
(Explain why choosing with cannot yield a decryption exponent satisfying .)
Solution · Answer
Any multiple is divisible by 10; it cannot differ from 1 by a multiple of 40. Equivalently, , so 10 has no inverse modulo 40.
Efficient exponentiation and its invariant
Computing as an integer before reducing modulo is unnecessary. Repeated squaring keeps numbers small by reducing after every multiplication. Start with an accumulator , a base and the nonnegative exponent . While , multiply by modulo when is odd; then replace by and by . The invariant is
Initially it holds because , and . If , the update changes to . If , the extra factor of is moved to before becomes . Thus the invariant is preserved in either case. The loop terminates because a positive integer is repeatedly halved. At termination , so . The number of loop iterations is proportional to the number of binary digits of ; the actual bit cost also depends on the multiplication and reduction algorithms and on the size of .
For example, compute using . The squares are , , and . The result is . Different orders of multiplication give the same residue, but reducing after each step prevents unnecessary growth.
A direct implementation of this simple loop may reveal information through timing or other side channels when the exponent is secret: the branch depends on its bits. The invariant proves the mathematical result, not constant-time execution. Implementation security requires explicit engineering beyond this arithmetic example.
Finding the inverse with Euclid's algorithm
The extended Euclidean algorithm supplies both a test for a valid exponent and its inverse. For the key above,
Thus is an inverse of 3 modulo 40, and its positive residue is 27. More generally, Bézout gives integers such that . If the gcd is 1, is an inverse. If the gcd is larger than 1, no inverse can exist: a common divisor of and would divide both and , and hence divide 1, a contradiction.
Different representatives of an inverse have the form for integer . A positive representative is chosen so the decryption power is defined for every residue, including zero; writing a negative power would require invertibility and would exclude non-unit messages. The arithmetic relation is unchanged by adding multiples of .
Quick check
(Find the inverse of 7 modulo 40 and explain how it follows from a Bézout identity.)
Solution · Answer
Euclid gives and , . Back-substitution gives . Hence is an inverse. Check: .
Quick check
(With modulus 55, use repeated squaring to compute .)
Solution · Answer
, , and . Since , . Reducing earlier or later gives the same residue.
Combining congruences explicitly
The correctness proof used only uniqueness, but the Chinese remainder theorem also constructs the unique residue modulo from a pair of residues. Since and are coprime, there are integers with . Given modulo and modulo , set
Modulo , the identity gives and , so . Modulo it gives and , so . Any other solution differs from by a multiple of both primes, hence by a multiple of . This proof supplies existence as well as uniqueness and does not require or to be invertible.
Worked example 4.1.8
(Two residues combined modulo 55)
Find the residue modulo 55 that is 2 modulo 5 and 4 modulo 11. Since , take , . The formula gives . Indeed, and . Merely adding 2 and 4 would not satisfy the conditions.
A holder of the factors can compute a power modulo each prime and reconstruct the answer modulo . This is often used to accelerate private-key arithmetic, but an implementation must also handle faults and protect the prime factors. The mathematical identity alone does not supply those operational protections.
Concept lensStructural
Two power maps glued by the Chinese remainder theorem
Reduction gives a ring isomorphism , under which becomes the pair of maps on and on . On zero is fixed and every nonzero satisfies , so undoes as soon as . Decryption therefore needs only modulo and , that is, modulo . For this modulus is , so already inverts .
What the deterministic example reveals
Suppose a raw-RSA public key is fixed and an observer knows that a message is either 2 or 3. The observer can raise both candidates to the public exponent and compare the results with the ciphertext. For the toy key , those ciphertexts are and . Seeing 8 identifies the first candidate, even though the observer has not factored 55 as part of this test. The example is deliberately small, but the equality test stems from determinism and a guessable message set rather than from this particular modulus size.
The map also preserves multiplication: if and , then . This follows from commutativity of modular multiplication. It means a modified ciphertext can decrypt to a predictably related residue. As a concrete calculation with exponent 3 and modulus 55, encrypting 7 gives 13; multiplying that ciphertext by gives . The modified ciphertext is the raw encryption of , and correctness makes it decrypt to 14. This algebraic observation does not describe a safe way to alter a real encrypted message; secure encodings and protocols are designed with such behavior in mind.
A digital signature has a different goal from encryption. Authenticity and confidentiality require different security definitions even though both may involve modular exponentiation. Reversing the labels on the textbook formulas does not by itself define a secure signature scheme. In particular, the treatment here proves only the encryption/decryption identity, not the security or correct design of any signature protocol.
Quick check
(With the toy public key , encrypt the candidates 4 and 5. Can a person who knows that the message is one of these distinguish them from a raw ciphertext?)
Solution · Answer
The candidates encrypt to and modulo 55. The observed residue is therefore enough to choose between these two candidates. This inference uses the known candidate set and deterministic public encryption; it is not a general method for recovering arbitrary long messages.
Quick check
(Solve and with .)
Solution · Answer
The residues congruent to 3 modulo 11 in this range are . Only 36 is congruent to 1 modulo 5, so . Uniqueness modulo 55 follows from the theorem. Enumeration works for this small example but is not an efficient general strategy for large moduli.
The numerical examples represent messages by integers in the range from zero to . A text message needs a specified encoding into that range and a procedure to reverse it. Not every arbitrary sequence of bytes fits in one residue, and splitting into blocks introduces further design questions. These representational choices are part of the encryption scheme, not consequences of Fermat's theorem. They must be specified before claiming that a program can encrypt a text. The proofs above only establish the relationship between two modular exponentiations for an already chosen residue.
Comparing correctness and security
The correctness proof assumes the stated congruence between public and private exponents and concludes that encrypting and decrypting a valid residue returns that residue. It does not specify what an attacker can observe, whether they can request other encryptions or decryptions, or how their probability of guessing a message is measured. A security definition must specify those capabilities and a success event before a resistance claim can be assessed. Even perfectly computed modular powers retain the candidate-comparison weakness of deterministic encoding.
Correctness also does not mean every choice of parameters works. If , the argument combining congruences for two distinct primes and the stated product cannot simply be reused. If is not coprime to , the required inverse does not exist. The hypotheses correspond to concrete steps of key construction and proof.