Implementation of Elliptic Curve Method (ECM) of Factoring on Reconfigurable Computing Machine (SRC)IntroductionContentsIntroduction (cont.)Introduction (cont.)Elliptic Curve MethodElliptic Curve Method (cont.)Elliptic Curve Method (cont.)ECM Architecture (operation table)ECM Architecture (Global View)Montgomery MultiplicationMontgomery Multiplication (Cont.)Montgomery Multiplication (Cont.)ECM Multiplier Unit (Top View)ECM Adder/Subtractor UnitFPGA ResultsFPGA Results (cont.)FPGA Results (cont.)ASIC ResultsReconfigurable Computing MachinesSystem ModelProgramming ModelsSRC Programming ModelECM Top View ModificationSRC Results (2 units)SRC Results (8 units)SRC Results (execution time)BenefitsFuture workQuestionsImplementation of ECM on SRC 1Implementation of Elliptic Curve Method (ECM) of Factoring on Reconfigurable Computing Machine (SRC)ECE645 – Dr. Kris GajHoang Le Mohammed KhaleeluddinRamakrishna BachimanchiImplementation of ECM on SRC2IntroductionWhy factor numbers? Security of RSA relies on difficulty to factor large compositesn = p.q, known n, what is p and q?(in practice: n ~ 1024 bit) In cryptanalysis:"Find efficient method for factoring (large) integers."Implementation of ECM on SRC3Contents Introduction ECM architecture ECM on FPGA ECM on ASIC ECM on SRC Future workImplementation of ECM on SRC4Introduction (cont.)Different algorithms for different purposes Best known method for factoring large integers: GNFS In GNFS smoothness test of “medium size” integers is required Methods suited for factoring numbers of 100-200 bit, e.g., MPQS ECM (small factors) Trial division (very, very small factors)Implementation of ECM on SRC5Introduction (cont.)Why ECM? Factor integers with relatively small factors (up to 200 bit) Almost ideal for hardware implementation: Allows for low I/O Requires little memory Easy to parallelizeImplementation of ECM on SRC6Elliptic Curve Method Algorithm proposed by [H.W. Lenstra 1985] Phase I Computer Q=k.P where  Scalar Multiplication Algorithm11 and logpepB p pkpeB≤⎡⎤==⎢⎥∏12 1012121122211212(, ,...,,); ( , )fo r ( 1 d o w n to 0 ) { if ( 1) ; 2 ; e lse 2 ; ; }LLikk kkPPCCiLkPPPPPPPPPPϑ−−===−==+===+Implementation of ECM on SRC7Elliptic Curve Method (cont.) Phase II Pre-compute a small table T of multiple k.Q Represent p in the form of p = m*D + k where  Fact: Compute for all primes and compute the final gcd of N12Compute and check if gcd( , ) 1iii pQpQ B p B z N⋅∀≤≤ >2[1, ] and 2DkDB∈≈gcd( , ) 1 iff gcd( , ) 1pQ mDQ kQ kQ mDQzN xz xz N>−>()mDQkQ kQmDQxz xz−∏Implementation of ECM on SRC8Elliptic Curve Method (cont.)Elliptic curves and point arithmetic: Use curves in Montgomery form: Point Addition: Point Duplication:23 2 2By z x Ax z xz=+ +22[( )( ) ( )( )][( )( ) ( )( )]PQ PQ P P Q Q P P Q QPQ PQ P P Q Q P P Q Qxzxzxzxzxzzxxzxzxzxz+−−−=−+++−=−+−+−22222224()()()()4[( )4(2)/4]pP P P P PPPPPPPPPPP PPxz x z x zxxzxzzxzxz xzA=+ −−=+ −=−++Implementation of ECM on SRC9ECM Architecture (operation table)ADD SUB MUL-I MUL-IIa1=xP+ zPs1=xP− zPNOP NOPa2=xQ+ zQs2=xQ− zQm1= (xP− zP)2m2=(xP+ zP)2NOP s3=m2− m1m3=s1 * a2m4= a1 * s2a3= m3+ m4s4=m3− m4m5= m2 * m1m6= s3 * c1a4= m1+ m6NOP m7= a32m8= s42NOP NOP m9= c2 * m8m10= s3 * a4NOP NOP m9= c2 * m8m10= m7 * c3NOP NOP NOP m11= s3 * a4 Point Addition (also used in phase I and Phase II depending on the row) Phase II Phase I Both phase I & Phase IIImplementation of ECM on SRC10ECM Architecture (Global View) One unit for 1 curve One control unit for all T curves 2 multipliers, 1 adder/subtractor, 1 local Mem per unitUNIT 1A/SM1M2LOCALMEMUNIT TA/SM1M2LOCALMEMCONTROLUNITGLOBALMEMINSTRUCTION MEMImplementation of ECM on SRC11Montgomery Multiplication An efficient technique for multiplying two integers modulo M. Replacing the modulus M by another divisor R for which the division step may be faster  Iterative process of additions and shifts without involving any division by M (if R is a power of 2) Conversions to Montgomery domain is required for using Montgomery Multiplication.Implementation of ECM on SRC12Montgomery Multiplication (Cont.) The algorithm in radix-200[0] 0; 0 -1 ( [ ] * ) mod 2; (1) [ 1] ( [ ] * * ) 2; (2) ; [];iiiiSfor i to n doqSi ABSi Si A B q M divend forreturn S n===++= + +Implementation of ECM on SRC13Montgomery Multiplication (Cont.) The critical delay of the algorithm above occurs in Reduce propagation delay CPA vs. CSA[ 1] ( [ ] * * ) 2iiSi Si A B q m div+= + +FAFAFAXn-1 Yn-1 Zn-1Xn-2 Yn-2 Zn-2XoYo ZoCn-1 Sn-1 Cn-2 Sn-2 Co SoSUMX Y ZCSFAFAFAXn-1 Yn-1 Xn-2 Yn-2XoYoCout Sn-1 Sn-2 SoSUMX Y ZSCinCoutImplementation of ECM on SRC14ECM Multiplier Unit (Top View)MULTIPLIERA_MBwriteA_M_ChoicestartCreadclkreset32 3232done_mulS1S2A (Shift_Reg)BCSR42ws>>1>>1S1in S2inABzeros zerosMmmBBS1out S2out BoutcarrysumS1inS2inS2out(0)S1out(0)Ai qiA1 A2 B CSUM CARRYEs Es loadAEbreg_rst reg_rst resetresetqiMMoutEbresetAiA(0)ww w wwwws wswwwwS1out(ws-1 downto 0)S2out(ws-1 downto 0)data_outws+wsreadBout(0)Airead readwswwws00([] * ) mod 2iiqSi AB=+VUWYCSACSASCCSR42wwwww+1 w+1w+2 w+2[ 1] ( [ ] * * ) 2iiSi Si A B q M div+= + +Implementation of ECM on SRC15ECM Adder/Subtractor Unit+C1C2LUT32X32MEM<>addr1 addr2WELOP1 OP2A_M_ChoiceA_M BsubsignZreadCinCoutsum1 sum2EC1EC2A_MADDER32 bti reg A32 bti reg BEBEAM2M<<1ADDER/SUBTRACTORA_MBwriteA_M_Choiceadd_subC readclkreset32 3232Implementation of ECM on SRC16FPGA Results Time & Freq comparison among different FPGAs. Time & Frequency27.1333.8864.412510054020406080100120140Virtex II XC2V6000-6 Spartan 3 XC3S5000-5 Virtex2000E-6Execution TimeMax Frequency for one unitImplementation of ECM on SRC17FPGA Results (cont.) Resource utilization for different FPGAs. Max No: of ECM units141070246810121416Virtex II XC2V6000-6 Spartan 3 XC3S5000-5 Virtex2000E-6Max No: of ECM unitsResources for one ECM unit9%10%16%0%2%4%6%8%10%12%14%16%18%Virtex II XC2V6000-6 Spartan 3 XC3S5000-5 Virtex2000E-6Resources for one ECM unitImplementation of ECM on SRC18FPGA Results (cont.) Comparison with the Proof-of-Concept Design by Pelzl, Šimka and et al. (on virtex2000E-6)Timing