A cryptographic protocol for secure communications

Background of the Invention

Technical field

The This invention relates to cryptographic communications generally and more particularly to methods and systems for the preparation of an authenticated and / or confidential communications between Participants who initially share only a relatively insecure secret.

State of technology

subscriber want frequently a confidential and authenticated communications perform. Although the Confidentiality can be sought through physical means is it often more efficient and effective to use cryptographic means. also can authenticate, although by physically secure and firmly associated devices may be desirable, also with cryptographic methods are more readily achieved.

With classical cryptographic methods to authenticate a be Participants over another participant by unveiling a secret (eg a password), that is known only to the respective subscribers. If the secret reveals is, it may, particularly in transmission of a exposed physically insecure communication channel eavesdropping be. This allows the listener to experience the mystery and later for one the subscriber spend.

the Kerberos authentication system of MIT Athena project attempts to solve this problem in the context of computer networks. RM Needham and MD Schroeder, "Using Encryption for Authentication in Large Networks of Computers ", Communications of the ACM, Volume 21, No. 12, 993-999 (December 1978). and J. Steiner, C. Neumann and JI Schiller, "An Authentication Service for Open Network Systems ", Proc. Winter USENIX Conference, Dallas, 1988. According to the Kerberos System is any user of the Kerberos system a non-secret unique login ID given, and the user must choose a secret password. the Password is supplied by the user to the Kerberos system and is kept secret by both participants. As the password is kept secret, it can be used by the user to be opposite to to authenticate the Kerberos system.

If a user of the Kerberos system wishes to a Kerberos computer access, the user sends his login ID to the Kerberos computer with an access request. Although the authentication characterized could be achieved, that the User is prompted his password with his ID to send, this method has the significant disadvantage that an eavesdropper determine the ID and the corresponding password of the user readily could.

Around to solve this problem, authenticates the Kerberos system the user's identity by producing a riddle, the probably be resolved only by the true user can. The puzzle can be regarded as a locked box, the message contains, the secured by a combination lock is. The riddle is constructed by the Kerberos system so that the combination of the combination lock the secret Password is, that is the true user known of the received ID assigned. The real user who knows their own password, can the password use to open the lock and restore the message therein. If the combination for the Combination lock of randomly a great Number of ways chosen is, it is for a person who for itself someone else spends, impractical, the lock to "crack".

Of the Mechanism by which the mystery is produced, typically uses several steps. First created the Kerberos system, a random number as the message that the transmitted user shall be. Next generates the Kerberos system a mystery (containing the random number) so, that this Password the user's key for the solution the riddle and the restoration of the message is. Take for example in that according to a Class of puzzles each puzzle equal to a random number plus a number of the password represents user. If the user's password is 3049, the and the random number 5294, then the puzzle 8343rd

the mystery is sent by the Kerberos system to the user. If this Example continues solves the user who knows their own password, the mystery and delivers the message restores, <?page 3?>by his or her password (3049) of the Brain (8343) subtracted to recover the message (5294). On Lauscher, the mystery that (8343), but not the password knows, is unlikely to discover the message. According to the Kerberos System all transfers between the user and the Kerberos system after the first puzzle also in the form of puzzles Posted. The key to the solution the following riddle however, the random number in the first puzzles that the Kerberos System would and a true user known. is authenticated implicitly when the user and the computer communicate useful can. And, since the whole communication is encrypted, the confidentiality is achieved.

At this point is a discussion of the nomenclature of cryptology appropriate. A class of puzzles is cryptographically as a " System "or" cryptosystem "known. The process of creating a puzzle is known as "encryption" and the process of dissolving a riddle, to restore the message therein, is known as "decryption". The riddle is as "encrypted Text refers to " and the message in the puzzle is referred to as "plain text". The Elements of a cryptosystem are a cryptographic key or key distinguished. According to the scheme a concrete cryptosystem is a key used to plain text to lock in ciphertext, and is also used to unlock the encrypted Text used to recover the plaintext.

Of the key for the Generating a specific riddle (Ie, locking plaintext into ciphertext) is as an "encryption key" known, and key to dissolve a puzzle (ie restore the plaintext from ciphertext) known as "decryption key". If according to the draft a particular cryptosystem, the encryption key and the decryption key identical are, the cryptosystem is known as a "symmetric cryptosystem." The above Cryptosystem shown is a symmetric cryptosystem, since the number 3049 is the key as well as the generation and the solution the riddle is.

On Cryptosystem with an encryption key E and another decryption key D, so that it is computationally impractical to determine D from E, is as a "cryptosystem asymmetric key "or a" public cryptosystem Keys "known. A cryptosystem asymmetric keys is not a cryptosystem symmetric key and is therefore useful for Introduction of secure communication between participants have not communicated generally above and not a shared secret for a Share symmetric cryptosystem. In contrast to a cryptosystem asymmetric key allows a distribution system with two public keys exchange remote users, messages back and forth until they a common key come to a cryptosystem symmetric keys. The basic requirement a cryptosystem with asymmetric keys is that an eavesdropper, knows of any news, find it computationally impractical must the common key to calculate.

Around to avoid a repeat of background material, is on W. Diffie and ME Hellman, "New Directions in Cryptography " IEEE Transactions on Information Theory, Vol IT-22, no. 6, S. 644-654 (Nov. 1976) and W. Diffie and ME Hellman, "Privacy and Authentication: An Introduction to Cryptography ", Proceedings made of the IEEE, Volume 67, No. 3, pp. 397-427 (March 1979).

