Анализ реализаций диалогового кода

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Реализация поставленных задач

1.1 Односторонние функции

1.2 Изучение односторонних функций

2. Изучение протокола "Свой - Чужой"

2.1 Выбор библиотеки

2.2 Реализация программы

Заключение

Список использованных источников

ПРИЛОЖЕНИЕ А

Введение

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

В соответствии с поставленной задачей были предложены и решены следующие основные вопросы:

1. Односторонние Функции. Изучение математических свойств односторонних функций.

2. Изучить протокол передачи команды (Свой - чужой) в автомобильной сигнализации.

3. Выбрать используемую библиотеку для реализации.

4. Сравнить варианты по времени выполнения.

Объектом исследования является криптография, информационное обеспечение арифметики длинных чисел. Язык программирования Си#. Предметом исследования является "Диалоговый код"

В работе использованы методы односторонних функций.



1. Реализация поставленных задач

1.1 Односторонние Функции

Односторонняя функция является математической функцией, которую нетрудно вычислить в одном направлении (направление вперед), но практически невозможно в противоположном (обратном) направлении, т.е для вычисления обратной функции потребуются сотни лет.

Неформально, функция F является односторонней функцией, если

1. Описание F является общеизвестным и не требует никакой секретной информации для ее вычисления.

2. Если известен х легко вычислить F(х).

3. По значению у трудно найти x (для определения х потребуется много времени).

Существование односторонней функции предполагает существование многих других полезных криптографических алгоритмов, в том числе:

* схемы шифра,

* схемы цифровой подписи,

* генератора псевдослучайных чисел.

1.2 Изучение математических свойств односторонних функций

В данной работе использовались следующие односторонние функции.

односторонний функция алгоритм шифр

1. F(x)=2x mod p

p-простое число.

длина числа P- 1024 бита

Данную одностороннюю функцию будем называть "функцией Диффи-Хеллмана". Приведем ее реализацию на языке C#:

static BigInteger DiffHellFun(BigInteger x, BigInteger p)

{

BigInteger res = BigInteger. ModPow(2, x, p);

return res;

}

2. X3 mod n

(n=p*q)

p-q - простые числа

p-q - 512 бит

n- (1024 бит)

Данную одностороннюю функцию будем называть "функцией RSA". Ее реализация на языке C#:

static BigInteger RSAFunc(BigInteger x,BigInteger p)

{

BigInteger q = GenerateLargePrime(64);

BigInteger res = BigInteger.ModPow(x, 3, BigInteger.Multiply(p, q));

return res;

}

3.X2 mod n

n=p*q

p,q- 512 бит

n-1024 бит.

Данную одностороннюю функцию будем называть "функцией Рабина". Ее реализация на языке C#:

static BigInteger RabinCarp(BigInteger x,BigInteger p)

{

BigInteger q = GenerateLargePrime(64);

BigInteger res = BigInteger.ModPow(x, 2, BigInteger.Multiply(p, q));

return res;

}

рис.1.1. Результат решений односторонних функций



2. Изучение протокола передачи команды "Свой - Чужой"

Для начала дадим определение, что такое протокол.

Протокол- это последовательность действий, предпринимаемых двумя или более сторонами, предназначенных для решений определённых функций, и достижения определенного результата.

Что должен знать участник протокола:

1. Каждый участник должен знать протокол и последовательность его действий.

2. Каждый участник должен следовать протоколу.

3. Протокол должен быть логичный, следовать определенной последовательности действий, чтобы не было сбоев.

4. Протокол должен быть полным для каждой возможной ситуации и следовать строго по протоколу.

Протокол "Свой-Чужой".

Исходя уже из названия протокола "Свой - чужой", выясняется, что протокол состоит из двух частей.

а) Следует выбрать необходимый объект и направить ему запрос или команду.

Для отправки запроса по защищенным каналам связи, данный запрос шифруется.

б) Получить ответ от выбранного объекта.

