programmers resources
  http://www.intel-assembler.it/  (c)2017 intel-assembler.it   info@intel-assembler.it
 
Search :  
Lingua Italiana    English Language   
Index
 
just an empty assembly space
just an arrow Intel Platform
just an arrow Article & Guides
just an arrow Download Software


23/01/2009 Featured Article: How to remove Buzus Virus (permalink)




:::3063304:::
Bottone Scambio Directory Pubblicitaonline.it
Home Page | Articles & Guides | Download | Intel Platform | Contacts

Google
 


Bookmark and Share
Download 
Tell a friend



PUBLIC-KEY CRYPTOGRAPHY

Theory and practice in public cryptography

(by james nechvatal)

A 130+ page document about cryptografy using public keys. It covers mathematics, digital signatures, hash functions and security issues.
This article is online from 2693 days and has been seen 2525 times




                     PUBLIC-KEY CRYPTOGRAPHY

James Nechvatal
Security Technology Group
National Computer Systems Laboratory
National Institute of Standards and Technology
Gaithersburg, MD 20899

December 1990

                            PREFACE

   This publication presents a state-of-the-art survey of public-
key cryptography circa 1988 - 1990. In doing so, it covers a number
of different topics including:

       1. The theory of public-key cryptography.

       2. Comparisons to conventional (secret-key) cryptography.

       3. A largely self-contained summary of relevant mathematics.

       4. A survey of major existing public-key systems.

       5. An exploration of digital signatures and hash functions.

       6. A survey of public-key implementations in networks.

       7. An introduction to zero-knowledge protocols and
          probabilistic encryption.

       8. An exploration of security issues and key sizes.

   The treatment of public-key cryptography in this publication
includes both theory and practice. Much of the existing published
work, including those documents listed in the references, treats
either the theory or specific systems/implementations, but not
both. The viewpoint here is that the theory and practice are
inseparable.

   Any mention of commercial products is for purposes of
explanation and illustration only. Also, the selection of
cryptosystems and hash functions mentioned in this publication
serve only to provide examples. Such identification does not imply
recommendation or endorsement by the National Institute of
Standards and Technology, nor does it imply that systems or
functions identified are necessarily the best available for the
purpose.

   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
topics of hash functions and digital signatures. Extensive coverage
of key management is also included, with a focus on certificate-
based management. Section 4 gives some examples of public-key
systems and hash functions. Section 5 gives some examples of actual
or proposed implementations of public-key cryptography. The major
example is the International Organization for Standardization (ISO)
authentication framework.

   Section 6 gives a sample proposal for a local-area network
implementation of public-key cryptography. It draws heavily on the
work of ISO.

   A variety of topics are covered in the appendices, including a
summary of relevant mathematics and algorithms. Also included is
a brief introduction to zero-knowledge protocols, probabilistic
encryption and identity-based public-key systems.

   In the following, letters refer to appendices; e.g. lemma G.2.1
refers to a lemma appearing in section 2 of appendix G.

   The author wishes to thank Dr. Ronald L. Rivest, Dr. Gustavus
Simmons, and Dr. Dennis Branstad for providing many comments and
suggestions, and Dr. Burton S. Kaliski Jr. for providing
information on implementations of the RSA public-key system. The
paper was edited by Miles Smid.

   This paper was supported in part by the United States Department
of Computer-Aided Logistics Supports, Department of Defense.


CONTENTS

1. Cryptosystems and cryptanalysis...............................1
   1.1 Requirements for secrecy..................................2
   1.2 Requirements for authenticity and integrity...............4
   1.3 Conventional systems......................................5
   1.4 Example of a conventional cipher: DES.....................5
   1.5 Another conventional cipher: exponentiation...............6
   1.6 Public-key cryptosystems..................................7
        1.6.1 Secrecy and authenticity...........................8
        1.6.2 Applicability and limitations.....................10

