Obtenção e conversão de números aleatórios.

Existem duas maneiras principais de obter números aleatórios:

1) Os números aleatórios são gerados por um anexo eletrônico especial (sensor de números aleatórios) instalado no computador. A implementação deste método quase não requer operações adicionais além do acesso ao sensor de números aleatórios.

2) Método algorítmico - baseado na geração de números aleatórios na própria máquina por meio de um programa especial. A desvantagem desse método é o consumo adicional de tempo do computador, pois neste caso a própria máquina realiza as operações do decodificador eletrônico.

Um programa para gerar números aleatórios usando uma determinada lei de distribuição pode ser complicado. Portanto, números aleatórios com uma determinada lei de distribuição geralmente não são obtidos diretamente, mas pela transformação de números aleatórios que possuem alguma distribuição padrão. Muitas vezes esta distribuição padrão é a distribuição uniforme (fácil de obter e fácil de converter para outras leis).

É mais vantajoso obter números aleatórios com uma lei uniforme usando um decodificador eletrônico, que libera o computador de custos adicionais tempo da máquina. Obter uma distribuição puramente uniforme em um computador é impossível devido à natureza limitada da grade de bits. Portanto, em vez de um conjunto contínuo de números no intervalo (0, 1), um conjunto discreto de números é usado 2n números, onde n– profundidade de bits da palavra de máquina.

A lei de distribuição de tal população é chamada quase uniforme . No n³20, as diferenças entre as leis uniformes e quase-uniformes tornam-se insignificantes.

Para obter números aleatórios quase uniformes, são usados ​​​​2 métodos:

1) geração de números aleatórios usando um decodificador eletrônico modelando alguns processos aleatórios;

2) obtenção de números pseudoaleatórios por meio de algoritmos especiais.

Para receber n Número aleatório binário de dígitos, o primeiro método simula uma sequência de variáveis ​​​​aleatórias independentes z eu, assumindo o valor 0 ou 1. A sequência resultante é 0 e 1, se a considerarmos como um número fracionário, e representa uma variável aleatória de distribuição quase uniforme no intervalo (0, 1). Os métodos de hardware para obter esses números diferem apenas na forma como obtêm a implementação z eu.

Um dos métodos baseia-se na contagem do número de partículas radioativas durante um determinado período de tempo Dt, se o número de partículas estiver além Dt mesmo, então z eu=1 , e se for estranho, então z eu=0 .

Outro método utiliza o efeito de ruído de um tubo de vácuo. Registrando o valor da tensão de ruído em determinados momentos eu, obtemos os valores das variáveis ​​​​aleatórias independentes você(t eu), ou seja tensão (Volts).

Magnitude z eu determinado por lei:

Onde um– um determinado valor da tensão limite.

Magnitude um geralmente selecionado a partir da condição:

Imperfeição método de hardwareé que não permite a utilização do método de execução dupla para controlar o funcionamento do algoritmo de resolução de qualquer problema, uma vez que execuções repetidas não conseguem obter os mesmos números aleatórios.

Pseudoaleatório números de telefone gerados em um computador usando programas especiais método recorrente: cada número aleatório é obtido do anterior por meio de transformações especiais.

A mais simples dessas transformações é a seguinte. Que haja algum n– bit número binário do intervalo nО (0, 1). Vamos resolver isso e obtemos 2n número de dígito. Vamos destacar as médias n descargas. Obtido desta forma n– o dígito número será o novo valor do número aleatório. Nós quadramos novamente, etc. Esta sequência é pseudoaleatória porque do ponto de vista teórico, não é aleatório.

A desvantagem dos algoritmos recorrentes é que sequências de números aleatórios podem degenerar (por exemplo, receberemos apenas uma sequência de zeros ou uma sequência de uns, ou pode aparecer periodicidade).

PRNGs determinísticos

Nenhum algoritmo determinístico pode gerar números completamente aleatórios; ele só pode aproximar algumas propriedades dos números aleatórios. Como disse John von Neumann: “ qualquer pessoa que tenha uma fraqueza por métodos aritméticos de obtenção de números aleatórios é pecadora, sem qualquer dúvida».

