在封闭且有限的数集合中

1、Chap. 4: Finite FieldsJen-Chang Liu, 2004Adapted from lecture slides by Lawrie BrownThe next morning at daybreak, Star flew indoors, seemingly keen for a lesson. I said, Tap eight. She did a brilliant exhibition, first tapping it in 4, 4, then giving me a hasty glance and doing it in 2, 2, 2, 2, bef

2、ore coming for her nut. It is astonishing that Star learned to count up to 8 with no difficulty, and of her own accord discovered that each number could be given with various different divisions, this leaving no doubt that she was consciously thinking each number. In fact, she did mental arithmetic,

3、 although unable, like humans, to name the numbers. But she learned to recognize their spoken names almost immediately and was able to remember the sounds of the names. Star is unique as a wild bird, who of her own free will pursued the science of numbers with keen interest and astonishing intellige

4、nce. Living with Birds, Len HowardLen HowardnBritish naturalist, who studied bird behaviorsnPublications:nBirds as Individuals (1953)nLiving with Birds (1956). IntroductionnFinite fields: increasing importance in cryptographynAES, Elliptic Curve, IDEA, Public KeynGoal: mathematics for GF(2n)01100010

5、0Plaintext: 2n110100111Ciphertext: 2nT(Plaintext, Key)1. Arbitrary mapping = large keys2. Mathematical form, ex. Hill cipherOutlinenGroup, rings, and fieldsnModular arithmeticnFinite fields of the form GF(p)nEuclids algorithm (find GCD)nPolynomial arithmeticnFinite fields of the form GF(2n)Motivatio

6、nn在封閉且有限的數集合中，可操作的運算種類？(+, -, x, /)GroupRingField+,-+,-,x+,-,x,/GroupnGroup: G, nG: a set of elementsn: binary operation to each pair (a,b) in Gnobeys:nclosure: ab is also in Gnassociative law:(ab)c = a(bc) nhas identity e:ea = ae = a nhas inverses a-1: aa-1 = enif commutative ab = ba nthen forms an

7、 abelian groupExample: group1. Set of integers under addition= Abelian group2. N symbols : Nn=1, 2, , nnSet Sn: all permutations over NnnBinary operation : permutation according to the first element= Group1, 2, , n, 2, 1 , n, , n, n-1, , 13,2,11,3,2=2,3,1Cyclic Groupndefine exponentiation as repeate

8、d application of operatornexample: a3 = aaanand let identity be: e=a0na group is cyclic if every element is a power of some fixed elementni.e. b = akfor some a and every b in groupna is said to be a generator of the groupEX. integers with addition: 1 as the generatorRingnRing: R, +, xnR: a set of “n

9、umbers”n+, x: two operations (addition and multiplication) nRing obeysnR,+: an abelian groupnmultiplication:nhas closurenis associative: ax(bxc)=(axb)xcndistributive over addition: ax(b+c) = axb + axcnif multiplication operation is commutative, it forms a commutative ring axb = bxaExample: RingnThe

10、set of even integers (pos, neg, and 0)nCommutative ringFieldnField: F, +, xnF: a set of numbers n+, x: two operations (addition and multiplication) nField obeys:nRingnF, +: abelian group for addition nF0, x: abelian group for multiplication (ignoring 0) ni.e. with multiplication inverse = division i

11、s possiblenZ, +, x ?Field for n-bit block?011000100Plaintext: 2n110100111Ciphertext: 2n+: additionx: multiplication?Problems: 1. the set of plaintext (and ciphertext) finite 2. how to define +,-,x,/ operationsOutlinenGroup, rings, and FieldsnModular arithmeticnFinite fields of the form GF(p)nEuclids

12、 algorithm (find GCD)nPolynomial arithmeticnFinite fields of the form GF(2n)Modulo operatornmodulo operator: a mod n to be the remainder (0) when a is divided by n) mod (/nannaa, a and n are integersModulo operator (cont.)nIntegers a and b are congruence modulo n a b mod n nwhen divided by n, a & b

13、have same remainder neg. 100 = 34 mod 11 nb is called the residue of a: b= a mod nnintegers can always write: a = qn + bnusually have 0 = b groupModulo 8(=23) ExampleNot all haveMulti. Inverse Not a fieldDoes notproduce allelements inZ8Modular Arithmetic (cont.)nPeculiarities compared with ordinary

14、arith.nif (a+b)(a+c) mod n then bc mod nnExistence of (-a):nif (ab)(ac) mod n then bc mod n ?nExistence of (a-1) ?(-a)+a+b)(-a)+a+c) mod n(a-1) ab)(a-1) ac) mod nNot always true, eg. n=8Multiplicative inverse exists iff. a is relatively prime to n QuestionnDo we have a finite field within Zn ?Modulo

15、 7 example: additionYes foradditive inverseModulo 7 Example: multiply Yes formulti. inverseQuestionnDo we have a finite field within Zn ?nGalois fieldnGF(p): ZP ,the modulo p is a prime numbernUnder ordinary arithmeticnGF(pn): , p is a prime numbern23 does not form a field under normal arithmeticnUn

