Me gustaría conocer un problema de modelado matemático en el diseño de contraseñas.
W.Diffie y M.E.Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory, IT-22. No. 6, noviembre de 1976, págs. 644-654
Una función de trampilla unidireccional es una función f que satisface las siguientes condiciones:
(1) Dado x, es fácil Calcular y = f(x);
(2) Dado y, es difícil calcular x tal que y=f(x).
(La llamada dificultad de cálculo x=f-1(Y) significa que el cálculo es bastante complicado y no tiene significado práctico).
(3) Cuando δ existe, es fácil calcular X tal que y=f(x) para cualquier Y dado, si existe el X correspondiente.
Nota: 1*. Sólo (1) y (2) se denominan funciones unidireccionales; el elemento (3) se denomina propiedad de trampilla y δ se denomina información de trampilla.
2* Cuando la función trampilla f se utiliza como función de cifrado, 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 lo utiliza como clave de descifrado. En este momento, δ se llama clave y se denota como Sk. Debido a que la función de cifrado es pública, cualquiera puede cifrar la información x en y=f(x) y enviarla al diseñador de la función (por supuesto, también se puede transmitir a través de un canal no seguro, ya que el diseñador es propietario de Sk, puede hacerlo); resuélvelo naturalmente 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).
Diffie y Hellman dieron la idea de la criptografía en su histórico artículo, pero no dieron un ejemplo real de criptografía de clave pública, ni encontraron una verdadera función unidireccional. Pero dieron un ejemplo de función unidireccional y, basándose en ello, propusieron el algoritmo de intercambio de claves Diffie-Hellman. Este algoritmo se basa en la dificultad de calcular logaritmos discretos sobre campos finitos: Sea F un campo finito y g∈F sea f * = f \{0} =
Descripción del protocolo de intercambio de claves Diffie-Hellman : Alice y Bob negocian un número primo grande P y un entero grande G, 1
Cuando Alice y Bob quieren comunicarse en privado, pueden hacerlo de la siguiente manera:
(1) Alice Envía un número aleatorio grande X y calcúlalo.
X=gx (módulo P)
(2) ¿Bob elige un número aleatorio grande x? y calcular x? =gx? (Ministerio de Defensa)
(3) Alice envía X a Bob;; ¿Bob x? Envíelo a Alice
(4) Alice calcula K=(X?)X(mod P); =(X)X? (mod P), es fácil de ver, ¿K=K? =gxx? (Ministerio de Defensa).
Según (4), Alice y Bob obtienen el mismo valor secreto K. Ambas partes utilizan K como clave de cifrado y descifrado y utilizan algoritmos de clave simétrica tradicionales para una comunicación segura.
Nota: El algoritmo de intercambio de claves Diffie-Hellman está patentado 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. Volumen 265438 + 0. No. 2. Febrero de 1978, págs. 120-126).
Z/(n) se expresa como Zn, donde n = pqp yq son números primos y son diferentes. Si
Z*n? {g∈ Zn|(g, n)=1}, ¿es fácil ver que Z*n es? (n) grupo factorial con g? (norte)? 1(mod n), ¿mientras? (n)=(p-1)(q-1).
El criptosistema RSA se describe a continuación:
Primero, espacio de texto plano p = espacio de texto cifrado C=Zn. (Ver P175).
A. Generación de claves
Seleccione p, q, p, q como números primos diferentes entre sí y calcule n=p*q,? (n)=(p-1)(q-1), elija el número entero e tal que (? (n), e) = 1, 1 & lt; (n)), calcule d tal que d=e-1(mod?(n)), clave pública Pk={e, n};
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 (e, n) texto sin formato: m
C. (use d, p, q)
Texto cifrado: c Texto sin formato: M=Cd(mod n)
Nota: 1* es un par de operaciones inversas en cifrado y descifrado.
2*, para 0 < M & lt cuando n, si (M, n) ≠ 1, entonces M es un múltiplo entero de p o q, asumiendo M=cp, de (cp, q) = 1, entonces hay M? (q)? 1(mód q)M? (q)? (pag)? 1 (tipo Q)
¿Hay m? (q)= 1+kq; M=cp La multiplicación en ambos lados es la misma.
¿Hay una m? (q)+1 = m+kcpq = m+kcnEntonces
¿Hay m? (q)+1? m (Moderno)
Ejemplo: Si Bob elige p=101, Q = 113, entonces n=11413. (n) = 100×112 = 11200; pero 11200 = 26× 52× 7, un entero positivo E puede usarse como índice de cifrado si y sólo si E no es divisible por 2, 5 o 7 (de hecho, Bob no descompondrá φ(n), utilizará el método de división (algoritmo euclidiano) para encontrar E tal que (E, φ (n) = Supongamos que Bob elige e=3533, luego, dividiendo por giros y vueltas, obtendrá :
d=e -1 ? 6597 (mod 11200), entonces la clave de descifrado de Bob d=6597
Bob publica n=11413 y e=3533 en un directorio. Alice quiere enviar el texto sin formato 9726 a Bob Calcular:
97263533(mod 11413) = 5761
Y enviar el texto cifrado 5761 en un canal. Cuando Bob recibe el texto cifrado 5761, usa el suyo. secreto para descifrar el índice (clave privada) )D = 6597:57616597(mod 11413)= 9726 descifrado
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 no es factible que las personas inviertan. La trampa que Bob puede descifrar es descomponer n = pq, ¿de acuerdo? 1). Por lo tanto, el descifrado de la clave privada d se realiza mediante una solución de algoritmo euclidiano.
4 Implementación del criptosistema RSA
Los pasos de implementación son los siguientes: Bob es el implementador. /p>
(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 uno. Número aleatorio e (0
(4)Bob calcula d=e-1(mod?(n))
La clave para que los criptoanalistas ataquen el sistema RSA es cómo descomponer n.
Si la solución. tiene éxito, de modo que n = pq, luego φ (n) = (P -1) (Q-1), y luego lo calcula el público
Abre e, descifra d (Adivina: crack RSA, descomponer n es un polinomio.
Equivalente a. Sin embargo, esta conjetura aún no se ha proporcionado ninguna prueba creíble)
Entonces, para que RSA sea seguro, P y Q deben ser lo suficientemente grandes.
El analista no tiene otra opción. Descomponga n en tiempo polinómico. Las opciones recomendadas para p y q son números primos decimales alrededor de 100. Se requiere que la longitud del módulo n sea de al menos 512 bits según lo utilizado por el EDI. estándar de ataque. El algoritmo estipula que la longitud de n es de 512 a 1024 bits, pero debe ser un 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, se analizan los factores primos del módulo n RSA
p y q también tienen los siguientes requisitos:
(1 )| p-q| es muy grande, normalmente p y q tienen la misma longitud;
(2)p-1 y q-1 contienen macrofactores p1 y q1 respectivamente.
(3)P1-1 y q1-1 contienen macrofactores p2 y q2 respectivamente.
(4)p+1 y q+1 contienen macrofactores p3 y q3 respectivamente.
Para mejorar la velocidad de cifrado, e generalmente se toma como un entero pequeño específico, como e = 216+1 en el estándar internacional EDI, e ISO/IEC9796 incluso permite e = 3. En este momento, la velocidad de cifrado es generalmente 10 veces más rápida que la velocidad de descifrado. A continuación, estudiamos las operaciones aritméticas de cifrado y descifrado, principalmente la operación de exponenciación módulo n. El famoso método de "multiplicación por suma de cuadrados" reduce el número de multiplicaciones modulares para calcular xc (mod n) a un máximo de 2l, donde L es el. representación binaria del número exponente c. Supongamos que n representa k bits en forma binaria, es decir, k = [log2n] +1. L≤k, por lo que xc(mod n) se puede completar en un 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 se expresa en forma binaria como :
c=
xc = xc0×(x2)c 1×…×(x2t-1)CT-1
Precalculado: 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. Hasta/muy
Se suele utilizar la multiplicación T-1. Consulte la página 177 del libro de referencia para realizar cálculos.
Programa del algoritmo 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
Características de la firma tradicional (firma manuscrita):
( 1) La firma es la parte física del documento firmado;
(2) Verificar la parte física y compararla para lograr el propósito de confirmación. (Fácil de falsificar)
(3) ¡"Copiar" fielmente no es fácil! ! !
Definición: (Esquema de firma digital) Un esquema de firma es un algoritmo de firma y verificación.
El algoritmo de prueba consta de dos partes. Se puede dividir a través del grupo de relaciones de cinco elementos (P, A, K, S, V):
(1)P es el conjunto finito de todos los mensajes posibles;
(2)A es el 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} satisfacen la condición: cualquier x ∈ p, y ∈ a. Firma con esquema de firma: ver (x, y) = {
Nota: 1*. Para cualquier k∈K, las funciones Sigk y Verk son funciones de tiempo polinomiales.
2*.Verk es una función pública, mientras que Sigk es una función secreta.
3* Si un tipo malo (como Oscar) quiere falsificar la firma de Bob en X, es computacionalmente imposible. Es decir, dado x, sólo Bob puede calcular la firma y tal que verk (x, y) = verdadero.
4* Los esquemas de firma no pueden ser incondicionalmente seguros. Con tiempo suficiente, Oscar siempre podría 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 q y d son secretas (claves privadas). Para x∈P, Bob debería firmar X y tomar K ∈ K. ¿Sigk(x)? xd(mod n)? y(módulo n)
Por lo tanto
Verk(x, y) = verdadero x? Ye (moderno)
(Nota: e, n están abiertos; ¡puedes verificar públicamente si la firma (x, y) es correcta o incorrecta! Es decir, si es la firma de Bob)
Nota: 1*. Cualquiera puede calcular x=ek(y) para una determinada firma Y para falsificar la firma de Bob en un mensaje aleatorio x.
2*. Transmisión cifrada de mensajes firmados: Supongamos que Alice quiere cifrar un mensaje firmado para Bob. Ella hace esto: para el texto sin formato X, Alice calcula la firma de X, y=SigAlice(x). luego Calculado utilizando la función de cifrado público de Bob, eBob.
Z=eBob(x, y), Alice envía Z a Bob. Después de que Bob recibe Z, el primer paso es descifrar.
dBob(Z)=dBobeBob(x,y)=(x,y)
Entonces comprueba
VeraAlice (x,y) = true
p>
P: Si Alice primero cifra el mensaje X y luego lo firma, ¿cuál será el resultado
? Y=SigAlice(eBob(x))
Alice envía (Z, y) a Bob, y Bob primero descifra Z para obtener X luego usa
VerAlice para verificar la firma cifrada; y sobre x . El problema potencial con este enfoque
El problema es que si Oscar obtiene el par (z, y), puede reemplazar la firma de Alice con su firma
¿y? =SigOscar(eBob(x))
(Nota: Oscar puede firmar el texto cifrado eBob(x) incluso si no conoce el texto sin formato x. Oscar se teletransporta (z, y?) Bob, Bob, él puede inferir que el texto sin formato Sea p
al menos 150 números primos decimales y p-1 tenga un factor primo grande. Zp es un campo finito,
Si α es una primitiva en Zp, entonces ZP * =
Cómo calcular el entero único A, (obligatorio, 0≤a≤ p-2 ), satisfaciendo
αa=β (módulo p)
Escribe a como a=logαβ.
En general, resolver a es computacionalmente difícil.
Descripción del sistema de clave pública Egamal en Zp*: Sea el espacio de texto plano P=Zp* y el texto cifrado esté vacío.
C=Zp*×Zp*, define el espacio clave K={(p,α,a,β)|β=αa(mod p)}
La clave pública es :p,α,β.
Clave (clave privada): a
Alice toma un número aleatorio secreto k∈ Zp-1 y cifra el texto sin formato x.
ek(x,k)=(y1,y2)
Donde y1 = α k (mod p), y2 = x β k (mod p).
Bob lo descifró,
dk(y1, y2)=y2(y1α)-1(mod p)
Nota: 1*. ¡Es fácil verificar que Y2(y 1α)-1 = X(αA)K(αKa)-1 = X! !
2* Utilizando el algoritmo de cifrado EIGamal, se puede proporcionar un esquema de firma basado en esto:
Alice quiere firmar el texto sin formato x. Primero, toma un número aleatorio secreto K. como la firma.
Firma
Sigk(x, k)=(?, ?)
¿Dónde? =αk(mod p),? =(x-a?)k-1(modelo p-1)
Cierto, x? ∈Zp* y ∈ Zp-1, la definición Verk(x,,?)=true es equivalente a
β?α?=αx (módulo p)
Debería ser Tenga en cuenta que si la firma se construye correctamente, entonces la verificación
será exitosa porque
β?α?= αa? ¿ak? (mod p)= αa? +k? (Ministerio de Defensa)
¿Sabes desde arriba? =(x- a?) puede introducir k-1 (mod p-1).
k? =x-a? (mod p-1) tiene un? +kx(mod p)
¿Entonces beta? = αx (módulo p)
Este esquema de firma ha sido identificado como un estándar de firma (1985) por el NIST (Instituto Nacional de Estándares y Tecnología).
Para RSA, visite el sitio web:
www.RSAsecurity.com