• 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
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.55.2020.tde-06012020-171245
Document
Author
Full name
Marcela Lopes Alves
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2019
Supervisor
Committee
Bruno, Odemir Martinez (President)
Martinez, Alexandre Souto
Mattos, Sérgio Henrique Vannucchi Leme de
Silva, Tiago Pereira da
Title in English
Classification of pseudo-random number generators by complex networks and computational geometry analysis
Keywords in English
Complex networks
Complex systems
Computational geometry
Randomness
Abstract in English
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.
Title in Portuguese
Classificação de geradores de números pseudoaleatórios aplicando análise de redes complexas e geometria computacional
Keywords in Portuguese
Aleatoriedade
Geometria computacional
Redes complexas
Sistemas complexos
Abstract in Portuguese
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2020-01-06
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.