Preface: I recently coded a tiny Rust library, implementing a cryptographic idea which had caught my interest. This post is my way of cementing my understanding of concepts which I found difficult. I’m not a cryptographer and make zero guarantees regarding the correctness of the code or math in this post. One final note, no Ai was used in writing the story in this post, I wrote it myself, so you can expect it to suck lol.

Code: The complete source code is available on my GitHub.

To send a message into the future

⠀⠀⠀⠀⠀ Dr. Angela Rae is head of Space Folding Research at The Periphery, a Top Secret remote Federation research facility located on the surface of a small moon at the outer fringe of the Kalix system. She and her 20-something-sized team of researchers are working as fast as they possibly can. A single thought is racing through everyone’s mind - “How did they find us?”.
⠀⠀⠀⠀⠀ Up there, orbiting at a chill 26,000 miles, is death. Having covertly decelerated in the radar shadow of a nearby moon, the Rebel ship suddenly emerged less than an hour ago, catching every living soul on this outer-rim secret research facility by surprise, spreading fear among its few inhabitants. Wasting no time, the rebels just communicated their terms: astand down all defences, halt all interstellar communication, and prepare to be boarded.
⠀⠀⠀⠀⠀ With the hostile rebellion force in orbit, and a likely extermination of all Federation members of this facility, Dr. Rae and her team are frantically gathering all the key discoveries of advanced Space Folding technology that she and the team have made over the last decade. Realizing the danger of having ground-breaking space-faring technology end up in enemy hands, Angela Rae has decided to initiate Facility End Of Life Protocol 2B: “Time-Lock Puzzle”. The protocol instructs Angela to encrypt all research findings into a time capsule located in the underground vault below the facility.
⠀⠀⠀⠀⠀ How did they find us? The thought is stabbing at the back of Angela’s mind, while she’s frantically navigating authorization steps of top secret subprocesses. This moon isn’t even registered in the Federation Naval Charts - it doesn’t exist. Do we have a spy on our team?
Allowing the terrifying thought to linger in her mind, Angela faces the group of researchers gathered around her.
⠀⠀⠀⠀⠀ “Everyone, listen up! There is zero chance that Federation forces will reach us in time - we’re on our own. None of us expected this, and I have as many questions as you. I have been instructed to create a Timed-Release Cryptographic Capsule. We need to hurry and prime its payload with all essential blueprints, the Ingegard algorithm, and confirming test data. If we don’t get the capsule ready and locked within the next hour then everything we’ve worked for will fall into the wrong hands. That could mean the end of the Federation as we know it. I understand this isn’t the way any of us expected things to end. I want to extend my sincere gratitude to each and every one of you.”
Angela hesitates for a moment, but then decides to follow dictum and with a straight face exclaims
⠀⠀⠀⠀⠀"The Federation thanks you for your sacrifice.".
⠀⠀⠀⠀⠀ The research compute room falls silent, its heavenly-white focus-friendly interior decoration creating a mockery of the grim situation the team is facing. The faint sound of busy compute-hardware carelessly whirring in the background sends chills through Angela’s spine. Her last statement clearly drove home the message, no one in this room will be alive in a couple of hours. ⠀⠀⠀⠀⠀ The team’s predicament, is the delicate challenge of keeping top secret research out of Rebel hands, until Federation forces return on their scheduled re-supply mission. On the flip side, locking the research away for an indefinite time would place it too far out of Federation scientist’s reach, in a war that the Federation is currently losing.
⠀⠀⠀⠀⠀ What’s needed, is to lock away the secrets for just enough time until Federation forces return and retake control of the facility.
What’s needed, is to send a message into the future.

Interlude: What follows are three short essays on time, locks, and puzzles. These essays are philosophical, rather than technical, in nature. Feel free to skip them, if the material is boring.

Work in Progress: Just a gentle reminder that the three essays below, are a work in progress. I’m hoping to finalize them in the comming days. I appologize in advance if they are hard to read in their current state.

⏱️ $\pmb{On\;time}$

This post is about the complexity of sending information into the future. Let’s put our Pretentious Philosopher hats on, and think about time for a moment. We’re especially interested in what the word future, in the context of a modern day Turing Complete Computing Machines with a Central Processing Unit.

The Sun, The Moon, and The Stars
Since the dawn of man, and for a very long time, the sun and the motion of celestial bodies, were the authoritative sources of time. The position of these have provided carbon based organisms on Earth with a shared authoritative source of time.
⠀⠀⠀⠀⠀For millions of years, this was the only way to - but around 1500 years before Christ, the sundial was invented. Until then, estimating the time of day had been highly subjective. With this breakthrough technology, man took the first steps towards a shared and objective estimate of time.

Mechanical Clocks
The 13th century saw the innovation of what would become an immensley important technology - mechanical clocks. These would come to replace the existing technology, the sundial, a widespread technology which enabled a shared measure of time. The Sun represented a reliable authoritative source of establishing morning, noon, and evening, but clouds could complicate the reading of a sundial for more precise time readings.

The Bell Tower
As Europe dragged it’s way out of the Dark Age, one institution successfuly established itself as the authority of time - Christianity, and its many bell tower churches. Bell towers were used to broadcast an ‘authoritative read’ of time throughout the day. And so, by the end of the 14th century, a shared standard version of time, slowly started spreading through Europe.

Time and Work
With the advent of supperior time tracking technology, europeans could measure and coordinate temoral events with high precision. The 13th century also introduced another time technoogy, the sandglass - a technology tracking the passing of time rather than the time of day.
⠀⠀⠀⠀⠀With these two technologies combined, it became possible to measure time with mucher higher integrity, how long someone had worked,and thereby how much they should be paid. The time-rate contract could now be subdivided further, from a full day’s of work, and a half a day’s of work into an hour of work.
⠀⠀⠀⠀⠀Time-based coordination also improved, making it easier to decide when a meeting should take place, and how long it should last (it obviously lasted far longer than appreciated by the attendees).

