Factoring of Large Numbers Using Reconfigurable Computer Project Specification Miaoqing Huang [email protected] Factoring a large integer into prime factors is one of the challenging tasks in cryptanalysis both in terms of computational complexity and the practical implementation. The security of widely used public key cryptosystem RSA mainly depends on this characteristic. Recently there has been much focus on development and implementation of various factorization algorithms. Of these currently available algorithms, Number Field Sieve (NFS) algorithm is known to be the most efficient with a large integer number (110 digits or more). Factorization of 512-bit was successfully done in 1999 and recently in March 2003, factorization of 530 bits was done. These experiments used distributed PCs and supercomputers which are general purpose computers. For this project, we will try to implement the second step, sieving, of the complete NFS algorithm in one FPGA chip in the reconfigurable platform, SRC-6E. Meanwhile, we will analysis the performance, cost and feasibility of the hardware design and compare our solution with other published approaches. 1. Platform SRC-6E Reconfigurable Computer by SRC Computers, Inc. 2. Algorithm to be implemented The second step of NFS algorithm, sieving, which is the costliest and most difficult step in the four steps to factor a large composite number. Several approaches to realize the step have been reported with their respective advantages and disadvantages. We will select one implementation method from two proposals, mesh-based circuit or TWIRL and realize it on SRC-6E platform. 3. Design Entry Method C, MAP C, Verilog HDL, and VHDL under Linux platform 4. Function Description The sieving step concerns with finding many co-prime (a,b) pairs, -A ≤a< A, 0<b<B, such that F1(a,b) and F2(a,b) are both smooth with respect to the chosen factor bases. To realize the above function, currently, there are two candidates, TWIRL and mesh-based circuit.For the two proposals, they both target on ASIC chips and have their respective advantages. Now we want to implement one of them on reconfigurable platform, i.e. FPGA chips. TWIRL includes three different implementation levels, Largish, Smallish and Tiny models. Probably, we will start from the Tiny model and then further to bigger design. The sieving based on Bernstein’s mesh-based approach is proposed by Geiselmann and Steinwandt. The mesh for processing units hold the pairs (p,r,i) for prime, residue and index specifying algebraic or rational factor base. Sorting through these triples and comparing to thresholds, the numbers with high probability of being smooth are searched with respective prime factors. One proposal will be selected to be realized on reconfigurable platform. 5. Testing Procedure The test vector will be fed into the FPGA chip from the CPU side. When the result is available, it will be checked with expected result to verify the correctness and accuracy of the whole design. Meanwhile, we will adjust the parameters of the design to evaluate the influence of respective parameters to the implementation. 6. Time Schedule Sept. 26th First specification version submission Sept. 27th – Oct. 2nd Basic theory and concepts learning and understanding Oct. 3rd Final specification version submission Oct. 4th – Oct. 12th Algorithm studying and flow diagram generating Oct. 9th Implementation Plan Selection Oct. 13th First progress report Oct. 14th – Nov. 2nd FPGA implementation of the selected approach Nov. 3rd Second progress report Nov. 4th – Nov. 10th Design Verification Nov. 11th – Nov. 16th Design Optimization Nov. 17th Third progress report Nov. 18th – Nov. 30th Design Analysis and Draft reports writing Dec. 1st Final progress report with the draft version of the final viewgraph presentation Dec. 2nd – Dec. 10th Design Analysis and Report ModificationDec. 11th Project reports submission Dec. 13th Project reports review submission Dec. 15th Final Oral Presentation and final written reports 7. Possible areas of the specification to be changed • The definition of function description will be much more detailed with the understanding of algorithm and progress of project. • The scale of the design, i.e. how many basic units can be includes in one FPGA chips, will be defined with project progress. • The timetable of project will be adjusted with the actual progress. • The literature list is to be altered with the project progress. 8. List of literature [1] http://www.srccomputers.com/ The website of the manufacturer of platform [2] "SRC-6E MAP Hardware Guide", SRC Computers, Inc. 2004. [3] "SRC-6 C Programming Environment V1.7 Guide", SRC Computers, Inc. 2004. [4] A. K. Lenstra, E. Tromer, A. Shamir, W. Kortsmit, B. Dodson, J. Hughes, and P. Leyland, “Factoring estimates for a 1024-bit RSA modulus”, Proc. Asiacrypt 2003, Springer-Verlag, to appear. http://www.wisdom.weizmann.ac.il/~tromer/ [5] A.J.Menezes, P.C. Van Oorschot, and S.A.Vanstone, “Handbook of Applied Cryptology”, Chapters 3.2.6-3.2.7, pp.95-98, 1997 [6] “Factoring Large Numbers: Fun or Applied Science?”, http://www.cwi.nl/publications/annual-reports/1999/AR/PDF/factoring.pdf [7] A. K. Lenstra, A. Shamir, J. Tomlinson, and E. Tromer, “Analysis of Bernstein’s Factorization Circuit”, Proc. Asia-crypt 2002, LNCS 2501, 1-26, Springer-Verlag, 2002 [8] Daniel J. Bernstein, “Circuits For Integer Factorization: A Proposal”, NSF DMS, 2001 [9] Adi Shamir, and Eran Tromer, “On the cost of factoring RSA-1024”, RSA CryptoBytes. Vol.6 No.2, 10-19, 2003 [10] Arjen K. Lenstra, and Adi Shamir, “Analysis and optimization of the TWINKLE factoring device”, Proc. Euro-crypt 2002, LNCS 1807 35-52, Springer-Verlag, 2000[11] H. J. Kim, and W. H. Mangione-Smith, “Factoring Large Numbers with Programmable Hardware (Presentation)”, UCLA Electrical Engineering Dept. http://klabs.org/richcontent/MAPLDCon99/Presentations/D5A_Kim_S.PDF [12] Adi Shamir, and Eran Tromer, “Factoring Large Numbers with the TWIRL Device”, CRYPTO 2003, LNCS 2729, pp. 1-26, 2003 [13] Will Geiselmann, and Rainer Steinwandt, “A Dedicated Sieving Hardware”, PKC 2003, LNCS, 2567, pp. 254-266, 2003 [14] Will Geiselmann, and Rainer Steinwandt, “Yet Another Sieving Device (extended version)”, 2003 [15] Matthew E. Briggs, “An Introduction to the General
View Full Document
Unlocking...