Digital Signature and RSA

Part 1: Generic Model of Digital Signature Process

A digital signature uses asymmetric (public key) cryptography to provide authentication, integrity, and non-repudiation. The sender signs using their private key; the receiver verifies using the sender's public key.

Model

Sender side:

1. Message: Sender has the original plaintext message $M$.
2. Hashing: A hash function $H$ (e.g., SHA-1, MD5) is applied to $M$ to produce a fixed-length message digest $h = H(M)$.
3. Signing: The digest is encrypted with the sender's private key to form the digital signature $S = E_{PR_{sender}}(h)$.
4. Transmission: The message $M$ and signature $S$ are sent together.

Receiver side: 5. Recompute hash: Receiver applies the same hash function to the received message: $h_1 = H(M)$. 6. Decrypt signature: Receiver decrypts $S$ with the sender's public key to recover $h_2 = D_{PU_{sender}}(S)$. 7. Compare: If $h_1 = h_2$, the message is authentic and unaltered; otherwise it has been tampered with or is forged.

Sender:   M --H--> h --Encrypt(PR_sender)--> S ;  send (M, S)
Receiver: M --H--> h1
          S --Decrypt(PU_sender)--> h2
          compare h1 == h2 ? valid : invalid

Properties provided: Authentication, Integrity, Non-repudiation.

Part 2: RSA

Given data

• $p = 7$, $q = 19$
• Public key $e = 29$
• Private key $d = 41$
• Plaintext to encrypt: $M = 4$
• Ciphertext to decrypt: $C = 3$

Step 1: Parameters

$$n = p \times q = 7 \times 19 = 133$$ $$\phi(n) = (p-1)(q-1) = 6 \times 18 = 108$$

Check: $e \times d = 29 \times 41 = 1189$, and $1189 \mod 108 = 1189 - 11\times108 = 1189-1188 = 1$. ✓ Keys valid.

Step 2: Encrypt $M = 4$

$$C = M^e \bmod n = 4^{29} \bmod 133$$

Successive squaring mod 133:

• $4^1 = 4$
• $4^2 = 16$
• $4^4 = 16^2 = 256 \equiv 123$
• $4^8 = 123^2 = 15129 \equiv 6$ (since $15129 - 113\times133 = 15129-15029=100$... recheck)

Recheck $4^8$: $15129 \div 133 = 113.75$, $113\times133 = 15029$, remainder $= 100$. So $4^8 \equiv 100$, not 6.

Redo carefully:

• $4^4 \equiv 123$
• $4^8 = 123^2 = 15129$; $133\times113 = 15029$; $15129-15029 = 100 \Rightarrow 4^8 \equiv 100$
• $4^{16} = 100^2 = 10000$; $133\times75 = 9975$; $10000-9975 = 25 \Rightarrow 4^{16} \equiv 25$

Binary: $29 = 16+8+4+1$, so $$4^{29} = 4^{16}\cdot 4^{8}\cdot 4^{4}\cdot 4^{1} \equiv 25 \times 100 \times 123 \times 4 \pmod{133}$$

Step by step:

• $25 \times 100 = 2500;\ 2500 - 18\times133 = 2500 - 2394 = 106$
• $106 \times 123 = 13038;\ 13038 - 98\times133 = 13038 - 13034 = 4$
• $4 \times 4 = 16$

$$\boxed{C = 4^{29} \bmod 133 = 16}$$

Step 3: Decrypt $C = 3$

$$M = C^d \bmod n = 3^{41} \bmod 133$$

Successive squaring mod 133:

• $3^1 = 3$
• $3^2 = 9$
• $3^4 = 81$
• $3^8 = 81^2 = 6561;\ 6561 - 49\times133 = 6561-6517 = 44$
• $3^{16} = 44^2 = 1936;\ 1936 - 14\times133 = 1936-1862 = 74$
• $3^{32} = 74^2 = 5476;\ 5476 - 41\times133 = 5476-5453 = 23$

Binary: $41 = 32 + 8 + 1$, so $$3^{41} = 3^{32}\cdot 3^{8}\cdot 3^{1} \equiv 23 \times 44 \times 3 \pmod{133}$$

• $23 \times 44 = 1012;\ 1012 - 7\times133 = 1012 - 931 = 81$
• $81 \times 3 = 243;\ 243 - 133 = 110$

$$\boxed{M = 3^{41} \bmod 133 = 110}$$

Final Results

• Encryption of plaintext $4$: $C = 16$
• Decryption of ciphertext $3$: $M = 110$

Galois Field, Block Cipher Modes, and Quadratic Residues

Step 1 - Extract (Given Data)

• Modulus for quadratic residues: $n = 7$
• Tasks: (a) define Galois field with example, (b) explain any two block cipher modes, (c) find quadratic residues of 7.

No numeric data is missing. All parts are solvable.

Step 2 - Solve

Part 1: Galois Field

