INTRODUCTIONPreliminariesThe sieving part of the NFSOverlook of the proposalimplementationHardware layoutFinding the route to a target nodeStoring the factor bases in the meshFinding the first a_value for each node at the start of sievThe construct and function of processing nodeTesting Result On Reconfigurable PlatformIntroduction to PlatformMemory parameter adjustCoding and simulation resultConclusionFurther WorkGeorge Mason University ECE646 Term Project Fall, 2004_ 1Implementation of Sieving Step of NFS On Reconfigurable Platform Miaoqing Huang Abstract — Factorization of large numbers has been a constant source of interest in cryptanalysis as it is the basis of security for RSA cryptosystem. Number Field Sieving (NFS) algorithm is the most effective solution to factor a large composite number, whose length exceeds 110 bits. The second step of NFS, sieving step, is the most time-consuming step in NFS. W. Geiselmann and Rainer Steinwandt have proposed to use the specially designed ASIC to implement the sieving step. The author explores the feasibility to implement the sieving step on reconfigurable platform following the idea from the paper of Geiselmann and Steinwandt. Detailed description and parameters specification are talked about to realize the proposal, and the testing result from SRC reconfigurable computer is given. Index Terms — Factorization, Mesh Routing, Number Field Sieve, RSA, SRC I. INTRODUCTION actoring 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 Number Field Sieve (NFS) introduced by Pollard J M in 1988, is the asymptotically fastest known algorithm for the factorization of large numbers (110 digits or more). This method has recently been very effectively used to factorize certain RSA numbers, the latest being the RSA-576 number with 576 bits (174 digits) in it. The NFS algorithm consists of the following steps: 1. Polynomial Selection 2. Sieving, i.e. Relation Collection Step 3. Matrix Step 4. Square Root step The most time-consuming process of the NFS algorithm is Sieving Step. Initiated by Bernstein’s paper, in the last few years, several proposals to speed up the relation collection step, i.e. sieving step, of the number field sieve by means of specialized hardware have been published. Based on the analysis from several researchers, one can “conclude that from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve.” Thus, it is no surprise to see several attempts have been made to apply dedicated hardware to accelerate the relation collection step. Currently, two devices, TWIRL by Shamir and Tromer, and one Mesh Routing Circuit by Geiselmann and Steinwandt, are two good candidates to implement practically. Compared to TWIRL, the mesh routing design is much easier, because of its regular basic layout and the simplicity of inter-chip communication. Both proposals talked about above are based on ASIC technology. The authors of the two solutions provide the theoretical analysis for their plans, yet neither has been realized actually because of its prohibitive cost. FPGA, as a low-cost substitute of ASIC, is a good option to implement such a proposal before we go to the ASIC design and manufacture step. And with the advancement of reconfigurable platform, the performance of such system is comparable to the special design machine, yet the cost will be more acceptable. In this paper, we will try to explain how to adopt the idea from the mesh routing design and give the first-round of testing result on the reconfigurable platform – SRC Reconfigurable Computer. II. PRELIMINARIES A. The sieving part of the NFS A standard reference for an instruction to the number field sieve is given in [9], and the detailed description is beyond our scope. Here we only recall those aspects of the sieving step which are related for describing the mesh routing algorithm. In the first step of the NFS, two univariate polynomials, ][)(),(21xxfxfΖ∈are determined that share a common root m modulo n: )(mod0)()(21nmfmf ≡≡ FGeorge Mason University ECE646 Term Project Fall, 2004_ 2Typically, f1(x) is of degree d≥5 and f2(x) is monic and linear (i.e. f2(x) = x-m) such as the examples below. f1(x) = a5x5 + a4x4 + a3x3 + a2x2 + a1x + x0f2(x) = x - m From these two polynomials, the bivariate and homogeneous polynomials, ],[),(),,(21yxyxFyxF Ζ∈are derived via )./(),(),/(),(2211yxfyyxFyxfyyxFd⋅=⋅= Now everything related to f1(x) and F1(x, y) is said to belong to the algebraic side, and everything related to f2(x) and F2(x, y) is referred to as the rational side. In particular, for given smoothness bounds, B1, B2 ∈ N0, the sets (i = 1, 2) 2},,),(mod0)(:),{( NproBpprimepprfrpPiii⊆<≤<∈≡=are referred to as algebraic and rational factor base, respectively. For a 768-bit number, we can assume B1= 109 and B2=108. Throughout the relation collection step, pairs of co-prime integers (a, b) are to be found, such that the values F1(a, b) and F2(a, b) are smooth. This means that both F1(a, b) and F2(a, b) factor over the primes < B1 and < B2 respectively. The actual computation of (a, b)-pairs where both F1(a, b) and F2(a, b) are smooth can be performed by sieving over a rectangular region -A≤a<A, 0<b≤B. To organize this sieving, different techniques are available; here we focus on so-called line sieving, which is outlined in Figure 1. For the line sieving depicted in the above picture, we can find that actually, we will test all the pairs (a, b) in the rectangular region to find the possible candidates which fit the requirement to be selected for the next step. If the dimension of rectangular region is very huge, using traditional sequential computer will be infeasible to get the result in the limited time. In Figure 1, we start from the smallest value of b, and then increment the b one by one. For each value of b, we will check the whole range of a, from –A to A. If we adopt sequential method, for an a_value in the bound, we need to check whether a=br+kp, as long as a locates in [-A, A]. When A reaches 1013 and B reaches 109, it is infeasible to finish the whole process in a short time. Parallel computing is the only approach to
View Full Document
Unlocking...