This message can only be revealed after 100 years.

During my semester in an intro to art class at UIUC, I created the following piece titled “When you read this I’ll be gone”.

When you read this I'll be gone

The image encodes a time locked message in the hue of the non-black pixels which can only be revealed after 100 years. I’ll explain:

Time Locked Crypto

Time locked crypto gives us the ability to create a mathematical time capsule. The time lock puzzle I used is from this paper by Rivest, Shamir, and Wagner. The scheme will look familiar to you if you have experience with RSA. I’ll paraphrase the method from the paper.

Encryption

If Alice wants to encrypt a message $M$ which takes $T$ seconds to reveal, then Alice performs the following steps:

  1. Alice generates strong, large, random primes $p$ and $q$ and calculates $n=pq$, $\phi(n) = (p-1)(q-1)$
  2. She calculates $t=TS$, where $S$ is the number of squarings per second a solver could perform
  3. She generates a random key $K$ and encrypts $C_M = AES(K, M)$ (or using some other symmetric cipher)
  4. She chooses a random $a$ s.t. $1 < a < n$
  5. Alice “hides” the key $K$ by calculating $C_K = K + a^{2^t}\text{ }(\text{mod } n)$ This can be calculated efficiently by an application of Euler’s theorem since Alice knows $\phi(n)$, which can only be efficiently obtained by knowing $p$ and $q$.
    1. She computes $e = 2^t\text{ }(\text{mod } \phi(n))$
    2. Now $C_K = K + a^e\text{ }(\text{mod } n)$
  6. She outputs $(n, a, t, C_K, C_M)$ and deletes all other information.

Decryption

Bob wants to decrypt the message from Alice. He is given $(n, a, t, C_K, C_M)$ and performs the following steps:

  1. Bob calculates $a = a^2\text{ }(\text{mod } n)$ $t$ times. This is the same as calculating $a^{2^t}\text{ }(\text{mod } n)$ This step should take $T$ seconds.
  2. Let the final value of $a$ be $b$.
  3. Bob calculates $K = C_K - b\text{ }(\text{mod } n)$
  4. He decrypts $C_M$ with $K$ to get $M$

Analysis

The useful aspect of this scheme is that there is no known way to parallelize the calculation of $a^{2^t}\text{ }(\text{mod } n)$. The fastest known way requires this repeated squaring which can only be performed sequentially. This means that decryption time only decreases with single core performance, so super computers don’t help things at all.

Another way to decrypt would be to factor $n$ into $p$ and $q$, but with well-chosen $p$ and $q$, this is thought to be impossible today. That is, at least until quantum computers become powerful enough. I suppose I’m betting on quantum computers not being strong enough for at least 100 years :)

An adversary could try to brute force $K$, so be sure to choose a cipher with a strong enough key size.

Choosing the correct number of squarings becomes more difficult as the intended decryption time increases. There’s no way I can possibly predict how fast computers will become in the next 100 years. I’m betting on Moore’s law being dead, though, and I chose a number which I hope gets me close enough to 100 years :)

Conclusion

Thanks for reading! Check out the source code for my implementation of the time lock puzzle here and various scripts to make the art here.