В соответствии с заданием рассматривается следующий протокол передачи команды от брелка (B) к автомобилю (A): (изначально в авто и брелок записан одинаковый секретный ключ длиной 128бит минимум.)

B -> A : номер авто, код команды

A -> B : случайное число длиной 128 бит минимум

B -> A : f (полученное случайное число || секретный ключ || номер авто, код команды), где B (Брелок) знает секретный ключ, причем ключ в эфир не передается.

Основное назначение протокола "Свой-Чужой" состоит в том, чтобы между брелком и автомобилем был защищенный канал связи, а так же опознавательная метка, в данном случае номер транспортного средства (регистрационный знак).

Заметим, что данный протокол использует криптографические устройства шифрования. Это связанно с тем, чтобы данный протокол не позволил злоумышленнику повторить перехваченную команду, каждый раз ему потребуется вычислять ответ на другое случайное число.

Особенность протокола состоит в том, что распознание защитной системой проходит в несколько этапов.

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

Если автомобиль распознал идентификацию, да, это с моего брелка была отправлена команда, то направляется ответный сигнал с кодом, сконфигурированный случайным образом.

Брелок, получив ответный сигнал со своего автомобиля, обрабатывает его по определенному алгоритму и полученный результат посылает автомобилю.

Автомобиль, получив ответ от своего брелка, производит аутентификацию по тому же алгоритму после чего сравнивает свой результат и результат присланный брелком и если они совпадают, то выполняет команду брелка.

2.1 Выбор библиотеки

Для реализации f(x) необходимо выбрать средство для вычислений с большими целыми числами (например, библиотеку libgmp, данная библиотека работает в С++). Но на языке программирования C# будем использовать целочисленный тип BigInteger из пространства имен System.Numerics.

2.2 Реализация программы

1. В соответствии с заданием рассматривается следующий протокол передачи команды от брелка (B) к автомобилю (A): (изначально в авто и брелок записан одинаковый секретный ключ длиной 128
бит минимум. f(x) -- односторонняя функция)

B -> A : номер авто, код команды A -> B : случайное число длиной 128 бит минимум B -> A : f (полученное случайное число || секретный ключ || номер авто, код команды) Авто вычисляет аналогичную функцию на основе своих данных. Если значение вычисленной функции совпало с полученным, то выполняет команду. В противном случае ничего не делает.

Для написания программы выбрана платформа. Microsoft. NET Framework 4.0 и язык C# а также среда разработки Visual Studio 2010 service pack 1.

Так как в трех описанных задачах алгоритмов, мы имеем дело с арифметикой больших чисел, то, исходя из этого, будем использовать целочисленный тип BigInteger из пространства имен System.Numerics. Для этого нужно добавить ссылку в проект на пространстве имен System.Numerics в Visual Studio 2010. Поскольку в задачах имеется подзадача генерирования простого числа заданной длины, отсюда следует, что нужно разрабатывать метод для генерации случайного большого числа. Для метода генерации есть различные способы. В программе использован тест Миллера- Рабина для проверки числа на простоту.

Тест Миллера -- Рабина -- вероятностный полиномиальный тест простоты. Тест Миллера -- Рабина, наряду с тестом Ферма и тестом Соловея -- Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоты числа. Тем не менее, тест Миллера -- Рабина часто используется в криптографии для получения больших случайных простых чисел.

Заключение

В процессе написания дипломной работы мной изучен алгоритм Диффи-Хеллмана, алгоритм RSA, шифр Рабина, а так же Изучение протокола передачи команды "Свой - Чужой"

Что касается времени, алгоритм Диффи-Хеллмана на реализацию тратит больше времени, чем алгоритм RSA и шифр Рабина, а самым быстрым по реализации является алгоритм Рабина, так он сводится к одному умножению по модулю.

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

Список использованных источников

1) Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии Учебное пособие -- М.: Гелиос АРВ, 2002. -- 480 c. ISBN 5-85438-025-0

2) Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. -- М.: Горячая линия -- Телеком, 2002. -- 175 с. -- (Специальность. Для высших учебных заведений). -- 3000 экз. -- ISBN 5-93517-075-2.

