Самое трудное – это начать, поэтому я с вашего позволения на этом вступление и закончу. ;)
Пусть есть некий генератор псевдослучайных чисел, характеризующийся некоторым периодом – обозначим его через X. Допустим также, что у нас имеется набор масок количеством Y и размерностью N (а вы надеялись на другую букву? ;-)). Каждая маска имеет несколько – L – окон. Графически это можно представить так –
|
|
|
|
|
|
|
|
|
|
В приведенном примере N = 10, L = 3. Для машинной обработки, конечно, каждую маску лучше представлять элементом массива размерностью L и содержащим информацию об удаленности окна от начала маски, в примере это 2, 5 и 7.
Для дальнейших манипуляций ограничим период используемого ГПСЧ до 2k<X и обозначим его как X0. Возьмем из имеющегося набора M1 масок, так чтобы (M1,X0)=1, т.е. M1 и X0 – взаимнопростые. Например, пусть M1 будет равно 3 и первой маской в этом наборе будет приведенная в примере. Так же договоримся , что после 2k члена последовательности X0 будет идти первый, т.е. закольцуем ее.
Теперь берем из последовательности X0 2, 5 и 7 члены (как бы накладывая маску на ряд чисел, образно выражаясь) и производим над ними некоторые действия в зависимости от фантазии разработчика. Например, можно их сложить, и ,если они находятся в интервале от 0 до 1, взять дробную часть от суммы.
Таким образом, получаем первое число новой последовательности чисел, обозначим её X1. Каждый следующий член новой последовательности получаем, сдвигая начало наложения маски на 1. Например, второй член получаем, используя вторую маску из набора и сдвигая на 1 от начала последовательности X0. Пусть окна во второй маске располагаются в позициях 3, 7, 8, тогда из последовательности X0 будут взяты 4,8 и 9 члены. После использования третьей маски берется первая и т.д.
Таким образом, получим новую последовательность X1 мощностью 2k*3, я думаю тоже псевдослучайную. Ничто не мешает нам повторить данный метод над полученной последовательностью ПСЧ еще раз (и еще много, много раз ;) ), используя имеющийся набор масок или генерируя новый – это на любителя, главное не забывать о взаимной простоте X и M. Например, возьмем M2 равное 5 и после вышеперечисленных манипуляций получим X2 мощностью 2k*3*5 и т.д.
На этом, пожалуй, закончу первую часть.
Самые догадливые уже, наверно, поняли, еще читая первую часть, о чем пойдет речь.
Имея некий набор масок, и сопоставив каждому символу определенную маску можно кодировать информацию по описанной выше технологии, главное, чтобы последовательность ПСЧ была достаточно большой, в чем собственно поможет метод, описанный в первой главе.
На этом, пожалуй, закончу и вторую часть.
Думаю, даже самые догадливые, прочитав предыдущие две части, до подобного не додумались. Не огорчайтесь, ибо я и сам додумывался до всего этого в обратном написанному порядке. ;)
Про то, что такое игра «Жизнь» Дж. Конвея я писать не буду – не знающие могут набрать в Google слова Жизнь и Конвей и обрести прозрение. Скажу лишь, что по сути «Жизнь» является однонаправленной функцией. Плохо, что f(x) можно получить из различных x, поэтому применение данного метода в шифровании потребует дополнительной проверки на дубли, хотя этого можно избежать, используя апробированные на сей счет наборы масок (опять они – куда без них?! ;-) ).
Суть метода заключается в следующем. Опять же набор масок – на этот раз двумерных (хотя существуют правила «Жизни» для одномерных и трехмерных пространств). Каждому шифруемому символу соответствует определенная маска с которой производится определенное число итерация по правилам игры «Жизнь» (думаю, лучше если это число не будет постоянным, иначе все выродится в метод описанный во второй части). Далее возможен как описанный во второй и первой частях способ заполнения массива ПСЧ каким-либо генератором с последующими действиями над выбранными числами, так и что-нибудь более экзотическое, например суммирование полученного расположения клеток по строкам или по столбцам с весовыми коэффициентами и т.п.
Большим минусом у классической игры «Жизнь» является то обстоятельство, что в конце концов после некоторого количества итераций, число которых зависит от величины поля и начального расположения клеток, колония вырождается и принимает устойчивое состояние, поэтому особо с количеством итераций не разгуляешься. Но существуют диалекты игры свободные от этого изъяна. Так что и здесь можно найти выход, манипулируя правилами рождения и смерти клеток в игре.
Думаю, возможно использовать «Жизнь» и для генерации ПСЧ - надо подумать на досуге, только очень медленный алгоритм получится. :-(
На этом, пожалуй, закончу не только третью часть, но и весь опус.
P.S. Если из вышеизложенного кто-то что-то не понял– «Звиняйте, хлопцы, бананьев нема!» © или как говорят там, у них, As is.
Андрей Сапожников.