Qualquer PRNG com recursos limitados, mais cedo ou mais tarde, entra em ciclos - começa a repetir a mesma sequência de números. A duração dos ciclos PRNG depende do próprio gerador e tem uma média de cerca de 2n/2, onde n é o tamanho do estado interno em bits, embora os geradores lineares congruentes e LFSR tenham ciclos máximos da ordem de 2n. Se um PRNG puder convergir para ciclos muito curtos, o PRNG se tornará previsível e inutilizável.

A maioria dos geradores aritméticos simples, embora muito rápidos, apresentam muitas desvantagens sérias:

• O período/períodos são muito curtos.
• Os valores consecutivos não são independentes.
• Alguns bits são "menos aleatórios" que outros.
• Distribuição unidimensional desigual.
• Reversibilidade.

Em particular, o algoritmo do mainframe revelou-se muito pobre, o que levantou dúvidas sobre a validade dos resultados de muitos estudos que utilizaram este algoritmo.

PRNG com fonte de entropia ou RNG

Assim como existe a necessidade de gerar sequências de números aleatórios facilmente repetíveis, também existe a necessidade de gerar números completamente imprevisíveis ou simplesmente completamente aleatórios. Esses geradores são chamados geradores de números aleatórios(RNG - Inglês) gerador de números aleatórios, RNG). Como esses geradores são mais frequentemente usados ​​para gerar chaves simétricas e assimétricas exclusivas para criptografia, eles são mais frequentemente construídos a partir de uma combinação de um PRNG criptograficamente forte e uma fonte externa de entropia (e é precisamente essa combinação que agora é comumente entendida como um RNG).

Quase todos os principais fabricantes de chips fornecem RNGs de hardware com várias fontes entropia usando vários métodos para livrá-los da previsibilidade inevitável. No entanto, em no momento a velocidade com que os números aleatórios são coletados por todos os microchips existentes (vários milhares de bits por segundo) não corresponde à velocidade dos processadores modernos.

Em computadores pessoais, os autores de software RNGs usam fontes de entropia muito mais rápidas, como ruído placa de som ou contador de ciclos do processador. Antes de ser possível ler os valores do contador do relógio, a coleta de entropia era o ponto mais vulnerável do RNG. Este problema ainda não está totalmente resolvido em muitos dispositivos (por exemplo, cartões inteligentes), que permanecem vulneráveis. Muitos RNGs ainda usam métodos tradicionais (desatualizados) de coleta de entropia, como medir reações do usuário (movimento do mouse, etc.), como, por exemplo, ou interação entre threads, como em Java seguro aleatório.

Exemplos de RNG e fontes de entropia

Alguns exemplos de RNGs com suas fontes e geradores de entropia:

	Fonte de entropia	PRNG	Vantagens	Imperfeições
/dev/random no Linux	Contador de clock da CPU, porém coletado apenas durante interrupções de hardware	LFSR, com hash de saída via	Ele “aquece” por muito tempo, pode “ficar preso” por muito tempo ou funciona como um PRNG ( /dev/urandom)
Yarrow por Bruce Schneier	Métodos tradicionais (desatualizados)	AES-256 e	Design flexível e resistente a criptografia	Demora muito para “aquecer”, estado interno muito pequeno, depende muito da força criptográfica dos algoritmos selecionados, lento, aplicável exclusivamente para geração de chaves
Gerador por Leonid Yuryev	Ruído da placa de som	?	Provavelmente uma fonte boa e rápida de entropia	Nenhum PRNG independente e conhecido com criptografia forte, disponível exclusivamente como Windows
Microsoft		Integrado ao Windows, não fica preso	Estado interno pequeno, fácil de prever
	Comunicação entre threads		Ainda não há outra escolha em Java, há um grande estado interno	Coleta lenta de entropia
Caos por Ruptor	Contador do clock do processador, coletado continuamente	Hashing do estado interno de 4.096 bits com base em uma variante não linear do gerador Marsaglia	Até que o mais rápido de todos, o grande estado interno, fique “preso”
RRAND do Ruptor	Contador de clock do processador	Criptografando o estado interno com uma cifra de fluxo	Muito rápido, estado interno de tamanho arbitrário para escolher, sem “travamento”

