洪士灝臺灣大學:資訊工程學研究所林宗慶Lin, Zong-CingZong-CingLin2010-06-092018-07-052010-06-092018-07-052009U0001-2006200916220600http://ntur.lib.ntu.edu.tw//handle/246246/185400The Elliptic Curve Method (ECM) is the method of choice for nding medium-size prime factors. A good ECM implementation is useful for evaluating the strength of the RSA (Rivest, Shamir, Adleman) public-key cryptographic algorithm because it is a critical step in the Number Field Sieve algorithm that is employed as the stateof-the-art cryptanalysis technique against the RSA. In this thesis, we describe ourork to accelerate the ECM with the Cell multi-core processor. We discuss how the performance of cryptanalysis-related applications can bene t from the architecturaleatures of the Cell processor. Finally, we show that our implementation outperforms the previous records.mong previously published results, the ECM implementation with the best performance is achieved using an NVIDIA GTX 295 graphics card on an Intel X86-based platform, which can compute 401 curves per second for 280-bit integers in ECM Stage 1 with B1 = 8192. That implementation also achieves the best cost-performance ratio to date. In our results, the PowerXCell 8i processor, which is a recently revised variant in the Cell family, can handle 776 curves per second, which outperforms the previous record by 93% with much less power consumption, despite the fact that GPU''s (Graphics Processing Units) have greater raw capabilities measured in GFLOPS (Giga Floating-Point Operation per Second).e attribute the high performance and high power e ciency to several architectural features of the Cell processor, namely, the wider main arithmetic pipeline, an auxiliary pipeline for handling managerial tasks, fast direct memory access capability, and the larger fast on-die memory.Acknowledgements ibstract(Chinese) iibstract iiiist of Figures viiist of Tables ix Introduction 1.1 Number Field Sieve Algorithm 2.2 Elliptic Curve Method 5.3 STI Cell Broadband Engine 7.4 Thesis Organization 10 Related Works 12.1 The Latest Milestone in Big Integer Factorization 13.2 ECM implementations on Graphic Processing Units 13.3 Use Cell as SSL accelerator 14.4 Fast Elliptic Curve Cryptography on the Cell Processor 15 Implementation of Elliptic Curve Method on the Cell processor 16.1 Elliptic Curve Scalar Multiplication 18.2 Operations of Point Addition and Doubling 22.3 Modular Operations in ZN 24.4 Operations of Multi-Precision Integers 24.5 Pipeline Implementation of ECM Stage1 30 Performance Results and Comparison 33.1 Experimental Setup 33.2 Experimental Results 37.2.1 Throughput of Kernel Operations 37.2.2 Dynamic Access to Access Sliding Window Entries 43.2.3 Resulted Throughput on Each Cell-based Platforms 44.3 Performance Comparison 48 Conclusion and Future Work 51ibliography 541398919 bytesapplication/pdfen-US橢圓曲線法Cell處理器整數因數分解數域篩選法密碼分析ellitpic curve methodCell processorinteger factorizationnumber field sievecryptanalysisthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/185400/1/ntu-98-R96922004-1.pdf