Device for and method of cryptography that allows third party access

A device for transmitting an encrypted message and an access field, where a sender and a receiver agree on a session key, comprising:

• a) a first means for performing a commutative one-way function, having a first input for receiving an element g of a Galois Field, having a second input for receiving the session key, and having an output;
• b) a second means for performing a commutative one-way function, having a first input for receiving a public device unique key Y.sub.i, having a second input for receiving the session key, and having an output;
• c) a third means for performing a commutative one-way function, having a first input for receiving a public family key Y.sub.f, having a second input for receiving the session key, and having an output;
• d) a first symmetric-key encryptor, having a plaintext input for receiving the session key, having a key input connected to the output of said second commutative one-way function means, and having a ciphertext output;
• e) a combiner, having a first input for receiving an identification number, having a second input connected to the ciphertext output of said first symmetric-key encryptor, and having an output;
• f) a second symmetric-key encryptor, having a plaintext input connected to the output of said combiner, having a key input connected to the output of said third commutative one-way function means, and having a ciphertext output;
• g) a third symmetric-key encryptor, having a plaintext input for receiving the sender's plaintext message, having a key input for receiving the session key, and having a ciphertext output;
• and
• h) a shift-register for receiving and transmitting the output of said first commutative one-way function means, the ciphertext output of said second symmetric-key encryptor, and the ciphertext output of said third symmetric-key encryptor.

A method of recovering a plaintext message from a ciphertext message concatenated to an access field, where a sender and a receiver agree on a session key, and where the access field comprises g.sup.sk, where g is an element in a Galois Field and sk is the session key, and an encrypted version of an identification number combined with an encrypted version of the session key, comprising the steps of:

• (a) forming g.sup.sk ;
• (b) comparing the result of step (a) to g.sup.sk received from the sender, processing is halted if the result of step (a) does not match the g.sup.sk received from the sender;
• (c) forming a first temporary key;
• (d) encrypting the session key using the first temporary key;
• (e) forming a second temporary key;
• (f) decrypting the encrypted version of an identification number combined with an encrypted version of the session key received from the sender using the second temporary key;
• (g) extracting the encrypted session key from the result of step (f);
• (h) comparing the result of step (d) to the result of step (g), processing is halted if the result of step (d) does not match the result of step (g);
• and
• (i) decrypting the ciphertext received from the sender using the session key in order to recover the plaintext message.

A device, used by a receiver, for decrypting a message sent from a sender to the receiver, where the message comprises the sender's ciphertext message concatenated to an access field, where the sender and the receiver agree on a session key, and where the access field comprises g.sup.sk, where g is an element in a Galois Field and sk is the session key, and an encrypted version of an identification number combined with an encrypted version of the session key, comprising:

• a) a shift-register, having an input for receiving the message sent by the sender, having a first output for transmitting g.sup.sk received from the sender, having a second output for transmitting an encrypted version of an identification number combined with an encrypted version of the session key received from the sender, and having a third output for transmitting the ciphertext message received from the sender;
• b) a first means for performing a commutative one-way function, having a first input for receiving an element g of a Galois Field, having a second input for receiving the session key, and having an output;
• c) a first comparator, having a first input connected to the first output of said shift-register, having a second input connected to the output of said first commutative one-way function means, and having an output that indicates whether or not the first and second input to the comparator match;
• d) a second means for performing a commutative one-way function, having a first input for receiving a public device unique key Y.sub.i, having a second input for receiving the session key, and having an output;
• e) a third means for performing a commutative one-way function, having a first input for receiving a public family key Y.sub.f, having a second input for receiving the session key, and having an output;
• f) a symmetric-key encryptor, having a plaintext input for receiving the session key, having a key input connected to the output of said second commutative one-way function means, and having a ciphertext output;
• g) a first symmetric-key decryptor, having a ciphertext input connected to the second output of said shift-register, having a key input connected to the output of said third commutative one-way function means, and having a plaintext output;
• h) an extractor, having an input connected to the plaintext output of said first symmetric-key decryptor, and having an output for transmitting the sender's encrypted session key;
• i) a second comparator, having a first input connected to the ciphertext output of said symmetric-key encryptor, having a second input connected to the output of said extractor, and having an output for indicating whether or not the sender's encrypted session key matches the receiver's encrypted session key;
• and
• g) a second symmetric-key decryptor, having a ciphertext input connected to the third output of said shift-register, having a key input for receiving the session key, and having a plaintext output at which the sender's plaintext message appears.

