Реализация логическими схемами операций умножения и инвертирования в конечных полях характеристики два тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1 Введение

2 Известные методы умножения в конечных полях характеристики два

3 Известные методы инвертирования в конечных полях характеристики два

4 Общие методы.

4.1 Сведение инвертирования в поле размерности п = П1П2 к инвертированию в поле размерности п2.

4.2 Сведение инвертирования в поле размерности п = пхпгпз к инвертированию в поле размерности п3.

4.3 Расширение второй степени

4.4 Расширение третьей степени.

4.5 Расширение четвертой степени.

4.6 Расширение пятой степени.

4.7 Расширение шестой степени.

5 Примеры

5.1 СР{22).

5.1.1 Оптимальный нормальный базис 2-го типа, х2 + х +

5.2 ОР(23).

5.2.1 Оптимальный нормальный базис 3-го типа, ж3 + х2 +

5.3 = б^(223).

5.3.1 Оптимальный нормальный базис 3-го типа, хл + х2 +

5.4 210) = 225).

5.4.1 Оптимальный нормальный базис 2-го типа, х5+ж 4 + х2 + х + 1.

5.5 = <З.Р(2з2).

5.5.1 Оптимальный нормальный базис 2-го типа, х2 + х +

5.6 С^(212) = С^(234).

5.6.1 Оптимальный нормальный базис 1-го типа, хА+хл + х2 + х + 1.

5.7 С7?(215) = 23").

5.7.1 Оптимальный нормальный базис 2-го типа, т/'+хА-\х2 + х + 1 5.

5.8 С/?(230) = С^(2235) и (?^(230) = С?^(2з25)

5.8.1 Оптимальный нормальный базис 2-го типа, х5 + х4 + х2 + х + 1 з.

5.9 С^(230) = С^(2253)

5.9.1 Оптимальный нормальный базис 3-го типа, ха + х2 +

5.10 СР(230) = СР(2352)

5.10.1 Оптимальный нормальный базис 2-го типа, х2 + х +

5.11 вЬ\ 24).

5.11.1 Оптимальный нормальный базис 1-го типа, х4+ж3 + ж2 + ж + 1.

5.11.2 Стандартный базис, ж4 + х + 1.

5.12 212) = <2^(243).

5.12.1 Оптимальный нормальный базис 3-го типа, ж3 + ж2 +

5.13 <^(220) = С^(245).

5.13.1 Оптимальный нормальный базис 2-го типа, х5 +хл + х2 + ж + 1.

5.14 С.Р(25).

5.14.1 Оптимальный нормальный базис 2-го типа, ж5+ж4 + х2 + х + 1.

5.14.2 Стандартный базис, х5 + х2 + 1.

5.15 210) = С^(252).

5.15.1 Оптимальный нормальный базис 2-го типа, х2 + х +

5.16 ОР(215) = 253).

5.16.1 Оптимальный нормальный базис 3-го типа, ж3 + х2 +

5.17 ОГ(220) = 25').

5.17.1 Оптимальный нормальный базис 1-го типа, ж4+ж3 + ж2 + ж + 1.

5.18 С^(26).

5.18.1 Оптимальный нормальный базис 2-го типа, ж6+ж5 + ж4 + ж + 1.

5.18.2 Стандартный базис, ж6 + ж3 + 1.

5.19 СР(230) = вР{265).

5.19.1 Оптимальный нормальный базис 2-го типа, ж5+х4 + х2 + х + 1.

Конечные поля возникли в работах Гаусса [1] и Галуа [2], которые имели предшественниками Ферма, Эйлера, Лагранжа и Лежандра. Современное изложение их теории появилось в работах Мура [3] и Диксона [4]. В учебниках алгебры, например в [5], [6], конечным полям уделяется мало внимания, за недавним исключением [7], но зато им посвящены специальные книги, например [8], [9], [10], [11], и в каждом солидной книге по теории кодирования есть глава (или главы), посвященные конечным полям.

