В данном посте буду вести речь о программной реализации Скремблера. О том что такое Scrambler (читается Скремблер) вы можете ознакомиться по следующим ссылкам:
Если кратко, то Скремблер предназначен для шифрования потока бит при передаче информации с возможностью расшифровать переданные данные зная ключ скремблера и его определение (полином).
Что интересно, в сети я не нашел подробных инструкций по реализации скремблера на каком-нибудь языку программирования
Сразу оговорюсь. Здесь приведу лишь реализацию генератора цикла псевдослучайной последовательности его исследование. Любая последовательность сгенерированная скремблером обладает свойствами цикличность, коррелированность и сбалансированность. Итак начнём.
Для начала объявим переменные и свойства которые нам пригодятся
int shiftRegister;// текущее содержимое скремблера
private int[] summators; // скремблер - массив степеней полинома
Random rnd;
public int key; // ключ скремблера
public int period; // период псевдосучайной последовательности
public int[] Cycles; // Число циклов
public bool IsBalansed; // Сбалансированность
public bool IsCycles; // Цикличность
// для исследования на корреляцию
public bool IsCorrelationed; // Коррелированность
public int CorMatch = 0; // число совпадений
public int CorMissMath = 0; // число несовпадений
public Scrembler(int[] summators)
{
Summator = summators;
}
public int[] Summator
{
get
{
return summators;
}
set {
if (value == null)
{
throw new Exception("Это не похоже на сумматор");
}
value.OrderByDescending(i => i);// Сортируем по убыванию
if (value.Min() < 1)
{
throw new Exception("Такой маленькой степени не может быть!");
}
if (value.Max() > 31)
{
throw new Exception("Такой большой степени не может быть!");
}
summators = value;
regenerateKey();
}
}Заметели незнакомую и странную функцию regenerateKey()? Она нужна для генерации ключа - одной из составляющих для генерации последовательности
private int keyGenerator()
{
int maxStepen = summators[0];
rnd = new Random();
int minKey = (int)Math.Pow(2, maxStepen - 1);
key = (int)(minKey + rnd.NextDouble() * (minKey - 1));
return key;
}
public void regenerateKey()
{
key = keyGenerator();
sequenceGenerator();
}И наконец сам метод генерации и исследования
public void sequenceGenerator()
{
shiftRegister = key;
int i;
int j;
int tmp;
List<int> history = new List<int>();
int min = (int)Math.Pow(2, summators[0] - 1);
int count = (int)Math.Pow(2, summators[0]);
List<bool> sequence = new List<bool>();
int cycleIndexStart = 0; // индекс в истории последовательностей с которого начинается цикл
for (i = 0; i < count; i++)
{
if (history.Contains(shiftRegister))
{
for (j = 0; j < history.Count; j++)
{
if (history[j] == shiftRegister)
{
cycleIndexStart = j;
break;
}
}
break; }
history.Add(shiftRegister);
tmp = shiftRegister << summators[0] - 1;
for (j = 1; j < summators.Length; j++)
{
tmp ^= shiftRegister << summators[j] - 1;
}
shiftRegister = (tmp & min) | (shiftRegister >> 1);
sequence.Add(true ? (shiftRegister & 1) == 1 : (shiftRegister & 1) == 0);
}
sequence.RemoveRange(0, cycleIndexStart);// Удаляем первые элементы последовательности не входящие в цикл
period = sequence.Count;
...Исследование.
// исследуем на сбалансированность
int countOfZero = 0;
int countOfUnion = 0;
for (i = 0; i < sequence.Count; i++)
{
if (sequence[i]) countOfUnion++;
else countOfZero++;
}
if ((countOfUnion - countOfZero) == 0 || (countOfUnion - countOfZero) == 1) IsBalansed = true;
// исследуем на цикличность
List<int> ciclesCounts = new List<int>();
List<bool> cicle = new List<bool>(); // Для хранении подряд идущих последовательностей 0 или 1
bool sign = sequence[0]; // начальный бит
int cycleLength = 0;
// Копируем последовательность
List<bool> csequence = sequence.GetRange(0, sequence.Count);
while (csequence.Count != 0)
{
for (i = 0; i < csequence.Count; i++)
{
if (sign) // в случае подряд идущих 1
{
if (csequence[i]) cicle.Add(csequence[i]);
else break;
}
else // 0
{
if (!csequence[i]) cicle.Add(csequence[i]);
else break;
}
}
// Тоже самое можно было получить используя LINQ
//IEnumerable<bool> cicle;
// в cicle вернется последовательность подряд идущих лог. 0 или лог. 1
//cicle = csequence.TakeWhile(i =>
//{
// if (sign)// в случае подряд идущих 1
// {
// if (i) return true;
// else return false;
// }
// else // 0
// {
// if (!i) return true;
// else return false;
// }
//});
cycleLength = cicle.Count();
//Элемент массива с индексом index соотвествует
// количеству подряд идущих лог. 1 или 0 длиной index+1
while (ciclesCounts.Count < cycleLength)
{
ciclesCounts.Add(0);
}
ciclesCounts[cycleLength - 1]++;
//меняем знак
sign = !sign;
//Удаляем часть последовательности
csequence.RemoveRange(0, cycleLength);
}
Cycles = ciclesCounts.ToArray();
// Проверка на Цикличность
int temp = 2;
IsCycles = false;
for (i = 0; i < Cycles.Length; i++)
{// получаем длину части последовательности: 1/2, 1/4, 1/8, ...
int tempResult = period / temp;
// Если число подряд идущих лог. 1 или 0 длинной i+1 равно длине части
// последовательности +-1, то последовательность обладает свойством цикличностью
if (Cycles[i] == tempResult || Cycles[i] == tempResult + 1 || Cycles[i] == tempResult - 1)
{
IsCycles = true;
}
else
{
IsCycles = false;
}
if (temp < period) temp *= temp;
else temp = period + 1; // сравнивать длину последовательности 1 или 0 с нулём бессмысленно
if (temp == 0) temp = period + 1; // в случае выхода значения temp за границы int
}
// исследуем на корреляцию
int sequenceLength = sequence.Count;
int corr = 0;
List<bool> copy = sequence.GetRange(rnd.Next(sequence.Count - sequenceLength), sequenceLength);
// Получаем копию посл-ти циклично сдвинутую вправо
List<bool> seq = copy.GetRange(0, copy.Count);
copy.Insert(0, copy[copy.Count - 1]);
copy.RemoveAt(copy.Count - 1);
CorMatch = 0;
CorMissMath = 0;
for (i = 0; i < copy.Count; i++)
{
if (seq[i] == copy[i])
{
corr++;
CorMatch++;
}
else
{
corr--;
CorMissMath++;
}
}
IsCorrelationed = corr < 2 && corr > -2 ? true : false;
}