A method of recovering a plaintext message by a third party from a message sent from a sender to a receiver, where the message comprises the sender's ciphertext message concatenated to an access field, where the sender and the receiver agree on a session key, and where the access field comprises g.sup.sk, where g is an element in a Galois Field and sk is the session key, and an encrypted version of an identification number combined with an encrypted version of the session key, comprising the steps of:

• (a) forming a first temporary key;
• (b) decrypting the encrypted version of an identification number combined with an encrypted version of the session key intercepted from the sender using the first temporary key;
• (c) separating the result of step (b) into bits that are based on the sender's identification number and bits that are based the sender's encrypted session key;
• (d) using the bits based on the sender's identification number to recover bits that mathematically relate the sender's g.sup.sk to the sender's first temporary key;
• (e) forming a second temporary key using the result of step (d) and the g.sup.sk intercepted from the sender;
• (f) decrypting the bits that are based on the sender's encrypted session key using the second temporary key to recover the sender's session key;
• and
• (g) decrypting the sender's ciphertext message using the sender's session key to recover the sender's plaintext message.

A device, used by a third party to a message sent from a sender to a receiver, for intercepting the message and recovering the sender's plaintext message, where the message comprises the sender's ciphertext message concatenated to an access field, where the sender and the receiver agree on a session key, and where the access field comprises g.sup.sk, where g is an element in a Galois Field and sk is the session key, and an encrypted version of an identification number combined with an encrypted version of the session key, comprising:

• a) a shift-register, having an input for intercepting the message sent by the sender to the receiver, having a first output for transmitting g.sup.sk intercepted from the sender, having a second output for transmitting an encrypted version of an identification number combined with an encrypted version of the session key intercepted from the sender, and having a third output for transmitting the ciphertext message intercepted from the sender;
• b) a first means for performing a commutative one-way function, having a first input for receiving a secret family key x.sub.f that corresponds to the sender's public family key Y.sub.f, having a second input connected to the first output of said shift-register, and having an output;
• c) a first symmetric-key decryptor, having a ciphertext input connected to the second output of said shift-register, having a key input connected to the output of said first commutative one-way function means, and having a plaintext output;
• d) an extractor, having an input connected to the plaintext output of said first symmetric-key decryptor, and having a first output for transmitting bits based on the sender's identification number, and having a second output for transmitting bits based on the sender's encrypted session key;
• e) a memory stored with data that mathematically relates bits based on the sender's identification number to the sender's public device unique key Y.sub.i, having an address input connected to the first output of said extractor, and having an output;
• f) a second means for performing a commutative one-way function, having a first input connected to the first output of said shift-register, having a second input connected to the output of said memory, and having an output;
• g) a second symmetric-key decryptor, having a ciphertext input connected to the second output of said extractor, having a key input connected to the output of said second commutative one-way function means, and having a plaintext output;
• and
• h) a third symmetric-key decryptor, having a ciphertext input connected to the third output of said shift-register, having a key input connected to the plaintext output of said second symmetric-key decryptor, and having a plaintext output at which the sender's plaintext message appears.

A method of generating and using an access field, where a sender and a receiver agree on a session key, comprising the steps of;

• (a) generating, randomly, an initialization vector;
• (b) forming an exponent (m) using the session key and the initialization vector;
• (c) forming U=g.sup.m mod p, where g is an element of order q in GF(p), where p is a prime number, and where p is a prime divisor of (p-1);
• (d) forming a temporary device unique key;
• (e) encrypting the session key with the temporary device unique key;
• (f) forming a temporary family key;
• (g) encrypting an identifier of the sender, a device unique public key of the sender, a signature of the device unique public key of the sender, and the encrypted session key using the temporary family key;
• (h) concatenating a string of bits to the initialization vector;
• (i) encrypting the session key using the result of step (h);
• (j) encrypting a plaintext message using the result of step (i);
• (k) concatenating a tag, the initialization vector, U, the result of step (g), and the result of step (j);
• and
• (1) transmitting the result of step (k) to the recipient.

A device for transmitting an encrypted message and an access field, where a sender and a receiver agree on a session key, comprising:

• a) a means for uniquely mapping the session key and an initialization vector into an exponent m, having a first input for receiving the session key, having a second input for receiving the initialization vector, and having an output for transmitting the exponent m;
• b) a first means for exponentiation, having a first input for receiving the exponent m from the output of the mapping means, having a second input for receiving a device unique public-key (Y.sub.i), and having an output for transmitting ((Y.sub.i **m) mod p), where p is a prime number;
• c) a second means for exponentiation, having a first input for receiving the exponent m from the output of the mapping means, having a second input for receiving a public family key (Y.sub.f), and having an output for transmitting ((Y.sub.f **m) mod p);
• d) a third means for exponentiation, having a first input for receiving the exponent m from the output of the mapping means, having a second input for receiving an element g of order q in GF(p), and having an output for transmitting U=(g.sup.m mod p), where U forms a portion of the access field;
• e) a first means for hashing, having an input for receiving ((Y.sub.i **m)mod p) from the first exponentiation means, and having an output for transmitting a temporary device unique key (t=h((Y.sub.i **m) mod p)), where the first hashing means uniquely maps a binary input string into a binary output string;
• f) a second means for hashing, having an input for receiving ((Y.sub.f **m) mod p) from the second exponentiation means, and having an output for transmitting a temporary family key (w=h((Y.sub.f **m) mod p)), where the second hashing means uniquely maps a binary input string into a binary output string;
• g) a first means for encryption, having a first input for receiving the session key as plaintext, having a second input for receiving the output of the first hashing means (t) as the key, and having an output for transmitting an encrypted version of the session key as ciphertext;
• h) a means for receiving inputs of various bit lengths, concatenating the inputs, and outputting portions of the concatenated inputs in fixed block-lengths until all of the inputs are put out, having a first input for receiving a device identification number of the sender, a second input for receiving a digital signature of the sender, a third input for receiving a string of binary bits as a pad, a fourth input for receiving the device unique public key of the sender, a fifth input for receiving the output of the first encryption means, and an output for transmitting fixed block-length portions of the inputs;
• i) a second means for encryption, having a first input connected to the output of said multiplexer for receiving plaintext, having a second input connected to the output of said second hashing means for receiving key, having a third input for receiving the initialization vector, and having an output for transmitting an encrypted version of the output of the means for receiving inputs of various bit lengths as ciphertext;
• j) a means for concatenation, having a first input for receiving the initialization vector, a second input for receiving a string of binary bits, and an output for transmitting a binary string (z) that is the concatenation of the initialization vector and the string of binary bits;
• k) a third means for encryption, having a first input for receiving the session key as plaintext, having a second input connected to the output of said concatenation means for receiving key, and having an output for transmitting an encrypted version of the session key as ciphertext;
• l) a fourth means for encryption, having a first input for receiving the sender's plaintext message as plaintext, having a second input connected to the output of said third encryption means for receiving key, having a third input for receiving the initialization vector, and having an output for transmitting an encrypted version of the plaintext as ciphertext;
• and
• m) a shift-register, having a first input for receiving the initialization vector, a second input connected to the output of the third exponentiation means, a third input connected to the output of said second encryption means, a fourth input for receiving a string of binary bits, a fifth input connected to the output of said fourth encryption means, and an output for transmitting the ciphertext message concatenated to the access field.

A method of recovering a plaintext message from an encrypted message concatenated to an access field, where a sender and a receiver agree on a session key, and where the access field comprises an initialization vector of the sender, a number U formed by the sender, and a string of bits representing an encrypted form of an identifier of the sender, a device unique public key of the sender, a signature of the sender, and an encrypted version of the session key, comprising the steps of:

• (a) receiving a ciphertext message concatenated to an access field;
• (b) recovering from the access field the initialization vector, the number U, and the encrypted form of the identifier of the sender, the device unique public key of the sender, the signature of the sender, and the encrypted version of the session key;
• (c) forming an exponent (m);
• (d) forming U=g.sup.m mod p, where g is an element of order q in GF (p), where p is a prime number, and where q is a prime divisor of (p-1);
• (e) comparing U received in step (b) to U formed in step (d), proceeding with the next step if U received matches U formed, otherwise, stopping;
• (f) forming a temporary family key;
• (g) recovering the device unique public key of the sender, the signature of the sender, and the encrypted version of the session key from the portion of the access field that contains the encrypted form of the identifier of the sender, the device unique public key of the sender, the signature of the sender, and the encrypted version of the session key by decrypting this portion of the access field using the result of step (f);
• (h) verifying the signature of the sender, proceeding to the next step if the signature is verified, otherwise, stopping;
• (i) forming a temporary device unique key;
• (j) recovering the session key from the encrypted version of the session key recovered in step (g) by decrypting the encrypted session key using the result of step (i);
• (k) comparing the session key recovered in step (j) with the session key known by the recipient, proceeding with the next step if these two session keys match, otherwise, stopping;
• (l) concatenating a string of bits to the initialization vector;
• (m) encrypting the session key using the result of step (1) as key;
• and
• (n) recovering the plaintext message from the ciphertext message received from the sender by decrypting the ciphertext using the result of step (m) as key.