В диссертации изучается сложность реализации арифметических операций в конечных полях характеристики два. Так как операции сложения и совпадающая с пей операция вычитания очень просты, то заниматься приходится только умножением и делением, а точнее инвертированием ненулевых элементов, так как деление сводится к инвертированию и умножению. Хотя полученные результаты можно применять и для программной имплементации операций в конечных полях, целью работы было исследование реализации этих операций логическими схемами, точнее схемами из произвольных функциональных логических элементов с двумя входами (схемами в базисе из всех двуместных булевых функций). Выбор этого базиса объясняется как его удобством в теоретических рассмотрениях, так и тем, что он содержится практически во всех библиотеках логических элементов, используемых в практическом синтезе VLSI — больших и сверхбольших интегральных схем.

Общая теория сложности схем для булевых функций была развита работах К.Э. Шеннона [12] и О.Б.Лупанова (например, [13]).

При построении логических схем в первую очередь было стремление в первую очередь минимизировать их глубину, т.е. максимальное число элементов в лщбой цепи, соединяющей входы схемы с ее выходами. В практическом синтезе VLSI стремятся минимизировать задержку схемы (время сс срабатывания после подачи на вход последнего сигнала). Задержка схема равна задержке ее критического пути (пути с максимальной задержкой), которая складывается из внутренних задержек его элементов и задержек соединяющих их проводников. Реально элемент не имеет единой задержки, задержка определяется отдельно для каждой пары входной пин-выходной пин, причем она зависит довольно сложным образом от логических значений входа и выхода в рассматриваемый момент, от их капаситетов, от капаситетов связанных с ними проводников и т.д. Учитывать все это в теоретической работе представляется нереальным и неинтересным. Поэтому минимизацию реальной задержки естественно заменить на минимизацию глубины, которая в определенном смысле пропорциональна ей.

Во вторую очередь (после минимизации глубины) было стремление уменьшить сложность схемы, т.е. число составляющих ее элементов. В реальном синтезе сложности соответствует площадь, занимаемая схемой, которая складывается из площадей, занимаемых ее элементами (а они у разных элементов разные, иногда даже если элементы логически одинаковые), и площади, занимаемой проводниками (которая иногда превосходит площадь занимаемую элементами, хотя проводники проводят по специальным слоям схемы, не содержащим элементов). В данной работе будет рассматриваться только сложность схем, но минимизация сложности главной целыо не является, так как практически более важно увеличить быстродействие схемы, а сложность важна только лишь когда схема с трудом помещается на кристалле.

Схемы для арифметических операций в конечных полях широко используются в кодировании (например, [14], [15], [16], [17]), криптографии (например, [18], [19], [20], [21], [10], [23], [24]), цифровой передаче сигналов (например, [25], [26] ) и др. областях.

В частности, такие схемы используются в аппаратной реализации как кодирующих, так и декодирующих устройств для линейных кодов, например, кодов ВСН и Рида-Соломона (например, [27], [28]), основанных на использовании алгоритма . Берлекемпа-Месси (например, [14], [29], [15], [16], [17]). В последнее время коды ВСН и Рида-Соломона (а потому и используемые в них схемы) нашли применение в так называемых турбо-кодах, используемых в телевизионных приемниках со спутниковыми антеннами (например, [30]).

Арифметические схемы для конечных полей используются в криптографии с секретным ключом при построении блочных шифров (например, схемы для операций в поле GF(28) применяются в новом американском стандарте AES, разработанном бельгийскими криптографами и пришедшем па смену DES [31], [32]), и в построении генераторов псевдослучайных последовательностей (см., например, [33]).

В указанных применениях чаще всего используются поля характеристики два, как наиболее удобные для схемной реализации. Далее рассматриваются только такие поля. В отмеченных применениях используются поля сравнительно малой размерности (п < 16 в кодировании и п < 32 при построении псевдослучайных генераторов), что дало основание Э.Р.Верлекемпу написать в [14] что поля большой размерности представляют только академический интерес.