Again with respect to the Kerberos system sees an eavesdropper on a communications channel, uses the Kerberos system, only the login ID of the person, the network in plain text is, that is something that is already publicly is known. The password the person is never transmitted explicitly, and the key and the subsequent messages are encrypted and are therefore ostensibly for sure. However, the Kerberos system has several limitations and some weaknesses. SM Bellovin and M. Merritt, "Limitations of the Kerberos Authentication System ", Proc. Winter USENIX Conference, Dallas, (1991). People seek out bad passwords, and good either forget written down or do not like. Thus, a Lauscher passive encrypted record messages and a modified brute force attack on a password Start by encrypted Messages with tentative passwords are decrypted, to understand Plaintext is generated. Kerberos has additional shortcomings on, but shows weakness on which all classical key exchange protocols Two participants have in common: the cryptographic passwords are Offline, brute force attacks exposed. Nevertheless, can such Key exchange protocols be appropriate if the passwords long, accidentally selected Strings are lead but considerable Difficulties if the passwords of selected naive users will.

Other Attempts the problem of attacks by offline password-rates to avoid, to be <?page 4?>Example of TMA Lomas, L. Gong, JH Saltzer and RM Needham in "Reducing Risks from Poorly Chosen Keys " Proceedings of the Twelfth ACM Symposium on Operating System Principles, SIGOPS, 14-18 (December 1989); and L. Gong, "Verifiable-text Attacks in Cryptographic Protocols ", Proc. of the IEEE INFOCOM - The Conf. on Computer Communications, (1990). Lomas et al. teach a protocol in which cryptoanalytical most Attacks are unsuccessful, but which requires authentication, that each participant additionally to their respective passwords a Password, a public key for a Cryptosystem asymmetric keys knows. If the public key reasonable to provide security degree, one can not easily remember it.

Out the article by Abbruscato: "Choosing a Key Management Style Suits did the Application ", in Data Communications, McGraw Hill, New York, vol. 15, no. 4, April 1986, pp 149-150, 153-160, is a key distribution method between subscribers A and B using a public key to encrypt a symmetric key known.

The transferred Received messages are a known of a two participants verification key derived MAC protected.

Summary the invention

In of the present invention, of which various aspects, species and variations in the claims are set, the shared secret authentication signal (Ie password) used to at least a portion of one or more of in a distribution system with public Keys (such as for example, the Diffie-Hellman discussed below) system messages exchanged encrypt.

The present invention provides a mechanism for the preparation of a confidential and authenticated communications between Participants who share only a relatively insecure secret by a different from the prior art approach is used, and where many of the costs and limitations of prior art cryptographic Protocols are avoided. The present invention according to the conducted Communication is safer than in the prior art and prevents, that this shared secret (eg a password) is revealed an eavesdropper.

These Results are in one embodiment achieved with the present invention, in which a part of one or more of the messages of a distribution system with public keys is encrypted with the shared secret as the encryption key. In this respect, resembles Embodiment the Kerberos system, but differs in so far as essential as the ciphertext is not merely a random number, but a portion of a message distribution system of a public key.

There a cryptosystem asymmetric key a superset of the functionality of a Distribution system with public keys provides, it is believed that distribution systems public key cryptosystems asymmetric key included, with which the comparable functionality of distribution systems with public keys provided.

Short description the drawing

<figref idrefs="S39">1</figref> shows a sequence of messages, which in an exemplary embodiment of the invention are used, the asymmetric cryptosystem with keys used and where the first two messages are encrypted with a password.

<figref idrefs="S39">2</figref> shows a sequence of messages, which in an exemplary embodiment the invention can be used to protect against attacks on the Passwords are, when a session key was recovered from an attacker.

<figref idrefs="S40">3</figref> shows a sequence of messages, which in an exemplary embodiment of the invention are used, in which only part of the initial message with the password encoded is.

<figref idrefs="S40">4</figref> shows a sequence of messages, which in an exemplary embodiment of the invention are used, in which only part of the response message with the password encoded is.

&lt;?page 5?&gt;

<figref idrefs="S40">5</figref> shows a sequence of messages with a non-within the scope of the present invention falling embodiment are used, which a distribution system with public keys used.

<figref idrefs="S41">6</figref> shows a device which uses an asymmetric key cryptosystem and in which the first two messages are encrypted.

Detailed description

1. notation

It The following notation is used throughout: <dl><dt>A, B</dt><dd>Participants who want to communicate (Alice and Bob).</dd><dt>P</dt><dd>The password: a shared secret, which often as a key is used.</dd><dt>P_n</dt><dd>A key: in usually either P or derived from P.</dd><dt>P (X)</dt><dd>The secret key encryption an argument "X" with the key P.</dd><dt>P^-1(X)</dt><dd>The secret key decryption an argument "X" with the key P.</dd><dt>e_A(X)</dt><dd>encryption asymmetric key an argument "X" with the public key E_A,</dd><dt>D_A(X)</dt><dd>decryption asymmetric key an argument "X" with the private key D_A,</dd><dt>query_A</dt><dd>A random challenge, generated by Alice.</dd><dt>query_B</dt><dd>A random challenge, generated by Bob. </dd><dt>R</dt><dd>A session key or is a number from which a session key may be derived.</dd><dt>p, q</dt><dd>Primes.</dd></dl>

On Cryptosystem symmetric key is a conventional Cryptosystem prior up to the 70's; use such cryptosystems symmetric key secret key. In contrast, use a cryptosystem with asymmetric keys public Encryption- and private decryption key.

In the following description and in the claims, "secure communications" means a communication, authenticating and / or confidential.