The Atomic Clock
The modern day version of the 14th century Bell Tower, continuously broadcasting the standard version of time, as a authoritative time-sync service, are a few atomic clocks located deep down in cosmic ray protective underground caves. These clocks provide a hyperfine and ultra reliable tracking of the dilation of time.
⠀⠀⠀⠀⠀One such atomic clock is the one in Boulder, Colorado, United States. It measures the radation measurements of ceasium atoms. TODO: citation. The time of these atomic clocks are then broadcast globally, via the Internet. Computers and phones all over the planet, use Network Time Protocol (NTP) to periodically synchronize their clock with these atomic clocks. time.google.com is an example of an NTP online server which other computers can synch against.
⠀⠀⠀⠀⠀However, as with any broadcast, there are latency issues to consider when trying to synchronize or coordinate actions and events on a very precice level. At some level of time-granularity, network latency issues and physical distance from the NTP server should start causing considerable uncertainty challenges of tracking the standard version of time.

The Computer Clock
The clock on a computer is a piece of software that, not supringsingly, keeps track of time. The Internet has made it so that computers increasingly get the correct time from the Internet. Admitably, most personal computers today are connected to the Internet, but let’s ignore that for a while, and focus on time for the individual isolated computing machine.
⠀⠀⠀⠀⠀Anyone who has administrative rights to a computer can change its date and clock , both forward (from January 1st to January 2) and backwards (from January 1st, 2000, to December 31, 1999). Making the same change to the international date and time that’s used by 8_000_000_000 people, would require a superhuman effort since we’d be trying to change the massively distributed consensus about the state of something.
⠀⠀⠀⠀⠀ The fact that an individual (non-distributed) computer has no way of knowing if the time and date is true, makes it challenging for software to target the future.

The Second
The standards organisation, Système International d’Unités (SI), defines the second as the standard measure of time. But what exactly is a second? According to SI, a second is defined (hold on to your philosopher hat)

Did you get that? I kinda didn’t! 😂

This is probably something that an Ai can ELI5 to us, but I didn’t want to use any Ai in writing this post. Let’s just leave it at “A second has something to do with state changes in a heavy atom.” 🤷‍♂️

The Future

If we’re trying to send a message into the future, then we need to spend some time thinking about what the future means for our use case.
Some questions which need to be answered are:

1. Precision - Is the future a fixed date and time, or an approximation?
2. Oracle - Who or what shall be the arbitrer of when that future has arrived?
3. Attacks - What are security issues related to 1. and 2. ?

Before we delve into these three questions, let’s first spend a moment thinking about locks.

🔒 $\pmb{On\;locks}$

List of topics to cover (briefly):
[ ] Ancient locks and keys
[ ] Challenges with online locks
[ ] Diffie-Hellman core idea
[ ] Security through fact that factorising is harder than multiplication
[ ] RSA, AES, and why I chose to use the GCM mode of AES
[ ] Randomness
[ ] Bitlength
[ ] Carmicheal Numbers and the need for primality testing of huge numbers
[ ] Example of fake primes i.e. 561, that loook prime bu aren’t
[x] Probabilitic Primality Testing with Rabin-Miller
[x] Deterministic Primality Testing with AKS, and why I implmented both
[ ] The security issues of throwing away, and not throwing away the (two) primary keys that were used during lock creation.
[ ] A very important quality of a lock - provide checks that the lock can in fact be opened (we could theoretically create a lock with no key) So, Proof of Existence of key.

Probabilistic Primality Testing

Suppose that we want to create a 100-digit prime number.
The Prime Number Theorem states that the density of primes near a large number is approximately $1/\mathbb{ln}\,x$. In other words, the probability of a 100-digit number is prime is: $$\frac{1}{\mathbb{ln}(10^{100})} \approx \frac{1}{230}$$

Knowing there are no even primes above 2, we can limit our search to only odd numbers. That improves $\approx \frac{1}{230}$ into $\approx \frac{1}{115}$, essentially doubling our chances of finding a prime number.
⠀⠀⠀⠀⠀ Expecting to find a lot more composite numbers (numbers that are not prime), it would be helpful if we could quickly determine if a number is composite or not.
The famous Fermat’s Theorem comes to our rescue.
⠀⠀⠀⠀⠀ Theorem: (Fermat’s Primality Test) Let $n>1$ be an odd integer. Choose an integer $b$ with $1<b<n$, often we simply choose $b=2$. If $b^{n-1} \not\equiv 1 \, (\mathbb{mod} \; n)$ then $n$ is composite.

The theorem can be stated the opposite way: if there exists solutions to $x^2 \equiv 1 (\mathbb{mod} \; n)$ other than $\pm 1$, then $n$ is not a prime number.

Deterministic Primality Testing
In 2002, _Agrawal, Kayal, and Saxena, published a paper where they outlined the “AKS primality test” which is deterministic in the sense that we get a discreet (Yes/No), rather than probabilitic answer to the question “Is this number prime?”. However, AKS has a pretty high time-comlexity and runs in $O(log_2(n)^{12})$. If we want to find out if a 100-digit number is prime, well, that’s a whopping . . . $$O(log_2(100)^{12})$$.

🧩 $\pmb{On\;puzzles}$

List of topics to cover (briefly):
[ ] Moore’s Law
[ ] puzzle needs to be sequential to reduce hardware attack
[ ] how can we verify that our solution is parallelization-resistant?
[ ] squaring power varies because of how OS scheduler works
[ ] Montgomery Multiplication
[ ] GMP
[ ] How to guesstimate a solver’s squaring power using Moore’s Law
[ ] Mention Post-Quantumn Cryptography alternatives

