3 jun. 2013

¿Qué sucede al introducir el número de tarjeta de crédito en línea?

Números primos Ocultar sus secretos

tarjetas de crédito, lo que sucede al introducir el numero en linea
Los números primos están de moda en estos días. Te puedo decir qué pasa cuando la gente al azar comienzan a preguntarme sobre ese algo aleatoriedad de los números primos , sin siquiera saber que soy un matemático! En el último par de semanas hemos oído hablar de un hermoso resultado de las diferencias entre los números primos y unos primo-numerados ciclos de vida de las cigarras " . Nuestra historia de amor actual con los primos a pesar de que muchas personas han preguntado si esta es toda la materia teórica abstracta o simplemente si los números primos tienen aplicaciones en el mundo real.

De hecho, tienen aplicaciones en algo tan ubicuo y mundano como hacer una compra en línea. Cada vez que introduzca su número de tarjeta de crédito en Internet, números primos entrar en acción. Antes de que su número de la tarjeta se envía a través de los cables, debe ser encriptada para mayor seguridad, y una vez que ha recibido por el comerciante, que debe ser descifrado. Uno de los esquemas de cifrado más comunes, el algoritmo RSA, se basa en números primos. Se utiliza una "clave pública", información que está disponible públicamente, y una "clave privada", algo que sólo la parte de decodificación (comerciante) tiene. En términos generales, la clave pública se compone de un gran número que es el producto de dos números primos, y la clave privada se compone de estos dos mismos números primos. Es muy difícil de factorizar un número grande entregado en números primos. Por ejemplo, se tomó dos años investigadores recientemente para factorizar un número de 232 dígitos , incluso con cientos de ordenadores paralelos. Es por eso que el algoritmo RSA es tan eficaz.

Los números primos son números enteros mayores que 1 que no son divisibles por cualquier número entero distinto de 1 y sí mismo. Los primeros son 2, 3, 5, 7, 11, 13 ... Para explicar cómo funciona el algoritmo RSA, tengo que decir que por primera vez sobre algo llamado pequeño teorema de Fermat. Fue descubierta por Pierre Fermat, el mismo matemático francés que se le ocurrió la famosa último teorema de Fermat . Fermat tenía una inclinación por ser secreta, y en el caso de su último teorema, dejó una nota en el margen de un libro afirmando su teorema y agregó: "He descubierto una demostración verdaderamente maravillosa de esto, que este margen es demasiado estrecho para contener. "Llámelo la 17 ª versión del siglo de una prueba de Twitter. Muchos matemáticos profesionales y aficionados trataron de reproducir supuesta prueba de Fermat, y tardó más de 350 años para llegar a una real .

Anuncio

Para entender lo que significa pequeño teorema de Fermat, tenemos que aprender a hacer aritmética "modulo N." Esto es algo que, de hecho, lo hacemos todo el tiempo al añadir ángulos. Si se gira un objeto por 180 grados, y luego por el otro 270 grados, el resultado neto será la rotación de 90 grados. Eso es porque 180 + 270 = 450, y luego restamos 360 de la misma, debido a la rotación de 360 grados significa que no hay rotación neta en absoluto. Esto es lo que los matemáticos llaman adición "módulo 360." Del mismo modo, podemos hacer además modulo cualquier número entero N en lugar de 360. ( Otro ejemplo conocido es la adición de horas, donde N = 12. ) Y también puede hacer la multiplicación modulo N.

Supongamos ahora que N es un número primo. Luego tenemos el siguiente hecho notable: Aumento de cualquier número a la N ª potencia módulo N, tenemos que volver ese mismo número. Por ejemplo, si N = 5, entonces la 5 ª potencia de 1 es 1 y la 5 ª potencia de 2 es 32, que es igual a 2 módulo 5 porque después de restar el múltiplo más cercano de 5 (en este caso, que restar 30, o 5 × 6), que se quedan con 2 (porque 32 = 5 × 6 + 2). Del mismo modo, la 5 ª potencia de 3 es igual a 3 módulo 5, y así sucesivamente. Esto es pequeño teorema de Fermat. Fermat primero divulgado en una carta a un amigo. "Yo le enviaremos una prueba de ello", escribió, "pero me temo que es demasiado largo." Fue una burla tal, este Fermat. A diferencia de la prueba de su último teorema, sin embargo, la prueba de la pequeña es sorprendentemente simple-incluso podría caber en el margen de un libro. Me gustaría escribir aquí, pero mi editor me dice que mi artículo es ya demasiado tiempo. No se preocupe, sin embargo, se puede leer la prueba en este extracto de mi libro Love and Math .