It Embodiments the invention presented using cryptosystems asymmetric keys. In the following description and in the claims are in "distribution systems that employ public Keys "cryptosystems asymmetric keys with included, the functions of a distribution system with public keys supply.

2. embodiments, use cryptosystems with asymmetric keys

The In an exemplary embodiment the invention exchanged messages are in <figref idrefs="S39">1</figref> shown. This typical embodiment use a cryptosystem with asymmetric keys. Alice<figref>101</figref> and bob <figref>103</figref> are entities the confidential and authenticated communications over a want to establish channel. The messages shown can through public or private communication channels, such as telephone calls received, will. In this embodiment, and each embodiment the detailed Description it is assumed that Alice and Bob prior to the beginning the message exchange both know the secret P. It should also in this embodiment and each embodiment the detailed Description Alice the caller and the called party Bob. Regarding <figref idrefs="S39">1</figref> applies: <ul><li>1. Alice generates a random pair of public key / private key e_A and D_A and encrypted E_A or a portion thereof in a cryptosystem symmetric key For example, a type in Data Encryption Standard, Federal Information Processing Standards Publication 46, National Bureau of Standards, US Dept. of Commerce, January 1977, describes wherein said password P as the key is used so that P (E_A) Results. Alice sends P (E_A) (Msg. <figref>109</figref>) to Bob (see <figref>109</figref>). This message may include other information, such as the identity of the Transmitter or the rest of the public key, if a part thereof is not encrypted.</li><li>2. Bob, who knows P, decrypts Msg. <figref>109</figref>To P^-1(P (E_A)) = e_A to obtain. Bob then generates a Random secret key R and encrypts with him in the cryptosystem asymmetric keys &lt;?page 6?&gt;the key E_ATo E_A(R) to be produced. This string is further encrypted with P. Bob sends P (E_A(R)) (Msg. <figref>115</figref>) to Alice (please refer <figref>115</figref>).</li><li>3. Alice, the P and D_A knows, used this in order to D_A(P^-1(P (E_A(R)))) = R to obtain. Thereafter, R or R derived figures as a key in further communications be used between Alice and Bob.</li></ul>

2.1. Key validation process

As soon as The participants have agreed on a key R, can in certain circumstances be appropriate when the participants take steps to ensure that the Key during transmission has not been tampered. In the present specification are those Started as a key validation process known.

2.1.1. Protection against playback attacks

the outlined in the above section 2 embodiment is may not apply all applications because it may insufficient protection against playback attacks. A replay attack is an attempt of the eavesdropper, the control of the communication channel has to recall previous past messages in the communication channel to to try for outputting one of the participants. If the possibility of a replay attack consists, comprises A preferred embodiment the invention provides a mechanism for repelling such an attack. Referring again to <figref idrefs="S39">1</figref> includes this embodiment Thus the following messages: <ul><li>1. As previously begins the message exchange when Alice <figref>101</figref> P (E_A) (Msg. <figref>109</figref>) to Bob <figref>103</figref> sends.</li><li>2. Again, the responses to Bob as previously described by by sending P (E_A(R)) (Msg. <figref>115</figref>) to Alice.</li><li>3. When receiving msg. <figref>115</figref> begins the query / response mechanism. Alice decrypts Msg. <figref>115</figref>To obtain R, generates a random string query_A and encrypts it with R to R (query_A) to create. She sends R (query_A) (Msg. <figref>121</figref>) to Bob (see <figref>121</figref>).</li><li>4. Bob decrypts Msg. <figref>121</figref>To query_A to obtain, generates a random string query_B. encoded the two queries with the secret key and sends R R (query_A, query_B) (Msg. <figref>127</figref>) to Alice (see <figref>127</figref>).</li><li>5. Alice decrypts Msg. <figref>127</figref>To query_A and query_B to obtain, and compares the former with their former Query. If a match encoded they query_B with R and sends R (query_B) (Msg. <figref>133</figref>) to Bob (see <figref>133</figref>).</li><li>6. On receiving msg. <figref>133</figref> Bob decrypts, to query_B to obtain, and compares with the earlier Query. If a match is the query / response mechanism successful, and participants can R or a group derived from R string as a session key in use of the further communication.</li></ul>

Of the Query / response of the above embodiment could be achieved by other mechanisms for the validation of R to be replaced. For example could encrypts the time by R be exchanged under the safety-critical assumption that clocks are synchronized and monotonous to a certain extent.

2.1.2 Protection from recovered session keys

If a cryptanalysis specialist restores a session key R, can he use R as a reference to P and E_A to attack. <figref idrefs="S39">2</figref> shows the messages that In an exemplary embodiment be replaced, the attack of a P or E_A Disabled, when R is known. If there is a chance that an unauthorized cryptanalysis specialist a session key could recover contains another preferred embodiment the invention provides a mechanism to prevent such an attack. Regarding <figref idrefs="S39">2</figref> applies: <ul><li>1. the message exchange when Alice As previously begins <figref>201</figref>&lt;?page 7?&gt;P (E_A) (After r. <figref>209</figref>) to Bob <figref>203</figref> sends.</li><li>2. Again, the responses to Bob by P (E_A(R)) (Msg. <figref>215</figref>) sends to Alice (see <figref>215</figref>).</li><li>3. Alice decrypts Msg. <figref>215</figref>To obtain R, randomly generates a unique challenge query_A and a random subkey S_A, The query and the partial key encrypted with R and sends R (query_A, S_A) (Msg. <figref>221</figref>) to Bob (see <figref>221</figref>).</li><li>4. When receiving msg. <figref>221</figref> Bob decrypts them to query_A and S_A to obtained a unique query generates query_B and a random subkey S_B and encrypts the two queries and its subkey with the secret key R and sends R (query_A, query_B, S_B) (Msg. <figref>227</figref>) to Alice (see <figref>227</figref>).</li><li>5. On receiving msg. <figref>227</figref> decrypts Alice them to query_A and query_B to receive, and compares the former with their previous query. If a match encoded they query_B with R to R (query_B) to obtain. Alice sends R (query_B) (Msg. <figref>233</figref>) to Bob (see <figref>233</figref>).</li><li>6. On receiving msg. <figref>233</figref> Bob decrypts them to query_B to obtain, and compares them with query_B of Msg. <figref>227</figref>, If a match Calculate the two participants a key S = f (S_A. S_B), For a specific, two known function f. S is used as the secret key, to all subsequent exchange information to encrypt, and R is reduced to the role of a key exchange key.</li></ul>