PRNG em criptografia

Um tipo de PRNG são os PRBGs - geradores de bits pseudo-aleatórios, bem como várias cifras de fluxo. PRNGs, como cifras de fluxo, consistem em um estado interno (geralmente variando em tamanho de 16 bits a vários megabytes), uma função para inicializar o estado interno com uma chave ou semente(Inglês) semente), funções de atualização de estado interno e funções de saída. PRNGs são divididos em aritmética simples, criptografia quebrada e criptografia forte. Seu objetivo geral é gerar sequências de números que não podem ser distinguidas do aleatório por métodos computacionais.

Embora muitos PRNGs fortes ou cifras de fluxo ofereçam muito mais números "aleatórios", tais geradores são muito mais lentos que os geradores aritméticos convencionais e podem não ser adequados para qualquer tipo de pesquisa que exija que o processador esteja livre para cálculos mais úteis.

Para fins militares e condições de campo Apenas PRNGs (cifras de fluxo) criptográficas fortes e secretas não são usadas; Exemplos de PRNGs criptograficamente fortes bem conhecidos são ISAAC, SEAL, Snow, o algoritmo teórico muito lento de Blum, Blum e Shub, bem como contadores com funções hash criptográficas ou cifras de bloco criptograficamente fortes em vez de uma função de saída.

Equipamento PRNG