16、der polynomial arithmeticnpZOutlinenGroup, rings, and FieldsnModular arithmeticnFinite fields of the form GF(p)nEuclids algorithm (find GCD)nPolynomial arithmeticnFinite fields of the form GF(2n)Galois Fields: GF(p)nTheorem: Zn=0,1,n-1 is a commutative ring. Any integer aZn in has a multiplicative i

17、nverse iff a is relatively prime to nnIn other words, nIf n is a prime number, then all nonzero integers in Zn are relatively prime to n= all nonzero integers in Zn have multiplicative inverses= Zn is a finite field= GF(p), p is a primeGalois Fields: GF(p)nGF(p) is the set of integers 0,1, , p-1 wit

18、h arithmetic operations modulo prime pnthese form a finite fieldnsince have multiplicative inversesnhence arithmetic is “well-behaved” and can do addition, subtraction, multiplication, and division without leaving the field GF(p)Example: GF(2)+0 1010 11 0 x0 1010 00 1w-w w-1010 x1 1XORANDQ: How to f

19、ind the multiplicative inverse?nFor GF(7), it is easy to build a tablenFor GF(1759), how to find the multiplicative inverse of 550?OutlinenGroup, rings, and FieldsnModular arithmeticnFinite fields of the form GF(p)nEuclids algorithm (find GCD) and extended Euclids algorithm (find multiplicative inve

20、rse)nPolynomial arithmeticnFinite fields of the form GF(2n)Greatest Common Divisor (GCD)na common problem in number theorynGCD (a,b) of a and b is the largest number that divides evenly into both a and b neg. GCD(60,24) = 12nGCD(.,.)=1: no common factors (except 1) and hence numbers are relatively p

21、rimeneg. GCD(8,15) = 1nhence 8 & 15 are relatively prime Euclids GCD Algorithmnuses theorem that: (ab0)nGCD(a,b) = GCD(b, a mod b) To prove: The set of common divisors of a and b = The set of common divisors of a and (a mod b)Example GCD(1970,1066)1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 +

22、 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gcd(10, 6)10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 + 2 gcd(4, 2)4 = 2 x 2 + 0 gcd(2, 0)Finding Inversesncan extend Euclids algori

23、thm:EXTENDED EUCLID(m, b)1.(A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b)2. if B3 = 0return A3 = gcd(m, b); no inverse3. if B3 = 1 return B3 = gcd(m, b); B2 = b1 mod m4. Q = A3 div B35. (T1, T2, T3)=(A1 Q B1, A2 Q B2, A3 Q B3)6. (A1, A2, A3)=(B1, B2, B3)7. (B1, B2, B3)=(T1, T2, T3)8. goto 2Inverse o

24、f 550 in GF(1759)(商)410B2=A2-Q*B2=0-3*1=-3inverseRecall: inverse matrix in Hill ciphernFind inverse matrix fornNote that 26 is not a prime, not every element in 0,1,2,25 has multiplicative inversenInverse formula:7549K9212274319547457911KInverse of Hill cipherQ A3 B3 26 171 17 91 9 81 8 18 1 0A2 B2

25、0 1 1 -1-1 2 2 -32515125207483506161921227239212271711KMultiplicative inverseOutlinenGroup, rings, and FieldsnModular arithmeticnFinite fields of the form GF(p)nEuclids algorithm (find GCD)nPolynomial arithmeticnFinite fields of the form GF(2n)Motivation for GF(2n)nFor a 8-bit blocknZ256 =0,1,255 is

26、 not a field = no divisionnThe largest prime 251,255 are wastednIs that possible to find a field for Z256 ?nYes. Define new arithmetic operations for Z256Mapping from GF(2n) to polynomialsnEx. 8-bit block100101110123456711101001xxxxxxxx= To build the field for 0,1,2,2n-1= Require modular polynomial

27、arithmeticPolynomial ArithmeticnPolynomialsn3 polynomial arithmetic available:nordinary polynomial arithmeticnPolynomial with coefficients in Zp; arithmetic on the coefficients is performed modulo pnPolynomial with coefficients in Zp, and the polynomials are defined modulo a polynomial m(x); arithme

28、tic on the coefficients is performed modulo p1. Ordinary Polynomial ArithmeticnAdd(+) or subtract(-) corresponding coefficientsnMultiply(x) all terms by each otherneg. 1101, 0111nf(x) = x3 + x2 + 1 and g(x) = x2 + x + 1f(x) + g(x) = x3 + 2x2 + x + 2f(x) g(x) = x3 - x f(x) x g(x) = x5+2x4+2x3+2x2+x+1

29、GF(24) ?1. Not in 0,1 2. degree32. Polynomial Arithmetic with Modulo CoefficientsnPolynomial coefficients are in a field F=p,+,xnWe are most interested in coefficients in GF(2)neg. 1101, 0111nlet f(x) = x3 + x2 + 1 and g(x) = x2 + x + 1f(x) + g(x) = x3 + x f(x) x g(x) = x5 + x + 1GF(24) ?degree 33. Modular Polynomial Arithmetic for GF(2n)nPolynomial coefficients