Usuario:Óscar Baños Campos/Taller

TEMA 1. FUNDAMENTOS:

Funciones: Funciones Hash y su uso en la criptografía.

Definición de función Hash

Una función Hash comúnmente denotada H, es una función para la cual un elemento de un conjunto se proyecta sobre otro conjunto asegurando que para el elemento del primer conjunto le corresponde un único elemento del conjunto imagen, en cambio a los elementos del conjunto imagen les pueden o no corresponder uno, varios o incluso ningún elemento del primer elemento.

Cuando a un elemento del conjunto imagen le corresponden múltiples elementos del conjunto generador al cual se le aplica la función se dice que existen colisiones.

$f:A\rightarrow B$

$h(x)\rightarrow y$

(Siendo x comúnmente llamada llave e y clave)

Uso de las funciones Hash en criptografía

El uso principal de las funciones hash en la criptografía es un tipo de funciones conocidas como SHA las cuales presentan no reflexividad y un número nulo de colisiones o computacionalmente imposible de hallarlas, es decir, dada una clave es prácticamente imposible intentar hallar una llave o grupo de llaves que la verifique, esto es importante pues para un usuario con una llave pública y otra privada se pueden crear funciones Hash multiparámetro que permitan obtener a partir de una cadena de bits o texto un resultado numérico conocido como Hash Seguro.

Estas funciones permiten un encadenamiento de datos que facilita crear cadenas de bloques conocida como BlockChain (o cadena de bloques) el cual se utiliza como sistema base para que las criptomonedas se puedan utilizar de forma fiable como método de pago.

La característica principal de dichas funciones Hash es que una vez obtenida la clave a través de la llave privada y una cadena de texto el resto de usuarios de la criptomoneda podrán comprobar si se verifica dicha información con una llave publica que únicamente sirve como comprobador de que un usuario de la criptomoneda emitió el recibo.

Siendo sLL llave secreta o privada y pLL llave pública se puede crear una firma digital de un usuario en cuestión para los textos cifrados.

$Hash(cadena,sLL)=clave$

$verificacion(cadena,clave,pLL)=Verdadero/Falso$

La primera permite a un usuario crear una firma digital para verificar que un mensaje dentro de una transacción ha sido emitida por él mismo y la segunda permite que el receptor verifique que el emisor fue el autor original de dicha transacción.

Esta firma digital permite crear un sistema de confianza el cual se basa en que si ningún otro usuario conoce tu llave secreta, nadie podrá ser capaz de falsificar una transacción realizada a tu nombre. La importancia radica en que la firma digital varia con cada mensaje, es decir que para cada transacción de una criptomoneda se tendría que crear una nueva clave de la cual solo el usuario original conoce la llave secreta, debido a que el SHA de mayor uso extendido es de 256 bits (bitcoin lo utiliza aunque algunas otras criptomonedas utilizan el 512 bits para seguridad añadida) eso deja una posibilidad de 1 entre $2^{256}$ posibles combinaciones.

Este número es lo suficientemente grande como para evitar que se pueda buscar una llave probando combinaciones y asegurar que la probabilidad de colisión sea tan baja que resulte inviable encontrar un brecha, cabe mencionar que a día de hoy sigue sin haberse encontrado una brecha o colisión que provoque una vulnerabilidad al sistema. pero si se llegó a encontrar en SHA menores como el de 160 bits o 128.

Números primos y Teorema de Dirichlet

El teorema de Dirichlet sobre progresiones aritméticas es un resultado de la teoría analítica de números demostrado por el matemático Dirichlet. Este teorema sobre la distribución de los números primos en $\mathbb {N}$, fue conjeturado por Gauss y finalmente demostrado en 1837 por Dirichlet, nombre por el que actualmente se le conoce.

Enunciado

Sea $a,\,d\in \mathbb {N}$ tal que el máximo común divisor $\operatorname {mcd} (a,d)=1$, entonces la progresión aritmética $a_{n}=a+n\cdot d$ contiene infinitos números primos. Dirichlet

Esto quiere decir que los números a+nd forman una progresión aritmética

$a,\ a+d,\ a+2d,\ a+3d,\ \dots ,\$

en la que hay infinitos números primos, o dicho de otra manera, hay infinitos números primos congruentes con a módulo d.

Por ejemplo, el teorema asegura que hay una cantidad infinita de números primos que terminen en 7, ya que los números que terminan en 7 forman una progresión aritmética (7, 17, 27, 37, ...) es decir, es una sucesión de números de la forma a+nd con a=7 y d=10, siendo estos primos entre sí, luego su máximo común divisor es 1.

Enunciado extendido

El enunciado anterior esta formulado para la base decimal o base 10 pero se puede extender a diferentes bases.