The One-Way Trapdoor The security of most modern encryption scheme rely on the fact that it’s much harder to factorize a number $n$, into number $p$ and $q$, than to produce $n$ by multiplying $p$ and $q$. For example, can we aggree that it’s harder to factorize 143, than to calculate 13 * 11? So, there’s an asymmetric relationship, in terms of work, between factorising and multiplying numbers. This insight by Witt Diffie, paved the way to what would eventually become, the RSA encryption/decryption protocol. The bedrock och modern day cryptography.
⠀⠀⠀⠀⠀In a paper published in 1996, cryptologists Rivest, Shamir, and Wagner suggested the following solution: encrypt a message to such degree that it is unlikely to be decrypted until a pre-determined amount of time has passed.
Decrypting the message boils down to solving a cryptographic puzzle: namely, the classic RSA (Rivest-Shamir-Adelmann); security by requiring factorization of a large prime.

Clarification: It’s important to note that with future we really mean after a computer has continuously worked on the puzzle for an approximate amount of time. So “two years in the future” means “a computer working on trying to decrypt the message for 24 hours each day, over a period of approximately two years.”.

Insight: A human pregnancy (normally) takes 9 months. The process cannot be parallelized by two women having a baby in 4.5 months.

Parallelization-Resistant Puzzles

We want to reduce the computational hardware advantage that an attacker might exploit by mounting a massively parallelized attack to break our encryption.
We do this by using a process that is hard to parallelize.
⠀⠀⠀⠀⠀ A Time-Lock Puzzle is a computational challenge which requires a precise amount of computational work in order to solve the puzzle. The solution to the puzzle is a number $b$ which was generated by the repeated squaring (mod n) of a seed number $a$. The output of each squaring operation becomes the input of the next squaring operation.
⠀⠀⠀⠀⠀ If we know the average number of squaring operations that a particular machine can perform per second, then we can calculate how much time it would take that machine to square $a$ all the way up to $b$.

The Time-Lock Puzzle Algorithm

We are now throughly prepared to delve into the prorocess of creating a Time-Lock Puzzle.
Let’s have look at the seven steps that need to be performed.

▲ The seven steps of creating a Time-Lock Puzzle.

We are now ready to implement these steps.

🦀 Implementation

Step 0: Preparing the Payload

$M$: Message to Protect
Dr. Angela Rae, and her team of fellow researchers, have quickly collected all essential research data related to their groundbreaking Space Folding innovation. Blueprints of machines, the Ingegard algorithm, and confirming test data. An assistant checks the total bitsize of the data;
⠀⠀⠀⠀⠀ “We’ve wiped all non-essential data from the mainframe, we’re down to just three data files containing project essential information, for a total of 886 kb of message data.”
⠀⠀⠀⠀⠀Angela raises an eyebrow.
⠀⠀⠀⠀⠀"That’s all? A decade’s worth of research in less than a megabyte?".
⠀⠀⠀⠀⠀The assistant looks around nervously, then returns to face the penetrating gaze of a woman who’s infamous for ferreting out mistakes. He shrugs, then starts with a panicky voice. . .
⠀⠀⠀⠀⠀"I mean, it’s all the data that Federation scientists will need to recreate the space folding machine without our help, considering we’ll all be —"
⠀⠀⠀⠀⠀"FINE!", Angela cuts him off.
⠀⠀⠀⠀⠀"Excellent. Let’s move on. We need to calculate the duration of the Time-Lock. Remember, we want to aim for a date that is close to the expected return and facility-take-over by Federation forces. Go!"

$T$: Duration of Protection
One of Dr. Rae’s assistants, Embla Garpe - an introvert dark-haired mathematician, has attracted the attention of everyone in the facility command room.
⠀⠀⠀⠀⠀To Angela and her crew’s utter amazement, and against every facility protocol in the entire Federation, Embla . . . is smoking . . . a nicotine cigarette. For a brief moment, everyone just stares at the young woman - white smoke slowly shrouding her in ethereal mysticism. Equally amazing is the fact that Embla doesn’t seem to be aware of it. The slender woman is focused on the delicate task of calculating time-lock duration estimations, browsing through Federation re-supply frequency logs, and looking up solar system outlier event probabilities.
⠀⠀⠀⠀⠀If it wasn’t for the fact, that death is pretty much knocking on the facility bulk door, Angela would curse out the young assistant, instruct security to throw her in the brig, and have her shipped out on the next rotation. Instead, she smiles, and calmly asks Embla . . .
⠀⠀⠀⠀⠀"Do you have an ETA of the next Federation ship?".
⠀⠀⠀⠀⠀Without turning in her chair, Embla takes a deep drag on the cigarette, which is quickly reaching its own end of life. The moment seems frozen in time, a slow irreversible stream of entropy particles drifting through the room.
⠀⠀⠀⠀⠀"I do.".
⠀⠀⠀⠀⠀By now, the team’s focus has completely switched from Embla to the cigarette in her hand, which is close to burning her fingers. As if on queue, she puts out the cigarette (to Angela’s horror On the fucking terminal desk!), and with complete disregard for Facility Code of Conduct, flicks away the bud into the far corner. Embla leans back in her chair, starring into a distant future she’ll never get to experience, and then says. . .
⠀⠀⠀⠀⠀ “Based on the Poisson distribution and Principal Component Analysis of all available time-frequency logs, the limit of the log-linear converges with a high confidence and acceptable error margin on the value, 8.02999”. She finally turns to face Angela and the rest of the team . . .
“In other words, a Federation ship will arrive . . . in 8 days.”

