Напишем код. Положим в массив результат работы генератора
putSeq2Array(0,5,2,32,ReferenceArray);
Где X0=0, a=5,c=2,m=32
Но если Вам выборка уже дана, самостоятельно заполните опорный массив (ReferenceArray) не вызывая процедуру генерации putSeq2Array.
Для взлома нам нужно 5ть значению из любого места псевдо-случайной последовательности. Подставим их в уравнение линейного конгруэнтного метода
XNext=(a*Xprev+c) mod m
Получим систему из 4х уравнений.
В данном примере система следующая
(a*18+c) mod m=28,
(a*28+c) mod m=14,
(a*14+c) mod m=8,
(a*8+c) mod m=10,
a>0,c>0,m>0,
a,c,m are Integer [целочисленные]
a>0,c>0,m>0, a,c,m are Integer - по условию линейного конгруэнтного метода - значит это можно штурмовать перебором. Тупой перебор, если корней не нашлось, увеличьте const Predicate вплоть до Integer.MaxValue (а может и больше). Цифры системы выше используются в теле процедуры TryFind(), будьте внимательны. Эта же процедура вызывает функцию TryUse(), которая в моём примере генерирует по найденным a,c,m и одному из корней уравнения (14) новую последовательность и сравнивает её с ReferenceArray поэлементно. В случае успеха юзеру сообщаются эти a,c,m как проверенные.
const Predicate=3000;//Integer.MaxValue;
Xfirst = 0;
var a:=1;
m:=1;
c:=1;
x1:=1;
Xprev:=0;
ReferenceArray:array of Cardinal;
CandidateArray:array of Cardinal;
procedure putSeq2Array(const ReferenceXfirst,ReferenceA:Cardinal;ReferenceC:Cardinal;ReferenceM:Cardinal;arr:array of Cardinal);
var i:Integer;
var myXNew:Integer;
begin
myXNew:=ReferenceXfirst;
for i:=0 to Length(arr)-1 do
begin
arr[i]:=myXNew;
myXNew:=(ReferenceA*myXNew+ReferenceC) mod ReferenceM;
end;
end;
function TryUse(const CandidateXfirst,CandidateA,CandidateC,CandidateM:Cardinal):Boolean;
var i,j:Integer;
begin
if ReferenceArray=nil then begin result:=false; exit; end;
SetLength(CandidateArray,Length(ReferenceArray));
putSeq2Array(CandidateXfirst,CandidateA,CandidateC,CandidateM,CandidateArray);
//CandidateArray и ReferenceArray могут начинаться с неодинаковых элементов
//попробуем найти первый одинаковый элемент, result:=false иначе
result:= false;
for i:=0 to Length(ReferenceArray)-1 do
if CandidateArray[i]=ReferenceArray[0] then
begin
for j:=i to Length(ReferenceArray)-1-i do
if CandidateArray[j]<>ReferenceArray[j-i] then begin result:=false; exit;end
else result:= true;
end;
//else begin result:=false; exit;end;
end;
procedure TryFind();
var Ci,Mi,Ai,Xprev_i:Integer;
begin
for Ci:=c to Predicate do
for Mi:=m to Predicate do
for Ai:=a to Predicate do
if (Ai*8+Ci) mod Mi = 10 then
begin
if (Ai*18+Ci) mod Mi = 28 then//if (4*Ai+Ci) mod Mi =3 then
begin
if (Ai*28+Ci) mod Mi = 14 then
begin
if (Ai*14+Ci) mod Mi =8 then//if (Ai*Xprev_i+Ci) mod Mi = 1 then writeln('of cause a='+Ai+' ,c='+Ci+' ,m= '+Mi+' ,XPrev='+XPrev_i);
if TryUse(14,Ai,Ci,Mi) then
writeln('a='+Ai+' ,c='+Ci+' ,m= '+Mi);
end;
end;
end;
end;
BEGIN
SetLength(ReferenceArray,51);
putSeq2Array(0,5,2,32,ReferenceArray);
TryFind();
END.
Источник: https://habrahabr.ru/post/132217/ |