2. Key management...............................................12
   2.1 Secret-key management....................................12
   2.2 Public distribution of secret keys.......................13
   2.3 Management of public components in a public-key system...15
        2.3.1 Use of certificates...............................16
        2.3.2 Generation and storage of component pairs.........17
        2.3.3 Hardware support for key management...............18
   2.4 Using public-key systems for secret key distribution.....19
        2.4.1 A protocol for key exchange.......................20
   2.5 Protocols for certificate-based key management...........22
        2.5.1 Certificate management by a central authority.....22
        2.5.2 Decentralized management..........................23
        2.5.3 A phone-book approach to certificates.............24

3. Digital signatures and hash functions........................25
   3.1 Public-key implementation of signatures..................27
        3.1.1 Signing messages..................................27
        3.1.2 The issue of nonrepudiation.......................29
        3.1.3 The issue of proof of delivery....................30
   3.2 Hash functions and message digests.......................31
        3.2.1 Usage of hash functions...........................33
        3.2.2 Relation to one-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
               4.1.3.1 Restrictions on p and q..................43
               4.1.3.2 Notes on factoring.......................44
        4.1.4 Low-exponent versions of RSA......................45
   4.2 Other public-key systems.................................46
        4.2.1 Knapsack systems..................................47
        4.2.2 The ElGamal signature scheme......................49
   4.3 Examples of hash functions...............................53
        4.3.1 Merkle's meta-method..............................53
        4.3.2 Coppersmith's attack on Rabin-type functions......56
        4.3.3 Quadratic congruential hash functions.............57
   4.4 Hardware and software support............................58
        4.4.1 Design considerations for RSA chips...............58
        4.4.2 Proposed designs for RSA chips....................59

5. Implementations of public-key cryptography...................61
   5.1 MITRENET.................................................61
   5.2 ISDN.....................................................62
        5.2.1 Keys..............................................62
        5.2.2 Calling...........................................63
   5.3 ISO Authentication Framework.............................64
        5.3.1 Use of certificates...............................64
        5.3.2 Certification paths...............................65
        5.3.3 Expiration and revocation of certificates.........66
        5.3.4 Authentication 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
   A.1 Computational complexity and cryptocomplexity............83
   A.2 Classical complexity theory..............................84
   A.3 Public-key systems and cryptocomplexity..................84
   A.4 Probabilistic algorithms.................................85
   A.5 Status of some relevant problems.........................86

Appendix B. Algorithms and architectures........................89
   B.1 Technology...............................................89
   B.2 Computing modes..........................................90
   B.3 Some relevant algorithms and implementation..............92
       B.3.1 Quadratic 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
   J.1 Quadratic residues modulo a prime.......................115
   J.2 The Jacobi symbol.......................................116
   J.3 Square roots modulo a prime.............................117
   J.4 Quadratic residuosity modulo a prime....................118

Appendix K. Primitive roots and discrete logarithms............119

Appendix L. Primality testing..................................123
   L.1 The Solovay/Strassen test...............................124
   L.2 Lehman's test...........................................125
   L.3 The Miller/Rabin test...................................126

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

Figure 1. Adaptive Chosen Plaintext Attack........................3
Figure 2. Using Public-Key for Secrecy and Authenticity..........10
Figure 3. The Diffie/Hellman Key Exchange........................15
Figure 4. A Protocol for Real-Time Authentication................21
Figure 5. A Protocol for Signing with Hash Function and Secrecy..28
Figure 6. Using RSA for Authenticity and Secrecy.................40
Figure 7. The ElGamal Signature Algorithm........................51
Figure 8. One-Way Authentication Protocol........................69




Top
Download 
Tell a friend
Bookmark and Share



Similar Articles

CLASSICAL CRYPTOGRAPHY COURSE
Course in 24 lesson
(by LANAKI)

RSA manual
Theory and implementation of RA
(by RSA Laboratories)

 Tags: cryptography


webmaster jes
writers rguru, tech-g, aiguru, drAx

site optimized for IE/Firefox/Chrome with 1024x768 resolution

Valid HTML 4.01 Transitional


ALL TRADEMARKS ® ARE PROPERTY OF LEGITTIMATE OWNERS.
© ALL RIGHTS RESERVED.

hosting&web - www.accademia3.it

grossocactus
find rguru on
http://www.twitter.com/sicurezza3/
... send an email ...
Your name

Destination email

Message

captcha! Code