Однако с развитием криптографии с открытым ключом поля большой размерности нашли применение во многих криптографических протоколах, основанных на предположении о трудности задачи дискретного логарифмирования, например, в ключевом обмене Диффи-Хеллмапа [34]. После появления работы Купершмита [35] и современного совершенствования компьютерной и программистской техники стало ясно, что для повышения надежности таких протоколов необходимо использовать поля размерности не меньше 1000.

Но благодаря возникновению в работах Коблида и Миллера и последующему развитию эллиптической криптографии (см., например, [22], [30], [38], [37], [39], [40], [41], [42]) появилась возможность использовать поля размерности порядка 200, что облегчило проблему производства схем для арифметики в таких полях.

1. Gauss K.F., Disquisitiones Arithmeticae, Fleischner, Leipzig (1801). Русский перевод: Гаусс К.Ф. Труды по теории чисел - М., изд. АН СССР (1959).

2. Galois Е., Sur la theorie des nombres, Bull. Sci. Math, dc M.Ferussac, 13 (1830), 428-435. Русский перевод: Галуа Э. Математические работы.-Москва-Ижевск (2002).

3. Моогс Е.Н.,Л double-infinite system of simple groups Bull. New York Math.Soc. 3 (1983), 73-78.

4. Dickson L.E., Proof of the existence of the Galois field of order pr, Bull.Amer.Math.Soc., 6 (1900) 20^-204.

5. Лепг С., Алгебра, M., Мир (1968).6. ван дер Варден Алгебра, М., Мир (1976).

6. Глухов М.М., Елизаров В.П., Нечаев А.А., Алгебра, т.т.1-2, М., Гелиос АРВ (2003).

7. Lidl R., Niederreiter Н., Finite fields, Addison-Wesley publishing company (1983).

8. McElice R.J. Finite Fields for Computer Scientists and Endineers, Kluwer Academic Publishers, 1987.

9. Menezes A., Application of finite fields, Cluwer Academic Publishers (1993).

10. Jungnickel D., Finite fields. Structure and arithmetic, Wissenschaftsvcrlag, Mannheim, Leipzig, Wien, Zurich (1993).

11. Шениоп К.Э., Избранные работы no теории информации и кибернетике, ИЛ, Москва (1963).

12. Лупапов О.Б., Асимптотические оценки сложности управляющих систем, изд. Московского университета (1984).

13. Berlekamp E.R., Algebraic coding theory, McGraw Hill (1968). Русский перевод: Берлекемп Э.Р., Алгебраическая теория кодирования.- М., Мир (1971).

14. Peterson W.W., Weldon E.J. Error-correcting codes, The Mit Press, Cambridge, Massachusets (1972). Русский перевод: Питерсон У., Уэл-дон Э., Коды, исправляющие ошибки.- М., Мир (1976).

15. MacWilliams F.J., Sloane N.J.A., The theory error-correcting codes, North-Holland, Amsterdam (1977). Русский перевод: Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А., Теория кодов, исправляющих ошибки.-М.,Связь, (1979).

16. Blahut R.E., Theory and practice of error control codes, Addison-Wesley publishing company (1984). Русский перевод: Блейхут Р.Э., Теория и практика кодов, контролирующих ошибки.- М., Мир (1986).

17. Salomaa A., Public-Key Cryptography, Springer-Verlag, (1990). Русский перевод: Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.

18. Нечаев В.И. Основы защиты информации, М. Высшая школа, (1999).

19. Koblitz N., A course in number theory and cryptography, SpringerVerlag (1994). Русский перевод: Коблиц II., Курс теории чисел и криптографии.- М., ТВП (2001).

20. Schneier В., Applied cryptography, John Wiley &Sons, Inc. (1996). Русский перевод: Шнайер В., Прикладная криптография.- М., Триумф (2002).

21. Menezes A., Elliptic curve public key cryptosystems, Cluwer Academic Publishers (1993).

22. Menezes A., van Oorshot P.,Vansotone S. Handbook of Applied cryptography, CRC Press (1997).

23. Ященко B.B. ред. Введение в криптографию, изд. МЦНМО (1998).

24. Blahut R.E., Fast algorithms for digital signal processing, Addison-Wesley publishing company (1985). Русский перевод: Блейхут Р.Э., Быстрые алгоритмы цифровой обработки сигналов М., Мир (1989).

25. McCLcllan J.H., Rader С.М., Number theory in digital signal processing, Prentice-Hall (1979). Русский перевод: Маккллеллан Дж.Х., Редер Ч.М., Применение теории чисел в цифровой обработки сигналов.-М., Радио и Связь (1983).

26. Berlckamp E.R., Bit-Serial Reed-Solomon encoders, IEEE Trans. Inf. Theory IT-28, 6 (1982), 869-74.

27. Mestcr M., Reed-Solomon encoder-decoder chip set, BTS Gmbh, Darmstadt, Germany (Nov.1991).

28. Massey J.L., Feedback Shift Register Synthesis and BCH decoding, IEEE Trans. Inform. Theory, IT15 (1969), 122-128.

29. Berrou C. and Clavieux A., Near optimum error correcting coding and decoding: turbo codes , IEEE Trans.Comm., (Oct.1996), 1261-1271.

30. Daemen J., Rijmen V., AES Proposal: Rijndael http: / / csrc.nist.gov/encryption/aes

31. Зепзии O.C., Иванов M.A., Стандарт криптографической зашиты AES. Конечные поля, М., Кудиц-Образ, 2002.

32. Иванов М.А., Чугунков И.В., Теория, применение и оценка качества генераторов псевдослучайных последовательностей, М., Кудиц-Образ, 2003.

33. Diffie W., Hellman М., New directions in cryptography, IEEE Trans. Inform. Theory, IT-22, (1976).

34. Coppersmith D., Fast evaluation of logarithms in fields of characteristic two, IEEE Trans.Inform. Theory,YT3Q, 4,(1984), 587-594.

35. Rosing M., Implementing elliptic curve cryptography, Manning, (1998).

36. Miller V., Uses elliptic curves in cryptography , CRYPTO-85, (1986), 417-426.

37. Koblitz N., Elliptic curve cryptosystems , Mathematics of computation, 48 (1987), 203-209.

38. Agnew G.B., Beth Т., Mullin R.C., Vanstone S.A. Arithmetic Operations in GF(2m), Journal of Cryptology, 6, (1993).

39. Schroeppel R., Orman R., O'Malley S., Spatscheck O., Fast key exchange with elliptic curve systems , CRYPTO-95, (1995), 43-56.

40. Bailey D., Paar C., Optimal extension fields for fast arithmetic in public-key algoritms , CRYPTO-98, (1998), 472-485.

41. Болотов A.A., Гашков С.Б., Фролов А.Б., Часовских A.A., Алгоритмические основы эллиптической криптографии, изд. МЭИ (2000).43. von zur Gathen J., Gerhard J., Modern Computer Algebra, Cambridge University Press (1999).

42. Болотов A.A., Гашков С.Б., Хохлов P.A. О слоо/сности алгоритмов построения неприводимых трехчленов и пятичленов над конечными полями, Интеллектуальные системы 4, 3-4, Москва (1999), 235262.

43. Гашков С.Б., Хохлов P.A., О глубине логических схем для деления в полях GF(2n) Алгебра и теория чисел: Современные проблелш и прилоэ/сения, Москва (2003), 73-75

44. Гашков С.Б., Хохлов P.A., О глубине логических схем для операций в полях GF(2"), Чебышевский сборник, т.4, выпуск 4(8), Москва (2003), 59-71.

45. Хохлов Р.А Об одном методе построения схем с малой глубиной для деления в полях GF(2"). Алгебра и теория чисел: Современные проблемы и прилоэ/сения, Москва (2004), 125-126.

46. Mastrovito E.D., VLSI architectures for computation in Galois fields, Ph.D. thesis, Linkoping University, Dept. Electr.Eng., Sweden (1991).

47. Карацуба A.A., Офман Ю.П., Умноэюение многозначных чисел на автоматах, ДАН СССР, 145 2, (1962).

48. Гашков С.Б., Чубариков В.Н., Арифметика. Алгоритмы. Слоэю-ностъ вычислений., М.Высшая школа, (2000).

49. Schocnhagc A., Schnelle Multiplication von Polynomen ueber Koerpern der Charakteristik 2 Acta Informática, 7 (1977), 395-398

50. Paar C., Effective VLSI architectures for bit paralel computation in Galois fields, Ph.D. thesis, Universität GH Essen, Germany, 1994.

51. Afanasyev V.B., Complexity of VLSI implementation of finite field arithmetic, in II Intern. Workshop on algebraic and combinatorial coding theory, Leningrad, USSR (Sep. 1990), 6-7.

52. Paar С., Fleischmann P., Roelse P., Effective multiplier architectures for Galois fields GF{24n, IEEE Trans. Сотр., bf 47 2 (1998), 162-70.

53. Hasan M.A., Wang M., Bhargava V.K., Division and bit-serial multiplication over GF(qn), IEEE Trans. Сотр., bf 41 8 (1992), 972980.

54. Kovac M., Rangathan N., Varanasi M., A VLSI systolic array implementation of Galois field GF(2") based on multiplication division algorithm , IEEE Trans. VLSI, bf 1 1 (1993).

55. Massey J.L., Omura J.K., Apparatus for finite fields computation, US patent 4587627 (1986).

56. Ficli F.E., Tomba M., The parallel complexity of exponentiating polynomials over finite fields , J. Assoc. Comput. Mach., bf 35 (1988), 651-667.

57. Mullin R.C., Onyszchuk I.M., Vanstone S.A., Wilson R.M Optimal -normal bases in GF(pn), Discrete Applied Mathematics, 22 (1988/89), 149-161.

58. Gao X., Lenstra H.W., Optimal normal bases, Design, Codes and Cryptography 2 (1992),315-323.

59. Ash D., Blake I, Vanstone S. Low complexity normal bases, Discrete Applied Mathematics, 25, (1988/89), 191-210

60. Seguin J.E.,Low complexity normal bases, Discrete Applied Mathematics, 28, (1990), 309-312.

61. Reyhani-Masoleh A., Hasan M.A., On effective normal basis multiplication, IndiaCRYPT, (2000).

62. Болотов А.А., Гашков С.Б., Быстрое умножение в нормальных базисах конечных полей, Дискретная математика,13 3, (2001), 3-31.

63. Коновалъцев И.В., Об одном алгоритме решения линейных уравнений в конечных полях. М., Наука, Проблемы кибернетики 19 (1967), 269-274.

64. Hsu I.S., Truong Т.К., Reed I.S., Glover N., A VLSI architecture for performing finite field arithmetic with reduced table lookup, Linear algebra and its applications, 98 (1988), 249-262.

65. Chin-Liang Wang, Jung-Lung Lin, A systolic architecture for computing inverses in finite field GF(2") , IEEE Trans. Сотр., bf 42 9 (1993),1141-46.

66. Olofsson M., VLSI aspects on inversion in finite fields, Ph.D. thesis, Linkoping University, Dept. Electr. Eng., Sweden (2002).

67. Morii M., Kasahara M. Efficient construction of gate circuit for computing multiplicative inverses in GF{2"), Trans, of the IEICE,E 72, 1 (1989), 37-42.

68. Paar C., Fan J.L., Efficient inversion in tower fields of characteristic two, ISIT, Ulm, Germany, (1997).

69. Litow B.E., Davida G.I., O(logn) time for finite field inversion, Lecture notes in computer sciences, 319 (1988), Springer-Verlag, 74-80.72. von zur Gathen J., Inversion in finite fields, J. Symbplic Comput., 9 (1990), 175-183.

70. Itoh Т., Tsujii S. A fast algorithm for computing multiplicative inverses in GF(2") using normal bases, Inform, and Сотр., 78 (1988), 171-177.

71. Кнут Д. Искусство программирования, т.2 изд. «Вильяме», (2000).