مروری بر عملیات معکوس در میدان‌های متناهی دودویی و اول
محورهای موضوعی : مهندسی برق و کامپیوتر
رضا روح قلندری
1
(دانشگاه صنعتی شریف)
حاتمه مثنایی بورانی
2
(دانشگاه صنعتی شریف)
سیاوش بیات سرمدی
3
(دانشگاه صنعتي شریف)
کلید واژه: الگوریتم‌های معکوسمیدان‌های متناهیقضیه کوچک فِرماالگوریتم اقلیدسی تعمیم‌یافته,
چکیده مقاله :
رمزنگاری کلید عمومی یکی از روش‌های مرسوم رمزنگاری است که به دلیل عدم نیاز به تبادل کلید، در سال‌های اخیر بسیار مورد توجه قرار گرفته است. روش‌هایی مانند توان‌رسانی، جفت‌سازی، رمزنگاری خم بیضوی و همگونی در این دسته قرار می‌گیرند که تاکنون پژوهش‌های زیادی برای کاهش پیچیدگی زمانی و مساحت این روش‌ها صورت گرفته است. عملیات معکوس به عنوان یکی از اصلی‌ترین اعمال موجود در روش‌های رمزنگاری کلید عمومی است که بخش زیادی از پیچیدگی محاسباتی و زمانی را در این پردازنده‌های رمزنگاری به خود اختصاص می‌دهد. بنابراین برای افزایش کارایی و سرعت پردازنده‌های رمزنگاری کلید عمومی، بهبود سرعت و مساحت عملیات معکوس در میدان‌های متناهی بسیار ضروری به نظر می‌رسد. در این مقاله، روش‌های موجود برای انجام عملیات معکوس بر روی میدان‌های دودویی و اول مورد بررسی قرار گرفته است. در سامانه‌های رمزنگاری امروزی، میدان‌های دودویی به دلیل سازگاری با سخت‌افزار، بسیار پرکاربرد هستند. در ابتدای این نوشتار، روش‌های موجود برای انجام عملیات معکوس در میدان‌های دودویی بررسی، الگوریتم‌های موجود بیان و از نظر پیچیدگی زمانی و منابع مورد نیاز با هم مقایسه شده است. سپس بهترین پیاده‌سازی‌های موجود روی بستر FPGA و به صورت مدار مجتمع معرفی می‌گردد. هدف اصلی در این روش‌ها کاهش تعداد ضرب مورد نیاز برای انجام عملیات معکوس در میدان دودویی و افزایش امکان توازی برای پیاده‌سازی هرچه بهتر این روش‌ها است. میدان‌های اول به دلیل پیچیدگی ساختاری و محاسباتی بیشتر نسبت به میدان‌های دودویی، تنوع و گستردگی کمتری دارند ولی در سالیان اخیر به دلیل ظهور کاربردهای جدیدی در رمزنگاری نظیر روش همگونی، مورد توجه بیشتری قرار گرفته‌اند. محققان این حوزه در تلاش هستند تا ضمن از بین بردن وابستگی زمان اجرای روش‌های موجود به مقدار ورودی، پیچیدگی زمانی و مساحت الگوریتم‌های محاسبه معکوس را تا حد امکان کاهش دهند. ارائه ساختارهایی نظیر آرایه ضربانی در همین راستا صورت گرفته که این مقاله به بررسی این روش‌ها می‌پردازد و در انتها روش‌های انجام عملیات معکوس را در میدان‌های اول از نظر پیچیدگی زمانی و محاسباتی با هم مقایسه می‌کند.
Public key cryptography is one of the common cryptosystems mainly because it does not have key agreement issue. One important operation in these cryptosystems is inversion. Therefore, improving its performance gains significant attention. In this paper, inversion operation over binary and prime fields are surveyed considering time and area complexity. Moreover, the implementation results on FPGA and ASIC platforms are investigated and analyzed.
[1] E. Wenger and M. Hutter, "Exploring the design space of prime field vs. binary field ECC-hardware implementations," in Proc. Nordic Conf. on Secure IT Systems, pp. 256-271, Tallinn, Estonia, 26-28 Oct. 2011.
[2] J. P. Deschamps, J. L. Imana, and G. D. Sutter, Hardware Implementation of Finite-Field Arithmetic, New York: McGraw- Hill, 2009.
[3] Q. Liao, "The Gaussian normal basis and its trace basis over finite fields," Number Theory, vol. 132, no. 7, pp. 1507-1518, Jul. 2007.
[4] A. Brauer, "On addition chains," Bulletin of the American Mathematical Society, vol. 45, no. 10, pp. 736-739, 1939.
[5] D. E. Knuth, The Art of Computer Programming: Sorting and Searching: Volume 3, 1973.
[6] P. L. Montgomery, "Modular multiplication without trial division," Mathematics of Computation, vol. 44, no. 170, pp. 519-521, Dec. 1985.
[7] A. A. Gutub, A. F. Tenca, and C. K. Koc, "Scalable VLSI architecture for GF(p) montgomery modular inverse computation," in Proc. of IEEE Computer Society Annual Symp.on VLSI, pp. 53-58, Pittsburgh, PA, USA, 25-26 Apr. 2002.
[8] A. Daly, W. Marnane, T. Kerins, and E. Popovici, "Fast modular division for application in ECC on reconfigurable logic," Lecture Notes in Computer Science, pp. 786-795, Sept. 2003.
[9] J. Bucek and R. Lorencz, "Comparing subtraction-free and traditional AMI," in Proc. of 9th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, DDECS'06, pp. 95-97, Prague, Czech Republic, 18-21 Apr. 2006.
[10] R. P. Brent and H. T. Kung, "Systolic VLSI arrays for polynomial GCD computation," IEEE Trans. on Computers, vol. 33, no. 8, pp. 731-736, Aug. 1984.
[11] H. T. Kung, "Why systolic arrays?" Computer, vol. 15, pp. 37-46, Jan. 1982.
[12] J. Stein, "Computational problems associated with Racah Algebra," J. of Computational Physics, vol. 1, no. 3, pp. 397-405, Feb. 1967.
[13] C. H. Wu, C. M. Wu, M. D. Shieh, and Y. T. Hwang, "High-speed, low complexity systolic designs of novel iterative division algorithms in GF (2m)," IEEE Trans. on Computers, vol. 53, no. 3, pp. 375-380, Mar. 2004.
[14] H. Brunner, A. Curiger, and M. Hofstette, "On computing multiplicative inverses in GF (2m)," IEEE Trans. on Computers, vol. 42, no. 8, pp. 1010-1015, Aug. 1993.
[15] J. H. Guo and C. L. Wang, "Systolic array implementation of Euclid's algorithm for inversion and division in GF (2m)," IEEE Trans. on Computers, vol. 47, no. 10, pp. 1161-1167, May 1998.
[16] Z. Yan and D. B. Sarwate, "High-speed systolic architectures for finite field inversion," Integration: The VLSI J., vol. 38, no. 3, pp. 383-398, Jan. 2005.
[17] M. Mozaffari-Kermani, R. Azarderakhsh, C. Y. Lee, and S. Bayat-Sarmadi, "Reliable concurrent error detection architectures for extended euclidean-based division over GF (2m)," IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 22, no. 5, pp. 995-1003, May 2014.
[18] S. Kim, N. S. Chang, C. H. Kim, Y. H. Park, and J. Lim, "A fast inversion algorithm and low-complexity architecture over GF (2m)," In: Hao Y. et al. (eds) Computational Intelligence and Security, CIS'05, 8 pp., Lecture Notes in Computer Science, vol 3802. Springer, Berlin, Heidelberg ,2005.
[19] Z. Yan, D. V. Sarwate, and Z. Liu, "Hardware-efficient systolic architectures for inversions in GF (2m)," IEE Proceedings-Computers and Digital Techniques., vol. 145, no. 4, pp. 272-278, Jul. 1998.
[20] Z. Yan, "Digit-serial systolic architectures for inversions over GF (2m)," in Proc. IEEE Workshop on Signal Processing Systems Design and Implementation, pp. 77-82, Banff, Canada, 2-4 Oct. 2006.
[21] A. K. Daneshbeh and M. A. Hasan, "A class of unidirectional bitserial systolic architectures for multiplicative inversion and division over GF (2m)," IEEE Trans. Computer, vol. 54, no. 3, pp. 370-380, Mar. 2005.
[22] J. H. Guo and C. L. Wang, "Bit-serial systolic array implementation of Euclid's algorithm for inversion and division in GF (2m)," in Proc. of Technical Papers. Int. Symp. on VLSI Technology, Systems, and Applications, pp. 113-117, Taipei, Taiwan, 3-5 Jun. 1997.
[23] J. Fan, L. Batina, and I. Verbauwhede, "Design and design methods for unified multiplier and inverter and its application for HECC," Integration, VLSI J., vol. 44, no. 4, pp. 280-289, Sept. 2011.
[24] K. Kobayashi and N. Takagi, "Fast hardware algorithm for division in G (2m) based on the extended euclid's algorithm with parallelization of modular reductions," IEEE Trans. on Circuits and Systems II: Express Briefs, vol. 56, no. 8, pp. 644-648, Aug. 2009.
[25] A. Ibrahim, T. F. Al-Somani, and F. Gebali, "New systolic array architecture for finite field inversion," Canadian J. of Electrical and Computer Engineering, vol. 40, no. 1, pp. 23-30, Winter 2017.
[26] C. C. Wang, et al., "VLSI architectures for computers multiplications and inverses in GF (2m)," IEEE Trans. on Computers, vol. 34, no. 8, pp. 709-717, Aug. 1985.
[27] T. Itoh and S. Tsujii, "A fast algorithm for computing multiplicative inverses in GF (2m) using normal bases," Information and Computation, vol. 78, no. 3, pp. 171-177, Sept. 1988.
[28] N. Takagi, "A fast algorithm for multiplicative inversion in GF (2m) using normal basis," IEEE Trans. on Computers, vol. 42, no. 9, pp. 1141-1146, May 1993.
[29] V. Dimitrov and K. Jarvinen, "Another look at inversions over binary fields," in Proc. IEEE Symp. on Computer Arithmetic, ARITH’13, pp. 211-218, Austin, TX, USA, 7-10 Apr. 2013.
[30] R. Azarderakhsh and A. Reyhani-Masoleh, "Low-complexity multiplier architectures for single and hybrid-double multiplications in Gaussian normal bases," IEEE Trans. on Computers, vol. 62, no. 4, pp. 744-757, Apr. 2013.
[31] R. Azarderakhsh, K. Jarvinen, and V. Dimitrov, "Fast inversion in GF (2m) with normal basis using hybrid-double multipliers," IEEE Trans. on Computers, vol. 63, no. 4, pp. 1041-1047, Apr. 2014.
[32] J. Hu, W. Guo, J. Wei, and R. C. Cheung, "Fast and generic inversion architectures over GF (2m) using modified Itoh-Tsujii algorithms," IEEE Trans. on Circuits and Systems II: Express Briefs, vol. 62, no. 4, pp. 367-371, Apr. 2015.
[33] K. Jarvinen, V. Dimitrov, and R. Azarderakhsh, "A generalization of addition chains and fast inversions in binary fields," IEEE Trans. on Computers, vol. 64, no. 9, pp. 2421-2432, Sept. 2015.
[34] M. Nocker, Data Structures for Parallel Exponentiation in Finite Fields, Ph.D Diss., 2001.
[35] B. Rashidi, "High-speed hardware implementation of Gaussian normal basis inversion algorithm over F2m," Microelectronics J., vol. 63, pp. 138-147, May 2017.
[36] J. Guajardo and C. Paar, "Itoh-Tsujii inversion in standard basis and its application in cryptography and codes," Designs, Codes and Cryptography, vol. 25, no. 2, pp. 207-216, Nov. 2002.
[37] F. Rodriguez-Henriquez, N. Cruz-Cortes, and N. A. Saqib, "A fast implementation of multiplicative inversion over GF (2m)," in Proc. Int. Conf. on Information Technology: Coding and Computers, ITCC’05, vol. 1, pp. 574-579, Covtat, Croatia, 20-23 Jun. 2005.
[38] F. Rodriguez-Henriquez, G. Morales-Luna, N. A. Saqib, and N. Cruz-Cortes, "Parallel Itoh-Tsujii multiplicative inversion algorithm for a special class of trinomials," Designs, Codes and Cryptography, vol. 45, no. 1, pp. 19-37, Jan. 2007.
[39] C. Rebeiro, S. S. Roy, S. S. Reddy, and D. Mukhopadhyay, "Revisiting the Itoh-Tsujii inversion algorithm for FPGA platforms," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 19, no. 8, pp. 1508-1512, Aug. 2011.
[40] V. R. Venkatasubramani, N. Murali, and S. Rajaram, "An improved quad Itoh-Tsujii algorithm for FPGAs," IEICE Electronics Express, vol. 10, no. 18, 10 pp., Article -20130612, Jan. 2013.
[41] S. S. Roy, C. Rebeiro, and D. Mukhopadhyay, "Theoretical modeling of the Itoh-Tsujii inversion algorithm for enhanced performance on k-LUT based FPGAs," in Proc.Design, Automation and Test in Europe Conf. and Exhibition, DATE’16, 6 pp., Grenoble, France, 14-18 Mar. 2011.
[42] S. S. Roy, C. Rebeiro, and D. Mukhopadhyay, "Generalized high speed Itoh-Tsujii multiplicative inversion architecture for FPGAs," Integration, The VLSI J., vol. 45, no. 3, pp. 307-315, Jun. 2012.
[43] L. Parrilla, A. Lloris, E. Castillo, and A. Garcia, "Minimum-clock-cycle Itoh-Tsujii algorithm hardware implementation for cryptography applications over GF (2m) fields," Electronics Letters, vol. 48, no. 18, pp. 1126-1128, Aug. 2012.
[44] L. Li and S. Li, "Fast inversion in GF (2m) with polynomial basis using optimal addition chains," in Proc. IEEE Int Symp. in Circuits and Systems, ISCAS’17, 4 pp., Baltimore, MD, USA, 28-31 May 2017.
[45] J. Maitin-Shepard, "Optimal software-implemented Itoh-Tsujii inversion for GF (2m)," Designs, Codes and Cryptography, vol. 82, no. 2, pp. 301-318, Aug. 2017.
[46] F. Rodriguez-Henriquez, N. A. Saqib, A. D. Perez, and C. K. Koc, Cryptographic Algorithms on Reconfigurable Hardware, Springer-Verlag US, 2007.
[47] J. Li, Z. Li, C. Xue, J. Zhang, W. Gao, and S. Cao, "A fast modular inversion FPGA implementation over GF (2m) using modified x2n unit," in Proc. IEEE Int. Symp. on Circuits and Systems, ISCAS'18, 5 pp., Florence, Italy, 27-30 2018.
[48] G. M. de Dormale and J. J. Quisquater, "High-speed hardware implementations of elliptic curve cryptography: a survey," J. of Systems Architecture, vol. 53, no. 2-3, pp. 72-84, Feb./Mar. 2007.
[49] B. Vallee, "Dynamics of the binary Euclidean algorithm: functional analysis and operators," Algorithmic, vol. 22, no. 4, pp. 660-685, Mar. 1998.
[50] A. Akhavi and B. Vallee, "Average bit-complexity of Euclidean algorithms," in Proc. Int. Colloquium on Automata, Languages, and Programming, pp. 373-387, Ceneva, Switzerland, 14-21 Jul. 2000.
[51] H. Mahdizadeh and M. Masoumi, "Novel architecture for efficient FPGA implementation of elliptic curve cryptographic processor over GF (2163)," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 21, no. 12, pp. 2330-2333, Dec. 2013.
[52] N. Takagi, "A VLSI algorithm for modular division based on the binary GCD algorithm," IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E81-A, no. 5, pp. 724-728, 1998.
[53] L. A. Tawalbeh, A. F. Tenca, S. Park, and C. K. Koc, "A dual-field modular division algorithm and architecture for application specific hardware," in Proc. IEEE the 38th Asilomar on Signals, Systems and Computers Conf., vol. 1, pp. 483-487, Nov. 2004.
[54] A. Mrabet, N. El-Mrabet, B. Bouallegue, S. Mesnager, and M. Machhout, "An efficient and scalable modular inversion/division for public key cryptosystems," in Proc. Int. Conf. on Engineering & MIS, ICEMIS’17, 6 pp., Astana, Kazakhstan, 6-8 Jun. 2017.
[55] E. Savas and C. K. Koc, "Montgomery inversion," J. of Cryptographic Engineering, vol. 8, no. 3, pp. 201-210, Apr. 2018.
[56] J. W. Bos, "Constant time modular inversion," J. of Cryptographic Engineering, vol. 4, no. 4, pp. 275-281, Aug.. 2014.
[57] D. J. Bernstein, "Curve25519: new Diffie-Hellman speed records," in Proc. Int. Workshop on Public Key Cryptography, pp. 207-228, New York, NY, USA, 5-7 Nov. 2006.