It is conceivable that a resourceful cryptanalysis specialist might be able the Presence of queries and responses in different messages to use to attack R. If such an attack Problem is to the responses are modified so that it comprises a one-way function queries instead of the queries contain himself. Thus could Msg.<figref>227</figref> to <st32:df xmlns:st32="http://lighthouseip.com/">R (g (query<st32:sub>A</st32:sub>), Query<st32:sub>B</st32:sub>, S<st32:sub>A</st32:sub>)</st32:df>will, and Msg. <figref>233</figref> would like changed.

2.2. Bilateral encryption compared to unilateral encryption

If a part of both of the first two messages are encrypted with the password, and it Msg. <figref>109</figref> and Msg. <figref>115</figref> in the above presented embodiment happens, contains the embodiment of a called bilateral encryption. In other embodiments, but is necessary no bilateral encryption. If only one of the first message is encrypted, it is unilateral encoding called. Note that it are two types of unilateral encryption: (1) if the encrypted first message is and (2) when the second message is encrypted. Section 2.2.1 shows an embodiment of the invention, in which only the first message is encrypted with the password, and Section 2.2.2 shows an embodiment in which only encrypts the second message is.

2.2.1. An embodiment that uses the RSA asymmetric key cryptosystem

A Exemplary Embodiment the invention uses a "RSA" known cryptosystem asymmetric keys, the RL Rivest, A. Shamir and L. Adleman in US Pat. No. 4,405,829, issued on 20.09.1983, and in "A Method of Obtaining Digital Signatures and Public Key Cryptosystems ", Communications of the ACM, Vol. 21, No. 2, 120-26 (Feb. 1978), is taught. In front the description of the embodiment An overview of RSA given.

2.2.1.1. Overview RSA

The public key e_A for the RSA cryptosystem consists of a pair of natural Numbers &lt;e, n&gt;, where n is the product two primes p and q, and e is relatively prime to <st32:df xmlns:st32="http://lighthouseip.com/">φ (n) = Φ (p) φ (q) = (p - 1) (q - 1)</st32:df>&lt;?page 8?&gt;, where φ (n) Euler Totient function. It is preferred that p and q in the form 2p '+ 1 and 2q '+ 1 are present, wherein p 'and q' are primes. The private decryption key is d calculated so that the following applies: <st32:df xmlns:st32="http://lighthouseip.com/">ed ≡ 1 (mod (p - 1) (q - 1)).</st32:df>

A Message m is encrypted by the following statement: <st32:df xmlns:st32="http://lighthouseip.com/">c ≡ m<st32:sup>e</st32:sup>(Mod n);</st32:df> the ciphertext c is as follows decrypted: <st32:df xmlns:st32="http://lighthouseip.com/">m ≡ c<st32:sup>d</st32:sup>(Mod n).</st32:df>

2.2.1.1. An exemplary embodiment, uses the RSA

<figref idrefs="S40">3</figref> shows the messages in an exemplary embodiment are exchanged to the invention, with the RSA cryptosystem asymmetric keys used. Regarding<figref idrefs="S40">3</figref> applies: <ul><li>1. The message exchange begins when Alice <figref>301</figref> a random pair of public Key / private key e_A and D_A generated. e_A includes the numbers &lt;e, n&gt;. Since n is prime is, they can be distinguished from a random number and must be in plain text be sent. To encrypt e, Alice begins with the binary Coding of e and encrypts all bits of which e is composed, with the exception of the least Bits in a symmetric cryptosystem using the password P. Alice sends P (s), n (Msg. <figref>309</figref>) to Bob (see <figref>309</figref>).</li><li>2. Bob, who knows P, decrypts Msg. <figref>309</figref>To P^-1(P (e)) = e to obtain generates a random secret key R and encrypts him in the cryptosystem asymmetric keys with the key E_ATo E_A(R) to be produced. In other embodiments, can e_A(R) are encrypted with P, in the preferred embodiment, RSA used that does not happen. Bob sends e_A(R) (Msg. <figref>315</figref>) to Alice (please refer <figref>315</figref>).</li><li>3. When receiving msg. <figref>315</figref> decrypts Alice they, obtain R. Thereafter derived numbers used R or R as a session key will. At this point, a key validation process are as implemented, for example, the query / response mechanism.</li></ul>

It was a warning about of sending n noted in plain text: It is characterized password P exposed to the risk of cryptanalysis. More specifically, n, if there is an attacker available, be factored, and R would then disclosed and exposed to attack P.

2.2.2. An embodiment the El-Gamal cryptosystem asymmetric key used

