Cryptographic methods for remote authentication

A method where one party, Alice, creates a cryptographic key K that is shared with another party, Bob, based on a secret value S that Alice shares with Bob, including the steps of

• choosing at least one parameter based on said secret value S that defines one of a multitude of means for public key distribution, and
• using the means for public key distribution defined by said parameter to create K,
• wherein the defined means for public key distribution includes at least one means selected from the group consisting of
• (a) means for creating a first outgoing message that includes a public key that is not encrypted using a symmetric cryptosystem with a key based on S, and
• (b) means for creating a second incoming message that includes a public key that is not encrypted using a symmetric cryptosystem with a key based on S, and
• wherein using the defined means for public key distribution does not reveal S to an attacker posing as Alice or Bob and prevents said attacker from testing a large number of guesses for S for each use of the method, and
• wherein using the defined means for public key distribution substantially insures that Bob will obtain the same value for K only if he has used the same value for S.

A method where one party, Alice, creates a cryptographic key K that is shared with another party, Bob, based on a secret value S that Alice shares with Bob, including the steps of

• choosing at least one parameter based on said secret value S that defines one of a multitude of means for public key distribution, and
• using the means for public key distribution defined by said parameter to create K,
• wherein the defined means for public key distribution includes
• a first mapping means that transforms a first base signal into an outgoing signal QA that is sent to Bob, and
• a second mapping means that transforms a second base signal into said cryptographic key K, and
• wherein the mapping means are exponentiation means for signals in a prime order mathematical group, and
• wherein using the defined means for public key distribution does not reveal S to an attacker posing as Alice or Bob and prevents said attacker from testing a large number of guesses for S for each use of the method, and
• wherein using the defined means for public key distribution substantially insures that Bob mill obtain the same value for K only if he has used the same value for S.

A method where one party, Alice, creates a cryptographic key K that is shared with another party, Bob, based on a secret value S that Alice shares with Bob, including the steps of

• choosing at least one parameter based on said secret value S that defines one of a multitude of means for public key distribution, and
• using the means for public key distribution defined by said parameter to create K,
• wherein said public key distribution means includes
• a first mapping means that transforms a first base signal into an outgoing signal QA that is sent to Bob, and
• a second mapping means that transforms a second base signal into said cryptographic key K, and
• wherein the mapping means are exponentiation means for signals in a mathematical group of points on an elliptic curve, and
• wherein using the defined means for public key distribution does not reveal S to an attacker posing as Alice or Bob and prevents said attacker from testing a large number of guesses for S for each use of the method, and
• wherein using the defined means for public key distribution substantially insures that Bob will obtain the same value for K only if he has used the same value for S.

A method for creating, in a protocol with another party, an authenticated cryptographic key using an authentication signal S derived from a potential small password, including the steps of choosing a random signal RA,

• receiving an incoming signal QB,
• using a first mapping means to generate an outgoing signal QA, wherein
• said first mapping means includes
• a base input, a mapping input, a mapped output, and a means for transforming a signal at said base input into a signal at said mapped output using a signal at said mapping input, wherein the transformation is infeasible to invert without using said signal at said mapping input,
• said base input of said first mapping means receives a signal selected from the group consisting of
• (a) said authentication signal S, and
• (b) said incoming signal QB,
• said mapping input of said first mapping means receives a first function of said first signal RA, and said mapped output of said first mapping means produces said outgoing signal QA, and
• generating a key signal K using a second mapping means that is identical to said first mapping means, wherein
• said base input of said second mapping means receives a signal selected from the group consisting of
• (a) said authentication signal S, and
• (b) said incoming signal QB,
• said base input of said second mapping means receives a different signal than said base input of said first mapping means,
• said mapping input of said second mapping means receives a second function of said first signal RA,
• said mapped output of said second mapping means produces said key signal K, wherein the value of said key signal K is infeasible to generate solely with said incoming signal QB and said fourth signal QA, and
• wherein said authenticated cryptographic key is based on said key signal K.

A method for creating an authenticated cryptographic key based on a potentially small shared authentication signal S that is shared with another party Bob, including the steps of