A device, used by a receiver, for decrypting an encrypted message concatenated to an access field, where a sender and the receiver agree on a session key, comprising:

• a) a shift-register, having an input for receiving the encrypted message concatenated to an access field, having a first output for transmitting an initialization vector used by the sender, having a second output for transmitting ((g.sup.m)mod p) generated by the sender;
• having a third output for transmitting an encrypted version of an identification number of the sender, a device unique public key of the sender, a digital signature of the sender, an encrypted version of the session key used by the sender, and a string of binary bits;
• having a fourth output for transmitting a string of bits received from the sender, and having a fifth output for transmitting a ciphertext message sent by the sender;
• b) a means for uniquely mapping the session key and the initialization vector into an exponent m, having a first input for receiving the session key, having a second input connected to the first output of the shift-register for receiving the initialization vector, and having an output for transmitting the exponent m;
• c) a first means for exponentiation, having a first input connected to the output of said mapping means, having a second input for receiving a public family key (Y.sub.f), and having an output for transmitting ((Y.sub.f **m)mod p), where p is a prime number;
• d) a second means for exponentiation, having a first input connected to the output of said mapping means, having a second input for receiving an element g of order q in GF(p), and having an output for transmitting (g.sup.m mod p);
• e) a first comparator, having a first input connected to the second output of said shift-register, having a second input connected to the output of said second exponentiation means, and having an output that indicates whether or not the two inputs to said first comparator match, processing of the message received from the sender stops if the two inputs to the first comparator do not match;
• f) a first means for hashing, having an input for receiving ((Y.sub.f **m)mod p) from the first exponentiation means, and having an output for transmitting a temporary family key (w=h((Y.sub.f **m) mod p)), where the first hashing means uniquely maps a binary input string into a binary output string;
• g) a first means for decryption, having a first input connected to the third output of said shift-register for receiving ciphertext, having a second input connected to the output of said first hashing means for receiving key, having a third input for receiving the initialization vector, and having an output for transmitting a decrypted version of the first input;
• h) a means for storing data, having an input connected to the output of said first decryption means, having a first output for transmitting the first decrypted portion of V, having a second output for transmitting the second decrypted portion of V, having a third output for transmitting the third decrypted portion of V, and having a fourth output for transmitting the fourth decrypted portion of V;
• i) a means for verifying a digital signature, having a first input connected to the fourth output of said shift-register, having a second input connected to the first output of said storage means, having a third input connected to the second output of said storage means, having a fourth input connected to the third output of said storage means, having a fifth input for receiving the public family key (Y.sub.f), and having an output that indicates whether or not the digital signature of the sender has been verified, processing of the message received from the sender stops if the sender's digital signature is not verified;
• j) a third means for exponentiation, having a first input connected to the output of said mapping means, having a second input connected to the second output of said storage means, and having an output for transmitting ((Y.sub.i **m)mod p), where p is a prime number;
• k) a second means for hashing, having an input connected to the output of said third exponentiation means, and having an output for transmitting a temporary device unique key (t=h((Y.sub.i **m) mod p)), where the second hashing means uniquely maps a binary input string into a binary output string;
• l) a second means for decryption, having a first input connected to the fourth output of said storage device as ciphertext, having a second input connected to the output of said second hashing means for receiving key, and having an output for transmitting a decrypted version of the session key;
• m) a second comparator, having a first input connected to the output of said second decryption means, having a second input for receiving the session key used by the sender, and having an output that indicates whether or not the two session keys match, processing of the message received from the sender stops if the two session keys do not match;
• n) a means for concatenation, having a first input connected to the first output of said shift-register, having a second input for receiving a string of binary bits, and having an output for transmitting the concatenation of the first input and the second input;
• o) a means for encryption, having a first input for receiving the session key known to the recipient as plaintext, having a second input for receiving the output of the concatenation means as key, and having an output for transmitting an encrypted version of the session key;
• and
• p) a third means for decryption, having a first input connected to the fifth output of said shift-register for receiving ciphertext, having a second input connected to the output of said encryption means for receiving key, having a third input for receiving the initialization vector, and having an output for transmitting the plaintext of the ciphertext message intercepted.

A method of intercepting and recovering a plaintext message by a third party from an encrypted message concatenated to an access field sent from a sender to a receiver, where the access field comprises an initialization vector of the sender, a number U formed by the sender, and a string of bits representing an encrypted form of an identifier of the sender, a device unique public key of the sender, a signature of the sender, and an encrypted version of a session key, comprising the steps of:

• (a) intercepting the encrypted message concatenated to the access field, where the encrypted message concatenated to the access field was sent from the sender to the recipient;
• (b) recovering the initialization vector, the number U, and the encrypted identifier of the sender, the device unique public key of the sender, the signature of the sender, and the encrypted session key from the access field;
• (c) forming a temporary family key;
• (d) recovering the identifier of the sender, the device unique public key of the sender, the signature of the sender, and the encrypted session key by decrypting the portion of the access field that contains the identifier of the sender, the device unique public key of the sender, the signature of the sender, and the encrypted session key using the result of step (c);
• (e) requesting the secret unique key held by each escrow agent based on the identifier of the sender recovered in step (d);
• (f) combining the secret unique keys received as a result of step (e);
• (g) forming a temporary device unique key;
• (h) recovering the session key by decrypting the encrypted session key using the result of step (g);
• (i) concatenating a string of bits to the initialization vector;
• (j) encrypting the session key using the result of step (i);
• and
• (k) recovering the plaintext message by decrypting the ciphertext using the result of step (j).

A device, used by a third party, for decrypting an intercepted encrypted message concatenated to an access field which was sent by a sender to a receiver, comprising:

• a) a shift-register, having an input for receiving the intercepted message, having a first output for transmitting an initialization vector used by the sender, having a second output for transmitting U=((g.sup.m) mod p) generated by the sender;
• having a third output for transmitting an encrypted version of an identification number of the sender, a device unique public key of the sender, a digital signature of the sender, an encrypted version of the session key used by the sender, and a string of binary bits;
• having a fourth output for transmitting a string of binary bits transmitted by the sender, and having a fifth output for transmitting a ciphertext message sent by the sender to the recipient;
• b) a first means for exponentiation, having a first input for receiving the second output of the shift-register, having a second input for receiving a secret family key (x.sub.f), and having an output for transmitting ((U**x.sub.f)mod p), where p is prime number;
• c) a first means for hashing, having an input connected to the output of said first exponentiation means, and having an output for transmitting a temporary family key (w=h((U**x.sub.f) mod p)), where the first hashing means uniquely maps a binary input string into a binary output string;
• d) a first means for decryption, having a first input connected to the third output of said shift-register for receiving ciphertext, having a second input connected to the output of said first hashing means for receiving key, having a third input for receiving the initialization vector, and having an output for transmitting a decrypted version of the first input;
• e) a means for storing data, having an input connected to the output of said first decryption means, having a first output for transmitting the identification number of the sender, having a second output for transmitting the device unique public key of the sender, having a third output for transmitting the digital signature of the sender, and having a fourth output for transmitting the encrypted version of the session key used by the sender;
• f) a means for verifying a digital signature, having a first input for receiving the public family key (Y.sub.f), having a second input connected to the fourth output of said shift-register, having a third input connected to the first output of said storage means, having a fourth input connected to the second output of said storage means, having a fifth input connected to the third output of storage means, and having an output that indicates whether or not the digital signature of the sender has been verified, processing of the message intercepted from the sender stops if the sender's digital signature is not verified;
• g) a means for adding, having a first input for receiving one part of an escrowed key held by an escrow agent, having a second input for receiving a second part of an escrowed key held by a second escrow agent, and having an output for transmitting ((x.sub.i =x.sub.i1 +x.sub.i2) mod q), where q is a prime divisor of (p-1), and where p is a prime number;
• h) a second means for exponentiation, having a first input connected to the second output of said shift-register, having a second input connected to the output of said adding means, and having an output for transmitting ((U**x.sub.i) mod p);
• i) a second means for hashing, having an input for receiving the output of said second exponentiation means, and having an output for transmitting a temporary device unique key (t=h((U**x.sub.i) mod p)), where the second hashing means uniquely maps a binary input string into a binary output string;
• j) a second means for decryption, having a first input connected to the fourth output of said storage means for receiving ciphertext, having a second input connected to the output of said second hashing means for receiving key, and having an output for transmitting a decrypted version of the session key;
• k) a means for concatenation, having a first input for receiving the first output of said shift-register, having a second input for receiving a string of binary bits, and having an output for transmitting the result of concatenating the first input and the second input to said concatenation means;
• l) a means for encryption, having a first input connected to the output of said second decryption means for receiving plaintext, having a second input connected to the output of said concatenation means for receiving key, and having an output for transmitting an encrypted version of the session key;
• and
• m) a third means for decryption, having a first input connected to the fifth output of said shift-register for receiving ciphertext, having a second input connected to the output of said encryption means for receiving key, having a third input for receiving the initialization vector, and having an output for transmitting the plaintext of the ciphertext intercepted.