Encriptacion - Rinjdael

Capítulo 3
Principios Algebraicos Básicos
En este capítulo se resumen los aspectos más sobresalientes de la Teoría de Campos
Finitos. Se presentan primero conceptos fundamentales del álgebra de Grupos, Anillos y Campos.
A continuación se examina la estructura de Campos Finitos. Por último se analizan los principios
básicos de Campos Compuestos por hallarse este tema íntimamente relacionadocon la
implementación del Algoritmo Rijndael.

3.1 Grupos

Definición 3.1.1: Un conjunto de G elementos sobre los cuales se ha definido una operación
binaria, se denomina grupo cuando satisface condiciones de asociatividad, contiene un elemento
identidad único y, para cada elemento de G, existe un único elemento inverso [ALL83].

Si la operación binaria satisface condiciones deconmutatividad se dice que G es un grupo
conmutativo o abeliano. Entre los grupos conmutativos más conocidos se encuentran el de los
números enteros y el de los números racionales. El conjunto de enteros es un grupo conmutativo
bajo la operación de suma (+), siendo el 0 el elemento identidad y –i la inversa de un número
entero i. El conjunto de números racionales excluyendo el cero es un grupoconmutativo bajo la
operación de multiplicación (x), siendo 1 el elemento neutro y el número b/a el inverso multiplicativo
de a/b.

El conjunto G = {0, 1} bajo la operación suma módulo-2 (⊕) es un grupo conmutativo. La
operación es equivalente en el Algebra Booleana a una EXOR. En dicho grupo, 0 es el elemento
identidad y la inversa de cada elemento es el mismo elemento.

25

Definición 3.1.2: Elnúmero de elementos de un grupo G se denomina orden del grupo y se
denota ordG. De esta manera, según la cantidad de elementos, se puede hablar de dos grandes
clases de grupos: infinitos y finitos. Para los fines de esta tesis, se consideran sólo los grupos
finitos.

Definición 3.1.3: El orden de un elemento g en un grupo finito G, es el número más pequeño

s > 0 , tal que g s tenga comoresultado el elemento identidad y se denota ordg . Se deduce que
existirán s potencias distintas de

g [ALL83]. Se deduce también que el orden máximo de un

elemento no puede superar al orden del grupo al que pertenece, pues entonces el conjunto de
potencias de dicho elemento sería mayor que el número de elementos del grupo. Dado que todos
los elementos de G deben ser distintos entre sí,esta última situación no sería posible.

Definición 3.1.4: Siendo m un entero positivo, es posible definir un grupo finito conmutativo de
orden m: G = { 0, 1, 2, .... ,m-1}, bajo la operación suma módulo-m [HIL78], siendo 0 el elemento
identidad y (m-i) el elemento inverso de i. Se lo conoce como grupo aditivo.

Definición 3.1.5: El grupo de enteros G = {1, 2, 3,...., p-1}, con p primo, bajo laoperación
multiplicación módulo-p es un grupo conmutativo cuyo elemento identidad es 1 [ALL83]. Siendo i
un elemento de G tal que

i < p , i y p deben ser primos relativos por lo que se verifica que existen

dos enteros a y b que cumplen el Algoritmo de Euclides. Por el Teorema de Euclides a y p son
primos relativos y se relacionan por medio de la Ec.(3.1) [HIL78].

a.i + b. p = 1
Severifica que, si el producto

(3.1)

(a.i ) se divide por p, el resto de la división da 1. Si

0 < a < p , a pertenece a G y resulta ser inverso multiplicativo de i [LIN83].

Sin embargo, si
pues

a no pertenece a G, al dividir a por p, el resto r < p es distinto de p y de 0

a y p son primos relativos. De este modo r pertenece a G y es tal que 1 < r < ( p − 1) y

26

resulta serel inverso multiplicativo de i. Las Ec.(3.2) a Ec.(3.5) ilustran lo explicado.

a = qp + r

(3.2)

a.i = qp.i + r.i

(3.3)

qp.i + r.i = −b. p + 1

(3.4)

r.i = (−b + q.i ) p + 1

(3.5)

El grupo G = {1, 2, 3,...., p-1} bajo la multiplicación módulo-p resulta ser un grupo
multiplicativo. Si p no es un número primo, G no es grupo bajo la multiplicación módulo-p [LIN83]....