Этап 1. Реализация комбинирующего генератора для анализа

Комбинирующий генератор (G) - криптографический объект, который генерирует некоторую псевдослучайную последовательность. Именено его мы и будем пытаться атаковать. Для начала нам следует реализовать сам генератор.

Замечу, что я сделал несколько конкретизаций:

1. Длина РСЛОС может быть любая, я же принял длину всех РСЛОС в 16 ячейки памяти;
2. Функция f может иметь достаточно сложную структуру, я же предлагаю рассматривать функцию, определенную для генератора Геффе.

Булева функция, для него имеет вид: (x1 * x2) ^ ((x1 ^ 1) * x3)

                    Таблица истинности:	
x1	x2	x3		(x1 * x2) ^ ((x1 ^ 1) * x3)
0	0	0		            0
0	0	1		            1	
0	1	0		            0
0	1	1		            1
1	0	0		            0
1	0	1		            0
1	1	0		            1
1	1	1		            1

Следовательно, корреляция с гаммой будет наблюдаться только для последоваательней, возвращаемых вторым и третьим регистром

Функция: createG() // создание G

Вход: пустой

Выход: G // комбирирующий генератор

G представляет собой структуру / класс и состоит из:

uint8_t N;     // количество РСЛОС в G	
uint16_t r[N]; // реверснутые полиномы обратной связи для РСЛОС
uint16_t a[N]; // начальные состония РСЛОС	


1. N <- 3;
2. r[0] <- 0x8016, r[1] <- 0x801C, r[2] <- 0x801F; // взято отсюда http://users.ece.cmu.edu/~koopman/lfsr/15.txt
3. Для i = 0 .. N - 1:			 
    3.1. a[i] <- R[0, 65535]; // R[a, b] - выбрать рандомно из промежутка от a до b включительно
4. Вернуть G;

Функция: workG() // работа G

Вход: G, uint32_t l // G - комбирирующий генератор, l - длина выходной последовательности, которую мы хотим получить

Выход: uint8_t z[l] // z[l] - выходная битовая последовательность

uint8_t tmp[N];     // временный массив    
uint8_t z[l] = {0}; // выходная битовая последовательность


1. Для i = 0 .. l - 1:
    1.1. Для j = 0 .. N - 1:
        1.1.1. Если (a[j] & 0x0001) == 1:
            То a[j] <- ((a[j] ^ r[j]) >> 1) | 0x8000, tmp[j] <- 1;
            Иначе a[j] <- a[j] >> 1, tmp[j] <- 0;
    1.2. z[i] <- (tmp[0] * tmp[1]) ^ (tmp[0] ^ 1) * tmp[2]; // булева функция для генератора Геффе
2. Вернуть z;

Этап 2. Реализация базовой корреляционной атаки Зигенталера

На этом этапе будет реализована базовая атака Зигенталера

Функция: createAndWorkTestR() // работа РСЛОС для алгоритма Зигенталера

Вход: uint16_t d, uint32_t l, uint8_t i

Выход: x[l] // x[l] - выходная битовая последовательность

uint16_t r;       // реверснутые полином обратной связи для РСЛОС
uint16_t a;       // начальное состоние РСЛОС
uint8_t x[l];     // выходная битовая последовательность


1. Если i == 1, то r <- 0x801C;
   Если i == 2, то r <- 0x801F;  		 
2. a <- d;
3. Для i = 0 .. l - 1:	
    3.1. Если (a & 0x0001) == 1:
        То a <- ((a ^ r) >> 1) | 0x8000, x[i] <- 1;
        Иначе a <- a >> 1, x[i] <- 0;	
4. Вернуть x;

Функция: createAndWorkTestG() // работа генератора для алгоритма Зигенталера

Вход: uint16_t d, uint32_t l, uint16_t a[N]

Выход: x[l] // x[l] - выходная битовая последовательность

uint16_t r[N];    // реверснутые полиномы обратной связи для РСЛОС
uint8_t tmp[N];   // временный массив
uint8_t x[l];     // выходная битовая последовательность


1. r[0] <- 0x8016, r[1] <- 0x801C, r[2] <- 0x801F; 		 
2. a[0] <- d;
3. Для i = 0 .. l - 1:
    3.1. Для j = 0 .. N - 1:
        3.1.1. Если (a[j] & 0x0001) == 1:
            То a[j] <- ((a[j] ^ r[j]) >> 1) | 0x8000, tmp[j] <- 1;
            Иначе a[j] <- a[j] >> 1, tmp[j] <- 0;
    3.2. x[i] <- (tmp[0] * tmp[1]) ^ (tmp[0] ^ 1) * tmp[2]; // булева функция для генератора Геффе
4. Вернуть x;

Фукция: zigentalerAlg() // алгоритм Зигенталера

Вход: G, uint32_t l, uint8_t z[l] // G - комбирирующий генератор(Вместо генератора только N), l(size) - длина выходной последовательности, z[l] (sequence) - сгенерированная битовая последовательность

Выход: uint16_t a[N] // полученные с помощью атаки начальные состония РСЛОС

double p[N];          // априорные вероятности (prior_probabilities)
double c;             // кросс-корреляционная функция (cross_correlation_fun)
uint8_t x[l];         // выходная битовая последовательность (test_sequence)
uint16_t a[N];        // полученные с помощью атаки начальные состония РСЛОС (result)


1. uint32_t n = l / 2;
2. Для j = 1 .. N - 1:
        2.1. Для d = 1 .. 65535:
                2.1.1. x <- createAndWorkTestR(d, n, j);
                2.1.2. Для i = 0 .. n - 1:
                            2.1.2.1.  с <- c  + ((-1) ^ z[i] * (-1) ^ x[i]);
                2.1.3. c <- c / n;
                2.1.4. Если c < 0.5, то перейти на 2.1.1 для d <- d + 1;
                2.1.5. a[j] <- d, перейти на 2 для j <- j + 1;							
3. Для d = 1 .. 65535:
        3.1. x <- createAndWorkTestG(d, l, a[N]);
        3.2. Для i = 0 .. 1 - 1:
                3.2.1.  с <- c  + ((-1) ^ z[i] * (-1) ^ x[i]);
        3.3. c <- c / l;
        3.4. Если c < 0.95, то перейти на 3.1 для d <- d + 1;
        3.5. a[0] <- d;			
4. Вернуть a;

Этап 3. Основная функция (main())

Вход: пустой

Выход: 0

uint32_t l = 1000; // выбранная на шару длина битовой последовательности
uint32_t z[l];     // выходная битовая последовательность
uint16_t a[N];     // полученные с помощью атаки начальные состония РСЛОС

1. G <- createG();
2. z <- workG(G, l);
3. a <- zigentalerAlg(G, l, z[l]);
4. Для j = 0 .. N - 1:
    Если a[j] != G.a[j]:
        То вывести на экран "Мы НЕ сдали лабу(" и перейти на 6;
5. Вывести на экран "Мы сдали лабу)";
6. Вернуть 0;

(c) Written by Maksim Kazlovski.