AbstractIntroductionValue of Public Key CryptographyRSA Reliance on Large Prime NumbersWhat Makes a Prime StrongTwo Approaches of Finding Large PrimesMaurer’s AlgorithmOverview of Maurer’s Random Prime ProcedureExponentiateRandomPrimeTestTrialDivisionG_optGenerateSizeListCheckLemma1Outline of Technical ApproachObjective of the ProjectExpected ResultsResourcesHardwareSoftwareOverview of Program DesignTesting ProceduresMain Program LevelRandom Prime Procedure LevelFunction LevelProgram PerformanceSpeedMemory UsageStored File SizeRun-Time RAM RequirementsThe amount of RAM used depends on the number of variables usDesign and Development IssuesLibrary DifficultiesCompromises in Procedure DesignSummary of Program ResultsReview of Data CollectedAnalysis of DataDegree of Agreement With Expected ResultsPractical Application of ResultsConclusionsReferencesGeorge Mason University Electrical and Computer Engineering (ECE) Cryptography and Computer Network Security ECE-543 (Fall 2000) Project Report Constructing Large Random Primes for RSA using Deterministic Methods: Maurer’s Algorithm (Project SK-3) 15 December 2000 Michael Hammer Issam AndoniGeorge Mason University 15 December, 2000 ECE 543/646 Project Table of Contents 1 Abstract................................................................................................................................... 1 2 Introduction............................................................................................................................. 1 2.1 Value of Public Key Cryptography..................................................................................... 1 2.2 RSA Reliance on Large Prime Numbers............................................................................ 2 2.3 What Makes a Prime Strong ............................................................................................... 2 2.4 Two Approaches of Finding Large Primes......................................................................... 3 3 Maurer’s Algorithm ................................................................................................................ 3 3.1 Overview of Maurer’s Random Prime Procedure .............................................................. 3 3.1.1 Exponentiate ............................................................................................................... 4 3.1.2 Random....................................................................................................................... 4 3.1.3 PrimeTest.................................................................................................................... 4 3.1.4 TrialDivision............................................................................................................... 5 3.1.5 G_opt........................................................................................................................... 5 3.1.6 GenerateSizeList......................................................................................................... 5 3.1.7 CheckLemma1............................................................................................................ 5 4 Outline of Technical Approach............................................................................................... 5 4.1 Objective of the Project ...................................................................................................... 5 4.2 Expected Results................................................................................................................. 5 4.3 Resources............................................................................................................................ 5 4.3.1 Hardware..................................................................................................................... 5 4.3.2 Software...................................................................................................................... 6 4.4 Overview of Program Design ............................................................................................. 6 4.5 Testing Procedures.............................................................................................................. 6 4.5.1 Main Program Level ................................................................................................... 6 4.5.2 Random Prime Procedure Level................................................................................. 7 4.5.3 Function Level ............................................................................................................7 4.6 Program Performance .........................................................................................................8 4.6.1 Speed........................................................................................................................... 8 4.6.2 Memory Usage............................................................................................................ 8 4.6.3 Design and Development Issues................................................................................. 8 5 Summary of Program Results............................................................................................... 10 5.1 Review of Data Collected................................................................................................. 10 5.2 Analysis of Data................................................................................................................ 11 5.3 Degree of Agreement With Expected Results .................................................................. 11 5.4 Practical Application of Results........................................................................................ 11 6 Conclusions........................................................................................................................... 11 7 References............................................................................................................................. 12 Appendix A: Original Source Code iGeorge Mason University 15 December, 2000 ECE 543/646 Project Constructing Large Random Primes for RSA using Deterministic Methods: Maurer’s Algorithm 1 Abstract Generating keys for cryptographic applications requires the ability to generate sufficiently large random prime numbers. The degree to which they are both large and random increases the
View Full Document
Unlocking...