Digital Signatures and Public Key Infrastructure Practice Flashcards

Administrative Updates and Assignment 3 Information

• Assignment 3 Details:     * Assignment 3 is currently available.     * The due date is $April\,23$, which falls after the mid-semester break.     * The assignment focuses on public key cryptography.     * Question 1 & 2: These are calculation-based. Students may use any software, such as Wolfram Alpha, to complete them.     * Topics Covered:         * RSA padding using random numbers.         * RSA OAEP (Optimal Asymmetric Encryption Padding).         * Digital Signatures (the focus of the current lecture).

• Student Feedback and Room Logistics:     * Concerns regarding the small TV screens in the current room were acknowledged. These rooms are typically used for tutorials rather than lectures.     * A lack of power outlets on the tables was noted as a limitation of the current facility.     * The course is timetabled in the current room for the remainder of the semester, but the instructor will aim for rooms with larger screens and better power access in future years.

• Exam and Course Pace:     * The exact date of the final exam is currently unknown. Exam timetables are usually released around week $9$ or $10$.     * The course is a postgraduate course and moves at a fast pace.     * There is a distinction between the technical depth of the lectures and what is required for the exam. Students are encouraged to review old exam papers to understand the necessary level of understanding.     * A revision lecture will be held at the end of the course to discuss exam expectations and the required level of detail in answers.

Public Key Infrastructure (PKI) and Trust

• The Trust Problem: When sending a message to a recipient (e.g., Alice), the sender must know Alice's public key. A man-in-the-middle could intercept the request and provide a malicious key instead.

• Establishing Trust: Trust cannot be created from nothing. It requires either a face-to-face exchange (e.g., using a USB stick) or reliance on a trusted entity.

• Mechanism of PKI:     * PKI uses digital signatures to verify identities.     * Devices come pre-installed with public keys from trusted manufacturers like Apple, Google, and Microsoft, or from Certification Authorities (CAs).     * Alice provides her public key along with a certificate signed by a trusted authority. The sender verifies the signature on the certificate using the pre-installed public keys.

• Root of Trust: The ultimate root of trust is the assumption that the device was purchased from a reliable source and that the initial operating system installation (e.g., iOS, Android, macOS) was legitimate. Digital signatures are the fundamental requirement for this entire infrastructure to work.

Digital Signature Fundamentals

• Definition: A digital signature scheme consists of three distinct algorithms:     * Key Generation: Generates a public key ($PK$) and a matching private/secret key ($SK$).     * Signing Algorithm: Uses the private key to generate a signature on a specific message or piece of information.     * Verify Algorithm: Uses the public key, the message, and the signature to either accept or reject the signature.

• Comparison to MACs (Message Authentication Codes):     * In a MAC, the same secret key is used for both signing and verifying.     * In a digital signature, a private key is used for signing, while a public key is used for verification.     * Signatures provide authentication but not privacy (privacy is the role of encryption).

• Advantages of Public Key Signatures:     * One-to-Many Verification: A signature can be generated once and verified by anyone with the public key.     * Software Update Example: Companies like Adobe or Microsoft can sign a single software update and distribute it to millions of users, all of whom can verify the signature with the same public key. If using MACs, the company would have to sign a unique version for every individual phone or device, which is impractical.

Security Model: Existential Forgery under Adaptive Chosen Message Attack

• Forgery: The ability to generate a valid signature without knowledge of the secret key.

• Adaptive Chosen Message Attack:     * The attacker can access an oracle and request valid signatures for any number of messages ($m_1, m_2, \dots, m_n$).     * The attacker then attempts to create a forgery for a new message ($m$).

• Existential Forgery: The attacker wins if they can produce a valid signature for any message, even a completely meaningless one, provided that message was not one of the messages signed by the oracle during the attack.

• Security Strength: While this model seems absurdly strong, modern schemes are designed to remain secure even under these conditions.

The Role of Hash Functions in Signatures

• Efficiency: Documents and files (e.g., images, large Word documents) can be massive. Standard signature algorithms cannot efficiently process such large, arbitrary-length data directly.

• Implementation:     * The document is first hashed into a short, fixed-length string (e.g., $256\,\text{bits}$).     * The signature is performed only on this hash.

• Collision Resistance Requirement:     * Because hash functions map large inputs to fixed-size outputs, collisions (two different documents with the same hash) theoretically exist.     * If an attacker finds two documents with the same hash, the signature for one will be valid for the other.     * Therefore, collision-resistant hash functions (e.g., SHA-3) are a fundamental requirement for the integrity of digital signatures.

• RSA Hashing Requirements: Because an RSA modulus ($n$) is typically large ($2,000$ or $4,000\,\text{bits}$), the document may be processed through a sponge construction to squeeze out enough bits to match the necessary size.

RSA Digital Signatures