$S$ : Squaring Power of the Attacker
An entity that tries to solve the puzzle contained inside the Capsule, is denoted an attacker. Solving the puzzle requires the solver to perform a specific number of squarings modulo n, until the cipherkey $C_K$ is found. The attacker in this case is the compute hardware of the Rebellion ship, currently in orbit above Angela Rae’s research facility.
⠀⠀⠀⠀⠀ “Long-range optics confirm it. That’s a Class IV Blüm Blüm Shub - an old rebel scout ship.” someone shouts from behind a computer screen. “We’ll simply have to pray that it hasn’t been refitted with a Quantumn Shor Solver”. Test engineer Tania Teigen pops up, she looks at them with a cynical smile. “Because if they have one onboard, then our cute little puzzle won’t last 1 quecto second.”.
⠀⠀⠀⠀⠀ Having identified the ship’s type, the team quickly cross-reference the research facility’s military Knowledge Base, “. . . the Rebel ship-computer should have a computing power of around
3 million squarings per second. . . and that’s assuming the rebels manage to allocate 90% of the ship’s compute power to the decryption of the Time-Lock Puzzle. It’s going to get cold as hell in that ugly ass ship!”, jokes Yuyeh - Angela’s longtime research assistant.
⠀⠀⠀⠀⠀ “I know I’m not the genius around here, but—”.
⠀⠀⠀⠀⠀ It’s Jenz, a member of the Periphery’s Residential Support Team.
⠀⠀⠀⠀⠀ “How do we know the Rebels won’t simply steal the capsule, load it onboard their ship, and make a run for it? What am I missing here?”
⠀⠀⠀⠀⠀ Angela Rae looks up from the delicate calculations in front of her. She smiles. In a few hours she, and everyone else on this remote research facility, will likely be dead or captives on a Rebel ship. The chances of anyone ever seeing their family or loved ones are basically zero. And despite this grim state of affairs, her team is actively trying to solve the problem.
⠀⠀⠀⠀⠀ “No, it’s a fair question, Jenz.” Angela starts with a weary, but forgiving tone.
⠀⠀⠀⠀⠀ “As most of you know, the research we’ve done here is considered by the Federation to be a top priority. In the creation of this site, no cost was considered too high, no resources were spared. The Capsule, located 3 kilometers below this room, is protected by a state of the art military force field. There’s no technology, that we know of, capable of displacing the Capsule even one milimeter from its locus. Not even a nuclear strike. The Rebels can interact with it, but it can’t be physically moved. You can think of it, as a pretty good safe.”.
⠀⠀⠀⠀⠀ Angela returns to the work at hand, fighting back tears.
⠀⠀⠀⠀⠀ “Listen up, everyone. . . .please! These estimates will have to do - we’re simply out of time. Rebel fighters will land on this site in less than an hour. We must proceed to the next phase, and start priming the Capsule payload.”

Read More: I wrote about squaring mod p in this post.

The Capsule Payload
Dr. Angela Rae and her team have gathered all the information necessary to initiate the creation of a Time-Lock Puzzle. The puzzle will be stored inside the Capsule, which is located in the underground vault. Angela takes one last look at the details:

• $M$ (Message in the form of blueprints and test data): 886 kb of message data
• $T$ (Time-Lock duration): 8 days = 60 seconds * 60 minutes * 24 hours = 691_200 seconds
• $S$ (Squaring power of the Rebel Attackers): 3_000_000 squarings per second

A loud “PING!” startles Angela, and everyone else in the command center. A proximity warning informs them that Kalman-tracking-procedures have detected an inbound non-Federation-registered vessel - a highly unlawful and equally unusual occurrence.
⠀⠀⠀⠀⠀ “Oh, God! The Rebels are almost here. Quick, someone fetch me a Vanguard suit and help me put it on. I have to get down to the Capsule in the vault, and start the Time-Lock procedure.”.
⠀⠀⠀⠀⠀ Angela looks at her team, wondering if they still respect her authority.
⠀⠀⠀⠀⠀ “On my way.”, Yuyeh shouts as he scrambles through the room to go and get a Vanguard hazardous environment suit, capable of withstanding the -90°C temperature inside the vault.

Step 1: Compute the Composite Modulus

⠀⠀⠀⠀⠀ It’s been six minutes, Dr. Angela Rae is riding the elevator down to the vault, which houses the Capsule. Breathing in the Vanguard suite bothers her, but given the circumstances she doesn’t care.
Communication with the topside command center was suddenly cut off when she passed 2.7 km below ground level. She doesn’t know if it was due to Rebels finally cutting through blast doors and killing everyone, or if the Kalix moon’s radiation levels modulate the communication frequencies into static noise. Regardless, no one topside has responded to her last couple of half-hearted “Hello? Do you hear up there? YuYeh, come in! SitRep, please!”.
No answer.
⠀⠀⠀⠀⠀ The elevator decelarates to a complete standstill. A voice-assisted control panel on Angela’s right demands that she accepts a full biometric authorization scan. She complies. “Scanning. . . . Welcome Dr. Rae.” The female voice is provokingly calm, and as the elevator door opens, Angela can’t help but curse the syntetic voice from the inside her suit.
“Bitch, I’m about to die, okay? Nevermind, don’t answer that.” She reminds herself that she’s there to do a job. At this very moment, members of her team might be tortured by Rebels, hoping to gain access to the capsule. She needs to hurry.
⠀⠀⠀⠀⠀ The Vault is actually much smaller than she imagined. She’s been briefed about it, but that was over ten years ago. But there is one thing that align well with the fragments of memories that she has…some fifty meters straight ahead of her is a massive construct and in the middle of it floats a dark orb-like construct - The Capsule.
⠀⠀⠀⠀⠀ As she approaches the Capsule it seems to react to her presence. There’s a humming sound, some kind of vibration in the air - The force field?. The Capsule is beautiful, and ugly, at the same time. A mix of organic and synthetic technology.
⠀⠀⠀⠀⠀ Suddenly a request for a direct neural link is made . . . from the Capsule it seems.
She recognizes the procedure from the training she received as a young cadet at the Federation Military Research Academy.
⠀⠀⠀⠀⠀She authorizes herself. A tremendous feeling of power flows through Angela, as she gains direct control of the Capsule.

