Учебно-методический комплекс по дисциплине " криптография 1 " Научная сфера: 300 000 Сфера технического производства

Практическая работа №7
Тема. Создание генератора псевдослучайных чисел и его программного обеспечения
Генераторы случайных чисел — ключевая часть веб-безопасности. Небольшой список применений:

• 
  Генераторы сессий (PHPSESSID)
  
• 
  Генерация текста для капчи
  
• 
  Шифрование
  
• 
  Генерация соли для хранения паролей в необратимом виде
  
• 
  Генератор паролей
  
• 
  Порядок раздачи карт в интернет казино
  

Как отличить случайную последовательность чисел от неслучайной?
Пусть есть последовательность чисел: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9. Является ли она случайной? Есть строгое определение для случайной величины. Случайная величина — это величина, которая принимает в результате опыта одно из множества значений, причём появление того или иного значения этой величины до её измерения нельзя точно предсказать. Но оно не помогает ответить на наш вопрос, так как нам не хватает информации для ответа. Теперь скажем, что данные числа получились набором одной из верхних строк клавиатуры. «Конечно не случайная» — воскликните Вы и тут же назовете следующие число и будете абсолютно правы. Последовательность будет случайной только если между символами, нету зависимости. Например, если бы данные символы появились в результате вытягивания бочонков в лото, то последовательность была бы случайной.
Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.
Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)
Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел. ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.
Энтропия – это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.
Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.
Уязвимости ГПСЧ

• 
  Предсказуемая зависимость между числами.
  
• 
  Предсказуемое начальное значение генератора.
  
• 
  Малая длина периода генерируемой последовательности случайных чисел, после которой генератор зацикливается.
  

Линейный конгруэнтный ГПСЧ (LCPRNG)
Распространённый метод для генерации псевдослучайных чисел, не обладающий криптографической стойкостью. Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

где a (multiplier), c (addend), m (mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа (seed) X0 и при разных его значениях получаются различные последовательности случайных чисел.
Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].
Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений

Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия, эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.
Предсказание результатов линейно-конгруэнтного метода
Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь (есть онлайн запуск) и здесь . Описание алгоритма можно найти в.
Простая реализация конгруэнтного метода на Java.
public static int a = 45;
public static int c = 21;
public static int m = 67;
public static int seed = 2;
public static int getRand() {
seed = (a * seed + c) % m;
return seed;
}

public static void main(String[] args) {

for(int i=0; i<30; i++)
System.out.println(getRand());
}
Отправив 20 чисел на сайт, можно с большой вероятностью получить следующие. Чем больше чисел, тем больше вероятность.
Взлом встроенного генератора случайных чисел в Java
Многие языки программирования, например C(rand), C++(rand) и Java используют LСPRNG. Рассмотрим, как можно провести взлом на примере java.utils.Random. Зайдя в исходный код (jdk1.7) данного класса можно увидеть используемые константы
private static final long multiplier = 0x5DEECE66DL; // 25214903917
private static final long addend = 0xBL; // 11
private static final long mask = (1L << 48) - 1; // 281474976710655 = 2^48 – 1
Метод java.utils.Randon.nextInt() выглядит следующим образом (здесь bits == 32)
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
Результатом является nextseed сдвинутый вправо на 48-32=16 бит. Данный метод называется truncated-bits, особенно неприятен при black-box, приходится добавлять ещё один цикл в brute-force. Взлом будет происходить методом грубой силы(brute-force).

Пусть мы знаем два подряд сгенерированных числа x1 и x2. Тогда необходимо перебрать 2^16 = 65536 вариантов oldseed и применять к x1 формулу:

((x1*multiplier + addend) & mask) << 16
до тех пор, пока она не станет равной x2. Код для brute-force может выглядеть так
import java.lang.reflect.Field;
import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;

public class PasswordCracking {

public static final long multiplier = 0x5DEECE66DL;
public static final long addend = 0xBL;
public static final long mask = (1L << 48) - 1;

public static void main(String[] args) {

Random random = new Random();
long v1 = random.nextInt();
long v2 = random.nextInt();
long v3 = random.nextInt();
long v4 = random.nextInt();
System.out.println("v1=" + v1 + "\nv2=" + v2 + "\nv3=" + v3 + "\nv4=" + v4);
// brute-force seed
for (int i = 0; i < 65536; i++) {
long seed = (((long) v1) << 16) + i;
int nextInt = (int)(((seed * multiplier + addend) & mask) >>> 16);
if (nextInt == v2) {
System.out.println("Seed found: " + seed);
Random crackingRandom = new Random();
try {
/* set the seed for Random to be convinced that we have found the
right seed because constructor Random (long seed) uses the
private static long initialScramble (long seed) {
return (seed ^ multiplier) & mask;
}
for simplicity will use Reflection */
Field privateSeedField = Random.class.getDeclaredField("seed");
privateSeedField.setAccessible(true);
AtomicLong crackingSeed = (AtomicLong)privateSeedField.get(crackingRandom);
crackingSeed.set(seed);
}catch(Exception e) {
System.out.println(e.toString());
System.exit(1);
}
long cv1 = crackingRandom.nextInt();
long cv2 = crackingRandom.nextInt();
long cv3 = crackingRandom.nextInt();
long cv4 = crackingRandom.nextInt();
System.out.println("Set fiend seed and generate random numbers");
System.out.println("cv1=" + cv1 + "\ncv2=" + cv2 + "\ncv3=" + cv3 + "\ncv4=" + cv4);
break;
}
}
}
}
Вывод данной программы будет примерно таким:

v1 = -1184958941

v2 = 274285127
v3 = -1566774765
v4 = 30466408
Seed found: -77657469128792
Set fiend seed and generate random numbers
cv1 = 274285127
cv2 = -1566774765
cv3 = 30466408
cv4 = -803980434
Несложно понять, что мы нашли не самый первый seed, а seed, используемый при генерации второго числа. Для нахождения первоначального seed необходимо провести несколько операций, которые Java использовала для преобразования seed, в обратном порядке.
public static long getPreviousSeed(long prevSeed) {
long seed = prevSeed;
// reverse the addend from the seed
seed -= addend; // reverse the addend
long result = 0;
// iterate through the seeds bits
for (int i = 0; i < 48; i++) {
long mask = 1L << i;
// find the next bit
long bit = seed & mask;
// add it to the result
result |= bit;
if (bit == mask) {
// if the bit was 1, subtract its effects from the seed
seed -= multiplier << i;
}
}
System.out.println("Previous seed: " + result);
return result;
}
И теперь в исходном коде заменим
crackingSeed.set(seed);
на
crackingSeed.set(getPreviousSeed(seed));