Воскресенье, 2024-05-19
Сборник компьютерных технологий
Меню сайта
Категории раздела
My articles [30]
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0
Главная » Статьи » My articles

Взлом Линейного конгруэнтного метода (LCG)

Напишем код. Положим в массив результат работы генератора

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/
Категория: My articles | Добавил: DungeonLords (2017-06-04)
Просмотров: 1271 | Теги: взлом ГПСЧ, LCG, Линейный конгруэнтный метод
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа
Поиск
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Copyright Forcer, Inc © 2024
    Бесплатный конструктор сайтов - uCoz