Numeros-p-adicos-y-criptografAa

Vista previa del material en texto

repositorio.uptc@uptc.edu.corepositorio.uptc@uptc.edu.co
Números p-ádicos y Criptografı́a
Adriana Alexandra Albarracı́n Mantilla[
[Universidad Industrial de Santander, Grupo de investigación ALCOM, e-mail:
alealbam@uis.edu.co
Resumen: En los últimos años la Teorı́a de números p-ádicos ha despertado interés,
debido a sus aplicaciones en problemas, de fı́sica matemática, de big data, de crip-
tografı́a, de psicologı́a, y de otras ramas de las ciencias. Este desarrollo ha sido mo-
tivado principalmente por una idea fı́sica, la conjetura en partı́culas fı́sicas que en lon-
gitud de Planck (equivalente a 10−33 cm), el espacio-tiempo tiene una estructura no
Arquimediana. En la década de los ochenta, I. Volovich propuso utilizar los números
p-ádicos en lugar de los números reales, en los procesos que involucran mediciones
de distancias más pequeñas que la constante de Planck, dado que la distancia de
Planck es la menor distancia que puede ser medida utilizando el Axioma Arquimedi-
ano. Cuando sobre estos cuerpos p-ádicos se consideran curvas elı́pticas es posible
hacer criptografı́a, que se puede definir como el arte de cifrar y descifrar información,
utilizando técnicas matemáticas que hagan posible el intercambio de mensaje de man-
era tal que puedan ser leı́dos únicamente por las personas a quienes van dirigidos,
pues el objetivo de la criptografı́a es garantizar el secreto en la comunicación entre dos
entidades y asegurar que la información que se envı́a sea auténtica. En esta charla se
mostrará el uso de números p-ádicos en la criptografı́a.
Palabras clave: Números p-ádicos, curvas elı́pticas, criptografı́a.
CONTENIDO
1 Números p-ádicos
1.1 Valuaciones
• Todo número entero a, puede escribirse de la forma a = pvp(a)a ′ con p-primo fijo,
y p - a ′.
• Si x = ab ∈ Q→ x = pvp(x)
a ′
b ′ , con m.c.d(a
′, b ′) = 1 y tal que p - a ′, p - b ′.
• La valuación p-ádica, es la aplicación vp : Q→ Z ∪ {∞} tal que
1
1. vp(x) = +∞, si x = 0;
2. vp(xy) = vp(x) + vp(y);
3. vp(x+ y) > min{vp(x), vp(y)}.
Ejemplo 1.1
•
v3(18) = 2, dado que 3
2 · 2 = 18.
•
v2(1728) = 6, puesto que 2
6 · 27 = 1728.
•
v5
(
49
50
)
= v5(49) − v5(50) = 0− 2.
Ahora, definimos la norma p-ádica, | · |p : Q→ R+ como
|x|p =
{
p−vp(x) si x 6= 0
0 si x = 0
Una norma || · || es no Arquimediana, si para todo x, y ∈ Q satisface:
1. ||x|| > 0 ∧ ||x|| = 0⇐⇒ x = 0
2. ||xy|| = ||x|| ||y||
3. ||x+ y|| 6 max(||x||, ||y||)
La propiedad 3. es la desigualdad triangular fuerte, conocida como propiedad ultramétrica.
La norma | · |p es no Arquimediana.
Ejemplo 1.2
|9|3 = 3
−v3(9) = 3−2 =
1
9
,
|24|2 = 2
−v2(24) = 2−3 =
1
8
,∣∣∣∣1528
∣∣∣∣
7
= 7−v7(15)+v7(28) = 7.
¡Todo triángulo es Isósceles!
En efecto. Consideremos un triángulo de vértices x, y, z y dado que (x−y)+(y−z) = x−z,
entonces si ||x − y|| = ||y − z||, el triángulo ya es isósceles. Ahora si ||x − y|| 6= ||y − z||
entonces podemos escribir ||x− z|| = ||(x− y) + (y− z)|| y por la desigualdad triangular no
Arquimediana con ||x− y|| 6= ||y− z||, se obtiene||x− z|| = max(||x− y||, ||y− z||).
2
El cuerpo de los números p-ádicos Qp es la completación de Q con respecto a la norma
p-ádica | · |p. Todo número x ∈ Qp, x 6= 0 puede representarse de manera única como
x = pγ(x0+x1p+x2p
2+ · · · ), donde γ = γ(x) ∈ Z es la valuación de x y los xj son enteros
tales que x0 > 0 y 0 6 xj 6 p− 1, j = 0, 1, · · ·
Ejemplo 1.3
−1 = (p− 1) + (p− 1)p+ (p− 1)p2 + · · ·
En efecto, sea
x(n) :=(p− 1) + (p− 1)p+ · · ·+ (p− 1)pn
=(p− 1)
pn+1 − 1
p− 1
=pn+1 − 1.
Entonces lim
n→∞ x(n) = limn→∞pn+1 − 1 = −1, puesto que
|pn+1|p = p
−n−1.
1.2 Aritmética en Zp
Denotamos por Zp al anillo de enteros p-ádicos, y se define como:
Zp ={x ∈ Qp : |x|p 6 1}
={x ∈ Qp : x =
∞∑
k=k0
xkp
k, k0 > 0}.
El grupo de unidades del anillo Zp está dado por:
Z×p = {x ∈ Zp : |x|p = 1} = {x ∈ Zp : x =
∞∑
k=0
xkp
k, x0 6= 0}.
Dado que Zp es un anillo local, es decir es un dominio de ideales principales con único
ideal maximal, P = {x ∈ Qp : |x|p < 1} = Zp \Z×p = pZp. El cuerpo residual está dado por:
Zp/pZp ' Fp = Z/pZ, donde Fp es el cuerpo finito de p elementos.
Aśı:
pnZp = {x ∈ Qp : |x|p 6 pn, n ∈ N}
= {x ∈ Zp : x =
∑
k>n
xkp
k, n ∈ N}.
Todo elemento no nulo z de Zp, puede escribirse de manera única (salvo unidades) en la
forma z = pvp(z)u, donde u ∈ Z×p .
3
2 Criptografı́a
Criptograf́ıa significa, arte de la escritura secreta, por ello podemos decir que es la ciencia
que trata de la protección de la información frente a intrusos. si denotamos por la letra
P el problema y por la letra Sla solución, podremos afirmar que en criptograf́ıa:
• P : A quiere enviar un mensaje a B por un canal de comunicación inseguro.
• S : Transformar en forma controlada, el mensaje de tal forma que sea incomprensible
para un intruso.
Cifrar es transformar un texto plano en un texto ilegible que se denomina criptograma,
mientras que descifrar es recuperar el texto plano de un criptograma.
Un criptosistema es una qúıntupla (M,C,K, E,D), donde
• M: Textos planos, mensajes (alfabeto conocido).
• C: Criptogramas (alfabeto asociado).
• K: Conjunto de claves.
• E: Para cada clave k ∈ K, existe Ek algoritmo para cifrar.
• D: Para cada clave k ∈ K, existe Dk algoritmo para descifrar.
2.1 Tipos de Cifrados
Existen cifrados por transposición y por sustitución.
• Cifrados por transposición: Es un reordenamiento del mensaje (texto plano) usual-
mente siguiendo una figura geométrica plana, por ejemplo, cifrador ferrocarril:
EUARS-SNSJC-ETEMN-EETOE-SO, escribiendo en forma de zig-zag, encontramos
la frase: ESTO ES UN MENSAJE SECRETO.
• Cifrados por sustitución: Cada letra o bloques de letras del texto plano (mensaje),
son cambiados por la misma letra ( śımbolo) o bloques de letras en el texto del
cifrado. La sustitución puede ser de tipo, mono-gráfico, mono-alfabético, poli-
alfabético. Dentro de estos se encuentran, el cifrado de Julio César, el cifrado
por desplazamiento, el cifrador af́ın, entre otros. En el cifrado de Julio César, el
algoritmo de cifrado consiste en cambiar cada letra por la tercera siguiente del
alfabeto.
4
Ejemplo 2.1 : Cifrador Afı́n
Sean a = 2, b = 1. Dado que m.c.d.(a, 27) = 1 y b ∈ {0, 1, · · · , 26}, tenemos que:
Ek : Z27 → Z27
α → (aα+ b) (mod 27)
Dk : Z27 → Z27
β → a∗(β− b) (mod 27)
Mensaje numéricos: 19 4 2 18 4 20 15
Criptograma numérico: 12 9 5 10 9 14 4
Criptograma: M J F K J Ñ E
2.2 Tipos de Criptografı́a
• De clave secreta (criptosistema simétrico). Son aquellos que usan una única clave
para cifrar y descifrar los mensajes entre el emisor y el receptor. No son adecuados
para proteger la comunicación entre múltiples personas que probablemente no se
conozcan. Falta de criterios para evaluar su seguridad.
• De clave pública (criptosistema asimétrico). Son aquellos sistemas en los cuales el
emisor y el receptor poseen un par de claves: una será de tipo público y la otra de
tipo privado, y para enviar mensajes el emisor tiene que cifrar el mensaje con la
clave pública del receptor, para que aśı el receptor sea el único que pueda descifrar
el mensaje usando la clave privada.
En 1976, Whitfield Diffie y Martin Hellman introducen el concepto de criptograf́ıa
de clave pública y en 1978, Ronald Rivest, Adi Shamir y Leonard Adleman, pro-
pusieron el criptosistema RSA.
2.2.1 Criptosistema RSA
El criptosistema RSA se basa en la hipótesis de que para n y e enteros positivos dados,
donde n es el producto de dos primos grandes, la funciónm→ me (mod n) es de dirección
única.
Algoritmo RSA
• Construir un entero n = pq, donde p y q son dos primos grandes.
• Calcular φ(n) = (p− 1)(q− 1).
• Elegir un entero e, tal que 1 < e < φ(n) y m.c.d.(e,φ(n)) = 1
• Calcular d, el inverso multiplicativo de e módulo φ(n), es decir 1 < d < φ(n) y
ed ≡ 1(mod φ(n)).
5
• El par (n, e) constituye la clave pública para el usuario y d es su clave privada.
• n recibe el nombre de módulo, e es el exponentede encriptación y d es el exponente
de des-encriptación.
• Para enviar un mensaje a este usuario, solo hay que conocer su clave pública (n, e).
Si el texto claro es m, donde m < n, éste se encripta calculando c = me (mod n).
• El usuario descifra el mensaje haciendo uso de su clave privada calculando cd =
m (mod n).
Ejemplo: 2.2.1
Sean p = 61, q = 53 entonces n = 61 · 53 = 3233.
• φ(n) = 60 · 52 = 3120.
• Sea e = 17 tal que m.c.d.(17, 3120) = 1.
• 0 < d < 3120 tal que 17d ≡ 1 (mod 3120).
• d = 2753, puesto que 17d = 17 · 2753 = 46801 ≡ 1(mod 3120).
• Sim = 64 entonces el texto encriptado es c = 1577, puesto que 6417 ≡ 1577(mod 3233).
• Para descrifrar c calculamos 15772753 (mod 3233) y obtenemos m = 64.
En 1985, Neal Koblitz y Vı́ctor Miller, propusieron la criptograf́ıa con curvas eĺıpticas
(ECC), cuya seguridad computacional se basa en el problema del logaritmo discreto. Sea
(G, ·) un grupo multiplicativo, a ∈ G un elemento de orden n y b ∈ 〈a〉. El problema del
logaritmo discreto consiste en encontrar 0 6 k 6 n− 1 tal que ak = b, aśı k = loga b.
Trabajar con curvas eĺıpticas permite el uso de claves más pequeñas y garantiza el nivel
de seguridad que se traduce en ahorro de banda en las redes de comunicación, consumo
de memoria, tiempo y capacidad de procesador.
6
3 Curvas Elı́pticas
Sea K un cuerpo. El plano proyectivo P2 se define como el conjunto formado por todas
las clases de equivalencia de ternas (x, y, z) con x, y, z ∈ K, donde al menos uno de ellos
x, y ó z es no nulo.
Sea K la clausura algebraica fija de un cuerpo K. Una curva eĺıptica C sobre K es una
curva proyectiva plana C ⊂ P2(K) no singular definida por una ecuación de la forma
y2z+ a1xyz+ a3yz
2 = x3 + a2x
2z+ a4xz
2 + a6z
3,
donde a1, a2, a3, a4, a6 ∈ K.
El conjunto de puntos de C que satisfacen la ecuación y2+a1xy+a3y = x3+a2x2+a4x+a6,
más un punto del infinito O se denota por C(K), y es un grupo abeliano generado por un
número finito de puntos racionales.
3.1 Criptografı́a y curvas elı́pticas
La criptograf́ıa con curvas eĺıpticas es una variante de la criptograf́ıa de clave pública
basada en las propiedades matemáticas de las curvas eĺıpticas propuestas por Koblitz
y Miller en 1985, y son importantes porque usa claves más pequeñas que los métodos
tradicionales como el RSA, con un nivel de seguridad equivalente al RSA. El objetivo es
encontrar un subgrupo finito del grupo de puntos racionales de la curva C definida sobre
Qp en el cual se pueda trabajar como en el cuerpo finito Fp.
Dados los puntos P,Q ∈ E(K) y k ∈ Z, se define la ecuación Q = [k]P, donde la notación
[k]P significa sumar k veces P. El problema del algoritmo discreto para curvas eĺıpticas
consiste precisamente en hallar el valor de k.
Considerando las curvas eĺıpticas definidas sobre Qp, usando su grupo formal (serie de po-
tencias), y la reducción de curvas, es posible determinar el grupo cociente C(Qp)/Ĉ(pZpn),
llamado el grupo criptográfico en el que se puede hacer criptograf́ıa como en Fp, donde Ĉ,
corresponde al grupo formal asociado a C. Aśı: Ĉ(Zp) = {P(x, y) ∈ C : vp(x) < 0}∪ {OC} ⊂
C(Qp) y Zpn = {z ∈ Zp : vp(z) > n}.
Sabemos que los representante del grupo cociente C(Qp)/Ĉ(pZpn), son elementos de
C(Qp) y las coordenadas de estos puntos pertenecen a Qp, y la mayoŕıa de elementos de
Qp no podŕıan ser almacenados en un computador real, por lo tanto se aproximan las
coordenadas usando la representación en series de potencias de los elementos de Qp.
7
References
[1] ALBEVERIO S.A., KHRENNIKOV YU. AND SHELKOVICH V. M., Theory of p-adic,
Dsitributions Linear and Nonlinear Models, London Mathematical Society, Lecture
notes Series 370, Cambridge New York, 2010.
[2] BACHMAN GEORGE., Introduction to p-adic Numbers and Valuation Theory, Aca-
demic Press, N.Y., 1964.
[3] KOBLITZ NEAL, p-adic Numbers, p-adic Analysis and Zeta Fucntions, Springer-
Verlag, New York, 1997.
[4] KOBLITZ NEAL, Algebraic aspects of cryptography, Springer-Verlag, 1998.
[5] BLAKE I., SEROUSII G., SMART N., Elliptic Curves: Number Theory and criptogra-
phy, Cambridge University Press, 2000.
8