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

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

el numero 10 presenta una factorización en dos números primos $10=2^{1}*5^{1}$ es decir, 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

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)$

Estas 4 clases de equivalencias en base 10 se obtienen aplicando la función $\phi$ de Euler obteniendo el número de coprimos de un número dado que representa las clases de equivalencias totales

en las que se pueden distribuir los número primos en: $\phi (N)=a$ a posibles clases de equivalencias.

Retomando el enunciado primero, tenemos que los número primos se distribuyen equitativamente entre todas las clases de equivalencias para cualquier n-base dada, es decir en la base 10 habrá aproximadamente tantos primos acabados en 7 como acabados en 3, 9 o 1.

Esto se aplica al enunciado del teorema pues las sucesiones que tengan como estructura

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