Generating Large Prime Numbers:
Following protocol, Angela instructs the Capsule to generate two large random prime numbers $p$, and $q$. She then accepts the Capsule’s suggestion to produce their composite modulus $n$.

$$n=p \cdot q$$

The implementation of this step is pretty straightforward,

pub struct Capsule {
    p: BigUint,
    q: BigUint,
    a: BigUint,
    tlp: Option<TimeLockPuzzle>,
}

impl Capsule {
    pub fn new(&self, bits: u64) -> Self {
        Capsule {
            p: Capsule::generate_large_random_prime(bits),
            q: Capsule::generate_large_random_prime(bits),
            a: BigUint::from(2u32),
            tlp: None,
        }
    }

    fn compute_composite(&self, p: &BigUint, q: &BigUint) -> BigUint {
        p * q
    }
}

Step 2: The Euler Phi Function

To understand the next step, let’s first look at a concept from Number Theory, that of a divisor.
The negative and positive whole numbers are collectively denoted as: $$\mathbb{Z} = \{ …, -3, -2, -1, 0, 1, 2, 3, … \}$$

In elementary school we learned that $4$ divides $12$, because $4 \cdot 3=12$ (if we have $3$ multiples of $4$ the sum is $12$). The same goes for $-4$ dividing $12$, because $-4 \cdot -3=12$. So, $4$ is a divisor of $12$.

Definition: Divisor
Let $p,q\in \mathbb{Z}$. If there exist an $m \in \mathbb{Z}$, such that $p \cdot m = q$, then we say that $p$ is a divisor of $q$, or that $q$ is a multiple of $p$.

The positive divisors of 8 are 1,2, and 4. The positive divisors of 15 are 1,3, and 5. Neither 8, nor 15 is a prime number (remember that a prime number is only divisible by itself and 1).
Further, they only share one single divisor which is 1. Let’s define that relation:

Definition: Relative Prime
Two numbers $p,q\in Z$ are relatively prime if their greates common divisor is 1.

We can shorten greatest common divisor into $gcd$, for example, $gcd(8,15)=1$.

If $gcd(p,q)=1$ then there is exactly one solution, $e$. We can find that value $e$ by computing $a \cdot c \; (mod\, \mathbf{N})$ and then compute $b \cdot c \; (mod\, \mathbf{N})$ . Euler’s Phi function $phi(n)$ will inform us about the number of positive whole numbers < n, that are relative primes with n.

Next, the Capsule computes:

$$\phi(n) = (p-1)(q-1)$$

Which in code is implemented this way:

fn phi(&self, p: &BigUint, q: &BigUint) -> BigUint {
    (p - &BigUint::from(1u32)) * (q - &BigUint::from(1u32))
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_phi() {
        let p = BigUint::from(631u32);
        let q = BigUint::from(2153u32);

        let c = Capsule::default();
        assert_eq!(c.phi(&p, &q), BigUint::from(1355760u32));
    }
}

Step 3: Compute the Puzzle Strength

Angela is exhausted. She has lost count of the number of physical concern warnings that the Vanguard suite is flashing. Right now, she needs to focus on the next phase of the Time-Lock Puzzle activation procedure. In this cold and fateful place, the Capsule in front of her is waiting for Angela to provide two pieces of information, $T$ and $S$: $$T \cdot S = t$$ ⠀⠀⠀⠀⠀She takes a moment to remind herself that $T$ is the approximate number of seconds that they want the Time-Lock Puzzle to withstand an attacker’s decryption efforts. Further, $S$ is the number of squarings modulo $n$ per second that the attacker’s compute hardware can perform. The resulting $t$, is the Time-Lock’s Puzzle Strength - the total number of squarings that the attacker will have to perform to solve Time-Lock Puzzle.
⠀⠀⠀⠀⠀ Angela enters Ebmla Garpe’s estimates of time left until the next Federation ship will arrive: 691,200 seconds (8 days). Next, Angela enters Tania Teigen’s guestimated squaring power of the Rebel ship: 3,000,000. The Capsule instantly displays the total number of squarings needed to unlock it, once its Time-Lock Puzzle is activated:
$$691,200 \cdot 3,000,000 = 2,073,600,000,000$$

“Two trillion squarings to solve the Time-Lock Puzzle. Is that really strong enough?”
Feelings of anxiety wash over Angela, “. . .what if that pretentious cigarette-smoking bitch made an arithmetic mistake and we die for nothing?”.
⠀⠀⠀⠀⠀ Realising that she’s talking to herself, and feeling ashamed of the way she’s expressing her doubts over colleagues who are probably dead or dying - Angela squashes the urge to 10x the Puzzle Strength. She decides to trust her team, and proceeds by carefully entering the values for $T$ and $S$ via the Capsule’s neural arming interface.

The implementation is pretty straightforward,

fn compute_composite(&self, p: &BigUint, q: &BigUint) -> BigUint {
    p * q
}

fn compute_puzzle_strength(&self, s: &BigUint, t: &BigUint) -> BigUint {
    let _t = t * s;
    _t
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn angela_rae_test_run__step_03() {
        #[allow(non_snake_case)]
        let T = BigUint::from(691_200u32); // time-lock duration in seconds.
        
        #[allow(non_snake_case)]
        let S = BigUint::from(3_000_000u32); // number of squarings per second.

        let c = Capsule::default();
        assert_eq!(
            c.compute_puzzle_strength(&S,&T), 
            BigUint::from(2_073_600_000_000u64)
        );
    }
}