$Sea\,a,b\in \mathbb {N} \,\,\,\,b\,una\,base\,numerica,\,mcd(a,b)=1$

Siempre que a sea $a\in {2,3,...,(b-1)}$ es decir, a está comprendida entre el menor número primo, 2, y el número menor inmediato a la base, obtendremos distintas clases de congruencias en dicha base.

Es decir, aquellos número coprimos con la base b serán válidos para verificar que $a_{n}=a+n*b$ ,solo es necesario comprobar con las primeras clases pues, tomando el ejemplo de la base 10

$mcd(7,10)=1$ podemos afirmar que en la sucesión 17, 27, 37... habrá números primos, al igual con la sucesión de la clase del 1,3 y 9 pero sería redundante aplicarlo a la clase del 17 que esta contenida a su vez en la del 7.

De aquí se puede deducir aplicando la función $\phi$ de Euler para la base b, habrá 'd' distintas clases de equivalencias.

En la base decimal

$\phi (10)=4$ clases de equivalencia distintas que son 1,3,7,9 es decir, todos los números acabados en esas cifras o que sean pertenecientes a su clase de equivalencia podrán ser números primos.

Esto se debe a que la función de Euler se puede utilizar para calcular la cantidad de número coprimos a un número dado, en el caso del 10 son 4 número coprimos.

Para ilustrar el teorema extendido a bases numéricas diferentes tomemos el ejemplo de la base 10 o decimal.

cuando hacemos una tabla que contiene a los números naturales nos fijamos

que solo los número acabados en 1, 3, 7 o 9 pueden ser número primos (a excepción del 2 y 5) pues todos los demás que acaben en cifra par o 5 serán múltiplos de estos números

Esto es fácilmente visualizable pues el 10 esta compuesto por 2 y 5; $10=2*5$

0 mod 10	0	10	20	30	40	50	60	70	80	90
1 mod 10	1	11	21	31	41	51	61	71	81	91
2 mod 10	2	12	22	32	42	52	62	72	82	92
3 mod 10	3	13	23	33	43	53	63	73	83	93
4 mod 10	4	14	24	34	44	54	64	74	84	94
5 mod 10	5	15	25	35	45	55	65	75	85	95
6 mod 10	6	16	26	36	46	56	66	76	86	96
7 mod 10	7	17	27	37	47	57	67	77	87	97
8 mod 10	8	18	28	38	48	58	68	78	88	98
9 mod 10	9	19	29	39	49	59	69	79	89	99

En este caso tenemos 4 clases de equivalencias que se corresponden al residuos 1, 3, 7, 9 congruentes con módulo 10

$X\equiv 1(mod10)$

$X\equiv 3(mod10)$

$X\equiv 7(mod10)$

$X\equiv 9(mod10)$

Cualquier X que verifique dicha congruencia podrá ser número primo, es decir, si un número no cumple con lo anterior podemos afirmar que es imposible que sea número primo.

Una conclusión que se puede extraer es que para todas las clases tendrán un número aproximado de primos, es decir, que dado un número primo aleatorio las probabilidades de que pertenezca a una clase o a otra son las mismas por tanto si fuésemos añadiendo números primos sucesivos observaríamos que se distribuyen equitativamente entre la clase del 1, 3, 7, 9 para la base 10 y esto se puede aplicar a cualquier base distinta.

De aquí se puede concluir que las distribuciones de números primos suelen tener un aspecto uniforme esto es fácilmente observable en distintas representaciones gráficas en las cuales los números primos tienen a formar grupos pero no es resultado de una propiedad de los números primos sino que a la hora de obtener diferentes clases de equivalencia los número primos se agrupan en las clases que son coprimas con la base en la cual se representa.

Demostración

La demostración del teorema utiliza las propiedades de ciertas funciones multiplicativas (conocidas como funciones-L de Dirichlet) y varios resultados sobre aritmética de números complejos y es suficientemente compleja como para que algunos textos clásicos de teoría de números decidan excluirla de su repertorio de demostraciones.​

Véase también

• Principio del palomar

Enlaces externos

• Wikiversidad alberga proyectos de aprendizaje sobre Óscar Baños Campos/Taller.
• Weisstein, Eric W. «Dirichlet's theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Hazewinkel, Michiel, ed. (2001), «Dirichlet_theorem&oldid=33719», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 .

Bibliografia

Tema 1. Paginas web o existentes en la propia wiki:

Enlaces de video de youtube:

https://www.youtube.com/watch?v=bBC-nXj3Ng4

https://www.youtube.com/watch?v=S9JGmA5_unY

Tema 2.

Teoria de numeros:

https://www.youtube.com/watch?v=EK32jo7i5LQ

http://www.scielo.org.co/pdf/rein/v35n2/0120-419X-rein-35-02-00163.pdf