A Time-memory Trade Solution to Generate One-time Passwords Using Quadratic Residues Over Z_n

摘要

Authentication is a subject with applications in many fields. Since commonly used fixed passwords offer only a low level of security some more advanced techniques based on one-time passwords have been proposed. Among them, Leslie Lamport in his paper Password Authentication with Insecure Communication proposed the use of irreversible functions to generate one-time passwords. Because of the intractability of their inverses, cryptographic hash functions are the first solution for this purpose. Some functions defined over Z_n have also intractable inverses and for this reason are used in public key encryption. These functions can be used to generate one-time passwords and they have some advantages because they are more flexible than hash functions, but unfortunately they are harder to compute. This paper proposes a more efficient solution from the computational point of view based on a function defined over Z_n . The solution uses quadratic residues in a time-memory trade method. The computational performance of the proposed solution is analyzed and the results show that under certain circumstances the time-memory trade method gives better results for the functions defined on Z_n than for hash functions. A final case study ilustrates a practical example in which the results of the paper can be easily used.