Step 4: Generating the Key to the Kingdom

⠀⠀⠀⠀⠀ Having assumed that she’s the only living organism in the vault, Dr. Angela Rae can barely believe her senses when she hears a sound behind her. She slowly turns around, just in time to see the elevator doors closing. . . and in horror witness the elevator accelerate up, towards the topside facility Command Center.
⠀⠀⠀⠀⠀"I’m the only Federation member with a security clearance to access that elevator. The Rebels must have breached our computer systems and somehow circumvented our security systems to gain access to the Vault elevator.".
⠀⠀⠀⠀⠀ Angela’s mind is racing in different directions, desperately looking for a probable scenario that does not land in the one that is staring right at her. “The elevator ride took 6 minutes to get down here. That means. . . I have less than 12 minutes to finish the locking procedure before this place is swarming with Rebels.”. She instructs her Vanguard to set a countdown timer for 12 minutes. In the top right corner of her helmet, numbers start counting down.
⠀⠀⠀⠀⠀The next phase of the Time-Lock Puzzle creation calls for Angela to initiate a Capsule procedure that will generate a secret key that will later be used to encrypt her message payload.
⠀⠀⠀⠀⠀ The key should be long enough so that brute searching for it is pointless, even with expected advances in computing power during the lifetime of the puzzle. Well, nothing groundbreaking in terms of computing power is likely to materialize in the hands of the Rebels within 8 days, the estimated time of arrival of the next Federation ship.

The implemention is as straightforward, as an inbound group of Rebels hoping to disturb your circles.",

fn compute_cm(&self, plaintext: &[u8]) -> (Key<Aes256Gcm>, Vec<u8>) {
    // The Capsule generates an AES-GCM mode private key.
    let key: Key<Aes256Gcm> = Aes256Gcm::generate_key(&mut OsRng);

    // This part is implemented in Step 5, below.
    (key, cm)
}

Step 5: Encrypting a Live’s Work

The blinking 00:08:37, in the upper right corner of her helmet’s information display, informs Angela that she has around eight minutes left to live. She started the countdown the moment she realized that the Rebels had likely succeeded in gaining access to the elevator, which is the only way to reach the vault.
⠀⠀⠀⠀⠀ Angela starts the transfer of the tiny 886 kb message payload, from the computer of her Vanguard suit, over to the Capsule. She authorizes a long list of security requests regarding the encryption of message data. “The folks who created this alien bowling bowl sure weren’t in a hurry. I’ll be dead long before this thing. . .”
A brief a humming sound, is followed by the Capsule informing Angela that the message payload, containing blueprints, the Ingegard algorithm, and the confirming test data - was successfully encrypted and stored inside the Capsule.
⠀⠀⠀⠀⠀ With the private key $K$, and the nonce generated in the previous step, the Capsule proceeds to encrypt Dr. Angela Rae’s message payload $M$. Surprisingly, it uses a Federation standard issue AES-GSM mode cryptosystem.

Formally, we get the encrypted text message, $C_M$, via: $$C_M = ENC(K,M)$$

Which we can implement using,

fn compute_cm(&self, plaintext: &[u8]) -> (Key<Aes256Gcm>, Vec<u8>) {
    // The Capsule generates an AES-GCM mode private key.
    let key: Key<Aes256Gcm> = Aes256Gcm::generate_key(&mut OsRng);
    
    // To make the encryption procedure unique, a 96 bit nonce (number used once)
    // is generated and used to uniquely seed the encryption.
    let mut nonce_bytes = [0u8; 12];
    OsRng.fill_bytes(&mut nonce_bytes);
    let nonce = Nonce::from_slice(&nonce_bytes);
    
    // The message payload is encrypted with the nonce and the key.
    let cipher = Aes256Gcm::new(&key);
    let cm = cipher
        .encrypt(&nonce, plaintext.as_ref())
        .expect("Encryption failed");

    // The encryption key and the encrypted message.
    (key, cm)
}

Step 6: Constructing the Cipher Key

“I knew this idea would never work.”

Dr. Angela Rae is close to having a mental breakdown. Her Vanguard environment suite is scrambling to issue a truckload of chemicals into her bloodstream, all in an effort to lower her racing heart rate. A 300 milliseconds long stream of positive imagery is flashed directly into Angela’s iris, an effort to trigger a serotonin response that will offset her accelerating depression.
⠀⠀⠀⠀⠀ “Cows on green spring pastures? Really? I’m minutes from having my brain split open by Rebel lasers, or worse, be tortured for hours until my mind caves in. . . and some Federation astro psychiatrist had the idea that images of happy cows will make me calm down?”.
⠀⠀⠀⠀⠀No answer. Not even from the dark mysterious orb floating in midair, in front of her. If only she had someone to talk to. “Yuhey?!”, she tries - nothing but silence.
⠀⠀⠀⠀⠀The countdown has just entered the territory of 2 minutes, 00:02:58 to be exact. Leaning on decades of discipline, and soothing images of cows on green pastures, Angela wills herself into action. The cipher key is one of the last elements that needs to be created, in order to activate the Time-Lock Puzzle, lock the Capsule, and declare mission accomplished.

The Capsule CipherKey Procedure:
Having generated the private key $K$ in step 4, Dr. Angela Rae initiates a Capsule procedure which performs the following calculation:
6.1 First, the Capsule picks a random $\mathbf{a}$ modulo $\mathbf{n}$, with $1<\mathbf{a}<\mathbf{n}$.

6.2. To be able to perform the computation which will produce the cipherkey $C_K$, the Capsule first has to compute: $$\mathbf{e}=2^\mathbf{t}\quad (mod\; \phi(\mathbf{n}))$$

