nsa5631961.htm
89b68b96e250572c7d5f81209a1ff805fb9649418de2d949ecce66d81f8400fd<HTML>
<HEAD>
<TITLE>NSA Patent 5,631,961 - 1997</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<P>
29 May 1999<BR>
Source: US Patent Office Online:
<A HREF="http://www.uspto.gov/">http://www.uspto.gov/</A>
<P>
Search "National Security Agency" though none of the patents disclose the
full name.
<P>
For related images see IBM's patent server:
<A HREF="http://www.patents.ibm.com/ibm.html">http://www.patents.ibm.com/ibm.html</A>
<P>
<HR>
<TABLE WIDTH="100%">
<TR>
<TD ALIGN="LEFT" WIDTH="50%"><B>United States Patent </B></TD>
<TD ALIGN="RIGHT" WIDTH="50%"><B> 5,631,961 </B></TD>
</TR>
<TR>
<TD ALIGN="LEFT" WIDTH="50%"><B> Mills , et al.</B></TD>
<TD ALIGN="RIGHT" WIDTH="50%"><B>May 20, 1997 </B></TD>
</TR>
</TABLE>
<P>
<HR>
<FONT size="+1"> Device for and method of cryptography that allows third
party access </FONT><BR>
<BR>
<CENTER>
<B>Abstract</B>
</CENTER>
<P>
A device for and method of transmitting an encrypted message and an access
field from a sender to a receiver, where a third party may intercept and
process the transmission. The sender and receiver agree on a session key.
The sender raises an element of a Galois Field to the session key; forms
a temporary device unique key; encrypts the session key with the temporary
device unique key; forms a temporary family key; encrypts an identifier of
the sender and the encrypted session key using the temporary family key;
encrypts a plaintext message using the session key; forms the access field
by concatenating the element of a Galois Field raised to the session key
to the encrypted version of the sender's identifier and the sender's encrypted
session key; concatenates the ciphertext to the access field; and transmits
the access field and the ciphertext to the receiver. The receiver may recover
the plaintext from the sender's transmission. The third party may partially
process the transmission to find the identity of the sender. The third party
may then request an escrowed key that would allow the third party to recover
the plaintext of the sender's message.
<P>
<HR>
<TABLE WIDTH="100%">
<TR>
<TD VALIGN="TOP" ALIGN="LEFT" WIDTH="10%">Inventors:</TD>
<TD ALIGN="LEFT" WIDTH="90%"><B>Mills; Robert A.</B> (Gambrills, MD);
<B>Unkenholz; Mark R.</B> (Eldersburg, MD); <B>Wilson; Mark W.</B> (Columbia,
MD); <B>Burroughs; John E.</B> (Annapolis, MD)</TD>
</TR>
<TR>
<TD VALIGN="TOP" ALIGN="LEFT" WIDTH="10%">Assignee:</TD>
<TD ALIGN="LEFT" WIDTH="90%"><B>The United States of America as represented
by the Director of the</B> (Washington, DC)</TD>
</TR>
<TR>
<TD VALIGN="TOP" ALIGN="LEFT" WIDTH="10%" NOWRAP>Appl. No.:</TD>
<TD ALIGN="LEFT" WIDTH="90%"><B> 528966</B></TD>
</TR>
<TR>
<TD VALIGN="TOP" ALIGN="LEFT" WIDTH="10%">Filed:</TD>
<TD ALIGN="LEFT" WIDTH="90%"><B>September 15, 1995</B></TD>
</TR>
</TABLE>
<P>
<TABLE WIDTH="100%">
<TR>
<TD VALIGN=TOP ALIGN="LEFT" WIDTH="40%"><B>U.S. Class:</B></TD>
<TD VALIGN=TOP ALIGN="RIGHT" WIDTH="60%"><B>380/21</B>; 380/28; 380/23; 380/4;
380/30</TD>
</TR>
<TR>
<TD VALIGN=TOP ALIGN="LEFT" WIDTH="40%"><B>Intern'l Class: </B></TD>
<TD VALIGN=TOP ALIGN="RIGHT" WIDTH="60%">H04K 001/00</TD>
</TR>
<TR>
<TD VALIGN=TOP ALIGN="LEFT" WIDTH="40%"><B>Field of Search: </B></TD>
<TD ALIGN="RIGHT" VALIGN="TOP" WIDTH="60%">380/21,28,30,23,24,25,3,4,49</TD>
</TR>
</TABLE>
<P>
<HR>
<CENTER>
<B>References Cited
<A href="/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-adv.htm&r=0&f=S&l=50&d=CR97&Query=ref/5,631,961">[Referenced
By]</A></B>
</CENTER>
<P>
<HR>
<CENTER>
<B>U.S. Patent Documents</B>
</CENTER>
<TABLE WIDTH="100%">
<TR>
<TD WIDTH="25%"><A href="/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F4304961">4304961</A></TD>
<TD WIDTH="25%">Dec., 1981</TD>
<TD WIDTH="25%" ALIGN="LEFT">Campbell, Jr.</TD>
<TD WIDTH="25%" ALIGN="RIGHT">178/22.</TD>
</TR>
<TR>
<TD WIDTH="25%"><A href="/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F4908861">4908861</A></TD>
<TD WIDTH="25%">Mar., 1990</TD>
<TD WIDTH="25%" ALIGN="LEFT">Brachtl et al.</TD>
<TD WIDTH="25%" ALIGN="RIGHT">380/25.</TD>
</TR>
<TR>
<TD WIDTH="25%"><A href="/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F4965827">4965827</A></TD>
<TD WIDTH="25%">Oct., 1990</TD>
<TD WIDTH="25%" ALIGN="LEFT">McDonald</TD>
<TD WIDTH="25%" ALIGN="RIGHT">380/25.</TD>
</TR>
<TR>
<TD WIDTH="25%"><A href="/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F5276737">5276737</A></TD>
<TD WIDTH="25%">Jan., 1994</TD>
<TD WIDTH="25%" ALIGN="LEFT">Micali</TD>
<TD WIDTH="25%" ALIGN="RIGHT">380/30.</TD>
</TR>
<TR>
<TD WIDTH="25%"><A href="/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F5555303">5555303</A></TD>
<TD WIDTH="25%">Sep., 1996</TD>
<TD WIDTH="25%" ALIGN="LEFT">Stambler</TD>
<TD WIDTH="25%" ALIGN="RIGHT">380/25.</TD>
</TR>
<TR>
<TD WIDTH="25%"><A href="/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=%2Fnetahtml%2Fsearch-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN%2F5557346">5557346</A></TD>
<TD WIDTH="25%">Sep., 1996</TD>
<TD WIDTH="25%" ALIGN="LEFT">Lipner et al.</TD>
<TD WIDTH="25%" ALIGN="RIGHT">380/21.</TD>
</TR>
</TABLE>
<P>
<BR>
<TABLE WIDTH="90%">
<TR>
<TD><BR>
<CENTER>
<B>Other References</B>
</CENTER>
</TD>
<TD ALIGN=LEFT><BR>
Federal Register vol. 58, No. 145, A Proposed Federal Information Processing
Standard for an Escrowed Encryption Standard (ESS) 58FR40791.</TD>
</TR>
</TABLE>
<P>
<BR>
<I>Primary Examiner:</I> Cain; David C. <BR>
<I>Attorney, Agent or Firm:</I> Morelli; Robert D. <BR>
<HR>
<CENTER>
<B><I>Claims</I></B>
</CENTER>
<P>
<HR>
<BR>
<BR>
1. A method of generating and using a public-key law enforcement access field,
where a sender and a receiver agree on a session key, comprising the steps
of; <BR>
<BR>
(a) forming g.sup.sk, where g is an element in a Galois Field, and where
sk is the session key; <BR>
<BR>
(b) forming a first temporary key; <BR>
<BR>
(c) encrypting the session key using the first temporary key; <BR>
<BR>
(d) combining an identification number with the result of step (c);
<BR>
<BR>
(e) forming a second temporary key; <BR>
<BR>
(f) encrypting the result of step (d) using the second temporary key;
<BR>
<BR>
(g) encrypting a plaintext message using the session key; <BR>
<BR>
(h) concatenating the results of steps (a), (f), and (g); and <BR>
<BR>
(i) transmitting the result of step (h) to the receiver. <BR>
<BR>
2. The method of claim 1, wherein said step of forming a first temporary
key comprises forming Y.sub.i **sk, where Y.sub.i is a public device unique
key. <BR>
<BR>
3. The method of claim 2, wherein said step of combining an identification
number with the result of step (c) comprises concatenating the identification
number to the result of step (c). <BR>
<BR>
4. The method of claim 3, wherein said step of forming a second temporary
key comprises forming Y.sub.f **sk, where Y.sub.f is a public family key.
<BR>
<BR>
5. A device for transmitting an encrypted message and an access field, where
a sender and a receiver agree on a session key, comprising: <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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 <BR>
<BR>
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. <BR>
<BR>
6. The device of claim 5, wherein the first, second, and third commutative
one-way function means each comprise an exponentiator. <BR>
<BR>
7. 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: <BR>
<BR>
(a) forming g.sup.sk ; <BR>
<BR>
(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; <BR>
<BR>
(c) forming a first temporary key; <BR>
<BR>
(d) encrypting the session key using the first temporary key; <BR>
<BR>
(e) forming a second temporary key; <BR>
<BR>
(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; <BR>
<BR>
(g) extracting the encrypted session key from the result of step (f);
<BR>
<BR>
(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 <BR>
<BR>
(i) decrypting the ciphertext received from the sender using the session
key in order to recover the plaintext message. <BR>
<BR>
8. The method of claim 7, wherein said step of forming a first temporary
key comprises forming Y.sub.i **sk, where Y.sub.i is a public device unique
key. <BR>
<BR>
9. The method of claim 8, wherein said step of forming a second temporary
key comprises forming Y.sub.f **sk, where Y.sub.i is a public family key.
<BR>
<BR>
10. 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: <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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 <BR>
<BR>
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. <BR>
<BR>
11. The device of claim 10, wherein the first, second, and third commutative
one-way function means each comprise an exponentiator. <BR>
<BR>
12. 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: <BR>
<BR>
(a) forming a first temporary key; <BR>
<BR>
(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; <BR>
<BR>
(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; <BR>
<BR>
(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; <BR>
<BR>
(e) forming a second temporary key using the result of step (d) and the g.sup.sk
intercepted from the sender; <BR>
<BR>
(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
<BR>
<BR>
(g) decrypting the sender's ciphertext message using the sender's session
key to recover the sender's plaintext message. <BR>
<BR>
13. The method of claim 12, wherein said step of forming a first temporary
key comprises forming (g.sup.sk)**x.sub.f, where x.sub.f is a secret family
key that is mathematically related to the public family key Y.sub.f.
<BR>
<BR>
14. The method of claim 13, wherein said step of forming a second temporary
key comprises forming g.sup.sk **x.sub.i, where x.sub.i is a secret unique
key that is mathematically related to the sender's public device unique key
Y.sub.i. <BR>
<BR>
15. 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: <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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 <BR>
<BR>
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. <BR>
<BR>
16. The device of claim 15, wherein the first, second, and third commutative
one-way function means each comprise an exponentiator. <BR>
<BR>
17. A method of generating and using an access field, where a sender and
a receiver agree on a session key, comprising the steps of; <BR>
<BR>
(a) generating, randomly, an initialization vector; <BR>
<BR>
(b) forming an exponent (m) using the session key and the initialization
vector; <BR>
<BR>
(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); <BR>
<BR>
(d) forming a temporary device unique key; <BR>
<BR>
(e) encrypting the session key with the temporary device unique key;
<BR>
<BR>
(f) forming a temporary family key; <BR>
<BR>
(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; <BR>
<BR>
(h) concatenating a string of bits to the initialization vector; <BR>
<BR>
(i) encrypting the session key using the result of step (h); <BR>
<BR>
(j) encrypting a plaintext message using the result of step (i); <BR>
<BR>
(k) concatenating a tag, the initialization vector, U, the result of step
(g), and the result of step (j); and <BR>
<BR>
(1) transmitting the result of step (k) to the recipient. <BR>
<BR>
18. The method of claim 17, wherein said step of forming an exponent comprises
the step of mapping the session key and the initialization vector to an exponent.
<BR>
<BR>
19. The method of claim 17, wherein said step of forming a temporary device
unique key comprises: <BR>
<BR>
t=h((Y.sub.i **m)mod p), where h is a function that maps a number to a key.
<BR>
<BR>
20. The method of claim 17, wherein said step of forming a temporary family
key comprises: <BR>
<BR>
w=h((Y.sub.f **m)mod p), where h is a function that maps a number to a key.
<BR>
<BR>
21. The method of claim 18, wherein said step of forming a temporary device
unique key comprises: <BR>
<BR>
t=h((Y.sub.i **m) mod p), where h is a function that maps a number to a key.
<BR>
<BR>
22. The method of claim 21, wherein said step of forming a temporary family
key comprises: <BR>
<BR>
w=h((Y.sub.f **m) mod p), where h is a function that maps a number to a key.
<BR>
<BR>
23. A device for transmitting an encrypted message and an access field, where
a sender and a receiver agree on a session key, comprising: <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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); <BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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
<BR>
<BR>
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. <BR>
<BR>
24. The device of claim 23, wherein the first exponentiation means, the second
exponentiation, and the third exponentiation means are each comprised of:
<BR>
<BR>
a) a multiplier; <BR>
<BR>
b) a memory connected to said multiplier; and <BR>
<BR>
c) a means for modulo reducing the result of exponentiation, where said modulo
reducing means is connected to said memory and said multiplier. <BR>
<BR>
25. 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: <BR>
<BR>
(a) receiving a ciphertext message concatenated to an access field;
<BR>
<BR>
(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; <BR>
<BR>
(c) forming an exponent (m); <BR>
<BR>
(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);
<BR>
<BR>
(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;
<BR>
<BR>
(f) forming a temporary family key; <BR>
<BR>
(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); <BR>
<BR>
(h) verifying the signature of the sender, proceeding to the next step if
the signature is verified, otherwise, stopping; <BR>
<BR>
(i) forming a temporary device unique key; <BR>
<BR>
(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); <BR>
<BR>
(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; <BR>
<BR>
(l) concatenating a string of bits to the initialization vector; <BR>
<BR>
(m) encrypting the session key using the result of step (1) as key; and
<BR>
<BR>
(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. <BR>
<BR>
26. The method of claim 25, wherein said step of forming an exponent comprises
the step of mapping the session key and the initialization vector to an exponent.
<BR>
<BR>
27. The method of claim 25, wherein said step of forming a temporary family
key comprises: <BR>
<BR>
w=h((Y.sub.f **m)mod p), where h is a function that maps a number to a key.
<BR>
<BR>
28. The method of claim 25, wherein said step of forming a temporary device
unique key comprises: <BR>
<BR>
t=h((Y.sub.i **m)mod p), where h is a function that maps a number to a key.
<BR>
<BR>
29. The method of claim 28, wherein said step of forming a temporary family
key comprises: <BR>
<BR>
w=h((Y.sub.f **m)mod p), where h is a function that maps a number to a key.
<BR>
<BR>
30. The method of claim 29, wherein said step of forming a temporary device
unique key comprises: <BR>
<BR>
t=h((Y.sub.i **m)mod p), where h is a function that maps a number to a key.
<BR>
<BR>
31. 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: <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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); <BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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;
<BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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 <BR>
<BR>
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.
<BR>
<BR>
32. The device of claim 31, wherein the first exponentiation means, the second
exponentiation means, and the third exponentiation means are each comprised
of: <BR>
<BR>
a) a multiplier; <BR>
<BR>
b) a memory connected to said multiplier; and <BR>
<BR>
c) a means for modulo reducing the result of exponentiation, where said modulo
reducing means is connected to said memory and said multiplier. <BR>
<BR>
33. 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: <BR>
<BR>
(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; <BR>
<BR>
(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;
<BR>
<BR>
(c) forming a temporary family key; <BR>
<BR>
(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);
<BR>
<BR>
(e) requesting the secret unique key held by each escrow agent based on the
identifier of the sender recovered in step (d); <BR>
<BR>
(f) combining the secret unique keys received as a result of step (e);
<BR>
<BR>
(g) forming a temporary device unique key; <BR>
<BR>
(h) recovering the session key by decrypting the encrypted session key using
the result of step (g); <BR>
<BR>
(i) concatenating a string of bits to the initialization vector; <BR>
<BR>
(j) encrypting the session key using the result of step (i); and <BR>
<BR>
(k) recovering the plaintext message by decrypting the ciphertext using the
result of step (j). <BR>
<BR>
34. The method of claim 33, wherein said step of forming a temporary family
key comprises: <BR>
<BR>
w=h((U**x.sub.f) mod p), where h is a function that maps a number to a key.
<BR>
<BR>
35. The method of claim 33, wherein said step of forming a temporary device
unique key comprises: <BR>
<BR>
t=h((U**x.sub.i) mod p), where h is a function that maps a number to a key.
<BR>
<BR>
36. The method of claim 35, wherein said step of forming a temporary device
unique key comprises: <BR>
<BR>
t=h((U**x.sub.i) mod p), where h is a function that maps a number to a key.
<BR>
<BR>
37. 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: <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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; <BR>
<BR>
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); <BR>
<BR>
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;
<BR>
<BR>
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;
<BR>
<BR>
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; <BR>
<BR>
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 <BR>
<BR>
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. <BR>
<BR>
38. The device of claim 37, wherein the first exponentiation means, and the
second exponentiation are each comprised of: <BR>
<BR>
a) a multiplier; <BR>
<BR>
b) a memory connected to said multiplier; and <BR>
<BR>
c) a means for modulo reducing the result of exponentiation, where said modulo
reducing means is connected to said memory and said multiplier.
<HR>
<CENTER>
<B><I> Description</I></B>
</CENTER>
<P>
<HR>
<BR>
<BR>
FIELD OF THE INVENTION <BR>
<BR>
This invention relates to a device for and a method of cryptography and,
more particularly, to a device for and method of cryptography that allows
third party access to encrypted messages between a first and second party.
<BR>
<BR>
BACKGROUND OF THE INVENTION <BR>
<BR>
Federal Register Vol. 59, No. 27 announced approval of Federal Information
Processing Standards Publication 185 (FIPS-185), Escrowed Encryption Standard
(EES). This standard specifies a technology developed by the Government of
the United States of America for providing strong encryption of unclassified
information and to provide for escrowed keys. This latter feature assists
law enforcement agencies and other government agencies, under proper legal
authority, in the collection and decryption of electronically transmitted
information. <BR>
<BR>
Key escrow technology was developed to address the concern that widespread
use of encryption would hinder lawfully authorized electronic surveillance.
In the past, law enforcement authorities have encountered very little encryption
because of the expense and difficulty in using this technology. More recently,
however, low-cost encryption technology has become commercially available
to all. The key escrow technology provided by FIPS-185 addresses the needs
of the private sector for secure cryptography and the needs of U.S. law
enforcement to conduct lawfully authorized electronic surveillance.
<BR>
<BR>
FIPS-185 specifies use of a symmetric-key encryption (and decryption) algorithm
and a Law Enforcement Access Field (LEAF) creation method which allows the
decryption of encrypted telecommunications by authorized law enforcement
agencies. <BR>
<BR>
The definition of "escrow" in the present invention is the delivery to a
third person of an item that is to be given to a grantee only upon the
fulfillment of a condition. Therefore, a key escrow system is one that entrusts
one or more components comprising a cryptographic key to one or more
key-component holders (i.e., escrow agents). The key-component holders provide
the components of a key to a "grantee" (e.g., a law enforcement official)
only upon fulfillment of the condition that the grantee obtain proper legal
authorization to conduct electronic surveillance of a particular device whose
key is being requested. The key components obtained through this process
are then used by the grantee to obtain the session key used by the particular
device. The session key is then used to decrypt the message sent by the device
of interest. <BR>
<BR>
Data for purposes of this patent application includes voice, facsimile, and
computer information communicated in a telephone system. <BR>
<BR>
The following terms are used as defined below: a) decryption is the conversion
of ciphertext to plaintext through the use of a cryptographic algorithm;
b) digital data is data that have been converted to a binary representation;
c) encryption is the conversion of plaintext to ciphertext through the use
of a cryptographic algorithm; d) key components are the parts from which
a key may be derived; e) key escrow is the process of managing (e.g., generating,
storing, transferring, auditing) the components of a cryptographic key by
key component holders; and f) LEAF creation method is a part of a key escrow
system that is implemented in a cryptographic device and creates a Law
Enforcement Access Field. <BR>
<BR>
FIPS-185 requires the following functions, at a minimum, to be implemented:
a) data encryption, where a session key is used to encrypt plaintext information
in one or more modes of operation specified in FIPS-81 (i.e., electronic
codebook, cipher block chaining, output feedback, and cipher feedback); b)
data decryption, where the session key used to encrypt the data is used to
decrypt resulting ciphertext to obtain the data; and c) LEAF creation, where
a family key and a unique key are used to create a Law Enforcement Access
Field (LEAF) in accordance with a LEAF Creation Method, and where the LEAF
is transmitted in a way that allows it to be decrypted with legal authorization.
<BR>
<BR>
FIPS-185 requires the use of the following parameters: a) a device unique
identifier (UID), where the UID is unique to a particular device, and where
the UID is used by the Key Escrow System; b) a device unique key (KU), where
KU is a cryptographic key that is unique to a particular device and used
by the Key Escrow System; c) cryptographic protocol field (CPF), where CPF
is the field identifying the registered cryptographic protocol used by a
particular application and used by the Key Escrow System; d) escrow authenticator
(EA), where EA is a binary pattern that is inserted in the LEAF to insure
that the LEAF is transmitted and received properly and has not been modified,
deleted, or replaced in an unauthorized manner; e) initialization vector
(IV), where IV is a mode and application dependent vector of bytes used to
initialize, synchronize, and verify the encryption, decryption, and key escrow
functions; f) family key (KF), where KF is the cryptographic key stored in
all devices designated as a family that is used to create a LEAF; g) session
key (KS), where KS is the cryptographic key used by a device to encrypt and
decrypt data during a session; and h) Law Enforcement Access Field (LEAF),
where LEAF is the field containing the encrypted session key and the device
identifier and the escrow authenticator. <BR>
<BR>
The LEAF is transmitted with the ciphertext. The device unique key is composed
of two components, where each component is independently generated and stored
by an escrow agent. The session key used to encrypt transmitted information
is used to decrypt received information. <BR>
<BR>
The escrowed encryption standard described in FIPS-185 uses symmetric keys
(i.e., keys that are used for both encryption and decryption). The symmetric
keys, which are stored in the device, are subject to reverse engineering.
The present invention discloses an escrowed encryption device and method
that does not require the storage of a secret key and is, therefore, not
susceptible to reverse engineering. From a security standpoint, the present
invention is substantially stronger than a symmetric-key escrowed-encryption
system. Instead, the present invention uses public key techniques to transmit
and store in the device a public version of the key. <BR>
<BR>
The closest prior art would most likely be found amongst devices for and
methods of creating an access code. For example, the prior art may include
U.S. Pat. Nos. 4,304,961 (entitled "AUTHENTICATOR CODE GENERATOR"), 4,908,861
(entitled "DATA AUTHENTICATION USING MODIFICATION DETECTION CODES BASED ON
A PUBLIC ONE WAY ENCRYPTION FUNCTION"), and 4,965,827 (entitled "AUTHENTICATOR").
One difference between these patents and the present invention is the manner
in which the secure transformation is accomplished. Another difference is
the public-key processing contained in the present invention that is not
contained in these prior art patents. <BR>
<BR>
U.S. Pat. No. 5,276,737, entitled "FAIR CRYPTOSYSTEMS AND METHODS OF USE,"
discloses a cryptosystem that requires the users to break a traffic key into
shares. Each share would then be held by a trustee so that no one trustee
could reconstruct the traffic key. Each trustee is provided with information
that would enable each trustee to independently verify that the trustee is
in possession of a share of a traffic key. The present invention differs
from U.S. Pat. No. 5,276,737 in that the present invention does not require
the traffic key be broken into shares and given to trustees. Also, the present
invention does not provide trustees with information that would enable them
to independently verify that they hold a share of the traffic key.
<BR>
<BR>
SUMMARY OF THE INVENTION <BR>
<BR>
The object of the present invention is to eliminate the vulnerability of
losing a secret key via reverse engineering from an encryption device. This
object is realized by disclosing a encryption device and method that uses
public-key techniques to encrypt and store the secret key. The secret key
is encrypted using a commutative one-way function that makes the secret key
irretrievable without knowing the associated decryption algorithm.
<BR>
<BR>
For an escrowed encryption system to work, more than a sender and a receiver
may be involved. There may be an authority who signs public keys, an authority
who signs secret keys, and escrow agents who hold parts of the secret keys.
<BR>
<BR>
The present invention envisions at least three parties to an encrypted
communication, a sender, a receiver, and a third party who may eavesdrop
on the communication between the sender and the receiver. The sender and
receiver are each given an element g in a field (e.g., a Galois Field), a
public device unique key Y.sub.i that is unique to each device, and a public
family key Y.sub.f that is known by all users of the present invention. The
sender and receiver agree on a session key sk that will be used to encrypt
and decrypt a communication between the sender and the receiver. <BR>
<BR>
The sender forms a datum U using the Galois Field element g, the session
key sk and a commutative one-way function block. A one-way function is a
function that is easy to compute but difficult if not impossible to undo
or reverse unless an additional piece of information is available to enable
one to undo the function. Presently, one-way functions may be constructed
using multipliers or exponentiators. It is believed that one cannot find
the factors of a number that is the product of two large prime numbers. This
is commonly referred to as a factoring problem. U.S. Pat. No. 4,405,829,
entitled CRYPTOGRAPHIC COMMUNICATIONS SYSTEM AND METHOD, issued to Rivest,
Shamir, and Adelman, commonly referred to as the RSA cryptosystem, is based
on the factoring problem. It is also believed that one cannot find the power
to which a large element of a finite group has been raised. This is commonly
referred to as a discrete logarithm problem. U.S. Pat. No. 4,200,770, entitled
CRYPTOGRAPHIC APPARATUS AND METHOD, issued to Diffie, Hellman, and Merkle,
is based on the discrete logarithm problem. A commutative one-way function
is a one-way function that also exhibits the commutative property (i.e.,
the property that it does not matter in what order the group operation is
performed). <BR>
<BR>
In the preferred embodiment of the present invention, g is an element of
order q in a Galois Field of order p (i.e., GF (p)), where p and q are prime
numbers and q is a prime divisor of (p-1). The commutative one-way function
is an exponentiator. Therefore, the datum U is g raised to sk (i.e., U=g.sup.sk).
It is believed that sk cannot be recovered from U. The present invention
relies on the intractability of the discrete logarithm problem rather than
the intractability of the factoring problem. <BR>
<BR>
The sender forms a first temporary key using the sender's public device unique
key Y.sub.i, the session key sk, and a second commutative one-way function.
In the preferred embodiment, the second commutative one-way function is identical
to the first commutative one-way function. Therefore, the first temporary
key is Y.sub.i **sk ("**" denotes raising the item that precedes "**" to
the power following "**"). <BR>
<BR>
The session key sk is then encrypted using a symmetric-key encryptor and
the first temporary key as the key. The encrypted session key is then combined
with an identification number unique to the sender. Preferably, the combination
step is concatenation. <BR>
<BR>
A third commutative-one way function is used with the public family key Y.sub.f
and the session key to form a second temporary key (i.e., Y.sub.f **sk).
The second temporary key is used as the key to a second symmetric-key encryptor
for encrypting the combination of sender's identification number and the
encrypted session key. The result is a datum that will be referred to as
V. <BR>
<BR>
The sender's plaintext message is encrypted to form a ciphertext message
using a third symmetric-key encryptor and the session key sk as the key.
The first, second, and third symmetric-key encryptors may be identical to
each other or they may differ from each other. Datums U, V, and the ciphertext
are then sent to the receiver. <BR>
<BR>
The receiver receives datums U, V, and the ciphertext from the sender. Knowing
the Galois element g and the session key sk, the receiver forms a datum that
should be identical to the datum U received using a commutative one-way function
that is identical to the commutative one-way function used by the sender
to form the datum U. The receiver then compares the datum formed to the datum
U received. If they match, processing continues. Otherwise, processing is
halted. <BR>
<BR>
The receiver uses the sender's public device unique key Y.sub.i, the session
key sk, and a second commutative one-way function block to form a first temporary
key (e.g., Y.sub.i **sk). The receiver uses the first temporary key to encrypt
the session key sk using a symmetric-key encryptor. The symmetric-key encryptor
is identical to the symmetric-key encryptor used by the sender to encrypt
the session key sk. <BR>
<BR>
The receiver uses the public family key Y.sub.f, the session key sk, and
a third commutative one-way function block to form a second temporary key
(e.g., Y.sub.f **sk). The receiver's first, second, and third commutative
one-way function blocks may be the same or they may be different, but they
must correspond to the first, second, and third commutative one-way function
blocks used by the sender. That is, the sender and receiver must use like
commutative one-way function blocks for like purposes. <BR>
<BR>
The receiver's second temporary key is used as the key for a first symmetric-key
decryptor which is used to decrypt the datum V received from the sender.
The first decryptor must be able to undo or reverse the output of the sender's
second encryptor. An extractor is used to separate the sender's encrypted
session key from the sender's identification number. The sender's encrypted
session key is then compared to the receiver's encrypted session key. If
the encrypted session keys match, processing continues. Otherwise, processing
is halted. <BR>
<BR>
If both of the comparisons made by the receiver are successful then the receiver
decrypts the ciphertext received from the sender using the session key sk
as the key to a second symmetric-key decryptor. The second symmetric-key
decryptor must be able to undo or reverse the result of the third symmetric-key
encryptor used by the sender to encrypt the sender's plaintext message.
<BR>
<BR>
In the present invention, a third party may under proper circumstances gain
access to communications between the sender and the receiver. The third party
may be anyone who has a legitimate need to gain access to such a communication
(e.g., employers, law enforcement agencies, etc.). Proper authority may come
from an employment agreement or an order of a court. It may also be required
that the third party seek from one or more authorizing entities the necessary
items to recover the communication between a sender and a receiver
<BR>
<BR>
The third party is given a secret family key x.sub.f which corresponds to
the public family key Y.sub.f held by both the sender and the receiver. The
third party is also given data based on the identification numbers of all
of the valid senders. <BR>
<BR>
The third party intercepts the datums U, V, and the ciphertext sent by the
sender to the receiver. The third party uses the secret family key x.sub.f,
the intercepted datum U, and a first commutative one-way function block to
form a first temporary key (e.g., U**x.sub.f). The first commutative one-way
function block is identical to the third commutative one-way function blocks
used by the sender and the receiver (i.e., the commutative one-way function
blocks that uses the public family key Y.sub.f). <BR>
<BR>
The first temporary key is used as the key for a first symmetric-key decryptor
to decrypt the intercepted datum V. The first symmetric-key decryptor must
be able to undo or reverse the result of the second symmetric-key encryptor
used by the sender. The result of the decryption is the sender's identification
number and the sender's encrypted session key. <BR>
<BR>
The combination based on the sender's identification number and the sender's
encrypted session key is separated into two component parts. The first component
part is based upon the sender's identification number while the second component
part is based on the sender's encrypted session key. The bits based on the
sender's identification number is used as an address to a memory unit. The
output of the memory unit x.sub.i is used with the intercepted datum U and
a second commutative one-way function block to form a second temporary key
(e.g., U**x.sub.i). <BR>
<BR>
The second temporary key is used with a second symmetric-key decryptor to
decrypt the bits based on the sender's encrypted session key in order to
recover the sender's session key. The second symmetric-key decryptor must
be able to undo or reverse the result of the sender's first symmetric-key
encryptor. <BR>
<BR>
With the session key sk and a third symmetric-key decryptor, the third party
decrypts the intercepted ciphertext message in order to recover the sender's
plaintext message. The third symmetric-key decryptor must be able to undo
or reverse the result of the sender's third symmetric-key encryptor.
<BR>
<BR>
In an alternate embodiment of the present invention, the following system-wide
parameters are used: <BR>
<BR>
a) p=a prime number; <BR>
<BR>
b) q=a prime divisor of p-1; <BR>
<BR>
c) g=an element of order q in GF (p); <BR>
<BR>
d) x.sub.u =a universal secret (i.e., master) key; <BR>
<BR>
e) x.sub.e =a secret key known only by an escrow certification authority;
<BR>
<BR>
f) x.sub.f =a secret family, or common, key, where x.sub.f is known only
by the third party; <BR>
<BR>
g) Y.sub.u =(g**x.sub.u)mod p, the universal public key; <BR>
<BR>
h) Y.sub.e =(g**x.sub.e)mod p, an escrow certifier's public key; <BR>
<BR>
i) Y.sub.f =(g**x.sub.f)mod p, the public family key; <BR>
<BR>
j) Tag=an identification field in a third party access field; <BR>
<BR>
k) k.sub.e =a secret key, known only by a holder of the universal secret
key; <BR>
<BR>
l) r.sub.e =((g**k.sub.e) mod p)mod q, half of an escrow certifier's signature;
and <BR>
<BR>
m) s.sub.e =(k.sub.e -1) (SHA(Y.sub.f .vertline..vertline.Tag
.vertline..vertline.Y.sub.e)+(x.sub.u) (r.sub.e))mod q, the other half of
the escrow certifier's signature, where ".vertline..vertline." denotes
concatenation. The term "SHA" refers to a secure hash algorithm. <BR>
<BR>
The following information is unique to each user of the alternate embodiment
of the present invention: <BR>
<BR>
a) ID.sub.i =user i's identification number; <BR>
<BR>
b) x.sub.i1 =a secret unique key held by a first escrow agent; <BR>
<BR>
c) x.sub.i1 =a secret unique key held by a second escrow agent; <BR>
<BR>
d) Y.sub.i =((g**(x.sub.i1 +x.sub.i2) mod q) mod p), the device unique public
key; <BR>
<BR>
e) k.sub.i =a secret key known only by the escrow certifier; <BR>
<BR>
f) r.sub.i =((g**k.sub.i) mood p) mood q, one-half of the signature for device
i; and <BR>
<BR>
g) s.sub.i =(k.sub.i- 1) (SHA(Y.sub.f .vertline..vertline.Tag
.vertline..vertline.ID.sub.i .vertline..vertline.Y.sub.i)+(x.sub.e) (r.sub.i))mod
q, the other half of the signature for device i. <BR>
<BR>
To send a message, a sender does the following: <BR>
<BR>
(a) the sender knows p, q, g, Y.sub.i, Y.sub.f, f, h, r.sub.i, s.sub.i, and
Tag; <BR>
<BR>
(b) the sender and recipient know the session key (sk); <BR>
<BR>
(c) generate a random number (IV); <BR>
<BR>
(d) form m=f (IV,sk); <BR>
<BR>
(e) form U=g.sup.m mod p; <BR>
<BR>
(f) form t=h((Y.sub.i **m) mod p); <BR>
<BR>
(g) form w=h((Y.sub.f **m) mod p); <BR>
<BR>
(h) form V=E.sub.w (IV, (ID.sub.i .vertline..vertline.Y.sub.i
.vertline..vertline.r.sub.i .vertline..vertline.s.sub.i
.vertline..vertline.E.sub.t (sk) .vertline..vertline.first pad)),
<BR>
<BR>
where "E.sub.w " denotes an encryption algorithm that uses w as a key to
encrypt the data within the parens; <BR>
<BR>
(i) form z=IV.vertline..vertline.second pad; <BR>
<BR>
(j) form sk*=E.sub.z (sk); <BR>
<BR>
(k) form ct=E.sub.sk* (IV, pt); <BR>
<BR>
(l) form the third party access field (e.g.,
Tag.vertline..vertline.IV.vertline..vertline.U.vertline..vertline.V); and
<BR>
<BR>
(m) transmit ct concatenated to the third party access field to the recipient.
<BR>
<BR>
To recover the plaintext, the recipient would do the following: <BR>
<BR>
(a) the recipient knows the p, q, g, Y.sub.f, f, h, sk used by the sender;
<BR>
<BR>
(b) receive ct and the third party access field from the sender; <BR>
<BR>
(c) recover IV, U, V, and Tag from the third party access field; <BR>
<BR>
(d) form m=f(IV, sk); <BR>
<BR>
(e) form U=g.sup.m mod p; <BR>
<BR>
(f) proceed if U recovered equals U formed, otherwise, stop; <BR>
<BR>
(g) form w=h((Y.sub.f **m) mod p); <BR>
<BR>
(h) recover Y.sub.i, r.sub.i, s.sub.i, ID.sub.i, and E.sub.t (sk) from the
third party access field by decrypting V; <BR>
<BR>
(i) verify the signature (r.sub.i, s.sub.i) recovered in step (h) using the
Tag recovered in step (c) and the ID.sub.i and Y.sub.i recovered in step
(h), proceed if the signature (r.sub.i,s.sub.i) is verified, otherwise, stop;
<BR>
<BR>
(j) form t=h((Y.sub.i **m) mod p) using the Y.sub.i recovered in step (h);
<BR>
<BR>
(k) recover sk by decrypting E.sub.t (sk); <BR>
<BR>
(l) proceed if sk recovered equals sk known, otherwise, stop; <BR>
<BR>
(m) form z=IV.vertline..vertline.second pad; <BR>
<BR>
(n) form sk*=E.sub.z (sk); and <BR>
<BR>
(o) recover the plaintext message (pt) by decrypting the ct using sk* (i.e.,
D.sub.sk* (IV, ct), where "D.sub.sk* " denotes a decryption algorithm that
uses sk* as a key to decrypt the contents of the parens). <BR>
<BR>
While the sender is sending ct and the third party access field to the recipient,
an authorized third party may do the following: <BR>
<BR>
(a) the third party knows p, q, g, Y.sub.f, x.sub.f, h, and D; <BR>
<BR>
(b) intercept the ct concatenated with the third party access field;
<BR>
<BR>
(c) recover Tag, IV, V, and U from the third party access field; <BR>
<BR>
(d) identify the secret family key, x.sub.f, from the Tag; <BR>
<BR>
(e) form w=h((U**x.sub.f) mod p); <BR>
<BR>
(f) recover ID.sub.i, Y.sub.i, r.sub.i, s.sub.i, and E.sub.t (sk) from V
by decrypting V using w and IV (i.e., D.sub.w (IV, V)); <BR>
<BR>
(g) verify the (r.sub.i, s.sub.i) received; <BR>
<BR>
(h) identify the escrow agents from the Tag; <BR>
<BR>
(i) request x.sub.i1 from the first escrow agent and x.sub.i2 from the second;
<BR>
<BR>
(j) form x.sub.i =(x.sub.i1 +x.sub.i2) mod q; <BR>
<BR>
(k) form t=h((U**x.sub.i) mod p); <BR>
<BR>
(l) recover sk by decrypting E.sub.t (sk); <BR>
<BR>
(m) form z=IV.vertline..vertline.second pad; <BR>
<BR>
(n) form sk*=E.sub.z (sk); and <BR>
<BR>
(o) recover the plaintext message by decrypting ct using sk* (i.e., D.sub.sk*
(IV, ct)). <BR>
<BR>
BRIEF DESCRIPTION OF THE DRAWINGS <BR>
<BR>
FIG. 1 is a flow chart of the steps that a sender performs; <BR>
<BR>
FIG. 2 is a schematic of a device used by the sender; <BR>
<BR>
FIG. 3 is a flow chart of the steps that a recipient performs; <BR>
<BR>
FIG. 4 is a schematic of a device used by the recipient; <BR>
<BR>
FIG. 5 is a flow chart of the steps that a third party performs; <BR>
<BR>
FIG. 6 is a schematic of a device used by the third party; <BR>
<BR>
FIG. 7 is a flow chart of the steps that a sender performs in the alternate
embodiment of the present invention; <BR>
<BR>
FIG. 8 is a schematic of a device used by the sender in the alternate embodiment
of the present invention; <BR>
<BR>
FIG. 9 is a flow chart of the steps that a recipient performs in the alternate
embodiment of the present invention; <BR>
<BR>
FIG. 10 is a schematic of a device used by the recipient in the alternate
embodiment of the present invention; <BR>
<BR>
FIG. 11 is a flow chart of the steps that a third party performs in the alternate
embodiment of the present invention; and <BR>
<BR>
FIG. 12 is a schematic of a device used by the third party in the alternate
embodiment of the present invention. <BR>
<BR>
DETAILED DESCRIPTION <BR>
<BR>
The present invention discloses a public-key escrowed encryption device that
eliminates the weaknesses associated with storing a secret key in an encryption
device. Instead of storing the secret key that may be lost via reverse
engineering, the present invention uses public-key techniques to store and
transmit an encrypted secret key. The secret key is encrypted using commutative
one-way functions that are believed to render the encrypted secret-key
irretrievable absent knowledge of the associated decryption algorithm.
<BR>
<BR>
The present invention envisions at least three parties to an encrypted
communication, a sender, a receiver, and a third party who, under certain
circumstances, may eavesdrop on the communication between the sender and
the receiver. <BR>
<BR>
FIG. 1 illustrates the method that the sender must go through to send a message
to the receiver. The sender is given an element g in a Galois Field, a public
device unique key Y.sub.i that is unique to the sender's device, and a public
family key Y.sub.f that is known by all users of the present invention.
<BR>
<BR>
The sender and receiver agree on a session key that will be used to encrypt
and decrypt communications between the sender and the receiver. <BR>
<BR>
The sender forms a datum U using the Galois Field element g, the session
key sk and a first commutative one-way function block. A one-way function
is a function that is easy to compute but difficult if not impossible to
undo or reverse unless an additional piece of information is available to
enable one to undo the function. In the preferred embodiment of the present
invention, g is an element of order q in a Galois Field of order p (i.e.,
GF(p)), where p and q are prime numbers, and q is a prime divisor of (p-1).
The first commutative one-way function block is an exponentiator. Therefore,
the datum U is equal to g raised to the session key sk (i.e., U=g.sup.sk).
It is believed that the session key sk cannot be recovered from U.
<BR>
<BR>
The sender forms a first temporary key using the sender's public device unique
key Y.sub.i, the session key sk, and a second commutative one-way function
block. In the preferred embodiment, the second commutative one-way function
block is identical to the first commutative one-way function block. Therefore,
the first temporary key is Y.sub.i **sk. <BR>
<BR>
The first temporary key is used to encrypt the session key sk using a first
symmetric-key encryptor. The encrypted session key is then combined with
an identification number that is unique to the sender. In the preferred
embodiment, the combination step is concatenation. <BR>
<BR>
A second temporary key is formed using the session key sk, the public family
key Y.sub.f, and a third commutative-one way function block (e.g., the second
temporary key is Y.sub.f **sk). The second temporary key is used as the key
to a second symmetric-key encryptor to encrypt the combination of the sender's
identification number and the encrypted session key. The result is a datum
referred to as V. <BR>
<BR>
A plaintext message that the sender wishes to encrypt and send to the receiver
is encrypted using the session key sk and a third symmetric-key encryptor.
The first, second, and third symmetric-key encryptors may be the same or
they may be different. Datums U, V, and the ciphertext are then sent to the
receiver. <BR>
<BR>
FIG. 2 is a schematic of the sender's device 1. A first commutative one-way
function block 2 receives a Galois field element g along a first input 3
and receives a session key sk along a second input 4. The output 5 of the
first commutative one-way function block 2 forms a datum U. The commutative
one-way function block 2 may be realized with a multiplier or an exponentiator.
In the preferred embodiment, the commutative one-way function block 2 is
an exponentiator. Therefore, U is equal to g.sup.sk. <BR>
<BR>
A second commutative one-way function block 6 receives a public device unique
key Y.sub.i via a first input 7 and receives the session key sk via a second
input 4. In the preferred embodiment, the second commutative one-way function
block 6 is identical to the first commutative one-way function block 2.
Therefore, the output 8 of the second commutative one-way function block
6 is a datum that represents a first temporary key (i.e., Y.sub.i **sk).
<BR>
<BR>
A first symmetric-key encryptor 9 uses the first temporary key as the key
to encrypt the session key sk. The first symmetric-key encryptor 9 has a
first input 4 for receiving the session key sk as plaintext, a second input
connected to the output 8 of the second commutative one-way function block
6 for receiving the first temporary key as the key, and an output 10 for
transmitting the encrypted session key. The first symmetric-key encryptor
9 may be realized with any secure symmetric-key encryptor. <BR>
<BR>
The encrypted session key is combined with an identification number that
is unique to the sender's device 1. A combiner 11 for combining the
identification number and the encrypted session key has a first input connected
to the output 10 of the first symmetric-key encryptor 9 for receiving the
encrypted session key, a second input 12 for receiving the identification
number, and an output 13 for transmitting the combination of identification
number and encrypted session key. The combiner 11 may be realized in many
ways. In the preferred embodiment, the combiner concatenates the identification
number to the encrypted session key. <BR>
<BR>
A third commutative one-way function block 14 is used to form a second temporary
key using the session key and the public family key Y.sub.f. The third
commutative one-way function block 14 has a first input 4 for receiving the
session key sk, a second input 15 for receiving the public family key Y.sub.f,
and an output 16 for transmitting the second temporary key. The third commutative
one-way function block 14 is identical to the first commutative one-way function
block 2. Therefore, the output 16 of the third commutative one-way function
block 14 transmits Y.sub.f **sk. <BR>
<BR>
A second symmetric-key encryptor 17 uses the second temporary key as the
key to encrypt the combination of identification number and encrypted session
key. The second symmetric-key encryptor 17 has a first input connected to
the output 13 of the combiner 11 for receiving the output of the combiner
11 as plaintext, a second input connected to the output 16 of the third
commutative one-way function block 14 for receiving the second temporary
key as key, and an output 18 for transmitting the result which is a datum
referred to as V. The second symmetric-key encryptor 17 may be identical
to the first symmetric-key encryptor 9. <BR>
<BR>
A third symmetric-key encryptor 19 uses the session key sk as the key to
encrypt the plaintext message that the sender wishes to send to the receiver.
The third symmetric-key encryptor 19 has a first input 4 for receiving the
session key sk as the key, a second input 20 for receiving the plaintext,
and an output 21 for transmitting the resulting ciphertext. The third
symmetric-key encryptor 19 may be identical to the first symmetric-key encryptor
9. <BR>
<BR>
The output 5 of the first commutative one-way function block 2, the output
18 of the second symmetric-key encryptor 17, and the output 21 of the third
symmetric-key encryptor 19 are connected, respectively, to a first input,
a second input, and a third input to the register 22. The register 22 has
an output 23 from which the datum U, V, and the ciphertext may be transmitted
to the receiver. <BR>
<BR>
FIG. 3 illustrates the steps that the receiver must perform. The receiver
receives datums U, V, and the ciphertext from the sender. Knowing the Galois
element g and the session key sk, the receiver forms a datum that is identical
to the datum U from the sender. The receiver uses a commutative one-way function
that is identical to the commutative one-way function used by the sender
to form the datum U. The receiver then compares the datum it formed to the
datum U received from the sender. If they match, processing continues. Otherwise,
processing is halted. <BR>
<BR>
The receiver uses the sender's public device unique key Y.sub.i, the session
key sk, and a second commutative one-way function block to form a first temporary
key (e.g., Y.sub.i **sk). The receiver uses the first temporary key to encrypt
the session key sk using a first symmetric-key encryptor. The receiver's
first symmetric-key encryptor is identical to the symmetric-key encryptor
used by the sender to encrypt the session key sk. <BR>
<BR>
The receiver uses the public family key Y.sub.f, the session key sk, and
a third commutative one-way function block to form a second temporary key
(e.g., Y.sub.f **sk). The receiver's first, second, and third commutative
one-way function blocks may be identical to each other or they may be different
from one another, but they must correspond to the first, second, and third
commutative one-way function blocks used by the sender. That is, the sender
and receiver must use like commutative one-way function blocks for like purposes.
<BR>
<BR>
The receiver's second temporary key is used as the key for decrypting the
datum V received from the sender. The receiver uses a first symmetric-key
decryptor to decrypt the datum V. The receiver's first decryptor must be
able to undo or reverse the output of the sender's second encryptor.
<BR>
<BR>
The result of decrypting the datum V is the combination of the sender's
identification number and the sender's encrypted session key. These two
components are separated, and the sender's encrypted session key is compared
to the receiver's encrypted session key. Processing continues if they match.
Otherwise, processing is halted. <BR>
<BR>
If both of the comparisons made by the receiver are successful, the receiver
proceeds to decrypt the ciphertext received from the sender using the session
key sk as key with a second symmetric-key decryptor. The receiver's second
symmetric-key decryptor must be able to undo or reverse the operation of
the third symmetric-key encryptor used by the sender to encrypt the plaintext.
<BR>
<BR>
FIG. 4 is a schematic of a device 30 that the receiver may use to implement
the method illustrated in FIG. 3. <BR>
<BR>
A register 31 receives datums U, V, and the ciphertext transmitted by the
sender via an input 32. Valid data received would be data sent by a sender
who has used the device 1 of FIG. 2 to generate the data. The register 31
has a first output 33 for transmitting the received datum U, a second output
34 for transmitting the received datum V, and a third output 35 for transmitting
the received ciphertext. <BR>
<BR>
A first commutative one-way function block 36, having a first input 37 for
receiving an element g of a Galois field, having a second input 38 for receiving
the session key sk, and having an output 39, is used to form a datum that
is identical to the datum U received from the sender. The receiver's first
commutative one-way function block 36 must be identical to the first commutative
one-way function block 2 of FIG. 2 (i.e., either a multiplier or an
exponentiator). In the preferred embodiment of the present invention, the
sender's first commutative one-way function block 2 is an exponentiator.
Therefore, the datum available at the output 39 of the receiver's first
commutative one-way function block 36 is g.sup.sk. <BR>
<BR>
A comparator 40, having a first input connected to the output 39 of the
receiver's first commutative one-way function block 36, having a second input
connected to the first output 33 of the register 31 for receiving the sender's
datum U, and having an output 41, compares the sender's datum U to the datum
generated by the receiver. If the two datum's match, processing continues.
Otherwise, processing is halted. <BR>
<BR>
A second commutative one-way function block 42, having a first input 43 for
receiving the sender's public device unique key Y.sub.i, having a second
input 38 for receiving the session key sk, and having an output 44, forms
the receiver's first temporary key. The receiver's second commutative one-way
function block 42 must be identical to the second commutative one-way function
block 6 of FIG. 2 (i.e., a multiplier or an exponentiator). In the preferred
embodiment, the sender's second commutative one-way function block 6 is an
exponentiator. Therefore, Y.sub.i **sk appears at the output 44 of the receiver's
second commutative one-way function block 42. <BR>
<BR>
A symmetric-key encryptor 45, having a plaintext input 38 for receiving the
session key sk as plaintext, having a key input connected to the output 44
of the second commutative one-way function block 42 for receiving the receiver's
first temporary key as a key, and having a ciphertext output 46, is used
to encrypt the session key sk. The receiver's symmetric-key encryptor 45
is identical to the first symmetric-key encryptor 9 of FIG. 2. Eventually,
the encrypted version of the session key appearing at the output 46 of the
receiver's symmetric-key encryptor 45 will be compared to the sender's encrypted
session key. If they match, processing continues. Otherwise, processing is
halted. <BR>
<BR>
A third commutative one-way function block 47, having a first input 48 for
receiving a public family key Y.sub.f, having a second input 38 for receiving
the session key sk, and having an output 49, forms the receiver's second
temporary key. The receiver's third commutative one-way function block 47
must be identical to the third commutative one-way function block 14 of FIG.
2 (i.e., a multiplier or an exponentiator). In the preferred embodiment,
the sender's third commutative one-way function block 14 is an exponentiator.
Therefore, Y.sub.f **sk appears at the output 49 of the receiver's third
commutative one-way function block 49. <BR>
<BR>
A first symmetric-key decryptor 50, having a ciphertext input connected to
the second output 34 of the register 31 for receiving the sender's datum
V, having a key input connected to the output 49 of the third commutative
one-way function block 47 for receiving the receiver's second temporary key
as a key, and having a plaintext output 52, is used to decrypt the sender's
datum V (i.e., the combination of the sender's identification number and
the sender's encrypted session key). The receiver's first symmetric-key decryptor
50 must be able to undo or reverse the result of the sender's second
symmetric-key encryptor 17 of FIG. 2. <BR>
<BR>
An extractor 53, having an input connected to the output 52 of the first
symmetric-key decryptor 50, and having an output 54, separates the sender's
identification number from the sender's encrypted session key and transmits
the sender's encrypted session key via the output 54. <BR>
<BR>
A second comparator 55, having a first input connected to the output 46 of
the symmetric-key encryptor 45 for receiving the receiver's encrypted session
key, having a second input connected to the output 54 of the extractor 53
for receiving the sender's encrypted session key, and having an output 56,
compares the sender's encrypted session key to the receiver's encrypted session
key. If they match, processing continues. Otherwise, processing is halted.
<BR>
<BR>
A second symmetric-key decryptor 57, having a first input connected to the
third output 35 of the register 31 for receiving the sender's ciphertext
as ciphertext, having a second input 38 for receiving the session key as
key, and having a plaintext output 58, decrypts the sender's ciphertext in
order to recover the sender's plaintext message. The receiver's second
symmetric-key decryptor 57 must be able to undo or reverse the output 21
of the sender's third symmetric-key encryptor 19. <BR>
<BR>
FIG. 5 illustrates the steps that a third party must perform in order to
recover the plaintext from the sender's message. In the present invention,
a third party may, under proper circumstances, gain access to a communication
between the sender and the receiver. The third party may be anyone who has
a legitimate need to gain access to such communications (e.g., employers,
law enforcement agencies, etc.). Proper authority may come from an employment
agreement or an order of a court. It may also be required that the third
party seek the necessary items to recover the communication between a sender
and a receiver from one or more authorizing entities. <BR>
<BR>
The third party is given a secret family key x.sub.f which corresponds to
the public family key Y.sub.f held by both the sender and the receiver. The
third party is also given data based on the identification numbers of all
of the valid senders. <BR>
<BR>
The third party intercepts the datums U, V, and the ciphertext sent by the
sender to the receiver. The third party uses the secret family key x.sub.f,
the intercepted datum U, and a first commutative one-way function block to
form a first temporary key (e.g., U**x.sub.f). The first commutative one-way
function block is identical to the third commutative one-way function blocks
used by the sender and the receiver (i.e., the commutative one-way function
blocks that use the public family key Y.sub.f). <BR>
<BR>
The first temporary key is used as the key for a first symmetric-key decryptor
to decrypt the intercepted datum V. The first symmetric-key decryptor must
be able to undo or reverse the result of the second symmetric-key encryptor
used by the sender. The result of the decryption is the sender's identification
number and the sender's encrypted session key. <BR>
<BR>
The sender's identification number and the sender's encrypted session key
are separated into two component parts. The first component part is the sender's
identification number (ID.sub.i) while the second component part is the sender's
encrypted session key. The sender's identification number is used as an address
to a memory unit. The output of the memory unit x.sub.i is used with the
intercepted datum U and a second commutative one-way function block to form
a second temporary key (e.g., U**x.sub.i). The x.sub.i is mathematically
related to the public device unique key Y.sub.i (i.e., Y.sub.i =g**x.sub.i)
so that the third part may recover the sender's session key. <BR>
<BR>
The second temporary key is used with a second symmetric-key decryptor to
decrypt the bits based on the sender's encrypted session key in order to
recover the sender's session key. The second symmetric-key decryptor must
be able to undo or reverse the result of the sender's first symmetric-key
encryptor. <BR>
<BR>
With the session key sk and a third symmetric-key decryptor, the third party
decrypts the intercepted ciphertext message in order to recover the sender's
plaintext message. The third symmetric-key decryptor must be able to undo
or reverse the result of the sender's third symmetric-key encryptor.
<BR>
<BR>
FIG. 6 is a schematic of a device 60 that the third party may use to implement
the method illustrated in FIG. 5. <BR>
<BR>
A register 61 intercepts datums U, V, and the ciphertext transmitted by the
sender via an input 62. The register 61 has a first output 63 for transmitting
the intercepted datum U, a second output 64 for transmitting the intercepted
datum V, and a third output 65 for transmitting the intercepted ciphertext.
<BR>
<BR>
A first commutative one-way function block 66, having a first input connected
to the first output 63 of the register 61 for receiving the intercepted datum
U, having a second input 67 for receiving the secret family key x.sub.f,
and having an output 68, forms the third party's first temporary key. The
third party's first commutative one-way function block 66 must be identical
to the third commutative one-way function block 14 of FIG. 2 (i.e., a multiplier
or an exponentiator). In the preferred embodiment, the sender's third commutative
one-way function block 14 is an exponentiator. Therefore, U**x.sub.f appears
at the output 68 of the third party's first commutative one-way function
block 66. <BR>
<BR>
A first symmetric-key decryptor 69, having a ciphertext input connected to
the second output 64 of the register 61 for receiving the intercepted datum
V, having a key input connected to the output 68 of the first commutative
one-way function block 66 for receiving the third party's first temporary
key as a key, and having a plaintext output 70, is used to decrypt the
intercepted datum V (i.e., the combination of the sender's identification
number and the sender's encrypted session key). The third party's first
symmetric-key decryptor 69 must be able to undo or reverse the result of
the sender's second symmetric-key encryptor 17 of FIG. 2. <BR>
<BR>
An extractor 71, having an input connected to the output 70 of the first
symmetric-key decryptor 69, having a first output 72 for transmitting bits
ID based on the sender's identification number, and having a second output
73 for transmitting bits based on the sender's encrypted session key, separates
the bits based on the sender's identification number from the bits based
on the sender's encrypted session key. <BR>
<BR>
A memory 74, having an input connected to the first output 72 of the extractor
71, and having an output 75, accepts the sender's identification number and
transmits the secret unique key x.sub.i so that the third party may recover
the sender's session key sk. <BR>
<BR>
A second commutative one-way function block 76, having a first input connected
to the first output 63 of the register 61 for receiving the intercepted datum
U, having a second input connected to the output 75 of the memory 74 for
receiving the secret unique key x.sub.i based on the sender's identification
number ID.sub.i, and having an output 77, forms the third party's second
temporary key. The third party's second commutative one-way function block
76 must be identical to the sender's second commutative one-way function
block 6 of FIG. 2 (i.e., a multiplier or an exponentiator). In the preferred
embodiment, the sender's second commutative one-way function block 6 is an
exponentiator. Therefore, U**x.sub.i appears at the output 77 of the third
party's second commutative one-way function block 76. <BR>
<BR>
A second symmetric-key decryptor 78, having a first input connected to the
second output 73 of the extractor 71 for receiving bits based on the sender's
encrypted session key as ciphertext, having a second input connected to the
output 77 of the second commutative one-way function block 76 for receiving
the second temporary key as key, and having a plaintext output 79, decrypts
the bit based on the sender's encrypted session key in order to recover the
sender's session key. <BR>
<BR>
A third symmetric-key decryptor 80, having a first input connected to the
third output 65 of the register 61 for receiving the intercepted ciphertext
as ciphertext, having a second input connected to the output 79 of the second
symmetric-key decryptor 78 for receiving the session key as key, and having
a plaintext output 81, decrypts the intercepted ciphertext in order to recover
the sender's plaintext message. The third party's third symmetric-key decryptor
80 must be able to undo or reverse the output 21 of the sender's third
symmetric-key decryptor 19. <BR>
<BR>
In an alternate embodiment of the present invention, several entities may
exist. A first entity may hold a master key. The master key may be used to
sign a public key of a second entity. The second entity may certify (i.e.,
sign) a public unique key Y.sub.i. Escrow agents may hold parts of the secret
unique key x.sub.i and may only divulge these parts under certain circumstances
(e.g., when appropriate authority is demonstrated). <BR>
<BR>
The following system-wide parameters may be used in the alternate embodiment
of the present invention: <BR>
<BR>
a) p, a prime number, preferably, 1024 bits long, where p is known by all
users (i.e., escrow entities, the sender, the recipient, and the third party);
<BR>
<BR>
b) q, a prime divisor of p-1, preferably, 160 bits long, where q is known
by all users; <BR>
<BR>
c) g, an element of order q in GF(p), where g is known by all users;
<BR>
<BR>
d) x.sub.u, a universal secret (i.e., master) key known only by the universal
authority, where x.sub.u is, preferably, 160 bits long, and where x.sub.u
is used to sign (authenticate) the public signature key of the escrow
certification authority and the public family key; <BR>
<BR>
e) x.sub.e, a secret key known only by the escrow certification authority,
where x.sub.e is, preferably, 160 bits long, and where x.sub.e is used to
sign (authenticate) device unique public keys which are properly escrowed
with escrow agents and the public family key; <BR>
<BR>
f) x.sub.f, a secret family key, where x.sub.f is, preferably, 160 bits long
and known only by the third party, and where x.sub.f is used by the third
party to decrypt an access field generated by the sender to recover the
identification (ID.sub.i) of a particular device of the present invention;
<BR>
<BR>
g) Y.sub.u, the universal public key, where Y.sub.u =(g**x.sub.u)mod p, where
Y.sub.u is known by all users, and where Y.sub.u is used to verify a signature
on the escrow certification public key and public family key; <BR>
<BR>
h) Y.sub.e, the escrow certifier's public key, where Y.sub.e =(g**x.sub.e)mod
p, and where Y.sub.e is used to verify a signature on the device unique public
key, device unique identification, and the public family key; <BR>
<BR>
i) Y.sub.f, the public family key, where Y.sub.f =(g**x.sub.f)mod p, where
Y.sub.f is used in the process of encrypting the sender's access field;
<BR>
<BR>
j) Tag, an identification field in the sender's access field, where the Tag
is, preferably, 32 bits long, where the Tag is used to identify the holder
of the family key, the holder of the escrow keys, and the length of the sender's
access field, where a portion of the Tag, preferably, the first 16 bits,
would identify the holders of the keys while another portion of the Tag,
preferably, the last sixteen bits, identify the length of the sender's access
field; <BR>
<BR>
k) k.sub.e, a secret random number, where k.sub.e is used to generate the
escrow certifier's signature, preferably 160 bits long, known only by the
holder of the universal secret (master) key; <BR>
<BR>
l) r.sub.e, half of an escrow certifier's signature, where r.sub.e
=((g**k.sub.e)mod p)mod q, where r.sub.e is generated by the holder of the
universal secret (master) key and where r.sub.e is half of the escrow certifier's
signature; and <BR>
<BR>
m) s.sub.e, the other half of the escrow certifier's signature, where s.sub.e
=(k.sub.e- 1) (SHA(Y.sub.f
.vertline..vertline.Tag.vertline..vertline.Y.sub.e)+(x.sub.u) (r.sub.e))mod
q, and where s.sub.i is generated by the holder of the universal secret key.
<BR>
<BR>
The following information is unique to each user of the alternate embodiment
of the present invention: <BR>
<BR>
a) ID.sub.i, an identification number for device i, where ID.sub.i is,
preferably, 64 bits long, where a portion of ID.sub.i, preferably the first
24 bits, are used to identify the escrow agents and the family key, and where
another portion of ID.sub.i, preferably the last 40 bits, are used to store
the serial number of device i; <BR>
<BR>
b) x.sub.i1, a secret unique key for device i, where x.sub.i1 is, preferably,
160 bits long, and where x.sub.i1 is held by the first escrow agent;
<BR>
<BR>
c) x.sub.i2, a secret unique key for device i, where x.sub.i2 is, preferably,
160 bits long, and where x.sub.i2 is held by the second escrow agent;
<BR>
<BR>
d) Y.sub.i, a device unique public key for device i, where Y.sub.i =(g**
(x.sub.i1 +x.sub.i2) mod q )mod p, and where Y.sub.i is known by all users;
<BR>
<BR>
e) k.sub.i, a secret random number for device i, generated by the escrow
certifier, where k.sub.i is, preferably, 160 bits long, and where k.sub.i
is known only by the escrow certification authority; <BR>
<BR>
f) r.sub.i, one-half of the signature for device i, where r.sub.i
=((g**k.sub.i)mod p) mod q, and where r.sub.i is, preferably, created by
the escrow certifier; and <BR>
<BR>
g) s.sub.i, the other half of the signature for device i, where s.sub.i =(k.sub.i
-1) (SHA (Y.sub.f .vertline..vertline.Tag.vertline..vertline.ID.sub.i
.vertline..vertline.Y.sub.i)+(x.sub.e) (r.sub.i)) mod q, and where s.sub.i
is, preferably, created by the escrow certifier. <BR>
<BR>
The term "SHA" refers to a secure hash algorithm. Preferably, SHA follows
the secure hash standard adopted by the U.S. Government and published in
Federal Information Processing Standards Publication 180 (FIPS-180). FIPS-180
is incorporated by reference into the specification of the present invention.
<BR>
<BR>
Although it is preferred that the values Tag, Y.sub.e, Y.sub.f, r.sub.e,
s.sub.e, ID.sub.i, Y.sub.i, r.sub.i, and s.sub.i be stored in the device,
it is not necessary. These values may be transmitted to the device prior
to the creation of the sender's ciphertext and access field. If these values
are transmitted to the device instead of stored in the device, the two signatures
(i.e., (r.sub.e, s.sub.e) and (r.sub.i, s.sub.i)) must be verified prior
to creating the sender's ciphertext and access field. <BR>
<BR>
FIG. 7 is a flow chart of the steps that a sender must perform to send an
encrypted message and an access field to a recipient. These steps are as
follows: <BR>
<BR>
(a) the sender knows p, q, g, Y.sub.i, Y.sub.f, f, h, r.sub.i, s.sub.i, first
pad, second pad, and Tag; <BR>
<BR>
(b) the sender and recipient know the session key (sk), where sk may be agreed
upon by, or given to, the sender and recipient, and where sk is, preferably,
80 bits long; <BR>
<BR>
(c) generate a random number, preferably, 64 bits long, and designate it
as the initialization vector (IV); <BR>
<BR>
(d) form m=f(IV,sk), where the function f maps IV and sk into an exponent
(i.e., m), where m is, preferably, 160 bits long; <BR>
<BR>
(e) form U=g.sup.m mod p, where U is, preferably, 1024 bits long; <BR>
<BR>
(f) form t=h((Y.sub.i **m)mod p), where t is the temporary device unique
key, where the function h maps a number into a key (i.e., t), where t is,
preferably, 80 bits long; <BR>
<BR>
(g) form w=h((Y.sub.f **m)mod p), where w is a temporary family key, and
where w is, preferably, 80 bits long; <BR>
<BR>
(h) form V=E.sub.w (IV,(ID.sub.i .vertline..vertline.Y.sub.i
.vertline..vertline.r.sub.i .vertline..vertline.s.sub.i
.vertline..vertline.E.sub.t (sk).vertline..vertline.first pad)), where the
function E, initialized by IV, encrypts the message in the nested patens
using the key in the subscript (i.e., w), where E.sub.t (sk) means to encrypt
sk using the key t, where any secure symmetric-key encryption device may
be used to perform the function E, where, preferably, V is 1536 bits long
and the first pad is 48 zeros; <BR>
<BR>
(i) form z-IV.vertline..vertline.second pad, where the second pad is, preferably,
16 zeros; <BR>
<BR>
(j) form sk*=E.sub.z (sk); <BR>
<BR>
(k) form ct=E.sub.sk* (IV, pt); where pt is the plaintext message to be
encrypted, and where ct is the resulting ciphertext (or encrypted message)
to be transmitted; <BR>
<BR>
(l) form the access field (i.e.,
Tag.vertline..vertline.IV.vertline..vertline.U.vertline..vertline.V), where
the access field is, preferably, 2656 bits long; and <BR>
<BR>
(m) transmit the ciphertext concatenated to the access field (i.e.,
ct.vertline..vertline.access field) to the receiver. <BR>
<BR>
FIG. 8 is a schematic of a public-key escrowed encryption system 91 that
a sender may use to send ct.vertline..vertline.access field to a recipient.
The sender is given p, q, f, h, g, Y.sub.i, Y.sub.i, IV, r.sub.i, s.sub.i,
ID.sub.i, Tag, a first pad, and a second pad. The sender may be given sk,
or the sender and recipient may agree on an sk. <BR>
<BR>
IV and sk are transmitted to a function block 92 via a first input 93 and
a second input 94, respectively. Function block 92 maps the sk and the IV
to an exponent m. In the preferred embodiment, sk is 80 bits long, IV is
64 bits long, and m is 160 bits long. Any function that uniquely maps a pair
of inputs to an output would satisfy the requirements of the function block
92. IV also forms a portion of the access field. <BR>
<BR>
The output 95 of the function block 92 is connected to one of the two inputs
of a first exponentiator 96, a second exponentiator 97, and a third exponentiator
98. Each of these exponentiators 96, 97, 98 may be realized with a conventional
multiplier and a scratch-pad memory device because exponentiation may be
achieved through a series of multiplications. For example, a.sup.23
=(((((((a.sup.2).sup.2)a).sup.2)a).sup.2)a). <BR>
<BR>
An element g of order q in GF(p) is transmitted via a second input 99 of
the third exponentiator 98. The output 100 of the third exponentiator 98
(i.e., U=g.sup.m mod p) forms the U portion of the access field.
<BR>
<BR>
Y.sub.i, the device unique public-key for device i, is transmitted to the
first exponentiator 96 via a second input 101. The output 102 of the first
exponentiator 96 (i.e., (Y.sub.i **m)mod p) is connected to a first hash
function block 103. The first hash function block 103 maps the output 102
of the first exponentiator 96 to a number (i.e., t=h((Y.sub.i **m) mod p)),
preferably 80 bits long, which appears at the output 104 of the first hash
function block 103. <BR>
<BR>
Y.sub.f, the public family key for device i, is transmitted to the second
exponentiator 97 via a second input 105. The output 106 of the second
exponentiator 97 (i.e., (Y.sub.f **m)mod p) is connected to a second hash
function block 107. The second hash function block 107 maps the output 106
of the second exponentiator 97 to a number (i.e., w=h((Y.sub.f **m) mod p)),
preferably 80 bits long, that appears at the output 108 of the second hash
function block 107. <BR>
<BR>
A first encryptor 109 is used to encrypt the session key sk. The first encryptor
109 may be realized by any secure symmetric-key encryption device. Such a
device is generally known by those skilled in the art. The first encryptor
109 has a first input 94 for receiving sk as plaintext, a second input connected
to the output 104 of the first hash function block 103 (i.e., t) as key,
and a ciphertext output 110 for transmitting the encrypted version of sk
(i.e., E.sub.t (sk)). <BR>
<BR>
Y.sub.i, E.sub.t (sk), ID.sub.i, (r.sub.i,s.sub.i), and a first pad, preferably
48 zeros, are transmitted to a processing block 114 via inputs 101, 110,
111, 112, and 113, respectively. The processing block 114 takes in various
inputs of varying lengths, concatenates the inputs into one string of bits,
and outputs a uniform block-size portion of the string. For example, the
processing block 114 might have five inputs with the following bit lengths
respectively, 64, 128, 192, 256, and 320. If the uniform block-size output
where to be 64 bits then the processing block would concatenate these five
inputs together and output fifteen 64-bit blocks. The processing block 114
may be realized with a commercially available microprocessor. The output
115 of the multiplexer block 114 transmits uniform block-size portions of
the concatenated inputs 101, 110, 111, 112, and 113 in serial fashion.
<BR>
<BR>
The output 115 of the processor block 114 is encrypted by a second encryption
block 116. The second encryption block 116 is essentially identical to the
first encryption block 109 except for an extra input that enables the second
encryption block 116 to be initialized. The initialization input of the secon
<P>
encryption block 116 is connected to the second input 93 of the function
block 92. A plaintext input to the second encryption block 116 is connected
to the output 115 of the processor block 114. A key input to the second
encryption block 116 is connected to the output 108 of the second hash function
block 107. The ciphertext output 117 of the second encryption block 116 is
connected to an output register 118 that is used to store
ct.vertline..vertline.access field. <BR>
<BR>
A "Tag," preferably 32 bits long, forms the Tag portion of the access field.
The Tag is transmitted to the output register 118 via input 119. <BR>
<BR>
IV and a second pad, preferably 16 zeros, are transmitted to a concatenation
block 120 via inputs 3 and 121, respectively. The concatenation block 120,
which may be realized with a shift-register, concatenates a pad of zeros
to the initialization vector IV. The output 122 of the concatenation block
120 forms z. <BR>
<BR>
A third encryptor 123 is used to encrypt the session key 94 using the output
122 of the concatenation block 120 as the key. The third encryptor 123 is
identical to the first encryptor 109. The third encryptor 123 has a first
input for receiving the output 122 of the concatenation block 120 as the
key, a second input 94 for receiving sk as plaintext, and an output 124 for
transmitting the encrypted version of sk (i.e., sk*=E.sub.z (sk)) as ciphertext.
<BR>
<BR>
A fourth encryptor 125 is used to encrypt the intended plaintext message
pt. The fourth encryptor 125 may or may not be identical to the second encryptor
116. The initialization input of the fourth encryption block 125 is connected
to the second input 93 of the function block 92. A plaintext input 126 receives
the sender's plaintext message to be encrypted. A key input to the fourth
encryption block 125 is connected to the output 124 of the third encryption
block 123. The ciphertext output 127 of the fourth encryption block 125,
which is the encrypted version of the plaintext message (i.e., ct=E.sub.sk*
(IV, pt)), is connect to the output register 118. <BR>
<BR>
The access field (i.e., IV, U, V, Tag) and ct are transmitted to the receiver
via an output 128 of the output register 118. <BR>
<BR>
FIG. 9 is a flow chart of the steps that a receiver must perform to recover
the plaintext from the sender's ciphertext and access field. These steps
are as follows: <BR>
<BR>
(a) the recipient knows p, q, g, Y.sub.f, f, h, a first pad, a second pad,
and sk used by the sender; <BR>
<BR>
(b) receive ct.vertline..vertline.access field from the sender; <BR>
<BR>
(c) recover Tag, IV, U, and V from the access field; <BR>
<BR>
(d) form m=f(IV, sk), where m is, preferably, 160 bits long; <BR>
<BR>
(e) form U=g.sup.m mod p, where U is, preferably, 1024 bits long; <BR>
<BR>
(f) check to see if the result of step (e) matches the U recovered from the
access field in step (c), processing of the message stops if they do not
match; <BR>
<BR>
(g) form w=h((Y.sub.f **m)mod p), where w is a temporary family key, and
where w is, preferably, 80 bits long; <BR>
<BR>
(h) recover ID.sub.i, Y.sub.i, r.sub.i, s.sub.i, and E.sub.t (sk) from the
access field by decrypting V with w and IV (i.e., D.sub.w (IV, V)), where
any secure decryption device that can perform the inverse of the encryption
device used by the sender to create V can be used to perform the decryption;
<BR>
<BR>
(i) verify the (r.sub.i, s.sub.i) recovered in step (h) using the Tag recovered
in step (c), the ID.sub.i and Y.sub.i recovered in step (h), and the verification
method of U.S. Pat. No. 5,231,668, processing of the message stops if the
signature is not verified; <BR>
<BR>
(j) form t=h((Y.sub.i **m)mod p), using Y.sub.i recovered in step (h) and
verified in step (i); <BR>
<BR>
(k) recover sk by decrypting E.sub.t (sk) recovered in step (h) (i.e., sk=D.sub.t
(E.sub.t (sk)); <BR>
<BR>
(l) compare sk recovered in step (k) to sk known by the recipient, processing
of the message stops if they do not match; <BR>
<BR>
(m) form z=IV.vertline..vertline.second pad, where the pad is, preferably,
16 zeros; <BR>
<BR>
(n) form sk*=E.sub.z (sk); and <BR>
<BR>
(o) decrypt the ct received using sk* (i.e., pt=D.sub.sk*, (IV, ct)), to
recover the plaintext message (pt). <BR>
<BR>
FIG. 10 is a schematic of a public-key escrowed encryption system 140 that
a receiver of an access field.vertline..vertline.ct from a sender using the
device 91 of FIG. 8 may use to recover the sender's plaintext message. The
receiver is given p, q, f, h, g, Y.sub.f, and a first pad. The receiver may
be given sk, or the sender and receiver may agree on an sk. <BR>
<BR>
The access field.vertline..vertline.ct from the sender is received by the
receiver via input 141 to a serial-in parallel-out first shift-register 142.
The first shift-register 142 transmits the access field (i.e., IV, U, V,
Tag) and ct via outputs 143, 144, 145, 146, and 147, respectively. <BR>
<BR>
IV and sk are transmitted to a function block 148 via a first input connected
to the first output 143 of said first shift-register 142 and a second input
149, respectively. The function block 148 maps the sk and the IV to an exponent
m. In the preferred embodiment, sk is 80 bits long, IV is 64 bits long, and
m is 160 bits long. Any function that uniquely maps a pair of inputs to an
output would satisfy the requirements of the function block 148. <BR>
<BR>
The output 150 of the function block 148 is connected to each of the first
inputs of a first exponentiator 151, a second exponentiator 152, and a third
exponentiator 153. Each of these exponentiators 151, 152, 153 may be realized
with a conventional multiplier and scratch-pad memory device because
exponentiation may be achieved through a series of multiplications. For example,
a.sup.23 =(((((((a.sup.2).sup.2)a).sup.2)a).sup.2)a). <BR>
<BR>
An element g of order q in GF(p) is transmitted to the second exponentiator
152 via a second input 154. The output 155 of the second exponentiator 152
(i.e., U=g.sup.m mod p) is transmitted to the first input of a first comparator
156 so that the U generated by the second exponentiator 152 may be compared
to the U portion of the access field received. <BR>
<BR>
The second output 144 of the first shift-register 142 is connected to the
second input of the first comparator 156. The output 157 of the first comparator
156 indicates whether or not the U generated matches the U received. If they
match, processing proceeds. Otherwise, processing is halted. <BR>
<BR>
Y.sub.f, the public "family" key for device i, is transmitted to the first
exponentiator 151 via a second input 158. The output 159 of the first
exponentiator 151 (i.e., (Y.sub.f **m)mod p) is connected to a first hash
function block 160. The first hash function block 160 maps the output 159
of the first exponentiator 151 to a number (i.e., w=h((Y.sub.f **m) mod p)),
preferably 80 bits long, that appears at the output 161 of the first hash
function block 160. <BR>
<BR>
A first decryption block 162 is used to decrypt the V portion of the access
field received (i.e., V=E.sub.w (IV,(ID.sub.i .vertline..vertline.Y.sub.i
.vertline..vertline.r.sub.i .vertline..vertline.s.sub.i
.vertline..vertline.E.sub.t (sk).vertline..vertline.pad1)). V is decrypted
in order to recover the device identification (ID.sub.i), the public key
of the sender (Y.sub.i), the signature of the sender (r.sub.i, s.sub.i),
and the encrypted version of the session key (E.sub.t (sk)). The first decryption
block 162 may be realized by any secure symmetric-key decryption device that
is able to decrypt messages encrypted by the encryption blocks used by the
sender that have an initialization input. Such a device is generally known
by those skilled in the art. <BR>
<BR>
The initialization input of the first encryption block 162 is connected to
the first output 143 of the shift-register 142. The ciphertext input of the
first decryption block 162 is connected to the third output 145 of the
shift-register 142. The key input of the first decryption block 162 is connected
to the output 161 of the first hash function block 160. The output 163 of
the first decryption block 162 is connected to a storage device 170.
<BR>
<BR>
The storage device 170 stores the decrypted portions of V (i.e., the ID.sub.i
of the sender, Y.sub.i of the sender, the signature (r.sub.i,s.sub.i) of
the sender, and the encrypted version of the session key (E.sub.t (sk)) sent
by the sender). The storage device 170 transmits the ID.sub.i, Y.sub.i,
(r.sub.i,s.sub.i), and (E.sub.t (sk)), respectively, along the outputs 171,
172, 173, and 174 of the storage device 170. <BR>
<BR>
A signature verification block 175 is used to verify the signature transmitted
by the sender (i.e., (r.sub.i,s.sub.i)). The fourth output 146 (i.e., TAG)
of the first shift-register 142 is connected to the first input of the signature
verification block 175. The first output 171 of the storage device 170 is
connected to the second input of the signature verification block 175. The
second output 172 of the storage device 170 is connected to the third input
of the signature verification block 175. The third output 173 of the storage
device 170 is connected to the fourth input of the signature verification
block 175. Y.sub.f, the public family key for device i, is transmitted to
the fifth input of the signature verification block 182 via input 158. The
signature verification block 175 performs a verification method as disclosed
in U.S. Pat. No. 5,231,668, entitled DIGITAL SIGNATURE ALGORITHM. U.S. Pat.
No. 5,231,668 is hereby incorporated by reference into the specification
of the present invention. The output 176 of the signature verification block
175 indicates whether or not the signature has been verified. If the signature
is verified, processing continues. Otherwise, processing is halted.
<BR>
<BR>
Y.sub.i, the device unique public key for device i which appears at the second
output 172 of the storage device 170, is transmitted to the second input
of the third exponentiator 153. The output 177 of the third exponentiator
153 (i.e., (Y.sub.i **m) mod p) is connected to a second hash function block
178. The second hash function block 178 is identical to the first hash function
block 160. A temporary device unique key (i.e., t=h((Y.sub.i **m) mod p))
appears at the output 179 of the second hash function block 178. <BR>
<BR>
A second decryption block 180 is used to decrypt the encrypted session key
received from the sender (i.e., E.sub.t (sk)) in order to recover the sender's
session key. The second decryption block 180 is identical to the first decryption
block 162 with the exception that the second decryption block 180 does not
have an initialization input. The ciphertext input of the second decryption
block 180 is connected to the fourth output 174 of the storage device 170
for accepting E.sub.t (sk). The key input of the second decryption block
180 is connected to the output 179 of the second hash function block 178.
The sender's session key sk appears at the plaintext output 181 of the second
decryption block 180. <BR>
<BR>
A second comparator 182 is used to compare the sender's sk to the sk known
by the receiver. The second comparator 182 is functionally equivalent to
the first comparator 156. If the two session keys match, processing continues.
Otherwise, processing is halted. The output 181 of the second decryption
block 180 is connected to the first input of the second comparator 182. The
sk input 149 is connected to the second input of the second comparator 182.
The output 183 of the second comparator 182 indicates whether or not the
sk known to the receiver matches the sender's sk. <BR>
<BR>
A concatenator 184 is used to concatenate IV received from the sender with
a pad, preferably 16 zeros. The concatenator 184 may be realized with a
serial-in-parallel-out shift-register. IV is transmitted to the first input
of the concatenator 184 via the first output 143 of the shift-register 142.
The pad is transmitted to the concatenator 184 via the second input 185 of
the concatenator 184. The result (i.e., z=IV.vertline..vertline.pad) appears
at the output 186 of the concatenator 184. The output 186 of the concatenator
184 is used as the key to encrypt the session key sk. The resulting encrypted
session key sk* is used by the receiver to decrypt the sender's ciphertext
message. <BR>
<BR>
An encryption block 187 is used to encrypt the session key (sk) known by
the receiver. The encryption block 187 is identical to the encryption block
used by the sender to form the sender's working key (sk*). The encryption
block 187 has a plaintext input for receiving the sk known by the receiver
via input 149, a key input for receiving the key from the output 186 of the
concatenator 184, and a ciphertext output 188 for transmitting the encrypted
session key (i.e., sk*=E.sub.z (sk)). <BR>
<BR>
A third decryption block 189 must be able to decrypt the ciphertext message
sent by the sender to the receiver in order to recover the sender's plaintext
message. That is, the third decryption block 189 must be able to reverse
or undo the encryption performed by the fourth encryption block 125 of FIG.
8. The initialization input of the third decryption block 189 is connected
to the first output 143 of the shift-register 142. The ciphertext input of
the third decryption block 189 is connected to the fifth output 147 (i.e.,
the sender's ciphertext) of the shift-register 142. The key input of the
third decryption block 189 is connected to the output 188 of the encryption
block 187. The sender's plaintext message appears at the output 190 of the
third decryption block 189. <BR>
<BR>
FIG. 11 is a flow chart of the steps that a third party, under proper authority,
must perform to recover the sender's plaintext message. These steps are as
follows: <BR>
<BR>
(a) the third party knows p, q, g, Y.sub.f, x.sub.f, h, and D; <BR>
<BR>
(b) intercept the sender's ct.vertline..vertline.access field; <BR>
<BR>
(c) recover Tag, IV, V, and U from the access field; <BR>
<BR>
(d) identify the secret family key, x.sub.f, from the Tag; <BR>
<BR>
(e) form w=h((U**x.sub.f) mod p); <BR>
<BR>
(f) recover ID.sub.i, Y.sub.i, r.sub.i, s.sub.i, and E.sub.t (sk) from V
by decrypting V using w and IV (i.e., D.sub.w (IV, V)); <BR>
<BR>
(g) verify the (r.sub.i, s.sub.i) recovered in step (e) using the method
of U.S. Pat. No. 5,231,688; <BR>
<BR>
(h) identify the escrow agents from the Tag; <BR>
<BR>
(i) request x.sub.i1 from the first escrow agent and x.sub.i2 from the second
escrow agent using ID.sub.i ; <BR>
<BR>
(j) form x.sub.f =(x.sub.i1 +x.sub.i2)mod q; <BR>
<BR>
(k) form t=h((U**x.sub.i)mod p); <BR>
<BR>
(l) recover sk by decrypting E.sub.t (sk) using t formed in step (k) (i.e.,
D.sub.t)(E.sub.t (sk))); <BR>
<BR>
(m) form z=IV.vertline..vertline.second pad, where the second pad is, preferably,
16 zeros; <BR>
<BR>
(n) form sk*=E.sub.z (sk); and <BR>
<BR>
(o) recover the plaintext message by decrypting ct using sk* (i.e., D.sub.sk*
(IV, ct)). <BR>
<BR>
In a second alternate embodiment of the present invention, U and ID may be
given to the escrow agents. Therefore, instead of requesting x.sub.i1 and
x.sub.i2 from the escrow agents, the third party may request ((U**x.sub.i1)
mod p) from the first escrow agent and ((U**x.sub.i2) mod p) from the second
escrow agent. Instead of forming x.sub.i =(x.sub.i1 +x.sub.i2)mod q and
t=h((U**x.sub.i)mod p), the third party would form
t=h((U**x.sub.i1)(U**x.sub.i2)mod p). Processing would then continue as listed
above. In the second alternate embodiment, the escrow agent never reveals
the escrowed secret that is being held. Instead, the escrow agent would reveal
part of the temporary device unique key. This allows for a more secure escrow
system that may be used to incorporate time limits on the use of the temporary
device unique key. <BR>
<BR>
FIG. 12 is a schematic of a public-key escrowed encryption system 210 that
a third party may use to recover the plaintext of the sender's message if
the sender used the device 91 of FIG. 8 to generate the ciphertext.
<BR>
<BR>
The third party is initially given p, q, h, g, Y.sub.f, x.sub.f, and a second
pad. To recover the plaintext, the third party may request x.sub.i1 and x.sub.i2
from the escrow agents that may be holding these items. <BR>
<BR>
The access field.vertline..vertline.ct transmitted from the sender to the
receiver is intercepted by the third party via input 211 and transmitted
to a serial-in parallel-out shift-register 212. The shift-register 212 receives
a single serial transmission consisting of the access field.vertline..vertline.ct
(i.e., IV, U, V, Tag, and ct), separates these items, and transmits these
items in parallel fashion via outputs 213, 214, 215, 216, and 217, respectively.
<BR>
<BR>
The U output 214 of the shift-register 212 is connected to the first input
of a first exponentiator 218 and the first input of a second exponentiator
219. Each of these exponentiators 218, 219 may be realized with a conventional
multiplier and a scratch-pad memory device because exponentiation may be
achieved through a series of multiplications. For example, a.sup.23
=(((((((a.sup.2).sup.2)a).sup.2)a).sup.2)a). <BR>
<BR>
A secret family key x.sub.f is transmitted to the second input 220 of the
first exponentiator 218. The output 221 of the first exponentiator 218 (i.e.,
(U**x.sub.f) mod p) is connected to a first hash function block 222. The
first hash function block 222 maps the output 221 of the first exponentiator
218 to a number (i.e., w=h((U**x.sub.f) mod p)), preferably 80 bits long,
that appears at the output 223 of the first hash function block 222.
<BR>
<BR>
A first decryption block 224 is used to decrypt V from the access field (i.e.,
V=E.sub.w (IV,(ID.sub.i .vertline..vertline.Y.sub.i .vertline..vertline.r.sub.i
.vertline..vertline.s.sub.i .vertline..vertline.E.sub.t (IV, sk)
.vertline..vertline.pad1)). V is decrypted in order to recover the device
identification (ID.sub.i), the public key of the sender (Y.sub.i), the signature
of the sender (r.sub.i, s.sub.i), and the encrypted version of the session
key (E.sub.t (sk)). The first decryption block 224 may be realized by any
secure symmetric-key decryption device having an initialization input that
is able to decrypt messages encrypted by the encryption blocks used by the
sender which also have an initialization input. Such a device is generally
known by those skilled in the art. <BR>
<BR>
The initialization input of the first decryption block 224 is connected to
the first output 213 of the shift-register 212. The ciphertext input of the
first decryption block 224 is connected to the third output 215 (i.e., V)
of the shift-register 212. The key input of the first decryption block 224
is connected to the output 223 of the first hash function block 222. The
plaintext output 227 of the first decryption block 224 is connected to a
storage device 232. <BR>
<BR>
The storage device 232 stores the decrypted portions of V (i.e., the ID.sub.i
of the sender, Y.sub.i of the sender, the signature (r.sub.i,s.sub.i) of
the sender, and the encrypted version of the session key (E.sub.t (sk)) sent
by the sender). The storage device 232 transmits the ID.sub.i, Y.sub.i, (r.sub.i,
s.sub.i), and (E.sub.t (sk)), respectively, along the outputs 233, 234, 235,
and 236 of the storage device 232. The ID.sub.i is used by the third party
to determine if the message transmitted from the sender to the receiver is
of any interest to the third party. If so, processing continues. Otherwise,
processing is halted. <BR>
<BR>
A signature verification block 237 is used to verify the signature transmitted
by the sender (i.e., (r.sub.i,s.sub.i)). Y.sub.f, the public family key for
device i, is transmitted to the first input of the signature verification
block 237 via input 238. The TAG output 216 of the shift-register 212 is
connected to the second input of the signature verification block 237. The
first output 233 of the storage device 232 is connected to the third input
of the signature verification block 237. The second output 234 of the storage
device 232 is connected to the fourth input of the signature verification
block 237. The third output 235 of the storage device 232 is connected to
the fifth input of the signature verification block 237. <BR>
<BR>
The signature verification block 237 performs the verification method as
disclosed in U.S. Pat. No. 5,231,668, entitled DIGITAL SIGNATURE ALGORITHM.
The output 239 of the signature verification block 237 indicates whether
or not the signature has been verified. If the signature is verified, processing
continues. Otherwise, processing is halted. <BR>
<BR>
After determining the ID.sub.i of the sender, the third party asks each escrow
agent to provide a copy of their portion of the secret unique key for the
sender's device. For a system using two escrow agents, the two portions of
the secret unique key for the sender's device (i.e., x.sub.i1, x.sub.i2)
are transmitted, respectively, via a first input 240 and a second input 241
of a combiner block 242. The present invention is not limited to having two
escrow agents. Any number of escrow agents and escrow schemes may be used.
The combiner block 242 combines these two portions of the sender's secret
unique key and provides the combination at the output 243 of the combiner
block 242 (e.g., (x.sub.i1 +x.sub.i2) mod q). The combiner block 242 may
be realized using commercially available exclusive-or gates. <BR>
<BR>
The output 243 of the combiner block 242 is connected to the second input
of the second exponentiator 219. The first input of the second exponentiator
219 is connected to the U output 214 of the shift-register 212. The second
exponentiator 219 is identical to the first exponentiator 218. <BR>
<BR>
The output 244 of the second exponentiator 219 (i.e., (U**((x.sub.i1 +x.sub.i2)
mod q) mod p) is connected to a second hash function block 245. The second
hash function block 245 is identical to the first hash function block 222.
The second hash function block 245 produces a number (i.e., t), preferably
80 bits long, that appears at the output 246 of the second hash function
block 245. <BR>
<BR>
A second decryption block 247 is used to recover the sender's session key.
The second decryption block 247 is essentially identical to the first decryption
block 224. The second decryption block 247 does not have an initialization
input. The ciphertext input of the second decryption block 247 is connected
to the fourth output 236 of the storage device 232. The key input of the
second decryption block 247 is connected to the output 246 of the second
hash function block 245. The sender's session key appears at the plaintext
output 248 of the second decryption block 247. <BR>
<BR>
A concatenator 249 is used to concatenate IV received from the sender with
a pad, preferably 16 zeros. The concatenator 249 may be realized with a
serial-in-parallel-out shift-register. The IV output 213 of the shift-register
212 is connected to the first input of the concatenator 249. The pad is provided
via the second input 250 to the concatenator 249. The result (i.e.,
z=IV.vertline..vertline.pad) appears at the output 251 of the concatenator
249. The result is used as the key to encrypt the sender's session key recovered
by the second decryption block 247. The encrypted session key (sk*) was used
by the sender to encrypt the plaintext message and will be used by the receiver
to recover the sender's plaintext. <BR>
<BR>
An encryption block 252 is used to encrypt the sender's session key which
was recovered by the second decryptor 247. The encryption block 252 is identical
to the encryptor used by the sender to form the encrypted version of the
sender's session key (i.e., sk*). The encryption block 252 has a plaintext
input connected to the plaintext output 248 of the second decryption block
247, a key input connected to the output 251 of the concatenator 249, and
a ciphertext output 253 for transmitting the encrypted session key (i.e.,
sk*=E.sub.z (sk)). <BR>
<BR>
A third decryption block 254 is used to decrypt the ciphertext intercepted
from the sender and, therefore, recover the sender's plaintext message. The
third decryption block 254 is identical to the first decryption block 224.
The third decrypt ion block 254 has an initialization input connected to
the first output 213 of the shift-register 212, a ciphertext input connected
to the fifth output 217 (i.e., the sender's ciphertext message) of the
shift-register 212, and a plaintext output 256 at which appears the sender's
plaintext message (i.e., pt=E.sub.sk* (IV,ct)). <BR>
<BR>
<CENTER>
<B>* * * * *</B>
</CENTER>
<P>
<HR>
<CENTER>
</CENTER>
</BODY></HTML>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed