알고리즘 알고리즘

2005년 8월

교육학석사(전기․전자․통신교육전공)학위논문

합성체를 합성체를 합성체를

합성체를 이용한 이용한 이용한 이용한 유한체의 유한체의 유한체의 역원 유한체의 역원 역원 역원 계산 계산 계산 계산 알고리즘

알고리즘 알고리즘

알고리즘 구현 구현 구현 구현

조선대학교 교육대학원

전기․전자․통신교육전공

신 자 영

[UCI]I804:24011-200000234722

합성체를 합성체를 합성체를

합성체를 이용한 이용한 이용한 이용한 유한체의 유한체의 유한체의 역원 유한체의 역원 역원 역원 계산 계산 계산 계산 알고리즘

알고리즘 알고리즘

알고리즘 구현 구현 구현 구현

Implementation Implementation Implementation

Implementation of of of of Inverse Inverse Inverse Inverse Algorithm Algorithm Algorithm Algorithm in in in Finite in Finite Finite Finite Fields Fields Fields using Fields using using using Composite

Composite Composite

Composite Fields Fields Fields Fields

2005년 8월

조선대학교 교육대학원

전기․전자․통신교육전공

신 자 영

합성체를 합성체를 합성체를

합성체를 이용한 이용한 이용한 이용한 유한체의 유한체의 유한체의 역원 유한체의 역원 역원 역원 계산 계산 계산 계산 알고리즘

알고리즘 알고리즘

알고리즘 구현 구현 구현 구현

지도교수 이 강 현

이 논문을 교육학석사(전기․전자․통신 교육전공)학위 청구논문으로 제출합니다.

2005년 4월

조선대학교 교육대학원

전기․전자․통신교육전공

신 자 영

신자영의 교육학 석사학위 논문을 인준합니다.

심사위원장 조선대학교 교수 朴 種 伯 인 심사위원 조선대학교 교수 朴 暢 均 인 심사위원 조선대학교 교수 李 康 鉉 인

2005년 6월

조선대학교 교육대학원

ListofTable···ⅲ ListofFigures···ⅳ Abstract···ⅴ

···1

···3

2.1GeneralFieldTheory ···3

2.2FiniteFields···5

2.3PrimeFieldArithmetic···10

2.4ConstructingFiniteFields···12

···17

3.1Fermattheorem ···17

3.2ExtendedEuclidalgorithm···17

3.3CalculationoftheinverseusingamultiplieroftheGF(2⁸)finitefield··19

3.4CompositeFields···19

···21

4.1Processofcalculatingfinitefieldinverse···21

4.2Circuitdesignoftheproposedinversealgorithm···22

4.3Simulation ···23

4.4Measuringfunction ···25

···27

···29

References···30

Table1.Resultsofcircuitsynthesisandcomparisonoffunction···25

Fig.1.Representationof ∊



Fig.2.Circuitdesignforinversecalculationusingcompositefields···23

Fig.3.showsthevaluesofS andR blocks ···23

Fig.4.Valuesfrom simulation ···24

Fig.5.Gatelevelcircuit···25

Fig.6.FPGA Circuitdesign···27

Fig.7.FLEX10K FPGA verificationcircuit···28

ABSTRACT Implementation

Implementation Implementation

Implementation of of of of Inverse Inverse Inverse Inverse Algorithm Algorithm Algorithm Algorithm in in in Finite in Finite Finite Finite Fields Fields Fields using Fields using using using Composite

Composite Composite

Composite Fields Fields Fields Fields

SHIN,Ja-young

Advisor:Prof.RHEE,KangHyeon,Ph.D.

MajorinElectricity,ElectronicsandCommunicationEducation GraduateSchoolofEducation,ChosunUniversity

유한체(FinitefieldorGaloisfield)는 스위칭 이론,디지털 신호처리 및 화상처리, 디지털 통신의 암호화 및 해독화를 요하는 보안 통신 등에서 많이 응용되고 있다.

특히 오류정정부호 중 BCH 부호나 Reed-Solomon부호와 같은 블록부호는 유한 체 상에서 정의되며,CD(CompactDisc),DAT(DigitalAudioTape),타원곡선 알 고리즘 등의 부호화 및 복호화에 의 산술연산이 적용되어진다.현재 많은 응용분야에서 유한체 연산의 실시간 처리를 요하므로 유한체 연산을 위한 전용 하 드웨어 설계가 필요하게 되었고 이에 대한 많은 연구가 행하여지고 있다.

유한체는 사칙연산이 정의되는 유한개의 연소를 갖는 필드이며 모든 소수 P와 양수 에 대해서 개의 원소를 갖는 하나의 필드만이 존재한다.이 필드를 유한 체 필드라고 부르며 으로 나타낸다.유한체 상에서의 연산은 가ㆍ감산과 승 산,그리고 제산이 있으나 디지털 시스템은 유한체의 개수가 2의 승수인 에 서 이루어진다.유한체의 역원의 계산은 크게 유한체 제산기를 이용하는 방법과 승 산기를 이용하는 방법으로 나누어진다.제산기를 이용하는 방법은 빠른 동작 속도 를 가지나 하드웨어의 면적이 커지며,승산기를 이용한 방법은 하드웨어의 면적은

작아지나 계산에 많은 시간이 소모된다.본 논문에서는 합성체(CompositeFields) 를 이용하여 의 유한체의 역원을 계산할 수 있는 알고리즘을 제시하고 이 를 하드웨어로 구현하여 현재 사용되어지는 'ItohandTsujii'하드웨어 구조와 하 드웨어 면적 및 계산 속도의 성능을 비교 하였다.또한 AES의 SubBytes블록에 이를 삽입하여 AlteraFLEX10K FPGA 에뮬레이터 보드에 구현하여 제시된 알고 리즘의 회로가 정상적으로 동작함을 확인하였다.

Finitefields(orGaloisfields)areappliedfrequentlyinsecuritycommunication needing digital communication coding and interpretation such as switching theorem,digitalsignalprocessingandimageprocessing.

Especially,block codes such as BCH code and Reed-Solomon code among error correcting codes are defined with finite fields.Arithmetic operation of

is used for the encoding and decoding of CD (compact disc), DAT(digitalaudiotape),and ellipticalcurvecryptography.In application fields, many researches are underway fordesigning hardwares forusing finite field operation is needed since processing finite field operation is needed in real time[1,2].

A finite field is a field having a finite number of elements with four fundamental rules of arithmetics and exists in the field having only elements for prime number and positive number ofallelements.This finitefieldisexpressedas .Operationsonafinitefieldincludeaddition, subtraction,multiplication and division. However,adigitalsystem isachieved at where the number of finite fields is 2,i.e.,within multiplier.

Calculation ofmultiplicative inverse offinite field is divided largely into two methods,i.e.,themethod using a finite field dividerand themethod using a multiplier.Theformermethodisfastbutneedsalargeareaofhardware.The lattermethod needsasmallerareaofhardwarebutneedsmuch time.In this paper,we proposed an algorithm thatcould calculate multiplicative inverse offinite field using composite fields,implemented this algorithm in a hardware,andcomparethishardwarewiththecurrentlyused'ItohandTsujii' hardwarein respecttostructure,areaand computation time.Furthermore,this hardware was inserted into the AES SubBytes block to show on FPGA

emulatorboardtoconfirm thatthecircuitofproposed algorithm wasnormally functioning. Inthispaper,thecalculationofalgorithm multiplicativeinverseis examined in Chapter3 and the calculation ofalgorithm multiplicative inverse wasimplementedusingtheproposedcompositefieldinChapter4.InChapter5, we compare the circuitimplementation,activity characteristic,and 'Itoh and Tsujii'function.TheconclusionisdrawninChapter6.

Finite fields are the generalstarting pointfor the constructions of many combinatorial structures. It will be important to know the fundamentals concerning these fields in order to investigate combinatorialstructures and relatedareasofcombinatorialinterest.Unfortunately,theareaoffieldtheoryis ratherlargeand itwould be impossible forus to coveritin detailand still havetimetoworkwiththeresults.Intheinterestofconserving time,wewill presentthe elements ofgeneralfield theory withoutproofs and only prove statementswhenweturnourattentionspecificallytofinitefields.

Itwillbe assumed thatyou are familiarwith the definition ofa field,the definition and basicpropertiesofvectorspacesand thefactthattheintegers moduloaprime form afield (afiniteone),which wewilldenoteby

(standingfortheGaloisFieldoforder ).

Let be a field containing a subset ,which is itselfa field underthe operations inherited from .Then is called an extension of ,and a subfield of .Every field has a smallestsubfield,called the prime subfield, which isisomorphicto eitherthefield ofrationals ,in which casewesay thatithascharacteristiczero,ortoa forsomeprime ,in whichcase we say thatithas characteristic .We shalldenote the characteristic ofan arbitraryfield bychar .

If isanextensionof (denoted ),and isanelementof butnot an elementof ,then the smallestfield containing both and willbe denotedby andisasubfieldof .Similarly,thesmallestfieldcontaining

andtheelements in willbewritten as

.Any extensionfield of canbeviewedasavectorspaceover and the dimension ofthis vectorspace is called the degree of over ,and is denotedby .Ifthevectorspaceisfinitedimensionalwesaythat isa finite extension of .If is a finite extension of and is a finite

extensionof ,then .

Denoteby thering ofpolynomialsover in thevariable . isa principalidealdomain(anidealisasubring thatisclosedundermultiplication, aprincipalidealisanidealgeneratedbyasingleelement,andaprincipalideal domain isacommutativering with unity allofwhoseidealsareprincipal).A polynomialin issaidtobemonicifthecoefficientofthehighestpower in is unity.It is irreducible if it is not the product of two nonscalar polynomialsin .If isanirreduciblepolynomialin ,thenanyzero (i.e.,root)of isnotin andsothereisasmallestextensionfield of thatcontainsit.Furthermore, isisomorphictothequotientfield , where denotes the principalidealof generated by .Ifthe irreduciblepolynomial isofdegree ,then .Furthermore,if is thezeroof inquestion,then andtheelements

form abasisof over .

Beforewecontinue,letusillustratetheseideaswith awell-known example.

The field ofcomplex numbers is usually described in one oftwo ways, eitheras the setofnumbers where a and b are realnumbers and

    _orifyou prefernottomention theimaginary number , can be describedasthesetofallpairs ofrealnumberswhereaddition oftwo pairs is theusualcomponentwise addition and multiplication oftwo pairsis defined by .Thesecond version isofcourse viewing asavectorspaceofdimension 2overtherealnumbers .Letus

seehow wewouldconstruct starting with thesubfield .Now and is the ring of allpolynomials with realcoefficients.The polynomial

   _{is monic si}ncethe coefficientof is and itis irreducible over since itcannotbe factored into polynomials with only realcoefficients.The principalideal consistsofallpolynomialsthathave   _asafactor.

The quotient field structure, is obtained by taking each polynomialin and dividing itby   _{.Thepolynomial}sthathavethe sameremainderafterdivisionform equivalenceclasses,whicharetheelements of the quotient field.The different possible remainders are the polynomials

  _{,where i}n ,and we identify the equivalence classes with these remainders.The association   _iff   _clearly shows thatthe quotient fieldand areisomorphic.Now,let beazeroof  _,i.e.    _,so

      _{whichisnotanelementof . formsabasisfor over} sinceeveryelementof canbewrittenas       _{with in and} and are easily seen to be linearly independent.Using this basis,we can identifytheelementsof withtheircoefficientvectors,i.e.   _{iff to} getthe second representation as a vector space ofdimension 2 (notice the highestpowerof intheirreduciblepolynomial).

Fields are abstractions of familiar number systems (such as the rational numbers ,the realnumbers ,and the complex numbers ) and their essentialproperties.They consistofa set together with two operations, addition(denotedby+)andmultiplication(denotedby·),thatsatisfytheusual arithmeticproperties:

(i)( ,+)isanabeliangroupwith(additive)identitydenotedby .

(ii)( ,·)isanabeliangroupwith(multiplicative)identitydenotedby . (iii)Thedistributivelaw holds:   ⋅  ⋅  ⋅ _forall ∊

Iftheset isfinite,thenthefieldissaidtobefinite.

Thissection presentsbasicfactsaboutfinitefields.Otherpropertieswillbe presentedthroughoutthebookasneeded.

A field is equipped with two operations, addition and multiplication.

Subtraction offield elements is defined in terms ofaddition:for 





         _{where istheuniqueelementin such that}

( iscalled thenegativeof .)Similarly,division offield elementsisdefined in termsofmultiplication:for









Theorderofafinitefieldisthenumberofelementsinthefield.Thereexists afinitefield oforder ifandonlyif isaprimepower,i.e.,  ^ _where isaprimenumbercalledthecharacteristicof ,andm isapositiveinteger.

If ,then is called a prime field.If ≥ ,then is called an extensionfield.Foranyprimepower ,thereisessentiallyonlyonefinitefield oforder informally,this means thatany two finite fields oforder are structurally the same except that the labeling used to represent the field elements may be different.We say thatany two finite fields oforder are isomorphicanddenotesuchafieldby_.

Let beaprimenumber.Theintegersmodulo ,consisting oftheintegers

     _{with addition and multiplicati}on performed modulo ,is a finitefieldoforder .Weshalldenotethisfieldby_{ andcallpthemodulus} of_{.Foranyinteger , shal}ldenotetheuniqueintegerremainder ,

≤ ≤ ,obtained upon dividing by thisoperation iscalled reduction modulo .

Finite fields oforder^ _{are called binary fiel}ds orcharacteristic-two finite fields.One way to construct_^ _is to use a polynomialbasis representation.

Here,the elements of_^ _{are the binary polynomials (polynomials whose} coefficientsareinthefield )ofdegreeatmost :

_^ _{  }^{  } _{  }^{  }⋯ _^ _  _ _ ∊  

An irreducible binary polynomial of degree m is chosen (such a polynomialexistsforany m andcan beefficiently found).Irreducibility of meansthat cannotbefactoredasaproductofbinary polynomialseach of degree less than . Addition of field elements is the usual addition of polynomials,with coefficientarithmetic performed modulo 2.Multiplication of field elements is performed modulo the reduction polynomial .For any binary polynomial , shalldenote the unique remainder polynomial ofdegreelessthan obtained upon long division of by

thisoperationiscalledreductionmodulo .

Thepolynomialbasisrepresentation forbinary fieldscan begeneralized to all extensionfieldsasfollows.Let beaprimeand ≥ .Let_  _denotethe setofallpolynomialsin thevariable with coefficientsfrom _{.Let ,the} reductionpolynomial,beanirreduciblepolynomialofdegreem in_ _-sucha polynomialexistsforany and andcanbeefficientlyfound.Irreducibilityof meansthat cannotbefactored asa productofpolynomialsin _  each ofdegreelessthan .Theelementsof_^ _{arethepolynomialsin}_  ofdegreeatmost :

_^ _{  }^{  } _{  }^{  }⋯ _^ _  _  _ ∊

Addition offield elementsistheusualaddition ofpolynomials,with coefficient arithmeticperformedin_{.Multiplicationoffieldelementsi}sperformedmodulo thepolynomial .

A subset ofafield isasubfieldof ifkisitselfafieldwith respect totheoperationsof .Inthisinstance, issaidtobeanextensionfieldof . Thesubfieldsofafinitefieldcanbeeasilycharacterized.A finitefield_^ _has precisely onesubfieldoforder^ foreachpositivedivisor ofm theelements ofthissubfield aretheelements ∊_^ _satisfying ^ _{.Conversely,every} subfieldof_^ _hasorder^ forsomepositivedivisor of .

The finite field _^ _{can be vi}ewed as a vectorspace overits subfield _. Here,vectorsareelementsof_^_{,scalarsareelementsof}_,vectoradditionis theadditionoperationin_^_{,andscalarmultiplicationisthemultiplicationin}_^ of_{-elementswith} _^_-elements.Thevectorspacehasdimension and has manybases.

If __ ⋯_ _{isabasis,then} ∊_^ _canbeuniquelyrepresentedby an -tuple__ ⋯ _ _of_-elements where  __ __⋯ __.For example,in the polynomialbasis representation of the field Fpm described above,_^ _{isan -dimensi}onalvectorspaceover and^{  }^{  }⋯  isabasisfor_^ _over_.

The nonzero elements ofa finite field _,denoted ^_,form a cyclic group undermultiplication.Hencethereexistelements ∊^_{ call}ed generatorssuch that:

^_ ^   ≤  ≤    

Theorderof ∊^_{ isthesmallestpositivei}nteger suchthat^ _.Since

^_{ isacyclicgroup,itfollowsthat isadivisorof .}

Thissection presentsalgorithmsforperforming arithmeticin theprimefield

_.Algorithmsforarbitrary primes arepresented.Thereductionstepcanbe accelerated considerably when the modulus has a specialform.Efficient reductionalgorithmsfortheNIST prime.

The algorithms presented here are wellsuited forsoftware implementation.

Weassumethattheimplementationplatform hasa -bitarchitecturewhere is a multiple of 8.Workstations are commonly 64 or 32-bit architectures.

Low-powerorinexpensivecomponentsmayhavesmaller ,forexample,some embeddedsystemsare16-bitandsmartcardsmay have = 8.Thebitsofa

-bitword are numbered from to ,with the rightmostbitof designatedasbit .

Theelementsof aretheintegersfrom to .Let  _  _bethe bitlength of ,and be its wordlength.Fig.1 illustrates the case where the binary representation ofa field elementa is stored in an array

            _{of -bi}twords,wheretherightmostbit of istheleastsignificantbit.

Fig.1Representationof ∊_ asanarray of -bitwords.

Hardware characteristics may favourapproaches differentfrom those ofthe algorithmsandfieldelementrepresentationpresentedhere.

A[t-1] … A[2] A[1] A[0]

Algorithms for field addition and subtraction are given in terms of corresponding algorithms formulti-word integers.The following notation and terminologyisused.Anassignmentoftheform " ←"foraninteger is understoodtomean

← ^_,and

←   ∊ ^ ←

If      ^ _for ∊ ^ _and^∊   _then  ^  _and  is called the carry bitfrom single-word addition (with    _{ifand only if}

    ^_.

Field multiplication of ∊_ can be accomplished by firstmultiplying and as integers,and then reducing the result modulo .Algorithms are elementary integer multiplication routines which illustrate basic operand scanning and productscanning methods,respectively.In both algorithms,( ) denotesa( )-bitquantity obtained by concatenation of -bitwords and

.

The calculation      ⋅   _{is called the i}nner product operation.Sincetheoperandsare -bitvalues,theinnerproductisboundedby

 ^    ^  ^ ^  andcanberepresentedby( ).

Formodulo thatarenotofspecialform,thereduction mod can bean

expensivepartofmodularmultiplication.Sincetheperformanceofellipticcurve schemes depends heavily on the speed of field multiplication, there is considerableincentivetoselectmodulo,suchastheNIST-recommendedprimes, thatpermitfastreduction.Inthissection,wepresentonlythereductionmethod ofBarrettandanoverview ofMontgomerymultiplication.

The methods of Barrett and Montgomery are similar in that expensive divisions in classical reduction methods are replaced by less-expensive operations. Barrett reduction can be regarded as a direct replacement for classical methods; however, an expensive modulus-dependent calculation is required, and hence the method is applicable when many reductions are performed with a single modulus.Montgomery's method,on the otherhand, requirestransformationsofthedata.Thetechniquecan beeffectivewhen the cost of the input and output conversions is offset by savings in many intermediatemultiplications,asoccursinmodularexponent.

Note that some modular operations are typically required in a larger frameworksuchasthesignatureschemes,andthemoduloinvolvedneednotbe ofspecialform.

We willillustrate the above materialby actually constructing some finite fields.

Since   ^_{, the prime field must be whose el}ements we will representby and ,andwhereadditionandmultiplicationaredonemodulo

.Weseekan extension ofdegree overtheprimefield,soourfirsttask is

tofindamonicirreduciblepolynomialofdegree in .Forlargefield thiscanbeadifficultassignment,butforsmallfieldsitisnottoobad.While therearesometheoremsthatmayhelp,thebruteforceprocedureiseffectiveif theprimefieldissmall.Wecan in facteasily listallofthemonicquadratics inthisring,theyare:

^

^ 

^ 

^ 

^   

^   

^ 

^   

^   

Now the problem is to find the irreducible ones in this list.Clearly,any polynomialwithouta constantterm is factorable( is a factor),so the first, fourth and seventh can immediately be crossed out.For the remaining six polynomials,we may optforone oftwo procedures.We could take each in turn and substituteallthefield elementsfor ,ifnoneofthesesubstitutions evaluatestozero,thepolynomialisirreducible(i.e.,ithasnorootinthefield).

So,forexample,substituting in^  _{givesthevalues}^   _,^    and ^   _,thus ^  _{factors,in fact}^         _{.On the} other hand,the same procedure for^  _gives ^   _,^    _and

^    _{and so}^  _{is irreducibl}e.The second possible procedure is to takeallthelinearfactors(in thiscase,becausewewantquadraticproducts)

and multiply them in allpossible pairs to get a list of allthe factorable quadratics,removing these from ourlistleaves allthe irreducible quadratics.

So,

        ^   

        ^ 

        ^   

Implying that,^ _,^    _and ^    are the only irreducible monic quadratic polynomials in .We could now choose any one of theseletting beazeroofthechosen polynomialandwriteouttheelements of initsvectorform representationusingthebasis .Thishowever does notgive us the mostusefulrepresentation ofthe field.Rather,we will usethefactthatthemultiplicativegroup ofthefield iscyclic,so ifwecan find aprimitiveelement(i.e.,ageneratorofthecyclicgroup)wewillhavea handy representation ofthe elements.Now the primitive elements are to be foundamong therootsoftheirreduciblepolynomials(they cannotbeelements oftheprimefield).Thecyclicgroup weareafterhasorder ,so notevery root need be primitive.For example,letting be a root of ^ _,i.e.,

^   _,so^ _,wecanwriteoutthepowersof .

^  ^  ^ ^     ^     

Andso hasorder anddoesnotgeneratethecyclicgroupoforder ,i.e., is nota primitive element.On the other hand,consider a rootofthe polynomial^   _,sothat^      _or^   .Now thepowers

^ 

^   

^       ^             

^ ^         

^ 

^ ^   

^ ^           

^ ^         

so isaprimitiveelementandsowehaverepresentedtheelementsof

asthe powersof togetherwith .Noticealsothattheboldedtermsonthe rightareallthepossibletermsthatcan bewritten aslinearcombinationsof thebasis{ over .Whenworkingwithfinitefieldsitisconvenientto havebothoftheaboverepresentations,sincethetermsontheleftareeasyto multiply and the terms on the rightare easy to add.So forinstance,ifwe wanted to calculate    ^   _{, we would do so in this way,}

   ^ ^^ ^  _andso   ^               ^

Since   ^_{,the prime field is} and we need to find a monic irreduciblecubicpolynomialoverthatfield.Sincethecoefficientscanonlybe and ,thelistofirreduciblecandidatesiseasilyobtained.

^ 

^   

^ ^ 

^ ^   

Now substituting gives inallcases,andsubstituting willgive onlyif there are an odd number of terms,so the irreducible cubics are just

^    _and ^ ^ .Now the multiplicative group ofthis field is a cyclicgroupoforder andsoeverynonidentityelementisagenerator.Letting bearootofthefirstpolynomial,wehave^     _,or^   _,so thepowersof are:

^ 

^ ^

^   

^ ^ 

^ ^   

^ ^ 

^ 

Now supposewehad chosen a rootofthesecond polynomial,say , .We wouldthenhave^ ^  andtherepresentationwouldbegivenby

^ 

^ ^

^ ^ 

^ ^   

^   

^ ^ 

^ 

Weknow thatthesetwo representationsmustbeisomorphic,show thatthe isomorphism isinducedby  ^_.

Typicalmethods of calculating inverses in finite fields include the Fermat theorem,the method using extended Euclid algorithms,and the method using finitefieldmultipliers[3,4].Thereisalsothemethodofusing compositefieldsas proposedinthisstudy.

TheFermattheorem isexpressedastheEquation(1)whentherandom numbersa andphaverelationofrelativelyprime.





^    ∊ 

^{ } ^{  } ^{ }  ^   ^ ₍₁₎

WhenaninverseiscalculatedwithFermattheorem,themultiplicationof time andsquareof timesareneededforoperationon .

Equation (2)showstheprocessofcalculating thegreatestcommon dividers oftwopolynomials,i.e.,   _and  _,         _{using Euclid} algorithm.

_{ }      _     

_{ }   _ _   _ 

_   _ _   _ 

⋮ ⋮

_{  }   _ _   _{  } 

(2)

whenGCD isinEquation(2),theEquation (3)resultsaccording toextendedEuclid algorithm.

              

        ⁽³⁾

In addition,   _and    in Equation (3)can be calculated as the repetitive calculationasinEquation(4).

_{ }    _   

_{ }    _   

_   _{  } _{  }   _{  }    ≤  ≤    

_   _{  } _{  }   _{  } 

(4)

_  inEquation(4)iscalculatedwithEquation(2)._  calculatedrepeatedly until   inEquation(2)reaches_{  } _,becomes  _,and_{  }  _becomes

^{ } _.

Here,Equation(3)isrewrittentobecome

            ₍₅₎

Atthistime,since isanirreduciblepolynomial,itisalways .

Thus,theresultbecomes

          

    

       ⁽⁶⁾

Whenthefinitefiledelement isinputtedinthe field,theinverseof isachievedasinEquation(7).

^{ } ^ 

^{ } ^{ }⋅^ ^{ (7)}

We compared the circuitarea and computation time ofproposed algorithm with 'ItohandTsujii'circuitappliedinEquation(7).

Using thesecond compositefield,thealgorithm calculating themultiplicative inverseoffinitefield wasproved by CristofPaar[5].When twofinitefields ζ and δ have δ=ζ^-1relationship,wecould calculatethemultiplicativeinverseof finitefieldaccordingtoEquation(8).

 _ _

 _ _

_ __^{ }

__^{ }

_^___^

(8)

Weimplemented theinversealgorithm in finitefield using Equation (8).For hardware design,the multiplicative inverses ofChristofPaar[1]were referred and multiplicativeinversesweredesigned.Refereeing totheMastrovito structure[6],finitefieldmultiplierwasdesigned.

in finite fields can be or .In this study, wasusedasthecompositefieldof [7,8].

Equation(9)canebeusedwhen ∊^^_.

 _ _{ (9)}

Here, istherootoftheirreduciblepolynomial of andsatisfies

_⋅_∊^_{.Equation(10)istheirreduciblepolynomial .}

   ^  ₍₁₀₎

From Equations(9)and(10),^{ } _canbedrivenasEquation(11).

^{ }   

⋅   __^ ____ __

    ^ 

(11)

Equations (12)and (13)show the process ofcalculating the multiplicative inversesoffinitefields,i.e.,_{ and}_{ anddri}venfrom Equation(11).

______  ____

    ⁽¹²⁾

______ 

____ 

_____^{ }

___^{ }__^{ }  

__^{ }_^___^  

(13)

As a result,the computation ofmultiplicative inverses in finite fields using compositefieldsisdrivenasEquation(14).

__⋅^{ } _ __⋅^{ }

_^___^^{  (14)}

From Equation (14),the computation algorithm ofmultiplicative inverse of finite field was implemented as in Fig.2.Here,the irreducible polynomialof compute field used was    ^   ^_. ^ _{is calculated to be}

^   ^ _.

S

Squarer

Inverter R

14 14 14 14{1001}

βββ β

Adder Multiplier

Fig.2.Circuitdesignforinversecalculationusingcompositefields

InFig.2, blockisthearrangeblockchangingtheinputextensionfieldinto compositefield. blockisthearrangeblockchanging thecompositefieldinto theextension field.in which [8].Fig.3showsthevaluesof and blocks.

 

































       

       

       

       

       

       

       

       



































       

       

       

       

       

       

       

        Fig.3.BlockcoefficientofS andR

When the results driven were coded using VHDL,the outputvalues were

normal.Comparison with the resultantvalues was done using the inverse of finitefieldmultiplierexplainedintheinversetableofAES S-boxandChapter.

Fig.4show thesimulationresult,showingthesameinversevalue.

Fig.4.Valuesfrom simulation

Fig.5 is the gatelevelcircuitsynthesized using core_slow.db in Synopsys.

Theoverallcellareawas4593.87.

Fig.5.Gatelevelcircuit

The inverse computation algorithm proposed in this study and ‘Itoh and Tsujii'algorithm arecomparedinTable1.

Design

Architecture CellArea DataArriver Time 'ItohandTsujii' 12030.64 19.960[ns]

ProposedDesign 4593.87 15.155[ns]

Table1.Resultsofcircuitsynthesisandcomparisonoffunction

Whenthefunctionwascompared,thedesignproposedinthisstudyshoweda decreaseof61.6% in cellareaand an increaseof24.97% in computation time

comparedwith'ItohandTsujii'design.

Theinversealgorithm proposedinChapter4wasimplementedonAltera FLEX10K.Activityofimplementedalgorithm wasconfirmedbyimplementing FPGA circuitratherthantherom tablebydesigningAES SubBytesTransform circuit.ThecircuitdesignisshowninFig.6.

Fig.6.FPGA Circuitdesign

Fig.7showsthepictureactuallyrealizedonFPGA emulatorboard.

Fig.7.FLEX10K FPGA verificationcircuit

In Fig.7,the output data in the ouput data portion is outputted in 7 segments and the circuitinitializes through the RESET Key.The INVERSE Keyisthecontrolpreventingthecircuitfrom inversetransformation.

Weproposedanoptimalalgorithm tocalculatethemultiplicativeinverseofa finitefieldusing compositefieldsandimplementtheresultonAlteraFLEX10K FPGA board.Inthispaper,wecouldimplementthecircuitwithAND andXOR gate. The result of circuit synthesis showed that cell area was 4593.87, showing a decrease of 61.8% in cellarea compared with 'Itoh and Tsujii' algorithm,whichusesmultipliersoffinitefields,andthecomputationtimewas 15.155[ns], which improved by 24.07%. Furthermore, in order to confirm whether the multiplicative inverse of finite field was functioning normally, normalfunction was confirmed using AES SubBytes Transform designed to substituteforROM tableusedforinversecalculation.

[1]C.Paar.EfficientVLSIArchitecturesforBit-ParallelComputation in Galois Fields.Ph.D thesis,Institute for ExperimentalMathematics,University of Essen,1994

[2]VincentRijmen.EfficientimplementationoftheRijndaelS-box.

http://www.esat.kuleuven.ac.be/~rijmen/rijndael/sbox.pdf,

[3]FederalInformation Processing Standards Publication 197,Nov.26,2001.

AnnouncingtheADVANCED ENCRYPTION STANDARD.

[4]MichaelRosing,ImplementingEllipticCurve Cryptography,Manning,1999.

[5]C.Paar,P.FleischmannandS.Pedro,FastArithmeticforPublic-KeyAlgorithms inGaloisFieldswithCompositeExponents, .,vol.48, no.10,pp.1025-1034,Oct.1999.

[6]E.D Mastrovito,"VLSIArchitecture forComputation in Galois Field," PhD Thesis,PhD Dissertation,LinkpingUniv.,LinkpingSweden,1991.

[7]T.ItohandS.Tsujii,"A fastalgorithm forcomputingmultiplicativeinverses in GF(2^m)using normalbasis",J.Society forElectronicCommunication,pp.

31-36,1986.

[8]Cillian O'Driscoll.Hardware implementation aspects ofthe Rijndaelblock cipher.Master'sthesis,UniversityColleg.

[9]The originalgranddaddy in the area is:Dickson,LinearGroups (with an ExpositionoftheGaloisFieldTheory),Dover,1958.

[10]Berlekamp,AlgebraicCodingTheory,McGraw-Hill,New York1968.

[11]Blake & Mullin,An Introduction to Algebraic and CombinatorialCoding Theory,AcademicPress,1976.

[12] IntroductiontotheTheoryofError-CorrectingCodes,Wiley,1982.

[13] Lidl & Niederreiter, Finite Fields, Vol. 20 in the Encyclopedia of

MathematicsanditsApplications,Addison-Wesley,1983.

[14]Lidl& Niederreiter,Introduction to Finite Fields and their Applications, CambridgeUniversityPress,1986.

[15] McEliece,Finite Fields for Computer Scientists and Engineers,Kluwer AcademicPublishers,1987.