El sistema criptográfico asimétrico RSA: Consideraciones de la

seguridad del criptosistema RSA

¿Cómo podemos probar que el criptosistema RSA es seguro?

Ma1temáticas NS

Palabras:

1
Índice

1. Introducción

2. Criptografía moderna (intro to crypt mes web escriure simplificadíssim mates pero no

moltes puto esquizo que no acabes si no fas per damunt, paraules guapes en plan

permutaciones)

2.1 La criptografía moderna

2.2 Mensaje y cifrado

2.3 Claves y funciones Enc, Dec y Gen

2.4 Computacionalmente seguro e incondicionalmente seguro

2.5 Funciones trap-door

2.6 Presunciones de los sistemas criptográficos

3. Teoría de números (retallar coses inútils y revisar problemes notació, 2 y algoritmo

extendido de Euclides)

3.1 Divisibilidad, números primos

3.2 Máximo común divisor, algoritmo de Euclides y la identidad de Bézout

3.3 Aritmética modular

3.4 Función phi de Euler

3.5 El teorema de Euler

4. El sistema RSA

4.1 El criptosistema RSA

4.2 Generación de claves (fer més fácil si no se pot fuck it)

4.3 Funciones de encriptación y desencriptación

4.4 Ejemplo

2
 5. Prueba de seguridad (prueba de su funcionamiento no es necesario tiempo polinomial

solo mencionar lo que implicaba ref a toda la sección 3 con tal de probar corrección y ref

importante a la sección de los números primos, criptánalisis sin entrar en detalles solo

mencionar y ejemplos, limitaciones de esta prueba en los supuestos criptoanal y

factorizar enteros en tiempo polinomial)

5.1 Prueba de corrección del funcionamiento del criptosistema RSA

5.2 Presunción de su seguridad

5.3 El problema RSA

6. Conclusión (conclusión, limitaciones, mira si te que haber reflexió)

7. Bibliografía (revisar totes les fonts consultades a Mendeley y preparar citacions)

Ápendices programas utilizados para ejemplos y simulaciones

3
1. Introducción

En esta monografía se considera la pregunta de investigación “ ¿Cómo podemos probar que el

criptosistema RSA?”. Esta surgió a partir de mi curiosidad por entender como funcionaba el

intercambio seguro de información entre computadoras, lo que me llevó a realizar una

investigación preliminar sobre la criptografía y los principales métodos criptográficos,

llevándome esta a interesarme finalmente por el criptosistema RSA debido a que me fascinó la

relativa sencillez de funcionamiento un método tan seguro y comúnmente utilizado actualmente.

Esto me empujó a intentar querer entender como era posible que este funcionase y en que

sostiene esta aparente seguridad.

Si bien soy consciente que este sigue siendo un problema abierto al no estar claro si es posible

computar la factorización de enteros en tiempo polinomial (tal y como será explicado en la

última sección), siendo este hecho una limitación, trataré de probar la corrección del esquema del

criptosistema hasta llegar al porque de este problema. Con tal de realizar esto en esta monografía

se abordará la pregunta desde un enfoque descendente, primeramente, antes de empezar con el ce

problema se establece marco de conocimiento en el que se enmarca este, siendo este el de la

criptografía moderna y de las características generales de esta, con la finalidad de tener los

conocimientos necesarios con tal de entenderlo.

A continuación, se presentan (y en caso de ser necesario se prueban) los conceptos de teoría de

números necesarios con tal de comprender como funciona el sistema y poder probar

posteriormente su seguridad. Tras la presentación de estos conocimientos indispensables se

procede a la descripción del criptosistema la cual será necesaria con tal de finalmente probar su

seguridad aplicando los conocimientos de las secciones anteriores, teniendo en cuenta las

limitaciones inherentes.

4
2. Criptografía moderna

2.1 La criptografía moderna

Según la RAE la criptografía puede ser definida como el “Arte de escribir con clave secreta o de

un modo enigmático.”1, refiriéndose a esta como un arte de escribir códigos con tal de ocultar

información. Sin embargo, si bien está definición puede ser considerada correcta para la

criptografía clásica (la cual era en gran medida dependiente de la creatividad y habilidades

personales y en gran medida su seguridad era subjetiva), actualmente esta definición puede

