• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.55.2020.tde-06012020-171245
Documento
Autor
Nombre completo
Marcela Lopes Alves
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2019
Director
Tribunal
Bruno, Odemir Martinez (Presidente)
Martinez, Alexandre Souto
Mattos, Sérgio Henrique Vannucchi Leme de
Silva, Tiago Pereira da
Título en inglés
Classification of pseudo-random number generators by complex networks and computational geometry analysis
Palabras clave en inglés
Complex networks
Complex systems
Computational geometry
Randomness
Resumen en inglés
Randomness has stimulated mankinds attention and imagination ever since we began to observe the behavior of nature. It was by understanding the randomness and patterns that humans learned to control crops, for example, which led to the creation of the first communities. In the modern world, with the aim of mimicking the randomness of natural phenomena, computers are used to generate sequences that look as random as possible running pseudo-random number generators (PRNG). PRNGs have diverse applications in information security, digital games, simulations, modeling, gambling, arts, among others. Despite this fact, existing methods of randomness measure do not offer a definitive solution to the need of classifying PRNGs. The main methods of randomness measurement consist of statistical tests through which the sequences generated by the algorithms are analyzed. Once PRNGs are analyzed by these test suits, they are considered (un)satisfactory random. This paper explores an aspect that has been neglected in statistical tests: the spatial distribution of pseudo-random sequences. It is conjectured that this distribution is the source of undisclosed patterns in test suites. One way to study this arrangement more depth is using models that explore the relation of values and iterations. The relation of elements in space has to be the basis of the paradigm. This work applies theory of graphs and computational geometry methods to find patterns in pseudo-random sequences. The analyzed sequences are plotted in a Cartesian plan generating a set of points that are converted into graphs considering the Euclidean distance between the points within a radius. The best combination of descriptors formed by measurements of graphs and geometric properties is selected. When patterns emerge, one can point out flaws in the widely used methods for measuring PRNGs quality. It is intended to suggest a complementary approach for the evaluation of PRNGs, contributing to a better classification of the PRNGs and, consequently, to cause improvements in the studies on information security. This includes identifying patterns in sequences generated by algorithms that are considered pseudo-random by current statistical tests and thus identifying the limitations of these assessments.
Título en portugués
Classificação de geradores de números pseudoaleatórios aplicando análise de redes complexas e geometria computacional
Palabras clave en portugués
Aleatoriedade
Geometria computacional
Redes complexas
Sistemas complexos
Resumen en portugués
A aleatoriedade tem estimulado a atenção e a imaginação da humanidade desde que começamos a observar o comportamento da natureza. Foi entendendo a aleatoriedades e padrões, que os humanos aprenderam a controlar colheitas, por exemplo, o que levou a criação das primeiras comunidades. No mundo moderno, com o objetivo de imitar a aleatoriedade dos fenômenos naturais, os computadores são usados para gerar sequências que sejam as mais aleatórias possível executando os geradores de números pseudoaleatórios (PRNGs). A pseudoaleatoriedade possui diversas aplicações em segurança da informação, jogos digitais, simulações, modelagem, jogos de azar, artes, entre outros. Apesar disso, os métodos existentes de medida de aleatoriedade não oferecem uma solução definitiva para a necessidade de classificar PRNGs. Os principais métodos de medida de aleatoriedade consistem em testes estatísticos através dos quais as sequências geradas pelos algoritmos são analisadas. Uma vez que PRNGs são analisados por estes testes, eles são considerados ou não satisfatoriamente aleatórios. Este trabalho explora um aspecto que tem sido negligenciado nos testes estatísticos: a distribuição espacial das sequências pseudoaleatórias. É conjecturado que essa distribuição seja fonte de padrões não revelados nas suítes de teste. Uma maneira de estudar esse arranjo com mais profundidade é usando modelos que exploram a relação de valores e as iterações. A relação dos elementos no espaço deve ser a base do paradigma. Este trabalho aplica teoria de grafos e métodos de geometria computacional para encontrar padrões em sequências pseudoaleatórias. As sequências analisadas são plotadas em um plano Cartesiano gerando um conjunto de pontos que são convertidos em grafos considerando a distância euclidiana entre os pontos dentro de um raio. A melhor combinação de descritores formados pelas medidas de grafos e propriedades geométricas é selecionada. Quando os padrões emergirem, pode-se apontar falhas nos métodos amplamente utilizados para classificação de PRNGs. Pretende-se sugerir uma abordagem complementar para a avaliação de PRNGs, contribuindo para uma melhor classificação dos PRNGs e, consequentemente, causar melhorias nos estudos sobre segurança da informação. Isso inclui identificar padrões em sequências geradas por algoritmos que são considerados pseudoaleatórios pelos testes estatísticos atuais e, assim, identificar as limitações dessas avaliações.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2020-01-06
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.