Борисенко, la piel-mate del MGU

A diferencia de la codificación simétrica, a que el procedimiento del desciframiento se restablece fácilmente por el procedimiento de la cifración y atrás, en el esquema de la codificación con la llave abierta es imposible calcular el procedimiento del desciframiento, sabiendo el procedimiento de la cifración. Más exactamente, el tiempo del trabajo del algoritmo que calcula el procedimiento del desciframiento, es tanto grande que de ello no es posible cumplir en cualesquiera ordenadores modernos, lo mismo que en cualesquiera ordenadores del futuro. Tales esquemas de la codificación llaman asimétrico.

Así, tenemos dos representaciones:

Donde S - la multitud de mensajes de todo género no cifrados, T - la multitud de mensajes cifrados. La letra "E" - la primera letra de la palabra "Encoding", la letra "D" - la primera letra de la palabra "Decoding". La representación

Traduce el mensaje inicial s en el mensaje cifrado t, la representación

Traduce el mensaje cifrado t atrás en s. Aquel hecho que D es el procedimiento que decodifica, en la lengua matemática significa que la composición de las representaciones DE es la representación idéntica: para cualquiera s es justo

Todo esto es justo para cualquier esquema de la codificación asimétrica. Pasaremos directamente al esquema RSA llamado tan por las primeras letras de los apellidos de sus autores - Rumley, Shamir, Adleman. Notaremos en seguida que el esquema RSA posee dos propiedades adicionales muy útiles.

1. La multitud de mensajes S iniciales coincide con la multitud de mensajes T codificados; en calidad de esta multitud se usa el anillo de las deducciones por el módulo m, donde m - la obra de dos números simples grandes (la notación decimal m tiene la longitud no menos 200).

2. ¡No sólo DE = 1, sino también ED = 1! Así, D y E - dos representaciones mutuamente de vuelta. Esto permite el propietario del procedimiento secreto de la descodificación D aplicarla para la codificación. Además todos pueden раскодировать este mensaje, usando el procedimiento E abierto, pero sólo el propietario del procedimiento D secreto puede mandarlo. Tal esquema "de vuelta" de la aplicación de la llave abierta permite certificar el remitente del mensaje. En las aplicaciones prácticas (para аутентификации del remitente) el esquema de vuelta hasta es más importante, que la recta.

Así, en el esquema RSA en calidad de la multitud de mensajes iniciales y cifrados se usa el anillo de las deducciones Z_m, donde

La obra de dos números simples grandes (la longitud de la notación decimal cada uno los números p y q es no menos 100). Cada mensaje parece en forma del elemento Z_m. (Cualquiera собщение es una consecuencia битов, que se puede examinar como el número grande entero. Si la longitud del mensaje más que la longitud de la notación binaria m, se estrella a los bloques, y cada bloque es cifrada separadamente.)

El número m abierto, sin embargo la descomposición m en el multiplicador - secreto. La descomposición permite calcular la función de Ejlera (la consecuencia 3):

Es fácil mostrar que el conocimiento de la función de Ejlera da la posibilidad de exponer el número en el multiplicador, así que la complicación de la tarea de la fracturación de la llave abierta es igual a la complicación de la tarea de la descomposición en el multiplicador. Los matemáticos creen que es la tarea realmente difícil, aunque ningunas apreciaciones satisfactorias de abajo en la actualidad no es recibido. (Y es poco probable la tarea NP-completa.)

Generaremos el elemento casual e en el anillo de las deducciones por el módulo phi (m), tal que él es convertible en este anillo (e.d. es simple con phi (m)). Un par (m, e) es la llave abierta. La representación E consiste en la edificación en el grado e en el anillo de las deducciones por el módulo m.

Para el cálculo práctico se aplica el algoritmo de la edificación rápida en el grado.

Para el elemento e es calculado el elemento de vuelta d en el anillo de las deducciones por el módulo phi (m).

Esto se hace fácilmente por medio del algoritmo extendido de Evklida. Un par (m, d) es la clave secreta. La representación D consiste en la edificación en el grado d en el anillo de las deducciones por el módulo m.

Mostraremos que la representación D es izquierda de vuelta a E, e.d. para cualquiera ссобщения s se cumple la igualdad D (E (s)) = s. Tenemos

Así, DE = 1. Es demostrado análogamente que ED = 1.

Es examinada la multitud de mensajes Z_m, donde m - la obra de dos números simples grandes: m = p*q. El número m es abierto, pero su descomposición en el multiplicador - secreto. El conocimiento de la descomposición permite calcular la función de Ejlera phi (m) = (p-1) * (q-1). Sale Por casualidad el elemento convertible e en el anillo de las deducciones por el módulo phi (m). Para él es calculado (por medio del algoritmo extendido de Evklida) el elemento de vuelta d en el anillo de las deducciones por el módulo phi (m). La representación E es dada a un par (m, e) y consiste en la edificación en el grado e por el módulo m:

La representación D es dada a un par (m, d) y consiste en la edificación en el grado d por el módulo m:

Estas dos representaciones son de vuelta. Un par (m, e) es la llave abierta (public key), un par (m, d) es la clave secreta (private key).

El ejemplo. Examinaremos el ejemplo con los números pequeños para solamente ilustrar el esquema RSA. En las aplicaciones reales usan los números grandes enteros, aproximadamente 200-400 cifras decimales.

Que m = 11*13 = 143. Calcularemos la función de Ejlera phi (m) = 10*12 = 120. Escogeremos e = 113, entonces d = 17 - de vuelta a e el elemento en el anillo Z₁₂₀.

Un par (143, 113) compone la llave abierta, el vapor (143, 17) - la clave secreta. La representación E consiste en la edificación en el grado 113 por el módulo 143, la representación D - en el grado 17 por el módulo 143. Examinaremos el mensaje cualquiera s = 123. Entonces

Así, 41 es un mensaje codificado. Aplicaremos a él el procedimiento que decodifica:

Hemos recibido el mensaje inicial.

En relación al esquema RSA surge una serie de las tareas algorítmicas.

1. Para la generación de las llaves tenemos que saber generar los números simples grandes. La tarea próxima es la comprobación de la simplicidad del número entero.

2. La fracturación de la llave en RSA tiene que saber exponer el número entero en el multiplicador (o que prácticamente mismo, saber calcular la función de Ejlera). La fractura de la llave puede interesar solamente a los criminales, pero, por otro lado, los que tratan de proteger la información, deben ser están seguros que la tarea de la descomposición en el multiplicador es bastante difícil.