Universidad del Valle de Guatemala
Facultad de Ciencias y Humanidades
Departamento de Matemática
Matematica Discreta
PROYECTO II
ENCRIPTACIÓN RSA
José Andrés Auyón Cobar – 201579
Ángel de Jesús Mérida Jiménez – 23661
André Emilio Pivaral López – 23574
Catedrático: Mario Alberto Castillo Mazariegos
Sección: 10
Nueva Guatemala de la Asunción, 20 de noviembre de 2024
1
Índice
Índice............................................................................................................................................... 1
Introducción .................................................................................................................................... 2
Objetivos ......................................................................................................................................... 2
Objetivo General ......................................................................................................................... 2
Objetivos Específicos .................................................................................................................. 2
Marco Teórico................................................................................................................................. 3
Diseño e Implementación del Programa ......................................................................................... 4
generar_primo(rango_inferior, rango_superior) ......................................................................... 4
mcd(a, b)...................................................................................................................................... 4
inverso_modular(e, n) ................................................................................................................. 5
generar_llaves(rango_inferior, rango_superior).......................................................................... 5
encriptar(mensaje, llave_publica) ............................................................................................... 5
desencriptar(caracter_encriptado, llave_privada) ....................................................................... 6
Resultados ....................................................................................................................................... 6
Manejo de Errores ....................................................................................................................... 6
Conclusiones ................................................................................................................................... 7
Referencias...................................................................................................................................... 8
Anexos ............................................................................................................................................ 9
2
Introducción
La criptografía es una herramienta esencial para garantizar la seguridad de la información
en el ámbito digital. Desde el comercio electrónico hasta las comunicaciones personales, la
necesidad de proteger los datos contra accesos no autorizados nunca ha sido más crucial. En este
contexto, el sistema RSA (Rivest-Shamir-Adleman) ha demostrado ser uno de los métodos más
confiables y ampliamente utilizados para la transmisión segura de información.
RSA, fue desarrollado en 1977, se fundamenta en principios matemáticos sólidos,
específicamente en la teoría de números y el álgebra modular. Su principal fortaleza radica en la
dificultad computacional de factorizar números enteros grandes, un problema que sigue siendo
ineficiente de resolver incluso con las tecnologías computacionales más avanzadas.
El sistema RSA opera con un esquema de clave pública y privada: una clave pública para
encriptar datos y una clave privada para desencriptarlos. Este diseño permite la comunicación
segura entre partes que no han compartido previamente una clave secreta, resolviendo uno de los
desafíos más grandes de los sistemas de cifrado tradicionales. RSA no solo asegura la
confidencialidad, sino que también puede ser utilizado para verificar la integridad y autenticidad
de los datos.
Este proyecto tiene como objetivo desarrollar una comprensión profunda de RSA, desde
los fundamentos matemáticos hasta su implementación práctica en Python. Por medio de este
ejercicio, se busca no solo enseñar los conceptos teóricos, sino también fomentar habilidades en
resolución de problemas, programación y seguridad informática.
Objetivos
Objetivo General
Desarrollar e implementar el sistema de encriptación RSA en Python para comprender sus
fundamentos matemáticos y prácticos.
Objetivos Específicos
● Comprender y analizar en profundidad los fundamentos teóricos del sistema de
encriptación RSA, incluyendo la generación de la clave pública y la clave privada, así como los
procesos matemáticos subyacentes de encriptación y desencriptación de datos.
3
● Aplicar la teoría de números y los principios del álgebra modular para implementar de
manera efectiva las funciones clave del sistema RSA, con un enfoque en la precisión matemática
y la seguridad del algoritmo.
● Probar, evaluar y validar la implementación desarrollada a través de una serie de casos
prácticos que demuestren la funcionalidad y robustez del sistema, identificando posibles mejoras
y optimizando el rendimiento del código.
Marco Teórico
La criptografía, como disciplina dentro de la matemática aplicada y la informática, busca
garantizar la seguridad y privacidad de la información en entornos digitales. En este contexto, el
sistema de encriptación RSA, desarrollado por Rivest, Shamir y Adleman en 1977, se basa en
conceptos fundamentales de la teoría de números y el álgebra modular. RSA utiliza una
arquitectura de claves pública y privada, lo que permite que dos partes se comuniquen de manera
segura sin necesidad de compartir previamente una clave secreta.
El principio que garantiza la seguridad del sistema RSA radica en la dificultad
computacional de factorizar números grandes en sus factores primos. Este problema, conocido
como *Factorización Entera*, es considerado uno de los más complejos en matemática discreta.
RSA aprovecha esta característica para generar claves criptográficas mediante números primos
grandes y operaciones modulares, asegurando que cualquier intento de romper el cifrado requiera
recursos computacionales prohibitivos.
El algoritmo RSA sigue una serie de pasos matemáticos definidos. Inicialmente, se generan
dos números primos grandes, p y q, cuya multiplicación produce n, el módulo del sistema. A partir
de estos números, se calcula ϕ(n), conocida como la función de Euler, que mide la cantidad de
enteros coprimos con n. Un número entero e, que es coprimo con ϕ(n), se elige el exponente de
encriptación. Posteriormente, se calcula el inverso modular de e, denotado como d, que actúa como
el exponente de desencriptación. Estas operaciones garantizan que el sistema funcione de manera
reversible, permitiendo que un mensaje encriptado con la clave pública (e, n) pueda ser
desencriptado con la clave privada (d, n).
El sistema RSA no solo permite el cifrado de mensajes, sino que también asegura la
autenticidad de los datos, ya que cualquier modificación en el mensaje encriptado sería fácilmente
4
detectable al desencriptarlo. En términos de implementación, el algoritmo se descompone en
funciones específicas que incluyen la generación de números primos, el cálculo del máximo común
divisor (MCD), la obtención de inversos modulares y la ejecución de las operaciones de
encriptación y desencriptación. Cada una de estas funciones se basa en principios matemáticos
sólidos y algoritmos eficientes, como el algoritmo de Euclides y su versión extendida.
RSA es ampliamente utilizado en aplicaciones modernas como firmas digitales, comercio
electrónico y sistemas de autenticación, lo que lo hace una herramienta importante en el ámbito de
la seguridad informática. La paralelización es esencial cuando se trabaja con grandes volúmenes
de datos o cuando se busca mejorar el rendimiento de una aplicación. En el caso de las operaciones
matriciales, el tiempo de ejecución puede crecer exponencialmente con el tamaño de las matrices.
Diseño e Implementación del Programa
generar_primo(rango_inferior, rango_superior)
Descripción
Esta función genera un número primo aleatorio dentro de un rango dado. Los números
primos son fundamentales en RSA porque garantizan la seguridad del sistema al ser componentes
clave de la generación de claves.
Pasos
1. Utilizar un generador de números aleatorios para seleccionar candidatos dentro del rango
especificado.
2. Verificar si cada candidato es primo mediante un algoritmo eficiente, como la prueba de
divisibilidad o el método de Criba de Eratóstenes.
3. Retornar un primo aleatorio. Si no se encuentra ningún primo, manejar el caso con un
mensaje de error o devolver None.
mcd(a, b)
Descripción
Calcula el máximo común divisor (MCD) de dos números utilizando el algoritmo de
Euclides. Este concepto es crucial para verificar que el exponente público e sea coprimo con ϕ(n).
Pasos
5
1. Si b = 0, entonces mcd(a, b) = a.
2. Si no, realizar mcd(a, b) = mcd(b, a%b) de manera recursiva.
inverso_modular(e, n)
Descripción
Calcula el inverso modular de e módulo n usando el algoritmo extendido de Euclides. Esto
resuelve la ecuación e⋅d ≡ 1 (mod n), donde d es la clave privada.
Pasos
1. Usar el algoritmo extendido de Euclides para encontrar valores x y y tales que e⋅x + n⋅y = 1.
2. Retornar x mod n, que es el inverso modular.
generar_llaves(rango_inferior, rango_superior)
Descripción
Genera el par de claves pública y privada necesarias para el sistema RSA. Define el
esquema criptográfico de RSA, permitiendo encriptar y desencriptar.
Pasos
1. Generar dos números primos p y q.
2. Calcular n = p⋅q y ϕ(n) = (p−1)⋅(q−1).
3. Elegir un e coprimo con ϕ(n) y calcular d usando inverso_modular.
4. Retornar:
o Clave pública: (e, n).
o Clave privada: (d, n).
encriptar(mensaje, llave_publica)
Descripción
Encripta un mensaje usando la clave pública.
Pasos
1. Convertir el mensaje a un número entero M.
2. Calcular C = M^e mod n usando la clave pública (e, n)
6
desencriptar(caracter_encriptado, llave_privada)
Descripción
Desencripta un mensaje cifrado usando la clave privada.
Pasos
1. Calcular M=C^d mod n con (d,n).
Resultados
Número Prueba Mensaje Original Mensaje Encriptado Resultado Esperado Prueba Exitosa
1 2921 2795 2921 Sí
2 3589 3434 3589 Sí
3 200 55 200 Sí
Los resultados de funcionamiento detallados se encuentran apéndices, donde se ilustra el
flujo del proceso para encriptar y desencriptar el mensaje original.
Manejo de Errores
El código maneja diversos errores, como si el mensaje original no está dentro del rango de
la llave generada.
También maneja errores donde el mensaje original pueda ser un número negativo, letras,
caracteres o números decimales.
7
El sistema implementa un manejo de errores que valida todas las entradas antes de
procesarlas, garantizando que el mensaje original esté dentro del rango válido n-1, sin embargo,
se le instruye al usuario utilizar una clave de al menos n-2 para evitar que sea de fácil
desencriptación y que este sea un número entero.
Rechaza valores fuera de rango, números negativos, decimales, letras, caracteres especiales
o cualquier entrada no numérica, mostrando mensajes de error claros y específicos para guiar al
usuario hacia una entrada correcta. De esta manera se asegura confiabilidad al procesar solo datos
válidos.
Conclusiones
La implementación práctica del sistema RSA nos permitió no solo profundizar en los
fundamentos teóricos de este método de cifrado, sino también experimentar su funcionamiento de
manera tangible. A través de este proyecto, logramos comprender mejor conceptos avanzados de
teoría de números, como la generación de números primos, la función totiente de Euler y el cálculo
de inversos modulares, que son esenciales para el desarrollo y seguridad de sistemas criptográficos.
Estos conceptos, que pueden parecer abstractos en un contexto teórico, cobraron vida cuando los
aplicamos directamente al proceso de generación de claves y cifrado.
Además, este proyecto fue una excelente oportunidad para mejorar nuestras habilidades de
programación, especialmente en el uso de Python para implementar algoritmos matemáticos. A lo
largo del proceso, fue necesario traducir complejas operaciones matemáticas en varias funciones
reutilizables que permitieran un manejo adecuado de las claves y los mensajes. Esta experiencia
también nos permitió reflexionar sobre la importancia de la criptografía en la seguridad digital,
destacando su relevancia en la protección de datos sensibles en sistemas más complejos y en
aplicaciones reales.
El sistema RSA que implementamos cumplió con las expectativas y objetivos planteados
al inicio del proyecto. La capacidad de encriptar y desencriptar mensajes funcionó correctamente
en todos los casos de prueba, lo que nos permitió confirmar que la lógica matemática detrás del
algoritmo estaba implementada de manera precisa. Además, el sistema garantizó la consistencia
de los mensajes tanto en su versión encriptada como en la desencriptada. También logramos
incorporar un manejo robusto de errores, lo que contribuyó a hacer el sistema más confiable al
8
validar adecuadamente las entradas de los usuarios y asegurar que los mensajes estuvieran dentro
del rango esperado para su procesamiento.
Un aspecto clave del proyecto fue la implementación del algoritmo de Euclides extendido
para calcular el inverso modular, una operación fundamental en la generación de claves RSA. Este
proceso requirió un análisis detallado y cuidadoso para evitar errores lógicos, lo que nos permitió
validar iterativamente los resultados y asegurar que el algoritmo funcionara correctamente en todas
las situaciones. La capacidad de depurar y verificar cada paso del cálculo fue crucial para
garantizar la integridad del sistema.
Finalmente, uno de los desafíos adicionales fue la optimización del rendimiento en etapas
críticas del proceso, como la generación de claves. Al principio, la generación de números primos
y el cálculo de las claves para rangos de números grandes eran relativamente lentos. Sin embargo,
mediante la optimización de los algoritmos utilizados, logramos equilibrar de manera efectiva la
seguridad del sistema con su eficiencia. Esta mejora no solo hizo el proceso más rápido, sino que
también permitió que el sistema fuera escalable, manteniendo la fiabilidad y robustez necesarias
para aplicaciones más complejas.
Referencias
Stallings, W. (2017). Cryptography and network security: Principles and practice (7th
ed.). Pearson.
Katz, J., & Lindell, Y. (2014). Introduction to modern cryptography (2nd ed.). CRC Press.
Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures
and public-key cryptosystems. Communications of the ACM, 21(2), 120–126.
https://doi.org/10.1145/359340.359342
Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on
Information Theory, 22(6), 644–654. https://doi.org/10.1109/TIT.1976.1055638
Python Software Foundation. (2024). Python documentation (version 3.11).
https://docs.python.org/3/
Lutz, M. (2013). Learning Python (5th ed.). O'Reilly Media.
9
Schneier, B. (2015). Cryptography engineering: Design principles and practical
applications (2nd ed.). Wiley.
Khan Academy. (n.d.). RSA encryption. Khan Academy.
https://www.khanacademy.org/computing/computer-science/cryptography
Python Cryptography Toolkit. (n.d.). Cryptography and RSA.
https://cryptography.io/en/latest/
Python for Security. (2018). Understanding RSA encryption in Python.
https://www.pythonforsecurity.com/rsa-encryption-tutorial/
Anexos
Figura 1. Prueba con mensaje original 2921.
Figura 2. Prueba con mensaje original 3589.
Figura 2. Prueba con mensaje original 200.
