среда, 4 ноября 2009 г.

Пишем Скремблер (How to create Scrambler)

В данном посте буду вести речь о программной реализации Скремблера. О том что такое 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;
}
Нет комментариев.
Отправить комментарий