Definition: A Galois Field (Finite Field), denoted $GF(p^n)$, is a field containing a finite number of elements, satisfying all field axioms (closure, associativity, commutativity, additive and multiplicative identities, additive and multiplicative inverses for non-zero elements, and distributivity).

The order (number of elements) must be a prime power $p^n$, where $p$ is prime and $n \geq 1$.

• $GF(p)$: elements ${0, 1, \ldots, p-1}$ with arithmetic mod $p$.
• $GF(2^8)$ is used in AES.

Example: $GF(7) = {0, 1, 2, 3, 4, 5, 6}$ (arithmetic mod 7)

Addition: $5 + 4 = 9 \equiv 2 \pmod 7$

Multiplication: $3 \times 5 = 15 \equiv 1 \pmod 7$

Multiplicative inverse: since $3 \times 5 \equiv 1 \pmod 7$, we have $3^{-1} = 5$.

Every non-zero element has an inverse, so $GF(7)$ is a valid Galois field.

Part 2: Two Modes of Block Cipher Encryption

Mode 1: Electronic Codebook (ECB)

• Plaintext is split into fixed-size blocks ($P_1, P_2, \ldots$).
• Each block is encrypted independently with the same key $K$: $$C_i = E(K, P_i)$$
• Advantages: Simple, fast, fully parallelizable; random access to blocks.
• Disadvantages: Identical plaintext blocks give identical ciphertext blocks, exposing data patterns; weak for structured data.

Mode 2: Cipher Block Chaining (CBC)

• Each plaintext block is XORed with the previous ciphertext block before encryption. An Initialization Vector (IV) seeds the first block: $$C_i = E(K,; P_i \oplus C_{i-1}), \qquad C_0 = IV$$
• Decryption: $P_i = D(K, C_i) \oplus C_{i-1}$
• Advantages: Identical plaintext blocks give different ciphertext (hides patterns); more secure than ECB.
• Disadvantages: Encryption is sequential (not parallelizable); a transmission error in one block corrupts that block and the next during decryption.

Part 3: Quadratic Residues of 7

An integer $a$ is a quadratic residue mod $n$ if there exists $x$ with $x^2 \equiv a \pmod n$ and $\gcd(a,n)=1$.

Compute $x^2 \bmod 7$ for $x = 1$ to $6$:

Distinct quadratic residues: $$QR(7) = {1, 2, 4}$$

Non-residues: ${3, 5, 6}$

Check with formula: For prime $p$, number of QRs $= \dfrac{p-1}{2} = \dfrac{7-1}{2} = 3$. ✓ (matches ${1,2,4}$)

Final Answers

• $GF(7) = {0,\ldots,6}$ under mod-7 arithmetic is the example Galois field.
• ECB and CBC modes explained as above.
• Quadratic residues of 7: ${1, 2, 4}$.

PKI Trust Model

Introduction

Public Key Infrastructure (PKI) is a framework that manages the creation, distribution, storage, and revocation of digital certificates. The PKI trust model defines how trust is established and maintained among entities using public key certificates.

Key Elements of the PKI (PKIX) Model

The PKIX (Public Key Infrastructure X.509) model consists of the following elements:

1. End Entity

A generic term used to denote end users, devices, or any other entity that can be identified in the subject field of a public key certificate. End entities are the ultimate consumers of PKI services.

2. Certification Authority (CA)

• The trusted third party that issues and signs digital certificates.
• The CA binds a public key to an identity by digitally signing the certificate with its own private key.
• Trust in the PKI system ultimately rests on trust in the CA.

3. Registration Authority (RA)

• Acts as an intermediary between the end entity and the CA.
• Verifies the identity of the end entity before the CA issues a certificate.

4. Certificate Repository

• A publicly accessible store (e.g., LDAP directory) where certificates and Certificate Revocation Lists (CRLs) are published and retrieved.

5. Digital Certificates

• A certificate binds a public key to an individual or entity.
• It is signed by the CA, so any party that trusts the CA can verify the certificate.
• Benefits include:
  • Authentication: The individual's unique private key was used to apply the signature, so recipients can be confident of the signer's identity.
  • Integrity: Even the slightest change to the original document causes signature verification to fail.
  • Confidentiality: Content encrypted with a public key can only be decrypted with the corresponding private key.

How the Trust Model Works

End Entity  <---->  Registration Authority (RA)
                          |
                          v
                  Certification Authority (CA)
                          |
                    Issues Certificate
                          |
                    Certificate Repository
                          |
                    Relying Party verifies

1. An end entity requests a certificate, providing proof of identity to the RA.
2. The RA validates the request and forwards it to the CA.
3. The CA issues a signed digital certificate binding the entity's identity to its public key.
4. The certificate is stored in a repository for public access.
5. A relying party retrieves the certificate, verifies the CA's signature, and trusts the public key.

Public Key Distribution in PKI

Several techniques are used for distributing public keys:

Summary

The PKI trust model establishes a chain of trust rooted in a trusted CA. By using digital certificates, it ensures authentication, integrity, and confidentiality in public key cryptography, solving the key distribution problem in a scalable and verifiable manner.