6.3 It then computes $\mathbf{b}$, which is, in fact, the solution to the puzzle: $$\mathbf{b}=\mathbf{a}^\mathbf{e} \quad (mod\; \mathbf{n})$$

6.4. The output of the procedure will be a cipherkey $C_K$ which can be used to unlock the Time-Lock Puzzle. The cipherkey is produced with the following computation:
$$C_K = K + \mathbf{a}^{2^\mathbf{t}}\quad (mod\; \mathbf{n})$$

6.5. To verify that the cipherkey $C_K$ is actually working, the Capsule will use it to open a simulated version of the Time-Lock Puzzle. This step is described in the Appendix.

Implementation:

 fn compute_ck(&self, 
        a: &BigUint, phi_n: &BigUint, t: &BigUint,
        n: &BigUint, k: &Key<Aes256Gcm>
        ) -> BigUint {

    let e: BigUint = a.modpow(t, phi_n);
    let b: BigUint = a.modpow(&e, n);
    let ck = (BigUint::from_bytes_be(k.as_slice()) + b) % n;

    ck
}

Step 7: Endgame

With one minute left of her life, Dr. Angela Rae - Head of a Top Secret Federation advanced research program, located on a remote moonbase no one will ever hear about - is enjoying the sweet ouverture of Johann Sebastian Bach’s Orchestral Suite No.3 in D-dur. The 1,281 year-old masterpiece, is flowing through the loudspeakers of the Vanguard suite, a serenade of Angela’s accomplishment.
⠀⠀⠀⠀⠀ “One last step, and it’s Check Mate on these Rebel bitches!”
⠀⠀⠀⠀⠀ In front of her, the black alien-like Capsule, is patiently waiting for Angela to issue the final Initiate Locking command, which will seal the Capsule for a duration of 2 trillion squarings.
⠀⠀⠀⠀⠀ As a Federation Officer assigned to a military research program, and the only holder of the secret key which can instantly open the Capsule - Angela knows she cannot let the Rebels capture her alive. They would simply torture her until she told them everything, including the name of her secret lover.
⠀⠀⠀⠀⠀ She has ordered and authorized her Vanguard suit to inject instantly fatal doses of a military nerve agent, into her bloodstream at her command. Angela initiates the final step, authorizing the destruction of the secret keys $p$ and $q$ that were used to seed the whole creation of the Time-Lock Puzzle. Without these two keys, it’s impossible to open the Time-Lock without having to decrypt it by performing 2 trillion squaring operations.
⠀⠀⠀⠀⠀ The Capsule confirms the deletion of the two keys.
Beaming with a bittersweet mix of pride and sorrow, Angela orders the Capsule to commence the Locking Procedure,
⠀⠀⠀⠀⠀ “Give me a Softcopy when the locking procedure is - "
Angela stops mid-sentence, something in the corner of her eye is screaming for her attention. About 30 meters away from her, the elevator decelerates to a complete standstill. Doors open.
⠀⠀⠀⠀⠀ “Yuyeh?!” _What is he doing here?
Angela is surprised to see the face of her longtime colleague.
But she’s stunned to see dark shadows with raised weapons flash towards her.
She raises her arms in a fencing posture, screaming for the Vanguard computer to deliver the killing toxin into her bloodstream.
⠀⠀⠀⠀⠀ With shocking speed, Rebel hands are already upon her, ripping open the Vanguard. A sharp blow from an instrument, just below her right kidney. Chemically induced stasis? Are they trying to put me. . . in a . . . in a coma?.
⠀⠀⠀⠀⠀ Angela can feel two chemicals, Vanguard vs Rebel, fighting each other. One trying to kill her, the other trying to prevent her from dying. An unbelievably sharp pain seers her brain.
Screaming, she drops to the ground. Minus -90 degrees Celsius sweeps across her suitless body, but is barely registered by her failing nervous system. Her exposed retinas fail to deliver any signals that her brain can make sense of - darkness caves in on her.
⠀⠀⠀⠀⠀ A synthetically amplified human voice cuts through the darkness . . .
⠀⠀⠀⠀⠀ “Sir, we’re losing her. She managed to take a suicide toxin before we got to her. Our nanoserum is keeping her alive, but she’s in pretty bad shape.”
⠀⠀⠀⠀⠀ Another voice, this one much older . . . and calmer.
⠀⠀⠀⠀⠀ “Severe the blood flow to her brain. Tap into her cortex. Full tissue hardcopy. Do it!”
⠀⠀⠀⠀⠀ On the floor, a tiny part of what was once Dr. Angela Rae’s is trapped in limbo. A deadly neurotoxin compelling her to give up, give in, and die. But hardcoded organic reflexes, of what’s left of her neural system, are refusing the offer. Something, somewhere, is enticing her to remain…and reveal? Reveal what? Her curiosity piqued, the balance shifting towards . . . something.
⠀⠀⠀⠀⠀ “Sir, the neurotoxin has been neutralized. Brain tissue corruption is over 85%. I cannot confirm that the keys to the Capsule can be extracted from what’s left of her brain.”
⠀⠀⠀⠀⠀ The Rebel Strike Team Commander, standing over what remains of Dr. Angela Rae, is clearly disapointed . . . but hopeful.
⠀⠀⠀⠀⠀ “Copy. Transfer her to the Shub and initiate extraction procedures - salvaging that key is of extreme importance. And bring that guy!”.
⠀⠀⠀⠀⠀ The commander points to Yuyeh.
⠀⠀⠀⠀⠀ “He might be useful in creating a memory trap, that we can lure her conscious into. You two!, secure the facility, cut off any lines of escape, and set up T1C comms. We might be here longer than we plan-”
⠀⠀⠀⠀⠀ There’s a, barely noticeable, shift in the airwaves.
⠀⠀⠀⠀⠀ The Rebel commander swings around, weapon raised at the Capsule.
⠀⠀⠀⠀⠀ “What just happened?”
A tiny status indicator on a nearby panel enlightens him. $\text{LOCKING PROCEDURE COMPLETE}$.
⠀⠀⠀⠀⠀ “Fuck!”