considerarse obsoleta, ya que debido a el desarrollo del paradigma de una teoría de sólida a

finales del siglo XX esta ha dejado atrás su consideración de arte hasta pasar a ser una rama de

las matemáticas bien establecida con estrechas relaciones con la teoría de la información y la

computación. Deja atrás su noción de arte dependiente de la creatividad personal hasta permitir

su estudio científico, gracias a la creación de unas definiciones rigurosas (sabiendo así que se

quiere conseguir al desarrollar un sistema criptográfico) y la posibilidad de realizar pruebas de

seguridad estableciendo exactamente, las presunciones formales tomadas en estas. Sumado a

esto, cabe mencionar la multitud de aplicaciones que esta sirve en la era de la información,

siendo la transmisión de mensajes secretos tan solo meramente una de ellas. Debido a esto en su

libro “Introduction to Modern Cryptography” J. Katz y Y. Lindell ven necesario redefinir a la

criptografía moderna como “the scientic study of techniques for securing digital information,

Real Academia Española. (2019). Criptografía. En Diccionario de la lengua española (22.a ed.).
Recuperado de [Link]

5
transactions, and distributed computations.”2, estableciendo con esta definición su categoría de

ciencia rigurosa y multitud de aplicaciones actuales.

2.2 Mensaje y cifrado

La criptografía se basa en una serie de esquemas de encriptación los cuales tienen como objetivo

esconder información en una comunicación por un canal no seguro entre dos usuarios de un

posible atacante malicioso. Llamamos a la información que se quiere llegar a compartir por las

dos partes mensaje (denotado m) y a la información compartida por el canal tras ser encriptada

cifrado (denotado c)3

2.3 Claves y funciones Enc, Dec y Gen

Con tal de realizarse este intercanvio de información de manera segura todo criptosistema consta

de tres funciones4:

2.3.1 La función generatriz de claves Gen, la cual genera una clave/s k a partir de una

distribución probabilística diferente según el criptosistema utilizado. Esta clave/s será/n usada

por las otras funciones con tal de encriptar y desencriptar el mensaje.

2.3.2 La función encriptadora (denotada por Enc k (m) ) la cual utiliza el usuario que quiere enviar

el mensaje y mediante una clave k y m devuelve el cifrado c.