Além dos geradores LFSR legados e bem conhecidos que foram amplamente utilizados como PRNGs de hardware no século 20, infelizmente, muito pouco se sabe sobre PRNGs de hardware modernos (cifras de fluxo), uma vez que a maioria deles foi desenvolvida para fins militares e é mantida em segredo. . Quase todos os PRNGs de hardware comercial existentes são patenteados e também mantidos em segredo. PRNGs de hardware são limitados por requisitos estritos de memória consumível (na maioria das vezes o uso de memória é proibido), velocidade (1-2 ciclos de clock) e área (várias centenas de FPGA - ou

Devido à falta de PRNGs de bom hardware, os fabricantes são forçados a usar cifras de bloco muito mais lentas, mas bem conhecidas, disponíveis (Computer Review No. 29 (2003)

Yuri Merda. Curso “Problemas modernos de criptografia” Aula 9: Geradores pseudoaleatórios

L. Barash. Algoritmo AKS para verificar números quanto a primalidade e procurar constantes geradoras de números pseudoaleatórios

Zhelnikov Vladimir. Sequências pseudo-aleatórias de números // Criptografia do papiro ao computador M.: ABF, 1996.

random.org (inglês) - serviço online para geração de números aleatórios

Números Aleatórios Criptográficos

Teoria e Prática da Geração de Números Aleatórios

Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Análise do Gerador de Números Aleatórios do Linux

Um conjunto de testes estatísticos para geradores de números aleatórios e pseudo-aleatórios para aplicações criptográficas NIST SP 800-22

19/09/2017, terça, 13h18, horário de Moscou , Texto: Valeria Shmyrova

A empresa Security Code, desenvolvedora do complexo criptográfico Continent, recebeu a patente de um sensor biológico de números aleatórios. Este é justamente um sensor biológico, já que a aleatoriedade se baseia na reação do usuário à imagem que lhe é mostrada. A empresa garante que tais tecnologias nunca foram patenteadas no mundo antes.

Obtenção de uma patente

A empresa Security Code recebeu uma patente para tecnologia de sensor biológico de números aleatórios. Segundo os desenvolvedores, ao criar a tecnologia, foi utilizada “uma nova abordagem para resolver o problema de geração de números aleatórios usando um computador e uma pessoa”. O desenvolvimento já é utilizado em diversos produtos, incluindo Continent-AP, Secret Net Studio, Continent TLS e Jinn, bem como na biblioteca criptográfica SCrypt.

Conforme explicaram representantes da empresa ao CNews, o trabalho no sensor já dura três anos. É composto por uma parte científica, uma parte de implementação e uma parte experimental. Três pessoas são responsáveis ​​pela parte científica da empresa; toda a equipe de programadores participou do desenvolvimento, e testes e experimentos foram realizados por toda a equipe, que soma várias centenas de pessoas.

Capacidades tecnológicas

O novo sensor pode gerar sequências aleatórias em dispositivos pessoais – não são necessários dispositivos adicionais ou complementos de hardware. Ele pode ser usado na criptografia de dados e em qualquer área onde sejam necessárias sequências binárias aleatórias. Segundo os desenvolvedores, ajuda a criar chaves de criptografia em dispositivos móveis com muito mais rapidez. Esta propriedade pode ser usada para criptografar dados ou gerar uma assinatura eletrônica.

Como explicado Alice Koreneva, analista de sistemas de “Código de Segurança”, o sensor da empresa gera sequências aleatórias com base na velocidade e precisão da resposta da mão do usuário às mudanças na imagem na tela do PC ou tablet. Um mouse ou tela sensível ao toque é usado para entrada. É assim: os círculos se movem aleatoriamente pela tela, alguns de seus parâmetros mudam com o tempo. Em alguns momentos, o usuário reage às mudanças na imagem. Levando em consideração as peculiaridades de suas habilidades motoras, isso se reflete na massa aleatória de bits.

Você pode gerar sequências de números aleatórios com base em reações humanas espontâneas

Fora da criptografia, o sensor pode ser usado para gerar números aleatórios em jogos de computador ou para selecionar os vencedores da competição.

Novidade científica

Como a empresa explicou ao CNews, muitos métodos conhecidos A construção de sensores de números aleatórios é baseada em leis e fenômenos físicos ou em algoritmos determinísticos. As sequências podem ser geradas por meio de um computador - neste caso, a instabilidade de algumas partes do computador e a incerteza da interferência do hardware são tomadas como base para a aleatoriedade.

A novidade da tecnologia do Código de Segurança reside no fato de que a fonte da aleatoriedade é a reação de uma pessoa a uma imagem mutável exibida no display do dispositivo. É por isso que o nome da invenção contém a palavra “biológico”. A empresa informa que nem ela nem a Rospatent encontraram análogos patenteados da tecnologia na Rússia ou no mundo. Contudo, em geral tais técnicas são conhecidas: por exemplo, uma sequência pode ser gerada com base em ações do usuário, tais como cliques ou movimentos do mouse ou pressionamentos de teclas no teclado.

Segundo Koreneva, a equipe de desenvolvimento analisou maneiras diferentes gerando sequências aleatórias. Como se viu, em muitos casos não existem estimativas razoáveis ​​do desempenho da geração, ou das propriedades estatísticas das sequências geradas, ou de ambos. Isto se deve à dificuldade de justificar uma tecnologia já inventada. O Código de Segurança afirma que sua pesquisa produziu estimativas razoáveis ​​da taxa de geração, foi capaz de justificar boas características probabilísticas e propriedades estatísticas e estimou a entropia contribuída pelas ações humanas.

Produtos que usam tecnologia

"Continente" é hardware pacote de software, projetado para criptografia de dados. Usado no setor público russo, por exemplo, no Tesouro. Consiste em um firewall e ferramentas para criação de VPN. Foi criado pela empresa NIP Informzashita e agora está sendo desenvolvido pela Security Code LLC.

Especificamente, o servidor de acesso “Continent” e o sistema de proteção criptográfica de informações “Continent-AP” são um módulo para acesso remoto seguro usando algoritmos GOST, e “Continent TLS VPN” é um sistema para fornecer acesso remoto seguro a aplicações web também usando GOST. algoritmos de criptografia.

Secret Net Studio é solução abrangente para proteger estações de trabalho e servidores a nível de dados, aplicações, rede, sistema operativo e periféricos, que também desenvolve o “Código de Segurança”. Jinn-Client foi projetado para proteção criptográfica de informações para criar uma assinatura eletrônica e visualização confiável de documentos, e Jinn-Server é um complexo de software e hardware para construir sistemas de gerenciamento de documentos eletrônicos legalmente significativos.

Biblioteca criptográfica SCrypt, que também usa novo sensor, foi desenvolvido pelo “Código de Segurança” para aplicação mais conveniente de algoritmos criptográficos em diversos produtos. Este é um código de programa único que foi verificado quanto a erros. A biblioteca oferece suporte a hashing criptográfico, assinatura eletrônica e algoritmos de criptografia.

O que o “Código de Segurança” faz?

"Security Code" é uma empresa russa que desenvolve software e hardware. Foi fundada em 2008. O escopo do produto é a proteção de sistemas de informação e sua conformidade com os padrões internacionais e da indústria, incluindo a proteção de informações confidenciais, incluindo segredos de estado. O “Código de Segurança” possui nove licenças do Serviço Federal de Controle Técnico e de Exportação (FSTEK) da Rússia, do Serviço Federal de Segurança (FSB) da Rússia e do Ministério da Defesa.

A equipe da empresa é composta por cerca de 300 especialistas, os produtos são vendidos por 900 parceiros autorizados em todas as regiões da Rússia e nos países da CEI. A base de clientes do Security Code inclui cerca de 32 mil organizações governamentais e comerciais.

Existem três maneiras fundamentalmente diferentes de obter números usados ​​como aleatórios: física, tabular e algorítmica.

Acredita-se que a primeira tentativa de criar um gerador físico de números aleatórios remonta a 3.500 aC. e está associado a jogo de tabuleiro senet, entretenimento social egípcio antigo. De acordo com as reconstruções modernas das regras do jogo, quatro bastões planos, um lado branco e o outro preto, foram usados ​​​​para determinar o número de pontos marcados por cada jogador e a ordem dos movimentos neste jogo. Os palitos foram lançados ao mesmo tempo e, dependendo da combinação de cores que caiu, foram determinadas possibilidades adicionais para os jogadores. No início do século XX. sequências de números aleatórios foram simuladas manualmente - usando lançamento de moeda ou dados, desdobrando cartas de jogar, roleta, retirar bolas de uma urna, etc. Sensores físicos (hardware) modernos são dispositivos especiais que geram números aleatórios com base na conversão de ruído aleatório de origem natural ou artificial (ruído térmico, efeito de tiro em tubos de vácuo, decaimento radioativo etc.). Por exemplo, um carro ERNIE 4 (equipamento indicador eletrônico de números aleatórios),

• 1 Às vezes, embora raramente, a distribuição especificada pela tabela 0 1 ... 8 9 é considerada padrão
• 0,1 0,1 ... 0,1 0,1/, que determina os números vencedores da loteria britânica mensal, usa ruído térmico de transistores como fonte de variáveis ​​aleatórias. Você método físico A obtenção de uma sequência de números aleatórios apresenta características que são desvantagens para o modelo de simulação. Estas incluem, em primeiro lugar, a necessidade de medidas especiais para garantir a estabilidade da fonte do sinal convertido em números aleatórios e a impossibilidade de reproduzir a sequência resultante de números aleatórios.

Tabelas de números aleatórios são removidas as deficiências mencionadas. Vamos explicar o que significa uma tabela de números aleatórios. Vamos supor que implementamos N experimentos independentes, como resultado dos quais obtiveram números aleatórios a, a 2, osdg. Escrever esses números (na ordem de aparecimento e na forma de uma tabela retangular) resultará no que é chamado de tabela de números aleatórios. É usado da seguinte forma. Durante os cálculos, podemos precisar de um dígito aleatório ou de um número aleatório. Se for necessário um número aleatório, podemos pegar qualquer número desta tabela. O mesmo se aplica ao caso de um número inteiro aleatório - para cada dígito você pode escolher qualquer dígito. Se precisarmos de um número aleatório 0 k dos próximos dígitos сс, e 2 , ос/, e assumirmos que 8 = (Hoco^.-.o^. Neste caso, no caso de uma tabela “ideal” de dígitos aleatórios , podemos selecionar dígitos dele aleatoriamente, possivelmente em uma linha, você pode usar qualquer algoritmo de seleção que não dependa dos valores dos números da tabela, começar de qualquer lugar da tabela, ler em qualquer direção.

As primeiras tabelas de números aleatórios foram obtidas por meio de roletas. Essas tabelas foram publicadas diversas vezes em forma de livro. Uma das tabelas mais famosas, publicada em 1927, continha mais de 40.000 números aleatórios “extraídos aleatoriamente dos relatórios do censo”.

Antecedentes históricos

Leonard Tippett (Leonard Henry Caleb Tippett, 1902-1985) - estatístico inglês, aluno de K. Pearson e R. Fisher. Em 1965-1966 - Presidente da Royal Statistical Society. Alguns resultados importantes na teoria dos valores extremos estão associados ao seu nome, por exemplo, a distribuição de Fisher-Tippett e o teorema de Fisher-Tippett-Gnedenko.

Mais tarde, foram projetados dispositivos especiais (máquinas) que geravam números aleatórios mecanicamente. A primeira máquina desse tipo foi usada em 1939 por M. J. Kendall e B. Babington-Smith para criar tabelas contendo 100 mil dígitos aleatórios. Em 1955 a empresa Corporação Rand publicou as conhecidas tabelas contendo um milhão de dígitos aleatórios obtidos por outra máquina deste tipo. Aplicação Prática tabelas de números aleatórios estão atualmente limitadas, via de regra, a problemas em que são utilizados métodos de seleção aleatória

amostras, por exemplo, em estudos sociológicos ou na realização de controle estatístico de aceitação da qualidade de produtos individuais para diversos fins.

Isso é interessante

Na Rússia, está em vigor GOST 18321-73 (ST SEV 1934-79), que estabelece as regras para seleção de unidades de produtos na amostra ao realizar controle de qualidade de aceitação estatística, métodos estatísticos de análise e regulação processos tecnológicos para todos os tipos de produtos individuais para fins industriais e técnicos e bens de consumo. Afirma, em particular, que na seleção de unidades de produtos para a amostra, “são utilizadas tabelas de números aleatórios de acordo com ST SEV 546-77”.

aplique repetidamente; todos os números são fáceis de reproduzir; e o fornecimento de números nessa sequência é limitado. No entanto, uma sequência de números pseudoaleatórios tem vantagem óbvia antes da tabela: existir fórmulas simples para calcular um número pseudoaleatório, enquanto apenas 3-5 comandos são gastos na obtenção de cada número, e o programa de cálculo ocupa apenas algumas células na unidade.

Existem muitos algoritmos para obtenção de sequências de números pseudoaleatórios; implementações de tais algoritmos, chamados sensores (geradores) de números pseudoaleatórios, são descritas com algum detalhe na literatura especializada. Vamos indicar vários dos algoritmos mais conhecidos.

• Tippett L. Números de amostragem aleatória. Londres: Cambridge University Press, 1927.
• Veja: Knuth D. E. A Arte da Programação. 3ª edição. M.: Williams, 2000. T. 2. cap. 3.Números aleatórios.

É proposta uma abordagem para a construção de um sensor biológico de números aleatórios projetado para gerar sequências aleatórias em um computador ou tablet a uma velocidade de várias centenas de bits por minuto. A abordagem é baseada no cálculo de uma série de quantidades associadas à reação aleatória do usuário a um processo pseudo-aleatório exibido na tela do computador. O processo pseudo-aleatório é implementado como o aparecimento e movimento curvilíneo de círculos na tela dentro de uma determinada área específica.

Introdução

A relevância dos problemas associados à geração de sequências aleatórias (RS) para aplicações criptográficas se deve à sua utilização em sistemas criptográficos para geração de informações chaves e auxiliares. O próprio conceito de aleatoriedade tem raízes filosóficas, o que indica a sua complexidade. Em matemática, existem diferentes abordagens para definir o termo “aleatoriedade”; a sua visão geral é apresentada, por exemplo, no nosso artigo “Os acidentes não são aleatórios?” . As informações sobre abordagens conhecidas para definir o conceito de “aleatoriedade” estão sistematizadas na Tabela 1.

Tabela 1. Abordagens para determinar a aleatoriedade

Nome da abordagem	Autores	A essência da abordagem
Freqüência	von Mises, Igreja, Kolmogorov, Loveland	Na joint venture, deve ser observada a estabilidade da frequência de ocorrência dos elementos. Por exemplo, os sinais 0 e 1 devem ocorrer de forma independente e com probabilidades iguais não apenas no SP binário, mas também em qualquer uma de suas subsequências, escolhidas aleatoriamente e independentemente das condições iniciais de geração.
Complexo	Kolmogorov, Chaitin	Qualquer descrição da implementação de uma joint venture não pode ser significativamente mais curta do que a própria implementação. Ou seja, o SP deve ter uma estrutura complexa e a entropia de seus elementos iniciais deve ser elevada. Uma sequência é aleatória se sua complexidade algorítmica estiver próxima do comprimento da sequência.
Quantitativo	Martin-Lof	Divisão espaço de probabilidade sequências em não aleatórias e aleatórias, ou seja, em sequências que “falham” e “passam” em um conjunto de testes específicos projetados para identificar padrões.
Criptográfico	Abordagem moderna	Uma sequência é considerada aleatória se a complexidade computacional da busca por padrões não for menor que um determinado valor.

Ao estudar as questões de síntese de um sensor biológico de números aleatórios (doravante denominado BioRSN), é aconselhável levar em consideração próxima condição: uma sequência é considerada aleatória se for comprovada a aleatoriedade da fonte física, em particular, a fonte é localmente estacionária e produz uma sequência com determinadas características. Esta abordagem para a definição de aleatoriedade é relevante na construção de um BioDSCh, podendo ser condicionalmente chamada de “física”. O cumprimento das condições determina a adequação da sequência para uso em aplicações criptográficas.
Conhecido várias maneiras gerar números aleatórios em um computador, envolvendo o uso de ações significativas e inconscientes do usuário como fonte de aleatoriedade. Tais ações incluem, por exemplo, pressionar teclas do teclado, mover ou clicar com o mouse, etc. A medida de aleatoriedade da sequência gerada é a entropia. A desvantagem de muitos métodos conhecidos é a dificuldade de estimar a quantidade de entropia obtida. Abordagens relacionadas à medição das características dos movimentos humanos inconscientes permitem obter uma fração relativamente pequena de bits aleatórios por unidade de tempo, o que impõe certas restrições ao uso de sequências geradas em aplicações criptográficas.

Processo pseudo-aleatório e tarefa do usuário

Vamos considerar a geração de SP usando reações significativas do usuário a algum processo pseudo-aleatório bastante complexo. A saber: em momentos aleatórios no tempo, são medidos os valores de um determinado conjunto de grandezas que variam no tempo. Os valores aleatórios das quantidades do processo são então representados como uma sequência aleatória de bits. Os recursos do aplicativo criptográfico e do ambiente operacional determinaram uma série de requisitos para o BioDSCh:

1. As sequências geradas devem ter características estatísticas próximas às sequências aleatórias ideais, em particular, polaridade ( frequência relativa"1") da sequência binária deve estar próximo de 1/2.
2. Durante a implementação do processo pelo usuário médio, a velocidade de geração deve ser de pelo menos 10 bits/seg.
3. A duração da geração pelo usuário médio de 320 bits (que corresponde no algoritmo GOST 28147-89 à soma do comprimento da chave (256 bits) e do comprimento da mensagem de sincronização (64 bits)) não deve exceder 30 segundos.
4. Facilidade de uso pelo usuário com o programa BioDSCh.

Descrevemos o princípio de construção da classe BioDSCh em consideração. Chamaremos de área de trabalho um retângulo localizado no centro da tela de um computador pessoal ou tablet e ocupando a maior parte da tela para fornecer ao usuário uma análise visual conveniente do processo. No centro da área de trabalho, N círculos de diâmetro d são gerados sequencialmente em intervalos de tempo de fração de segundo, a partir de onde iniciam o movimento retilíneo em diferentes direções. A direção do movimento do i-ésimo círculo, gerado no momento do i-ésimo clique do usuário (no caso de um tablet, um toque com o dedo), é determinada pela direção do “vetor de saída do círculo”, invisível para o usuário, no mesmo momento, que gira uniformemente a uma determinada velocidade em torno do centro da área de trabalho, i=1,…,N.
Os círculos se movem como projeções de bolas em uma mesa de bilhar, quando colidem, são refletidos uns nos outros e nos limites da área de trabalho, muitas vezes mudando a direção do movimento e simulando um processo geralmente caótico de movimento dos círculos ao longo do trabalho área (Fig. 1).

Figura 1. Trajetórias de movimento dos centros do círculo dentro da área de trabalho

A tarefa do usuário é gerar M bits aleatórios. Após o último círculo aparecer na área de trabalho, o usuário deve remover rapidamente todos os N círculos móveis clicando em sequência aleatória na área de cada círculo com o mouse (no caso de um tablet, com o dedo). A sessão de geração de um determinado número de bits SP termina após a exclusão de todos os círculos. Se o número de bits gerados em uma sessão não for suficiente, a sessão é repetida quantas vezes forem necessárias para gerar M bits.

Quantidades medidas de processo

A geração de SP é realizada medindo uma série de características do processo pseudo-aleatório descrito em tempos aleatórios determinados pela reação do usuário. A taxa de geração de bits é maior quanto mais características independentes forem medidas. A independência das características medidas significa a imprevisibilidade do valor de cada característica de acordo com valores conhecidos outras características.
Observe que cada círculo que se move na tela é numerado, dividido em 2 k setores iguais invisíveis ao usuário, numerados de 0 a 2 k -1, onde k é um número natural e gira em torno de seu centro geométrico com uma determinada velocidade angular. O usuário não vê a numeração dos círculos e setores do círculo.
No momento de entrar no círculo (clique ou toque bem-sucedido com o dedo), são medidas uma série de características do processo, as chamadas fontes de entropia. Deixe a i denotar o ponto de impacto i-ésimo círculo, i=1,2,... Então é aconselhável incluir entre as grandezas medidas:

• Coordenadas X e Y do ponto ai;
• distância R do centro do círculo ao ponto a i;
• número do setor dentro do i-ésimo círculo contendo o ponto a i ;
• número do círculo, etc.

Os valores medidos são convertidos em uma representação binária, cujos elementos são então filtrados quando incluídos na sequência de bits resultante.

Resultados experimentais

Para determinar os parâmetros para a implementação prioritária do BioDSCh, foram realizadas cerca de 10 4 sessões por diferentes performers. Os experimentos realizados permitiram determinar as áreas valores adequados para os parâmetros do modelo BioDSCh: dimensões da área de trabalho, número e diâmetro dos círculos, velocidade de movimento dos círculos, velocidade de rotação do “vetor de partida dos círculos”, número de setores em que os círculos estão divididos, velocidade angular rotação de círculos, etc.
Ao analisar os resultados da operação do BioDSCh, foram feitas as seguintes premissas:

• os eventos registrados são independentes no tempo, ou seja, a reação do usuário ao processo observado na tela é difícil de replicar com alta precisão tanto para outro usuário quanto para o próprio usuário;
• as fontes de entropia são independentes, ou seja, é impossível prever os valores de qualquer característica a partir dos valores conhecidos de outras características;
• a qualidade da sequência de saída deve ser avaliada levando em consideração abordagens conhecidas para determinar a aleatoriedade (Tabela 1), bem como a abordagem “física”.

A avaliação dos intervalos de confiança para os valores das grandezas de processo calculadas corresponde a um nível de significância de 0,05. Para reconhecer a uniformidade da distribuição dos sinais da amostra resultante (após redução à forma binária), foi utilizado o teste qui-quadrado de concordância com distribuição uniforme.
De acordo com o comprimento das sequências binárias geradas, foi estabelecida uma limitação aceitável de sua polaridade p: |p-1/2|?b, onde b?10 -2.
O número de bits obtidos a partir dos valores das grandezas do processo medidas (fontes de entropia) foi determinado empiricamente com base na análise da entropia da informação dos valores das características consideradas. Foi estabelecido empiricamente que “remover” qualquer círculo permite obter cerca de 30 bits de uma sequência aleatória. Portanto, com os parâmetros de layout do BioDSCh usados, 1-2 sessões de operação do BioDSCh são suficientes para gerar a chave e o vetor de inicialização do algoritmo GOST 28147-89.
Direções para melhorar as características dos geradores biológicos devem estar associadas tanto à otimização dos parâmetros deste layout quanto ao estudo de outros layouts do BioDSCh.