Introduction
Suppose Alice wants to encrypt a secret message "hello" and pass the ciphertext (the encrypted message) to Bob who decrypts and reads the original message. Alice and Bob use a shared password "john" to encrypt and decrypt. Alice and Bob do not want Eva to read the message, but they are aware that Eva knows how to decrypt the message and learns the ciphertext. What Eva does not know is the password "john". However Eva has a hackers dictionary of a million passwords including "john"; and she can try each password from the dictionary in a hope to decrypt the message. If decryption is fast, then trying all million passwords is not a big job. Can Alice and Bob make sure that Eva is not able to decrypt and read their secret message?
There are two possible solutions. One is to use a complex password e.g. "john34xrvq968b"'. But Alice and Bob already have to remember so many different passwords that remembering another complex password is too difficult for them. So let us ignore this case. The second solution is to make decryption expensive. In other words every time Eva tries a new password, the program spends a fair amount of time to decrypt and to give the result whether the password matched or not. If one decryption takes 30 seconds, then Eva has to wait a year to try all the passwords from the dictionary. Of course Eva can use a supercomputer with parallel computation to reduce that time, but in any case a lot of computational work has to be done to break the encryption.
Strengthening Password Using Time
The most obvious solution is to increase the complexity of the decryption by extra computational work. For example, the original password can be digested by a hash function in a number of cycles before applying to encryption. However, the problem here is - how much of the 'extra work' is enough? With a fixed number of cycles the number must be known that adds a parameter to the algorithm. If you add too little, then it does not make it too hard for Eva to break the decryption. If you add too much, then the decryption for Bob can be unusable on a weak computational device.
A solution is to let the algorithm increase the decryption complexity by Alice giving a certain amount of time when encrypting. From Alice's point of view - she starts the encryption process and then decides when to stop. The amount of time when she waits defines the complexity of the future decryption: the longer period, the more time-consuming decryption is.
In this case the decryption process must solve a corresponding computational problem. On a similar computational device this would take as much time as Alice waited. For Eva, every attempt to match the password requires the same computational effort, i.e. spent time.
A Cipher Example
Let us consider a cipher presented in the Diagram. To encrypt message M Alice uses a one-way function to generate the
cipher pattern X out of the password P and the salt S. Salt is a random string added to the password to make the cipher pattern different for every encryption. Obviously the salt has to be passed together with the encrypted message, so Bob is able to generate the same cipher pattern. For Eva, however, the salt prevents pre-digestion of the dictionary to speed up cracking the password.
Instead of using the cipher pattern immediately Alice lets the algorithm to digest it again and again in a cycle until Alice presses stop. The algorithm selects the best pattern according to a predefined rule; for example, the smallest or the greatest. This rule ensures that the generation is logarithmic in time -- the number of new best found patterns is O(log n). The found cipher pattern X is used to encrypt the message M producing the ciphertext C. To get C out of M and X any strong cipher algorithm can be used.
The decryption process works in a similar way. However this time every new best found cipher pattern is tried to decrypt the message. This process continues until the message is decrypted. The decryption diagram is the same with the exception that the message M and the cipher text C are swapped.
An alternative to cyclic digestion of cipher pattern can be produced by an enumerated suffix appended to the password, such as 1,2,3,... changing the password to "john1", "john2", etc. If Alice encrypts the message for herself to decrypt later, she may remember a part of the suffix that can make decryption faster. For example, while encrypting, the algorithm has found the combination "salt+john5663058" producing the smallest X and reported to Alice the suffix 5663058. If Alice remembers the first digit 5 and uses "john5" to decrypt, the decryption will take 10 times faster because it has to run only up to 663058 instead of 5663058. The suffix can be constructed of any symbols. The only condition is that it is selected from a reproducible sequence.
A Numerical Example
See http://jrxv.net/x/16/sewp_main.pdf
Suppose Alice wants to encrypt a secret message "hello" and pass the ciphertext (the encrypted message) to Bob who decrypts and reads the original message. Alice and Bob use a shared password "john" to encrypt and decrypt. Alice and Bob do not want Eva to read the message, but they are aware that Eva knows how to decrypt the message and learns the ciphertext. What Eva does not know is the password "john". However Eva has a hackers dictionary of a million passwords including "john"; and she can try each password from the dictionary in a hope to decrypt the message. If decryption is fast, then trying all million passwords is not a big job. Can Alice and Bob make sure that Eva is not able to decrypt and read their secret message?
There are two possible solutions. One is to use a complex password e.g. "john34xrvq968b"'. But Alice and Bob already have to remember so many different passwords that remembering another complex password is too difficult for them. So let us ignore this case. The second solution is to make decryption expensive. In other words every time Eva tries a new password, the program spends a fair amount of time to decrypt and to give the result whether the password matched or not. If one decryption takes 30 seconds, then Eva has to wait a year to try all the passwords from the dictionary. Of course Eva can use a supercomputer with parallel computation to reduce that time, but in any case a lot of computational work has to be done to break the encryption.
Strengthening Password Using Time
The most obvious solution is to increase the complexity of the decryption by extra computational work. For example, the original password can be digested by a hash function in a number of cycles before applying to encryption. However, the problem here is - how much of the 'extra work' is enough? With a fixed number of cycles the number must be known that adds a parameter to the algorithm. If you add too little, then it does not make it too hard for Eva to break the decryption. If you add too much, then the decryption for Bob can be unusable on a weak computational device.
A solution is to let the algorithm increase the decryption complexity by Alice giving a certain amount of time when encrypting. From Alice's point of view - she starts the encryption process and then decides when to stop. The amount of time when she waits defines the complexity of the future decryption: the longer period, the more time-consuming decryption is.
In this case the decryption process must solve a corresponding computational problem. On a similar computational device this would take as much time as Alice waited. For Eva, every attempt to match the password requires the same computational effort, i.e. spent time.
A Cipher Example
Let us consider a cipher presented in the Diagram. To encrypt message M Alice uses a one-way function to generate the
Instead of using the cipher pattern immediately Alice lets the algorithm to digest it again and again in a cycle until Alice presses stop. The algorithm selects the best pattern according to a predefined rule; for example, the smallest or the greatest. This rule ensures that the generation is logarithmic in time -- the number of new best found patterns is O(log n). The found cipher pattern X is used to encrypt the message M producing the ciphertext C. To get C out of M and X any strong cipher algorithm can be used.
The decryption process works in a similar way. However this time every new best found cipher pattern is tried to decrypt the message. This process continues until the message is decrypted. The decryption diagram is the same with the exception that the message M and the cipher text C are swapped.
An alternative to cyclic digestion of cipher pattern can be produced by an enumerated suffix appended to the password, such as 1,2,3,... changing the password to "john1", "john2", etc. If Alice encrypts the message for herself to decrypt later, she may remember a part of the suffix that can make decryption faster. For example, while encrypting, the algorithm has found the combination "salt+john5663058" producing the smallest X and reported to Alice the suffix 5663058. If Alice remembers the first digit 5 and uses "john5" to decrypt, the decryption will take 10 times faster because it has to run only up to 663058 instead of 5663058. The suffix can be constructed of any symbols. The only condition is that it is selected from a reproducible sequence.
A Numerical Example
See http://jrxv.net/x/16/sewp_main.pdf
