Криптография как наука

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

Федеральное агентство связи

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«Сибирский государственный университет телекоммуникаций и информатики»

Кафедра информатики

Курсовая работа

Криптография

Выполнил:

Монгуш С.

Студент 1 курса, ф. МРМ

гр. РС-41

Проверил:

Монарев

Новосибирск 2015 г.



Оглавление

криптографический протокол электронный подпись

1. Краткое описание электронной подписи на базе шифра Эль-Гамаля

2. Описание основных переменных и функций электронной подписи на базе шифра Эль-Гамаля. Пример работы программы

3. Краткое описание криптографического протокола «Электронные деньги»

4. Описание основных переменных и функций криптографического протокола «Электронные деньги». Пример работы программы

5. Программный код электронной подписи на базе шифра Эль-Гамаля

6. Криптографический протокол «Электронные деньги»



1. Краткое описание электронной подписи на базе шифра Эль-Гамаля

Пусть, Алиса собирается подписывать документы. Алиса выбирает большое простое число p и число g, такие, что различные степени g суть различные числа по модулю p. Эти числа передаются или хранятся в открытом виде и могут быть общими для целой группы пользователей. Алиса выбирает случайное число x, 1 < x < p - 1, которое она держит в секрете. Это ее секретный ключ, только она его знает. Затем она вычисляет число

y = g ^ x mod p

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

Теперь Алиса может подписывать сообщения. Допустим, она хочет подписать сообщение m = m1,…,mn. Опишем последовательность действий для построения подписи.

Вначале Алиса вычисляет значение хеш-функции h = h(m), которое должно удовлетворять неравенству 1 < h < p. Затем Алиса выбирает случайное число k (1 < k < p - 1), взаимно простое с p - 1, и вычисляет число

r = g ^ k mod p.

Далее Алиса вычисляет числа

u = (h - xr) mod (p - 1),

s = (k ^-1) mod (p - 1)

Под (k^-1) подразумевается число, удовлетворяющее уравнению



(k ^-1) * k mod (p - 1) = 1

Такое (k ^-1) существует, так как k и p - 1 взаимно просты, и может быть найдено по обобщенному алгоритму Евклида. Наконец, Алиса формирует подписанное сообщение <m; r, s>.

Получатель подписанного сообщения, прежде всего, заново вычисляет значение хеш-функции h = h(m). Затем он проверяет подпись, используя равенство

y ^ r * r ^ s = g ^ h mod p

Если подпись верна, то условие выполняется.

2. Описание основных переменных и функций электронной подписи на базе шифра Эль-Гамаля. Пример работы программы

Функции:

int pprime (int number) - подбор простого числа P

int vozved (int a, int chislo, int p) - функция быстрого возведения в степень

int vzprost (int a, int b) - проверка на взаимную простоту

int evklid (int a, int b) - обощенный алгоритм Евклида: ? * d mod p = 1

Переменные:

int m, P, q, G, x, y, k, r, u, s, kmin1, rez, rez1, result



3. Краткое описание криптографического протокола «Электронные деньги»

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

1) Покупатель снимает нужную сумму со своего счета в банке

2) Покупатель «пересылает» деньги в магазин

3) Магазин сообщает об этом в банк, соответствующая сумма денег зачисляется на счет магазина, а покупатель забирает товар (или последний ему доставляется).

Наша цель - разработать такую схему, чтобы

Она была надежна

Чтобы банк не знал, кто купил товар, т.е. была сохранена анонимность обычных денег.

Банк имеет следующую информацию: секретные числа P, Q, c и открытые



N = P * Q,

d = c ^ -1 mod (P - 1) * (Q - 1). (5.9)

Допустим, покупатель решил израсходовать некоторую заранее оговоренную с банком сумму (например, 100$). (Мы сначала рассмотрим случай, когда может использоваться банкнота только одного номинала (скажем, 100$).) Покупатель генерирует число n, которое он не будет посылать в банк. Затем он генерирует случайно число r, взаимно простое с N, и вычисляет число

n' = (n * r ^ d) mod N. (5.11)

Число n' покупатель отправляет в банк.

Банк вычисляет число

s' = n' ^ c mod N (5.12)

и отправляет s' обратно покупателю (не забыв при этом снять 100$ с его счета).

Покупатель находит число r ^ - 1 mod N и вычисляет

