0
$\begingroup$

I need an encryption algorithm that doesn't require keys and computationally easy to encrypt, hard to decrypt.

Decrypting can involve brute force.

If the algorithm can be applied again and again (encrypt text, then encrypt the encrypted, ...), it would be better as I would be able to scale the time to decrypt as I will, however, it shouldn't be like vigenere cipher, in which you can decrypt it in a limited number of steps (O(1)) no matter how many times you encrypted it.

Also if it has a library in Python or C or if it's simple enough for me to implement it it would be better.

Any helps are appreciated, I really need it.

Update: This was very helpful, describing the algorithm pointed out by the accepted answer: https://www.cs.tufts.edu/comp/116/archive/fall2013/wclarkson.pdf

And there's even scripts written already for it:

https://github.com/wclarkson/timelock

https://gist.github.com/raullenchai/3042166

And even I made one:

https://github.com/Aerbil/Time-lock-encryption


Kinda off-topic, the personal reason why i need it:

I have a habit of getting very heavily addicted to my smartphone very fast if I know it's password. Since a long time, I set my phone's password to a very long thing I won't be able to remember and wrote it to a paper and put that paper to somewhere distant from my home (so that it requires a lot of time to access it). This works, I'm so much more productive, disciplined, hardworking and not a zombie, and I'm able to do essential things like calling, replying to messages and taking notes already without unlocking my phone. But I'm afraid someone can take the password unknowingly. So I decided to encrypt my password and keep it on my computer.


$\endgroup$
7
  • $\begingroup$ You can encrypt your password using some symmetric key cipher with a random key sampled from a small space and then throw away the key. Then you need to use brute force to decrypt by trying all the keys from the small key space. $\endgroup$
    – lamba
    Commented Jul 19, 2022 at 6:42
  • $\begingroup$ @lamba Thanks very much! This is perfect for my purposes. I would want to accept your answer, but there doesn't seem to be a checkmark to do this. $\endgroup$
    – Aerbil
    Commented Jul 19, 2022 at 6:57
  • $\begingroup$ @lamba needs to convert his comment to an answer for you to accept it. Note that if there is any evidence as to what this small subset of the keyspace is, the scheme is totally insecure $\endgroup$
    – kodlu
    Commented Jul 19, 2022 at 7:03
  • $\begingroup$ @kodlu Thanks. Yeah I know. $\endgroup$
    – Aerbil
    Commented Jul 19, 2022 at 15:50
  • $\begingroup$ Are you more interested in time complexity (total amount of computations) or the actual time it takes to compute? In your case it sounds like you might want to have the ability to decrypt the password on your computer, but with a cryptographically enforced waiting period. $\endgroup$
    – Nic
    Commented Jul 20, 2022 at 0:11

2 Answers 2

1
$\begingroup$

From you mentioning that you are more concerned about the wall clock (i.e. real-life), I think what you are looking for is a delay (i.e. sequential) function. The basic concept is to require your computer to compute many operations in series (not staring one until it has finished the previous one), while keeping the total amount of work necessary relatively low. This way, if you rent a very large computer on the cloud, you won't gain a huge advantage over you just letting your own computer crunch the numbers in the background with a spare hardware thread.

I should note that it is trivial to require having the output of the delay function to decrypt your password as long as you know the output when you encrypt it. To do this, just hash the output and use it as the encryption key.

Hash based

I will first propose a very simple function to implement, but with the disadvantage that you will have to run the function for both encryption and decryption. This disadvantage is mitigated somewhat because we are reducing the total amount of work necessary to compute it.

First find a C library that has cryptographic hash functions. Our requirements for the hash function are low, and any modern cryptographic hash function is sufficient. It should come in an efficient library that is easy to use in a compiled language.

Let $f$ be the hash function, and k be an initial starting value (such as your name or a random number). Set your encryption key to be $(f\circ f\circ f\circ \ldots f\circ f\circ f)(k)$. The number of iterations, $t$, determines how long this will take. In pseudo code:

x = k
loop t times {
x = hash(x)
}
return x

Experiment with different lower test $t$s to determine the speed of your computer.

At the cost of making this a little more complicated, you can modify this to make encryption parallelizable (i.e. takes advantage of multi-threading) without decryption being parallelizable. However encryption will still require the same amount of total work as decryption. I won't explain this technique here.

RSW

If you want the encryption to take significantly less total work than decryption, then you need to use a delay function with a trapdoor. Whoever has the trapdoor (e.g. the creator of the function) can evaluate the function easily, but those who don't have to do the many steps. You will simply delete your trap door after you encrypt your password.

RSW, as the name suggests, is very similar to RSA, except it serves a different purpose: a delay function with a trapdoor. The basic idea of the function is to evaluate $k^{2^t}\mod N$ where the prime factorization of $N$ is the trap door. This takes $t$ steps to compute with out the trap door. Rather than describing RSW I will give you a link to the original paper. I will give you a few implementation details.

You mentioned knowing both C and Python. I suggest installing the GMP library on your computer and then installing the Python interface GMPY2. Since the creation of the puzzle is a bit complicated but not too computationally expensive I suggest using Python's IDLE to create the function and finding the initial result. While in most real life scenarios you would want to choose a modulus size of at least 1024 bits, 512 bits makes sense considering your threat model is yourself in 6 hours.

For the function evaluation I recommend C or C++. I have found the fastest method is to set an integer e to be $2^s$ where $s$ is a divisor of $t$ and is probably more than around ~10000. GMP will store all $s$ bits in RAM which is why we don't want it to be as large as $2^t$. Use GMP to call mpz_powm() with e as the exponent $t/s$ times.

$\endgroup$
4
  • $\begingroup$ Thanks! If I have time, I would want to use RSW, otherwise I'll use simpler hashing inshaAllah. I read the paper and I understood halfly, to clarify, k being the key used to encrypt the message and t being the number of steps required (and known publicly), is encrypted key k^2^t mod N? And the ease of encryption comes from the fact that we can compute a mod (b*c) from a mod b and a mod c? The part I didn't understand is that how we can even get back to k from k^2^t mod N? Doesn't taking modulus in that function reduce the amount of information? $\endgroup$
    – Aerbil
    Commented Jul 21, 2022 at 5:55
  • $\begingroup$ I selected yours as answer as both are better than brute force, as encryption time is deterministic. $\endgroup$
    – Aerbil
    Commented Jul 21, 2022 at 6:03
  • $\begingroup$ I meant decryption time, comments are uneditable after 5 mins. $\endgroup$
    – Aerbil
    Commented Jul 21, 2022 at 6:46
  • 1
    $\begingroup$ Ok, now I started to make sense of decryption (after learning what that phi symbol is), you can ignore all comments of mine under your answer. $\endgroup$
    – Aerbil
    Commented Jul 21, 2022 at 16:41
2
$\begingroup$

You can encrypt your password using some symmetric key cipher with a random key sampled from a small space (e.g., they key can be a number between 0 and 999) and then throw away the key. Then you need to use brute force to decrypt by trying all the keys from the small key space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.