the El-Gamal cryptosystem, T. El Gamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete logarithms ", IEEE Transactions on Information Theory, Volume 31, 469-72 (July 1985) is used in an in <figref idrefs="S40">5</figref> shown, not used in the scope of the present invention falling embodiment. In contrast to the embodiment RSA contains, must under certain circumstances an embodiment the El-Gamal cryptosystem contains, not the first, but encrypt the second message.

2.2.2.2. An overview the El-Gamal cryptosystem asymmetric keys

If Bob an encrypted Message (eg the key R) wants to send to Alice, then Bob must this intention notified. When Alice, agreed the encrypted to receive message, Alice and Bob agree then a common Base α and the module β. Alice then examined a random number R_A in the Interval [0, β - 1] of and calculated <img img-content="tx" img-format="tif" he="3" wi="6" file="00200001.tif" /> (Mod β). sends Next Alice <img img-content="tx" img-format="tif" he="3" wi="6" file="00200002.tif" /> (Mod β) in plain text to Bob, which also has a random number R_B in the interval [0, β - 1] selects and the following is calculated: <img img-content="mf" img-format="tif" he="10" wi="86" file="00200003.tif" />&lt;?page 9?&gt;and <st32:df xmlns:st32="http://lighthouseip.com/">c<st32:sub>2</st32:sub> = R · K (mod β)</st32:df>

The encrypted Message that is sent Bob to Alice, consists of the pair &lt;c₁. c₂&gt;.

Alice, the R_A and <img img-content="tx" img-format="tif" he="3" wi="6" file="00200004.tif" /> (Mod β) knows, decrypts the message to restore R by calculating the following: <img img-content="mf" img-format="tif" he="4" wi="86" file="00200005.tif" />and then c₂ by K divided.

2.2.2.3. An embodiment the El-Gamal cryptosystem used

<figref idrefs="S40">5</figref> shows the messages in one embodiment of the invention be replaced, the El-Gamal asymmetric cryptosystem keys used. Before the first message is assumed that Alice and Bob values the base α and agreed the module β have. Regarding<figref idrefs="S40">5</figref> applies. <ul><li>1. Alice <figref>501</figref> generates a random number R_A and calculated <img img-content="tx" img-format="tif" he="3" wi="6" file="00210001.tif" /> (Mod β). Although Alice <img img-content="tx" img-format="tif" he="3" wi="6" file="00210002.tif" /> (Mod β) can encrypt, it is in the preferred embodiment not encrypted. Alice sends <img img-content="mf" img-format="tif" he="4" wi="66" file="00210003.tif" />to Bob <figref>503</figref> (please refer <figref>409</figref>). This message may include other information, such as the identity the transmitter.</li><li>2. If Bob Msg. <figref>409</figref> receives, it generates a random number R_B, so that <img img-content="tx" img-format="tif" he="3" wi="6" file="00210004.tif" /> (Mod β) at random from is selected - the interval [1 0, β]. Bob also generates a random session key R and R is calculated <img img-content="tx" img-format="tif" he="3" wi="9" file="00210005.tif" /> (Mod β). Bob sends<img img-content="mf" img-format="tif" he="4" wi="104" file="00210006.tif" />Alice (see <figref>415</figref>).</li><li>3. Alice, who knows P represents, <img img-content="tx" img-format="tif" he="3" wi="5" file="00210007.tif" /> (Mod β) and thereafter R restores. After receiving Nachr.<figref>415</figref> can a the key validation process be started. Thereafter R, from R derived numbers or of a validation procedure derived number can be used as a session key.</li></ul>

2.5. Security considerations

2.5.1. partition attacks

The major limitation each embodiment is that from encryptions, use the P, may leak any information. In certain cryptosystems this is difficult. For example, the public keys are in RSA always odd. If no special precautions be taken could an attacker half the experimental values ​​P 'rule when P^-1(P (e)) is an even number. At first glance, this is an insubstantial Reduction of key space; but without correction they can impair the safety embodiment to lead. In the present specification, the term "key area" means the scope of possible cryptographic keys. If the key space is large, attempts an unauthorized cryptanalysis specialist, "the key space reduce "or impossible cryptographic keys to eliminate. Through the process of elimination can cryptanalysis specialist with given sufficient clues such as the above- shown, the key space reduce until the actual key reveals is.

one Recall that each Meeting another public key used, which is used by all previously independent. Thus tentatively close decryption, the 'lead to illegal values ​​of e, each Times different values ​​of P 'from. Expressed differently, an attacker who every time a session key negotiated is, the remaining tentative key space into two approximately equal halves split. The key space is thus reduced logarithmically; it rich comparatively few intercepted conversations out to all invalid geratenen P rejected. This attack is called a partition attack.

at certain cryptosystems, a minimum acceptable partition be. Consider the&lt;?page 10?&gt;Case of integers modulo a certain prime p must be encrypted with P. If n bits are used to p to encode, then can tentatively decryption, the values ​​in the range [p, 2ⁿ - 1] revealed be used to the Paßwortraum divide. If p but close to 2ⁿ or even 2ⁿ - 1 is only a few tentative passwords are excluded by each session. Accordingly, p is equal to 2ⁿ - 1 preferred while conversely values ​​of p, the distance from 2ⁿ - 1 away are, are not preferred.

A Another danger is caused by the attempt to create a number with a cryptosystem encrypt the a block size requires greater than the number is. The block size of Cryptosystem is the amount of plaintext that the cryptosystem with a single encryption encode can. The number should be padded with random data to the entire string to the block size of the cryptosystem bring to.