2.3.3 La función desencriptadora (denotada por Dec k (c) ¿ la cual utiliza el usuario que recibe el

cifrado con tal de obtener el mensaje, obteniendose m a partir de usando una clave k.

J. Katz y Y. Lindsell, Introduction to Modern Cryptography: CRC PRESS, 2007, p. 3-4

3

Introduction to modern c
4

Introduction to modern c

6
2.3.4 Según si se genera una con Gen una sola clave que tiene que ser compartida de antemanos

a la comunicación por los usuarios o dos claves una pública y una privada (la pública es

conocida por los dos usuarios y es usada por Enc y la privada no es compartida, tan solo es

conocida por el usuario que usa Dec), se distinguen dos tipos de criptosistemas los simétricos y

los asimétricos, teniendo estos últimos la ventaja de no tener que compartirse información

susceptible de antemano otorgando una mayor fiabilidad al sistema.

2.4 Computacionalmente seguro y incondicionalmente seguro

Con tal de poder analizar la seguridad de un criptosistema es necesario establecer que

entendemos por seguridad en la criptografía.

2.5 Funciones “trap-door”

Decimos que una función

2.6 Presunciones en los sistemas criptográficos

[Link]ía de números

Para poder comprender el funcionamiento del algoritmo RSA y proceder a la posterior prueba de

su seguridad, es necesario entender ciertos conceptos elementales de la llamada teoría de

números, rama de las matemáticas puras que se encarga del estudio de los enteros y sus

propiedades.

3.1 Divisibilidad, división euclidiana y números primos

3.1.1 Decimos que un número a divide a un número b (relación expresada con la notación a∨b)

si b = ac para un entero c. A partir de esta definición podemos derivar ciertas propiedades 5 las

cuáles serán útiles en partes posteriores de la monografía:

Andreescu, T., & Andrica, D. (2009). Number Theory: Structures, Examples, and Problems. p. 15

7
 [Link] Si a∨b , b ≠ 0 entonces |a|≤|b| (ya que si ¿ a∨¿∨b∨¿ entonces ningún numero

entero c puede igualarla con b)

[Link] Si a∨bi a∨c entonces a∨αb + βc para cualquier entero α , β. (Esto puede ser

probado al observar que

b=ab' , c=ac ' siendo c ' y b ' un número entero → αb+ βc=αa b ' + βa c ' =a(α b ' + β c ' )

[Link] Si a∨b y a∨b ± c entonces a∨c (b = ab’ entonces b ± c=ab ' ± c , entonces c debe

ser dividible ya que sino seria imposible dividir la suma)

[Link] a∨a (Ya que a = ac, c =1)

[Link] Si a|b y b| c entonces a∨c (Ya que si b=b' a y c=c ' b entonces c=c ' b ' a

implicando a∨c)

[Link] Si a∨c y a∨b entonces en c ±b=n ,implica a∨n (Ya que

c ±b=c ' a+b' a=a(c ' +b' )

3.1.2 Si bien no todos los números se dividen podemos encontrar para cualquier entero positivo a

y b un par de enteros (q, r) que cumplen b=aq+ r ,r < a, siendo esta la llamada división

euclidiana. Este teorema puede ser probado de la siguiente manera:

Consideramos el set de enteros de forma a - nb S = { a−n b : n ∈ Z }. Al ser b no igual a 0, el set es

infinito al existir infinitas n. S ∩ N ≠ ∅ al existir una n para la que a−nb> 0, existiendo por tanto

enteros positivos en el set. Definimos r como el menor número positivo en S. Por la definición del

set podemos ver que existe una q, q ∈ Z para la cuál r =a−q∗b. Por tanto, a=qb+ r , r >0

Suponemos que r ≥ b, entonces r −b=a−( q+1 ) a implicando que 0 0< r−b< r, llevandonos a una

contradicción, implicando que r <b Queda así demostrada la existencia de q y r para la ecuación.

Con tal de demostrar su unicidad asumimos que existen unos enteros r ' , a' para los cuales

' ' ' ' '

a=qa+r =q ' a+r ' , 0 ≤ r ,r ' <a qa−q a=r −r , a ( q−q ) =r −r → a ∣(r −r ). Por lo tanto, ∣r −r ' ∣<a

8
, implica que r −r ' ha de ser 0 siendo por tanto equivalentes. Por lo tanto para que ( q−q ' ) a=0 , q

debe ser igual a q’, ya que a no es cero, implicando que solo existen un solo r y q.

3.1.3 Considerando la definición 3.1.1 podemos definir a los números primos como aquellos

enteros p que solo se dividen por 1 y p, p>1, llamándose compuestos todos los otros. Dos

propiedades básicas (y útiles en la criptografía) de estos números son:

[Link] Todo número puede ser expresado como un producto de una secuencia única de

números primos. Este es el llamado teorema fundamental de la aritmética.

Podemos probarlo de la siguiente manera6: Primeramente, probamos que existe una

manera de factorizar a n. Sea p1 un primo divisor de un entero n. Entonces en el caso que

n= p1 esta es su factorización. Si p1 <n entonces n= p1 r 1 , r 1 >1. Si r 1 es primo entonces

ya hemos terminado. Si no podemos volver a expresar el número como p1 p 2 r 2 y así

sucesivamente, probando así la existencia de su factorización, siendo ahora necesario

probar su unicidad. Asumimos que existe un entero compuesto n que tiene 2

combinaciones posibles de factores primos, es decir

n= p1 p2 … p k =q 1 q2 … q j , k > 2, j>2 , k =1 ,2 , 3 , … , k , j=1 ,2 , 3 , … , jDecimos que pk ≠ q j,

siendo n es el entero mínimo que cumple estas características. Asumimos que p1 es el

factor primo más pequeño de n. Aplicando el algoritmo de división euclidiana (3.1.2) se

entiende que cualquiera de los primos q jde la secuencia puede representarse como

q j= p 1 c k +r k , 1≤ r k < p1, por lo tanto, sabemos que

n=q1 q 2 … q j=( p1 c1 +r 1 )( p ¿ ¿ 1 c2 +r 2 ) …( p1 c k + r k )¿, llamamos A a todos aquellos enteros

Andreescu

9
del resultado de la expansión que tienen como factor p1 , y al producto de la permutación

r k n’ siendo por tanto n= p1 p2 … p k = A p1 +n ' , implicando por [Link] que p1∨n ' y que al

ser este divisible tiene una factorización en primos tal y como hemos probado en la parte

inicial de la demostración, n' = p 1 s 1 s 2 … si, siendo siprimos. Sabemos según 3.1.2 que

r k < p1 por tanto n ' debe tener una factorización de forma t 1 t 2 … t j , siendo t j < p1, teniendo

n' por tanto dos posibles factorizaciones. Sin embargo, sabemos que n' <n por lo tanto se

contradice la minimalidad de n, produciendo una prueba por contradicción.

[Link] Existen infinitos números primos, hecho que en los sistemas criptográficos los

vuelve muy útiles al no tener el límite, la difiultad de la factorización de un producto de

dos primos. Una prueba7 es conocida desde los tiempos del matemático Euclides

(matemático griego que vivió hace más de 2000 años) la cual fue descrita en su libro

Elementos:

Asumimos que existe un número finito de primos creando la secuencia { p1 , p 2 , … , pn }.

Consideramos el número P = p1 ∙ p1 ∙ … pn +1. Si P es primo entonces es mayor que pn,

contradiciendo por tanto su maximalidad. Entonces si P no es primo es compuesto y debe

tener al menos un factor primo pk . Es fácil observar que pk ∨ p 1 ∙ p 1 ∙ … p n. Por tanto,

según la propiedad [Link] debe dividir a 1 al dividir a P, implicando una contradicción y,

probando por tanto que hay infinitos primos.

Traducción elementos

10
3.2 Máximo común divisor, algoritmo de Euclides, la identidad de Bézout

3.2.1 El máximo común divisor de dos números a y b (denotado mcd(a, b)) se define como el

mayor divisor que tienen en común dos números. Matemáticamente podemos decir que un entero

d es el mcd de dos números a y b si y solo si d | a y d | b y si y solo si un entero c c | a y c | b

implica c | d8

3.2.1.1Si el mcd de dos números es 1 estos son llamados coprimos.

3.2.2 Con tal de hallar el máximo común divisor existe un algoritmo eficiente llamado el

algoritmo de Euclides9. Para dos enteros a y b se aplica la división euclidiana (3.1.2), obteniendo

r (único por 3.1.2). Después de realizar la división euclidiana se repite el procedimiento con b y

r, ya que mcd(a,b) = mcd(b,r). Podemos probar esto de la siguiente manera:

Sea c = mcd(a,b). Vemos que c∨a y c ∨b, implicando que c debe también dividir a r por [Link],

ya que a = bq + r (3.1.2). Si existiera un número mayor que c que dividiera a bq y a r también

dividiria a a ([Link]) implicando que no sería el mcd, por tanto el mcd(b,r) = c. Este proceso se

repite con el nuevo residuo hasta obtener (c,0), siendo entonces c el mcd al ser el máximo divisor

con 0.

Ejemplo:

mcd(58, 9)

58 = 9*6 + 4

mcd (9, 4)

Chicago paper
9

Doc uni (posible canviar)

11
9=4*2+1

mcd(4,1)

4 = 1* 4 + 0

mcd(58,9) = 1

3.2.3 La identidad de Bézout establece que para dos enteros positivos a y b existen dos enteros x

y y que cumplen ax +by=mcd(a ,b).

3.2.4 Algoritmo extendido de Euclides:

Existe una extensión del algoritmo de Euclides que nos permite computar x y y. Observamos que

a medida que utilizamos 3.2.1, se forman una serie de ecuaciones de números de la forma

a=b q+ r → r =a−qb.

3.3 Aritmética modular

La aritmética modular, sistema introducido por Carl Friedrich Gauss en su libro Disquistiones

Arithmeticae10, es un sistema aritmético que se basa en las llamadas relaciones de congruencia.

Las relaciones establecidas en este sistema constituyen una de las partes fundamentales de la

teoría de números, teniendo además aplicaciones en multitud de campos, entre ellos el de la

criptografía moderna, siendo uno de los pilares que sustentan el criptosistema RSA tal y como

más adelante será descrito.

3.3.1 Decimos que dos enteros a y b son congruentes módulo n (escrito a ≡ b mod m) con n ≠ 0 si

m∨(a−b), siendo esto equivalente a afirmar que lo son si y solo si al realizar la división

10

.
12
euclidiana de a y b por m se obtiene la misma r 11 (siendo probado al observar que

a−b=n q1 −n q2 +r 1−r 2 implicando que a - b tan solo será dividido por m si r 1−r 2=0 ,es decir

r 1=r 2.

Por ejemplo, 7 ≡25 mod 6 al ser el residuo de 7 y 25 al ser divididos por división euclidiana

(3.1.2) con 6 1 para los dos.

Las congruencias tienen las siguientes propiedades fundamentales:

[Link] Reflexividad (es decir a ≡ a mod m, ya que a−a=0 , m∨0)

[Link] Transitividad (es decir a ≡ b mod m y b ≡ c mod n implica a ≡c mod n , m ya que el

residuo es igual para todos los números divididos por n.

[Link] Si a ≡ b mod n y c ≡ d mod n entonces a+ c ≡ b+dmod n y a−c ≡b−d mod n y

ac ≡bd mod n

[Link] Si ka ≡ kb mod n y k es coprimo con n ([Link]) entonces se puede cancelar k

siendo a ≡ b mod n ya que12:

k (a−b)≡ 0 mod nal ser r a −r b=0 Entonces n |k (a−b), por tanto, para un entero c

k ( a−b )=c∗n. Al ser k coprimo con n no puede contener factores de n, siendo por tanto .

n∨( a−b) y entonces u−v ≡mod n implicando que u ≡ v mod n.

3.3.2 El anillo de todos los enteros módulo n se denota por la notación Z n, es decir, cada residuo

que cada entero da al ser dividido por n.

11

12

Dragonwins

13
3.4 Función phi de Euler

La función indicatriz o phi de Euler denotada por el símbolo φ ( n ) es definida como el número de

enteros menores o iguales a n que sean coprimos ([Link]) con n 13. Con tal de mostrar su valor

Ilustración 1: Primeros 1000 valores de phi

para los primeros 1000 números he realizado un programa que ha devuelto este gráfico

(Ápendice)

El teorema de Euler en el cuál esta aparece es sobre lo cual se sustenta la seguridad del sistema

RSA tal y como veremos más adelante. Además, esta posee ciertas características relevantes en el

RSA con tal de utilizar la función Gen como más adelante será explicado:

3.4.1 Para todo primo p la función φ ( p )=φ ( p−1 ), esto puede ser fácilmente probado al observar

que por su propia definición (3.1.3) el número primo es coprimo con todos los números menores

que el siendo por tanto phi equivalente a phi – 1.

3.4.2 Para todos los números coprimos ([Link]) m y n que al computarseφ ( n ) , n=m∗n que la

función es equivalente a φ ( m )∗φ ( n ) si m y n coprimos ([Link]), es decir, es una función

13

Weisstein, Eric W. «Euler's Totient Function». MathWorld (en inglés). Wolfram Research.

14
multiplicativa (función que es equivalente al producto del cómputo de sus factores en la

función14).

Por lo tanto, según la propiedad 3.4.2 el valor de phi puede computarse fácilmente si se conoce

todos los factores primos ([Link]) de un número n y se produce la multiplicación de estos

aplicando la propiedad 3.4.1.

3.5 El teorema Euler

3.5.1 El teorema de Euler establece que para todos los enteros coprimos a y n se cumple que a

elevado a la función phi de n es congruente con 1 módulo n, es decir:

a φ ( n) ≡ 1(mod n)

Tal y como veremos en las siguientes secciones de la monografía, es tan solo a partir de este

teorema que nos es posible probar el correcto funcionamiento del esquema de encriptación-

desencriptación del sistema RSA, es por tanto necesario probarlo con tal de poder probar como

funciona este.

Este teorema puede ser probado de la siguiente manera15:

¿
Digamos que definimos el set Z n como el conjunto de todos aquellos enteros k pertenecientes a

(0,n) coprimos con n, es decir Z n = { k ∈ ( 0 , n )|mcd ( k , n ) =1.

¿

¿
Vemos entonces que φ ( n )=¿ Z n ∨¿.

14

Andreescu
15

Mit proof chapter 8.10

15
Tenemos entonces el lema: dos elementos j , k ∈ Z n entonces j n k ∈ Z n ( j n denota el residuo de j
¿

en el anillo Z n)16

Para un elemento cualquiera k ∈ Z n y un subconjunto cualquiera S ⊆Z n sea kS :≔ {k n s∨s ∈ S } .

¿

Debido a [Link] podemos ver que |kS|=|S|, ya que k ∈ Z n siendo entonces cancelable k en la
¿

congruencia k s ≡ kt mod n, implicando que todos los elementos de S están en kS pero en distinto

orden, siendo entonces del mismo tamaño.

¿ ¿
Sabemos entonces aplicando los dos lemas anteriores que k Z n =Z n ya que la multiplcación en el

conjunto es cerrada siendo entonces k Z n ⊆ Z n , y al ser estos iguales se prueba que k Z n =Z n .

¿ ¿ ¿ ¿

Sea P el producto de todos de los enteros Z n módulo n, es decir, P=k 1 ∙ k 2 … k φ (n ) ( Z n ) .

¿

Sea entonces también Q para un elemento k ∈ Z n , el producto de todos los enteros que están Z n
¿ ¿

φ ( n)
en módulo n, Q=( k ∙ k 1 ) ∙ ( k ∙ k 3 ) … ( k ⋅ k φ (n) ) ( Z n )=k P ( Z n ) . Al ser Q=k Z n¿ y P=Z n¿ , vemos que P

φ ( n)
=Q=k P ( Z n ), siendo por tanto P ≡k φ ( n) P mod n . Al ser P el producto de los coprimos con n es

coprimo n, siendo entonces P cancelable ([Link]), quedando probado entonces que 1 ≡k φ (n ) mod n

sí k es coprimo con n.

16

Vease para prueba

16
4. El sistema RSA

El algoritmo RSA es un sistema criptográfico de clave asimétrica, desarrollado en 1979 por R.L.

Rivest, A. Shamir, y L. Adleman en su papel “A Method for Obtaining Digital

Signatures and Public-Key Cryptosystems”. Fue el primer sistema en incorporar todos los

elementos descritos por W. Diffie y M. Hellman anteriormente mencionados, incluyendo la

posibilidad de generar firmas digitales, creando el primer ejemplo funcional de una función

trapdoor. Tal y como fue originalmente descrito el sistema funciona de la siguiente manera17:

4.1 Gen, Enc, Dec

4.1.1 La función Gen genera dos conjuntos de claves, siendo el conjunto (e, n) la clave pública y

el conjunto (d, n) las claves privada. Primeramente, se elige “aleatoriamente” dos primos p y q,

teniendo estos la longitud deseada considerando la dificultad que quiere imponerse al sistema.

Seguidamente se computa n = pq. A continuación, se computa la función phi de Euler (3.4) la

cuál utilizando (3.4.1). Se elige un entero positivo e que ha de cumplir la condición de ser

coprimo con φ(n).18 A continuación, se define d como el inverso multiplicativo modular de e

17

RSA paper
18

En la publicación original se elegía d y se encontraba e optimizando la encriptación al poder ser e

pequeño.

17
módulo φ(n), es decir d cumple ed ≡1 mod( φ ( n ) ), aplicándose el algoritmo extendido de

Euclides (3.2.4). Finalmente, la función devuelve el conjunto de la clave pública y el conjunto

de la clave privada.

4.1.2 La función de encriptación del sistema Enc que deberá utilizar un usuario de este con tal de

encriptar un mensaje m y obtener un cifrado c mediante el uso de la clave pública se define de la

siguiente forma:

c=E nc( e, n) ( m )=me mod ( n )

4.1.3 La función de desencriptación del sistema Dec que el receptor de c utiliza para obtener m

mediante su clave privada se define de la siguiente manera

d
m=D ec ( d ,n ) ( C )=C mod ¿)

4.3 Ejemplo

Con tal de ilustrar con un ejemplo el funcionamiento del criptosistema he desarrollado un

programa para mostrar su funcionamiento paso por paso19:

Digamos que un usuario de una app de mensajería (la cual encripta los mensajes mediante el uso

de RSA), llamado Bob quiere mandarle un mensaje m =“¿Hola, qué tal?” a otra usuaria llamada

Alice. Primeramente, la terminal de Alice aplica Gen con tal de generar el par de claves. En este

caso, son p y q generados mediante una cuña de Erástotenes20, siendo p = 941 y q = 739. A

continuación, la terminal de Bob transforma el mensaje en su representación numérica mediante

19

Programa incluido en el Ápendice

20

Método de búsqueda de números primos

18
cualquier código21 siendo entonces m = [72, 111, 108, 97, 44, 32, 98, 117, 101, 110, 97, 115, 32,

116, 97, 114, 100, 101, 115].

Estos números son encriptados por su terminal mediante el uso de la clave pública de Alice, la

cuál consiste en el número e = 6553722 y n= p∗q=695399. Usando la función E(e, n) para carácter

de m (es decir aplicando m 65537 mod ( 695399 ) ¿estos son encriptados por el terminal de Alice

obteniendo el cifrado: [641582, 343454, 578242, 653882, 604219, 288756, 76919, 163336,

126097, 639059, 76919, 214976, 604219, 653882, 251161], siendo enviados a la terminal de

Alice, la cuál será la única capaz de descifrar m en un tiempo razonable al poseer la clave

privada. El terminal de Alice al recibir el mensaje aplica la función D( d ,n ) (m), siendo en este caso

d equivalente al entero obtenido resolviendo 65537∗d ≡1 mod 693720 , es decir ,364913,

obteniendose entonces m mediante la operación c 364913 mod ¿) para cade carácter, devolviéndose

así el mensaje original tras invertir la transformación a números.

5. Prueba de seguridad

Habiendo aprendido entonces todos los conocimientos necesarios con tal de entender el

criptosistema y las matemáticas detrás de este se procede a probar su corrección y a presentar su

seguridad y que supondría una prueba de esta.

5.1 Prueba de corrección del funcionamiento del criptosistema RSA

5.2 Presunción del RSA, el problema RSA

Conclusión

21

ASCII en el ejemplo
22

Primo usuado habitualmente en la mayoría de implementaciones RSA

19
He podido probar con un nivel de formalidad adecuado la seguridad del criptosistema RSA,

demostrando todo aquello necesario con tal de establecer la corrección de la seguridad del

sistema y la presunción en la cual se sustenta, consiguiendo así en gran medida los objetivos

planteados para la monografía.

He podido establecer la noción de seguridad que brinda el criptosistema RSA y probar su

corrección dejando la presunción que presenta el problema RSA.

Si bien es cierto que creo que he podido alcanzar a responder en gran medida esta pregunta, esta

investigación tiene ciertas limitaciones. Debido al alcance de esta monografía no he podido

alcanzar a profundizar sobre el problema RSA al requerir este muchos más conocimientos que

los presentes aquí con tal de atacarlo al continuar este siendo un problema abierto. Tan solo he

podido mostrar porque la presunción de la dificultad de la factorización de enteros lo sustenta,

sin embargo, creo que este es la repuesta a la pregunta ya que seria tan solo presentando una

prueba de que un algoritmo eficiente de factorización de enteros que podría ser probado y esto es

mostrado.

Finalmente, debo también destacar que otra limitación de la monografía es que no se ha

considerado el posible criptoanálisis del criptosistema, existiendo diversos ataques

criptoanalíticos viables que pueden computar en ciertos casos específicos el mensaje a partir del

cifrado, los cuales he obviado debido a su especificidad al ser la pregunta de investigación de

una extensión más amplia que estos.

20
Bibliografía

-RSA paper

-Introduction to group theory

-Introduction to modern cryptography

-Number theory andreescu

-Number theory other book

-Introduction to algorithms

-PKSC1

-asymptomatic notation paper

-Integer factoring

-Curso aritmética

-Math UChicgo modular arithmethic

Matthew Morgado, Modular arithmetic, [online] Recuperado de:

[Link]

- Weisstein, Eric W. «Euler's Totient Function». MathWorld, Wolfram Research.

Proof of Euler’s φ (Phi) Function Formula Juan Vargasa Shashank Chorg

Apéndice

21