Cryptography
The focus is on issues such as criteria for systems and
protocols for usage. These are presumably long-term, in contrast,
to the set of existing public-key systems which is more volatile.
Thus we provide information which will hopefully be of use to
implementors of systems, but the frameworks we develop are
versatile enough to be relevant in a variety of settings. The
latter may include, for example, both electronic mail systems and
electronic fund transfer systems.
The core of this exposition is sections 1 to 5. Sections 1 to
3 cover the fundamentals of public-key cryptography and the relatedÔne-way functions.....................33
3.2.3 Weak and strong hash functions....................34
3.3 Digital signatures and certificate-based systems.........35
4. Examples of public-key systems and hash functions............37
4.1 The RSA public-key scheme................................39
4.1.1 Choice of p and q.................................41
4.1.2 Further notes on implementation...................42
4.1.3 Security of RSA...................................43Ôion protocols..........................67
5.3.5 Further notes.....................................71
5.4 DARPA-Internet...........................................71
6. A sample proposal for a LAN implementation...................73
6.1 Integration into a network...............................73
6.2 Security threats.........................................74
6.3 Security services........................................74
6.4 Security mechanisms......................................75
6.5 Criteria for cryptosystems...............................76
6.5.1 Security..........................................77
6.5.2 Numerical criteria................................77
6.5.3 Other criteria....................................78
6.6 Criteria for hash functions..............................78
6.7 Example of a LAN security framework......................78
6.7.1 Key management....................................79
6.7.2 Component generation and storage....................79
6.7.3 Secret-key generation.............................79
6.7.4 Issuance and distribution of certificates.........80
6.7.5 Compromised or invalidated certificates...........80
6.7.6 Authentication....................................81
Appendix A. Mathematical and computational aspects..............83
Ôtic sieve factoring algorithm................92
B.3.2 Computations in finite fields......................93
B.3.3 Other algorithms...................................94
B.4 Application-specific architectures.......................94
B.4.1 Systolic and wavefront arrays......................94
B.4.2 Proposal for a quadratic sieve machine.............95
B.4.3 Massively parallel machines........................95
Appendix C. The classical theory of computation.................97
C.1 Turing machines..........................................97
C.2 Nondeterministic Turing machines.........................98
C.3 Computational complexity.................................99
Appendix D. The theory of probabilistic computing..............101
Appendix E. Breaking knapsacks.................................103
Appendix F. Birthday attacks...................................105
Appendix G. Modular arithmetic and Galois fields...............107
G.1 The Euler Phi function..................................108
G.2 The Euler-Fermat Theorem................................108
G.3 Galois fields...........................................110
Appendix H. Euclid's algorithm.................................111
Appendix I. The Chinese Remainder Theorem......................113
Appendix J. Quadratic residues and the Jacobi symbol...........115
Ô26
Appendix M. Mathematics of RSA and other exponential systems...127
Appendix N. Quadratic residuosity modulo a composite...........129
N.1 Characterizing quadratic residues.......................129
N.2 The Jacobi symbol once more.............................130
N.3 Quadratic residuosity and factoring.....................132
N.4 Quadratic residuosity and Blum integers.................133
Appendix O. An introduction to zero-knowledge..................137
Appendix P. Alternatives to the Diffie/Hellman model...........143
P.1 Probabilistic encryption................................143
P.2 Identity-based schemes..................................145
References.....................................................147Ôwas
transmitted by a properly identified sender and is not a replay of
a previously transmitted message. Integrity refers to assurance
that a message was not modified accidentally or deliberately in
transit, by replacement, insertion or deletion. A fourth service
which may be provided is nonrepudiation of origin, i.e., protection
against a sender of a message later denying transmission. Variants
of these services, and other services, are discussed in [ISO-87].
Classical cryptography deals mainly with the secrecy aspect. It
also treats keys as secret. In the past 15 years two new trends
have emerged:
a. Authenticity as a consideration which rivals and sometimes
exceeds secrecy in importance.
b. The notion that some key material need not be secret.
The first trend has arisen in connection with applications such
as electronic mail systems and electronic funds transfers. In such
settings an electronic equivalent of the handwritten signature may
be desirable. Also, intruders into a system often gain entry by
masquerading as legitimate users; cryptography presents an
alternative to password systems for access control.
The second trend addresses the difficulties which have
traditionally accompanied the management of secret keys. This may
entail the use of couriers or other costly, inefficient and not
really secure methods. In contrast, if keys are public the task of
key management may be substantially simplified.
An ideal system might solve all of these problems concurrently,
i.e., using public keys; providing secrecy; and providing
authenticity. Unfortunately no single technique proposed to date
has met all three criteria. Conventional systems such as DES
require management of secret keys; systems using public key
components may provide authenticity but are inefficient for bulk
encryption of data due to low bandwidths.Ô-
key systems can be used for signatures and also for the
distribution of keys used in systems such as DES. Thus it is
possible to construct hybrids of conventional and public-key
systems which can meet all of the above goals: secrecy,
authenticity and ease of key management.
For surveys of the preceding and related topics see, e.g.,
([BRAS88],[COPP87],[DENN83],[DIFF82],[DIFF79],[KLIN79],[KONH81],
[LEMP79],[MASS88],[MERK82],[POPE78],[POPE79],[SALO85],[SIMM79]).
More specialized discussions of public-key cryptography are given,
e.g., in ([DIFF88],[LAKS83],[MERK82b]). Mathematical aspects are
covered, e.g., in ([KRAN86],[PATT87]).
In the following, E and D represent encryption and decryption
transformations, respectively. It is always required that D(E(M))
= M. It may also be the case that E(D(M)) = M; in this event E or
D can be employed for encryption. Normally D is assumed to be
secret, but E may be public. In addition it may be assumed that E
and D are relatively easy to compute when they are known.
1.1 Requirements for secrecy.
Secrecy requires that a cryptanalyst (i.e., a would-be intruder
into a cryptosystem) should not be able to determine the plaintext
corresponding to given ciphertext, and should not be able to
reconstruct D by examining ciphertext for known plaintext. This
translates into two requirements for a cryptosystem to provide
secrecy:
a. A cryptanalyst should not be able to determine M from
E(M); i.e., the cryptosystem should be immune to
ciphertext-only attacks.
b. A cryptanalyst should not be able to determine D given
{E(Mi)} for any sequence of plaintexts {M1,M2,...};
i.e. the cryptosystem should be immune to known-plaintext
attacks. This should remain true even when the
cryptanalyst can choose {Mi} (chosen-plaintext attack),
including the case in which the cryptanalyst can inspect
{E(M1),...,E(Mj)} before specifying Mj+1 (adaptive
chosen-plaintext attack).
Adaptive chosen plaintext attack is illustrated below.
Ôtext Attack
To illustrate the difference between these two categories, we
use two examples. First, suppose E(M) = M3 mod N, N = p * q, where
p and q are large secret primes. Then (cf. sec. 4) it is infeasible
for a cryptanalyst to determine D, even after inspecting numerous
pairs of the form {M,E(M)}. However, an eavesdropper who intercepts
E(M) = 8 can conclude M = 2. Thus a ciphertext-only attack may be
feasible in an instance where known- or chosen-plaintext attack is
not useful.
On the other hand, suppose E(M) = 5M mod N where N is secret.
Then interception of E(M) would not reveal M or N; this would
remain true even if several ciphertexts were intercepted. However,
an intruder who learns that E(12) = 3 and E(16) = 4 could conclude
N = 19. Thus a known- or chosen-plaintext attack may succeed whereÔor the recipient of a message to
verify that it has not been modified in transit.
These requirements are independent of secrecy. For example, a
message M could be encoded by using D instead of E. Then assuming
D is secret, the recipient of C = D(M) is assured that this message
was not generated by an intruder. However, E might be public; C
could then be decoded by anyone intercepting it.
A related service which may be provided is nonrepudiation; i.e.,
we may add a third requirement if desired:
c. A sender should not be able to deny later that he sent a
message.
We might also wish to add:
d. It should be possible for the recipient of a message to
detect whether it is a replay of a previous transmission.
Ôed in detail here, except to contrast it
with other ciphers. It is a block cipher, operating on 64-bit
blocks using a 56-bit key. Essentially the same algorithm is used
to encipher or decipher. The transformation employed can be written
P-1(F(P(M))), where P is a certain permutation and F is a certain
function which combines permutation and substitution. Substitution
is accomplished via table lookups in so-called S-boxes.
The important characteristics of DES from the standpoint of this
exposition are its one-key feature and the nature of the operations
performed during encryption/decryption. Both permutations and table
lookups are easily implemented, especially in hardware. Thus
encryption rates exceeding 40 Mbit/sec have been obtained (e.g.,
[BANE82],[MACM81]). This makes DES an efficient bulk encryptor,
especially when implemented in hardware.
The security of DES is produced in classical fashion:
alternation of substitutions and permutations. The function F is
obtained by cascading a certain function f(x,y), where x is 32 bits
and y is 48 bits. Each stage of the cascade is called a round. A
sequence of 48-bit strings {Ki} is generated from the key. Let L(x)
and R(x) denote the left and right halves of x, and let XOR denote
exclusive-or. Then if Mi denotes the output of stage i, we have
L(Mi) = R(Mi-1),Ô) = MK mod p.
Now the condition GCD(K,p-1) = 1 implies (lem. G.1) that we can
find I with I * K ÀÀ 1 (mod p-1). Note that I is not a separate key;
I is easily derived from K or vice-versa (app. H). We may set
D(C) = CI mod p.
It may then be shown (cor. G.2.3) that D(E(M)) = M, as required.
Furthermore, E(D(C)) = C as well; i.e., E and D are inverse
functions. This makes exponentiation a versatile cipher; in
particular, we can encipher with D as well as E. Later we will note
that this can be useful in authentication. However, Pohlig and
Hellman used the above only as an example of a conventional
cryptosystem. That is, since I is easily derived from K, both E and
D are generated by the single, secret, shared key K. In section 4.1
we will see that if p were replaced by a product of two primes,
derivation of I from K would be non-trivial. This would cause the
key material to be split into two portions.
Despite the relative simplicity of the definitions of E and D,
they are not as easy to compute as their counterparts in DES. This
is because exponentiation mod p is a more time-consuming operation
than permutations or table lookups if p is large.
Security of the system in fact requires that p be large. This
is because K should be nondeterminable even in the event of a
known-plaintext attack. Suppose a cryptanalyst knows p, M, C, and
furthermore knows that C = MK mod p for some K. He should still be
unable to find K; i.e., he should not be able to compute discrete
logarithms modulo p. At present there are no efficient algorithmsÔhms in GF(pn) is also
easier. The case of small n is treated in [ELGA85b]. The greatest
progress has been made for the case p = 2 (e.g.,
[BLAK84],[COPP84]). In [COPP84] it is shown that discrete
logarithms in GF(2n) can be computed in time
exp(c * n1/3 * (log n)2/3).
For a survey of the discrete logarithm problem see, e.g.,
[ADLE86],[COPP87],[MCCU89],[ODLY84b].
1.6 Public-key cryptosystems.
The notion of public-key cryptography was introduced by Diffie
and Hellman [DIFF76b]; for a history see [DIFF88]. Public-key
systems, also called two-key or asymmetric [SIMM79], differ from
conventional systems in that there is no longer a single secret key
shared by a pair of users. Rather, each user has his own key
material. Furthermore, the key material of each user is divided
into two portions, a private component and a public component. The
public component generates a public transformation E, and the
private component generates a private transformation D. In analogy
to the conventional case E and D might be termed encryption and
decryption functions, respectively. However, this is imprecise: in
a given system we may have D(E(M)) = M, E(D(M)) = M, or both.
A requirement is that E must be a trapdoor one-way function.
One-way refers to the fact that E should be easy to compute from
the public key material but hard to invert unless one possesses the
corresponding D, or equivalently, the private key material
generating D. The private component thus yields a "trapdoor" which
makes the problem of inverting E seem difficult from the point of
view of the cryptanalyst, but easy for the (sole legitimate)
possessor of D. For example, a trapdoor may be the knowledge of the
factorization of an integer (see sec. 4.1).
We remark that the trapdoor functions employed as public
transformations in public-key systems are only a subclass of the
class of one-way functions. The more general case will be discussedÔ and D in public-
key systems has no analogue in a conventional cryptosystem: in the
latter, both EK and DK are parameterized by a single key K. Hence
if EK is known then it may be assumed that K has been compromised,
whence it may also be assumed that DK is also known, or vice-
versa. For example, in DES, both E and D are computed by
essentially the same public algorithm from a common key; so E and
D are both known or both unknown, depending on whether the key has
been compromised.
1.6.1 Secrecy and authenticity.
To support secrecy, the transformations of a public-key system
must satisfy D(E(M)) = M. Suppose A wishes to send a secure message
M to B. Then A must have access to EB, the public transformation of
B (note that subscripts refer to users rather than keys in this
context). Now A encrypts M via C = EB(M) and sends C to B. On
receipt, B employs his private transformation DB for decryption;
i.e., B computes DB(C) = DB(EB(M)) = M. If A's transmission is
overheard, the intruder cannot decrypt C since DB is private. Thus
secrecy is ensured. However, presumably anyone can access EB; B has
no way of knowing the identity of the sender per se. Also, A's
transmission could have been altered. Thus authenticity and
integrity are not assured.
To support authentication/integrity, the transformations in a
public-key system must satisfy E(D(M)) = M. Suppose A wishes to
send an authenticated message M to B. That is, B is to be able to
verify that the message was sent by A and was not altered. In this
case A could use his private transformation DA to compute C = DA(M)
and send C to B. Now B can use A's public transformation EA to find
EA(C) = EA(DA(M)) = M. Assuming M is valid plaintext, B knows that
C was in fact sent by A, and was not altered in transit. This
follows from the one-way nature of EA: if a cryptanalyst, starting
with a message M, could find C' such that EA(C') = M, this would
imply that he can invert EA, a contradiction.
If M, or any portion of M, is a random string, then it may be
difficult for B to ascertain that C is authentic and unaltered
merely by examining EA(C). Actually, however, a slightly more
complex procedure is generally employed: an auxiliary public
function H is used to produce a digital signature S = DA(H(M))
which A sends to B along with M. On receipt B can compute H(M)
directly. The latter may be checked against EA(S) to ensure
authenticity and integrity, since once again the ability of a
cryptanalyst to find a valid S' for a given M would violate the
one-way nature of EA. Actually H must also be one-way; we return to
this subject in section 3.2.
Sending C or S above ensures authenticity, but secrecy isÔy.
In actuality there are no common systems versatile enough for
the last usage without modification. In fact there is only one
major system (RSA) which satisfies E(D(M)) = D(E(M)) = M. The lack
of a common domain between two users creates a technical problem
in using such a system for secrecy and authenticity. We discuss
some approaches to this problem in section 4.1.
If the question of domains is ignored, the usage of a system
satisfying E(D(M)) = D(E(M)) = M with a hash function H is
illustrated below. There EA,DA,EB,DB are the public transformations
of A and B, respectively.
A: B:
____________________ _________________
| | _____\| |
| compute H(M) | /|\ /| receive (C,S) |
|____________________| | |_________________|
| | |
| | |
________\|/_________ | _________\|/_________
| | | | |
| compute C = EB(M) | | | compute M' = DB(C) |
|____________________| | |_____________________|
| | |
| | |
_________\|/__________ | _________\|/_________Ô | |
\|/________________\|
/
Figure 2. Using Public-Key for Secrecy and Authenticity
1.6.2 Applicability and limitations.
The range of applicability of public-key systems is limited in
practice by the relatively low bandwidths associated with public-
key ciphers, compared to their conventional counterparts. It has
not been proven that time or space complexity must necessarily be
greater for public key systems than for conventional systems.
However, the public-key systems which have withstood cryptanalytic
attacks are all characterized by relatively low efficiency. For
example, some are based on modular exponentiation, a relatively
slow operation. Others are characterized by high data expansion
(ciphertext much larger than plaintext). This inefficiency, under
the conservative assumption that it is in fact inherent, seems to
preclude the use of public-key systems as replacements for
conventional systems utilizing fast encryption techniques such as
permutations and substitutions. That is, using public-key systems
for bulk data encryption is not feasible, at least for the present.
On the other hand, there are two major application areas for
public-key cryptosystems:
a. Distribution of secret keys.
b. Digital signatures.
The first involves using public-key systems for secure and
authenticated exchange of data-encrypting keys between two parties
(sec. 2). Data-encrypting keys are secret shared keys connected
with a conventional system used for bulk data encryption. This
permits users to establish common keys for use with a system such
as DES. Classically, users have had to rely on a mechanism such as
a courier service or a central authority for assistance in the key
exchange process. Use of a public-key system permits users toÔonvenience and robustness.
Digital signatures are a second major application (sec. 3). They
provide authentication, nonrepudiation and integrity checks. As
noted earlier, in some settings authentication is a major
consideration; in some cases it is desirable even when secrecy is
not a consideration (e.g., [SIMM88]). We have already seen an
example of a digital signature, i.e., when A sent DA(M) to B. This
permitted B to conclude that A did indeed send the message. As we
will note in section 3, nonrepudiation is another property
desirable for digital signatures. Public key cryptosystems provide
this property as well.
No bulk encryption is needed when public-key cryptography is
used to distribute keys, since the latter are generally short.
Also, digital signatures are generally applied only to outputs of
hash functions (sec. 3). In both cases the data to be encrypted or
decrypted is restricted in size. Thus the bandwidth limitation of
public-key is not a major restriction for either application.
2. Key management.
Regardless of whether a conventional or public-key cryptosystem
is used, it is necessary for users to obtain other users' keys. In
a sense this creates a circular problem: in order to communicate
securely over insecure channels, users must first exchange key
information. If no alternative to the insecure channel exists, then
secure exchange of key information presents essentially the same
security problem as subsequent secure communication.
In conventional cryptosystems this circle can be broken in
several ways. For example, it might be assumed that two users can
communicate over a supplementary secure channel, such as a courier
service. In this case it is often the case that the secure channel
is costly, inconvenient, low-bandwidth and slow; furthermore, use
of a courier cannot be considered truly secure. An alternative is
for the two users to exchange key information via a central
authority. This presumes that each user individually has
established a means of communicating securely with the central
authority. Use of a central authority has several disadvantages as
noted below.
In public-key systems the key management problem is simpler
because of the public nature of the key material exchanged between
users, or between a user and a central authority. Also,
alternatives to the insecure channel may be simpler; e.g., a
physical mail system might suffice, particularly if redundant
information is sent via the insecure (electronic) channel.
Ôkey is needed, at least
two communications involving the central authority are needed for
each pair of users. Furthermore, such a system may not be robust:
failure of the central authority could disrupt the key distribution
system.
Some of the disadvantages of a central authority can be
mitigated by distributing key distribution via a network of issuing
authorities. One possibility is a hierarchical (tree-structured)
system, with users at the leaves and key distribution centers at
intermediate nodes. However, distributing key management creates
a new security problem, since a multiplicity of entry points for
intruders is created. Furthermore, such a modification might be
inefficient unless pairs of users communicating frequently were
associated to a common subtree; otherwise the root of the tree
would be a bottleneck as before.
Another alternative is a key translation center which requires
only one key-encrypting key exchange through a certification
authority.
Some of these disadvantages can also be mitigated by a public-
key approach to key distribution.
2.2 Public distribution of secret keys.Ôeach number in
[1,p) can be expressed as gx mod p for some x. Both p and g may be
public.
To establish a common secret key, A chooses a random x(A) in
[0,p-1] and B chooses a random x(B) in [0,p-1]; these are kept
secret. Then A computes
y(A) = gx(A) mod p
while B computes
y(B) = gx(B) mod p.
These need not be secret. Finally A sends y(A) to B and B sends
y(B) to A. Now A knows x(A) and y(B) and can compute
K = y(B)x(A) mod p = gx(B)x(A).
Similarly, B knows x(B) and y(A) and can compute
K = y(A)x(B) mod p = gx(A)x(B).
The Diffie/Hellman algorithm is illustrated below.
Ô | |
| |
________\|/_________ ________\|/_________
| | | |
| compute K = yB**xA | | compute K = yA**xB |
|____________________| |____________________|
Figure 3. The Diffie/Hellman Key Exchange
This establishes K as a secret common quantity which can be used
in some agreed-upon fashion to generate a secret key. The secrecy
of this scheme depends, as in section 1.5, on the difficulty ofÔous section. If A thinks that EC is really EB then A might
encrypt using EC and inadvertently allow C to decrypt using DC. A
second problem is integrity: any error in transmission of a public
component will render it useless. Hence some form of error
detection is desirable.
Regardless of the scheme chosen for public component
distribution, at some point a central authority is likely to be
involved, as in conventional systems. However, it may not be
necessary for the central authority to be on-line; exchange of
public components between users need not involve the central
authority. An example of how this can be implemented is given in
section 2.5. We also note there that the implications of compromise
of the central authority are not as severe as in the conventional
case.
Validity is an additional consideration: a user's public
component may be invalidated because of compromise of the
corresponding private component, or for some other reason such as
expiration. This creates a stale-data problem in the event that
public components are cached or accessed through a directory.
Similar problems have been encountered in management of multi-
cache systems and distributed databases, and various solutions have
been suggested. For example, users could be notified immediately
of key compromises or invalidations. This may be impractical, in
which case either users should be informed within a given time
period of changes needed for cached information on public
components, or users should periodically check with a centralÔ user possess ECA, the public transformation of the CA.
Then each user A may register EA with the CA. Since EA is public,
this might be done via the postal service, an insecure electronic
channel, a combination of these, etc.
Normally A will follow some form of authentication procedure in
registering with the CA. Alternatively, registration can be handled
by a tree-structured system: the CA issues certificates to local
representatives (e.g., of employing organizations), who then act
as intermediaries in the process of registering users at lower
levels of the hierarchy. An example of such a system is given in
section 5.4.
In any case, in return A receives a certificate signed by the
CA (see sec. 3 for a more thorough discussion of signatures) and
containing EA. That is, the CA constructs a message M containing
EA,
identification information for A, a validity period, etc. Then the
CA computes CERTA = DCA(M) which becomes A's certificate. The
latter
is then a public document which both contains EA and authenticates
it, since the certificate is signed by the CA. Certificates can be
distributed by the CA or by users, or used in a hierarchical system
which we return to later. The inclusion of the validity period is
a generalization of timestamping. The latter was not treated in
[KOHN78], but Denning [DENN81] notes the importance of timestamping
in guarding against the use of compromised keys.
In general, the problem of stale data is not wholly solved by
timestamping: a certificate may be invalidated before its
expiration date, because of compromise or administrative reasons.
Hence if certificates are cached by users (as opposed to being re-
distributed by the CA each time they are used), the CA must
periodically issue lists of invalidated certificates. Popek and
Kline [POPE79] have noted that certificates are analogous to
capabilities in operating systems. Management of certificates
creates analogous problems, such as selective revocation of
capabilities. The public nature of certificates, however, a priori
precludes an analogue of a useful feature of a capability system:
users cannot be restricted to communicating with a subset of other
users. If a selective capability feature is desired it must be
implemented through a controlled distribution of certificates,Ôus disadvantage
to the ROM mode of hardware key storage, namely the fact that the
party which loads a private key to ROM could retain a copy. An
alternative, but still classical, scheme is for the user to be
provided with a means of writing to a memory chip and then sealing
it from further writing.
A more modern and more secure hardware adjunct is a smart token,
smart card or other device which contains both memory and a
microprocessor. Such a device can both generate and store user
keys. Ideally, it should be implemented via a single chip which
stores both cryptographic algorithms and data.
In the classical case, encryption and decryption are handled by
separate units in a hardware device acting as an interface between
a user's computer and the network. As noted in [DENN79], thisÔeady seen an example
of a public-key cryptosystem implementing public key distribution
in section 2.2. Both secrecy and authentication can be provided
simultaneously in the distribution process via public-key systems.
This may be achieved using a single public-key system if its
encryption and decryption functions are inverses, or via a hybrid
of two public key systems providing secrecy and authentication
separately.
The essence of this usage is very simple: a secret key is merely
a particular form of message. Assuming that a system has been
established for distribution of public components of users as
discussed in the previous section, users can then establish secret
keys at will by employing the public system for encryption and
signing of secret keys. Thus the latter can be exchanged or changed
without difficulty. This is in contradistinction to a system in
which secret keys must be established via couriers or a central
authority.
The use of public-key cryptography thus reduces the problem of
secret key distribution to the problem of binding user identities
and user public keys. The latter is a simpler problem in that no
communication of secret information is necessary. That is, users
can generate their own private/public key pairs and need not expose
their private keys to anyone, including themselves. However, it is
critical that user public keys be properly authenticated. This is
a nontrivial consideration in large networks.
Since only integrity and authenticity are considerations, usersÔion path. Such a path need not require
use of insecure channels if the nodes in the path can communicate
securely. For example, a user might register with a local
certifying authority in person. The local authority might be
affiliated with an organization and may be able to use the user's
organization ID to certify the user's public key. If the local
authority can communicate securely with the central authority, the
user's public key may then be forwarded to the central authority
for distribution.
Assuming that user public components can be certified and
distributed, two users may use each other's public components to
establish common keys for use in message encryption, again without
resort to a secure channel.
2.4.1 A protocol for key exchange.
Suppose A and B wish to establish a shared secret key. Suppose
further that they have obtained each other's public components.
Some possible modes for binding user public keys to user identities
and distributing certified user public keys are discussed in
sections 5.3.1 - 5.3.2 and 5.4.6. In any case, A may now generate
a secret key K. For example, this may be a key-encrypting key to
be used to exchange session keys and possibly initialization
vectors if, e.g., DES is used in cipher feedback mode or cipher
block-chaining mode [NATI80]. Then A might form an expanded message
which contains K and other data, which could include an
identification for A, a timestamp, a sequence number, a random
number, etc. This added material is needed for A to authenticate
himself to B in real-time, and thus prevent replays. For example,
Needham and Schroeder [NEED78] suggest a three-way handshake
protocol:
First of all A may send to B the message C = EB(RA,IDA), where
EB
is B's public transformation, IDA is the identification of A, and
RA is a random number. Now B can decrypt C and obtain IDA. Now B
generates a random number RB and sends C' = EA(RA,RB) to A. Upon
decryption of C', A can verify in real time that B has received RA,
since only B could decrypt C. Finally A sends C" = EB(RB) to B;
when
B decrypts C" he can verify in real time that A has received RB,
since only A could decrypt C'. Thus A and B are authenticated to
each other in real time; i.e., each knows that the other is really
there.Ô ________\|/________
| | | | |
| compute (RA,RB) = DA(M') | |/______| send M' to A |
|__________________________| \ |___________________|
| |
| |
_______\|/______ ________\|/_________
| | _____\| |
| verify RA | /|\ /| receive M" from A |
|________________| | |____________________|
| | |
| | |
_________\|/_________ | _________\|/__________
| | | | |
| compute M" = EB(RB) | | | compute RB = DB(M") |
|_____________________| | |______________________|Ôspectively. These contain EA and EB (or
equivalently,
the public components of A and B) as noted in section 2.3.1.
We may assume that A and B have cached CERTA and CERTB,
respectively. If A has exchanged certificates with B previously,
A and B may have each other's certificates cached. If not, then
there are two ways in which A could obtain B's certificate. The
simplest is for A to request B's certificate directly from B; this
is explored in the next section. The advantage of this simple
approach is that on-line access to a central authority is avoided.
On the other hand, if A requests B's certificate directly from
B, or obtains it from a directory listing, security and integrity
considerations arise. For example, the certificate A obtains may
have been recently invalidated.
Thus A may wish to access B's certificate through the CA,
assuming that the latter is on-line. In this event A requests CERTA
and CERTB from S. We recall that each CERT has the form DS(M) where
M contains an E. Thus when A receives the requested certificates,
he can validate CERTA by computing ES(CERTA) and recovering EA.
This
validates the source of the certificates, thus validating CERTB as
well. Hence A may retrieve a duly authenticated EB from CERTB. The
disadvantage is the requirement of an on-line central node; the
advantage is that A is assured of the instantaneous validity of theÔnnels with excellent
security. A second advantage is that distribution of certificates
by a central authority assures that certificates are valid at time
of receipt. A prerequisite for the proper functioning of such a key
management system is the existence of a system for binding user
public keys and identities. Such a system requires distributed
trust.
A disadvantage of this mode of management is that as in section
2.1, the central authority may be a bottleneck. The severity is
mitigated by the fact that a secure channel is not needed, but the
essential problem is similar.
A more significant disadvantage arises from the concentration
of trust in one entity [KLIN79]. The security of the central
authority might be compromised, e.g., by penetration. The fact that
the central authority does not generally access users' private
components means that existing messages are not compromised, as
might be the case in a secret-key system [DIFF82]. However, if an
intruder accesses the central authority's private component, the
intruder could forge certificates. Some scenarios for intrusions
of this sort, explorations of consequences, and means for
minimizing damage are explored in [DENN83b] and [DIFF88].
Merkle [MERK82b] has suggested a tree-structured system as a
means of coping with the compromise of a central authority.
However, this scheme is not practical for large networks since the
tree must be restructured each time the user population changes.
2.5.2 Decentralized management.
Users may be responsible for managing their own certificates.
In this event the protocol is much simpler. When A wishes to
initiate communication (e.g., exchange of a secret key) with B, he
sends a message to B containing A's certificate, A's
identification, and other information such as a date, random number
etc. as described in the protocol in the previous section. This
message also requests B's certificate. Upon completion of the
certificate exchange, employing some protocol such as the handshake
above, A and B will possess each other's authenticatedÔheme is clearly in question [KLIN79].
Phone-book entries might contain errors, or entries could be
altered.
3. Digital signatures and hash functions.
Digital signatures were introduced by Diffie and Hellman
[DIFF76b]; for surveys see, e.g., [AKL-83],[POPE79],[RABI78]. A
digital signature is the electronic analogue of a handwritten
signature. A common feature is that they must provide theÔryptography by
Diffie and Hellman [DIFF76b].
As we note below, hash functions are useful auxiliaries in this
context, i.e., in validating the identity of a sender. They can
also serve as cryptographic checksums (i.e., error-detecting
codes), thereby validating the contents of a message. Use of
signatures and hash functions can thus provide authentication and
verification of message integrity at the same time.
Numerous digital signature schemes have been proposed. As notedÔ not
have a unique signature. This scheme is intended to deflect
adaptive chosen-text attacks, in which an attacker is permitted to
use a signer as an oracle. In such an attack, the attacker
specifies a sequence of messages to be signed, and is able to study
all previous signatures before requesting the next. In the GMR
scheme, it can be proved that an attacker can gain no information
by studying any number of signatures no matter how they are
generated.
However, this security gain is offset to some extent by data
expansion (high ratio of signature to message size) and a negative
effect on nonrepudiation. As in the case of the one-time schemes
discussed earlier, the signatures generated in nondeterministic
public-key schemes tend to be large in comparison to signatures
produced by deterministic public-key schemes (i.e., those which
produce a unique signature for a given message). Adjudication of
disputes is made difficult by increased bookkeeping and the
necessity of storing large databases of messages and their
signatures.
In the following we discuss only deterministic public-key
signature schemes, in which a message has a unique signature.
3.1 Public-key implementation of signatures.
We have noted previously that, like secret-key systems, public-Ô. In the simplest
case, A simply signs a document M by sending S = DA(M) to B.
If a hash function H is used, A computes S = DA(H(M)) and sends
both M and S to B. B validates A's signature S by computing H(M)
= EA(S). We also noted earlier that because EA is a trapdoor one-
way function, it should not be possible for an intruder to find S'
such that H(M) = EA(S') for a given message M. Thus A's signature
cannot be forged. Also, if A attempts to repudiate the M sent to
B above, B may present M and S to a judge. The judge can access EA
and hence can verify H(M) = EA(S); assuming the trapdoor DA is
indeed secret, only A could have sent S. Thus a priori we have
nonrepudiation (but see below).
For both authenticity and secrecy, A could send
M' = EB(M,DA(H(M)))
to B; B computes
(M,DA(H(M))) = DB(M')
and then verifies that
H(M) = EA(DA(H(M))).Ô | | |
________\|/_________ | _________\|/_________
| | | | |
| send M' to B | | | verify H' = H(M) |
|____________________| | |_____________________|
| |
| |
\|/________________\|
/
Figure 5. A Protocol for Signing with Hash Function and Secrecy
For nonrepudiation in the last case, B retains DB(M') =
(M,DA(H(M))). A judge can apply EA to DA(H(M)) and compare to H(M).
This again assumes common domains for the E's and D's; in section
4.1 we will note an example of how this point may be treated in
practice. In passing we remark that the preceding schemes satisfy
another desirable property: in the adjudication process, they do
not compromise security by exposing private components to a judge.
3.1.2 The issue of nonrepudiation.
Nonrepudiation, i.e., preventing senders from denying they have
sent messages, is contingent upon users keeping their private
components secret (e.g., [NEED78],[POPE79]). In the above, if DA
should be compromised, then A might be able to repudiate messages
sent even before the compromise. On the other hand, as in the case
of lost or stolen credit cards, A may still be held liable for
messages signed before the compromise was reported to a centralÔs a header m = identifying information.
c. U computes S2 = DU(m,S1).
d. U sends m and S2 to A.
e. A applies EU to S2 and checks the identifying information
in m, thereby verifying the origin of M.
f. A computes M' = (m,S1,timestamp).
g. A computes S' = DA(M').
h. A sends S' to R.
As noted above, a copy of S' may also be sent to U.
As noted in [POPE78], this type of scheme violates a desirable
criterion for network protocols, namely point-to-point
communication. It also requires trusted software, which is
undesirable.
In [BOOT81] the use of a central authority is suggested for this
purpose. In this scheme, the receiver of a message sends a copy to
the central authority. The latter can attest to the instantaneous
validity of the sender's signature; i.e., that it has not been
reported that the sender's private component has been compromised
at the time of sending. The value of such testimony is mitigated
by the necessity of users rapidly reporting key compromise to the
central authority. Also, the central authority becomes a
bottleneck.
Another partial solution involves timestamps ([DENN81],
[MERK82b]). This again may involve a network of automated
arbitrators, but very simple in nature, since they need merely
timestamp messages. In contrast to the notary publics above,
however, in [MERK82b] it is suggested that receivers obtain
timestamps. If a receiver needs to be sure of the validity of a
signature, he may check the validity of the sender's private
component by checking with a central authority. As long as the
received message is timestamped before the validity check, theÔlidity checks and timestamps, which may
again create bottlenecks. Furthermore, such schemes require a
network-wide clock and are vulnerable to forgery of timestamps, as
noted in [BOOT81].
If users are permitted to change their components, a central
authority should retain past components for use in disputes which
may arise later. Neither compromise nor change of components of a
user should cause catastrophic problems in practice, since credit
card systems have established precedents for protocols, both
administrative and legal. For example, as noted above, conventions
have been established for treatment of cases of lost or stolen
credit cards; presumably analogous procedures could be established
for component compromise.
3.1.3 The issue of proof of delivery.
The literature on public-key protocols concentrates on the
issues of validity of signatures and the effects of key compromise
on nonrepudiation. However, DeMillo and Merritt [DEMI83] note that
the inverse of a signature, namely protection against the recipient
of a message denying receipt, may also be a desired feature of a
system. It is mentioned as an optional security service in [ISO-
87].
Both nonrepudiation and proof of delivery must be implemented
via adjudicable protocols, i.e., protocols which can be verified
later by a third party. In [DEMI83] it is noted that nonarbitrated
adjudicable reception protocols are difficult to design. A simple
handshaking protocol might proceed as follows:
a. A computes X = EB(DA(M)).
b. A sends X to B.
c. B computes M = EA(DB(X)).
d. B computes Y = EA(DB(M)).
e. B acknowledges receipt of M by sending Y to A.
If this protocol is standard procedure then A can assume
nonreception unless he receives acknowledgement from B. However,
to serve as an adjudicable proof-of-reception protocol, B is
required to acknowledge anything A sends. Then an intruder C couldÔ Y to A.
c. A thinks that this is a legitimate message from C,
unrelated to his communication with B. Following protocol:
c.1. A computes M' = EC(DA(Y)).
c.2. A computes Z = EC(DA(M')).
c.3. A acknowledges receipt of M' by sending Z to C.
d. C computes EB(DC(EA(DC(Z)))) = EB(DC(M')) = EB(DA(Y)) = M.
This of course occurs because of step c, in which A is required
by protocol to acknowledge M' = gibberish. This shows that such an
automatic protocol may be undesirable. On the other hand, selective
acknowledgement might have an adverse effect on adjudicability.
3.2 Hash functions and message digests.
We noted that public-key systems generally encrypt more slowly
than conventional ciphers such as DES. Other digital signature
schemes are also relatively slow in general. Furthermore, some
schemes produce signatures comparable in size to, and in some cases
larger than, the messages they sign. This results in data expansion
and effectively lower bandwidth of transmission. Thus it is usually
not desirable to apply a digital signature directly to a long
message. On the other hand, we remarked that the entire message
must be signed. This is seemingly contradictory, but a heuristic
solution can be obtained by using a hash function as an
intermediary.
A hash function H accepts a variable-size message M as input and
outputs a fixed-size representation H(M) of M, sometimes called a
message digest [DAVI80]. In general H(M) will be much smaller than
M; e.g., H(M) might be 64 or 128 bits, whereas M might be a
megabyte or more. A digital signature may be applied to H(M) in
relatively quick fashion. That is, H(M) is signed rather than M.
Both M and the signed H(M) may be encapsulated in another message
which may then be encrypted for secrecy. The receiver may validate
the signature on H(M) and then apply the public function H directly
to M and check to see that it coincides with the forwarded signed
version of H(M). This validates both the authenticity and integrity
of M simultaneously. If H(M) were unsigned only integrity would be
assured.Ôhe same digest as a given message. Thus, altering a message will
change the message digest. This is important to avoid forgery.
In many settings this minimal requirement is regarded as too
weak. Instead, the requirement is added that it should not be
possible to find any two strings which hash to the same value. We
return to the distinction between these two criteria in section
3.2.3.
3.2.1 Usage of hash functions.
In a public-key system augmented by a hash function H, A might
send a message M to B as follows: for simplicity ignore secrecy
considerations. Then A sends M and S = DA(H(M)) to B. The latter
uses EA to retrieve H(M) from S, then computes H(M) directly and
compares the two values for authentication. For nonrepudiation, B
retains M, H(M) and S. If A attempts to repudiate M, a judge can
use the three items to resolve the dispute as before: he computes
H(M) = EA(S) and recomputes H(M) from M. If B could find M' with
H(M') = H(M), B could claim A sent M'. A judge receiving M', H(M)Ôs well. For example, we noted earlier that the security of public-
key systems depends on the fact that the public transformations are
trapdoor one-way functions. Trapdoors permit decoding by
recipients. In contrast, hash functions are one-way functions which
do not have trapdoors.
The concept of (non-trapdoor) one-way functions originated in
connection with log-in procedures ([WILK68] p. 91): Needham noted
that if passwords were stored encrypted under a one-way function,
a list of encrypted passwords would be of no use to an intruder
since the original passwords could not be recovered. When a user
logged in, the string entered would be encrypted and compared to
the stored version for authenticity. Essentially the same system
was rediscovered later in [EVAN74].
Usage of one-way functions to produce message digests or encrypt
passwords is very different from use of trapdoor one-way functions
to generate encryption functions {EA} in a public-key cryptosystem.
In the latter, (d) above becomes a dichotomy: it is computationally
infeasible for anyone except A to find M from C = EA(M); but it is
easy for A, the unique holder of the trapdoor DA, to compute M =
DA(C).
Ôn is amenable to further refinement.
3.2.3 Weak and strong hash functions.
The security of hash functions can be refined further: we may
distinguish between weak and strong hash functions. A function
satisfying (a) - (e) of the previous section may be termed a weak
hash function. Property (e) characterizes weak hash functions; it
states that a cryptanalyst cannot find a second message producing
the same message digest as a fixed message. On the other hand, H
may be termed a strong hash function if (a) - (d) still hold, but
(e) is modified as follows: it is computationally infeasible to
find any {x1,x2} with H(x1) = H(x2).
Strong and weak functions may often be obtained from the same
class of functions. Strong functions are then characterized by
larger message digests, which reduce the probability of collisions.
Strong functions are thus more secure, but the longer message
digests are likely to increase time needed to hash.
Although the two definitions above are superficially similar,
computationally they are quite different. For example, suppose H
is a hash function with an 80-bit output. Suppose a cryptanalyst
starts with a fixed message M and wishes to find a second message
M' with H(M) = H(M'). Assuming that the 280 outputs of H are
totally
random, any candidate M' has a probability of only 2-80 of meeting
the required condition. More generally, if the cryptanalyst tries
k candidates, the probability that at least one candidate satisfies
H(M) = H(M') is 1-(1-2-80)k which is about 2-80k by the binomial
theorem if the latter is small. For example, the cryptanalyst will
probably have to compute H for about k = 274 = 1022 values of M' to
have even one chance in a million of finding one M' which collides
with M. Thus H is secure in the weak sense.
Suppose for the same H the cryptanalyst merely seeks any values
{M1,M2} with H(M1) = H(M2). By example F.1, if he examines H(M) for
at least 1.17 * 240 < 2 * 1012 random values of M, the probabilityÔllision exceeds 1/2. A supercomputer could
probably find M1 and M2 with H(M1) = H(M2) in at most a few days.
Thus H is not secure in the strong sense.
The latter attack is called a birthday attack (app. F). It
should be noted that finding a collision H(x) = H(y) gives the
cryptanalyst no valuable information if x and y are random bit
strings. For a purpose such as forgery an adversary may need to
generate a large number (e.g. 1012 above) of variations of a
message
to find two which collide. Inclusion of timestamps or sequence
numbers in messages, according to a fixed format, may make it
computationally infeasible to find a collision of use to an
adversary.
3.3 Digital signatures and certificate-based systems.
We previously noted that digital signatures can be employed for
authentication in the process of distributing public components in
public-key systems. In particular, if the system is certificate-
based, the central issuing authority can sign certificates
containing public components.
The notion of a central authority can be extended to a
hierarchical (tree) structure. The central authority serves as the
root of the tree; leaves represent users. Intermediate nodes may
also be users. Typically the intermediate nodes will be arranged
in several levels representing, e.g., organizations and
organizational units. Each node of the tree is responsible for
authenticating its children. Thus an authentication path is created
for each node, ending at the root. For example, the central
authority may certify an organization; the organization may certify
a unit; the unit may certify an individual user. Certification may
be accomplished by having a parent node sign a certificate for the
child node. To validate another user's certificate, a user may
request the entire authentication path.
It is also possible for the tree to be replaced by a forest. For
example, in a multinational system there may be a different tree
for each country. In this event the roots must certify each other.
An authentication path may then pass through two or more roots.
More generally, an authentication structure can be an arbitrary
directed graph, with a directed edge from A to B if A certifies B.
Then authentication paths may be constructed by conjoining directed
paths from two users to a common trusted node; an example of this
more complex structure is given in section 5.3.
4. Examples of public-key systems and hash functions.
Ôlman exponential
exchange scheme (sec. 2.2), public key distribution is supported
but authentication is not. Such systems may need augmentation by
a system which supports signatures. The only well-known system
discovered to date which is secure, practical and suitable for both
secrecy and authentication is described in section 4.1.
Category (b.2.3) above could in theory be further subdivided
into systems with relatively low and high bandwidths, but there are
no well-known examples with high bandwidths. There does not exist
a secure, practical system suitable for key distribution and
digital signatures, and with high enough bandwidth to support bulk
data encryption. Prospects for creating radically new systems seem
dim; in fact, as noted in [DIFF88], most of the extant systems are
based on a small number of hard mathematical problems:Ôhis has generated
systems (e.g. sec. 2.2) suitable for key distribution, and others
suitable for signatures (e.g. sec. 4.2.2).
Exploitation of the difficulty of factoring has proven to be the
most versatile approach to design of public-key systems. Factoring
is widely-regarded as very difficult. If a modulus has unknown
factorization, various problems in modular arithmetic become
difficult. For example, discrete logarithm ((b.2) above) is
difficult, as is taking roots (b.3) and deciding quadratic
residuosity (b.4). These problems have generated the most widely-
known public-key system (sec. 4.1) and various others. We remark
in passing that the probabilistic scheme mentioned in section 3 and
appendix P are based on (b.4); more generally, quadratic
residuosity forms the basis of many zero-knowledge schemes.Ô n,
D(C) = Cd mod n.
In the above, M and C are in [0,n-1]. As in section 1.5 we have
D(E(M)) = M and E(D(C)) = C; i.e. D and E are inverses. Since d is
private, so is D; and since e and n are public, so is E. This
constitutes a cryptosystem which can be used for both secrecy and
authentication. That is, for secrecy, A sends EB(M) to B as usual;
for authentication, A sends DA(M) as usual. For both secrecy and
authentication, suppose first that message digests are not
employed. Assuming nA ÀÀ nB, A computes
C = EB(DA(M))
and sends C to B. Then B recovers M as usual by
M = EA(DB(EB(DA(M)))).
This process is illustrated below:
Ô This implementation only works because the range of DA is a
subset of the domain of EB; i.e. [0,nA-1] is a subset of [0,nB-1].
In the event that nA ÀÀ nB, Kohnfelder [KOHN78b] notes that A can
instead transmit
C' = DA(EB(M)).
Then B can recover M as
M = DB(EA(DA(EB(M)))).
This works since the range of EB is a subset of the domain of
DA.
For adjudication of possible disputes, B must retain C' and M. Then
to prove that A sent M, the judge can compute EA(C') and EB(M) and
test for equality.
However, in [DAVI83] and [DENN83b] it is noted that there is aÔtion holds, compute the Jacobi symbol (a/b)
(app. J). Both GCDs and Jacobi symbols are easy to compute via
well-known algorithms (app. H,J). Now check to see if
(a/b) ÀÀ a(b-1)/2 (mod b).
If b is not prime, this check will fail with probability at
least 1/2 (app. L). Thus, if 100 random a's are tested and all pass
the above test, the probability of b not being prime is about 1 in
2100. Hence it is possible to test in polynomial time whether b is
probably a prime. The probability of b being prime is about 1 in
115; hence repeated applications of the preceding algorithm will
probably quickly yield b which is probably a prime. This can be
taken to be p; a second application of the algorithm will yield q.
The Solovay/Strassen algorithm is discussed further in appendix
L, which also mentions alternative algorithms of Lehman [LEHM82]
and Miller and Rabin ([MILL76],[RABI80]).
The advantage of such probabilistic algorithms is that the
algorithms run in polynomial time. They do not guarantee a correct
answer, but the possibility of error is negligible as noted above.
If absolute certainty were required, deterministic algorithms for
primality testing could be used ([ADLE83],[COHE87],[COHE84]). These
guarantee primality, but have runtimes of the formÔumber
of modular multiplications are needed. The condition GCD(e,m) = 1
presents no problem; in fact the probability that two random
numbers are relatively prime is about 3/5 ([KNUT81] p. 324). Now
d can be found in polynomial time; however, d may be large. Hence
a version of the Chinese Remainder Theorem is employed for
decryption (app. M).
There are some restrictions on p and q in addition to the size
specification mentioned above. Some of these are noted in section
4.1.3.1. Also, the time and space requirements of RSA are
considerably larger than, e.g., DES. Storage for each of p, q, and
d will require at least 300 bits; n is about 600 bits. Only e can
be chosen to be small.
Exponentiation mod n is a relatively slow operation for large
n, especially in software. Efficient algorithms for computing
products mod n have been given, e.g., in [BLAK83], [BRIC82],
[MONT85] and [QUIS82]. In particular, [BRIC82] shows how
multiplication mod n can be done in m+7 clock pulses if n is m
bits. In [MONT85] it is shown how modular multiplication can avoid
division.
At the present time RSA decryption (encryption is slower) with
a 508-bit modulus has been performed at about 225 Kbits/sec in
hardware [SHAN90]. Decryption with a 512-bit modulus has been
effected at about 11 Kbits/sec in software [DUSS90].
4.1.3 Security of RSA.
The security of the private components in the RSA cryptosystem
depends on the difficulty of factoring large integers. No efficient
algorithms are known for this problem. Consequently, knowing n = Ôcks are equivalent to taking roots modulo
a composite number with unknown factorization, i.e. solving C = Me
mod n for M. This is probably about as difficult as discrete
logarithms, even in the case of square roots (e.g., [ADLE86]). In
fact (lem. N.3.2; cf. [KNUT81] p. 389, [RABI79]), taking square
roots modulo such n is, loosely speaking, as hard as factoring n.
It should be noted that the security of RSA is not provably
equivalent to the difficulty of factoring or the other problems
mentioned here. Also, security of RSA or other public-key systems
does not preclude breaking specific protocols for their use; see
e.g. [MOOR88] or [DOLE81]. An example of a protocol failure is
given in [MOOR88]: suppose two users use a common modulus n and
encryption exponents e and e' with GCD(e,e') = 1. If the same
message M is sent to both, then let C = Me mod n and C' = Me' mod
n.
If both C and C' are intercepted, an intruder can find (app. H) r
and s with r * e + s * e' = 1; now M = Cr * C's mod n.
4.1.3.1 Restrictions on p and q.
There are two major restrictions on p and q in order to foil
attempts at factoring n = p * q:
a. p and q should be about the same length.
b. p and q should be at least 75 digits in length.
Present factoring methods will be foiled by such a choice. For
longer-term security, p and q should be, e.g., around 100 digits.
Condition (a) is needed against the elliptic curve method (see
below).
An attempt to predict the period of time for which a given
modulus length will remain secure is necessarily guesswork.
Intelligent guesses are the best that can be hoped for by
implementors; these are connected with the status of progress in
factoring, which is highly dynamic.
Ô sieve, Caron
and Silverman [CARO87] factored 90-digit integers in several weeks
on a network of several dozen Sun-3's. Recently, 106-digit integers
have been factored on a larger network [LENS89], using the multiple
polynomial variant of the quadratic sieve. Recent announcements of
work in progress indicate that integers of around 116 digits may
be factored shortly, using the same network used in the 106-digit
case and another variant of the quadratic sieve.
Pomerance, Smith and Tuler [POME88] discuss a prototype of a
special pipelined architecture, optimized for the quadratic sieve,
which they claim is extensible to a machine which might factor 125-
digit integers in a year. However, this presents no threat to 200-
digit moduli, since all of the best general-purpose factoring
algorithms known, including the quadratic sieve, run in time
roughly
exp(((log n)(log log n))1/2).
The fastest present computers only execute on the order of 1010
operations per second, at a cost of $10 million or more. Even if
a future computer reached 1012 operations per second (and
presumably
a cost exceeding $100 million) it would take on the order of 1000
years to factor a 200-digit number using existing algorithms.
The strongest results on factoring obtained to date have
utilized networks of computers. The power of such networks is more
difficult to extrapolate than for supercomputers, since they are
expandable and the power of personal computers and workstations has
been rising at a higher rate than at the supercomputer level. In
theory it would be preferable to know that a cryptosystem would be
immune to an attack by an assemblage of every computer in the
universe. It seems difficult to estimate the total amount of
computing power this would bring to bear; furthermore, the question
in practice is what fraction of this total amount can be
realistically allotted to a given factoring problem (cf. app. B).
It follows that implementors may have a high level of confidence
in 200-digit moduli at the present. An interesting issue at the
time of this writing is whether a modulus with a length between 150
and 200 digits will provide security for a given length of time.
It seems certain that 154-digit (i.e., 512-bit) integers will be
factored eventually, but the question is when. If the preceding
runtime estimate is used, the conclusion is that 154 digits is
likely to be secure until the late 1990s, barring major algorithmicÔ is oriented to integers whose
second-largest prime factor is considerably smaller than the
largest prime factor. This motivates the condition that an RSA
modulus should have factors roughly equal in size. A recent
algorithm, the number field sieve [LENS90], applies to integers of
the form rd + s or rd - s where r and s are small. Again this will
not affect properly-chosen RSA moduli.
4.1.4 Low-exponent versions of RSA.
A priori the encryption exponent e in the RSA scheme is
arbitrary. However, it need not be random. It has been suggested
that e be chosen to have a common value by all users of an RSA-
based system. Using e = 2 is not feasible per se, since 2 is not
relatively prime to p-1 or q-1. However, extensions of this type
have been made. These are of some theoretical interest, since Rabin
[RABI79] and Williams [WILL80] have noted modifications of RSA with
exponent 2 for which successful ciphertext-only attacks are
essentially as difficult as factoring the modulus (app. N).
The exponent 3 can be used directly with RSA. It has the
advantage of greatly simplifying the encryption (but not the
decryption) process. In fact Knuth [KNUT81], Rivest [RIVE84] andÔn1,n2,n3} is generated as a
product of two random primes, the probability of duplicates among
the 6 primes used is near zero. Hence it may be safely assumed that
the {ni} are pairwise relatively prime. Let Ci = M3 mod ni. Suppose
all 3 {Ci} are intercepted. Using the Chinese Remainder Theorem
(app. I), the intruder can find x in [0,n'), n' = n1 * n2 * n3,
with
x ÀÀ Ci (mod ni), i = 1,2,3. Thus x ÀÀ M3 (mod n'). But M3 < n', so
M3
= x, so M = x1/3 (ordinary cube root). Hence the plaintext M can be
easily recovered from the three ciphertexts. Thus the use of e =
3 or other small exponents makes RSA vulnerable to ciphertext-only
attacks. The sender may attempt to modify M for each recipient to
deflect this attack, but Hastad shows that more generally, a low
exponent is vulnerable to linear dependencies in portions of
messages.
4.2 Other public-key systems.
Several public-key systems other than RSA have been proposed.
These are briefly surveyed here. As noted earlier, most of these
are either insecure, of questionable practicality, or limited to
one of signatures/secrecy but not both. In some cases their
security and/or practicality has not been established. None of
these systems rivals RSA if a combination of versatility, security
and practicality is the criterion. However, this does not preclude
the use of the secure systems for specific applications such as
digital signatures.
4.2.1 Knapsack systems.
These were proposed by Merkle and Hellman [MERK78b]. However,
the essence is the use of NP-complete problems (e.g.,
[GARE79],[HORO78]) which had been suggested for use in designing
public-key systems in [DIFF76b]. The Merkle/Hellman approach was
to employ a superincreasing sequence {ai}, i.e., a sequence of
positive integers for which Ô the present
context the {Mi} are binary; thus the above reduces to sum-of-
subsets. Solving the above is easy for superincreasing {ai}; in
fact the solution is unique. However, even deciding existence of
a solution of sum-of-subsets, or more generally integer
programming, is NP-complete ([GARE79], pp. 223, 245). Now for any
w and u satisfying
u > a1 + ... + an,
GCD(u,w) = 1,
a disguised knapsack problem may be produced from {ai} by defining
bi = w * ai mod u.
Then the associated knapsack problem
C = b1 * M1 + ... + bn * Mn
appears to a cryptanalyst to be hard since the {bi} appear random.
In actuality, it is easily solved using the connection with the
{ai}: since GCD(w,u) = 1, there exists W (app. H) such that
w * W ÀÀ 1 (mod u).
Then
W * C ÀÀ a1 * M1 + ... + an * Mn (mod u).
Since 0 ÀÀ Mi ÀÀ 1,
Ôn (Appendix E).
It should also be noted that even if a knapsack approach proves
to be secure and practical, such schemes are generally limited to
support for either secrecy or authentication but not both. In
contrast to RSA, the encryption and decryption functions are not
inverses, although D(E(M)) = M. A trivial example suffices to show
this: suppose
E(M) = 2M1 + 3M2.
To be invertible a function must be both injective and
surjective. However, E is not surjective (onto). For example there
is no M such that E(M) = 1; hence D(1) is undefined. Thus we could
not employ D for signatures as in RSA, since, e.g., 1 could not be
signed by computing D(1).
4.2.2 The ElGamal signature scheme.
Ô A: B:
____________________ _________________
| | _____\| |
| choose k | /|\ /| receive (M,r,s) |
|____________________| | |_________________|
| | |
| | |
_________\|/__________ | __________\|/___________
| | | | |
| find I*k ÀÀ 1 mod p-1 | | | compute C = a**M mod p |
|______________________| | |________________________|
| | |
| | |
__________\|/___________ | _________\|/_________
| | | | |
| compute r = a**k mod p | | | compute C' = yA**r |
|________________________| | | * r**s mod p |
| | |_____________________|
| | |
| | |
__________\|/___________ | |Ôbe chosen for each M; using any k twice
determines x(A) uniquely. The security of the method then depends
mainly on the difficulty of computing discrete logarithms in GF(p):
suppose an intruder intercepts M, r and s; a and p are public. Let
d = ar mod p and u * rs ÀÀ 1 (mod p). Then the intruder knows
aM ÀÀ y(A)r * rs (mod p).
Hence
u * aM ÀÀ y(A)r (mod p).
Thus
dx(A) ÀÀ (ax(A))r ÀÀ y(A)r (mod p).
Finally
dx(A) ÀÀ u * aM (mod p).
Finding x(A), which permits the intruder to masquerade as A, is
thus equivalent to the above discrete logarithm problem. It is easy
to solve this problem if p-1 has only small factors [POHL78], hence
p-1 should have a large prime factor as in RSA. An alternative
approach is to seek k and m satisfying
M = r * x(A) + s * k + (p-1) * m,Ôon; it could also turn out that no
substantial advantage is gained by varying r and s simultaneously).
The use of message-dependent portions of components is a plus and
minus: it increases bookkeeping, and makes it more difficult for
a third party to adjudicate a dispute. On the other hand it may
produce greater security against certain types of attacks. In fact
the k above could be chosen differently for different blocks of one
message.
In passing we note that, like knapsacks, this scheme goes in one
direction only: we have in effect
M = E(r,s) = (x(A) * r + k * s) mod (p-1).
This maps the ordered pair (r,s) to a unique M. The condition
GCD(k,p-1) = 1 guarantees that an (r,s) can always be found; i.e.,
E is surjective. But it is not injective (one-to-one): e.g., if p
= 7, k = 5, x(A) = 5, then E(1,2) = E(2,1) = 3. Thus text M cannot
be represented uniquely by a pair (r,s), which would lead to
ambiguity in an attempt to use this scheme in two directions.
Also, ElGamal notes that extension to GF(pn) (app. G) is
feasible. However, it is not clear that extensions to finite fields
are desirable (cf. sec. 1.5); gains in efficiency may be offset by
lower security for comparable key sizes.
Ôons are keyless;
keys needed for DES are generated from the message to be hashed.
The hash functions are pre-certified in the sense that their
security can often be proven to be the same as that of the
underlying conventional function.
Merkle assumes that encryption in a system such as DES defines
a function EK, where K is a key, which produces a random output.
This is technically impossible, and in fact DES is not a random
function since it is a permutation. Nonetheless, small deviations
from randomness may be tolerable. Another requirement is that for
a given key/plaintext (or ciphertext) pair, the ciphertext (or
plaintext) returned will not vary with time. Normally a
cryptosystem would meet this criterion.
Assume that a function EK(M) is available which satisfies these
requirements. In deference to the potential use of DES to define
E, assume K is 56 bits, M is 64 bits, and EK(M) is 64 bits. Since
E may be assumed to be an encryption function, it may be assumed
that there exists a decryption function with EK(DK(C)) = C. This is
undesirable in producing one-way hash functions. This problem may
be mitigated as follows: given a 120-bit input x, write x =
CAT(K,M) where CAT denotes concatenation, K is the first 56 bits
of x, and M is the last 64 bits. Let
f(x) = EK(M) XOR M,
where XOR is exclusive-or. Then f hashes 120 bits to 64 bits.
Furthermore, Merkle claims that f produces a random output even if
x is chosen non-randomly. A strong one-way hash function, as
defined in section 3.2.3, meets this criterion. Thus f might be
termed a fixed-size strong one-way hash function, with "fixed-
size" referring to the fact that f does not accept arbitraryÔhe
probability of collisions produced when hashing becomes significant
when the number of items hashed is around the square root of the
total number of hash function values.
In section 3.2.3 we noted how such attacks affect the security
of hash functions. For example, a 64-bit output (i.e., 264 hash
values) would be vulnerable to an attack using only 232 = 4 billion
messages. On the other hand, a 112-bit output would require
exhaustive search of on the order of 256 values, producing a
security level comparable to DES. Merkle discusses several
constructions for producing an output exceeding 64 bits from f.
Only the simplest construction will be discussed here. Given an
input x of 119 bits, let
CAT(f(CAT("0",x)),f(CAT("1",x))) = CAT(y,z),
where y is 112 bits. Then define F0(x) = y. In the above, " "
denotes constant bit string. We note that F0 hashes 119 bits to 112
bits. This is not very efficient, but the 112-bit output will deter
a birthday attack. The latter would require 256 = 7*1016 messages,
which is computationally infeasible; more precisely, adequate
computing power to effect a birthday attack would also break DES,
thereby obliterating DES-based hash functions.
This produces F0 which is also a fixed-size strong one-way hash
function. Finally F0 is extended to a one-way hash function F
accepting inputs of arbitrary size by cascading copies of F0. Given
an input x, suppose
x = CAT(x1,...,xn),
where n is arbitrary and each xi is 7 bits (pad x with a few zeroes
if need be). Let
R0 = 0,
Ri = F0(CAT(Ri-1,xi)) (1 ÀÀ i ÀÀ n),
where in the first equation the right side is a string of 112
zeroes. Let F(x) = Rn.
Ôe the claim is
true for n. Suppose
zi = CAT(x1,...,xi) (1 ÀÀ i ÀÀ n+1),
x = zn+1,
zi' = CAT(x1',...,xi') (1 ÀÀ i ÀÀ n+1),
x ' = zn+1',
Ri = F0(CAT(Ri-1,xi)) (1 ÀÀ i ÀÀ n+1),
Ri' = F0(CAT(Ri-1',xi')) (1 ÀÀ i ÀÀ n+1),
where each xi and xi' is 7 bits. Suppose x ÀÀ x' but F(x) = F(x'),
i.e., Rn+1 = Rn+1'. Let y = CAT(Rn,xn+1) and y' = CAT(Rn',xn+1').
Then
F0(y) = F0(y'). If xn+1 ÀÀ xn+1' then y ÀÀ y' and F0 is broken.
Suppose
xn+1 = xn+1'. Then Rn = Rn'; but zn ÀÀ zn' since x ÀÀ x'. Now we
observe
that by definition Ri = F(zi) and Ri' = F(zi'). Hence F(zn) =
F(zn').
By the induction hypothesis, F0 can be broken, completing the
proof.
A disadvantage of this F is that it hashes 7 bits per stage of
the cascade, and each stage involves two DES calculations. Thus 3.5
bits are hashed per DES calculation. Merkle gives other
constructions which are more complicated but hash up to 17 bits per
application of DES.
4.3.2 Coppersmith's attack on Rabin-type functions.
The Merkle meta-method is an attempt to use a conventional
system as a generator for hash functions. This type of approach has
its origin in some predecessors which have been broken by
combinations of birthday attacks and meet-in-the-middle attacks as
formulated by Coppersmith [COPP85].
An early attempt to construct a hash function in support of
signature schemes was given by Rabin [RABI78]. Let H0 be random
(Rabin uses 0) and suppose a message M is divided into fixed-size
blocks M1,...,Mn. Suppose E(K,N) represents encryption of block N
with key K using a conventional system such as DES. For i = 1,..,nÔeach X he computes a trial Hn-1
of
the form
H(n-1,X) = E(X,Hn-2).
He sorts these 232 values and stores them. Now he generates 232
trial values Y. For each Y he computes a trial Hn-1 of the form
H'(n-1,Y) = D(Y,Hn),
where D is the decryption function corresponding to E. We note that
H(n-1,X) is the value that Hn-1 would have if Mn-1 = X, and H'(n-
1,Y) is the value Hn-1 would have if Mn = Y. Each time the opponent
tries a Y he searches through the sorted H-list (about 32
operations per search) and tries to find an X and Y with H(n-1,X)
= H'(n-1,Y). By the birthday phenomenon (app. F), the probability
of finding X and Y is at least 1/2. If X and Y are found, the
opponent has obtained a bogus message with the proscribed hash
value; furthermore this takes at most about 233 encryptions, 232
storage and 64 * 232 comparison operations. This effectively breaks
the scheme. Actually Coppersmith's attack was directed against a
refinement by Davies and Price [DAVI80]; Rabin's original scheme
had been broken earlier.
4.3.3 Quadratic congruential hash functions.
Another attempt to create hash functions, differing from both
Merkle- and Rabin-type constructions, was made by Jueneman
[JUEN82]. Unlike the Merkle meta-method this uses no external
system as an adjunct. It is not keyless; an initialization vector
is used. This limits the scope of usage; in particular, such a
function is useless for signature-only schemes. Nonetheless,
quadratic congruential constructions are simple and efficient, and
hence would be useful in some contexts if secure. Unfortunately it
seems as though Coppersmith's attack applies to these as well.Ô (231-1).
Then the hash value is Hn. Coppersmith broke this first scheme.
A revised scheme was proposed in [JUEN86]. The text is split into
128-bit blocks, which are further divided into 4 words. Recent
results suggest that this scheme may be insecure also. This is
especially unfortunate in light of the fact that a hash function
given in Annex D of X.509 [CCIT87] is defined similarly, via
Hi+1 = Mi + Hi2 mod n.
Recent work calls this into question as well.
4.4 Hardware and software support.
As noted earlier, RSA and similar exponentiation-based
algorithms suffer from relatively low bandwidths. At a minimum this
implies that supporting software needs to be carefully designed;
hardware support is probably a necessity in many settings. As noted
by Sedlak [SEDL87], bandwidths of less than 64 kbps (kilobits per
second) will degrade performance in many networks. Furthermore,
arithmetic modulo numbers of an adequate number of bits (at least
512) should be supported. Essentially the requirement is a chip (or
chip set) that can quickly compute quantities such as a mod b, ai
mod b, and perhaps multiplicative inverses or greatest common
divisors. As Sedlak notes further, a single chip is preferable for
security reasons. Since off-chip communication is slower than on-
chip, single-chip implementations should also yield higher
bandwidths.
4.4.1 Design considerations for RSA chips.
Some general tradeoffs in such design schemes are discussed by
Rivest [RIVE84]. He classifies architectures as serial (S),
serial/parallel (S/P), or parallel/parallel (P/P). He then notes
the following time and hardware costs:
Ô) gates on an S/P.
3. O(k log k) time and O(k2) gates on a P/P.
c. Key generation, k-bit primes:
1. O(k4) time and O(1) gates on an S.
2. O(k3) time and O(k) gates on an S/P.
3. O(k2 log k) time and O(k2) gates on a P/P.
This is a somewhat oversimplified version of [RIVE84] presented
only for comparison purposes. Also, there are two basic assumptions
used above: exponentiation is an inherently sequential process; and
the 100 or so primality tests used in key generation are done
sequentially. The first assumption seems intrinsic. However, the
second is pragmatic: the tests all use the same hardware, and
replicating the latter 100-fold for parallel execution would be
highly cost-ineffective. Rivest uses the above to give some sample
timings:
a. Decryption rate, 200-digit modulus:
1. 0.005 kbps on an S.
2. 1.3 kbps on an S/P.
3. 95 kbps on a P/P.
b. Key generation, 100-digit primes:
1. 1,200,000 ms = 20 minutes on an S.
2. 5,000 ms = 5 seconds on an S/P.
3. 70 ms on a P/P.
It may be seen that reasonably high bandwidths can be achieved,Ôal ciphering units, in 1.5 um CMOS. He also
claims a key generation time of 2 seconds. A 5,000-transistor, 5
um CMOS prototype has been realized.
In [BRIC89] it is noted that chips capable of up to 450 kbps are
being designed.
5. Implementations of public-key cryptography.
We examine here some existing implementations of public-key
cryptography, some implementations which are in progress, and some
which have been proposed.
5.1 MITRENET.
One of the earliest implementations of public-key cryptography
was in the MEMO (MITRE Encrypted Mail Office) system, a secure
electronic mail system for MITRENET ([SCHA82],[SCHA80]). MITRENET
is a broadband cable system with a bandwidth of 1 mbps. It uses a
carrier sense protocol (e.g., [TANE81]); i.e., each station can
sense transmissions of all other stations. In fact the protocol
requires all parties to monitor all communication, in effect
requiring passive eavesdropping. A priori this provides no secrecy,
authentication or integrity services. Furthermore it employs
distributed switching, creating a potential for active intrusion.
This is a good setting for a privacy enhancement testbed.
The MEMO system is a hybrid public/private cryptosystem. DES is
used for data encryption. The Diffie/Hellman exponential key
exchange of section 2.2 is used for establishment of secret keys.Ô the system.
Each user workstation establishes secure communication with the
Public Key Distribution Center. A session begins with the user
requesting the file of public keys from the PKDC. The request is
honored if it passes an identification test involving the user's
private component. The file of public keys is then downloaded to
the user's workstation, encrypted with DES to ensure integrity.
When the user sends a message to another user, the workstation
generates a random document key. The latter is used to DES-encrypt
the message. The public key of the recipient is used to generate
a key-encrypting key which is used to DES-encrypt the document key.
There is no provision for lost keys. Some provision is made for
detecting modifications to messages, using checksums. However, the
use of Diffie/Hellman alone does not permit authentication to be
introduced.
5.2 ISDN.
In [DIFF87] a testbed secure Integrated Services Digital Network
terminal developed at Bell-Northern Research is described. It can
carry voice or data at 64 kbps. Public-key cryptography is used for
both key exchange and authentication. Reference to the
Diffie/Hellman exponential key exchange is made. Evidently it is
used in conjunction with DES. The article also alludes to
signatures, but implementation is unclear.
As noted in [DIFF88], the use of public-key in conjunction with
DES provides good security. In particular, the exponential key
exchange permits a session key unique to each call. Thus if long-
term keys are compromised, recordings of calls made prior to
compromise cannot be decoded. In conventional systems the
compromise of a long-term key may compromise communications made
previously with derived keys.
Public key computations in the terminal are implemented via a
DSP (digital signal processing) chip, while an off-the-shelf
integrated circuit implements DES, which is used for data
encryption. Key management involves keys installed in phones,Ôtronically.
Each BNR terminal incorporates a Northern Telecom M3000
Touchphone.
5.2.1 Keys.
A public/private component pair is embedded in the phone; this
pair is called the intrinsic key. The private component is
contained in a tamper-resistant compartment of the phone. The
public component serves as the name of the phone. These cannot be
altered.
A second long-term public key stored in the phone is the owner
key. This is used to authenticate commands from the owner. It can
be changed by a command signed with the current owner key, thus
permitting transfer to a new owner.
A third long-term public key in the phone is the network key.
This identifies the network with which the phone is associated. It
validates commands signed with the private component of the
network's key management facility. It can authenticate calls from
network users. It can be changed by a command signed by the owner
key.
A short-term component pair stored in the phone is the working
pair. These are embodied in a certificate signed by the key
management facility. During the setup process for a call, phones
exchange certificates. The network key is used to authenticate
certificates. This permits station-to-station calls.
Further information is needed for authenticated person-to-
person calls. This information is contained on a hardware "ignition
key" which must be inserted into the phone. This key contains the
user's private component encrypted under a secret password known
only to the user. It also contains a certificate signed by the KMF
which contains the user's public component and identifying
information. The latter is encrypted as well. Decryption of the
information on the ignition key is effected via a password typed
on the telephone touchpad.
Further certificates authorizing users to use particular phones
are acquired by the phone from the key management facility; these
are cached and replaced in FIFO fashion.
5.2.2 Calling.
A person-to-person call begins as follows: the caller inserts
his ignition key and dials the number. The phone interrogates the
ignition key to check the caller's identity. The phone then checksÔhowever, it is specified in [CCIT87] that
a cryptosystem should be usable for both secrecy and authenticity.
That is, the encryption and decryption transformations should be
inverses, as is the case with RSA. Multiple cryptosystems and hash
functions may be used in the system.
A user must possess a distinguished name. Naming Authorities are
responsible for assigning unique names. The crux of the
authentication framework is the binding of user names and public
components. Assuming for the moment that such binding has occurred,
subsequent authentication in the ISO framework consists of locating
a chain of trusted points within the Directory. Such a chain exists
if there is a common point of trust between two authenticating
parties.
5.3.1 Use of certificates.Ôhis can be cached; e.g., a component pair could be stored on
a smart card along with the user's certificate and the CA's
certificate. Additionally, certificates are entered in the
Directory. The user may place a copy of the certificate in the
Directory, or the CA may be authorized to do this. A user's
Directory entry may contain multiple certificates. A CA's entry in
the DIT contains the certificates issued for it by other CAs, as
well as certificates it issues for other nodes.
Semi-formally a certificate may be defined as follows:
certificate ::=
{
signature algorithm identifier;
issuer name;
validity period;
subject name;
subject information
}
validity period ::=
{
start date;
finish date
}
subject information ::=
{
subject public key;Ôtended by recursion: in a certification path
A1,...,An,
knowing the public component of Ai permits recovery of the public
component of Ai+1 from the certificate for Ai+1 issued by Ai.
For a user A to obtain B's certificate involves finding a common
trusted point, i.e., a node which has certification paths to the
two users individually. Joining these two paths produces a
certification path between A and B. The paths, if they exist, may
be obtained from the Directory.
Although there is no restriction placed on the structure of the
authentication graph, an important special case is when it is tree-
structured. In this event the CAs are arranged hierarchically;
hence each node (except the root) has a unique CA (its parent in
the tree). Then each CA stores the certificate obtained from its
superior CA, as well as various certificates issued by it. The
common trusted point for a pair of users is the root of the DIT.
A user A may cache the certificates of nodes along the path from
A to the root. The other half of the path to another user B is
obtained by conjoining the path from the root to B.
More generally, a user A who communicates frequently with users
certified by a particular CA could store paths to and from that CA
(these may be different in the non-hierarchical case). Then to
communicate with a given user B certified by that CA, A need only
consult the directory entry for the CA and obtain the certificateÔanother's certificate to its directory entry.
5.3.3 Expiration and revocation of certificates.
When a certificate expires it should be removed from the
Directory. Expired certificates should be retained by the issuing
CAs for a period of time in support of the nonrepudiation service.
Revocation of certificates may occur because of component
compromise involving either the user or the issuing CA. Revocation
may also be necessary for administrative reasons, e.g., when a CA
is no longer authorized to certify a user. A CA keeps a time-
stamped list of revoked certificates which the CA had issued, and
a list of revoked certificates issued by other CAs certified by the
first CA. Entries for CAs in the Directory should contain
revocation lists for users and CAs.
5.3.4 Authentication protocols.
Suppose A wishes to engage in communication with an
authenticated B. Suppose further that A has obtained a
certification path from A to B, e.g., by accessing the Directory,
and has utilized the path to obtain B's public component. Then A
may initiate one-, two-, or three-way authentication protocols.
One-way authentication involves a single communication from A to
B. It establishes the identities of A and B and the integrity of
any communicated information. It also deflects replay in
communication of authentication information.
Two-way authentication adds a reply from B. It establishes that
the reply was sent by B and that information in the reply had
integrity and was not replayed. It also establishes secrecy of the
two communications. Both one-way and two-way authentication use
timestamps. Three-way authentication adds a further message from
A to B, and obviates the necessity of timestamps.
Let
ÔB,
RA = random number generated by A,
RB = random number generated by B,
CA = certification path from A to B.
Identities refer to the distinguished names of A and B. A
timestamp included in a message M includes an expiration date for
M. Optionally, it also may include the time of generation of M.
Random numbers may be supplemented with sequence numbers; they
should not be repeated within the expiration period indicated by
a timestamp in the same communication.
The one-way protocol is as follows:
a. A:
1. generates an RA.
2. constructs message M = (TA,RA,IB,) where
is
arbitrary. The latter may include data encrypted under
EB for secrecy, e.g., when A is sending a data-
encrypting key to B.
3. sends (CA,DA(M)) to B.
b. B:
1. decrypts CA and obtains EA. Also checks certificate
expiration dates.
2. uses EA to decrypt DA(M), verifying both A's signature
and the integrity of the signed information.
3. checks the IB contained in M for accuracy.Ô | |
| | |
_________\|/__________ | _________\|/_________
| | | | |
| compute M' = | | | compute (TA,RA,IB) |
| DA(TA,RA,IB) | | | = EA(M') |
|______________________| | |_____________________|
| | |
| | |
________\|/________ | _________\|/_________
| | | | |
| send (CA,M') to B | | | verify TA,RA,IB |
|___________________| | |_____________________|
| |
| |
\|/________________\|
/
Figure 8. One-Way Authentication Protocol
The two-way protocol is:
a. as above.
b. as above.
c. B:Ôn.
3. checks the IB contained in M for accuracy.
4. optionally, checks the RA in M for replay.
5. generates an RB.
6. constructs M' = (TB,RB,IA,RA,) where RA was
obtained previously; TB may be zero.
7. sends DB(M') to A.
Ômessages
to prevent replays and forgery.
Annex C of [CCIT87] mentions RSA as an example of a public-key
system. A recommendation of a 512-bit modulus is made. It is also
recommended that a common public exponent of e = 216 + 1 be used
(the fourth Fermat number). In particular it is noted that aÔting all
conceivable services would be inappropriate. One approach to the
design of a generic structure is layered, with a kernel consisting
of the most basic services and outer layers added as desired. This
is the paradigm we adopt here. The sample proposal presented here
is not unique, and is intended for illustration purposes only.
A hybrid of public-key cryptography and conventional
cryptography presents advantages. The former is used for signatures
and for distribution of secret keys used in the latter; the latter
is used for bulk data encryption. In addition, a hash function is
needed so that only a compressed form of long text need be signed.
We do not endorse specific public-key systems or hash functions.
The conventional system could be taken to be DES.ÔOSI model,
encryption can occur at various levels, including application,
presentation, network or transport. As noted in [ISO-87], the
appropriate level depends on desired granularity of protection. In
particular, high granularity refers to separate keys for each
application or user and assurance of integrity. For this
granularity the presentation or application layers are most
appropriate. These two layers will be assumed here. In particular,
integration at the application layer gives the individual user
complete control over the algorithms used.
6.2 Security threats.
Some basic security threats (cf. ann. A of [CCIT87]) include:
a. masquerade
b. replay
c. interception of data
d. manipulation of messages
Ôipt) of
a message.
The kernel of a proposed system would include basic support for
the above services. This kernel could be standardized to a large
extent. However, outer layers of an implementation would need to
interface with various external frameworks as well. For example,
a system is needed to bind user public components and user
identities; this forms an important part of the authentication
service. Also, support for nonrepudiation is a complex matter as
we have noted. A public-key signature system implements basic
nonrepudiation of sending automatically, but does not a priori
protect against repudiation of sending due to compromised private
components; nor does it provide proof of receipt. Thus (4) is an
example of a service which relies heavily on an interface with an
external system which most likely would be implementation-
dependent, since its structure depends on considerations such asÔ in
conjunction with authentication implements integrity. Signature
refers to application of private components to message digests
(output of hash functions); it implements authentication and basic
nonrepudiation, in concert with an authentication framework. The
form of the latter is implementation-dependent. For example, a
directory service might be provided, along with "hot lists" of
compromised keys.
The four mechanisms above may be regarded as the kernel of an
implementation. Various other mechanisms which could be provided
are noted, e.g., in [ISO-87]. For example, to guard against replay,
timestamps using synchronized clocks might be provided. Another
possibility is the addition of a handshaking protocol. For
enhancement of the basic nonrepudiation mechanism (the signature),
a notary system could be used. Again these auxiliary services are
best added at the discretion of implementors. For example,
synchronized clocks may not be present, and notaries violate the
desirable feature of point-to-point communication, and hence should
not be included in standard specifications.
Ô communicate with
other equipment designed to provide the same security mechanisms
or functions.
6.5.1 Security.
The first and foremost criterion is of course security. It may
take 5 years or more for a given method to be thoroughly
cryptanalyzed, starting from the time it receives widespread public
exposure.
One subcriterion in this regard is that a system should be
published in an outlet such as a refereed journal with a reasonably
large circulation, or a book or conference proceeding which isÔcterized by low bandwidths. Exponentiation-
based methods such as RSA and the Diffie/Hellman exponential key
exchange are examples. Other systems suffer from large data
expansion, large key size or long key generation time.
There seem to be some inherent tradeoffs in this regard. That
is, it does not seem possible to construct a system which is secure
and also scores well on all numeric counts. The classic example is
key size; e.g., small key size in RSA would produce a high
bandwidth, but would also produce insecurity. That is, in this case
high bandwidth would produce low cryptanalysis time. Data expansion
seems to have a similar impact. For example, in appendix E it is
noted that Shamir's knapsack attack runs in time which rises as nd
where d = expansion factor. Again high bandwidth produced
insecurity. It would be interesting to know whether this trade-
off notion could be formalized.
6.5.3 Other criteria.
Versatility is an important criterion. The RSA system is
distinguished in this regard since it supports both key
distribution and signatures. All other major systems are limitedÔibed in this section is
compatible with a subset of [CCIT87]. Public components of
receivers are used as key-encrypting keys; private components of
senders are used to encrypt message digests. Data-encrypting keys
are generated for individual sessions. These may be associated to
an arbitrary conventional cryptosystem; DES is a possibility. The
public and private components may be associated to different
public-key systems if different algorithms are used for key
encryption and signatures.
Certificate-based key management is proposed. Since we are
focusing on local-area networks, a simple tree structure is
proposed, consisting of a root and one additional level containing
all users. In particular, the root issues all certificates.
Certification paths are thus trivial.
6.7.2 Component generation and storage.
It is proposed that users generate their own public/private
component pairs, using trusted software or hardware supplied by the
system. Key pairs could be stored on smart cards [HAYK88] or
tokens, along with the user's certificate. Such kernel mechanismsÔdjusted for parity. Data-
encrypting keys can be produced dynamically by pseudorandom number
generators which are time-variant.
An example of a generator for data-encrypting keys, as well as
initializing vectors, is given in appendix C of [ANSI85]. Let
E(K,Y) be encryption by DEA (essentially equivalent to DES) with
key K. Let K be a DEA key reserved for usage in key generation and
let V0 be a 64-bit secret seed. Let T be a date/time vector,
updated on each key or IV generation. Let
Ri = E(K,E(K,Ti) XOR Vi),
Vi+1 = E(K,Ri XOR E(K,Ti)).
Then Ri may be employed as an IV. To obtain a DEA key from R,
reset every eighth bit to odd parity.
Routines for generating DES keys are supplied with various
products. Schemes for pseudorandom number generation include [AKL-
84], [BLUM84],[BRIG76]. The last gives a pseudorandom bit generator
whose security is equivalent to discrete logarithm.
6.7.4 Issuance and distribution of certificates.
Public components are registered with the root. The root
generates a certificate containing the user's public component and
identifying information, and a validity period. Distribution of
certificates by users is recommended; certificates may be cached.
This eliminates the necessity of having the root be on-line.
Ôattempted
repudiation.
6.7.5 Compromised or invalidated certificates.
Assuming that certificates are cached, the root must
periodically issue hot lists of invalidated certificates. This
kernel service may be augmented in various ways to provide more
current validity information. Again, however, additional mechanisms
have drawbacks. As noted above, a central directory service could
provide real-time validity checks, but it must be on-line.
Furthermore, such checks a priori do not account for compromised
private components, during the period following compromise but
before a report is filed with the root. Even if users are required
to report known compromises within a specified time period, a
compromise may not become known to the user until later. As we
noted, this creates an administrative/legal problem, since a user
could disavow a signature on the basis of the latter type of
compromise. A notary system can be used to add a layer of validity
by having secondary signatures attest to the validity of senders'
signatures, but this violates the desired criterion of point-to-
point communication.
This is clearly an area in which solutions must be customized
to some degree. For example, authentication in a system used for
financial transactions may require more stringent controls than a
kernel provides.
The root should maintain a time-stamped list of revoked
certificates.
6.7.6 Authentication.
A hash function is used to produce a message digest. This is
signed with the private component of the sender. Timestamps and
random numbers may also be included to prevent replay. If more than
one hash function is permitted, identification of the function usedÔent of the root, which is
assumed to be known to all users. Then B forwards his certificate
to A, who validates it. Each may cache the certificate of the
other.
Now A and B may communicate securely. If A sends a message to
B, B uses A's validated public component, extracted from A's
certificate, to decipher the message digest. Then B may decrypt the
key used for data encryption, using B's private component. Now B
may decrypt the message text using this session key, then re-
compute the message digest and compare to the transmitted form.
Appendix A. Mathematical and computational aspects.
We discuss here some issues related to the computational
complexity of public-key cryptography. The foundation of the
security of such systems is the computational infeasibility of
performing cryptanalysis, in contradistinction to the relative ease
of encryption/decryption. We analyze some of the issues which arise
in this context. Also included is some background theoretical
computer science needed to discuss the issue of computational
complexity of cryptography and cryptanalysis, as well as zero-
knowledge proofs and related schemes.
This discussion may aid in understanding the security basis of
public-key cryptography. It may also shed some light upon the more
practical matter of choosing key sizes, i.e., the number of bits
in private and public components. This section may safely be
skipped by readers who do not wish to gain an in-depth
understanding of such issues.
A.1 Computational complexity and cryptocomplexity.
An ideal cryptosystem would have the property that encryption
and decryption are easy, but cryptanalysis is computationally
infeasible. In practice, this is commonly interpreted (e.g.,
[DIFF76b]) to mean that encryption/decryption should be executable
in polynomial time, while ideally cryptanalysis should take
exponential time. More generally, cryptanalytic time should be an
exponential function of encryption/decryption time.
Unfortunately, it is difficult to determine when this criterion
holds in practice. This is because it is usually very difficult to
determine a nonpolynomial lower bound for the time required forÔdless of n.
The class NP is (loosely) the class of decision problems
solvable in polynomial time via a nondeterministic algorithm.
Perhaps the single most important problem in computer science is
to decide whether P = NP. The NP-complete problems are the hardest
subclass of NP, having the property that if one instance of the
subclass is in P then P = NP. Many classical combinatorial search
problems can be given NP-complete formulations. Traveling salesman
and knapsack are examples (see [GARE79] for a long list).
The class of NP-hard problems are those problems, decision or
otherwise, which are at least as hard as NP-complete problems. Some
NP-hard problems are so hard that no algorithm will solve them;
they are undecidable. Such problems cannot be in NP. An example is
the halting problem (e.g., [HORO78]). Ô (e.g., [GROL88]). An early characterization was
suggested by Shamir [SHAM79], who quantifies this notion by
defining a complexity measure C(n,a) for algorithms as follows:
C(n,a) is a measure of an algorithm if at least a fraction a of
problem instances of size n can be solved by the algorithm in time
C(n,a). For example, an algorithm for finding one factor of n could
have complexity C(n,1/2) = O(1), since n has a 50% chance of being
even. However, such investigations have thus far failed to produce
a comprehensive framework, although they may be useful in a few
special instances.
Another simple example illustrates the difference between worst-
case and average-case complexity: as noted in [RABI76], algorithms
to sort n items are often predicated on the assumption that the
items are arranged in random order; i.e., all n! arrangements are
equally likely. If the file has a real-world origin it is more
likely that the file is already partially sorted. An optimized
algorithm might anticipate this and utilize an adaptive strategy.
In practice, a cryptosystem for which cryptanalysis has an
average-case polynomial complexity is generally worthless; in fact
this remains true if any measurable fraction of all instances
permits polynomial-time cryptanalysis (this is difficult to make
precise, since the fraction may vary with key size). Thus there is
no a priori connection between the breaking of a system and the
difficulty of the underlying problem, since the latter is
characterized in terms of worst-case complexity. For example, often
there exists a heuristic technique which yields an approximateÔ instead. It would be
interesting to know if such systems could be made practical.
A.4 Probabilistic algorithms.
Another important distinction between the classical theory of
complexity and cryptocomplexity is that the classical theory of
algorithms does not encompass probabilistic algorithms (e.g.,
[RABI76]), which again may produce rapid solutions to problems in
many instances but not even terminate in a few instances. They may
also produce answers which are probably but not necessarily
correct. Such algorithms are inappropriate in many contexts, e.g.,
real-time control settings in which a response must be guaranteed
in a fixed period of time, or where provable solutions are
required. However, they are powerful tools in both cryptography and
cryptanalysis.
As noted in [RABI76], probabilistic algorithms cannot be
measured by classical criteria, which focus on worst-case runtime.
Instead, a probabilistic algorithm may involve a tradeoff between
execution time and confidence. For example, most numbers have all
small factors. If an algorithm exploits this fact it may terminate
quickly for most inputs but take exponential time when large primes
appear as factors.
Gill [GILL77] models probabilistic computation by extending the
classical Turing machine model (e.g., [HORO78]) to the
probabilistic Turing machine (app. D). This has proven valuable in
the analysis of cryptographic systems, and probabilistic encryption
schemes in particular.
A.5 Status of some relevant problems.
The security of several major cryptosystems mentioned herein
depends on the hardness of problems whose complexity status is
unresolved. This includes factoring and discrete logarithm. The
importance of the subclass of NP-complete problems emerges in this
regard: if a problem is known to be in NP but is not known to be
NP-complete, a solution to the problem in polynomial time (placing
the problem in P) would not imply that problems such as traveling
salesman are in P. The latter proposition is widely disbelieved.
A second relevant class is co-NP, the complements of problemsÔhm exists, even probabilistic.
If e = 2 the complexity is essentially equivalent to factoring n
(lem. N.3.2). If e > 2 the status is less clear; as a consequence
it is not clear that the security of RSA is equivalent to
factoring.
Brassard [BRAS79] has shown that the discrete logarithm has an
associated decision problem which lies in the intersection of NP
and co-NP. Thus, if either factoring or taking discrete logarithms
is NP-hard, it follows from the definition of this class that the
associated decision problem is NP-complete and in co-NP. In turnÔng at present is silicon-based. Thus all estimates of
achievable computer performance are geared to this technology. The
question arises as to whether a radically different technology such
as superconductivity or optical computing will make silicon-based
performance standards obsolete, and if so, when this might occur.
We have no idea, and hence we ignore these.
Gallium arsenide technology is another matter. It has already
been integrated into some existing supercomputers. Some of the
differences between GaAs and silicon VLSI are (e.g., [MILU88]):
a. GaAs gates have a higher switching speed.
b. Off-chip communication in GaAs pays a relatively higher
penalty.
c. GaAs chips have lower density.Ô hierarchies;
these may not carry over mutatis mutandis to GaAs.
We conclude that at the moment, GaAs technology does not present
a real threat to silicon performance standards. Furthermore, it
does not appear likely that problems such as yield and integration
will be solved in the near future. Thus, for the remainder of
appendix B we assume no radical change in technology from the
present.
B.2. Computing modes.
Classically, computing was dominated by the Von Neumann model,
with a single processor executing a single instruction scheme on
a single data stream. This paradigm reached its peak with computers
such as the Cray-1 [CRAY80] and CYBER 205 [CONT80]. However, the
performance of a single processing unit is limited by its clock
speed. It does not seem feasible to reduce major cycles much below
1 ns with silicon technology. Furthermore, at these speeds memory
access becomes a bottleneck, not to mention I/O. Thus it is not
likely that uniprocessors will exceed 109 operations per second,
barring radical new technologies.
Two alternatives to the Von Neumann model are parallel and
distributed computing (e.g., [HWAN84]). Parallel computing
generally refers to processors in one box; distributed means each
processor is in its own box. Parallel computers may (loosely) be
subdivided into shared-memory, in which all processors share a
common address space, and distributed-memory, in which each
processor has its own address space. These modes remove the
restriction on the number of instruction and/or data streams whichÔsystems. The Denelcor HEP (e.g., [KOWA85]), Floating
Point T-Series [HAWK87] and ETA-10 [STEI86] are examples of
parallel systems which have not proven to be commercially
successful. Also, Cray and other supercomputer manufacturers have
been reluctant to expand into large-scale parallelism, partially
because of cost-related concerns. This creates an interesting
situation from a cryptographic point of view: there may be cases
where a computer powerful enough to break a given system could be
built in theory. Security of the system might then rest on the
assumption that no one will spend the money to build it, or that
the only units built will belong to wealthy government agencies and
be subject to tight controls.
Even if computers with 1000 or more powerful processors are
constructed, the question arises as to whether such a configuration
can achieve computing power in proportion to the number of
processors, i.e., linear speedup. The mode of interconnecting the
processors and memories is critical. If the shared-memory
configuration is used, with a collection of processors accessing
common memory partitioned into modules, interference in paths
through the network or in simultaneous attempts to access a module
will cause a bottleneck if a low-cost, low-bandwidth network such
as a bus is used. If a high-bandwidth network such as a crossbar
is used (i.e., with concurrent data transfers possible between many
processors and memory modules), the number of units interconnected
is limited by cost which rises as the square of the number of
processors. Thus such systems seem to be inherently limited in the
extent to which they can improve on uniprocessor performance.
An alternative is to connect processor/memory pairs using a
network such as a hypercube [SEIT85]. Machines of this type with
up to 65,536 weak processing elements (e.g., the Connection Machine
[HILL85]) or up to 1024 powerful processors (e.g., the NCUBE/10
[HAYE86]) have been constructed, and systems with up to 32,000
Cray-1 level processors have been proposed. There is debate (and
some controversy) over the speedups which such distributed-memory
machines can achieve. The latter consideration is related to cost-
effectiveness, which requires nearly-linear speedup. Also, the cost
of interconnection in a hypercube-based system rises as O(n log n),Ôs and
architectures, but also the greatest amount of computing power
which might realistically be brought to bear against a given task.
B.3 Some relevant algorithms and implementation.
Most of the powerful algorithms for factoring and discrete
logarithm are fairly new. As we have noted, most of them have not
been fully analyzed for runtimes. Nonetheless, some standards have
emerged in this regard. The best guess for the future can only
amount to anticipation of improvements in the present algorithms.
B.3.1 Quadratic sieve factoring algorithm.
The quadratic sieve [POME84] provides an alternative to the
earlier continued fraction factorization algorithm [MORR75].
As noted in [DAVI83b], the continued fraction approach usesÔapabilities may be nontrivial. Hence it
is not clear to what extent the preceding efficiency can be
maintained as the degree of parallelism grows.
An alternative is distributed computing: Silverman [SILV87] has
used the quadratic sieve implemented via a network of 9 SUN 3
workstations to factor numbers up to 80 digits in 8 weeks. Recently
another network was used to factor 106-digit numbers [LENS89].
It should be noted that the results obtained via the quadratic
sieve are directly relevant cryptanalytically, since the integers
factored are general. Integers of up to 155 digits, but with
special forms, have been factored, also by use of networks
[SIAM90]. However, these results are only indirectly relevant to
systems such as RSA, assuming moduli are properly chosen.
B.3.2 Computations in finite fields.
This is a subject which has been explored fairly thoroughly
(e.g., [BART63]), and we do not review it here.
Multiplication of elements in GF(m) has classically been
implemented at the circuit level using linear feedback shift
registers. However, Laws [LAWS71] has noted the potential for using
cellular arrays. These are highly amenable to VLSI implementation.
A pipeline architecture for multiplication and inverses is proposed
in [WANG85].
One class of algorithms of particular interest is for discrete
logarithms in GF(pn). Still more particularly, the case n = 2 has
been explored considerably ([BLAK84],[BLAK84b],[COPP84]). Since
finite logarithms are easy to compute in GF(m) if m has only smallÔnced by implementation efficiency.
B.3.3 Other algorithms.
Many of the most fundamental operations in this setting seem to
be characterized by inherent sequentiality. An example is
exponentiation; computing the n-th power seems to take log n steps
regardless of the number of processors available.
Another classical example is greatest common divisor. Although
some partial results are noted in [ADLE86], major improvement over
Euclid does not seem forthcoming regardless of advances in
architecture.
Many of the powerful factoring algorithms are highly
parallelizable (e.g., [SCHN84]). The main requirement is existence
of appropriate architectures.
B.4. Application-specific architectures.
General-purpose architectures such as the Cray are of interest
in this setting because of their immediate availability. At the
other extreme, architectures closely matching the algorithms of
interest could be constructed, but their over-specialized nature
would virtually preclude their commercial distribution. In between
are classes of architectures which are more versatile but not truly
general-purpose. We note several examples of partly-specific
architectures and a proposed highly-specific machine.
B.4.1 Systolic and wavefront arrays.
The notion of systolic arrays ([KUNG82],[KUNG78]) is an
extension of pipelining. The idea is to have a collection of
processors operate on data which is pulsed rhythmically through the
array. If the original requirement of a synchronous mode of
operation is relaxed, the result is a wavefront array [KUNG82b].
Both types were originally targeted at applications such as signal
processing which are compute-intensive and involve repetitions of
operations on many operands.
Ông algorithms are noted in [BREN83b].
It would be of interest to know what a more general-purpose
linear systolic array such as the Warp [ANNA87] (which curiously
more closely resembles a wavefront array) could accomplish on some
of the problems discussed in this paper, and factoring in
particular. The Warp is already in production.
B.4.2 Proposal for a quadratic sieve machine.
Pomerance et al. [POME88] describe a pipeline architecture which
would efficiently execute the quadratic sieve. This notion is of
considerable interest to anyone implementing an algorithm such as
RSA, since such a machine could presumably factor numbers beyond
the reach of present-day supercomputers.
Cost-effectiveness is carefully analyzed, as is critical for an
application-specific architecture. They speculate that a $50,000
version of the architecture should factor 100-digit numbers in
about 2 weeks; or 140 digits in a year on a $10 million version;
or 200 digits in 1 year on a $100 billion version. It should be
noted that the last is clearly predicated on the notion that the
architecture and algorithm will scale linearly with the number of
processing units; we noted earlier that various bottlenecks such
as inter-processor communication and memory access make this
somewhat dubious. Nonetheless the possibility arises that moduli
approaching 200 digits may be necessary in RSA because of the
potential existence of machines such as these.
The crux of the architecture are the pipe and pipe I/O units.
These should be custom and should be able to handle variable
strides without the considerable loss of efficiency which usually
accompanies nonconstant stride. The two units should be chained
together. The pipe should consist of stages, all of which are bus-
connected to the pipe I/O unit. The cycle time of memory should be
the same as the processing elements.
It is interesting to note that this architecture bears a close
resemblance to a linear systolic array.
B.4.3 Massively parallel machines.
An alternative to pipelined machines is to configure a large
number of primitive processing elements in an array and have them
execute the same instruction stream synchronously, processing a
large quantity of data in parallel (SIMD mode). Such machines areÔ
consisting of a control unit and a tape. At any time M is in some
state, and the read/write head of the tape is over some symbol on
the tape. If D(q,a) = (p,b) then initially the head is scanning aÔ M = (K,S,D,s) such
that for any w in W, the configuration (s,#w,#,e) yields
(h,#u,#,e), i.e., u is the output of M on input w, and furthermore
u = f(w). Then f is said to be computed by M.
Suppose alphabet A does not contain #, Y or N. Suppose L is a
language in A* and X is its characteristic function, i.e., for w
in A*, X(w) = Y if w is in L, X(w) = N otherwise. If X is computed
by Turing machine M then M is said to decide (or recognize) L.
Conversely, if X is the characteristic function of a language L and
X is Turing-computable, i.e., there exists a Turing machine which
computes X, then L is said to be Turing-decidable.
Ôterministic machines, which are merely special
cases of the more general nondeterministic case.
It is also true (but not as trivial) that any language accepted
by a nondeterministic Turing machine is also accepted by a
deterministic Turing machine. That is, nondeterminism does not
increase the power of Turing machines insofar as the class of
languages is concerned.
Similar extensions hold for decidable languages.
C.3 Computational complexity.
The time complexity of Turing machines is measured by the number
of steps taken by a computation. If T is a function on the
nonnegative integers, a deterministic Turing machine M is said to
decide language L in time T if it decides in time T(n) or less
whether w is or is not in L, where w has length n. If T is a
polynomial then L is said to be decided in polynomial time. If a
language is decidable in polynomial time on a multitape
deterministic Turing machine then it is decidable in polynomialÔgs a and b is written ab. If A and B are subsets of S*, AB
is the set of strings formed by concatenating elements from A and
B.
C.1 Turing machines.
A (one-tape, deterministic) Turing machine is a quadruple
(K,S,D,s) where:
a. S is an alphabet which contains a blank = #, but not the
symbols L or R which are reserved for tape movement to the
left or right.
b. K is a set of states which does not include the halt state
= h, which signals an end to computation.
c. s = initial state; it is in K.
d. D : K x S -> (K + {h}) x (S + {L,R}) where + denotes
union.
A Turing machine = M may be interpreted semi-physically asÔst nonblank symbol to the right of the head position. This
gives the configuration a unique description. In particular, if the
input to M is w then the initial configuration of M is (s,#w,#,e).
M is said to halt on input w if some halted configuration (state
= h) is reached from (s,#w,#,e) in a finite number of steps; then
it is said that (s,#w,#,e) yields a halted configuration. If M
halts on input w, M is said to accept w. The language accepted by
M is the set of strings w accepted by M. Conversely, a language is
said to be Turing-acceptable if it is accepted by some Turing
machine.
Suppose S is an alphabet, T and W are subsets of S, and
f: W -> T. Suppose there exists a Turing machine M = (K,S,D,s) such
that for any w in W, the configuration (s,#w,#,e) yields
(h,#u,#,e), i.e., u is the output of M on input w, and furthermore
u = f(w). Then f is said to be computed by M.
Suppose alphabet A does not contain #, Y or N. Suppose L is a
language in A* and X is its characteristic function, i.e., for w
in A*, X(w) = Y if w is in L, X(w) = N otherwise. If X is computed
by Turing machine M then M is said to decide (or recognize) L.
Conversely, if X is the characteristic function of a language L andÔa relation on
(K x S) x ((K + {h}) x (S + {L,R})).
That is, D is now multiple-valued, so that the next
configuration is no longer uniquely determined by the present.
Instead, in a given number of steps a configuration may yield a
number of configurations. Consequently an input may yield many
outputs. A sequence of steps starting from a given input defines
a computation; in general many computations are possible on one
input. A nondeterministic machine is said to accept an input if
there exists a halting computation on it. Again the language
accepted by a machine is the set of strings accepted by it.
Trivially any language accepted by nondeterministic machines is
also accepted by deterministic machines, which are merely special
cases of the more general nondeterministic case.
It is also true (but not as trivial) that any language accepted
by a nondeterministic Turing machine is also accepted by a
deterministic Turing machine. That is, nondeterminism does not
increase the power of Turing machines insofar as the class of
languages is concerned.
Similar extensions hold for decidable languages.
C.3 Computational complexity.
The time complexity of Turing machines is measured by the number
of steps taken by a computation. If T is a function on the
nonnegative integers, a deterministic Turing machine M is said to
decide language L in time T if it decides in time T(n) or less
whether w is or is not in L, where w has length n. If T is aÔic Turing machine is denoted by P. The class of
languages acceptable in polynomial time on some nondeterministic
Turing machine is denoted by NP.
It is not known whether P = NP.
Appendix D. The theory of probabilistic computing.
Probabilistic algorithms are employed as adjuncts in
cryptosystems for purposes such as finding primes. They have also
produced virtually all major practical cryptanalytic algorithms for
factoring, discrete logarithm etc. Here we review an extension of
the classical theory of computation which incorporates
probabilistic computing. This extension has proven particularly
valuable in the study of probabilistic cryptosystems.
An ordinary deterministic multitape Turing machine may be
considered to have an input tape, an output tape, and read-write
worktapes. A modification of the ordinary model (e.g., [GILL77])
is the probabilistic Turing machine. It has a distinguished state
called the coin-tossing state, which permits the machine to make
random decisions. In terms of languages recognized, these have the
same power as deterministic machines. However, time considerations
are more subtle. In particular, a notion of probabilistic run time
is needed, rather than measures such as maximum run time used for
ordinary machines.
A probabilistic Turing machine operates deterministically,
except when it is in a special coin-tossing state (or states). In
such a state the machine may enter either of two possible next
states. The choice between these is made via the toss of an
unbiased coin. The sequence of coin tosses may be considered to
constitute the contents of an auxiliary read-only input tape, the
random tape, which contains a binary string. Thus a computation by
a probabilistic machine is a function of two variables, the
ordinary input tape and the random tape.
If the random tape is unspecified, the output of the computation
of probabilistic machine M, M(x), is a random variable (e.g.,
[MCEL77]): M produces output y with probability Pr{M(x) = y}. For
a given input x, there may exist a y such that Pr{M(x) = y} > 1/2.Ôes
such as RSA as well as zero-knowledge schemes, probabilistic
encryption etc., is whether either of these inclusions is proper.
Appendix E. Breaking knapsacks.
We give a brief account of the demise of the Merkle/Hellman
trapdoor knapsack public-key system and some of its variants. A
much more complete discussion is given in [BRIC88].
We recall from section 4.2.1 that the security of this approach
rests on the difficulty of solving knapsack problems of the form
C = b1 * M1 + ... + bn * Mn,
ÔDLE82] to break the
Shamir/Graham knapsack, and by Brickell [BRIC84] to break the
iterated Merkle/Hellman knapsack. The multiplicative version was
broken by Odlyzko [ODLY84]. In fact all major proposed knapsacks
based on modular disguises have been broken using this approach.
It should be noted that the low-density attacks
([BRIC83],[LAGA83]) are successful where finding trapdoors fails.
These use a measure of density for a knapsack with coefficients
b1,...,bn defined by density = n/(log max {bi}). This type of
attack
is independent of whether the knapsack is a disguised version of
another. Trapdoors, in contrast, are easiest to find for high-
density knapsacks.
The concept of density is related to two important parameters
of cryptosystems, namely information rate and expansion factor d.
In [LAGA84] the information rate is defined to be the ratio of the
size of plaintext to the maximum size of the ciphertext. This is
the reciprocal of d, i.e., ciphertext/plaintext. Information rate
is essentially the same as density, although for the above knapsack
and modulus u it is defined slightly differently, namely as n/(log
nu). Both definitions are derived from approximations to the actual
ciphertext size, which is log(b1 * M1+...+bn * Mn). Lagarias notes
that the attack in [SHAM84b] runs in time O(P(n)*nd) for a
polynomial P. Hence the attack is feasible if d is fixed but not
if the expansion factor d is large. This illustrates the
interrelation between security and practicality.
Appendix F. Birthday attacks.
In section 4 we noted several usages of birthday attacks against
hash functions. Here we give a brief summary of the relevant
mathematics.
Suppose H is a function which has m possible outputs. Whenever
H outputs a value it is totally random and independent of any
previous values which have been output.
If H is evaluated k times, each output is akin to an object
placed in one of m cells corresponding to the range of H. Since the
k values of H are independent, any object could be placed in anyÔFor n >
1 let
Zn* = {x À
À Zn : x > 0 and GCD(x,n) = 1}.
For example, Z10* = {1,3,7,9}. That is, Zn* consists of the
nonzero elements of Zn which are relatively prime to n.
If a À
À Zn* let
a * Zn* = {a * x mod n : x À
À Zn*}.
For example, 2 * Z10* = {2,6,14,18} mod 10 = {2,6,4,8}, 3 * Z10*
= {3,9,21,27} mod 10 = Z10*. We have:
LEMMA G.1. Suppose n > 1 and a À
À Zn*. Then
a. For any x and y: a * x ÀÀ a * y ( mod n ) iff x ÀÀ y (mod
n).
b. a * Zn* = Zn*.
c. a has a multiplicative inverse modulo n; i.e.
there exists b À
À Zn* such that b * a ÀÀ 1 (mod n).
Proof: if x ÀÀ y (mod n) then trivially a * x ÀÀ a * y (mod n).
Conversely, suppose a * x ÀÀ a * y (mod n). Then n | (a * (x - y)).
But GCD(a,n) = 1, so n | (x - y), i.e. x ÀÀ y (mod n). Thus (a)
holds.
For (b): if x À
À Zn* then GCD(x,n) = 1, so GCD(a*x,n) = 1. Thus
a * x mod n À
À Zn*. Hence a * Zn* is contained in Zn*. By (a), if a
*
x ÀÀ a * y (mod n), then x ÀÀ y (mod n). Thus a * Zn* consists of n
distinct elements, and cannot be a proper subset of Zn*; (b)Ô + p-1 + |Zn*|.
Then (b) follows. QED.
G.2 The Euler-Fermat Theorem.
LEMMA G.2.1 (Euler's Theorem). Suppose n > 0 and a À
À Zn*. Then
aÀ-À(n) ÀÀ 1 (mod n).
Proof: if Zn* = {r1,...,rm} then a restatement of (b) of lemma
G.1
is
ÔGalois
fields, and denoted GF(pn). We have already noted that GF(p) = Zp
is defined by doing arithmetic modulo p. The elements of Zp are
called the residues modulo p; i.e., each integer x has a unique
representation x = q * p + r where r À
À Zp. To define GF(pn) we
choose an irreducible polynomial f(x) of degree n in the ring of
polynomials modulo p (e.g., [DENN83] p. 49). Now arithmetic may be
defined on this ring of polynomials, modulo f(x); i.e., write g(x)
ÀÀ h(x) iff f(x) is a divisor of g(x) - h(x). Each polynomial g(x)
has a unique representation g(x) = q(x)f(x) + r(x) for some
polynomial r(x) of degree at most n-1. The residues modulo f(x) are
the elements of GF(pn). These consist of polynomials of degree ÀÀ n-
1 with coefficients from Zp. Each of the n coefficients of a
residue has p possible values, accounting for the pn element count
for GF(pn).
Appendix H. Euclid's algorithm.
On a number of occasions we referred to Euclid's algorithm,
which can be used to find greatest common divisors and
multiplicative inverses. We give some versions of it here. These
versions are recursive, and minimize storage requirements.
Suppose x and y are arbitrary positive integers. Their greatest
common divisor GCD(x,y) can be computed in O(log max{x,y}) steps
by recursively employing GCD(s,t) = GCD(s,t mod s). This is
Euclid's algorithm:
function GCD(x,y) returns integer;
/* return greatest common divisor of x > 0 and y > 0 */
s := x; t := y; Ôn of
GCD yields the multiplicative inverse of x modulo n, i.e., u with
x * u ÀÀ 1 (mod n). With [y] denoting the largest integer ÀÀ y, the
extended Euclid algorithm to find u is:
function INVERSE(n,x) returns integer;
/* for n > 0 and x À
À Zn* return u À
À Zn*
with u * x ÀÀ 1 (mod n) */
procedure Update(a,b);
temp := b; b := a - y * temp; a := temp;
end Update;
g := n; h := x; w := 1; z := 0; v := 0; r := 1;
while (h > 0) do
y : = [g/h]; Update(g,h); Update(w,z); Update(v,r);
end while;
return(v mod n);
end INVERSE;
For example, for n = 18, x = 7, this gives the values
g: 18 7 4 3 1
h: 7 4 3 1 0
w: 1 0 1 -1 2
z: 0 1 -1 2 -7
v: 0 1 -2 3 -5
r: 1 -2 3 -5 18
y: 2 1 1 3
Finally u = -5 mod 18 = 13 is returned. This is equivalent to
finding the sequence 7/18, 2/5, 1/3, 1/2, 0/1 in which eachÔm*log max{xi}) time.
Appendix I. The Chinese Remainder Theorem.
The Chinese Remainder Theorem is useful for purposes such as
simplifying modular arithmetic. In particular we note in a later
appendix that its use increases the efficiency of decryption in
RSA.
We begin with a special case: with Zn as in appendix G, we have
LEMMA I.1. Suppose p and q are primes and p < q. Then:
a. For arbitrary a À
À Zp and b À
À Zq, there exists a unique
x À
À Zpq with
x ÀÀ a (mod p),
x ÀÀ b (mod q).
b. If u * q ÀÀ 1 (mod p), the x in (a) is given by
x = (((a - b) * u) mod p) * q + b.
Ôx
via a and b, i.e., the residues of x modulo p and q, respectively.
Although the most general case of the Chinese Remainder Theorem
is not used in this exposition, we remark that the above can be
extended:
THEOREM I.1. Given pairwise relatively prime moduli {p1,...,pn}
and arbitrary {a1,...,an}, there exists a unique x À
À [0,p1*..*pn)
satisfying x ÀÀ ai (mod pi) for each i.
Proof: a straightforward generalization of the above (e.g.,Ô2 is prime. Let s = (p-1)/2. Then
a. The elements of Sp are precisely the quadratic residues
modulo p.
b. There are s quadratic residues modulo p.
c. There are s quadratic nonresidues modulo p.
Proof: as noted above, Sp is a subset of the set of quadratic
residues modulo p. Furthermore, if x2 ÀÀ y2 (mod p) then p | x2-y2;
hence p | x-y or p | x+y. If x and y are in (0,s] then 1 < x+y <
p; thus p | x-y; hence x = y. It follows that Sp contains distinct
elements. QED.
Now suppose a is a quadratic residue, x2 ÀÀ a (mod p), and x À
À
Zp*. We note
(p - x)2 ÀÀ p2 - 2 * p * x + x2 ÀÀ a (mod p).
Since 0 < x < p, either x or p - x is in (0,s]. It follows that
a À
À Sp. Thus the set of quadratic residues modulo p is contained in
S. Hence the two sets are identical, establishing (a). Since |Sp|
= s, (b) follows. Also, the complement of Sp in Zp* is the set of
quadratic nonresidues modulo p. Since |Zp*| = 2s, the complement of
Sp also has cardinality s; (c) follows. QED.
J.2 The Jacobi symbol.
If p is a prime > 2 and 0 < a < p, the Legendre symbol (a/p) is
a characteristic function of the set of quadratic residues modulo
p (e.g., [RADE64]):
a. (a/p) = 1 if a is a quadratic residue mod p.
b. (a/p) = -1 if a is a quadratic nonresidue mod p.
More generally, if k > 1 is odd and h is in Zk*, the Jacobi
symbol (h/k) may be defined as follows:
a. The Jacobi symbol (h/p) coincides with the Legendre symbol
if p is prime.
b. If k = p1*...*pm with pi prime, (h/k) = (h/p1)*...*(h/pm).
Ô, which is Gauss' law of
quadratic reciprocity (e.g., [RADE64]). The above shows that the
Jacobi symbol (a/n) can be computed in O(log n) steps.
J.3 Square roots modulo a prime.
Regarding solutions of x2 ÀÀ a (mod p), i.e., the square roots of
a modulo p, we have:
LEMMA J.3.1. Suppose p > 2 is prime. Let s = (p-1)/2. Suppose
a is a quadratic residue modulo p. Then
a. a has exactly two square roots modulo p in Zp*. One of
these lies in (0,s] and the other in (s,p-1].
b. the square roots of a modulo p can be found in
probabilistic polynomial time.
Proof: by lemma J.1.1 we know that a À
À Sp as defined in J.1;
hence there exists a unique x in (0,s] with x2 ÀÀ a (mod p). Then y
= p - x satisfies y2 ÀÀ a (mod p), and y is in (s,p-1]. Conversely,
suppose y is in (s,p-1] and y2 ÀÀ a (mod p). Then x = p - y is in
(0,s], and x2 ÀÀ a (mod p). Hence y is unique. Thus we have (a).
For (b) we invoke a probabilistic polynomial-time algorithm for
finding square roots modulo a prime (e.g., [PERA86] or p. 22 of
[KRAN86]). QED.
Ôuence modulo p has at most s solutions (e.g., [RADE64] p. 21).
Thus all quadratic nonresidues b must have ep(b) = p - 1. QED.
Also, ep can be evaluated in O(log p) time. Thus quadratic
residuosity mod p can be decided in O(log p) time.
Appendix K. Primitive roots and discrete logarithms.
The use of primitive roots was noted in sections 2.2 and 4.2.2.
We also observed that the security of exponentiation-based
cryptosystems depends in part on the difficulty of computing
discrete logarithms. Here we briefly explore these topics.
Let Zp* be as in appendix G. Suppose p is a prime and a À
À Zp*.
Suppose m > 0, am ÀÀ 1 (mod p), but ar !ÀÀ 1 (mod p) for any r with
0 < r < m. Then we say that a belongs to the exponent m modulo p.
The existence of m is guaranteed by the Euler/Fermat Theorem (cor.
G.2.1), which shows m < p. Let
Cp(a) = {ax mod p : 0 ÀÀ x < m}.
Then we have
Ô subset of Zp*. The result follows from lemma
K.1, which shows |Cp(g)| = p - 1 = |Zp*|. QED.
The x in lemma K.2 is the discrete logarithm, or index, of y
modulo p with base = g. However, the range of the logarithm can be
any interval of length p - 1. We have used [0,p-2], but, e.g., we
could also take x to lie in [1,p-1].
A restatement of lemma K.2 is that the cyclic subgroup generated
by the primitive root g modulo p is the whole group Zp*. Thus g is
a generator of Zp*.
LEMMA K.3. Suppose p > 2 is prime and p-1 has k distinct prime
factors which are known. Then:
a. The number of primitive roots modulo p is À-À(p-1), where
À-À is the Phi function (app. G.1).
2. Testing a given a to determine if it is a primitive root
modulo p can be done in time O(k * log p) = O((log p)2).
Ô.
Thus gs ÀÀ -1 (mod p).
For (b): suppose x2 ÀÀ g (mod p). Now x ÀÀ gr (mod p) for some r;
hence g2r ÀÀ g (mod p), and g2r-1 ÀÀ 1 (mod p). Thus 2r - 1 ÀÀ 0 (mod
p-
1), impossible since p - 1 is even. QED.
Appendix L. Primality testing.
Testing large integers to determine whether they are prime plays
a major role in key generation in RSA and other public-key systems.
We give a few examples of algorithms to effect this.
It is well-known (e.g., [KNUT81] p. 366) that if the number of
primes between 1 and x is f(x), then with ln denoting natural
logarithm (to base e = 2.718..),
f(x) = x/(ln x) + O(x/(ln x)2).
Ôoint, more efficient algorithms are desirable. Thus,
probabilistic tests may be used in practice to make an "educated
guess" as to whether a candidate is prime.
Often a Monte Carlo approach is employed. In this event there
is a slight possibility of an erroneous conclusion; however, the
error probability can be made arbitrarily small. Typically, a
sequence of "witnesses" attest to the primality or compositeness
of a number. Agreement among a group of about 100 witnesses is
generally sufficient to reach a conclusion beyond any reasonable
doubt, although evidently the legality of this procedure has not
been tested in the courts.
L.1 The Solovay/Strassen test.
One example of a probabilistic polynomial-time primality test
is the Solovay/Strassen test [SOLO77] mentioned in section 4.1.1
(although this approach is commonly attributed to Solovay and
Strassen, it was noted implicitly by Lehmer [LEHM76]; cf.
[LENS86]). If n is an odd positive integer and a À
À Zn*, with theÔ e(b,n) (mod n).
That is, e is also multiplicative. It follows that G is a
subgroup of Zn*. The order of G must divide the order of Zn*
(e.g.,
[HERS64] p. 35). Thus if G ÀÀ Zn*, G has cardinality at most (n-
1)/2. Solovay and Strassen showed that indeed G ÀÀ Zn* if n is
composite. Hence if n is composite and a is chosen at random, the
probability that a is in G is at most 1/2. We thus test as follows:
function Solovay_Strassen(a,n) returns charstring;
/* for n > 2, n odd, a À
À Zn, decides probabilistically
whether n is prime */
if (GCD(a,n) > 1) return("composite")
else
if ((a/n) = e(a,n)) return("prime")
else return("composite");
end Solovay_Strassen;Ôobability of error is at most
2-100.
L.3 The Miller/Rabin test.
Another Monte Carlo test was noted by Miller [MILL76] and Rabin
[RABI80]. If n - 1 = u * 2k where u is odd and k > 0, let exp(i) =
2i, 0 ÀÀ i ÀÀ k - 1. If a ÀÀ Zn* then a is a witness to the
compositeness of n if au !ÀÀ 1 (mod n) and au*exp(i) !ÀÀ -1 (mod n),
0
ÀÀ i ÀÀ k - 1. Again, e.g., 100 witnesses may be tested; if noneÔ y mod
n. Then
a = Cd mod p,
b = Cd mod q.Ôctability of which forms the basis for RSA. This was
exploited by Rabin (cf. sec. 4.1.4) to obtain a modification of RSA
which is provably equivalent to factoring. Essentially his scheme
was to encrypt via
EN(x) = x2 mod N.
Let ZN* be as in appendix G.
N.1 Characterizing quadratic residues.
The basic extension of quadratic residuosity modulo a prime to
the composite modulus case is:
LEMMA N.1.1. If N = p * q, p and q primes > 2, then:
a. Suppose z À
À ZN*. Then z is a quadratic residue modulo
N iff z mod p is a quadratic residue modulo p and z mod
q is a quadratic residue modulo q.
b. A quadratic residue z modulo N has exactly four square
roots of the form {x,N-x,y,N-y} in ZN*.
c. If z is a quadratic residue modulo N, and p and q are
known, then the square roots of z modulo N can be found
in probabilistic polynomial time.
Proof: suppose z À
À ZN*, z mod p is a quadratic residue modulo p,
and z mod q is a quadratic residue modulo q. Then for some r and
t in Zp* and Zq*, respectively, we have r2 ÀÀ z (mod p) and t2 ÀÀ z
(mod q). By the Chinese Remainder Theorem (app. I) there exists w
in ZN with w ÀÀ r (mod p) and w ÀÀ t (mod q). Then w2 ÀÀ z (mod p or
q), so w2 ÀÀ z (mod N). Thus z is a quadratic residue modulo N. This
proves one direction of (a).
Now suppose z is a quadratic residue modulo N. Let zp = z mod p
and zq = z mod q. Then z À
À ZN*, and hence zp À
À Zp* and zq À
À Zq*.
Also,
w2 ÀÀ z (mod N) for some w in ZN*. Thus w2 ÀÀ z (mod p or q) and
henceÔ1,2). The Chinese Remainder
Theorem shows that w is uniquely determined in ZN by a given i and
j; hence z has at most four square roots modulo N in ZN*.
Conversely, by the Chinese Remainder Theorem once again, w can be
found for each (i,j) pair. Thus z has exactly four square roots
modulo N in ZN*. Let x denote one root. Then N - x is another. If
y is a third, then N - y is the fourth. This proves (b).
By lemma J.3.1, {xi} and {yj} can be found in probabilistic
polynomial time; the corresponding w's can then be found in
polynomial time. This proves (c). QED.
COROLLARY N.1.1. Suppose N = p * q, p and q primes > 2. Then:
a. EN is a four-to-one function.
b. If p and q are known and z is a quadratic residue modulo
N, the four values of x for which EN(x) = z can be found
in probabilistic polynomial time.
Proof: immediate from the previous lemma. QED.
N.2 The Jacobi symbol once more.
Suppose N = p * q where p and q are primes > 2. Then for x in
ZN*, the Jacobi symbol (x/N) is given by
(x/N) = (x/p)(x/q).
If the Jacobi symbol (x/N) = -1, then (x/p) or (x/q) = -1. Hence
x mod p and x mod q are quadratic nonresidues modulo p and q,
respectively. By lemma N.1.1, x is a quadratic nonresidue modulo
N. Since (x/N) can be evaluated in O(log N) time, (x/N) = -1 is a
deterministic polynomial-time test for quadratic nonresiduosity of
x modulo N, N = p * q. The interesting case is (x/N) = 1, whence
no conclusion can be drawn regarding quadratic residuosity of x
modulo N. To study this further, ZN* may be partitioned into four
subclasses, according to the Jacobi symbols (x/p) and (x/q):
ÔQ00(N) is the set of quadratic residues modulo N; the
other Q's contain nonresidues.
c. For i = 0 or 1 and j = 0 or 1, |Qij(N)| = (p-1)(q-1)/4.
Proof: (a) is trivial, and (b) is immediate from lemma N.1.1.
For (c), let g and h be generators for Zp* and Zq*, respectively.
For
w À
À ZN*, suppose w ÀÀ gr (mod p) and w ÀÀ hs (mod q), where 0 ÀÀ r <
p -
1 and 0 ÀÀ s < q - 1. Then r and s are unique. Conversely, any such
pair (r,s) uniquely determines w, by the Chinese Remainder Theorem.
Let f(w) = (r,s). Then f is a bijection from ZN* to Zp x Zq. Also,
if f(w) = (r,s) then
(w/p) = (gr/p) = (g/p)r,
(w/q) = (hs/q) = (h/q)s.
By lemma K.4, g and h are quadratic nonresidues modulo p and q,
respectively. Thus (w/p) = (-1)r and (w/q) = (-1)s. Let i = r mod
2 and j = s mod 2. Then (w/p) = (-1)i and (w/q) = (-1)j. Hence w is
in Qij(N). For k = 0,1 let Zpk and Zqk be the subsets of Zp* and
Zq*,
respectively, which contain elements = k (mod 2). Then for i = 0,1
and j = 0,1, f is a bijection from Qij(N) to Zpi x Zqj. The latter
has cardinality (p-1)(q-1)/2; this gives (c). QED.
Thus exactly half of the elements of ZN* have (x/N) = -1; these
are nonresidues modulo N. The other half have (x/N) = 1. Of the
latter, half (i.e., Q00(N)) are quadratic residues and half (i.e.,
Q11(N)) are nonresidues. The quadratic residuosity conjecture is
that determining which of the elements of ZN* with (x/N) = 1 are
quadratic residues modulo N is not solvable in probabilisticÔc residue and a nonresidue is a
nonresidue.
Proof: suppose x À
À Qij(N) and y À
À Qrt(N). Then (x/p) =
(-1)i, (x/q) = (-1)j, (y/p) = (-1)r, (y/q) = (-1)t. Hence (x*y/p)
=
(-1)i+r and (x*y/q) = (-1)j+t. Now x * y mod N will be a residue if
and only if i = r and j = t. This gives (a). In particular, x * y
mod N is a residue if both are in Q00(N), yielding (b). If x is a
residue and y a nonresidue, x is in Q00(N) but y is not; (c)
follows. QED.
Thus the quadratic residues modulo N form a subgroup of ZN*.
N.3 Quadratic residuosity and factoring.
We note the connection between quadratic residuosity and
factoring observed by Rabin [RABI79].
LEMMA N.3.1. Suppose N = p * q, p and q prime, x and y are in
ZN*, x2 ÀÀ y2 (mod N), and y !ÀÀ x or -x (mod N). Then possession of
x and y permits factoring N in deterministic polynomial time.
Proof: we have x - y !ÀÀ 0 (mod N) and x + y !ÀÀ 0 (mod N), so
GCD(N,y+x) < N and GCD(N,y-x) < N. Now x2 - y2 ÀÀ (x-y)(x+y) ÀÀ 0
(mod
N). Hence (x-y)(x+y) ÀÀ 0 (mod p). Thus p | y-x or p | y+x; also p
| N. If p | y-x, p | GCD(N,y-x) < N, so p = GCD(N,y-x). The latter
can be found via Euclid's algorithm (app. H). If p | y+x, p |
GCD(N,y+x) < N, so p = GCD(N,y+x). QED.
LEMMA N.3.2. Suppose N = p * q, p and q prime. Suppose thereÔbility of factoring N is at least 1/4. If
this procedure is repeated m times, the probability of success is
at least 1 - (3/4)m. Also, the problem size is log N, so m is a
polynomial in the problem size. QED.
COROLLARY N.3.2. If N = p * q, p and q prime, and the
factorization of N is computationally intractable, then the Blum
encryption function EN above is a trapdoor one-way function, with
(p,q) forming the trapdoor.
Proof: by the previous theorem, an algorithm to invert EN would
yield an algorithm to factor N. QED.
N.4 Quadratic residuosity and Blum integers.
Suppose N = p * q where p ÀÀ 3 (mod 4) and q ÀÀ 3 (mod 4). Then
N is called a Blum integer (normally p and q are specified to have
roughly the same size). For example, N = 77 is used in appendix O.
LEMMA N.4.1. If p,q ÀÀ 3 (mod 4) then (-1/p) = (-1/q) = -1.
Proof: in lemma J.4.1 take a = -1. We recall that (-1/p) = 1 if
and only if -1 is a quadratic residue modulo p. Thus (-1/p) = (-
1)(p-1)/2 (mod p) and similarly (-1/q) = (-1)(q-1)/2 (mod q). The
result
follows. QED.
LEMMA N.4.2. If N = p * q is a Blum integer then (-x/p) = -
(x/p), (-x/q) = -(x/q), (-1/N) = 1, and (-x/N) = (x/N).
Proof: the first two are immediate from the previous lemma; also
(-1/N) = (-1/p)(-1/q). QED.
Ô, i = 0,1,
j = 0,1.
Proof: let {x,N-x,y,N-y} be the square roots of z in ZN*. Since
N-x ÀÀ -x (mod p), by lemma N.4.2, (N-x/p) = -(x/p). Similarly (N-
x/q) = -(x/q), so if x À
À Qij(N), N-x À
À Q1-i,1-j(N); similarly for
y and
N-y. Now x2 ÀÀ y2 (mod N) and y !ÀÀ x or -x (mod N). Since by lemma
N.4.3, (y/N) = -(x/N), y cannot be in the same Q as x. By lemma
N.4.2, ((N-y)/N) = (y/N), so N-y cannot be in the same Q as x. Thus
y and N-y must be in Qi,1-j(N) and Q1-i,j(N) in some order. QED.
For Blum integers we can restrict the function EN to Q00(N);
i.e., let BN : Q00(N) -> Q00(N) by BN(x) = x2 mod N. Then we have
LEMMA N.4.5. If N = p * q is a Blum integer then:
a. BN is a permutation on Q00(N), i.e., on the set of
quadratic residues modulo N.
b. If the factorization of N is computationally intractable
then BN is a trapdoor one-way permutation, with (p,q)
constituting the trapdoor.
Proof: by corollary N.1.1 we know that if p and q are known and
y is in Q00(N), the equation EN(x) = y has exactly four solutions
which can be found in probabilistic polynomial time. By lemma
N.4.4, exactly one of these, x00, lies in Q00(N); x00 is easily
extracted from the set of four since only it satisfies (x/p) =
(x/q) = 1. Hence x00 is the unique solution of BN(x) = y. Thus BN
is
a permutation on Q00(N) whose inverse may be computed in
probabilistic polynomial time with knowledge of the trapdoor (p,q).
On the other hand, lemma N.3.2 shows that an algorithm to invert
BN can be converted to an algorithm to factor N. QED.Ômod p) in n tries is 2-n. Hence a can be found in probabilistic
polynomial time (in n = length of p). Now (a/p) = 1. Similarly,
find b with (b/q) = 1, also in probabilistic polynomial time. Use
the Chinese Remainder Theorem to find y in ZN* with y ÀÀ a (mod p)
and y ÀÀ b (mod q), in polynomial time (in length of N). QED.
Appendix O. An introduction to zero-knowledge.
The notion of zero-knowledge proofs was introduced in [GOLD89].
The essence of zero-knowledge is that one party can prove something
to another without revealing any additional information. In
deference to the depth and scope of this area, we give only an
illustrative example in this section. However, there is a close
connection between zero-knowledge schemes and probabilistic public-
key encryption. Furthermore, some zero-knowledge schemes which have
drawn attention because of applicability to smart card
implementations, such as the one used as the basis of the example
in this section, use Shamir's notion of identity-based public-key
systems. Thus the reader desiring a more formal introduction to
these topics may wish to skip to appendix P.
Suppose that Alice knows a fact P. She wants to convince Bob
that she knows P, but she does not trust Bob. Thus, Alice does not
want to reveal any more knowledge to Bob than is necessary. What
Alice needs is a zero-knowledge proof of P.
For example, suppose that Alice wants to prove to Bob that she
really is Alice. Suppose for convenience that there is some
authority which verifies identities. One possibility is that the
authority could issue Alice an identification. If this were
contained on a device such as a smart card, Alice could simply show
it to Bob. However, if Alice and Bob are communicating over a
network, then Alice's identifying information would have to be
transmitted to Bob over the network. Upon receiving it, Bob could
use it to impersonate Alice. Even if Bob were trusted, an
eavesdropper such as Alice's adversary Carol could do the same.
This situation also arises commonly in computer access control:
Bob might then be a host computer or network server, and Alice's
identification might be a password. If Alice uses her password toÔays she is. He does this by checking that
362 * 580 * 671 ÀÀ 53 (mod 77),
622 * 581 * 670 ÀÀ 37 (mod 77),
472 * 581 * 671 ÀÀ 60 (mod 77).
The original numbers {53,37,60} that Alice sent reappear.
Actually, this doesn't really prove Alice's identity; she could
have been an impersonator. But the chances of an impersonator
succeeding would have only been 1 in 64.
In an actual system, the number N would have been much larger
(e.g., 160 digits). Also, Alice would have been assigned an ID
consisting of more numbers, e.g., 4, by the authority, with a
secret also consisting of 4 numbers. Furthermore, Alice would have
generated more random numbers, e.g., 5, to send to Bob. The ID
numbers, secret numbers, and random numbers would have been about
as large as N. This would have reduced an impersonator's chances
of cheating successfully to about 1 in a million (more precisely
2-20) if 4 and 5 are the parameters, which certainly would have
convinced Bob of Alice's identity.
Why does this work? Because the authority chose {58,67} and
{9,10} so that
92 * 58 ÀÀ 1 (mod 77),
102 * 67 ÀÀ 1 (mod 77).
This says that 92 and 58 are multiplicative inverses modulo 77,
as are 102 and 67.
Thus
362 * 580 * 671 ÀÀ 192 * 92*0 * 580 * 102*1 * 671
ÀÀ 192 * (92 * 58)0 * (102 * 67)1
ÀÀ 192 ÀÀ 36 (mod 77),
622 * 581 * 670 ÀÀ 242 * 92*1 * 581 * 102*0 * 670
ÀÀ 242 * (92 * 58)1 * (102 * 67)0
ÀÀ 242 ÀÀ 37 (mod 77),
472 * 581 * 671 ÀÀ 512 * 92*1 * 581 * 102*1 * 671Ô92 and 102 are the
multiplicative inverses of 58 and 67, respectively, modulo 77. To
see this, suppose Carol tries to convince Bob that she is really
Alice; i.e., Carol pretends that {58,67} is her own ID. For
simplicity, suppose Carol tries to identify herself as Alice by
generating the same random {19,24,51}. Then she sends {53,37,60}
to Bob. Again for simplicity suppose Bob generates the same E and
sends it to Carol. Now Carol is in trouble; she doesn't know the
numbers 9 and 10, and can only guess them. The protocol requires
Carol to send three numbers, say {x,y,z}, to Bob. Then Bob will
check:
x2 * 580 * 671 ÀÀ 53 (mod 77),
y2 * 581 * 670 ÀÀ 37 (mod 77),
z2 * 581 * 671 ÀÀ 60 (mod 77).
Carol will have succeeded in her masquerade if she chose {x,y,z}
to make these checks come out right. But 67-1 ÀÀ 102 ÀÀ 23 (mod 77)
and 58-1 ÀÀ 92 ÀÀ 4 (mod 77), so x2 ÀÀ 53 * 23 ÀÀ 64 (mod 77), y2 ÀÀ 37
* 4 ÀÀ 71 (mod 77) and z2 ÀÀ 60 * 23 * 4 ÀÀ 53 (mod 77). Could Carol
solve these quadratic equations to find, e.g., x = 36, y = 62, z
= 47? For a small value of N such as N = 77, she could indeed.
However, if N is a product of two appropriately-chosen large primes
(e.g., each 80 digits or more), and if these primes are kept secret
by the authority, then the answer is no. That is, computing square
roots modulo a composite is computationally infeasible (app. N).
Thus, anyone who does not know Alice's secret ({9,10} in the above)
cannot impersonate her when N is large.
Another possibility is that Alice's interaction with Bob might
give Bob information which could allow impersonation of Alice, at
least on one occasion, by replay. Suppose Bob tries to convince
Carol that he is really Alice. Bob might try to imitate Alice by
sending (53,37,60} to Carol to start the protocol. Now Carol
doesn't necessarily select the E above. Suppose she selects
1 1
F = 0 0 .
0 1
Ô trouble; he might try to imitate
Alice again by sending {36,62,47} to Carol. Then Carol will check
362 * 581 * 671 ÀÀ 71 (mod 77).
Since 71 ÀÀ 53 (mod 77), Carol knows Bob is a fraud even without
the other two checks. Can Bob send some {r,s,t} instead of
{36,62,47} ? This will only work if
r2 * 581 * 671 ÀÀ 53 (mod 77),
s2 * 580 * 670 ÀÀ 37 (mod 77),
t2 * 580 * 671 ÀÀ 60 (mod 77).
As before, this gives r2 ÀÀ 58-1 * 67-1 * 53 ÀÀ 25 (mod 77), and
similarly s2 ÀÀ 37 (mod 77), t2 ÀÀ 71 (mod 77). As above, Bob can
solve these quadratic equations to find r,s,t because N = 77 is
small, but could not do so if N were large. Also, in the above
there is one chance in 64 that Carol would choose F = E, in which
case Bob's deception would go unmasked; but for larger parameters
such as 4 and 5 instead of 2 and 3, this would again be improbable
(one chance in a million (2-20) instead of 64).
Another possibility is that when Alice identified himself to
Bob, she may have inadvertently revealed some information which
could enable Bob to learn his secret, i.e., {9,10}, which would
permit impersonation. For this protocol to be zero-knowledge this
should not be possible. Can Bob deduce the numbers {9,10} from the
two sets of numbers {53,37,60} and {36,62,47}, and E? He knows that
Alice started with three numbers {a,b,c}, but he doesn't know these
were {19,24,51}. He knows that Alice's secret is {u,v} but doesn't
know these are {9,10}. He knows that the authority computed u and
v from
u2 ÀÀ 58-1 ÀÀ 4 (mod 77),
v2 ÀÀ 67-1 ÀÀ 23 (mod 77).
He also knows that Alice computed
a2 ÀÀ 53 (mod 77),
b2 ÀÀ 37 (mod 77),
c2 ÀÀ 60 (mod 77),Ôsolved when N is large.
This shows informally that the above protocol works:
a. It identifies Alice by proving that she possesses the
secret {9,10}.
b. It identifies Alice uniquely: anyone who doesn't know
this secret cannot impersonate Alice.
c. Alice's secret is not revealed in the process of
proving she possesses it.
Actually, (a) means that the possessor of {9,10} is identified
as the system user who has ID = {58,67} assigned by the authority.
Also, no matter how many times Alice proves her identity, her
secret will not be revealed (if N is sufficiently large); i.e., (c)
states loosely that the protocol is zero-knowledge. All of this
depends on the assumption that equations of the form x2 ÀÀ y (mod N)
cannot be solved if N is the product of two large primes which are
not known, but can be solved easily if the primes are known (app.
N). Such equations lie at the heart of most concrete zero-knowledge
schemes.
The formal definition of zero-knowledge is more complicated (see
[GOLD89]), but the above example demonstrates its essence in a
context which has been proposed as a candidate for actual
implementation in smart-card based identification schemes.
Appendix P. Alternatives to the Diffie/Hellman model.
The text of this treatise has been based on the work of Diffie
and Hellman [DIFF76b]. This model of public-key cryptography
includes two characteristics which have received some criticism:
a. Security of Diffie/Hellman type systems is generally
established empirically, i.e., by failure of
cryptanalysis.
b. Security of Diffie/Hellman type systems is dependent uponÔome
provable sense. For example, it is difficult to guarantee that
partial information about plaintext (e.g., its least significant
bit) cannot be recovered from the corresponding ciphertext even
when the entire plaintext cannot be found.
In section 5 we noted some examples of authentication frameworks
(e.g., use of certificates) which bind user IDs and public keys.
Without such a superstructure a public-key system is useless, since
a user would not be certain that he was employing the correct
public key for encryption or decryption. The security of the
public-key system thus depends on proper functioning of the
authentication framework, which is a priori unrelated to the
underlying cryptosystem.
In this section we briefly examine two modifications of the
basic Diffie/Hellman model. In one case the goal is to incorporate
the binding between a user ID and public key directly into the
cryptosystem, thereby eliminating the separation between the
cryptosystem and the authentication framework. The other scheme
addresses the subject of knowledge concealment; it is closely
related to zero-knowledge proofs. Both schemes have received
considerable attention not only because of possibly enhanced
security, but also because of their potential relevance to smart-
card implementations of public-key cryptography.
P.1 Probabilistic encryption.
Goldwasser and Micali [GOLD84] note that the public-key systems
of Diffie and Hellman are not provably secure. They observe that
use of a trapdoor function f to generate such systems does not
exclude the possibility that f(x) = y may be solvable for x without
the (original) trapdoor under certain conditions. Also, even if x
cannot be found from f(x), it may be possible to extract partial
information about x. One problem is that such trapdoor systems
proceed block by block. This makes it difficult to prove security
with respect to concealment of partial information such as least
significant bit.
In [GOLD84] Goldwasser and Micali suggest an alternative to
trapdoor-based public-key systems. Their procedure is to encrypt
bit by bit. They call this probabilistic encryption. It introduces
several advantages, namely uniformly difficult decoding and hiding
of partial information. Their scheme has the following properties:
Ôe1,...,ek), which B sends to A. To decode e, A sets mi
= 1 if ei is a quadratic residue modulo N, and mi = 0 otherwise.
This can be effected by A in polynomial time since A knows p and
q (lemmas J.4.1, N.1.1). It is correct because y * zi, the product
of a quadratic nonresidue and residue, is a quadratic nonresidue
modulo N (lemma N.2.2).
The security of partial information follows from the fact that
each bit of the message m is encoded independently. A disadvantage
of the technique is data expansion: if |N| = n, then n bits are
transmitted for each bit of a message.
One application is coin flipping by telephone: A randomlyÔhich a ciphertext for a given plaintext is randomly chosen from
a set of possible ciphertexts. Rivest and Sherman also develop a
classification for such schemes. A major aspect of randomized
schemes is often significant data expansion. For example, the
Goldwasser/Micali scheme would probably have ciphertext around 512
times as large as the plaintext. On the other hand, probabilistic
schemes may be much faster than their deterministic counterparts,
an attractive feature for smart-card implementations.
P.2 Identity-based schemes.
In [SHAM84], Shamir suggests yet another modification of
traditional public-key systems. In Shamir's framework a user's
public key coincides with his system ID. This eliminates the need
for any superstructure for distribution of public keys. It also
trivializes the authentication of public keys. However, unlike a
traditional public-key scheme this modification requires a trusted
key generation center.
The center issues a smart card to each user, containing the
user's private key. Thus the "private" key is really a shared
secret key. A card can generate the user's digital signature. The
center does not maintain a database of keys; in fact it need not
even keep information beyond a list of user IDs (needed to ensure
that there are no duplicate IDs).
Ô
A weakness in such a scheme is that anyone (intruder or insider)
possessing the trapdoor information can forge the signature of any
user. This is in contradistinction, e.g., to a credit-card scheme
in which a transaction is generally valid only if accompanied by
a user's physical signature. Also, the center is not required to
maintain any information on lost or stolen cards; thus the loss of
a card is disastrous since the possessor can forge the legitimate
user's signature indefinitely. Furthermore, the center may find
itself involved in litigation produced by any such security
problems, since it is providing the means by which users generate
signatures. Again this in contrast to the credit-card situation:
if a credit card is stolen, the thief cannot forge the legitimate
holder's physical signature, providing a means of distinguishing
between legal and illegal usage of the card. Use of passwords
(PINs) with cards could largely eliminate the problems accruing
from lost or stolen cards, but compromise of the trapdoor would
still be disastrous.
Shamir's notion was later ([FEIG87],[FIAT86]) incorporated into
zero-knowledge schemes. One of these was used as the basis for the
example in appendix O.
REFERENCES
[ADLE79] L. Adleman, "A subexponential algorithm for the discrete
logarithm problem with applications to cryptography," in 20th
Annual Symposium on Foundations of Computer Science, San Juan,
Puerto Rico, October 29-31, 1979, pp. 55-60. Silver Spring, MD:
IEEE Computer Society Press, 1979.
[ADLE82] L. M. Adleman, "On breaking the iterated Merkle-Hellman
public-key cryptosystems," in D. Chaum, R. L. Rivest, and A. T.
Sherman, Eds., Advances in Cryptology: proceedings of CRYPTO 82,
a Workshop on the Theory and Application of Cryptographic
Techniques, Santa Barbara, CA, August 23-25, 1982, pp. 303-308. New
York: Plenum Press, 1983.
[ADLE86] L. M. Adleman and K. S. McCurley, "Open problems in number
theoretic complexity," in D. S. Johnson, T. Nishizeki, A. Nozaki,
and H. S. Wilf, Eds., Discrete Algorithms and Complexity,Ôhaum, Eds., Lecture
Notes in Computer Science Vol. 196: Advances in Cryptology:
Proceedings of CRYPTO 84, a Workshop on the Theory and Application
of Cryptographic Techniques, Santa Barbara, CA, August 19-22, 1984,
pp. 73-82. Berlin/New York: Springer-Verlag, 1985.
[BLAK83] G. R. Blakley, "A computer algorithm for calculating the
product AB modulo M," IEEE Transactions on Computers, Vol. C-32,
No. 5, May 1983, pp. 497-500.
[BLUM84] M. Blum and S. Micali, "How to generate cryptographicallyÔrickell, "A fast modular multiplication algorithm
with application to two key cryptography," in D. Chaum, R. L.
rivest, and A. T. Sherman, Eds., Advances in Cryptology:
proceedings of CRYPTO '82, a Workshop on the Theory and Application
of Cryptographic Techniques, Santa Barbara, CA, August 23-25, 1982,
pp. 51-60. New York: Plenum Press, 1983.
[BRIC83] E. F. Brickell, "Solving low density knapsacks," in D.
Chaum, Ed., Advances in Cryptology: proceedings of CRYPTO 83, a
Workshop on the Theory and Application of Cryptographic Techniques,
Santa Barbara, CA, August 22-24, 1983, pp. 25-37. New York: Plenum
Press, 1984.
[BRIC84] E. F. Brickell, "Breaking iterated knapsacks," in G. R.
Blakley and D. Chaum, Eds., Lecture Notes in Computer Science Vol.
196: Advances in Cryptology: Proceedings of CRYPTO 84, a Workshop
on the Theory and Application of Cryptographic Techniques, Santa
Barbara, CA, August 19-22, 1984, pp. 342-358. Berlin/New York:
Springer-Verlag, 1985.Ô987, pp. 103-121.
[COHE84] H. Cohen and H. W. Lenstra, Jr., "Primality testing and
Jacobi sums," Mathematics of Computation, Vol. 42, No. 165, January
1984, pp. 297-330.
[CONT80] Control Data Corporation, CDC CYBER 200 Model 205 Computer
System. Minneapolis, MN, 1980.
[COPP84] D. Coppersmith, "Fast evaluation of logarithms in fields
of characteristic two," IEEE Transactions on Information Theory,
Vol. IT-30, No. 4, July 1984, pp. 587-594.
[COPP85] D. Coppersmith, "Another birthday attack," in H. C.
Williams, Ed., Lecture Notes in Computer Science Vol. 218: Advances
in Cryptology - CRYPTO '85, proceedings of a Conference on the
Theory and Applications of Cryptographic Techniques, Santa Barbara,
CA, August 18-22, 1985, pp. 14-17. Berlin/New York: Springer-
Verlag, 1986.
[COPP87] D. Coppersmith, "Cryptography," IBM Journal of Research
and Development, Vol. 31, No. 2, March 1987, pp. 244-248.
[COPP86] D. Coppersmith, A. M. Odlyzko, and R. Schroeppel,
"Discrete logarithms in GF(p)," Algorithmica, Vol. 1, No. 1, 1986,
pp. 1-15.
[CRAY80] Cray Research, Inc., Cray 1-S Series Hardware Reference
Manual. Mendota Heights, MN, June 1980.
[CRAY85] Cray Research, Inc., Cray X-MP Series of Computer Systems.Ôeth, N. Cot, and I. Ingemarsson, Eds.,
Lecture Notes in Computer Science Vol. 209: Advances in Cryptology:
Proceedings of EUROCRYPT 84, a Workshop on the Theory and
Application of Cryptographic Techniques, Paris, France, April 9-
11, 1984, pp. 183-215. Berlin/New York: Springer-Verlag, 1985.
[DEMI83] R. DeMillo and M. Merritt, "Protocols for data security,"
Computer, Vol. 16, No. 2, February 1983, pp. 39-51.
[DENN79] D. E. Denning, "Secure personal computing in an insecure
network," Communications of the ACM, Vol. 22, No. 8, August 1979,
pp. 476-482.
[DENN83b] D. E. Denning, "Protecting public keys and signature
keys," Computer, Vol. 16, No. 2, February 1983, pp. 27-35.
[DENN81] D. E. Denning and G. M. Sacco, "Timestamps in key
distribution protocols," Communications of the ACM, Vol. 24, No.
8, August 1981, pp. 533-536.
[DENN83] D. E. R. Denning, Cryptography and Data Security. Reading,
MA: Addison-Wesley, 1983.
[DESM83] Y. Desmedt, J. Vandewalle, and R. J. M. Govaerts, "A
critical analysis of the security of knapsack public key
algorithms," IEEE Transactions on Information Theory, Vol. IT-30,
No. 4, July 1984, pp. 601-611.
[DIFF82] W. Diffie, "Conventional versus public key cryptosystems,"
in G. J. Simmons, Ed., Secure Communications and Asymmetric
Cryptosystems, pp. 41-72. Boulder, CO: Westview Press, 1982.
[DIFF84] W. Diffie, "Network security problems and approaches,"
Proceedings of the National Electronics Conference, Vol. 38, 1984,
pp. 292-314.
Ôontvale, NJ: AFIPS Press, 1976.
[DIFF76b] W. Diffie and M. E. Hellman, "New directions in
cryptography," IEEE Transactions on Information Theory, Vol. IT-22,
No. 6, November 1976, pp. 644-654.
[DIFF79] W. Diffie and M. E. Hellman, "Privacy and authentication:
an introduction to cryptography," Proceedings of the IEEE, Vol. 67,
No. 3, March 1979, pp. 397-427.
[DIFF87] W. Diffie, B. O'Higgins, L. Strawczynski, and D. Steer,
"An ISDN secure telephone unit," Proceedings of the National
Communications Forum, Vol. 41, No. 1, 1987, pp. 473-477.
[DIXO81] J. D. Dixon, "Asymptotically fast factorization of
integers," Mathematics of Computation, Vol. 36, No. 153, January
1981, pp. 255-260.
[DOLE81] D. Dolev and A. C. Yao, "On the security of public key
protocols," in 22nd Annual Symposium on Foundations of Computer
Science, Nashville, TN, October 28-30, 1981, pp. 350-357. Silver
Spring, MD: IEEE Computer Society Press, 1981.
[DUSS90] S. R. Dusse and B. S. Kaliski, Jr., "A cryptographic
library for the Motorola DSP 56000," presented at EUROCRYPT '90,
Aarhuis, DEnmark, May 21-24, 1990.
[EHRS78] W. F. Ehrsam, S. M. Matyas, C. H. Meyer, and W. L.
Tuchman, "A cryptographic key management scheme for implementing
the Data Encryption Standard," IBM Systems Journal, Vol. 17, No.
2, 1978, pp. 106-125.
[ELGA85] T. ElGamal, "A public key cryptosystem and a signature
scheme based on discrete logarithms," IEEE Transactions on
Information Theory, Vol. IT-31, No. 4, July 1985, pp. 469-472.
[ELGA85b] T. ElGamal, "On computing logarithms over finite fields,"
in H. C. Williams, Ed., Lecture Notes in Computer Science Vol. 218:
Advances in Cryptology - CRYPTO '85, proceedings of a Conference
on the Theory and Applications of Cryptographic Techniques, Santa
Barbara, CA, August 18-22, 1985, pp. 396-402. Berlin/New York:
Springer-Verlag, 1986.Ôugust 1974, pp. 437-442.
[FEIG87] U. Feige, A. Fiat, and A. Shamir, "Zero knowledge proofs
of identity," in Proceedings of the Nineteenth Annual ACM Symposium
on Theory of Computing, New York, NY, May 25-27, 1987, pp. 210-
217. New York: ACM, 1987.
[FIAT86] A. Fiat and A. Shamir, "How to prove yourself: practical
solutions to identification and signature problems," in A. M.
Odlyzko, Ed., Lecture Notes in Computer Science Vol. 263: Advances
in Cryptology - CRYPTO '86, proceedings of a Conference on the
Theory and Applications of Cryptographic Techniques, Santa Barbara,
CA, August 11-15, 1986, pp. 186-194. Berlin/New York: Springer-
Verlag, 1987.
[FLYN78] R. Flynn and A. S. Campasano, "Data dependent keys for a
selective encryption terminal," in S. P. Ghosh and L. Y. Liu, Eds.,
AFIPS Conference Proceedings Vol. 47: National Computer Conference,
Anaheim, CA, June 5-8, 1978, pp. 1127-1129. Montvale, NJ: AFIPS
Press, 1978.
[GARE79] M. R. Garey and D. S. Johnson, Computers and
Intractability. New York: W. H. Freeman, 1979.
[GILL77] J. Gill, "Computational complexity of probabilistic Turing
machines," SIAM Journal on Computing, Vol. 6, No. 4, December 1977,
pp. 675-695.
[GOLD84] S. Goldwasser and S. Micali, "Probabilistic encryption,"
Journal of Computer and System Sciences, Vol. 28, No. 2, April
1984, pp. 270-299.
[GOLD89] S. Goldwasser, S. Micali, and C. Rackoff, "The knowledge
complexity of interactive proof systems," SIAM Journal on
Computing, Vol. 18, No. 1, February 1989, pp. 186-208.
[GOLD88] S. Goldwasser, S. Micali, and R. L. Rivest, "A digital
signature scheme secure against adaptive chosen-message attacks,"
SIAM Journal on Computing, Vol. 17, No. 2, April 1988, pp. 281-308.
[GORD84b] J. Gordon, "Strong RSA keys," Electronics Letters, Vol.
20, No. 12, June 7, 1984, pp. 514-516.
[GORD84] J. A. Gordon, "Strong primes are easy to find," in T.
Beth, N. Cot, and I. Ingemarsson, Eds., Lecture Notes in Computer
Science Vol. 209: Advances in Cryptology: Proceedings of EUROCRYPT
84, a Workshop on the Theory and Application of Cryptographic
Techniques, Paris, France, April 9-11, 1984, pp. 216-223.
Berlin/New York: Springer-Verlag, 1985.
[GROL88] J. Grollman and A. L. Selman, "Complexity measures forÔ
Architecture, 1987.
[JUEN82] R. R. Jueneman, "Analysis of certain aspects of output
feedback mode," in D. Chaum, R. L. Rivest, and A. T. Sherman, Eds.,
Advances in Cryptology - proceedings of CRYPTO 82, a Workshop on
the Theory and Application of Cryptographic Techniques, Santa
Barbara, CA, August 23-25, 1982, pp. 99-127. New York: PlenumÔys (for VLSI),"
in I. S. Duff and G. W. Stewart, Eds., Sparse Matrix Proceedings,
pp. 245-282. Philadelphia: SIAM, 1978.
[KUNG82b] S. Y. Kung, K. S. Arun, R. J. Gal-Ezer, and D. V. B. Rao,
"Wavefront array processor: language, architecture, and
applications," IEEE Transactions on Computers, Vol. C-31, No. 11,
November 1982, pp. 1054-1066.
[LAGA84] J. C. Lagarias, "Performance analysis of Shamir's attack
on the basic Merkle-Hellman knapsack system," in J. Paredaens, Ed.,
Lecture Notes in Computer Science Vol. 172: Automata, Languages and
Programming: 11th Colloquium, Antwerp, Belgium, July 16-20, 1984,
pp. 312-323. Berlin/New York: Springer-Verlag, 1984.Ôasse, "Factoring by electronic
mail," to appear in proceedings of EUROCRYPT '89.
[LENS83] H. W. Lenstra, Jr., "Integer programming with a fixed
number of variables," Mathematics of Operations Research, Vol. 8,
No. 4, November 1983, pp. 538-548.
[LENS86] H. W. Lenstra, Jr., "Primality testing," in J. W. de
Bakker et al., Eds., Mathematics and Computer Science, CWI
Monographs, I, pp. 269-287. Amsterdam/New York: North-Holland,
1986.
[LENS87] H. W. Lenstra, Jr., "Factoring integers with elliptic
curves," Annals of Mathematics, Vol. 126, 1987, pp. 649-673.
[LEWI81] H. R. Lewis and C. H. Papadimitriou, Elements of the
Theory of Computation. Englewood Cliffs, NJ: Prentice-Hall, 1981.
[LINN89] J. Linn and S. T. Kent, "Privacy for DARPA-Internet mail,"
in Proceedings of the 12th National Computer Security Conference,
Baltimore, MD, October 10-13, 1989, pp. 215-229.
Ôtions and DES," preprint.
[MERK78b] R. C. Merkle and M. E. Hellman, "Hiding information and
signatures in trapdoor knapsacks," IEEE Transactions on Information
Theory, Vol. 24, No. 5, September 1978, pp. 525-530.
[MILL76] G. L. Miller, "Riemann's hypothesis and tests for
primality," Journal of Computer and System Sciences, Vol. 13, No.
3, December 1976, pp. 300-317.
[MILU88] V. M. Milutinovic, Computer Architecture: Concepts and
Systems. New York: North-Holland, 1988.
[MONT85] P. L. Montgomery, "Modular multiplication without trial
division," Mathematics of Computation, Vol. 44, No. 170, April
1985, pp. 519-521.
[MOOR88] J. H. Moore, "Protocol failures in cryptosystems,"
Proceedings of the IEEE, Vol. 76, No. 5, May 1988, pp. 594-602.
[MORR75] M. A. Morrison and J. Brillhart, "A method of factoring
and the factorization of F7," Mathematics of Computation, Vol. 29,
No. 129, January 1975, pp. 183-205.
[NATI77] National Bureau of Standards, Federal InformationÔings of EUROCRYPT 84, a Workshop on
the Theory and Application of Cryptographic Techniques, Paris,
France, April 9-11, 1984, pp. 224-314. Berlin/New York: Springer-
Verlag, 1985.
[ORTO86] G. A. Orton, M. P. Roy, P. A. Scott, L. E. Peppard, and
S. E. Tavares, "VLSI implementation of public-key encryption
algorithms," in A. M. Odlyzko, Ed., Lecture Notes in Computer
Science Vol. 263: Advances in Cryptology - CRYPTO '86, proceedings
of a Conference on the Theory and Applications of Cryptographic
Techniques, Santa Barbara, CA, August 11-15, 1986, pp. 277-301.
Berlin/New York: Springer-Verlag, 1987.
[PATT87] W. Patterson, Mathematical Cryptology for Computer
Scientists and Mathematicians. Totowa, NJ: Rowman & Littlefield,
1987.
[PERA86] R. C. Peralta, "A simple and fast probabilistic algorithm
for computing square roots modulo a prime number," IEEE
Transactions on Information Theory, Vol. 32, No. 6, November 1986,
pp. 846-847.
[POHL78] S. C. Pohlig and M. E. Hellman, "An improved algorithm for
computing logarithms over GF(p) and its cryptographic
significance," IEEE Transactions on Information Theory, Vol. IT-24,
No. 1, January 1978, pp. 106-110.
[POME84] C. Pomerance, "The quadratic sieve factoring algorithm,"
in T. Beth, N. Cot, and I. Ingemarsson, Eds., Lecture Notes in
Computer Science Vol. 209: Advances in Cryptology: proceedings of
EUROCRYPT 84, a Workshop on the Theory and Application ofÔg, Vol. 17, No. 2, April 1988,
pp. 387-403.
[POPE78] G. J. Popek and C. S. Kline, "Encryption protocols, public
key algorithms and digital signatures in computer networks," in R.
A. DeMillo, D. P. Dobkin, A. K. Jones, and R. J. Lipton, Eds.,
Foundations of Secure Computation, pp. 133-153. New York: Academic
Press, 1978.
[POPE79] G. L. Popek and C. S. Kline, "Encryption and secure
computer networks," ACM Computing Surveys, Vol. 11, No. 4, December
1979, pp. 331-356.
[QUIN87] M. J. Quinn, Designing Efficient Algorithms for Parallel
Computers. New York: McGraw-Hill, 1987.
[QUIS82] J.-J. Quisquater and C. Couvreur, "Fast decipherment
algorithm for RSA public-key cryptosystem," Electronics Letters,
Vol. 18, No. 21, October 14, 1982, pp. 905-907.
[RABI76] M. O. Rabin, "Probabilistic algorithms," in J. F. Traub,
Ed., Algorithms and Complexity: New Directions and Recent Results,
proceedings of a Symposium, Pittsburgh, PA, April 7-9, 1976, pp.
21-39. New York: Academic Press, 1976.
[RABI78] M. O. Rabin, "Digitalized signatures," in R. A. DeMillo,
D. P. Dobkin, A. K. Jones, and R. J. Lipton, Eds., Foundations of
Secure Computation, pp. 155-168. New York: Academic Press, 1978.
[RABI79] M. O. Rabin, "Digitalized signatures and public-key
functions as intractable as factorization," MIT Laboratory for
Computer Science, Technical Report LCS/TR-212, January 1979.
[RABI80] M. O. Rabin, "Probabilistic algorithms for testing
primality," Journal of Number Theory, Vol. 12, 1980, pp. 128-138.
[RADE64] H. Rademacher, Lectures on Elementary Number Theory. New
York: Blaisdell, 1964.
[RIVE84] R. L. Rivest, "RSA chips (past/present/future)," in T.
Beth, N. Cot, and I. Ingemarsson, Eds., Lecture Notes in Computer
Science Vol. 209: Advances in Cryptology: proceedings of EUROCRYPT
84, a Workshop on the Theory and Application of CryptographicÔm," February
1990.
[RIVE78] R. L. Rivest, A. Shamir, and L. Adleman, "A method for
obtaining digital signatures and public-key cryptosystems,"
Communications of the ACM, Vol. 21, No. 2, February 1978, pp.
120-127.
[RIVE82] R. L. Rivest and A. T. Sherman, "Randomized encryption
techniques," in D. Chaum, R. L. Rivest, and A. T. Sherman, Eds.,
Advances in Cryptology: Proceedings of CRYPTO 82, a Workshop on the
Theory and Application of Cryptographic Techniques, Santa Barbara,
CA, August 23-25, 1982, pp. 145-163. New York: Plenum Press, 1983.
[SIAM90] "Number field sieve produces factoring breakthrough," SIAM
News, Vol. 23, No. 4, July 1990.
[SALO85] Salomaa, "Cryptography," in A. Salomaa, Encyclopedia of
Mathematics and its Applications Vol. 25: Computation and Automata,
pp. 186-230. Cambridge, UK: Cambridge University Press, 1985.
[SCHA82] B. P. Schanning, "Applying public key distribution to
local area networks," Computers & Security, Vol. 1, No. 3, November
1982, pp. 268-274.
[SCHA80] B. P. Schanning, S. A. Powers, and J. Kowalchuk, "MEMO:
privacy and authentication for the automated office," in
proceedings of the 5th Conference on Local Computer Networks,
Minneapolis, MN, October 6-7, 1980, pp. 21-30. Silver Spring, MD:
IEEE Computer Society Press, 1980.
[SCHN84] C. P. Schnorr and H. W. Lenstra, Jr., "A Monte Carlo
factoring algorithm with linear storage," Mathematics of
Computation, Vol. 43, No. 167, July 1984, pp. 289-311.
[SEDL87] H. Sedlak, "The RSA Cryptography Processor," in D. Chaum
and W. L. Price, Eds., Lecture Notes in Computer Science Vol. 304:
Advances in Cryptology - EUROCRYPT '87, a Workshop on the Theory
and Applications of Cryptographic Techniques, Amsterdam, The
Netherlands, April 13-15, 1987, pp. 95-105. Berlin/New York:
Springer-Verlag, 1988.
[SEIT85] C. L. Seitz, "The Cosmic Cube," Communications of the ACM,
Vol. 28, No. 1, January 1985, pp. 22-33.
[SHAM79] A. Shamir, "On the cryptocomplexity of knapsack systems,"
in proceedings of the Eleventh Annual ACM Symposium on Theory of
Computing, Atlanta, GA, April 30 - May 2, 1979, pp. 118-129. New
York: ACM, 1979.
[SHAM84b] A. Shamir, "Identity-based cryptosystems and signatureÔ Society Press, 1986.
[TANE81] A. S. Tanenbaum, Computer Networks. Englewood Cliffs, NJ:
Prentice-Hall, 1981.
[WAGN84] N. R. Wagner and M. R. Magyarik, "A public-key
cryptosystem based on the word problem," in G. R. Blakley and D.
Chaum, Eds., Lecture Notes in Computer Science Vol. 196: Advances
in Cryptology - Proceedings of CRYPTO 84, a Workshop on the Theory
and Applications of Cryptographic Techniques, Santa Barbara, CA,
August 19-22, 1984, pp. 19-36. Berlin/New York: Springer-Verlag,
1985.
Brought to you
|