one Note that both Problems can be eliminated in an operation. Assume again, that he integers modulo p encrypted. Assume further that the desired Input encryption block size m bits is, wherein 2^m &gt; p is. It should<img img-content="mf" img-format="tif" he="12" wi="21" file="00230001.tif" />

Of the Q value indicates how many fits p in the encryption block size. one choose reason a random value j ε [0, q - 1] and add to the jp Input value using non-modulo arithmetic (when the input value is less than 2^m - Is qp, to use instead the interval [0, q]). The receiver, which the module knows, the decrypted value restored to the correct area by dividing the input plus jp by β and the rest takes.

3. DO NOT SCOPE OF PROTECTION THE INVENTION FALLING EMBODIMENTS, THE DISTRIBUTION SYSTEMS BY PUBLIC KEYS USE

A embodiment uses the public key distribution system, the as "Diffie-Hellman" is known, and ME Hellman, W. Diffie and Merkle RC in the US Pat. No. 4,200,770, 04.29.1980, and in W. Diffie and ME Hellman, "New Directions in Cryptography ", IEEE Transactions on Info. taught Theory, Vol. 22, No. 6 (Nov. 1976) is.

3.1. Overview of Diffie-Hellman

Diffie-Hellman is not a cryptosystem. However, it is a mechanism for public Generating a secure key (Eg a session key) for a symmetric cryptosystem. Briefly Alice and Bob are looking the random exponent R_A or R_B out. Assuming that they a common base α and a module agree calculated Alice <img img-content="tx" img-format="tif" he="3" wi="6" file="00240001.tif" /> (Mod β) and Bob calculated <img img-content="tx" img-format="tif" he="3" wi="6" file="00240002.tif" /> (Mod β). Each Subscriber sends its calculated size in plain text to the other

Participants. Alice, the R_A and <img img-content="tx" img-format="tif" he="3" wi="5" file="00240003.tif" /> (Mod β) knows, calculated

<img img-content="mf" img-format="tif" he="4" wi="88" file="00240004.tif" />

Similarly calculated Bob, the R_B and <img img-content="tx" img-format="tif" he="3" wi="6" file="00240005.tif" /> (Mod β) knows, <img img-content="mf" img-format="tif" he="4" wi="88" file="00240006.tif" />

The Size R can then as the key used in further communications between Alice and Bob will. An intruder who only<img img-content="tx" img-format="tif" he="3" wi="6" file="00240007.tif" /> (Mod β) and <img img-content="tx" img-format="tif" he="3" wi="6" file="00240008.tif" /> (Mod β) knows, can not perform the same calculation. It should, however, noted be that Diffie Hellman no authentication supplies and therefore compromised by active listened lines can be.

3.2. Embodiment, uses the Diffie-Hellman

<figref idrefs="S40">5</figref> shows the messages at a not within the scope of the present Invention falling embodiment are exchanged to the invention, as described in connection with the Diffie-Hellman distribution system with public keys is used. Regarding<figref idrefs="S40">5</figref> applies: &lt;?page 11?&gt;<ul><li>1. Assuming that Alice <figref>501</figref> and Bob <figref>503</figref> a common base α and a module β agree Alice generates a random number R_A and calculated <img img-content="tx" img-format="tif" he="3" wi="6" file="00250001.tif" /> (Mod β). <img img-content="tx" img-format="tif" he="3" wi="6" file="00250002.tif" /> (Mod β) is in a cryptosystem symmetric key with the password P as a key encoded and Alice sends <img img-content="mf" img-format="tif" he="10" wi="81" file="00250003.tif" />to Bob (see <figref>509</figref>). Note that, when R_A is random, <img img-content="tx" img-format="tif" he="3" wi="6" file="00250004.tif" /> (Mod β) is random and an out-P no useful Information obtained.</li><li>2. Similar Bob generates a random number R_B and sends <img img-content="mf" img-format="tif" he="10" wi="80" file="00250005.tif" />Alice (see <figref>515</figref>). At this point both Alice Bob know <img img-content="tx" img-format="tif" he="3" wi="6" file="00250006.tif" /> (Mod β) and <img img-content="tx" img-format="tif" he="3" wi="6" file="00250007.tif" /> (Mod β) and can therefore key a session as described in section 3.1. Calculate shown. In addition, one of the key validation process be started as soon as a common by both Alice and Bob Value is calculated.</li></ul>

3.3. Bilateral compared to unilateral encryption

In usually are not both messages of the Diffie-Hellman distribution system encrypted with public keys. A unilateral encryption, encryption a portion of at least one of the messages of the Diffie-Hellman distribution system with public keys, ensures confidentiality and authentication. Therefore it on with respect <figref idrefs="S40">5</figref> possible, the encryption of one of the messages in <figref idrefs="S40">5</figref> skip, but not both. For example, msgs.<figref>509</figref> by the following will be replaced: <img img-content="mf" img-format="tif" he="4" wi="23" file="00260001.tif" />

As Alternatively Msg. <figref>515</figref> be replaced by the following: <img img-content="mf" img-format="tif" he="4" wi="23" file="00260002.tif" />

That the unilateral encoding the security of the system preserves, means that one pair of encryptions and decryption may be omitted. Since the encryption and decryption considerable may require computational resources and time, these resources can be omitted and Time can be saved.

3.4. Choose from α and β

The Values ​​of α and β can differ chosen are, each choice a compromise between cost and safety represents. Although there are several options for the module there are large Primwerte of β safer. also it is desirable to that α is a primitive Root of the field GF (β) is. If β so chosen is that <st32:df xmlns:st32="http://lighthouseip.com/">β = 2p + 1</st32:df>for a certain prime number p is true, then there are (β - 1) / 2 = p such values; therefore they are easy to find. Assume those restrictions in the following discussion to.

It is for Alice and Bob somewhat problematic, to agree on common values ​​for α and β, without an attacker to reveal information. P (β) can not be transferred be because the Test a random number to the primary property is too easy. At a embodiment are set α and β and published. This embodiment has the advantage that the Risk of leakage of information or partition attacks does not exist. The disadvantage is that the implementation less is flexible because all participants agree on those values have to. Publishing has of β the further disadvantage that in order to Maintaining security β must be large, thereby the exponentiation operations are costly.

It however possible, a certain compromise on the length of the module. There in the embodiment the password P for encryption About such values ​​is used, it is with the exception of all possi&lt;?page 12?&gt;chen geratenen P is not possible, to attempt a discrete logarithm. The aim is then is to choose a size for β, the sufficient for rate attacks are far too costly. 200 bit, is what estimated that discrete Logarithmuslösungen and after the setting up of tables take several minutes may be sufficient.

By other considerations are, however, suggested larger modules. If the password the user is compromised, the attacker are recorded Exponential available; these allow for a solution read old conversations. If a large selected modulus value is, would all such conversations stay safe.

The size requirements for β are from derived Desiring calculations of discrete logarithms in the GF (β) box to prevent. require the currently best algorithms for such calculations a big Amount of pre-calculations. If each time using a different β is, an attacker can not build tables in advance; thus , a much smaller and therefore cheaper module used will. In the preferred embodiment therefore produces Alice random values ​​of β and α and transmits them in the clear during the first exchanges. It is only a small security risk if an attacker knows these values; the only problem would be cut-and-paste attacks. Even This risk is minimal if Bob performs certain checks to is releasable before slightly choices to protect: that actually β prim is that it big enough (and therefore not addressed by pre-calculating tables may be) that β - 1 least a big has prime factor and that α is a primitive Root of GF (β) is. The last two conditions are interrelated; the factorization of β - 1 is necessary to know be to α to validate. If β in kp the form + 1 exists, where p is a prime number and k very a small integer, both conditions are satisfied.

So far was nothing of the choice of α said. However, when a suitable value of β is chosen, α is as a selected primitive root of β. It is no reason to examine the integers from 2 to; the Density of primitive roots guarantees that one relatively quickly place.

4. The cryptosystems

4.1. Selection of a cryptosystem symmetric key

The encoding symmetric key is in various embodiments used three times: To the first exchange of asymmetric keys to encrypt, in order to change queries and responses, and the following application session to protect. In general, on all three points the same cryptosystem symmetric key be used.

at the first exchange (eg Msg. <figref>109</figref> and Msg. <figref>115</figref>) there are strong restrictions the plaintext. The messages should advantageously not Another form of an attached use data representation.

at all preferred embodiments should the original Plaintext message contain non-random padding to achieve the encryption block size, and also any form of error detection checksum. Protection against communication errors is usually provided by protocols of lower layers. Although a cipher block chaining or a similar Methods may be used, to a plurality of blocks bind and hinder cryptanalytic attacks, are those Mechanisms generally not important because the transmitted bits are random be and therefore not been tampered with by an attacker benefit can. The challenge / response mechanism provides the necessary defense against such manipulation of messages.

at one embodiment can the encryption algorithm just an operation, such as the bit-wise Boolean XOR the password with the public key be.

Similarly to the Key validation messages are not generally protected by a strong cipher system. However, it was implicitly assumed that it is not feasible for an attacker is useful perform cut-and-paste operations on encrypted messages. If is said, for example, that Alice R (query_A, query_B) sends to Bob and that Bob with R (query_AReply), one could conclude that the attacker R (query_A) Cut out from the first message and it could be repeated in the second easily. In all preferred embodiments this should, of course, be advantageously prevented. If it in the concrete used Cryptosystem is necessary should therefore standardmäßi&lt;?page 13?&gt;ge process, such as, for example, uses cipher block chaining. The Cipher block chaining should prevent such attacks on "snip and echo" or "Cut and Paste". Alternatively, could Alice and Bob R use to different partial key R_A and R_B deduce that in only one Direction are used. Other alternatives include the use the message typification or adding message authentication codes; these can However introduce redundancy, which is undesirable in view of cryptanalytic attack. In such cases can in the section 2.1.2. preferable mentioned one-way functions be.

Finally, it must the use of R in the following login session no useful information about R reveal. If the systems will kryptoanalysiert and when R restored is, the attacker a password-rate attack on the exchange of messages can then initiate. Since this protocol to protect any sessions is applicable between participants, it is best to carefully and examines the concrete symmetric system under the assumption that the Opponents attacks with chosen may initiate ciphertext against the meeting. is in doubt embodiment preferably with separate data key replacement key.

4.2. Selecting a distribution system with public keys

in the Principle, any distribution system with public keys be used, including the puzzles Merkle, RC Merkle, "Secure Communications Over Insecure Channels, "Communications of the ACM, Volume 21, 294-99 (april 1978). In practice, certain systems are made practical reasons locked out. For example, could a system that many large Primes used be impractical in certain applications. RSA uses at least two such primes; dynamic key generation may degrade with certain hardware systems as too complex and therefore prove too costly.

On second aspect is whether the public key of a certain system randomly as a appearing bit string can be encoded or not. It has already been shown that this RSA can be a problem.

