Implementación de una aplicación para la generación de primos criptográficamente fuertes

Vista sencilla de ítem
dc.contributor.advisorZuñiga Galindo, Wilson
dc.contributor.authorSolano Gélvez, Claudia Cecilia
dc.contributor.authorPérez Manzano, Fernando Luis
dc.coverage.campusUNAB Campus Bucaramangaspa
dc.coverage.spatialBucaramanga (Santander, Colombia)spa
dc.date.accessioned2024-08-06T21:13:58Z
dc.date.available2024-08-06T21:13:58Z
dc.date.issued2001
dc.degree.nameMagíster en en Ciencias Computacionalesspa
dc.description.abstractLa siguiente tesis de investigación muestra los resultados de la implementación del algoritmo FastPríme propuesto por Ueli M. Maurer en el Journal of Criptology de Noviembre 14 de 1994. La aplicación desarrollada genera primos criptográficamente fuertes. Se constituye en una técnica constructiva y recursiva para generar primos Probables, haciendo uso de un caso especial del Teorema debido a Pocklington. Los primos pueden ser de hasta 8192 bits, útiles en un contexto criptográfico por su dificultad para ser criptoanalizados, requiriendo el conocimiento de la Teoría de Números, para resolver problemas difíciles que necesitan la utilización de computación masiva paralela y largos años de procesamiento. Estos números son lo suficientemente grandes y pueden ser usados para la generación de Certificados de Firmas digitales, para generar módulos RSA aleatorios y seguros, entre muchas otras aplicaciones.spa
dc.description.abstractenglishThe following research thesis shows the results of the implementation of the FastPrime algorithm proposed by Ueli M. Maurer in the Journal of Cryptology of November 14, 1994. The developed application generates cryptographically strong primes. It is a constructive and recursive technique to generate Probable primes, making use of a special case of the Theorem due to Pocklington. The primes can be up to 8192 bits, useful in a cryptographic context due to their difficulty to be cryptanalyzed, requiring knowledge of Number Theory, to solve difficult problems that need the use of massive parallel computing and long years of processing. These numbers are large enough and can be used for the generation of Digital Signature Certificates, to generate random and secure RSA modules, among many other applications.spa
dc.description.degreelevelMaestríaspa
dc.description.learningmodalityModalidad Presencialspa
dc.description.sponsorshipInstituto Tecnológico de Estudios Superiores de Monterrey (ITESM)spa
dc.description.tableofcontentsINTRODUCCIÓN ..................................................................................................................................................................................xiíi 1. IMPLEMENTACIÓN DE UNA APLICACIÓN PARA LA GENERACIÓN DE PRIMOS CRIPTOGRAFICAMENTE FUERTES............................................................................................................................................................................................. 1 1.1. OBJETIVO GENERAL.....................................................................................................................................................................1 1.2. OBJETIVOS ESPECÍFICOS...........................................................................................................................................................1 1.3. ALGUNAS IDEAS DE TEORÍA DE NÚMEROS.............................................................................................................................1 1.4. EL ALGORITMO DE MAURER...................................................................................................................................................... 4 1.4.1. Descripción del Algoritmo PondomPrime............................................................................................................................. 5 1.4.2. Descripción del Algoritmo FastPrime.................................................................................................................................... 9 1.4.3. Implementación del Algoritmo Fo<tPrime H...................................................................................................................... 1.5. REPUBLICADOS DEL ALGORITMO...............................................................................................................................................14 1.6. APLICACIONES.............................................................................................................................................................................17 1.7. CONCLUSIONES...........................................................................................................................................................................18 2. INTRODUCCIÓN A LA TEORÍA DE LOS NÚMEROS Y CRIPTOGRAFÍA ..................................................................................20 2.1. INTRODUCCIÓN........................................................................................................................................................................... 20 2.1.1. Divisibilidad y Primos.......................................................................................................................................................... 21 2.1.2. Aritmética Modular..............................................................................................................................................................28 2.2. TEORÍA DE NÚMEROS Y CRIPTOGRAFÍA............................................................................................................................... 35 2.2.1. Terminología........................................................................................................................................................................36 2.2.2. Cifrador de César...............................................................................................................................................................36 2.2.3. Cifrador Afín....................................................................................................................................................................... 37 2.2.4. Cifradores de Substitución.................................................................................................................................................. 37 2.2.5. Cifrador DES (Data Encryption Standard)......................................................................................................................... 37 2.2.6. Cifradores de Clave Pública...............................................................................................................................................39 2.3. TESTS DE PRIMALIDAD PROBABILÍSTICOS............................................................................................................................ 44 2.3.1. Test de Primalidad de Pseudoprimos.................................................................................................................................45 2.3.2. Test de Pseudoprimos Fuertes.......................................................................................................................................... 45 2.3.3. Algoritmo "Test de primalidad probabilístico de Rabin-Miller"............................................................................................47 2.4. TEST DE PRIMALIDAD BASADO EN EL TEOREMA DE POCKLINGTON-LEHMER................................................................47 2.4.1. Algunos Conceptos de la Aritmética de Congruencias.......................................................................................................48 2.4.2. Test de primalidad de Lucas - Lehmer...............................................................................................................................48 2.4.3. Test de primalidad de Pocklington - Lehmer....................................................................................................................... 49 3. UN ALGORITMO PARA LA GENERACIÓN DE NÚMEROS PRIMOS CRIPTOGRAFICAMENTE FUERTES ..................................... 51 3.1. BOSQUEJO DEL ALGORITMO PROPUESTO POR MAURER..................................................................................................51 3.1.1. Descripción del Algoritmo RandomPrime........................................................................................................................... 53 3.1.2. Descripción del Algoritmo FastPrime........................................................................... ......................................................59 3.2. ANALISIS DEL TIEMPO DE CORRIDA........................................................................................................................................62 3.2.1. Generación eficiente de pseudoprimos y el límite de la Prueba de división óptima........................................................ .62 3.2.2. Análisis de el procedimiento CheckLemmal....................................................................................................................... 65 4. RESULTADOS, COMENTARIOS Y CONCLUSIONES .............................................................................................................. 66 4.1. IMPLEMENTACIÓN DEL ALGORITMO.......................................................................................................................................66 4.1.1. La librería MIRACL..............................................................................................................................................................66 4.1.2. Las funciones implementadas para la aplicación Fastprime.exe........................................................................................ 67 4.1.3. Análisis del Algoritmo a través de Diagramas de Flujo de datos (DFD).............................................................................. 72 4.1.4. Detalles de compilación y construcción de la librería MTRACI y de. la aplicación Fast Prime.exe................................... 77 4.2 RESULTADOS DEL ALGORITMO..................................................................................................................................................... 80 4.3. COMENTARIOS Y CONCLUSIONES.............................................................................................................................................. 83 BIBLIOGRAFÍA .....................................................................................................................................................................................85 ANEXOS .............................................................................................................................................................................................. 07spa
dc.identifier.reponamereponame:Repositorio Institucional UNABspa
dc.identifier.repourlrepourl:https://repository.unab.edu.cospa
dc.identifier.urihttp://hdl.handle.net/20.500.12749/25936
dc.publisher.facultyFacultad Ingenieríaspa
dc.publisher.grantorUniversidad Autónoma de Bucaramanga UNABspa
dc.publisher.programMaestría en Ciencias Computacionalesspa
dc.relation.referencesADLEMAN, L. M. and HUANG, M. A. Primali+y testing and abelian varieties over finiti fields, Lecture Notes in Mathematics, VOL. 1512, Springer Verlag, 1992,spa
dc.relation.referencesADLEMAN, L. M. , POMERANCE, C. and RUMELY, R. S. On distinguishing prime numbers from composite Numbers, Annals of Mathematics, VOL. 117, 1983. pág. 173-206.spa
dc.relation.referencesBALOG, A. p+a without large prime factors. Seminaire de theorie des nombres de Bordeaux. Nro 31. 1983.spa
dc.relation.referencesCOHEN, H. y LENSTRA, A. K. Implementation of a new primality test, Mathematics of Computation, VOL. 48, Nro. 177,1987. Pp. 103-121.spa
dc.relation.referencesERDÓS, P. On the normal number of prime factors of p-1 an some related problems concerning Euler's <p-function. Quaterly Journal of Mathematics. Oxford, 1935. Vol. 6. Págs. 205-213.spa
dc.relation.referencesFRIEDLANDER, J. B, Shifted Primes without large primes factors en Number theory and applications. ed. R. A. Mallín, Kluwwer Academic Publishers, 1989.spa
dc.relation.referencesGOLDFtLD, M. On the number of primes p for which p+a has a large prime factor. Mathematika. Vol 16. 1969. Págs. 23-27.spa
dc.relation.referencesGOLDWASSER, S. y KILIAN, J. Almost all primes can be quickly certified, Proc. Of the 18,h Annual ACM Symposium on the Theory of Computing, 1986. Pp. 316- 329.spa
dc.relation.referencesHARDY, G. H. y I.ITTLEWOOD, J. E. Some Problems of 'partitio numerorum': III: on the expression of a number as a sum of primes. Acta Mathematica. Vol 44. 1922. Págs. 1-70.spa
dc.relation.referencesHOOLEY, C. On the largest prime factor of p+a. Mathematika. Vol. 20. 1973. Págs. 135- 143.spa
dc.relation.referencesKNUTH, D. E. y TRABB PARDO, L. Analysis of a simple factorization algorithm. Theoretical Computer Science. Vol. 3. 1976. pág. 321-348.spa
dc.relation.referencesKOBLITZ, N. Primality of the number of points on an elliptic curve or a finite field. Pacific Journal of Mathematics. Vol. 131. Nro 1. 1988. Págs. 157-165.spa
dc.relation.referencesKRANAKTS, E. Primality and Cryptography, Stuttgart : Te.nbner, and New York: John Wiley A Sons, 1986.spa
dc.relation.referencesKUMANDURY, Ramanujachary and ROMERO, Cristina. Number Theory with Computer Applications. Prentice Hall: Upper Saddle River, New Jersey, 1998.spa
dc.relation.referencesMAURER, Ueli M. Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters. Journal of Cryptology, Nov 14,1994.spa
dc.relation.referencesMAURER, Ueli M. Some number-theoretic conjectures and their relation to the generation of cryptographic primes en Cryptography and Coding II, C. Mitchell (ed.). Oxford University Press, 1992. pág. 173-191.spa
dc.relation.referencesMILLER, G. L. Riemann's hipothesis and tests for primality. Journal of Computer and System Sciences, VOL. 13,1976. pág. 300-317.spa
dc.relation.referencesMORAIN, F. Prime valúes of partición numbers and the primality of p (1840926), Tech, Report LIX/92/RR/11, Laboratoire d'Informatique de l’Ecole Polytechnique (LIX), F-91128 Palaiseau Cedex, FRANCE, 1992.spa
dc.relation.referencesPOCKLINGTON, H. C. The determinaron of the prime or composite nature of large numbers by Fermat's theorem. Proceedings of the Cambridge Philosophical Society. VOL. 18.1914-1916. pp 29-30.spa
dc.relation.referencesPOMERANCE, C. Popular valúes of Euler's function. Mathematika. Vol. 27. 1980. Págs. 84-89.spa
dc.relation.referencesPRATT, V. R. Every prime has a succint certifícate, SIAM Journal on Computing, VOL4,Nro 3,1975. pp 214-220.spa
dc.relation.referencesSANCHEZ, Jesús. Introducción al Análisis de Algoritmos. Editorial Trillas. 1998. Págs, 120-121.spa
dc.relation.referencesTANENBAUN, A. S. Redes de Ordenadores. Prentice- Hall Hispanoamericana, S. A. 1991. pp 586-593.spa
dc.relation.referencesWOOLbRIDGE, K. Valúes taken many times by Euler's phi-function. Proceedings of the AMS. Vol. 76. 1979. Págs. 229-234.spa
dc.relation.referenceshttp://www.swox.eom/gmp/index.html#bOWNLOAbspa
dc.relation.referencesftp://sable.ox.ac.uk/pub/math/freelip/spa
dc.relation.referenceshttp://www. i i i.de/mtommila/apfloat/spa
dc.rights.accessrightsinfo:eu-repo/semantics/openAccessspa
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 2.5 Colombia*
dc.rights.localAbierto (Texto Completo)spa
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.5/co/*
dc.subject.keywordsComputer sciencesspa
dc.subject.keywordsSystems engineerspa
dc.subject.keywordsCryptographyspa
dc.subject.keywordsNumber theoryspa
dc.subject.keywordsAlgorithmsspa
dc.subject.keywordsPrime numbersspa
dc.subject.keywordsData encryption (Computers)spa
dc.subject.lembCiencias computacionalesspa
dc.subject.lembIngeniería de sistemasspa
dc.subject.lembTeoría de los númerosspa
dc.subject.lembCifrado de datos (Computadores)spa
dc.subject.lembNúmeros primosspa
dc.subject.proposalCriptografíaspa
dc.subject.proposalAlgoritmosspa
dc.titleImplementación de una aplicación para la generación de primos criptográficamente fuertesspa
dc.title.translatedImplementation of an application for the generation of cryptographically strong primesspa
dc.type.coarhttp://purl.org/coar/resource_type/c_bdcc
dc.type.coarversionhttp://purl.org/coar/version/c_ab4af688f83e57aaspa
dc.type.driverinfo:eu-repo/semantics/masterThesis
dc.type.hasversioninfo:eu-repo/semantics/acceptedVersion
dc.type.localTesisspa
dc.type.redcolhttp://purl.org/redcol/resource_type/TM

Archivos

Bloque original

Mostrando 1 - 1 de 1
Miniatura
Nombre:
Solano Gelvez Claudia 2001.pdf
Tamaño:
29.76 MB
Formato:
Adobe Portable Document Format
Descripción:
Tesis
Descargar

Bloque de licencias

Mostrando 1 - 1 de 1
Miniatura
Nombre:
license.txt
Tamaño:
829 B
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar

Colecciones

Maestría en Ciencias Computacionales