diff --git a/writeup.md b/writeup.md
index 32843a1..cb7951f 100644
--- a/writeup.md
+++ b/writeup.md
## Student Responses
-<!-- Write your solutions below. Add sections for each problem as needed. -->
-<!-- Use proper mathematical notation where applicable. -->
+---
-[Your solutions here]
+## Question 1: Short Definitions
+**(a) capability** *(2 points)*
+
+A capability is an unforgeable token held by a process that grants specific, designated access rights (such as read, write, or execute) to a particular resource or object, where possessing the token is itself proof of authorization without requiring further identity checks.
+
+**(b) cylinder group** *(2 points)*
+
+A cylinder group is a cluster of consecutive disk cylinders in a Unix file system (e.g., BSD Fast File System) that contains its own local copies of the superblock, a free-block bitmap, a free-inode bitmap, and a set of inodes, enabling data and metadata for related files to be stored near each other on disk to improve I/O locality and performance.
+
+**(c) symbolic link** *(2 points)*
+
+A symbolic link is a special file system entry that stores a pathname string pointing to another file or directory, such that when the symbolic link is accessed the file system transparently redirects the access to the target named by that stored pathname.
+
+**(d) message digest** *(2 points)*
+
+A message digest is a fixed-size cryptographic hash value computed deterministically from a message's contents using a one-way hash function (such as SHA-256), such that any change to the message produces a different digest with overwhelming probability, thereby allowing verification of message integrity.
+
+**(e) extent** *(2 points)*
+
+An extent is a contiguous run of disk blocks described compactly as a (starting block number, length) pair, used in file systems to represent a sequence of consecutive data blocks belonging to a file more efficiently than listing each individual block number separately.
+
+---
+
+## Question 2: LoadProgram and Yalnix Demand Paging
+
+### Overview of Changes
+
+To implement demand paging in the Yalnix kernel on the RCS 421 hardware, we make two principal modifications:
+
+1. **LoadProgram** is changed to *not* read any text/data pages into physical memory. Instead, it marks all of those virtual pages as invalid in the page table and records where each page's data lives in the program file.
+2. **TrapMemoryHandler** is modified to detect when a fault is a demand-paging fault (a page that exists in the program but has not yet been loaded), and to respond by loading exactly that one page into a freshly allocated physical frame and updating the page table.
+
+### New / Modified Data Structures
+
+We add the following per-process demand-paging table to the PCB. It has one entry per virtual page number (VPN) in Region 0.
+
+```c
+/* Stored in program file, or -1 for BSS (zero-fill) pages */
+struct DemandPageEntry {
+ int is_demand; /* 1 = page is not yet loaded; 0 = already loaded or not demand */
+ int fd; /* open file descriptor for the program file; -1 for BSS pages */
+ off_t file_offset; /* byte offset in the program file where this page's data begins;
+ -1 for BSS (zero-fill) pages */
+ int prot; /* protection bits (PROT_READ|PROT_EXEC for text,
+ PROT_READ|PROT_WRITE for data/BSS) */
+};
+
+/* Added to each process's PCB: */
+struct DemandPageEntry demand_table[VMEM_REGION_SIZE / PAGESIZE];
+int prog_fd; /* file descriptor for the program's executable, kept open */
+```
+
+No changes are made to the existing page table entry (PTE) format; we simply use the existing `valid` bit in each PTE to indicate whether the physical frame is present.
+
+### Modified LoadProgram: Initialization
+
+Rather than allocating physical frames and reading program pages, LoadProgram marks each page table entry as invalid and records demand-paging information for each virtual page.
+
+```
+LoadProgram(char *name, char *args[], ExceptionInfo *ei, PCB *proc):
+
+ fd = Open(name, O_RDONLY) /* open the ELF executable */
+
+ /* Read ELF header and program header table */
+ Read ELF header → text_file_offset, text_vaddr, text_bytes
+ → data_file_offset, data_vaddr, data_bytes
+ → bss_vaddr, bss_bytes
+
+ /*
+ * All addresses below are VIRTUAL addresses.
+ * All page numbers computed below are VIRTUAL page numbers (VPNs)
+ * within Region 0.
+ */
+
+ /* ---- TEXT PAGES ---- */
+ text_start_vpn = text_vaddr >> PAGESHIFT /* virtual page number */
+ text_num_pages = ROUND_UP(text_bytes, PAGESIZE) / PAGESIZE
+
+ for vpn = text_start_vpn to text_start_vpn + text_num_pages - 1:
+ page_idx = vpn - text_start_vpn
+
+ /* Mark page table entry as INVALID (not in physical memory) */
+ proc->region0_pt[vpn].valid = 0 /* page not present */
+ proc->region0_pt[vpn].pfn = 0 /* no physical page yet */
+ /* (vpn is a VIRTUAL page number; pfn will be a PHYSICAL page number
+ when the page is eventually loaded) */
+
+ /* Record demand-paging info */
+ proc->demand_table[vpn].is_demand = 1
+ proc->demand_table[vpn].fd = fd
+ proc->demand_table[vpn].file_offset = text_file_offset + page_idx * PAGESIZE
+ proc->demand_table[vpn].prot = PROT_READ | PROT_EXEC
+
+ /* ---- DATA PAGES ---- */
+ data_start_vpn = data_vaddr >> PAGESHIFT /* virtual page number */
+ data_num_pages = ROUND_UP(data_bytes, PAGESIZE) / PAGESIZE
+
+ for vpn = data_start_vpn to data_start_vpn + data_num_pages - 1:
+ page_idx = vpn - data_start_vpn
+
+ proc->region0_pt[vpn].valid = 0
+ proc->region0_pt[vpn].pfn = 0
+
+ proc->demand_table[vpn].is_demand = 1
+ proc->demand_table[vpn].fd = fd
+ proc->demand_table[vpn].file_offset = data_file_offset + page_idx * PAGESIZE
+ proc->demand_table[vpn].prot = PROT_READ | PROT_WRITE
+
+ /* ---- BSS PAGES (zero-fill on demand) ---- */
+ bss_start_vpn = bss_vaddr >> PAGESHIFT /* virtual page number */
+ bss_num_pages = ROUND_UP(bss_bytes, PAGESIZE) / PAGESIZE
+
+ for vpn = bss_start_vpn to bss_start_vpn + bss_num_pages - 1:
+ proc->region0_pt[vpn].valid = 0
+ proc->region0_pt[vpn].pfn = 0
+
+ proc->demand_table[vpn].is_demand = 1
+ proc->demand_table[vpn].fd = -1 /* no file: zero-fill */
+ proc->demand_table[vpn].file_offset = -1
+ proc->demand_table[vpn].prot = PROT_READ | PROT_WRITE
+
+ /* Save the open fd in the PCB for future demand-load use */
+ proc->prog_fd = fd
+
+ /* Flush Region 0 TLB to ensure hardware sees all the invalid PTEs */
+ WriteRegister(REG_TLB_FLUSH, TLB_FLUSH_0)
+
+ /*
+ * Stack pages (Region 1) are allocated normally — at least the
+ * initial stack page must be present to start execution.
+ */
+ pfn_stack = AllocatePhysicalPage() /* returns a PHYSICAL page number */
+ /* stack_vpn_r1 is a virtual page number within Region 1's page table */
+ stack_vpn_r1 = (VMEM_1_LIMIT - PAGESIZE - VMEM_1_BASE) >> PAGESHIFT
+ proc->region1_pt[stack_vpn_r1].valid = 1
+ proc->region1_pt[stack_vpn_r1].prot = PROT_READ | PROT_WRITE
+ proc->region1_pt[stack_vpn_r1].pfn = pfn_stack /* PHYSICAL page number */
+ WriteRegister(REG_TLB_FLUSH, VMEM_1_LIMIT - PAGESIZE) /* virtual address */
+
+ /* Set entry point and stack pointer in ExceptionInfo */
+ ei->pc = (void *)text_vaddr /* VIRTUAL address: program entry point */
+ ei->sp = (void *)(VMEM_1_LIMIT - 8) /* VIRTUAL address: initial stack pointer */
+```
+
+Because all text/data/BSS PTEs have `valid = 0`, the very first instruction fetch (from the entry point virtual address) will immediately trigger a page fault, and the handler will load that page on demand.
+
+### Modified TrapMemoryHandler: Recognizing and Handling Demand-Paging Faults
+
+```
+TrapMemoryHandler(ExceptionInfo *ei):
+
+ /*
+ * ei->addr is the VIRTUAL address whose access caused the fault.
+ */
+ faulting_vaddr = (unsigned int) ei->addr /* VIRTUAL address */
+ faulting_vpn = faulting_vaddr >> PAGESHIFT /* VIRTUAL page number in Region 0 */
+
+ proc = CurrentProcess()
+
+ /* Only handle Region 0 demand-paging faults here */
+ if faulting_vaddr >= VMEM_1_BASE:
+ /* Region 1 fault or stack growth — handle separately */
+ HandleStackGrowthOrKernelFault(ei)
+ return
+
+ if faulting_vpn >= (VMEM_REGION_SIZE / PAGESIZE):
+ /* Out of bounds — kill process */
+ KillProcess(proc)
+ return
+
+ if proc->demand_table[faulting_vpn].is_demand == 1:
+ /*
+ * DEMAND PAGING FAULT: this virtual page exists in the program
+ * but has not yet been loaded into physical memory.
+ */
+
+ /* Allocate a free physical frame */
+ pfn = AllocatePhysicalPage()
+ /*
+ * pfn is a PHYSICAL page number.
+ * The corresponding PHYSICAL address of this frame is:
+ * phys_addr = pfn << PAGESHIFT
+ * We cannot access this physical address directly from the kernel;
+ * we must map it at a kernel VIRTUAL address first.
+ */
+
+ /*
+ * Temporarily map the new physical frame at a reserved kernel
+ * virtual page in Region 1 so we can write to it.
+ * KERNEL_TEMP_PAGE_VADDR is a pre-reserved VIRTUAL address in Region 1.
+ */
+ kernel_temp_vaddr = KERNEL_TEMP_PAGE_VADDR /* VIRTUAL address */
+ kernel_temp_vpn = (kernel_temp_vaddr - VMEM_1_BASE) >> PAGESHIFT
+ /* VIRTUAL page number in Region 1 */
+
+ kernel_region1_pt[kernel_temp_vpn].valid = 1
+ kernel_region1_pt[kernel_temp_vpn].prot = PROT_READ | PROT_WRITE
+ kernel_region1_pt[kernel_temp_vpn].pfn = pfn /* PHYSICAL page number */
+ WriteRegister(REG_TLB_FLUSH, kernel_temp_vaddr) /* flush by VIRTUAL address */
+
+ if proc->demand_table[faulting_vpn].fd == -1:
+ /*
+ * BSS page: zero-fill the physical frame.
+ * We access it through the kernel VIRTUAL address kernel_temp_vaddr.
+ */
+ memset((void *)kernel_temp_vaddr, 0, PAGESIZE)
+ /* kernel_temp_vaddr is a VIRTUAL address → physical write goes to pfn frame */
+
+ else:
+ /*
+ * Text or data page: read from the program file into the physical frame.
+ */
+ file_fd = proc->demand_table[faulting_vpn].fd
+ file_offset = proc->demand_table[faulting_vpn].file_offset
+
+ lseek(file_fd, file_offset, SEEK_SET)
+ n = read(file_fd, (void *)kernel_temp_vaddr, PAGESIZE)
+ /* kernel_temp_vaddr is a VIRTUAL address; the data lands in physical frame pfn */
+
+ /* Zero any partial remainder (e.g., last page of text/data) */
+ if n < PAGESIZE:
+ memset((void *)(kernel_temp_vaddr + n), 0, PAGESIZE - n)
+
+ /* Remove the temporary kernel mapping */
+ kernel_region1_pt[kernel_temp_vpn].valid = 0
+ WriteRegister(REG_TLB_FLUSH, kernel_temp_vaddr) /* VIRTUAL address */
+
+ /*
+ * Now make the page valid in the process's Region 0 page table.
+ * faulting_vpn is a VIRTUAL page number.
+ * pfn is the PHYSICAL page number of the newly loaded frame.
+ */
+ proc->region0_pt[faulting_vpn].valid = 1
+ proc->region0_pt[faulting_vpn].pfn = pfn /* PHYSICAL page number */
+ proc->region0_pt[faulting_vpn].prot = proc->demand_table[faulting_vpn].prot
+
+ /* Mark as loaded so we don't treat future faults on this page as demand faults */
+ proc->demand_table[faulting_vpn].is_demand = 0
+
+ /* Flush TLB for the now-valid virtual page */
+ WriteRegister(REG_TLB_FLUSH, faulting_vpn << PAGESHIFT) /* VIRTUAL address */
+
+ /*
+ * Return normally. The hardware will re-execute the faulting
+ * instruction; now that the PTE is valid and pfn is set, the
+ * hardware's address translation will succeed:
+ * VIRTUAL address faulting_vaddr
+ * → page table lookup → pfn (PHYSICAL page number)
+ * → PHYSICAL address: (pfn << PAGESHIFT) | (faulting_vaddr & PAGE_MASK)
+ */
+ return
+
+ else:
+ /*
+ * This is a genuine protection violation (e.g., write to read-only
+ * text page, or access to an unmapped address). Kill the process.
+ */
+ printf("Segmentation fault: killing process %d\n", proc->pid)
+ KillProcess(proc)
+```
+
+### Summary of Address and Page Number Usage
+
+| Quantity | Kind | Where it appears |
+|---|---|---|
+| `faulting_vaddr` | **Virtual address** | `ei->addr`; used as TLB flush argument |
+| `faulting_vpn` | **Virtual page number** | Index into `region0_pt[]` and `demand_table[]` |
+| `kernel_temp_vaddr` | **Virtual address** | Pre-reserved Region 1 virtual addr for temp mapping |
+| `kernel_temp_vpn` | **Virtual page number** (Region 1) | Index into `kernel_region1_pt[]` |
+| `pfn` | **Physical page number** | Stored in PTE `.pfn`; physical frame index |
+| `pfn << PAGESHIFT` | **Physical address** | The base physical address of the allocated frame |
+| `file_offset` | Byte offset in file | Passed to `lseek`/`read`; not a memory address |
+
+---
+
+## Question 3: Page Replacement Algorithms
+
+Page reference string: **3, 5, 0, 1, 0, 2, 1, 0, 3, 2, 4, 2, 0, 5**
+Physical memory: **4 frames**, initially empty.
+
+---
+
+### 3.1 Optimal Replacement
+
+**Strategy:** On a page fault, evict the page whose next use is furthest in the future (or that will never be used again).
+
+Tracing through the reference string (positions 0–13):
+
+| Step | Ref | Fault? | Memory (set) | Action |
+|------|-----|--------|--------------|--------|
+| 0 | 3 | **FAULT** | {3} | load 3 |
+| 1 | 5 | **FAULT** | {3,5} | load 5 |
+| 2 | 0 | **FAULT** | {3,5,0} | load 0 |
+| 3 | 1 | **FAULT** | {3,5,0,1} | load 1 |
+| 4 | 0 | hit | {3,5,0,1} | — |
+| 5 | 2 | **FAULT** | {3,2,0,1} | future uses: 3→pos 8, 5→pos 13, 0→pos 7, 1→pos 6; evict **5** (furthest) |
+| 6 | 1 | hit | {3,2,0,1} | — |
+| 7 | 0 | hit | {3,2,0,1} | — |
+| 8 | 3 | hit | {3,2,0,1} | — |
+| 9 | 2 | hit | {3,2,0,1} | — |
+| 10 | 4 | **FAULT** | {4,2,0,1} | future: 3→never, 2→pos 11, 0→pos 12, 1→never; evict **3** (never used again) |
+| 11 | 2 | hit | {4,2,0,1} | — |
+| 12 | 0 | hit | {4,2,0,1} | — |
+| 13 | 5 | **FAULT** | {4,2,0,5} | no future uses for anyone; evict **1** (arbitrary among never-used pages) |
+
+**Total page faults: 7**
+
+**Pages causing each fault (in order):** VPN 3, VPN 5, VPN 0, VPN 1, VPN 2, VPN 4, VPN 5
+
+---
+
+### 3.2 FIFO Replacement
+
+**Strategy:** Evict the page that has been in physical memory the longest (i.e., the oldest resident page).
+
+Queue notation: oldest ← [ ... ] → newest
+
+| Step | Ref | Fault? | Memory queue (oldest→newest) | Action |
+|------|-----|--------|------------------------------|--------|
+| 0 | 3 | **FAULT** | [3] | load 3 |
+| 1 | 5 | **FAULT** | [3, 5] | load 5 |
+| 2 | 0 | **FAULT** | [3, 5, 0] | load 0 |
+| 3 | 1 | **FAULT** | [3, 5, 0, 1] | load 1 |
+| 4 | 0 | hit | [3, 5, 0, 1] | — |
+| 5 | 2 | **FAULT** | [5, 0, 1, 2] | evict **3** (oldest); load 2 |
+| 6 | 1 | hit | [5, 0, 1, 2] | — |
+| 7 | 0 | hit | [5, 0, 1, 2] | — |
+| 8 | 3 | **FAULT** | [0, 1, 2, 3] | evict **5** (oldest); load 3 |
+| 9 | 2 | hit | [0, 1, 2, 3] | — |
+| 10 | 4 | **FAULT** | [1, 2, 3, 4] | evict **0** (oldest); load 4 |
+| 11 | 2 | hit | [1, 2, 3, 4] | — |
+| 12 | 0 | **FAULT** | [2, 3, 4, 0] | evict **1** (oldest); load 0 |
+| 13 | 5 | **FAULT** | [3, 4, 0, 5] | evict **2** (oldest); load 5 |
+
+**Total page faults: 9**
+
+**Pages causing each fault (in order):** VPN 3, VPN 5, VPN 0, VPN 1, VPN 2, VPN 3, VPN 4, VPN 0, VPN 5
+
+---
+
+### 3.3 LRU Replacement
+
+**Strategy:** Evict the page that was least recently used (i.e., the page whose most recent reference is the oldest).
+
+I track the last-use timestamp for each page in memory.
+
+| Step | Ref | Fault? | Memory contents | LRU victim | LRU order (MRU→LRU after step) |
+|------|-----|--------|-----------------|------------|-------------------------------|
+| 0 | 3 | **FAULT** | {3} | — | [3] |
+| 1 | 5 | **FAULT** | {3,5} | — | [5, 3] |
+| 2 | 0 | **FAULT** | {3,5,0} | — | [0, 5, 3] |
+| 3 | 1 | **FAULT** | {3,5,0,1} | — | [1, 0, 5, 3] |
+| 4 | 0 | hit | {3,5,0,1} | — | [0, 1, 5, 3] |
+| 5 | 2 | **FAULT** | {5,0,1,2} | evict **3** (last used step 0) | [2, 0, 1, 5] |
+| 6 | 1 | hit | {5,0,1,2} | — | [1, 2, 0, 5] |
+| 7 | 0 | hit | {5,0,1,2} | — | [0, 1, 2, 5] |
+| 8 | 3 | **FAULT** | {0,1,2,3} | evict **5** (last used step 1) | [3, 0, 1, 2] |
+| 9 | 2 | hit | {0,1,2,3} | — | [2, 3, 0, 1] |
+| 10 | 4 | **FAULT** | {0,2,3,4} | evict **1** (last used step 6) | [4, 2, 3, 0] |
+| 11 | 2 | hit | {0,2,3,4} | — | [2, 4, 3, 0] |
+| 12 | 0 | hit | {0,2,3,4} | — | [0, 2, 4, 3] |
+| 13 | 5 | **FAULT** | {0,2,4,5} | evict **3** (last used step 8) | [5, 0, 2, 4] |
+
+**Total page faults: 8**
+
+**Pages causing each fault (in order):** VPN 3, VPN 5, VPN 0, VPN 1, VPN 2, VPN 3, VPN 4, VPN 5
+
+---
+
+## Question 4: Unix File System Extension
+
+### Constraints
+
+- **Cannot** change the on-disk directory entry format (16-bit inode number + 14-character filename).
+- **Cannot** change the on-disk inode format.
+- Must be **space-efficient**: no second inode reserved for files that do not use the alternate data stream.
+
+### Design: Alternate Data Directory (ADD)
+
+**Key idea:** Introduce a single special, hidden directory — the *Alternate Data Directory* (ADD) — stored in the file system using exactly the existing on-disk formats. The ADD is a regular directory (using the unchanged directory entry format) whose entries map a file's primary inode number to a second "shadow" inode that holds the alternate data. Only files that actually have an alternate data stream have entries in the ADD.
+
+#### On-Disk Format Changes
+
+1. **Superblock extension:** Reserve one field in the superblock (or use a well-known, constant inode number, e.g., inode 3) to record the inode number of the ADD itself. Call this `alt_dir_ino`. This single constant is the only addition to the superblock.
+
+2. **Alternate Data Directory (ADD):** This is an ordinary directory stored on disk using the unchanged directory-entry format:
+ - Each entry: `{ uint16_t inode_num; char name[14]; }`
+ - The `name` field stores the decimal ASCII string representation of the primary file's inode number (e.g., for inode 42, the name is `"42\0..."`). A 16-bit inode number is at most 65535, which fits easily in 14 characters.
+ - The `inode_num` field stores the inode number of the **shadow inode** that holds the alternate data blocks for that file.
+
+3. **Shadow inode:** A shadow inode is an ordinary inode (same unchanged format) allocated from the file system's free inode pool. It stores direct, single indirect, double indirect, and triple indirect block pointers exactly as a regular file inode does — except it represents the alternate data stream of the associated primary file rather than an independently named file. The shadow inode does **not** appear in any ordinary directory.
+
+#### How the Alternate Data Stream is Located
+
+To access the alternate data for a file whose primary inode number is N:
+
+1. Look up inode number `alt_dir_ino` (from the superblock) to find the ADD.
+2. Search the ADD for a directory entry whose `name` field equals the decimal string of N.
+3. If found, retrieve the `inode_num` field of that entry; this is the shadow inode number M.
+4. Read inode M and use its block pointers (direct, single indirect, double indirect, triple indirect) to access the alternate data blocks, exactly as with any regular file inode.
+
+#### Space Efficiency
+
+- Files with **no** alternate data stream have **no** entry in the ADD and **no** shadow inode allocated. The only constant overhead is the `alt_dir_ino` field in the superblock.
+- Files **with** an alternate data stream consume exactly one ADD directory entry and one shadow inode (plus data blocks as needed) — no more.
+
+#### Supporting Independent Size and Independent Data Blocks
+
+- The shadow inode has its own `file_size` field (existing inode format), so the alternate data stream has an independent size.
+- The shadow inode's block pointers point to entirely separate data blocks from those pointed to by the primary inode. No data blocks are shared.
+- Writing/reading through the shadow inode path only affects the shadow inode's blocks; the primary inode and its blocks are completely unaffected, satisfying the independence requirement.
+
+#### Creating and Deleting Alternate Data Streams
+
+- **Creating:** Allocate a new inode M, add a directory entry `(M, decimal_string(N))` to the ADD, and update the ADD directory inode's size/block pointers as needed.
+- **Deleting:** When a file with inode N that has an alternate stream is unlinked (link count drops to 0), look up and remove the ADD entry for N, free all data blocks pointed to by shadow inode M, and free inode M itself.
+
+#### Retaining the Spirit of the Formats
+
+- The ADD is a genuine directory: its entries record meaningful associations (shadow inode ↔ primary inode name string).
+- Shadow inodes are genuine inodes representing a body of file data.
+- The existing inode and directory entry formats are used exactly as intended; only the interpretation of which files certain inodes and directory entries describe is extended.
+
+---
+
+## Question 5: Cryptographic Message Protection
+
+### Goal
+
+Ensure that a receiving process can verify:
+1. **Authenticity:** The message was sent by the person who claims to have sent it.
+2. **Integrity:** The message contents have not been modified since it was sent.
+
+### Cryptographic Primitives Used
+
+- **Asymmetric key pair per user:** each user U has a private signing key `SK_U` (kept secret) and a corresponding public verification key `PK_U` (publicly known).
+- **Cryptographic hash function `H`** (e.g., SHA-256): produces a fixed-size digest of any message.
+- **Digital signature scheme `Sign`/`Verify`** (e.g., ECDSA or RSA-PSS):
+ - `σ = Sign(SK_U, d)` — produces signature σ over digest d using private key SK_U.
+ - `Verify(PK_U, σ, d)` → true/false — checks that σ was produced by Sign(SK_U, d).
+- **Public Key Infrastructure (PKI) / key directory:** a trusted store (e.g., a certificate authority or trusted key server) from which any process can look up `PK_V` for any user V.
+
+### Initial State of Each Process
+
+Each user process is initialized with:
+- The **private signing key** `SK_self` of the person running it (obtained at login from a secure credential store on the local machine).
+- The **identity string** `self_id` of that person (e.g., a username or certificate).
+- Access to the **PKI** for public-key lookup (e.g., a trusted HTTPS endpoint or locally cached certificate bundle).
+
+This is a small, bounded amount of initial state regardless of how many users exist in the system.
+
+### Sending a Message
+
+```
+send_message(plaintext_body M, destination_process D):
+
+ /*
+ * Step 1: Compute a cryptographic digest of the message body.
+ * This digest uniquely represents the content of M.
+ */
+ digest = H(M) // fixed-size hash, e.g., 32 bytes for SHA-256
+
+ /*
+ * Step 2: Sign the digest with the sender's private key.
+ * Only someone who possesses SK_self can produce a valid signature
+ * that verifies under PK_self.
+ */
+ σ = Sign(SK_self, digest) // digital signature over digest
+
+ /*
+ * Step 3: Construct the complete transmitted message.
+ * Append sender identity and signature to the plaintext body.
+ */
+ transmitted_msg = { sender_id : self_id,
+ body : M,
+ signature : σ }
+
+ /*
+ * Step 4: Ask the kernel to deliver the message to the destination.
+ */
+ kernel_send(transmitted_msg, D)
+```
+
+### Receiving and Verifying a Message
+
+```
+receive_and_verify() → (verified_body, verified_sender_id):
+
+ /*
+ * Step 1: Receive the raw message from the kernel.
+ */
+ msg = kernel_receive()
+
+ claimed_sender = msg.sender_id // identity string claimed by sender
+ M = msg.body // received message body
+ σ = msg.signature // sender's digital signature
+
+ /*
+ * Step 2: Look up the claimed sender's public key from the PKI.
+ * If the claimed sender is unknown or has no public key, reject.
+ */
+ PK_sender = PKI_lookup(claimed_sender)
+ if PK_sender == NOT_FOUND:
+ reject_message("Unknown sender")
+ return
+
+ /*
+ * Step 3: Recompute the digest of the received message body.
+ */
+ digest_received = H(M)
+
+ /*
+ * Step 4: Verify the signature.
+ * Verify checks that σ = Sign(SK_sender, H(M_original)).
+ * If M was modified in transit, digest_received ≠ digest_original,
+ * so Verify returns false → Property 2 (integrity) caught.
+ * If an attacker forged σ without SK_sender,
+ * Verify returns false → Property 1 (authenticity) caught.
+ */
+ if Verify(PK_sender, σ, digest_received):
+ /*
+ * Both properties satisfied:
+ * 1. AUTHENTICITY: only the person holding SK_sender could
+ * have produced σ; if claimed_sender is who they say they
+ * are, the message is genuine.
+ * 2. INTEGRITY: the digest we recomputed from M matches what
+ * the sender signed; M has not been altered in transit.
+ */
+ accept message M as authentically from claimed_sender
+ return (M, claimed_sender)
+
+ else:
+ reject_message("Invalid signature: message forged or tampered")
+ return
+```
+
+### Why This Is Correct
+
+- **Authenticity:** A malicious user cannot forge a signature σ that passes `Verify(PK_Alice, σ, d)` without possessing Alice's private key `SK_Alice`. The sender_id field in the message can only be trusted when the corresponding signature verifies.
+- **Integrity:** `H` is a collision-resistant hash. If any bit of `M` changes in transit, `H(M_modified) ≠ H(M_original)` with overwhelming probability, so `Verify` returns false.
+- **Injection resistance:** A newly injected message from a malicious user M_evil will fail verification unless the attacker also possesses the private key of the claimed sender.
+
+### Computational Efficiency Optimization
+
+For a sending process that sends **many messages to the same destination**, we avoid the cost of a full asymmetric signature on every message by establishing a **symmetric session key** once, then using a fast HMAC for subsequent messages.
+
+```
+/* --- Session establishment (one-time per sender-recipient pair) --- */
+
+establish_session(destination_process D, recipient_identity R):
+
+ /*
+ * Generate a random symmetric session key (e.g., 256-bit AES key).
+ */
+ K_session = SecureRandom(256)
+
+ /*
+ * Encrypt K_session with the recipient's public key so only
+ * the recipient can read it.
+ */
+ K_enc = AsymmetricEncrypt(PK_R, K_session)
+
+ /*
+ * Sign the key establishment payload to authenticate it.
+ */
+ σ_init = Sign(SK_self, H(K_enc || self_id || R))
+
+ init_msg = { type : SESSION_INIT,
+ sender_id : self_id,
+ K_enc : K_enc,
+ signature : σ_init }
+ kernel_send(init_msg, D)
+
+ session_key_store[D] = K_session // store for future use
+
+/* --- Fast subsequent message sending --- */
+
+fast_send(M, destination_process D):
+
+ K = session_key_store[D]
+
+ /*
+ * HMAC is symmetric and orders of magnitude faster than asymmetric signing.
+ * Include self_id in the MAC input to bind sender identity.
+ */
+ mac = HMAC(K, self_id || M)
+
+ msg = { type : DATA,
+ sender_id : self_id,
+ body : M,
+ mac : mac }
+ kernel_send(msg, D)
+
+/* --- Fast receive and verify for session messages --- */
+
+fast_receive_and_verify(session_key K, claimed_sender S):
+
+ msg = kernel_receive()
+
+ if msg.type == SESSION_INIT:
+ K_session = AsymmetricDecrypt(SK_self, msg.K_enc)
+ σ = msg.signature
+ PK_sender = PKI_lookup(msg.sender_id)
+ if Verify(PK_sender, σ, H(msg.K_enc || msg.sender_id || self_id)):
+ session_key_store[msg.sender_id] = K_session
+ else:
+ reject_message("Bad session init")
+
+ else: /* DATA */
+ K = session_key_store[msg.sender_id]
+ mac_expected = HMAC(K, msg.sender_id || msg.body)
+ if mac_expected == msg.mac:
+ accept message msg.body from msg.sender_id
+ else:
+ reject_message("MAC verification failed")
+```
+
+The session key approach reduces per-message cryptographic cost to a single HMAC (a few microseconds) after the one-time asymmetric session establishment, while still providing both authenticity and integrity for every message.
BSCS Bench