It The temptation auszuklügeln the problem by instead of Initial value of the random number generator is transferred, with the generated public key is. Unfortunately, this may not be possible in many cases. apart of the costs (both sides would have the time consuming process of generating the key carry out) leads the random Initial value both to the public as well as the private key. And this could turn validate an attacker tentatively password by the session key retrieves.

The opportunity to transfer the initial value of a random number generator, works at an exponential key exchange. Since the primary module anyway publicly may be, must not be hidden. Unfortunately, this requires a possibility that both Users perform the step of generating large prime numbers, although they thereby respect save the required module size. It may be appropriate to consider the compromise again when very fast solutions the problem of the discrete logarithm found.

5. The device for execution the message exchange

<figref idrefs="S41">6</figref> shows an embodiment a device that the message exchange described in Section 2 perform can. This embodiment can be easily modified by those of ordinary skill to a any embodiment carry out the invention.

Alice <figref>601</figref> and bob <figref>603</figref> Two computers or other standard processing and communication stations or devices that share a secret P, the like in a register or <figref>600</figref> saved can be, and want a confidential and authenticated communication channel <figref>629</figref> manufacture. The secret P is in a register or the like, both in Saved Alice and Bob in. Alice comprises a transmitter<figref>602</figref>. a receiver <figref>612</figref>. a key validation device <figref>619</figref> and a session communication unit <figref>625</figref>, The transmitter<figref>602</figref> accepts as input the secret to P. The transmitter<figref>602</figref> contains a generator <figref>605</figref> for asymmetric keys, of a public key and a private key generated. The public key becomes a scrambler <figref>607</figref> for symmetric Key forwarded. The encryptor <figref>607</figref> for symmetric key takes as input the secret P and encrypts the public key or a portion thereof with the secret key P is the &lt;?page 14?&gt;key to Forming an introductory message. The initiation message is of the scrambler <figref>607</figref> for symmetric key to a communication channel <figref>609</figref> passed and there to a receiver <figref>610</figref> in Bob transferred.

Of the receiver <figref>610</figref> includes a decrypter <figref>611</figref> for symmetric Key. The descrambler <figref>611</figref> for symmetric key accepts as input the initiation message and the secret P and decrypts the initiation message to restore the public key. The public key is to the transmitter <figref>620</figref> forwarded. The transmitter<figref>620</figref> includes a encryptor <figref>616</figref> symmetric key, a encryptor <figref>617</figref> for asymmetric key and a generator <figref>618</figref> symmetric key. Of the generator <figref>618</figref> for symmetric keys generates a random symmetric key to the scrambler <figref>617</figref> for asymmetric key is forwarded. The encryptor<figref>617</figref> for asymmetric key takes as input the public key from the receiver <figref>610</figref> at and encrypts the symmetric key with the public Key, an encrypted key to form. encrypted key is supplied to the encryptor <figref>616</figref> for symmetric key weiterge passes which accepts as input the secret P, and there is the encrypted key further encrypted with the secret P to a response message to form. The response message is transmitted from the encryptor<figref>616</figref> for symmetric key to a communication channel <figref>615</figref> passed and there to a receiver <figref>612</figref> in Alice transferred.

Of the receiver <figref>612</figref> includes a decrypter <figref>614</figref> for symmetric key and a descrambler <figref>613</figref> for asymmetric Key. The descrambler <figref>614</figref> for symmetric key accepts as input the secret P and the response message, decrypts the Reply message to the encrypted key restore, and forward it to the descrambler <figref>613</figref> for asymmetric Key on. The descrambler <figref>613</figref> for asymmetric key also accepts as input the private key of the generator <figref>605</figref> for asymmetric key was passed, and used it to decode the encrypted key, to the symmetric key restore. The symmetric key is from the descrambler<figref>613</figref> for asymmetric key to the key validation device <figref>619</figref> forwarded. Analog passes the key generator <figref>618</figref> in Bob the symmetric key to the key validation device <figref>623</figref> from Bob continued. The key generator<figref>619</figref> from Alice and the key generator <figref>623</figref> from Bob communicate a communication channel <figref>621</figref> with each other to the symmetric key validate. The purpose of validating the key is the fact that no unauthorized eavesdropper who may the mystery P has discovered either for Alice or Bob can spend.

After the validation passes, the key validation device <figref>619</figref> from Alice the symmetric key to the session communication unit <figref>625</figref> further that the key in further communications with Bob over the communication channel <figref>629</figref> used. Although the communication channels <figref>609</figref>. <figref>615</figref>. <figref>621</figref> and <figref>629</figref> the Simplicity are shown as separate channels sake, of course, that in practice, two or more of these channels, the same physical channel could be, the well-known according Principles and practices can be suitably multiplexed. Analogous forwards the key validation device <figref>623</figref> from Bob the symmetric key to a session communication unit <figref>627</figref> Next, the the key in further communications with Alice over the communication channel <figref>629</figref> used.

6. applications

embodiments the invention can Secure public Telephone use. If someone secure public wants to use telephones, are usually some key information provided. Conventional solutions require that the Caller a physical key owns. embodiments the invention permits the use of short, input via keypad password, but uses a much longer session key for the call.

embodiments the present invention may be used with cellular telephones. A problem in the Cellular industry has so far been of fraud; embodiments the can then protect against fraud (And the confidentiality of the call to make sure) by a telephone useless, if no PIN or other key input will. Since the PIN or other key is not in the telephone is stored, it is not possible, a retrieve from a stolen unit.

embodiments the invention provide further a replacement for the Interlock protocol by Rivest and Shamir (RL Rivest and A. Shamir, "How to Expose to Eavesdropper " Communications of the ACM, Vol. 27, No. 4, 393-95 (1984)).