Me gustaría escuchar sus opiniones sobre un problema de modelado matemático del diseño de contraseñas.
La criptografía de clave pública, también conocida como criptografía de doble clave y criptografía asimétrica, fue propuesta por Lucas y Hellman en su artículo "Nuevas direcciones en criptografía" en 1976. Consulte la literatura que marcó época:
W.Diffie y M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, noviembre de 1976, PP.644-654
Unidireccional trampilla Una función es una función f que satisface las siguientes condiciones:
(1) Dado x, es fácil calcular y=f(x);
(2) Dado y, es fácil calcular x. Hacer y=f(x) es difícil.
(La llamada dificultad para calcular x=f-1(Y) significa que el cálculo es bastante complicado y no tiene significado práctico).
(3) Existe δ y cuando se conoce δ, para cualquier y dada, si existe la x correspondiente, es fácil calcular x tal que y=f(x).
Nota: 1*. Una función que solo satisface (1) y (2) se denomina función unidireccional; el elemento (3) se denomina propiedad de trampilla y δ se denomina información de trampilla.
2* Cuando se utiliza la función de trampilla f como función de cifrado, f se puede hacer pública, lo que equivale a hacer pública la clave de cifrado. En este momento, la clave de cifrado se denomina clave pública y se indica como Pk. El diseñador de la función f mantiene δ en secreto y la utiliza como clave de descifrado. En este momento, δ se denomina clave secreta, denotada como Sk. Dado que la función de cifrado es pública, cualquiera puede cifrar la información Out x=f-1(y).
3*. La propiedad (2) de la función de trampilla unidireccional muestra que es inviable para el espía inferir x a partir del texto cifrado interceptado y=f(x).
En su histórico artículo, Diffie y Hellman dieron la idea de los cifrados, pero no dieron ningún ejemplo real de cifrados de clave pública, ni fueron capaces de encontrar una función unidireccional de trampilla real. Sin embargo, dieron un ejemplo de función unidireccional y en base a ello propusieron el algoritmo de intercambio de claves Diffie-Hellman. Este algoritmo se basa en la dificultad de calcular logaritmos discretos en campos finitos: Sea F un campo finito, g∈F es el grupo multiplicativo de F*=F\{0}=
Descripción del protocolo de intercambio de claves Diffie-Hellman: Alice y Bob han negociado un número primo grande p y un entero grande g, 1
Cuando Alice y Bob quieran comunicarse confidencialmente, pueden hacerlo de la siguiente manera:
(1) Alice envía un número aleatorio grande x y calcula
X =gx(mod P)
(2)Bob selecciona un número aleatorio grande x? y calcula que Alice envía X a Bob; Bob envía X?
(4) Alice calcula K=(X ?)X(mod P); Bob calcula K ? =(X) (mod P).
Se sabe por (4) que Alice y Bob han obtenido el mismo valor secreto K. Ambas partes utilizan K como clave de cifrado y descifrado para realizar comunicaciones confidenciales utilizando algoritmos de clave simétrica tradicionales.
Nota: El algoritmo de intercambio de claves Diffie-Hellman tiene patentes en Estados Unidos y Canadá.
3 Algoritmo de clave pública RSA
El algoritmo de clave pública RSA fue propuesto por Rivest, Shamir y Adleman en 1978 (ver Comunicaciones de la ACM. Vol.21.No.2. Feb. 1978, PP.120-126) La base matemática de este algoritmo es el teorema de Euler en la teoría de números elemental y se basa en la dificultad de los factores enteros grandes.
Representa Z/(n) como Zn, donde n=pq; p y q son números primos y diferentes. Si
Z*n?{g∈ Zn|(g,n)=1}, es fácil ver que Z*n es un grupo multiplicativo de orden (n), y existe g? ? (n)?1 (mod n), y ? (n)=(p-1)(q-1).
El criptosistema RSA se describe a continuación:
Primero, el espacio de texto plano P = espacio de texto cifrado C=Zn (ver P175).
Generación de claves
Seleccione p, q, p, q como números primos mutuamente diferentes. y calcule n=p*q, ? (n)=(p-1)(q-1), elija el número entero e para que (? (n),e)=1,1 Tenga en cuenta que cuando 0 MK? (n)+1?M(mod n) ), y ed ? 1 (mod ? (n)), fácil de ver (Me)d ? M (mod n) B. Cifrar (use e, n) texto sin formato: M < n cifrado. texto: C=Me(mod n). C Decrypt (use d, p, q) Texto cifrado: C Texto sin formato: M=Cd (mod n) Nota: 1*, el cifrado y el descifrado son un par de operaciones inversas. 2*, para 0 Hay M? (q) = 1+kq. M =cpSí ¿Existe M? (q)+1=M+kcpq=M+kcnEntonces ¿Existe M (q)+1? > Ejemplo: Si Bob elige p=101 y q=113, entonces n=11413, ? (n)=100×112=11200; sin embargo, 11200=26×52×7, se puede usar un entero positivo e como Exponente cifrado, si y solo si e no es divisible por 2, 5 o 7 (de hecho, Bob no sabe cómo descomponer φ (n) y usa la división euclidiana (algoritmo europeo) para encontrar e, de modo que (e , φ( n)=1). Supongamos que Bob elige e=3533, entonces se utilizará el método de división euclidiana para obtener: d=e -1 ? d= 6597. Bob expone n=11413 y e=3533 en un directorio. Ahora supongamos que Alice quiere enviar el texto sin formato 9726 a Bob. Calcula: 97263533(mod 11413). =5761 Y cuando Bob recibe el texto cifrado 5761 en un canal, utiliza su índice de descifrado secreto (clave privada) d=6597 para descifrar: 57616597 (mod 11413)=9726. Nota: La seguridad de RSA se basa en el hecho de que la función de cifrado ek (x) = xe (mod n) es una función unidireccional, por lo que el cálculo inverso no es factible para las personas, pero Bob puede descifrarlo. se descompone n=pq, ¿sabemos? (n)=(p-1)(q-1). Así, el descifrado de la clave privada d se resuelve utilizando el algoritmo euclidiano. 4 Implementación del criptosistema RSA Los pasos para la implementación son los siguientes: Bob es el implementador (1 )Bob encuentra dos números primos grandes p y q (2)Bob calcula n=pq y ? (n)=(p-1)(q-1). (3)Bob elige un número aleatorio e(0 (4)Bob usa la división euclidiana método para calcular d= e-1(mod ? (n)) (5)Bob expone n y e como su clave pública en el directorio. El punto clave para que los criptoanalistas ataquen el sistema RSA es cómo descomponer n. Si la solución es exitosa para que n=pq, podemos calcular φ(n)=(p-1)(q-1), y luego usar la e abierta para resolver a partir del secreto d. (Conjetura: romper RSA equivale a descomponer n como un polinomio . ¡¡¡Sin embargo, hasta ahora no se ha proporcionado ninguna prueba creíble para esta conjetura!!!) Entonces, el requisito es: si RSA Safe, p y q deben ser números primos lo suficientemente grandes como para que el analista no pueda descomponer n en tiempo polinómico. Se recomienda elegir pyq son números primos decimales con aproximadamente 100 dígitos. Se requiere que la longitud del módulo n sea de al menos 512 bits. El algoritmo RSA utilizado por el estándar de ataque EDI estipula que la longitud de n está entre 512 y 1024 bits, pero debe ser múltiplo de 128. El estándar internacional de firma digital ISO/IEC 9796 estipula que la longitud de n es de 512 bits. Para resistir los algoritmos de descomposición de enteros existentes, los factores primos del módulo RSA n también tienen los siguientes requisitos: p y q: (1) |p-q |Muy grande, normalmente p y q tienen la misma longitud; (2)p-1 y q-1 contienen factores primos grandes p1 y q1 respectivamente (3) P1-1 y q1-1 contienen factores primos grandes p2 y q2 respectivamente (4)p+1 y q+1 contienen factores primos grandes p3 y q3 respectivamente Para Para mejorar la velocidad de cifrado, generalmente tome e como un número entero pequeño específico. Por ejemplo, el estándar internacional EDI estipula que e = 216 + 1, e ISO / IEC9796 incluso permite e = 3. En este momento, la velocidad de cifrado es generalmente más de 10 veces más rápida que la velocidad de descifrado. Estudiemos las operaciones aritméticas de cifrado y descifrado. Esta operación es principalmente la operación de exponenciación módulo n. El famoso método de "multiplicación de suma cuadrada" reduce el número de multiplicaciones modulares necesarias para calcular xc(mod n) a como máximo 2l, donde l es el número de bits en la representación binaria del exponente c. Si n está representado por k bits en forma binaria, es decir, k = [log2n] +1. Dado que l≤k, xc(mod n) se puede completar en tiempo o(k3). (Tenga en cuenta que no es difícil ver que la multiplicación se puede completar en un tiempo o(k2).) Algoritmo de multiplicación de suma cuadrada: El exponente c en forma binaria es : c= Xc=xc0×(x2)c1×…×(x2t-1)ct-1 Precálculo: x2=xx x4=x22=x2x2 . . . x2t-1 =x2t-2 *x2t-2 Cálculo de Xc: multiplica todos los x2i correspondientes a ci=1 para obtener xc. Para t-1 se utilizaron multiplicaciones más. Consulte la página 177 del libro para conocer el programa de algoritmo de cálculo xc(mod n): A=xc c=cc12+..+ct-12t-1= [ct-1,....,c1,c0]2 5 Esquema de firma RSA Concepto básico de firma Firma tradicional (firma manuscrita) Características: (1) Una firma es la parte física del documento firmado. (2) Verificar la parte física para compararla y lograr el propósito de confirmación. (Fácil de falsificar) (3) ¡¡¡No es fácil de “copiar” fielmente!!! Definición: (Esquema de firma digital) Un esquema de firma tiene un algoritmo de firma y verificación El algoritmo de prueba consta de dos partes. Puede ser grabado por el grupo de relación de cinco elementos (P, A, K, S, V): (1) P es un conjunto finito compuesto por todos los mensajes posibles (mensajes); (2)A es un conjunto finito de todas las firmas posibles; (3)k es un espacio de claves finito, que es un conjunto finito de claves posibles; (4) Para cualquier k ∈ K, existe un algoritmo de firma Sigk ∈ S y un algoritmo de verificación correspondiente Verk∈V para cada Sigk:p A y Verk:P×A {verdadero, falso}. , se cumplen las condiciones: Cualquier x∈P,y∈A Hay una firma del esquema de firma: Ver(x,y)= { Nota: 1*. las funciones Sigk y Verk son funciones de tiempo polinómicas. 2*.Verk es una función pública, mientras que Sigk es una función secreta. 3* Si una mala persona (como Oscar) quiere falsificar la firma de Bob para X, es computacionalmente imposible. Es decir, dado x, solo Bob puede calcular la firma y tal que Verk(x,y)=true. 4*. Un esquema de firma no puede ser incondicionalmente seguro. Con el tiempo suficiente, Oscar siempre puede falsificar la firma de Bob. Firma RSA: n=pq,P=A=Zn, define el conjunto de claves K={(n,e,p,q,d)}|n=pq,d*e?1( mod ?(n))} Nota: n y e son claves públicas; p, q, d son confidenciales (claves privadas). Para x∈P, Bob quiere firmar x, tome k∈K. Sigk(x)? xd(mod n)?y(mod n) Entonces Verk(x,y)=true x?ye(mod n) (Nota: e, n son públicos; ¡¡se puede verificar públicamente si la firma (x, y) es correcta o no!! Es decir, si es la firma de Bob) Nota: 1 *. Cualquiera puede verificar Una determinada firma y calcula x = ek (y) para falsificar la firma de Bob en el mensaje aleatorio x. 2*. Problema de transmisión cifrada de mensajes firmados: Supongamos que Alice quiere cifrar el mensaje firmado y enviárselo a Bob. Procede de la siguiente manera: para el texto sin formato x, Alice calcula la firma de x, y =. SigAlice (x), y luego usa la función de cifrado pública eBob de Bob para calcular Z = eBob (x, y), Alice le pasa Z a Bob y, después de que Bob recibe Z, lo descifra en el primer paso. , dBob(Z)=dBobeBob(x,y)=(x,y) Entonces verifica VerAlice(x,y)=True p> Pregunta: Si Alice primero cifra el mensaje x y luego lo firma, ¿cuál es el resultado ? Y=SigAlice(eBob(x)) Alice pasa (z, y) a Bob primero descifra z y obtiene x luego usa VerAlice para verificar la información sobre x; Firma cifrada y. Un problema potencial con este método es que si Oscar obtiene el par (z, y), puede reemplazar la firma de Alice con su propia firma y ?=SigOscar(eBob(x)) (Nota: Oscar puede firmar el texto cifrado eBob(x), incluso si no conoce el texto sin formato x. Oscar transmite (z, y?) a Bob, Bob puede inferir ese problema logarítmico de texto plano. Supongamos que P es un número primo decimal de al menos 150 dígitos y p-1 tiene un factor primo grande. Zp es un cuerpo finito, Si α es el elemento primitivo en Zp, existe Zp* =<α>. Si β∈Zp*=Zp\{0}, Cómo calcular un entero único a, (requisito, 0≤a≤ p-2), satisfaciendo αa= β (mod p) Registrar a como a=logαβ En términos generales, resolver a es computacionalmente intratable. Descripción del sistema de clave pública Egamal en Zp*: Supongamos que el espacio de texto plano es P=Zp*, el espacio de texto cifrado es C=Zp*×Zp* y la clave está definida Espacio K={ (p, α,a, β)|β=αa(mod p)} La clave pública es: p, α,β Clave secreta (clave privada): a Alice toma un número aleatorio secreto k∈ Zp-1 y cifra el texto plano x ek(x,k)=(y1,y2) Entre ellos, y1=αk(mod p),y2=xβk(mod p) Bob descifra, dk(y1,y2)=y2(y1α)-1( mod p ) Nota: 1*. ¡¡Fácil de verificar y2(y1α)-1=x(αa)k(αka)-1=x!! 2*. El algoritmo de cifrado puede proporcionar un esquema de firma basado en esto: Alice quiere firmar el texto plano x, primero toma un número aleatorio secreto k como firma Sigk(x,k)=(? , ? ) Donde ?=αk(mod p), ?=(x-a? )k-1(mod p-1) Para x, ?∈Zp* y ? ∈ Zp-1, definir Verk(x, ?,?)=True es equivalente a β?α?=αx(mod p) Cabe señalar que si esta firma se construye correctamente, entonces la verificación será exitosa porque β?α? = αa? αk? αa?+k? (mod p) De lo anterior, se puede deducir ?= (x- a?)k-1 (mod p-1) k? x- a?(mod p-1) tiene a?+k?x(mod p) Entonces β ?= αx (mod p) Este esquema de firma ha sido El El NIST (Instituto Nacional de Estándares y Tecnología) de EE. UU. lo determinó como estándar de firma (1985). Para contenido RSA, visite: www.RSAsecurity.com