Epilogue: I hope that someone enjoyed this format, of mixing math, code, a cheezy narrative, to try and make these technical concepts more fun to read about.

Appendix: How to solve the Time-Lock Puzzle

The Rebel Commander never expected this mission to be a walk in the Sim Park, but the current situation is best described as a tactical conundrum.
⠀⠀⠀⠀⠀ “Our medical team sure know their shit.”
⠀⠀⠀⠀⠀ On the table in front of him lies a grainy image printout of a number. During the last four hours, the team managed to salvage and extract fragments of a few visual memories from the female Federalist’s damaged brain. Most memories were stored in old neuron clusters, encoding what the team interpreted to be childhood memories; learning to ride a jetbike, some kind of 1st-in-class trophy, acceptance to the Federation Juvenile Military Academy, and so forth.

⠀⠀⠀⠀⠀ On the verge of giving up, the Rebel medical team then stumbled on a tiny neuro-cluster, bordering a massive volume of dead neurons. Similar to the childhood memory cluster, the tiny cluster appeared to encode the aggregate feeling of “pride and accomplishment”. However, in contrast to the old childhood cluster, these neurons had recently been stimulated!, not by the medical team’s nanorobotics, but by a surge of pure old-fashioned neurotransmitters, presumably belonging to the host.

⠀⠀⠀⠀⠀ Nanorobots successfully managed to entice a few individual neurons in the tiny cluster to connect to them, thereby creating a bridge to the remaining neurons. Building on top of that breakthrough, the team then relied on 31st century standard medical procedures for patients with traumatic brain injury - to map, copy, and virtualize the structure, density, and impedance of the cluster. Basically creating a biosynthetic 1:1 copy of the memory cluster, which could then be rendered back into the format that triggered the memory encoding in the first place. The final result of the entire operation now lay in front of the Rebel commander, in the form of a printed image, depicting a number:
$$691200$$

On the other side of the table, a female Sargent is the first one to speak. We’ve run a few million Posits on the ship’s computer. Provided our context, they all converge on that number representing time, which its standard unit being seconds. The amount corresponds to 8 days. From there, however, the confidence value in any extrapolation, into how 8 days relates to anything, drops quickly . . . except for one –”
⠀⠀⠀⠀⠀ “It’s the number of days left,” the commander interrupts, “until a military Federation ship will enter this system, hail this base, understand that something is wrong,
. . . and we’ll be knee-deep in shit.”
⠀⠀⠀⠀⠀ With obvious concern, the commander looks at the handful of senior rebels gathered around the planning table in the center of the Shub’s brig.
⠀⠀⠀⠀⠀ “In other words, we have 8 days to break into that Capsule.”

The Puzzle Solver
Let’s assume that the bitlength, of the chosen encryption scheme used, is large enough. In that case, “all” a Puzzle-solver needs to do, is to brute force search for the key $K$. However, brute-force-finding the key $K$ to the encryption $ENC$, this way is deemed infeasable, unless a Quantumn Computer is used. Intead, the fastest way to solve a Time-Lock Puzzle is to compute $\mathbf{b}$ (which was done by the Capsule in step 6.3.) : $$\mathbf{b}= \mathbf{a}^{2^\mathbf{t}} \quad (mod\; \mathbf{n})$$

Shortcut: Knowing the Euler Totient $\phi(n)$ enables $2^t$ to be reduced to $e\;(mod\; n)$, so that $b$ can be efficiently computed using the equation expressed in step 6.3.

However, computing $\phi(n)$ from $n$ is provably as hard as factoring $n$. Remember, Dr. Angela Rae managed to delete the primes $p$ and $q$, which were used to create the composite $n$, and! she also managed to get the Capsule locked before the Rebels got to her.
⠀⠀⠀⠀⠀ So, the fastest way to compute $b$, the answer to the puzzle, seems to be, to start with the number $a$ and then perform $t$ number of squarings in sequence (where the output of each squaring becomes the input of the next squaring) until $b$ is computed.
⠀⠀⠀⠀⠀ Let’s wrap up this little excursion by helping the Rebels with a subroutine which they can run on the Shub’s computer. Weather they manage to solve the puzzle and extract the blueprint to the Space Folding machine, before Federation forces return, we’ll never know.

Implementation,

use num_bigint::BigUint;
use num_traits::FromPrimitive;
use std::io::{self, Write};
use std::time::Instant;

fn main() {
    // The Time-Lock Puzzle has the form of a tuple: (n,a,t,CK,CM)
    let modulus_n = BigUint::from_u32(1355760);

    // The seed value that will be squared t times.
    let mut squaring_seed_a = BigUint::from_u64(2);

    // Number of required squarings.
    let required_squarings_t: u64 = 2_073_600_000_000;

    // Keeping track of time since squaring started.
    let start = Instant::now();

    // Starting the squaring procedure.
    for i in 0u64..=required_squarings_t {
        squaring_seed_a = Some(squaring_seed_a
            .as_mut()
            .expect("Squaring Failed")
            .modpow(
                &BigUint::from_u64(required_squarings_t).unwrap(),
                &modulus_n.as_ref().unwrap(),
                )
        );

        print!(
            "\rSquarings: {:013} Time:{}  Result:{:?}",
            i, start.elapsed().as_secs(), squaring_seed_a.clone().unwrap(),
        );

        io::stdout().flush().unwrap();
    }
}