3) Герасименко В. А. Защита информации в автоматизированных системах обработки данных., кн. 1, 2. М.: Энергоатомиздат, 1994.

4) Конхейм А. Г. Основы криптографии. М.: Радио и связь, 1987.

5) Мао В. Современная криптография: Теория и практика -- М.: Вильямс, 2005. -- 768 с. -- ISBN 5-8459-0847-7

6) Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях. М.: Научный мир, 2004. ISBN 5-89176-233-1.

7) Рябко Б. Я., Фионов А. Н. Криптографические методы защиты информации.

8) Ухлинов Л. М. Управление безопасностью информации в автоматизированных системах. М.: МИФИ, 1996.

9) Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. -- М.: Триумф, 2002. -- 816 с. -- 3000 экз. -- ISBN 5-89392-055-4.

10) Дебора Керр Computerworld #39/1996 Тайна открытого ключа. Завгородний В. И. Комплексная защита информации в компьютерных системах. М.: Логос, 2001 г. - 264 с.

11) Смарт Н. Криптография. М.: Техносфера, 2006 г. - 528 с.



Приложение А

Листинг программы Алгоритма Диффи-Хеллмана,RSA, Шифра Рабина

using System;

using System.Numerics;

using System.Collections;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace Crypto

{

class Program

{

static Random random = new Random(DateTime.Now.Millisecond);

static void Main(string[] args)

{

BigInteger x = new BigInteger(24638574625374610058928563791728872894);

BigInteger res = Diffe Hellman Fun(x);

Console.WriteLine("Diffe Hellman: \n{0}",res);

res = RSAFunc(x);

Console.WriteLine("\nRSA: {0}", res);

res = Rabin (x);

Console.WriteLine("\nRabin: {0}",res);

Console.ReadKey(true);

}

static BigInteger RSA Func(BigInteger x)

{

Primality primality = new Primality();

BigInteger p = GenerateLargePrime(128);

BigInteger q = GenerateLargePrime(128);

BigInteger res = BigInteger.ModPow(x, 3, BigInteger.Multiply(p, q));

return res;

}

static BigInteger Diffe Hellman Fun(BigInteger x)

{

Primality primality = new Primality();

BigInteger p = GenerateLargePrime(128);

BigInteger res = BigInteger.ModPow(2, x, p);

return res;

}

static BigInteger Rabin (BigInteger x)

{

Primality primality = new Primality();

BigInteger p = Generate Large Prime(18); //128 byte = 1024 bit

BigInteger q = Generate Large Prime(128);

BigInteger res = BigInteger.ModPow(x, 2, BigInteger.Multiply(p, q));

return res;

}

static BigInteger Generate Large Prime(int length)

{

Primality primality = new Primality();

string numbers = "";

for (int i = 0; i < length; i++)

{

numbers += random.Next(0, 10);

}

BigInteger number = BigInteger.Parse(numbers);

if (primality.IsPrimeMillerRabin(number))

{

return number;

}

else

{

return GenerateLargePrime(length);

}

}

public BigInteger Random(BigInteger min, BigInteger max)

{

byte[] maxBytes = max.ToByteArray();

BitArray maxBits = new BitArray(maxBytes);

Random random = new Random(DateTime.Now.Millisecond);

for (int i = 0; i < maxBits.Length; i++)

{

// Randomly set the bit

int randomInt = random.Next();

if ((randomInt % 2) == 0)

{

// Reverse the bit

maxBits[i] = !maxBits[i];

}

}

BigInteger result = new BigInteger();

// Convert the bits back to a BigInteger

for (int k = (maxBits.Count - 1); k >= 0; k--)

{

BigInteger bitValue = 0;

if (maxBits[k])

{

bitValue = BigInteger.Pow(2, k);

}

result = BigInteger.Add(result, bitValue);

}

// Generate the random number

BigInteger random BigInt = BigInteger.ModPow(result, 1, BigInteger.Add(max, min));

return randomBigInt;

}

}

public class Primality

{

public enum NumberType

{

Composite,

Prime

}

public bool Is Prime Rabin(BigInteger integer)

{

Number Type type = Rabin(integer, 400);

return type == Number Type. Prime;

}

public bool IsPrimePseudo(BigInteger integer)

{

NumberType type = PseudoPrime(integer);

return type == NumberType.Prime;

}

// Primality testing based on Rabin

public NumberType Rabin(BigInteger n, int s)

{

BigInteger nMinusOne = BigInteger.Subtract(n, 1);

for (int j = 1; j <= s; j++)

{

BigInteger a = Random(1, nMinusOne);

if (Witness(a, n))

{

return NumberType.Composite;

}

}

return NumberType.Prime;

}

// Generates a random BigInteger between min and max

public BigInteger Random(BigInteger min, BigInteger max)

{

byte[] maxBytes = max.ToByte Array();

BitArray maxBits = new Bit Array(maxBytes);

Random random = new Random(DateTime.Now.Millisecond);

for (int i = 0; i < maxBits.Length; i++)

{

// Randomly set the bit

int randomInt = random.Next();

if ((randomInt % 2) == 0)

{

// Reverse the bit

maxBits[i] = !maxBits[i];

}

}

BigInteger result = new BigInteger();

// Convert the bits back to a BigInteger

for (int k = (maxBits.Count - 1); k >= 0; k--)

{

BigInteger bitValue = 0;

if (maxBits[k])

{

bitValue = BigInteger.Pow(2, k);

}

result = BigInteger.Add(result, bitValue);

}

// Generate the random number

BigInteger randomBigInt = BigInteger.ModPow(result, 1, BigInteger.Add(max, min));

return random BigInt;

}

// Pseudo primality testing with Fermat's theorem

public Number Type Pseudo Prime(BigInteger n)

{

BigInteger modular Exponentiation =

Modular Exponentiation(2,

BigInteger.Subtract(n, 1),

n);

if (!modular Exponentiation.IsOne)

{

return NumberType.Composite;

}

else

{

return NumberType.Prime;

}

}

public bool Witness(BigInteger a, BigInteger n)

{

KeyValuePair<int, BigInteger> tAndU = GetTAndU(BigInteger.Subtract(n, 1));

int t = tAndU.Key;

BigInteger u = tAndU.Value;

BigInteger[] x = new BigInteger[t + 1];

x[0] = ModularExponentiation(a, u, n);

for (int i = 1; i <= t; i++)

{

// x[i] = x[i-1]^2 mod n

x[i] = BigInteger.ModPow(BigInteger.Multiply(x[i - 1], x[i - 1]), 1, n);

BigInteger minus = BigInteger. Subtract(x[i - 1], BigInteger. Subtract(n, 1));

if (x[i] == 1 && x[i - 1] != 1 && !minus.IsZero)

{

return true;

}

}

if (!x[t].IsOne)

{

return true;

}

return false;

}

public KeyValuePair<int, BigInteger> GetTAndU(BigInteger nMinusOne)

{

// Convert n - 1 to a byte array

byte[] nBytes = nMinusOne.ToByteArray();

BitArray bits = new BitArray(nBytes);

int t = 0;

BigInteger u = new BigInteger();

int n = bits.Count - 1;

bool lastBit = bits[n];

// Calculate t

while (!lastBit)

{

t++;

n--;

lastBit = bits[n];

}

for (int k = ((bits.Count - 1) - t); k >= 0; k--)

{

BigInteger bitValue = 0;

if (bits[k])

{

bitValue = BigInteger.Pow(2, k);

}

u = BigInteger.Add(u, bitValue);

}

KeyValuePair<int, BigInteger> tAndU = new KeyValuePair<int, BigInteger>(t, u);

return tAndU;

}

public BigInteger ModularExponentiation(BigInteger a, BigInteger b, BigInteger n)

{

// a^b mod n

return BigInteger.ModPow(a, b, n);

}

}

}

Размещено на Allbest.ru

...