Encriptacion rsa

Solo disponible en BuenasTareas
  • Páginas : 33 (8019 palabras )
  • Descarga(s) : 0
  • Publicado : 27 de abril de 2011
Leer documento completo
Vista previa del texto
Cap´ ıtulo 12

Algoritmo RSA

153

154

Anillo de los enterosM D

Nota: Los puntos marcados con M D se ver´n en la asignatura Matem´tica Discreta. Los a e M C en Matem´ticas para la Computaci´n. Los marcados con ambos se marcados con a o ver´n especialmente en la primera asignatura que aparezca, y se recordar´n brevemente a a en la otra.

12.1

Introducci´n o

El m´todo deencriptado de datos conocido como algoritmo RSA, por los nombres de sus e inventores (Rivest, Shamir y Adleman) es uno de los m´s usados hoy d´ para la transmisi´n a ıa o segura de datos a trav´s de canales inseguros. Este documento es una introducci´n a las bases e o matem´ticas de dicho algoritmo de encriptado escrita para llegar desde unos conocimientos a m´ ınimos (el concepto de anillo de losenteros y la existencia y unicidad de la descomposici´n o en factores primos de un entero) hasta la comprensi´n del algoritmo en s´ tratando de no o ı, omitir casi ninguna demostraci´n (aunque algunas se realizar´n en la clase, o se dejan como o a ejercicio, y una de ellas excede el alcance del curso). Est´ casi ´ a ıntegramente basado en los libros del prof. Manuel Lucena (Univ. de Ja´n) y de losprofesores J.M. Basart, J. Rif´ y M. e a Villanueva (Universitat Aut`noma de Barcelona). V´ase la bibliograf´ al final. o e ıa

12.2

Anillo de los enterosM D

Un concepto del que se parte es la existencia de un conjunto llamado de los n´ meros enteros, u en el que est´ definida una relaci´n de orden total (ser mayor que) y unas operaciones arita o m´ticas (suma y producto, con las definicionesusuales) que le confieren estructura de anillo, e es decir:

Z = {. . . , −4, −3, −2, −1, 0, 1, 2, 3, . . .}

• La operaci´n + en Z es conmutativa, asociativa, tiene elemento neutro (el 0) y todo o elemento tiene su sim´trico, llamado opuesto. Por tanto, (Z, +) es grupo conmutativo. e • La operaci´n · en Z es conmutativa, asociativa y tiene elemento neutro (el 1). Sin o embargo, no todo elementotiene sim´trico, que aqu´ se llamar´ inverso (de hecho, e ı ıa solamente el 1 y el −1 lo tienen, y son ellos mismos). • La operaci´n · es distributiva respecto a +. o Por tanto, (Z, +, ·) es un anillo conmutativo con elemento unidad, llamado el anillo de los enteros.

155

12.3
12.3.1

Conceptos b´sicos de aritm´tica en Z a e
Divisi´n enteraM D o

Dados a, b ∈ Z, diremos que la divisi´nde a entre b tiene cociente q y resto r si es cierto que o a = bq + r, siendo q un n´ mero entero sin restricciones, y r un n´ mero entero comprendido u u entre 0 y b − 1. Ejemplos: 137 dividido entre 21 da como cociente 6 y como resto 11, dado que se puede escribir 137 como 137 = 21 · 6 + 11. -137 dividido entre 21 da como cociente -7 y como resto 10, dado que se puede escribir -137 como −137 =21·(−7)+10. N´tese que escribir -137 como −137 = 21·(−6)−11 no cumple los o requisitos de la definici´n de divisi´n entera, dado que el supesto resto, -11, no est´ entre 0 y 21. o o a

12.3.2

M´ltiplos y divisoresM D u

Dados dos n´ meros enteros, a, b ∈ Z, con a ≤ b, se dice que a es m´ ltiplo de b, o equivalenu u temente, que b es divisor de a, si existe alg´ n entero q ∈ Z tal que a = q ·b, o lo que es lo u mismo, si al realizar la divisi´n entera de a entre b, seg´ n se ha definido en el punto anterior, o u el cociente es q y el resto es 0. Es obvio que 1 es divisor de cualquier n´ mero entero, dado u que ∀a ∈ Z, a = a · 1 con lo que el cociente es el propio a y el resto 0.

12.4
12.4.1

Definiciones b´sicas a
M´ximo com´n divisorM D a u

Dados n n´ meros enteros, {a1 , . .. , an } ∈ Z se llama m´ximo com´ n divisor, abreviado u a u m.c.d., al mayor n´ mero entero positivo m que es divisor de todos ellos, y se escribe m = u mcd(a1 , . . . , an ). Como 1 es divisor de cualquier n´ mero, en ausencia de otro divisor com´ n u u mayor, 1 ser´ el m.c.d. de cualquier conjunto de enteros. ıa

12.4.2

M´ ınimo com´n m´ltiploM D u u

Dados n n´ meros enteros, {a1 , ....
tracking img