Authentication system using one-time passwords

In a system in which a valid password is generated by generating an authentication parameter as a function of a time-dependent value using a predetermined first transformation having an inverse transformation and then generating a time-dependent password comprising a character string from said authentication parameter using a predetermined second transformation having an inverse transformation, said time-dependent value being recoverable from said authentication parameter using the inverse of said first transformation, said authentication parameter being recoverable from said password using the inverse of said second transformation, a method of validating a password presented to an authenticator comprising the steps of:

• regenerating said authentication parameter from the password presented to said authenticator using the inverse of said second transformation;
• regenerating said time-dependent value from said regenerated authentication parameter using the inverse of said first transformation;
• comparing the regenerated time-dependent value with a reference time-dependent value;
• and validating said password if said regenerated time-dependent value is within a predetermined tolerance of said reference time-dependent value, otherwise, rejecting said password.

In an authentication system, a method of generating and preliminarily validating a password, comprising the steps of:

• generating an authentication parameter from a set of authentication parameters having a predetermined first number of members;
• generating a password from a set of passwords having a second number of members greater than said first number of members from said authentication parameter using a predetermined transformation;
• presenting said password to an authenticator;
• determining whether there exists an authentication parameter in said set of authentication parameters from which the password presented to said authenticator is generated using said transformation;
• and
• preliminarily validating said password if there exists such an authentication parameter, otherwise, rejecting said password without further processing.

In an authentication system, a method of generating a time-dependent authentication code for presentation to an authenticator at an authenticating node, comprising the steps of:

• generating time-dependent information at a requesting node;
• combining said time-dependent information with non-time-dependent information to generate composite information, said time-dependent information being combined with said non-time-dependent information in such a manner that said time-dependent information is recoverable from said composite information by combining said composite information with said non-time-dependent information;
• generating an authentication code from said composite information using a predetermined transformation having an inverse transformation, said composite information being recoverable from said authentication code using said inverse transformation;
• transmitting said authentication code to said authenticator located at said authenticating node.

A method of transforming an input data block containing n bits into an output data block containing n bits, where n is an even integer, said method comprising the steps of:

• (a) partitioning the input data block into first and second halves each containing n/2 bits;
• (b) subjecting said halves of said input data block to a plurality of rounds of processing in which first and second input halves are transformed into first and second output halves serving as the corresponding input halves for the subsequent round, each of said rounds comprising the steps of:
• (1) generating a predetermined first function of the first input half;
• (2) generating the first output half as a predetermined second function of said predetermined first function and the second input half;
• and
• (3) generating the second output half as a predetermined third function of the first input half;
• at least one of said first, second and third functions involving a permutation of a set of n/2 input bits to yield n/2 output bits, said permutation being different for each of said rounds;
• and
• (c) recombining said first and second halves to produce said output data block.

A method of transforming an input data block containing n bits into an output data block containing n bits, where n is an even integer, said method comprising the steps of:

• (a) partitioning the input data block into first and second halves each containing n/2 bits;
• (b) subjecting said halves of said input data block to a plurality of rounds of processing in which first and second input halves are transformed into first and second output halves, the output halves of a given round serving as the corresponding input halves for the subsequent round, each of said rounds comprising the steps of:
• (1) padding said first input half with padding bits to
• generate a m-bit input value, where m is greater than n/2;
• (2) encrypting said m-bit input value using a predetermined m-bit encryption procedure to generate an m-bit output value;
• (3) selecting predetermined bits of said m-bit output
• value to form an n/2-bit output value;
• (4) generating the first output half for said round as a function of the modulo 2 sum of said n/2-bit output value and the second input half for said round;
• and
• (5) setting the second output half for said round equal to the first input half for said round;
• and
• (c) recombining said first and second halves to produce said output data block.