• Algorithm Logic: RSA operations are reversible. While encryption uses the public key first, signatures use the private key first.

• Public/Private Parameters:     * Public Key: $(n, e)$.     * Private Key: $d$.

• RSA Encryption/Decryption Review:     * Encrypt: $c = m^e \pmod{n}$.     * Decrypt: $m = c^d \pmod{n}$.

• RSA Signing Process:     1. Take a document and calculate its hash: $h = H(m)$.     2. Treat the hash as an integer and raise it to the power of the private key: $s = h^d \pmod{n}$.

• RSA Verification Process:     1. The receiver recomputes the hash of the message: $h = H(m)$.     2. The receiver raises the signature to the power of the public exponent: $v = s^e \pmod{n}$.     3. If $v = h$, the signature is accepted. This works because $(h^d)^e \equiv h \pmod{n}$.

• Security Note: To prove this is secure under the adaptive chosen message attack model, the hash function must be modeled as a "random oracle."

Discrete Logarithm Signatures (Schnorr-style)

• Public Parameters:     * Prime $p$.     * Generator $g$.     * Prime order $r$, where $r$ is the smallest integer such that $g^r \equiv 1 \pmod{p}$.

• Alice's Keys:     * Private Key: $a$.     * Public Key: $h = g^a \pmod{p}$.

• The Signing Process:     1. Alice chooses a random integer $b$ where $1 \le b \le r$.     2. Compute $s_0 = g^b \pmod{p}$.     3. Concatenate the message ($m$) with $s_0$ and hash it: $s_1 = H(m \parallel s_0)$.     4. Compute $s_2 = b + (a \times s_1) \pmod{r}$.     5. The resulting signature is the pair $(s_1, s_2)$.

• The Verification Process:     1. The verifier recomputes a value based on the signature and public key: $v = g^{s_2} \times h^{-s_1} \pmod{p}$.     2. The verifier hashes the message concatenated with $v$: $H(m \parallel v)$.     3. If this hash equals $s_1$, the signature is valid.

• Mathematical Proof of Verification:     * $g^{s_2} \times h^{-s_1} = g^{(b + a s_1)} \times (g^a)^{-s_1}$.     * Substitute: $g^{(b + a s_1)} \times g^{(-a s_1)} = g^{(b + a s_1 - a s_1)} = g^b$.     * Since $g^b = s_0$, the result of the calculation is the original $s_0$ used in the signing hash.

• Security Considerations:     * Self-referential Logic: Forgers cannot easily pick $s_1$ and $s_2$ to satisfy the hash because the hash output depends on the inputs in a circular way. Only the private key owner can "fix up" $s_2$ to make the equation work after the hash is computed.     * Information Leakage: The equation $s_2 = b + a s_1 \pmod{r}$ has two unknowns ($a$ and $b$). Even though an attacker sees $s_2$, they cannot solve for the private key $a$ without knowing the random value $b$. As long as $b$ is sampled uniformly at random, every possible value for $a$ is equally likely, leaking no information.     * The PlayStation Case Study: Approximately $15\,years$ ago, PlayStation's signature system for games failed because they did not generate the random integer $b$ uniformly. This bias allowed the private key to leak, enabling users to install unauthorized software.

Advanced and Future Topics in Cryptography

• Post-Quantum Cryptography (PQC):     * Quantum computers using Shor's algorithm can solve factoring and discrete log problems, breaking RSA and Elliptic Curve DSA.     * Current quantum hardware has reached approximately $300$ to $500\,qubits$.     * Recent research suggests Shor's algorithm could be run with as few as $10,000\,atomic\,qubits$.     * Google has announced goals for post-quantum transitions by $2029$.     * Lattice-based cryptography is a leading candidate for PQC that runs on current hardware but remains secure against quantum attacks.

• Fully Homomorphic Encryption (FHE):     * Allows computation directly on encrypted data without decrypting it first.     * Scenario: A user can upload an encrypted database and an encrypted SQL query to the cloud. The cloud performs the operation on the ciphertexts and returns an encrypted result. The cloud never sees the actual data or the query content.     * History: Proposed by Craig Gentry in $2009$. Initially viewed as purely theoretical and slow, $15\,years$ of research have made it practical for uses like privacy-preserving machine learning.

Questions & Discussion

• Question (Student): Regarding the variable $B$ in the Schnorr signature, does it need to be between a certain range or just random?

• Answer (Instructor): It must be between $0$ and $r - 1$ and it must be equally likely (uniformly distributed). If there is even a small bias in the distribution of $B$, the private key can be leaked over time. Transitioning back to the course context, RSA is simpler in comparison, but discrete log-based schemes (like ECDSA) are used extensively in practice.

• Closing Remarks: The instructor wished the students a happy Easter holiday and noted that presentations would follow the break.