XOR-based random number generator used to encrypt and decrypt a tree document

This is a two-part coding exercise. First, implement a pseudo-random number generator (PRNG) whose state update is built from bitwise XOR. Then use that generator to encrypt a tree-structured document, and to decrypt the result back into the original document. ### Constraints and Clarifications - Write the generator yourself from integer, shift and XOR operations; do not call a library random-number or cryptography function. - The generator is seeded with an integer key. The same seed must always produce the same sequence, because decryption has to regenerate exactly the numbers that encryption used. - The document is a tree: each node has a name, optional text content, and an ordered list of child nodes, similar to a simplified XML or JSON document. The exact node schema was not given; state the one you use. - Decrypting the encrypted output with the same key must reproduce the original tree exactly: the same structure, child order, names and text. ### Clarifying Questions - Which output width should the generator produce (for example 32-bit or 64-bit unsigned integers), and do its statistical quality and period matter here? - Should the encrypted result be an opaque blob, or must it keep the tree's shape, with each node's content encrypted in place? - Is the scheme meant to resist a real attacker, or is the exercise about using a deterministic keystream correctly? - Can node text contain arbitrary characters, including any delimiter you might want to use, and can the tree be very deep? ### Part 1 — The generator Implement a generator class that is constructed from an integer seed and returns a new pseudo-random unsigned integer of fixed width on each call, for example through a `next() -> int` method. Each output must come from updating an internal state with shifts and XOR. ```hint Fix the width If your language's integers are unbounded (Python's are), a left shift makes the number grow instead of dropping its high bits. Decide how the state stays at a fixed width. ``` ```hint Look for a stuck state Check whether some seed value makes the generator return the same number forever, and decide what the constructor does about it. ``` #### What This Part Should Cover - The state update, and how the state is kept at a fixed width - Seed handling, including any seed that would break the generator - Determinism: the same seed reproduces the same sequence - What this kind of generator is and is not good enough for ### Part 2 — Encrypt and decrypt a tree document Using your generator, write `encrypt(document, key)` and `decrypt(ciphertext, key)` so that `decrypt(encrypt(document, key), key)` returns a tree equal to the original document. ```hint Decide what you are encrypting The generator produces numbers and the document is a tree. Think about what form the document must be in before it can be combined with the generator's output, and how you get the tree back afterwards. ``` ```hint Decryption starts from the same place Think about which state the generator must be in when decryption begins, and why one XOR step can both encrypt and decrypt. ``` #### What This Part Should Cover - Turning the tree into something that can be encrypted, and back, without ambiguity, for example when text contains special characters - How the generator's output is combined with the data, and why decryption inverts it - Correctness on edge cases: empty text, non-ASCII text, a very deep or very wide tree - Time and memory cost in terms of the document's size ### What a Strong Answer Covers - Working, readable code for both parts, with a round-trip test - Fixed-width arithmetic and seeding handled deliberately rather than by accident - A serialization format that the document's own content cannot confuse - An honest statement of the security limits of a hand-made XOR-based generator - Running time linear in the size of the document ### Follow-up Questions - Two different documents are encrypted with the same key. What can someone who sees both ciphertexts learn, and how would you change the scheme to prevent it? - How would you encrypt only node names and text while keeping the tree's shape readable, and what would that reveal? - How would the receiver detect that the ciphertext was modified in transit? - How does your code behave on a tree that is 100,000 levels deep, and what would you change?