Descobrindo os parametros de um LCG

Uma das razões para não se utilizar geradores de números pseudo-aleatórios baseados em congruencia linear em criptografia é o fato destes serem passíveis de se descobrir os parametros de geração.

Tomarei como base o excelente artigo How to crack a Linear Congruential Generator, publicado na Reteam.org, onde o autor vale-se do efeito Marsaglia para descobrir tais parametros.

Marsaglia, renomado matemático americano, descobriu em 1968 que geradores baseados em congruencia linear geram números inteiros que formam planos hiperdimensionais quando plotados graficamente (vide imagem abaixo).

Basicamente, a solução proposta no artigo da Reteam faz uso da determinante de uma matriz tridimencional, composta por uma sequencia consecutiva de quatro números obtidos do gerador, para encontrar valores que são múltiplos do parâmetro m.

Em seguida, de posse de diversas determinantes, basta fazer um simples MDC para obter o valor correto de m.

Outra forma de calcular o MDC é usando-se o algoritmo de euclides:


function gcd(a, b)
if b = 0 return a
else return gcd(b, a mod b)


Uma vez que se tem m, pode-se obter os fatores a e c resolvendo-se um sistema de equações lineares congruenciais.

Vamos testar esse procedimento na prática.

1) Pega-se uma sequencia de números geradas pelo LCG em estudo:

S = {122, 4803, 7546, 9035, 4824, 727, 506, 2793, 7246, 2237…}

2) Da sequencia original S, pegaremos três sub-sequencias A, B e C:

A = {122, 4803, 7546, 9035}
B = {4803, 7546, 9035, 4824}
C = {7546, 9035, 4824, 727}

3) Calcula-se as determinantes de A, B e C.

Definindo-se os elementos das sub-sequencias como {a, b, c, d}, calcularemos a determinante da seguinte forma:

det = | (a * c + b * d + c * b) – (c * c + a * d + b * b) |

Assim:

det A = | (122*7546 + 4803*9035 + 7546*4803) – (7546*7546 + 122*9035 + 4803*4803) | = 554040

det B = 13767894

det C = 23832954

4) Calcula-se o MDC das determinantes.

Calculamos m = MDC(det A, det B, det C):

m = MDC( 554040, 13767894, 23832954 )

logo, usando-se o algoritmo de euclides:

m = 554040 * 13767894 mod 23832954 = 12567474
m = 23832954 mod 12567474 = 11265480
m = 12567474 mod 11265480 = 1301994
m = 11265480 mod 1301994 = 849528
m = 1301994 mod 849528 = 452466
m = 849528 mod 452466 = 397062
m = 452466 mod 397062 = 55404
m = 397062 mod 55404 = 9234

Como “55404 mod 9234 = 0”, então m é igual a “9234”.

5) Resolve-se as equações lineares para obter os parametros a e c.

Sistemas legados e números aleatórios

Recentemente precisei gerar números aleatórios em um sistema escrito em linguagem legada, no caso, o velho e confiável COBOL.

O objetivo era usar esses valores na chave primária de uma tabela, pois tinhamos como requisito que essa chave contivesse números sem significado, sorteados de tal forma que não fossem de fácil adivinhação, descartando-se assim o uso de um simples campo numérico autoincremental.

No caso, como a aplicação não precisava de primor estatístico e nem segurança criptográfica – além da linguagem não dar suporte a operadores binários – optei por implementar um simples gerador baseado em congruencia linear.

Nesse tipo de gerador, temos a seguinte relação recorrente:

O problema foi como escolher os três parâmetros de geração a, c e m de forma que possam ser processados em inteiros de 18 digitos (limitação imposta pela linguagem) e que tenha um ciclo de repetição o mais longo possível, isto é, percorra todos os números do conjunto de inteiros previamente definido antes que ocorra repetição dos elementos gerados.

Para calcular tais parâmetros, fiz uso da dica constante na própria página da wikipedia que diz como escolher valores que resultem em períodos longos de geração sem repetição.

Assim, com base no método citado no artigo, construí o roteiro abaixo (que é uma versão simplificada do roteiro original que utilizei):

1) Escolha um número máximo esperado para o numero aleatorio (MAX);
2) Procure o primeiro número PRIMO antes de: MAX / (3*3*3*3*3*2);
3) Parametro M = (PRIMO*3*3*3*3*3*2):
4) Parametro A = (PRIMO*3*2+1)
5) Definir o parametro C como 7.
6) Teste se:
6.1) A e 1 são congruentes em relação ao primo?
6.2) A e 1 são congruentes em relação a 3?
6.3) A e 1 são congruentes em relação a 2?

Vamos então a um exemplo prático.

Digamos que desejamos gerar números entre 0 e 9999, sendo que os números só devem se repetir quando não houver mais inteiros “sorteados”.

Seguindo os passos do roteiro acima temos:

1) MAX = 9999;
2) 9999 / 486 ~= 20. Nesse caso, PRIMO = 19;
3) Parametro M = (19*486) = 9234:
4) Parametro A = (19*3*2+1) = 115
5) Definir o parametro C como 7.
6) Teste se:
6.1) A e 1 são congruentes em relação ao primo? 115 mod 19 = 1.
6.2) A e 1 são congruentes em relação a 3? 115 mod 3 = 1.
6.3) A e 1 são congruentes em relação a 2? 115 mod 2 = 1.

Em sequencia, supondo-se a existencia da função LCG(a, c, m, semente_inicial), vejamos os primeiros numeros gerados com base na semente “1”:

LCG(115, 7, 9234, 1) = {122, 4803, 7546, 9035, 4824, 727, 506, 2793, 7246, 2237…}

Para atestar se o período alcançado pelos parametros calculados foi o mais longo possível, desenvolvi um pequeno programa que gera números aleatórios com base na LCG até que um número já sorteado apareça novamente (para períodos curtos, como o do exemplo, pode-se verificar isso até mesmo no MS-Excel).

Em todos os testes que fiz da LCG acima, o período foi de 9234 números até que ocorra repetição (isto é, período = m) , servindo assim para a finalidade proposta.