INTRODUCTION CRYPTOGRAPHY HAS A LONG AND FASCINATING HISTORY THE MOST COMPLETE NONTECHNICAL ACCOUNT OF THE SUBJECT IS KAHN S THE CODEBREAKERS THIS BOOK TRACES CRYPTOGRAPHY FROM ITS INITIAL AND LIMITED USE BY THE EGYPTIANS SOME YEARS AGO TO THE TWENTIETH CENTURY WHERE IT PLAYED A CRUCIAL ROLE IN THE OUTCOME OF BOTH WORLD WARS COMPLETED IN KAHN S BOOK COVERS THOSE ASPECTS OF THE HISTORY WHICH WERE MOST SIGNIFICANT UP TO THAT TIME TO THE DEVELOPMENT OF THE SUBJECT THE PREDOMINANT PRACTITIONERS OF THE ART WERE THOSE ASSOCIATED WITH THE MILITARY THE DIPLOMATIC SERVICE AND GOVERNMENT IN GENERAL CRYPTOGRAPHY WAS USED AS A TOOL TO PROTECT NATIONAL SECRETS AND STRATEGIES THE PROLIFERATION OF COMPUTERS AND COMMUNICATIONS SYSTEMS IN THE S BROUGHT WITH IT A DEMAND FROM THE PRIVATE SECTOR FOR MEANS TO PROTECT INFORMATION IN DIGITAL FORM AND TO PROVIDE SECURITY SERVICES BEGINNING WITH THE WORK OF FEISTEL AT IBM IN THE EARLY S AND CULMINATING IN WITH THE ADOPTION AS A U S FEDERAL INFORMATION PROCESSING STANDARD FOR ENCRYPTING UNCLASSIFIED INFORMATION DES THE DATA ENCRYPTION STANDARD IS THE MOST WELLKNOWN CRYPTOGRAPHIC MECHANISM IN HISTORY IT REMAINS THE STANDARD MEANS FOR SECURING ELECTRONIC COMMERCE FOR MANY FINANCIAL INSTITUTIONS AROUND THE WORLD THE MOST STRIKING DEVELOPMENTIN THE HISTORY OF CRYPTOGRAPHYCAME IN WHEN DIFFIE AND HELLMAN PUBLISHED NEW DIRECTIONS IN CRYPTOGRAPHY THIS PAPER INTRODUCED THE REVOLUTIONARY CONCEPT OF PUBLICKEY CRYPTOGRAPHY AND ALSO PROVIDED A NEW AND INGENIOUS METHOD FOR KEY EXCHANGE THE SECURITY OF WHICH IS BASED ON THE INTRACTABILITY OF THE DISCRETE LOGARITHM PROBLEM ALTHOUGH THE AUTHORS HAD NO PRACTICAL REALIZATION OF A PUBLICKEY ENCRYPTION SCHEME AT THE TIME THE IDEA WAS CLEAR AND IT GENERATED EXTENSIVE INTEREST AND ACTIVITY IN THE CRYPTOGRAPHIC COMMUNITY IN RIVEST SHAMIR AND ADLEMAN DISCOVERED THE FIRST PRACTICAL PUBLICKEY ENCRYPTION AND SIGNATURE SCHEME NOW REFERRED TO AS RSA THE RSA SCHEME IS BASED ON ANOTHER HARD MATHEMATICAL PROBLEM THE INTRACTABILITY OF FACTORING LARGE INTEGERS THIS APPLICATION OF A HARD MATHEMATICAL PROBLEM TO CRYPTOGRAPHY REVITALIZED EFFORTS TO FIND MORE EFFICIENT METHODS TO FACTOR THE S SAW MAJOR ADVANCES IN THIS AREA BUT NONE WHICH RENDERED THE RSA SYSTEM INSECURE ANOTHER CLASS OF POWERFUL AND PRACTICAL PUBLICKEY SCHEMES WAS FOUND BY ELGAMAL IN THESE ARE ALSO BASED ON THE DISCRETE LOGARITHM PROBLEM ONE OF THE MOST SIGNIFICANT CONTRIBUTIONS PROVIDED BY PUBLICKEY CRYPTOGRAPHY IS THE DIGITAL SIGNATURE IN THE FIRST INTERNATIONAL STANDARD FOR DIGITAL SIGNATURES ISO IEC WAS ADOPTED IT IS BASED ON THE RSA PUBLICKEY SCHEME IN THE U S GOVERNMENT ADOPTED THE DIGITAL SIGNATURE STANDARD A MECHANISM BASED ON THE ELGAMAL PUBLICKEY SCHEME THE SEARCH FOR NEW PUBLICKEY SCHEMES IMPROVEMENTS TO EXISTING CRYPTOGRAPHIC MECHANISMS AND PROOFS OF SECURITY CONTINUES AT A RAPID PACE VARIOUS STANDARDS AND INFRASTRUCTURES INVOLVING CRYPTOGRAPHY ARE BEING PUT IN PLACE SECURITY PRODUCTS ARE BEING DEVELOPED TO ADDRESS THE SECURITY NEEDS OF AN INFORMATION INTENSIVE SOCIETY THE PURPOSE OF THIS BOOK IS TO GIVE AN UP TO DATE TREATISE OF THE PRINCIPLES TECHNIQUES AND ALGORITHMS OF INTEREST IN CRYPTOGRAPHIC PRACTICE EMPHASIS HAS BEEN PLACED ON THOSE ASPECTS WHICH ARE MOST PRACTICAL AND APPLIED THE READER WILL BE MADE AWARE OF THE BASIC ISSUES AND POINTED TO SPECIFIC RELATED RESEARCH IN THE LITERATURE WHERE MORE INDEPTH DISCUSSIONS CAN BE FOUND DUE TO THE VOLUME OF MATERIAL WHICH IS COVERED MOST RESULTS WILL BE STATED WITHOUT PROOFS THIS ALSO SERVES THE PURPOSE OF NOT OBSCURING THE VERY APPLIED NATURE OF THE SUBJECT THIS BOOK IS INTENDED FOR BOTH IMPLEMENTERS AND RESEARCHERS IT DESCRIBES ALGORITHMS SYSTEMS AND THEIR INTERACTIONS CHAPTER IS A TUTORIAL ON THE MANY AND VARIOUS ASPECTS OF CRYPTOGRAPHY IT DOES NOT ATTEMPT TO CONVEY ALL OF THE DETAILS AND SUBTLETIES INHERENT TO THE SUBJECT ITS PURPOSE IS TO INTRODUCE THE BASIC ISSUES AND PRINCIPLES AND TO POINT THE READER TO APPROPRIATE CHAPTERS IN THE BOOK FOR MORE COMPREHENSIVE TREATMENTS SPECIFIC TECHNIQUES ARE AVOIDED IN THIS CHAPTER