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.