The Central Idea
Coding and cryptography both transform information, but they solve different problems.
Coding often focuses on representing information reliably and detecting or correcting errors.
Cryptography focuses on protecting information and establishing security properties such as confidentiality, integrity, and authenticity.
The common mathematical theme is:
\[ \boxed{\text{represent information as discrete symbols and transform it by precise rules}} \]Information as Symbols
Before information can be transmitted or protected, it must be represented using symbols from an alphabet.
A binary alphabet is
\[ \boxed{\{0,1\}}. \]A binary string is a finite sequence such as
\[ 101101. \]The same idea applies to larger alphabets, including decimal digits, letters, bytes, or other discrete symbol sets.
Bits and Binary Strings
A bit is a binary digit.
A string of \(n\) bits has
\[ \boxed{2^n} \]possible values.
For \(8\) bits,
\[ 2^8=\boxed{256}. \]This counting principle is fundamental in digital representation and key spaces.
Fixed-Length Codes
A fixed-length code assigns codewords of equal length to symbols.
Suppose we encode four symbols:
| Symbol | Codeword |
|---|---|
| A | 00 |
| B | 01 |
| C | 10 |
| D | 11 |
Two bits are enough because
\[ 2^2=4. \]How Many Bits Are Needed?
To represent at least \(m\) distinct symbols using fixed-length binary codewords, choose the smallest integer \(n\) satisfying
\[ 2^n\ge m. \]Equivalently,
\[ \boxed{n=\lceil\log_2 m\rceil}. \]For \(20\) symbols,
\[ 2^4=16<20 \]while
\[ 2^5=32\ge20. \]Therefore, at least \(5\) bits are required.
Transmission Errors
A communication channel can alter data.
A transmitted bit
\[ 0 \]might be received as
\[ 1, \]or vice versa.
Coding theory adds structured redundancy so that certain errors can be detected or corrected.
Parity Bits
One simple error-detection method adds a parity bit.
Under even parity, the parity bit is chosen so that the total number of \(1\)s is even.
Suppose the data bits are
\[ 1011. \]There are three \(1\)s, so append a parity bit of \(1\):
\[ \boxed{10111}. \]The resulting five-bit word contains four \(1\)s.
What Parity Detects
A single parity bit detects any odd number of bit flips.
In particular, it detects every single-bit error.
But two bit flips can preserve parity.
Therefore, parity is useful but limited.
Checksums
A checksum is a compact value computed from a block of data and transmitted or stored with it.
The receiver recomputes the checksum and compares the result.
A mismatch suggests that the data changed.
Different checksum rules provide different levels of error detection.
Hamming Distance
The Hamming distance between two equal-length strings is the number of positions in which they differ.
For example,
\[ 101101 \]and
\[ 100111 \]differ in two positions.
Therefore,
\[ \boxed{d_H(101101,100111)=2}. \]Minimum Distance of a Code
A code is a set of permitted codewords.
Its minimum distance is the smallest Hamming distance between any two distinct codewords.
If the minimum distance is \(d_{\min}\), then larger values generally allow stronger error detection and correction.
Error Detection from Minimum Distance
A code with minimum distance \(d_{\min}\) can detect up to
\[ \boxed{d_{\min}-1} \]errors in a codeword.
For example, if
\[ d_{\min}=4, \]then up to
\[ \boxed{3} \]errors can be detected.
Error Correction from Minimum Distance
A code with minimum distance \(d_{\min}\) can correct up to
\[ \boxed{ \left\lfloor\frac{d_{\min}-1}{2}\right\rfloor } \]errors.
If
\[ d_{\min}=5, \]then
\[ \left\lfloor\frac{5-1}{2}\right\rfloor = \boxed{2}. \]Repetition Codes
A simple error-correcting idea is to repeat each bit.
For example:
\[ 0\mapsto000 \]and
\[ 1\mapsto111. \]If
\[ 111 \]is received as
\[ 101, \]majority decoding suggests the original bit was \(1\).
Repetition is easy to understand but inefficient because it uses many extra bits.
Redundancy and Efficiency
Error-control coding creates a tradeoff.
More redundancy can improve reliability, but it also increases the number of transmitted or stored symbols.
If a codeword contains \(k\) information bits and \(n-k\) redundant bits, then the code rate is
\[ \boxed{R=\frac{k}{n}}. \]Higher rate means less redundancy.
Security Goals
Cryptographic systems are often designed to support several distinct goals.
- Confidentiality: unauthorized parties should not learn the protected content.
- Integrity: unauthorized modification should be detectable.
- Authenticity: a receiver should be able to verify the claimed source or origin.
- Availability: authorized users should be able to access the system or information when needed.
Cryptography supports some of these goals directly and others only as part of a broader security system.
Plaintext and Ciphertext
The original readable message is called plaintext.
The transformed protected message is called ciphertext.
Encryption transforms plaintext into ciphertext:
\[ \boxed{C=E_K(P)}. \]Decryption transforms ciphertext back into plaintext:
\[ \boxed{P=D_K(C)}. \]Keys
A key is a parameter controlling a cryptographic transformation.
Security should depend on protecting appropriate keys rather than keeping the general algorithm secret.
This allows algorithms to be studied publicly while keys remain specific to users or sessions.
Key Spaces
If a key has \(n\) independently chosen binary bits, then the nominal key space contains
\[ \boxed{2^n} \]possible bit strings.
For \(128\) bits, the nominal space contains
\[ 2^{128} \]possibilities.
Actual security depends on much more than key-space size alone.
Classical Substitution
A substitution cipher replaces symbols according to a rule.
One of the simplest examples shifts letters through a cyclic alphabet.
If letters are represented by
\[ A=0,\ B=1,\ \ldots,\ Z=25, \]then a shift cipher can be written
\[ \boxed{E_k(x)\equiv x+k\pmod{26}}. \]Shift-Cipher Example
Let
\[ k=3. \]The letter A is represented by \(0\).
Encrypt:
\[ 0+3\equiv3\pmod{26}. \]The value \(3\) corresponds to D.
Therefore,
\[ \boxed{A\mapsto D}. \]This is useful for understanding modular structure, but simple shift ciphers are not suitable for modern secure communication.
Decryption in a Shift Cipher
If encryption is
\[ E_k(x)\equiv x+k\pmod{26}, \]then decryption subtracts the shift:
\[ \boxed{D_k(y)\equiv y-k\pmod{26}}. \]The arithmetic wraps around because calculations are performed modulo \(26\).
Affine Ciphers
A slightly richer classical transformation has the form
\[ \boxed{E(x)\equiv ax+b\pmod m}. \]For decryption to be possible, multiplication by \(a\) must be reversible modulo \(m\).
Therefore,
\[ \boxed{\gcd(a,m)=1}. \]This condition guarantees that \(a\) has a multiplicative inverse modulo \(m\).
Modular Inverses
An integer \(a^{-1}\) is a multiplicative inverse of \(a\) modulo \(m\) when
\[ aa^{-1}\equiv1\pmod m. \]For example,
\[ 5\cdot21=105 \]and
\[ 105\equiv1\pmod{26}. \]Therefore,
\[ \boxed{5^{-1}\equiv21\pmod{26}}. \]Why Coprimality Matters
If
\[ \gcd(a,m)\ne1, \]then multiplication by \(a\) may send different inputs to the same residue.
That makes the transformation noninvertible.
Reversible encryption transformations require enough mathematical structure to recover the original message uniquely.
Symmetric-Key Cryptography
In symmetric-key cryptography, communicating parties share secret key material used for encryption and decryption.
Conceptually,
\[ C=E_K(P) \]and
\[ P=D_K(C). \]A major operational challenge is distributing and protecting the shared key.
Public-Key Cryptography
In public-key cryptography, different but mathematically related keys perform complementary operations.
A public key can be distributed widely.
A private key is kept secret.
Public-key methods support applications such as key establishment, encryption, and digital signatures.
One-Way Mathematical Structure
Public-key systems rely on mathematical operations that are easy to perform in one direction but difficult to reverse without special information.
The exact security assumptions depend on the cryptographic construction.
Discrete mathematics enters through structures such as:
- modular arithmetic;
- prime numbers;
- finite groups;
- elliptic-curve groups;
- hard computational problems.
RSA: The Mathematical Skeleton
RSA is a public-key construction built from modular arithmetic and prime factorization relationships.
In a simplified mathematical outline:
- choose distinct primes \(p\) and \(q\);
- form \(n=pq\);
- compute a related totient quantity;
- choose a public exponent \(e\) satisfying the required coprimality condition;
- choose a private exponent \(d\) satisfying a modular inverse relation.
Real implementations require secure parameter sizes, padding, vetted libraries, and additional protections beyond this mathematical outline.
A Tiny RSA Arithmetic Example
For a classroom-scale illustration, choose
\[ p=5,\qquad q=11. \]Then
\[ n=pq=55. \]Euler's totient is
\[ \varphi(n)=(5-1)(11-1)=40. \]Choose
\[ e=3, \]since
\[ \gcd(3,40)=1. \]We need \(d\) such that
\[ 3d\equiv1\pmod{40}. \]One solution is
\[ \boxed{d=27}, \]because
\[ 3\cdot27=81\equiv1\pmod{40}. \]These tiny values are strictly instructional and provide no real security.
Hash Functions
A cryptographic hash function maps input data to a fixed-length output.
Conceptually,
\[ \boxed{h:\{0,1\}^\ast\rightarrow\{0,1\}^n}. \]The input may have arbitrary finite length, while the output has fixed length \(n\).
Important Hash Properties
Cryptographic hash functions are designed around properties such as:
- efficient evaluation;
- preimage resistance;
- second-preimage resistance;
- collision resistance;
- strong diffusion of input changes into output changes.
These properties are stronger than ordinary checksum behavior.
Collisions Must Exist
A fixed-length hash has finitely many outputs but accepts arbitrarily many possible inputs.
Therefore, by the pigeonhole principle, distinct inputs must sometimes map to the same output.
Such a pair is called a collision.
Cryptographic design does not eliminate collisions. It aims to make useful collisions computationally difficult to find.
The Birthday Effect
For a hash with \(N\) possible outputs, collisions become statistically relevant after far fewer than \(N\) random samples.
The rough scale is
\[ \boxed{\sqrt{N}}. \]For an \(n\)-bit hash,
\[ N=2^n, \]so the collision scale is roughly
\[ 2^{n/2}. \]This is the same combinatorial phenomenon underlying the birthday paradox.
Message Authentication
Encryption alone does not automatically prove that a message was not altered.
Message-authentication mechanisms are designed to help detect unauthorized modification and verify that the sender possessed appropriate secret information.
This separates confidentiality from integrity and authenticity.
Digital Signatures
Digital signatures use asymmetric cryptographic structure to provide verifiable evidence tied to a private signing key.
A simplified conceptual workflow is:
- compute a digest of the message;
- produce a signature using the private signing key;
- verify the signature using the corresponding public key.
Secure signature systems rely on standardized constructions and careful key management.
Authentication Is Not Authorization
Authentication answers:
Who or what is this?
Authorization answers:
What is this identity allowed to do?
A system can authenticate an identity correctly and still deny access to a protected action.
Passwords and Hashing
Secure systems generally should not store ordinary user passwords in plaintext.
Password-verification systems typically use specialized password-hashing constructions with salts and deliberately expensive processing.
General-purpose fast hashes alone are not the preferred design for password storage.
Salts
A salt is a value combined with a password before the password-verification function is applied.
Salts help ensure that identical passwords do not automatically produce identical stored verification values.
Salts are normally stored with the resulting password verifier; they are not intended to serve as secret encryption keys.
Randomness
Cryptographic security often depends on unpredictable values.
Examples include:
- keys;
- nonces;
- session secrets;
- random challenges.
Predictable randomness can undermine otherwise sound cryptographic mathematics.
Nonces
A nonce is a value intended for limited or one-time use within a protocol.
Depending on the construction, a nonce may need to be:
- unique;
- unpredictable;
- or both.
The exact requirement depends on the protocol.
Security Depends on Protocols, Not Just Algorithms
A strong cryptographic primitive can be used incorrectly.
Secure systems also depend on:
- key generation;
- key storage;
- key rotation;
- message formatting;
- authentication order;
- failure handling;
- software implementation;
- system permissions.
Security is therefore a system property, not merely an equation.
Threat Models
A threat model states what capabilities an adversary is assumed to have and what assets must be protected.
Useful questions include:
- Can an attacker observe messages?
- Can an attacker modify messages?
- Can an attacker impersonate a participant?
- Can an attacker access stored data?
- What information is considered sensitive?
A security claim is meaningful only relative to assumptions about the environment and adversary.
Attack Surface
The attack surface is the collection of interfaces, components, permissions, inputs, and dependencies through which a system may be exposed.
Reducing unnecessary services, privileges, and interfaces can reduce attack surface.
This is an example of how discrete system design interacts with security reasoning.
Least Privilege
The principle of least privilege says that a user, process, or component should receive only the permissions needed for its required role.
Limiting privileges can reduce the consequences of mistakes or compromise.
Defense in Depth
Defense in depth uses multiple protective layers rather than depending on a single mechanism.
Examples of layers can include:
- authentication;
- authorization;
- encryption;
- network segmentation;
- logging;
- backup and recovery;
- monitoring.
The idea is analogous to redundancy in reliable systems.
Security and Reliability Are Different
Reliability asks whether a system continues to operate correctly under failures or random disturbances.
Security asks whether the system maintains required protections even in the presence of intentional adversarial behavior.
A system can be reliable but insecure, or secure against some threats but operationally unreliable.
Cryptography and Coding Are Different
Error-correcting codes are designed primarily to handle accidental corruption.
Cryptographic mechanisms are designed to address adversarial threats.
A parity bit may detect a transmission error, but it does not prevent an attacker from changing the data and recomputing the parity.
The source of uncertainty matters.
Common Error: Assuming Encoding Is Encryption
Encoding changes representation.
Encryption uses a cryptographic transformation intended to protect information under a specified threat model.
Converting text to binary, hexadecimal, or another visible representation does not by itself provide confidentiality.
Common Error: Assuming Compression Is Encryption
Compression reduces redundancy or file size.
It is not a security mechanism.
A compressed file can still be readable by anyone who can decompress it.
Common Error: Treating a Hash as Reversible Encryption
Encryption is designed to permit decryption with appropriate key material.
A cryptographic hash is not intended to be inverted to recover the original arbitrary input.
These are fundamentally different operations.
Common Error: Using Encryption Without Integrity Protection
Confidentiality and integrity are different properties.
A system should not assume that ciphertext is automatically protected from meaningful tampering merely because it is unreadable.
Modern secure designs use authenticated constructions or otherwise provide explicit integrity protection.
Common Error: Reusing Sensitive Random Values Incorrectly
Some cryptographic constructions require nonces, initialization values, or ephemeral secrets to be unique or unpredictable.
Reuse can seriously weaken security.
The exact requirement must be followed for the specific standardized construction being used.
Common Error: Designing a New Cipher for Real Security
A mathematically interesting transformation is not automatically a secure cryptographic system.
Real security should rely on publicly studied standards and well-reviewed implementations rather than improvised ciphers.
Classical and toy systems are valuable for learning the mathematics, not for protecting sensitive modern data.
A Reliable Procedure for Coding Problems
- Identify the source alphabet.
- Determine the available code symbols.
- Specify codeword length or code structure.
- Count the available codewords.
- Identify the expected error model.
- Calculate parity, checksum, or distance properties as required.
- Determine the detection or correction capability.
- Check the tradeoff between redundancy and efficiency.
A Reliable Procedure for Classical Modular-Cipher Exercises
- Map the symbol alphabet to integers.
- State the modulus.
- Apply the encryption function.
- Reduce results modulo the alphabet size.
- For reversible multiplicative rules, verify the required gcd condition.
- Find modular inverses when needed.
- Apply the inverse transformation for decryption.
- Convert numerical results back to symbols.
A Reliable Procedure for Security Reasoning
- Identify the asset being protected.
- Identify the required security property.
- State the threat model.
- Separate encoding, compression, encryption, hashing, and authentication roles.
- Use standardized constructions appropriate to the requirement.
- Protect keys and sensitive state.
- Check randomness and nonce requirements.
- Use least privilege and layered controls.
- Plan for failure, recovery, and key compromise.
Example: Full Error-Detection Workflow
Suppose the data bits are
\[ 1101010. \]Count the number of \(1\)s:
\[ 4. \]Under even parity, the total is already even, so append
\[ \boxed{0}. \]The transmitted word is
\[ \boxed{11010100}. \]If one bit flips during transmission, the received word will contain an odd number of \(1\)s and the parity check will fail.
Example: Full Hamming-Distance Workflow
Compare
\[ x=10101101 \]and
\[ y=11100100. \]Compare position by position.
They differ in positions 2, 4, and 8.
Therefore,
\[ \boxed{d_H(x,y)=3}. \]Example: Full Modular-Cipher Workflow
Use the toy shift rule
\[ E(x)\equiv x+7\pmod{26}. \]Suppose the plaintext symbol is H, represented by
\[ H=7. \]Encrypt:
\[ 7+7=14. \]The value \(14\) corresponds to O.
Thus,
\[ \boxed{H\mapsto O}. \]Decrypt by subtracting \(7\):
\[ 14-7=7, \]recovering H.
Practice 1: Binary Possibilities
How many distinct \(10\)-bit strings are possible?
Practice 2: Minimum Bit Length
What is the minimum fixed binary codeword length needed to represent \(50\) distinct symbols?
Practice 3: Even Parity
Under even parity, what parity bit should be appended to
\[ 1010011? \]Practice 4: Hamming Distance
Find the Hamming distance between
\[ 110010 \]and
\[ 100111. \]Practice 5: Detection Capability
A code has minimum distance
\[ d_{\min}=6. \]How many errors can it guarantee to detect?
Practice 6: Correction Capability
A code has minimum distance
\[ d_{\min}=7. \]How many errors can it guarantee to correct?
Practice 7: Modular Inverse Check
Does \(7\) have a multiplicative inverse modulo \(26\)?
Explain using the gcd criterion.
Practice 8: Shift Encryption
Let
\[ A=0,\ B=1,\ldots,Z=25. \]Encrypt the value
\[ x=20 \]using
\[ E(x)\equiv x+9\pmod{26}. \]Practice 9: Hash Output Count
How many possible outputs does a \(16\)-bit hash have?
Practice 10: Security Property
Which security property is primarily concerned with detecting unauthorized modification of data?
Practice Answers
Practice 1
\[ 2^{10}=\boxed{1024}. \]Practice 2
Since
\[ 2^5=32<50 \]and
\[ 2^6=64\ge50, \]the minimum length is
\[ \boxed{6\text{ bits}}. \]Practice 3
The string
\[ 1010011 \]contains four \(1\)s, which is already even.
Therefore, append
\[ \boxed{0}. \]Practice 4
Compare:
\[ 110010 \] \[ 100111. \]The strings differ in three positions.
\[ \boxed{d_H=3}. \]Practice 5
\[ d_{\min}-1=6-1=\boxed{5}. \]Practice 6
\[ \left\lfloor\frac{7-1}{2}\right\rfloor = \left\lfloor3\right\rfloor = \boxed{3}. \]Practice 7
Yes.
\[ \gcd(7,26)=1. \]Therefore, \(7\) has a multiplicative inverse modulo \(26\).
Practice 8
\[ 20+9=29. \]Reduce modulo \(26\):
\[ 29\equiv\boxed{3}\pmod{26}. \]The value \(3\) corresponds to D.
Practice 9
\[ 2^{16}=\boxed{65536}. \]Practice 10
The relevant property is
\[ \boxed{\text{integrity}}. \]What to Remember
Coding, security, and cryptography use discrete structures to represent, protect, verify, and transmit information.
- \(n\) bits produce \(2^n\) possible strings;
- parity and checksums detect some transmission errors;
- Hamming distance measures symbol differences;
- minimum distance determines error-detection and correction capability;
- modular arithmetic supports reversible symbol transformations;
- symmetric cryptography uses shared secret key material;
- public-key cryptography separates public and private key roles;
- hash functions map arbitrary-length input to fixed-length output;
- authentication and authorization are different;
- security depends on protocols, implementation, key management, and assumptions;
- toy ciphers illustrate mathematics but should not be used for real protection.
The central habit is: identify what property is required—reliable representation, confidentiality, integrity, authenticity, or something else—before choosing the mathematical mechanism.
Where We Go Next
Coding and cryptography show how discrete structures protect information as it is represented and transmitted. The next applied problem family shifts from information systems to operational systems in which customers, jobs, inventory, and service capacity interact over time.
The next lesson, Inventory and Queueing, examines stock levels, demand, replenishment, waiting lines, service rates, utilization, and stochastic congestion.