Este es limpio, pero ¿qué tiene que con la seguridad en Internet? Tenemos que idear una de dos etapas procedimiento: Primero cifrar un número de tarjeta de crédito y luego descifrarlo, por lo que si seguimos los dos pasos que volvamos al número original. La buena noticia del pequeño teorema de Fermat es que criar a un número de tarjeta para una potencia de módulo principal que prime es un procedimiento que nos devuelve el número original. La mala noticia es que, debido a un claro no es divisible por nada, no hay manera de romper este procedimiento en dos pasos. Sin embargo, Ron Rivest, Adi Shamir y Leonard Adleman, que da nombre al algoritmo RSA, no se desanimen. Tomaron la idea de Fermat un paso más allá. Le preguntaron: ¿Qué pasa si tomamos N que es el producto de dos números primos les llaman- p y q . Luego tenemos el siguiente análogo del pequeño teorema de Fermat: Elevar un número a la potencia ( p - 1) ( q - 1) + 1 nos va a devolver el mismo número de módulo N. Por ejemplo, N = 15 es el producto de p = 3 y q = 5. Entonces ( p - 1) ( q - 1) + 1 = (3 - 1) (5 - 1) + 1 = 9. Si se eleva un número a la 9 ª potencia, se obtiene el mismo número de módulo 15. Parece un milagro, pero de hecho, la prueba no es más complicado que el del pequeño teorema de Fermat.

Y ahora podemos utilizar para el cifrado: Para los números primos dados p y q , la combinación ( p - 1) ( q - 1) + 1 será típicamente un número que no es un número primo. Por lo tanto, se puede representar como el producto de dos números enteros, los llama r y s . (En nuestro ejemplo, ( p - 1) ( q - 1) + 1 = 9, para que podamos tomar r = 3 y s = 3.) Elevar un número a la potencia ( p - 1) ( q - 1) + 1 ahora se puede dividir en dos etapas: sensibilización a la r th poder y luego subir a la s ª potencia.

Así es como funciona en la práctica: El comerciante recoge dos grandes números primos p y q (hay varios algoritmos para generar números primos ), lleva su producto N, y elige r y s . Él o ella entonces hace r N y conocidos por todos, esta es la clave pública. El cifrado consiste en aumentar el número de tarjeta de crédito por el r ª potencia módulo N. Cualquiera puede hacerlo (en un equipo, ya que los números involucrados son bastante grandes). El descifrado, por el contrario, consiste en aumentar el número resultante de la s ª potencia módulo N. Esto devuelve el número de la tarjeta de crédito original ( ver aquí para más detalles ). El comerciante mantiene el número s secreto. Por lo tanto la transmisión de los números de tarjetas de crédito es seguro. 

La única manera de encontrar s , y por lo tanto para ser capaz de descifrar los números de las tarjetas, es determinar los factores primos p y q el número de N. Para n suficientemente grande, sin embargo, el uso de métodos conocidos de la factorización prima, que puede tomar muchas meses para encontrar p y q , incluso en una red de computadoras de gran alcance. Pero si se pudiera llegar a una forma más eficiente de factorizar números en primos (por ejemplo, mediante el uso de una computadora cuántica ), entonces se tendría una herramienta para romper el algoritmo RSA. Es por eso que una gran cantidad de investigación se dirige hacia la factorización de números en primos. Las puntuaciones de los matemáticos legítimos están trabajando en ello, y tal vez no los tan legítimos también.

Para un extraño, el algoritmo RSA se presenta como un truco de cartas: Eliges una carta de una pila, ocultarla (esto es como el cifrado), y después de algunas manipulaciones del mago que produce el tarjeta-Bazinga! Bueno, eso es más o menos lo que hace el algoritmo RSA ... excepto que el papel de la magia ahora se juega por las matemáticas.