s = (s' * r ^ -1) mod N. (5.13)

Заметим, что с учетом соотношений (5.12), (5.11) и (5.9) имеем

s = n' ^ c * r ^ -1 = (n * r^d)^c * r ^ -1 = n ^ c mod N,

т.е. мы получили подпись банка к n (см. (5.10)), но самого числа n ни банк, ни кто либо другой не видел. Вычисление (5.12) называется «слепой подписью», так как реальное сообщение (n) подписывающий не видит и узнать не может.

Таким образом, покупатель имеет число n, которое никому не известно и никогда не передавалось по каналам связи, и подпись банка s, совпадающую с вычисленной по (5.10). Покупатель формирует банкноту <n, s> и предъявляет ее в магазине, чтобы купить товар. Магазин отправляет эту банкноту в банк для проверки. Прежде всего, банк проверяет правильность подписи (эту проверку мог бы сделать и магазин, использую открытые ключи банка). Но кроме этого банк хранит все номера возвратившихся к нему банкнот и проверяет, нет ли числа n в этом списке. Если n есть в списке, то платеж не принимается (кто-то пытается использовать банкноту повторно), и банк сообщает об этом магазину. Если же все проверки прошли успешно, то банк добавляет 100$ на счет магазина, а магазин отпускает товар покупателю.

В данной системе для борьбы с мультипликативным свойством системы RSA мы используем внесение избыточности в сообщение. Допустим, что длина модуля N - 1024 бита. Такой же может быть и длина числа n. Будем записывать (случайно выбираемый) номер банкноты только в младшие 512 бит n, а в старшие 512 бит n запишем некоторое фиксированное число. Это фиксированное число может нести полезную информацию, такую, как номинал банкноты и наименование банка (с помощью 512 бит можно представить строку из 64 символов ASCII). Теперь банк при предъявлении банкноты будет обязательно проверять наличие фиксированного заголовка в параметре n и отвергать банкноту в случае его отсутствия. Вероятность того, что при перемножении двух чисел по модулю N результат совпадает с ними в 512 битах пренебрежимо мала. Поэтому получить фальшивую банкноту по формуле (5.14) не удается

n₃^c = (n₁n₂) ^ c = s₃ mod N, (5.14)



4. Описание основных переменных и функций криптографического протокола «Электронные деньги». Пример работы программы

Функции:

int gcda (int a, int b) - Проверка на взаимную простоту

int gcd (int a, int b) - обощенный алгоритм Евклида: ? * d mod p = 1

int pprime (int number) - подбор простого числа P

int bistr (int a, int chislo, int p) - функция быстрого возведения в степень

int bist (int a, int chislo, int p, int m) - a ^ chislo * m mod p

Переменные:

int P, Q, F, d, c, n, r, nn, ss, N, s, schetshop, schetshop - переменные необходимые для работы программы;

5. Программный код электронной подписи на базе шифра Эль-Гамаля

#include <iostream>

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

#include <fstream>

using namespace std;

//подбор простого числа P

int pprime (int number)

{

int count;

while(count != 2)

{

count = 0;

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

{

if (number % i == 0)

count++;

if (count > 2)

{

number++;

break;

}

}

}

return number;

}

//функция быстрого возведения в степень

int vozved (int a, int chislo, int p)

{

int b;

int y = 1;

int t = log2 (chislo);

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

{

b = chislo % 2;

chislo = chislo / 2;

if(b == 1)

y = y * a;

a = (a * a) % p;

}

return y % p;

}

// Проверка на взаимную простоту

int vzprost (int a, int b)

{

int q;

int u [3] = { a, 1, 0};

int v [3] = { b, 0, 1};

int T [3];

int c;

while(v [0] != 0)

{

c = u [0] / v [0];

T [0] = u [0] % v [0];

T [1] = u [1] - c * v [1];

T [2] = u [2] - c * v [2];

for (int i = 0; i != 3; i++)

{

u [i] = v [i];

v [i] = T [i];

}

}

return u [0];

}

//обощенный алгоритм Евклида

int evklid (int a, int b)

{

int q, c;

int u [3] = { a, 1, 0};

int v [3] = { b, 0, 1};

int T [3];

while(v [0] != 0)

{

c = u [0] / v [0];

T [0] = u [0] % v [0];

T [1] = u [1] - c * v [1];

T [2] = u [2] - c * v [2];

for (int i = 0; i != 3; i++)

{

u [i] = v [i];

v [i] = T [i];

}

}

q = a + u [2];

return q;

}

int main()

{

setlocale (0, "");

nt m = 18;

//Подбор чисел P и G (подробнее стр.19 - верх, 20 - середина)

int P, q, G;

q = rand() % 30;

q = pprime(q);

P = (2 * q) + 1;

G = 2 + rand() % (P - 1);

if (vozved (G, q, P) == 1)

G++;

int x;//держит в секрете

x = 2 + rand() % (P-1);

int y;

y = vozved (G, x, P);//публикует в качестве открытого ключа

//вычисление хэш-функции

int h = vozved (2, m, P);

int k;

k = 1 + rand() % (P / 2);

for(;;)

{

if (vzprost(k, (P - 1)) == 1)

break;

else

k++;

}

int r, u, s;

r = vozved (G, k, P);

u = (h - (x * r) % (P - 1) + P - 1) % (P - 1);

int kmin1;

kmin1 = evklid (P - 1, k);

s = (kmin1 * u) % (P-1);

///отправляем подписанное сообщение др пользователю <m; r, s>

int rez = vozved(y, r, P);

int rez1 = vozved(r, s, P);

int rezult = rez * rez1 % P;

//если подпись верна, условие выполняется

if (rezult == vozved (G, h, P))

cout << "Подпись подлинная" << endl;

else

cout << "Подпись не подлинная" << endl;

system("pause");

}

6. Криптографический протокол «Электронные деньги»

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

using namespace std;

//подбор простого числа P

int pprime (int number)

{

int count;

while(count != 2)

{

count = 0;

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

{

if (number % i == 0)

count++;

if (count > 2)

{

number++;

break;

}

}

}

return number;

}

//функция быстрого возведения в степень

int bistr (int a, int chislo, int p)

{

int b;

int y = 1;

int t = log2 (chislo);

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

{

b = chislo % 2;

chislo = chislo / 2;

if (b == 1)

{

y = y * a % p;

}

a = (a * a) % p;

}

return y % p;

}

//a ^ chislo * m mod p

int bist (int a, int chislo, int p, int m)

{

int b;

int y = 1;

int t = log2 (chislo);

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

{

b = chislo % 2;

chislo = chislo / 2;

if(b==1)

{

y = y * a;

}

a = (a * a) % p;

}

return (y * m) % p;

}

//проверка на взаимную простоту

int gcda (int a, int b)

{

int q;

int u [3] = { a, 1, 0};

int v [3] = { b, 0, 1};

int T [3];

int c;

while(v [0] != 0)

{

c = u [0] / v [0];

T [0] = u [0] % v [0];

T [1] = u [1] - c * v [1];

T [2] = u [2] - c * v [2];

for (int i = 0; i != 3; i++)

{

u [i] = v [i];

v [i] = T [i];

}

}

return u [0];

}

// ? * d mod F = 1

int gcd (int a, int b)

{

int q;

int u[3] = { a, 1, 0};

int v[3] = { b, 0, 1};

int T[3];

int c;

while(v[0] != 0)

{

c = u[0] / v[0];

T[0] = u[0] % v[0];

T[1] = u[1] - c * v[1];

T[2] = u[2] - c * v[2];

for (int i = 0; i != 3; i++)

{

u[i] = v[i];

v[i] = T[i];

}

}

q = (a + u[2]) % a;

return q;

}

int main()

{

setlocale (0,"");

int schetpok = 10000;

int schetshop = 0;

cout << "Изначально, на счету у покупателя находится: " << schetpok << " $" << endl;

cout << "И на счету у магазина: " << schetshop << " $" << endl << endl;

int P = 3 + rand() % 100;

P = pprime(P);

int Q = 3 + rand() % 100;

Q = pprime(Q);

int N = P * Q;

int F = ((P - 1) * (Q -1));

int d = rand() % 20;

for(;;)

{

if (gcda(d, F) == 1)

break;

else

d++;

}

int c = gcd(F, d);

int n = 2 + rand() % (N - 4);

int r = rand() % 20;

for(;;)

{

if (gcda(r, N) == 1)

break;

else

r++;

}

int nn = bist (r, d, N, n);

int ss = bistr(nn, c, N);

schetpok = schetpok - 100;

int rr = gcd (N, r);

int s = (ss * rr) % N;

cout << "Платежеспособная банкнота нашего покупателя <n,s>: <" << n << ", " << s << "> " << endl;

if (n == bistr(s, d, N))

{

schetshop = schetshop + 100;

cout << "В банке все проверки прошли успешно. Операция выполнена." << endl << endl;

}

else

cout << "Банкнота не прошла все проверки в банке. Операция не выполнена" << endl << endl;

cout << "Счет покупателя после перевода: " << schetpok << " $" << endl;

cout << "Счет магазина после перевода: " << schetshop << " $" << endl;

system("pause");

}

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

...