The Central Idea
A cryptographic system transforms a message into another form according to a mathematical rule.
In simplified notation,
\[ \boxed{\text{plaintext}\longrightarrow\text{ciphertext}}. \]A corresponding recovery process reverses the transformation:
\[ \boxed{\text{ciphertext}\longrightarrow\text{plaintext}}. \]Modular arithmetic provides a natural setting because it creates finite cyclic systems in which arithmetic can be controlled precisely.
Plaintext and Ciphertext
The original readable information is called plaintext.
The transformed representation is called ciphertext.
For example, a letter might first be represented numerically and then transformed by a modular rule.
Encoding Symbols as Numbers
To use arithmetic on text, assign numbers to symbols.
One simple classroom convention is
\[ A=0,\ B=1,\ C=2,\ldots,Z=25. \]Then the alphabet naturally fits into arithmetic modulo \(26\).
Under this convention,
\[ A\leftrightarrow0, \qquad M\leftrightarrow12, \qquad Z\leftrightarrow25. \]A Shift Cipher
A simple substitution rule adds a fixed amount modulo \(26\).
If the shift is \(k\), encryption can be modeled as
\[ \boxed{E(x)\equiv x+k\pmod{26}}. \]Decryption subtracts the same amount:
\[ \boxed{D(y)\equiv y-k\pmod{26}}. \]Example: Shift by \(3\)
Using
\[ E(x)\equiv x+3\pmod{26}, \]the letter \(B\) is represented by \(1\).
Therefore,
\[ E(1)\equiv1+3\equiv4\pmod{26}. \]The number \(4\) represents \(E\).
Thus
\[ \boxed{B\longrightarrow E}. \]Wraparound Is Modular Reduction
Suppose the same shift is applied to \(Y\), represented by \(24\).
\[ 24+3=27. \]Reduce modulo \(26\):
\[ 27\equiv1\pmod{26}. \]Therefore,
\[ \boxed{Y\longrightarrow B}. \]The apparent wraparound of the alphabet is simply modular arithmetic.
Why Shift Ciphers Are Weak
A shift cipher has only finitely many possible shifts.
For an alphabet of \(26\) symbols, there are only \(26\) possible values of \(k\), and one of them produces no change.
Such systems are mathematically useful for learning modular structure, but they are not considered secure for modern communication.
Affine Modular Transformations
A more general classroom transformation has the form
\[ \boxed{E(x)\equiv ax+b\pmod{26}}. \]Here \(a\) multiplies the symbol value and \(b\) shifts it.
To make the transformation reversible, multiplication by \(a\) must itself be reversible modulo \(26\).
The Invertibility Condition
The coefficient \(a\) has a multiplicative inverse modulo \(26\) exactly when
\[ \boxed{\gcd(a,26)=1}. \]Therefore, a reversible affine transformation requires \(a\) to be relatively prime to \(26\).
Example: A Valid Multiplicative Coefficient
Consider
\[ a=5. \]Since
\[ \gcd(5,26)=1, \]the number \(5\) has an inverse modulo \(26\).
In fact,
\[ 5\cdot21=105\equiv1\pmod{26}. \]Therefore,
\[ \boxed{5^{-1}\equiv21\pmod{26}}. \]Example: An Invalid Multiplicative Coefficient
Consider
\[ a=2. \]Since
\[ \gcd(2,26)=2, \]the number \(2\) has no multiplicative inverse modulo \(26\).
Thus a rule based on
\[ 2x+b\pmod{26} \]cannot be reversed uniquely for every symbol.
Decrypting an Affine Transformation
Suppose
\[ y\equiv ax+b\pmod{26} \]and \(a\) is invertible.
Subtract \(b\):
\[ y-b\equiv ax\pmod{26}. \]Multiply by \(a^{-1}\):
\[ \boxed{ x\equiv a^{-1}(y-b)\pmod{26} }. \]Example: Affine Encoding
Use
\[ E(x)\equiv5x+8\pmod{26}. \]Encode \(D\), represented by \(3\):
\[ E(3)\equiv5(3)+8=23\pmod{26}. \]The number \(23\) represents \(X\).
Therefore,
\[ \boxed{D\longrightarrow X}. \]Example: Affine Decoding
Since
\[ 5^{-1}\equiv21\pmod{26}, \]decrypt \(y=23\):
\[ x\equiv21(23-8)\pmod{26}. \]Thus
\[ x\equiv21(15)=315\pmod{26}. \]Since
\[ 315\equiv3\pmod{26}, \]we recover
\[ \boxed{x=3}, \]which corresponds to \(D\).
Keys
A key is information controlling a cryptographic transformation.
In the affine rule
\[ E(x)\equiv ax+b\pmod{26}, \]the values \(a\) and \(b\) function as key parameters.
Knowing the transformation allows the corresponding inverse transformation to be constructed when \(a\) is invertible.
Symmetric-Key Idea
In a symmetric-key system, communicating parties share secret information used for both encryption and decryption.
The central operational challenge is not only constructing a reversible transformation but also distributing and protecting the shared secret.
Classical substitution systems illustrate this basic model.
Public-Key Idea
A public-key system separates key information into two related parts:
- a public key that may be distributed;
- a private key that is kept secret.
The mathematical design allows an operation performed with one key to be related to an inverse or verification operation involving the other.
Why Number Theory Appears
Public-key systems often depend on arithmetic that is easy to perform in one direction but difficult to reverse without special information.
Introductory examples use concepts already developed in this unit:
- prime numbers;
- prime factorization;
- greatest common divisors;
- Euler's totient function;
- modular inverses;
- modular exponentiation.
A Simplified RSA-Style Framework
A standard classroom model begins with two distinct primes
\[ p \qquad\text{and}\qquad q. \]Form
\[ \boxed{n=pq}. \]For distinct primes,
\[ \boxed{\varphi(n)=(p-1)(q-1)}. \]These quantities establish the modular system used for exponent-based transformations.
Choosing an Exponent
Choose an integer \(e\) satisfying
\[ \boxed{\gcd(e,\varphi(n))=1}. \]This condition ensures that \(e\) has a multiplicative inverse modulo \(\varphi(n)\).
That inverse is an integer \(d\) satisfying
\[ \boxed{ed\equiv1\pmod{\varphi(n)}}. \]A Small Classroom Example
Choose
\[ p=5,\qquad q=11. \]Then
\[ n=5\cdot11=55 \]and
\[ \varphi(55) = (5-1)(11-1) = 40. \]Choosing \(e\) and \(d\)
Choose
\[ e=3. \]Since
\[ \gcd(3,40)=1, \]an inverse exists modulo \(40\).
We need \(d\) such that
\[ 3d\equiv1\pmod{40}. \]Since
\[ 3\cdot27=81\equiv1\pmod{40}, \]we may take
\[ \boxed{d=27}. \]Toy Exponent Transformation
In a simplified RSA-style classroom example, a numerical message \(m\) smaller than \(n\) may be transformed using
\[ \boxed{c\equiv m^e\pmod n}. \]Recovery uses
\[ \boxed{m\equiv c^d\pmod n}. \]The exponents \(e\) and \(d\) are linked by
\[ ed\equiv1\pmod{\varphi(n)}. \]Example: Transforming a Small Message
Using
\[ n=55,\qquad e=3, \]transform
\[ m=2. \]Compute
\[ c\equiv2^3=8\pmod{55}. \]Therefore,
\[ \boxed{c=8}. \]Recovering the Small Message
Use
\[ d=27. \]Then
\[ m\equiv8^{27}\pmod{55}. \]Rather than expand directly, use repeated squaring:
\[ 8^2=64\equiv9\pmod{55}, \] \[ 8^4\equiv9^2=81\equiv26\pmod{55}, \] \[ 8^8\equiv26^2=676\equiv16\pmod{55}, \] \[ 8^{16}\equiv16^2=256\equiv36\pmod{55}. \]Completing the Recovery
Since
\[ 27=16+8+2+1, \]we have
\[ 8^{27} = 8^{16}8^8 8^2 8. \]Reduce modulo \(55\):
\[ 36\cdot16\cdot9\cdot8. \]Step by step,
\[ 36\cdot16=576\equiv26\pmod{55}, \] \[ 26\cdot9=234\equiv14\pmod{55}, \] \[ 14\cdot8=112\equiv2\pmod{55}. \]Thus
\[ \boxed{8^{27}\equiv2\pmod{55}}, \]recovering the original message.
Why the Exponents Reverse Each Other
The relation
\[ ed\equiv1\pmod{\varphi(n)} \]means
\[ ed=1+k\varphi(n) \]for some integer \(k\).
For message values relatively prime to \(n\), Euler's theorem gives
\[ m^{\varphi(n)}\equiv1\pmod n. \]Therefore,
\[ m^{ed} = m^{1+k\varphi(n)} \equiv m \pmod n. \]This explains the basic exponent-reversal mechanism in the simplified setting.
The Euclidean Algorithm Appears Again
To compute \(d\), we solve
\[ ed\equiv1\pmod{\varphi(n)}. \]This is a modular inverse problem.
The Extended Euclidean Algorithm provides a systematic way to find \(d\) whenever
\[ \gcd(e,\varphi(n))=1. \]Prime Factorization Appears Again
In the classroom framework,
\[ n=pq. \]Knowing \(p\) and \(q\) makes
\[ \varphi(n)=(p-1)(q-1) \]easy to compute.
This illustrates why the arithmetic structure of a composite number can matter greatly in cryptographic design.
Public and Private Information
In a simplified RSA-style description:
- \(n\) and \(e\) may be treated as public parameters;
- \(d\) is kept private;
- the prime factors \(p\) and \(q\) are also sensitive in the ordinary construction.
The mathematical relationship between these values makes the two exponent operations compatible.
Encryption Is Not the Only Goal
Cryptographic systems can support several distinct goals:
- confidentiality — limiting who can read information;
- integrity — detecting unauthorized modification;
- authentication — establishing the identity or origin of a message;
- digital signatures — providing verifiable evidence tied to a private key.
Different cryptographic tools address different goals.
Digital-Signature Idea
Public-key mathematics can also be used in a reversed conceptual role: a private-key operation can produce information that others verify using the corresponding public key.
In real systems, signatures are applied to carefully constructed message digests and standardized encodings rather than directly to arbitrary raw messages.
Hash Functions
A cryptographic hash function transforms data of varying length into a fixed-length digest.
Hashing is not the same as encryption.
Encryption is designed to be reversible with appropriate key information, while a cryptographic hash is designed as a one-way transformation used for comparison, integrity checks, and related security constructions.
Classroom Examples Are Not Production Security
Small primes and tiny moduli are useful for understanding the mathematics, but they provide no meaningful modern security.
Real cryptographic systems use standardized algorithms, large parameters, secure randomness, careful padding or encoding rules, authenticated modes, and rigorously tested implementations.
The examples in this lesson are mathematical models, not deployment guidance.
Why “Invent Your Own Cipher” Is Risky
A reversible mathematical transformation is not automatically a secure cryptographic system.
Security depends on more than hiding a formula. It requires resistance to known analytical attacks, secure key handling, appropriate randomness, implementation correctness, and carefully defined threat assumptions.
Modern applications should rely on established, reviewed cryptographic standards rather than ad hoc designs.
Common Error: Confusing Encoding with Encryption
Converting
\[ A\mapsto0,\quad B\mapsto1,\ldots \]is an encoding convention.
Encoding changes representation but does not by itself provide secrecy.
Encryption applies a key-controlled transformation intended to protect information.
Common Error: Assuming Every Modular Multiplier Is Reversible
In
\[ E(x)\equiv ax+b\pmod n, \]the multiplier \(a\) must satisfy
\[ \gcd(a,n)=1 \]for a multiplicative inverse to exist.
Without an inverse, different inputs may collapse to the same output.
Common Error: Using Tiny Examples as Real Keys
Values such as
\[ p=5,\qquad q=11 \]are chosen only to make arithmetic visible by hand.
Their product
\[ n=55 \]can be factored immediately and offers no practical security.
Common Error: Assuming Mathematics Alone Guarantees Security
A sound mathematical idea can still be undermined by poor implementation.
Real systems must consider:
- random-number quality;
- key generation;
- key storage;
- message formatting;
- side-channel leakage;
- protocol design;
- software correctness.
A Reliable Procedure for a Shift-Cipher Exercise
- Choose a numerical representation for the symbols.
- Identify the modulus.
- Add the shift value.
- Reduce modulo the alphabet size.
- Convert the resulting number back to a symbol.
- For decryption, subtract the same shift and reduce again.
A Reliable Procedure for an Affine-Cipher Exercise
- Write the rule \(E(x)\equiv ax+b\pmod n\).
- Check that \(\gcd(a,n)=1\).
- Find \(a^{-1}\pmod n\).
- Encrypt with \(ax+b\) and reduce modulo \(n\).
- Decrypt with \(a^{-1}(y-b)\) and reduce modulo \(n\).
- Verify that the original symbol value is recovered.
A Reliable Procedure for a Toy Public-Key Example
- Choose small distinct primes \(p\) and \(q\) for classroom arithmetic.
- Compute \(n=pq\).
- Compute \(\varphi(n)=(p-1)(q-1)\).
- Choose \(e\) relatively prime to \(\varphi(n)\).
- Find \(d\) satisfying \(ed\equiv1\pmod{\varphi(n)}\).
- Transform a small numerical message with \(c\equiv m^e\pmod n\).
- Recover it with \(m\equiv c^d\pmod n\).
- Use repeated squaring rather than direct expansion for large powers.
- Treat the exercise as a mathematical model, not as a secure implementation.
Example: Full Affine Workflow
Use
\[ E(x)\equiv7x+4\pmod{26}. \]First verify
\[ \gcd(7,26)=1. \]The inverse of \(7\) modulo \(26\) is \(15\), because
\[ 7\cdot15=105\equiv1\pmod{26}. \]Therefore the decryption rule is
\[ \boxed{ D(y)\equiv15(y-4)\pmod{26} }. \]Checking the Affine Workflow
Encode \(C\), represented by \(2\):
\[ E(2)\equiv7(2)+4=18\pmod{26}. \]The value \(18\) represents \(S\).
Decrypt:
\[ D(18)\equiv15(18-4)=15(14)=210\pmod{26}. \]Since
\[ 210\equiv2\pmod{26}, \]the original symbol value is recovered.
Practice 1: Shift Cipher
Using
\[ A=0,\ldots,Z=25 \]and
\[ E(x)\equiv x+5\pmod{26}, \]encode \(H\).
Practice 2: Shift Decryption
Using the same shift \(5\), decrypt the numerical value
\[ 2. \]Practice 3: Invertibility
Determine whether
\[ E(x)\equiv6x+1\pmod{26} \]is reversible for every residue class.
Practice 4: Modular Inverse
Find the inverse of
\[ 9 \]modulo \(26\).
Practice 5: Affine Encoding
Use
\[ E(x)\equiv9x+2\pmod{26} \]to encode the numerical symbol value
\[ x=4. \]Practice 6: Affine Decoding
Using the same rule, decrypt the resulting value from Practice 5.
Practice 7: Toy Totient
Let
\[ p=7,\qquad q=13. \]Compute
\[ n \]and
\[ \varphi(n). \]Practice 8: Choose a Valid Exponent
For the values in Practice 7, determine whether
\[ e=5 \]is relatively prime to \(\varphi(n)\).
Practice 9: Find the Inverse Exponent
If
\[ \varphi(n)=72 \]and
\[ e=5, \]find \(d\) satisfying
\[ 5d\equiv1\pmod{72}. \]Practice 10: Identify the Limitation
A student proposes using
\[ p=3,\qquad q=5 \]as the basis for a real secure public-key system.
Explain why this is appropriate only as a classroom example.
Practice Answers
Practice 1
\(H\) corresponds to
\[ 7. \]Therefore,
\[ 7+5=12. \]The value \(12\) corresponds to \(M\).
Thus
\[ \boxed{H\longrightarrow M}. \]Practice 2
Subtract the shift:
\[ 2-5=-3. \]Reduce modulo \(26\):
\[ -3\equiv23\pmod{26}. \]Therefore,
\[ \boxed{23}. \]Under the stated encoding, \(23\) corresponds to \(X\).
Practice 3
\[ \gcd(6,26)=2. \]Since the GCD is not \(1\), \(6\) has no multiplicative inverse modulo \(26\).
Therefore,
\[ \boxed{\text{the transformation is not reversible for every class}}. \]Practice 4
We seek \(u\) such that
\[ 9u\equiv1\pmod{26}. \]Since
\[ 9\cdot3=27\equiv1\pmod{26}, \]we have
\[ \boxed{9^{-1}\equiv3\pmod{26}}. \]Practice 5
\[ E(4)\equiv9(4)+2=38\pmod{26}. \]Since
\[ 38\equiv12\pmod{26}, \]the encoded value is
\[ \boxed{12}. \]Practice 6
Since
\[ 9^{-1}\equiv3\pmod{26}, \]decrypt \(12\):
\[ x\equiv3(12-2)=30\pmod{26}. \]Therefore,
\[ \boxed{x\equiv4\pmod{26}}, \]recovering the original value.
Practice 7
\[ n=7\cdot13=91. \]Since the primes are distinct,
\[ \varphi(91) = (7-1)(13-1) = 6\cdot12 = 72. \]Therefore,
\[ \boxed{n=91,\qquad\varphi(n)=72}. \]Practice 8
\[ \gcd(5,72)=1. \]Therefore,
\[ \boxed{e=5\text{ is valid for the toy arithmetic condition}}. \]Practice 9
We need
\[ 5d\equiv1\pmod{72}. \]Since
\[ 5\cdot29=145=72(2)+1, \]we obtain
\[ \boxed{d=29}. \]Practice 10
The modulus would be
\[ n=3\cdot5=15. \]Factoring \(15\) is immediate, so the number-theoretic structure is fully exposed.
Such tiny values are useful only for hand calculations and conceptual demonstrations. Real cryptographic systems require standardized schemes and parameters large enough to resist practical attacks.
What to Remember
- Cryptography uses mathematical transformations to support goals such as confidentiality, integrity, and authentication.
- Encoding symbols as integers allows modular arithmetic to act on messages.
- Shift ciphers use addition modulo the alphabet size.
- Affine transformations require an invertible multiplier, so \(\gcd(a,n)=1\).
- Modular inverses provide the mathematical mechanism for reversing multiplication-based transformations.
- Public-key ideas separate public and private key information.
- Simplified RSA-style arithmetic uses primes, \(\varphi(n)\), modular inverses, and modular exponentiation.
- Classroom examples illustrate structure but are not secure implementations.
The central mathematical theme is: cryptographic transformations depend on carefully chosen modular operations whose inverse behavior is controlled by number-theoretic structure.
Where We Go Next
Cryptography shows how divisibility, primes, modular inverses, and power cycles can work together in an applied setting. The next lesson, Integer Patterns and Arithmetic Functions, returns to the structure of the integers themselves and studies functions and recurring patterns built from divisors, primes, and multiplicative properties.