• choosing a random signal RA,
• receiving an incoming signal QB,
• using a first mapping means to generate an outgoing signal QA, wherein
• said first mapping means includes
• a parameter input, a base input, an exponent input, an exponential output, and means for transforming a signal at said base input into a signal at said exponential output using a signal at said exponent input, wherein the transformation is infeasible to invert without using said signal at said exponent input,
• said base input of said first mapping means receives a signal selected from the group consisting of
• (a) a base value g, and
• (b) said incoming signal QB,
• said exponent input of said first mapping means receives said first signal RA,
• said parameter input of said first mapping means receives said authentication signal S, and
• said exponential output of said first mapping means produces said outgoing signal QA,
• and
• generating a fifth signal K, using a second mapping means that is identical to said first mapping means, wherein
• said base input of said second mapping means receives a signal selected from the group consisting of
• (a) said base value g, and
• (b) said incoming signal QB,
• said base input of said second mapping means receives a different signal than said base input of said first mapping means,
• said exponent input of said second mapping means receives a function of said first signal RA,
• said parameter input of said second mapping means receives said authentication signal S,
• said exponential output of said second mapping means produces said fifth signal K,
• wherein said fifth signal K is infeasible to generate solely with said incoming signal QB and said fourth signal QA, and
• wherein the authenticated cryptographic key is based on said fifth signal K.

A method for Alice to prove knowledge of a password to another party Bob, where Bob has access to a bidden form of the password, including the steps of

• using an exponential key exchange system wherein
• an exponent C is chosen by Alice based on a password,
• an exponential S is computed corresponding to a base g and said exponent C,
• the hidden form of the password comprises said base g and said exponential S, and
• wherein said exponential key exchange system is used to create a primary shared key, and
• said primary shared key is used in conjunction with a secondary key to create a proof that Alice knows the password.

A system for Alice to prove knowledge of a password to another party Bob that has access to a hidden transformation of the password, including

• a first input connected to receive a first signal C representing the password,
• a second input, connected to receive a second signal U,
• a third input connected to receive a third signal that is derived from an incoming message received from Bob,
• a first output to provide a proof signal,
• means for constructing said proof signal that is a transformation of said second signal U with
• said first signal C and said third signal, and which transformation is infeasible to invert, and
• means for sending said proof signal in an outgoing message to Bob,
• wherein said hidden transformation of the password includes exponentiation of a base element in a mathematical group using an exponent derived from said first signal C, and
• wherein the system prevents an attacker who poses as Bob from testing a large number of guesses for the password for each use of the method,
• whereby Bob may use said proof signal to verify that Alice knows the password.

A system for verifying a password using a hidden password including

• a first input connected to receive a first signal X,
• a third input connected to receive a third signal S,
• a fourth input connected to receive a fourth signal that is derived from a message received from another party,
• a fifth input connected to receive a proof signal,
• a first output,
• means for generating at the first output a fourth signal U, that is a transformation of said first signal X and which transformation is infeasible to invert,
• means for generating a sixth signal, that is a transformation of said third signal S with said first signal X and which transformation is infeasible to invert,
• means for verifying whether said proof signal corresponds to said sixth signal and said fourth signal, and
• means for aborting when said proof signal does not correspond to said sixth signal and said fourth signal,
• wherein said third signal S represents the hidden password, and is a value computed as a transformation of the password,
• whereby a successful verification of said proof signal is interpreted as proof of knowledge of the password.

A method where one party, Alice, creates a cryptographic key K that is shared with another party, Bob, based on a secret password value known by Alice and a corresponding verifier value known by Bob, including the steps of

• creating a proof value by using an exponential computation in a mathematical group using an exponent that is based on a value C,
• wherein
• C is a function of the password,
• the verifier value comprises at least a base value g and an exponential value S,
• g and S are elements of said mathematical group related by the equation S=gC, which establishes the correspondence of the verifier to the password,
• using the method does not reveal the password to an attacker posing as Alice or Bob and prevents said attacker from testing a large number of guesses for the password for each use of the method, and
• wherein using the method substantially insures that Bob will obtain the same value for K only if he uses the verifier that corresponds to Alice's value C.