How Do I Get You To Do Your Homework - And Know How Long It Will Take You?
The title sounds like the age-old problem of teachers setting homework, as to how does the teacher know how long it will take? But what if you set a piece of homework and you think it will take 2 hours, but two students get together and split the homework task into two, and so they that it will only take them one hour to do the homework. The other problem is that the teacher will have to take the same steps as the student in order to time how long each question will take, but can the teacher create a question which takes a much shorter to produce, than to undertake?
What we need is a task which is intrinsically sequential and where the output of one task leads to the next one. It's a bit like having some puzzles to solve and which are contained in locked boxes. Once you solve a task from one box, it reveals the key for the next box. If we can determine the amount of time to solve the puzzles, and which is constant for everyone, we will thus set a task in which we know the amount of work that must be invested, in order to complete the whole task.
In cryptography, we define this as a time-locked cryptography puzzle with a defined workload. Ron Rivest in 1996 [paper] defined a puzzle which was fairly easy to compute [O(log(n))] and more difficult to solve [O(n^2)]. For this we create a range value (a) and then raise it to the power of 2^t, and where t is the difficulty level.
The method makes the usage of a squaring process which increases the work to compute the key. Now let's say that Bob wants to make sure that Alice cannot open a message within a given amount of time. Initially, Bob starts with two prime numbers (p) and (q) and determines (n):
n=p×q
We can also calculate PHI as:
PHI=(p?1)×(q?1)
Next we create an encryption (K) and with a message (MM) we encrypt:
C_m=Encrypt(K,M)
Next we select a random value (a) and a difficulty level (t), and compute a value of b which is added to the key (K):
C_K=K+a^{2^t} (mod n)
Bob will then send {n,a,t,C_K,C_m} and get Alice prove her work in order to decrypt the cipher message (C_m).
Alice then takes the values and computes the key with:
Key=C_K?a^2{^t} (mod n)
and which will have a workload dependent on the difficulty (t).
Bob, though, does not have the same workload at Alice, as he knows some or the original values. For him, he uses PHI to reduce the complexity:
?=2^t (mod PHI)
And then the calculation of the value to find becomes:
b=a^e (mod n)
The following is a sample run [here]:
Message: The quick brown fox
Keyseed: 12345
Key: WZRHGrsBESr8wYFZ9sx0tPURuZgG2lmzyvWpwXPKz8U=
Keyval: 40517827634140982427891826463487354397562163067645485726320510288945209855941
Bob sends this as the puzzle
N: 5808519655638548297258092061418259166774543092617038796300914729783059570485346403807454618287525932811499665099257674691573742312634492877501558241926510855265445655865943438821912402793071410193718769033138895292899984621735782974450454023113374373918673037042253066818942089671557106505473585751547903422068492120948273678721315120463641764405010804880764577517991306650182004053654755677171480098164870018127440284136797039199208818583865459976018367716791615092378912189828151394009348523859513336870704003245896134059043428841497988022873465729540129905401323861892790008954081042521197986890397363455472811639
a: 101
t: 1
CK: 40517827634140982427891826463487354397562163067645485726320510288945209866142
Encrypted: gAAAAABbCrlEUvLDQQX6gIiGqA81TTHzm5rD4Y6c4I5X5-qnkhGzqC8lOojkzmmy4cIJ3WXIn9aKO_5P3VY21ScNDf0wtOsTXo93-GbmwF6-_hBtyInh6g8=
Alice receives and now computes
Key guess= 40517827634140982427891826463487354397562163067645485726320510288945209855941
Decrpyted: The quick brown fox
And here is some sample code [here]. We use SHA-256 to hash the seed.
import datetime
import time
import hashlib
import base64
from cryptography.fernet import Fernet
import sys
from base64 import b64decode
import struct
message="hello"
keyseed = "12345"
a = 101
t= 3
def tost(i):
result = []
while i:
result.append(chr(i&0xFF))
i >>= 8
result.reverse()
return ''.join(result)
print "Message:\t",message
print "Keyseed:\t",keyseed
p=75184456329323393981453160999168869619896388565246270326667621020749883434526629149123313289822093813309128973674541785507146180116583118006552309466590981238828120901809218798591532127897713278598850326780359769279464340716666681725354754726329143696440538687112219849324721464631600820710676683650403820541
q=77256921699294288099751913986725879141470275753142260831695319390868938092522018978912165340760059157501314281329434440243543281733706145540078343592028736575027896004544593182243130855408638162095082271337507750610446164552740816661833414846974163466111988532153163988528271485739448606877973413411116622979
n = p*q
PHI = (p-1)*(q-1)
h = hashlib.sha256(keyseed).digest()
key=base64.urlsafe_b64encode(h)
encrypted = Fernet(key).encrypt(message)
print "Key:",key
keyval = int(b64decode(key).encode('hex'), 16)
print "Keyval:",keyval
CK = ((keyval) + a**(2*t)) % n
print "\n\nBob sends this as the puzzle"
print "N:\t",n
print "a:\t",a
print "t:\t",t
print "CK:\t",CK
print "Encrypted:\t",encrypted
print "\n\nAlice receives and now computes"
Key = (CK - a**(2*t)) % n
print "\nKey guess=",Key
val=tost(Key)
Keyguess = base64.urlsafe_b64encode( val)
decrypted = Fernet(Keyguess).decrypt(encrypted)
print "Decrypted:",decrypted
There you go. I've made you do some work!