 |
Отечественный стандарт цифровой подписи
|
|
|
|
Отечественный стандарт цифровой подписи обозначается как ГОСТ Р 34.10–94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSA. В нем используются следующие параметры:
р — большое простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит;
q — простой сомножитель числа 
, имеющий длину 254...256 бит.
а — любое число, меньшее , причем такое, что 
;
х — некоторое число, меньшее q;
Кроме того, этот алгоритм использует однонаправленную хэш-функцию 
. Стандарт ГОСТ Р 34.11–94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147–89.
Первые три параметра p, q и а являются открытыми и могут быть общими для всех пользователей сети. Число х является секретным ключом. Число у является открытым ключом.
Чтобы подписать некоторое сообщение m, а затем проверить подпись, выполняются следующие шаги.
1. Пользователь А генерирует случайное число k, причем 
.
2. Пользователь А вычисляет значения
Если 
, то значение 
принимают равным единице. Если 
, то выбирают другое значение k и начинают снова.
Цифровая подпись представляет собой два числа:
и 
.
Пользователь А отправляет эти числа пользователю В.
3. Пользователь В проверяет полученную подпись, вычисляя Если 
, то подпись считается верной.
Различие между этим алгоритмом и алгоритмом DSA заключается в том, что в DSA
что приводит к другому уравнению верификации.
Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является отражением стремления разработчиков отечественного стандарта к получению более безопасной подписи.
|
|
|
Этот стандарт вступил в действие с начала 1995 г.
Задание на курсовую работу
Написать на произвольном языке программирования программу, реализующую алгоритм цифровой подписи (EGSA, DSA или ГОСТ 34.10–94) с использованием указанной в таблице 1 хэш-функции в соответствии с индивидуальным вариантом. Варианты заданий приведены в таблице 2.
Таблица 2 — Варианты заданий на курсовую работу
| № вар. | Алгоритм цифровой подписи | Алгоритм хэш-функции | № вар. | Алгоритм цифровой подписи | Алгоритм хэш-функции |
| 1. | EGSA | 2. | DSA | ||
| 3. | EGSA | 4. | DSA | ||
| 5. | EGSA | 6. | DSA | ||
| 7. | EGSA | 8. | DSA | ||
| 9. | EGSA | 10. | DSA | ||
| 11. | EGSA | 12. | DSA | ||
| 13. | EGSA | 14. | ГОСТ | ||
| 15. | EGSA | 16. | ГОСТ | ||
| 17. | EGSA | 18. | ГОСТ | ||
| 19. | EGSA | 20. | ГОСТ | ||
| 21. | EGSA | 22. | ГОСТ | ||
| 23. | EGSA | 24. | ГОСТ | ||
| 25. | DSA | 26. | ГОСТ | ||
| 27. | DSA | 28. | ГОСТ | ||
| 29. | DSA | 30. | ГОСТ | ||
| 31. | DSA | 32. | ГОСТ | ||
| 33. | DSA | 34. | ГОСТ | ||
| 35. | DSA | 36. | ГОСТ |
Заключение
Выбор для конкретных ИС должен быть основан на глубоком анализе слабых и сильных сторон тех или иных методов защиты. Обоснованный выбор той или иной системы защиты в общем-то должен опираться на какие-то критерии эффективности. К сожалению, до сих пор не разработаны подходящие методики оценки эффективности криптографических систем.
Наиболее простой критерий такой эффективности - вероятность раскрытия ключа или мощность множества ключей (М). По сути это то же самое, что и криптостойкость. Для ее численной оценки можно использовать также и сложность раскрытия шифра путем перебора всех ключей.
Однако, этот критерий не учитывает других важных требований к криптосистемам:
− невозможность раскрытия или осмысленной модификации информации на основе анализа ее структуры,
− совершенство используемых протоколов защиты,
|
|
|
− минимальный объем используемой ключевой информации,
− минимальная сложность реализации (в количестве машинных операций), ее стоимость,
− высокая оперативность.
Желательно конечно использование некоторых интегральных показателей, учитывающих указанные факторы.
Для учета стоимости, трудоемкости и объема ключевой информации можно использовать удельные показатели - отношение указанных параметров к мощности множества ключей шифра.
Часто более эффективным при выборе и оценке криптографической системы является использование экспертных оценок и имитационное моделирование.
В любом случае выбранный комплекс криптографических методов должен сочетать как удобство, гибкость и оперативность использования, так и надежную защиту от злоумышленников циркулирующей в ИС информации.
Приложение.
Пример реализации арифметики больших целых чисел
В данном примере реализованы операции сложения (BigInt Add(BigInt value)), вычитания (BigInt Substract(BigInt value)), умножения (BigInt Multiply(int value)), деления с остатком (BigInt Divide(int v, out int r)), возведения в степень k по модулю n (BigInt Pow(BigInt k, BigInt n)) и вычисления обратного по модулю n (BigInt Inverse(BigInt n)) на языке C#.
using System;
using System.Collections.Generic;
using System.Text;
namespace LongArithmetic
{
class BigInt
{
private List<int> _arr = new List<int>();//массив который хранит большое числа
private const int Order = 8; //база
private bool _sign = true;
private const int MyBase = 2 ^ Order;
public BigInt Zero = new BigInt("0");
public BigInt One = new BigInt("1");
public BigInt(string s)
{
int tempValue = 0;
int tempOrder = 0;
_sign = true;
for (int i = s.Length - 1; i >= 0; i--)
{
if (i == 0 && s[0] == '-')
_sign = false;
else
{
if (tempOrder == Order)
{
_arr.Add(tempValue);
tempValue = int.Parse(s[i].ToString());
tempOrder = 1;
}
else
{
tempValue = tempValue +
(int) Math.Pow(10, tempOrder)*int.Parse(s[i].ToString());
tempOrder++;
}
}
}
if (tempOrder!= 0)
_arr.Add(tempValue);
}
public BigInt(IEnumerable<int> arr, bool sign)
{
foreach (var t in arr)
_arr.Add(t);
_sign = sign;
}
public BigInt(List<int> arr, bool sign)
{
_arr = arr;
_sign = sign;
}
public override string ToString()
{
var ans = new StringBuilder();
if (!_sign)
ans.Append('-');
ans.Append(_arr[_arr.Count - 1].ToString());
for (int i = _arr.Count - 2; i >= 0; i--)
{
string temp = _arr[i].ToString();
int zeroCount = Order - temp.Length;
for (int j = 0; j < zeroCount; j++)
ans.Append('0');
ans.Append(temp);
}
return ans.ToString();
}
private int AbsCompareTo(BigInt other)
{
var ans = 0;
if (_arr.Count == other._arr.Count)
{
for (int i = 0; i < _arr.Count; i++)
{
if (_arr[i] > other._arr[i])
ans = 1;
if (_arr[i] < other._arr[i])
ans = -1;
|
|
|
}
}
else
{
if (_arr.Count > other._arr.Count)
ans = 1;
if (_arr.Count < other._arr.Count)
ans = -1;
}
return ans;
}
public int CompareTo(BigInt other)
{
if (_sign && other._sign) //оба положительных
return AbsCompareTo(other);
if (_sign &&!other._sign) //первое число положительное
return 1;
if (!_sign && other._sign) //второе число положительное
return -1;
return -1 * AbsCompareTo(other);//оба отрицательные
}
public void ChangeSign(bool sgn)
{
_sign = sgn;
}
private List<int> Normalize(List<int> arr)
{
while (_arr.Count > 0 && arr[_arr.Count - 1] == 0) //удаляем лидирующие нули
_arr.RemoveAt(_arr.Count - 1);
return arr;
}
public BigInt AbsAdd(BigInt value)
{
int k = 0;//значение переноса
int n = Math.Max(_arr.Count, value._arr.Count);//максимальная длина числа
var ans = new List<int>();//результирующий массив
for (int i = 0; i < n; i++)
{
//временное значение i-го разряда из первого числа
int tempA = (_arr.Count > i)? _arr[i]: 0;
//временное значение i-го разряда из второго числа
int tempB = (value._arr.Count > i)? value._arr[i]: 0;
ans.Add(tempA + tempB + k);
if (ans[i] >= MyBase) //если результат получился больше базы
{
ans[i] -= MyBase;
k = 1;
}
else
k = 0;
}
if (k == 1)
ans.Add(k);
return new BigInt(ans, true);
}
public BigInt AbsSubstract(BigInt value)
{
if (AbsCompareTo(value) == -1)
{
BigInt temp = value.AbsSubstract(this);
temp.ChangeSign(false);
return temp;
}
int k = 0;//перенос
int n = Math.Max(_arr.Count, value._arr.Count);
var ans = new List<int>();
for (int i = 0; i < n; i++)
{
int tempA = (_arr.Count > i)? _arr[i]: 0;
int tempB = (value._arr.Count > i)? value._arr[i]: 0;
ans.Add(tempA - tempB - k);
if (ans[i] < 0)
{
ans[i] += MyBase; //прибавляем базу
k = 1; //задаем перенос
}
else
k = 0;
}
return new BigInt(Normalize(ans), true);
}
public BigInt Add(BigInt value)
{
if (_sign && value._sign)
return AbsAdd(value);
if (!_sign && value._sign)
return value.AbsSubstract(this);
if (_sign &&!value._sign)
return AbsSubstract(value);
BigInt ans = AbsAdd(value);
ans.ChangeSign(false);
return ans;
}
public BigInt Substract(BigInt value)
{
if (_sign && value._sign)
return AbsSubstract(value);
if (!_sign && value._sign)
{
BigInt ans = AbsAdd(value);
ans.ChangeSign(false);
return ans;
}
if (_sign &&!value._sign)
return AbsAdd(value);
return value.AbsSubstract(this);
}
public BigInt Multiply(int value)
{
BigInt ans = AbsMultiply(Math.Abs(value));
if (_sign && value >= 0)
return ans;
if (!_sign && value < 0)
return ans;
ans.ChangeSign(false);
return ans;
}
public BigInt AbsMultiply(int value)
{
if (value >= MyBase)
throw new Exception("This value is bigger than base");
int k = 0;
var ans = new List<int>();
foreach (var t in _arr)
{
long temp = t * (long)value + k;
ans.Add((int)(temp % MyBase));
k = (int)(temp / MyBase);
}
ans.Add(k);
return new BigInt(Normalize(ans), true);
}
public BigInt Multiply(BigInt value)
|
|
|
{
BigInt ans = AbsMultiply(value);
if ((_sign && value._sign) || (!_sign &&!value._sign))
return ans;
ans.ChangeSign(false);
return ans;
}
public BigInt AbsMultiply(BigInt value)
{
var ans = Zero;
for (var i = 0; i < _arr.Count; i++)
{
var temp = value.AbsMultiply(_arr[i]);
for (var j = 0; j < i; j++)
temp._arr.Insert(0, 0);
ans = ans.AbsAdd(temp);
}
return ans;
}
public BigInt Divide(int v, out int r)
{
if (v == 0)
throw new Exception("divide by zero");
var ans = AbsDivide(Math.Abs(v), out r);
if ((_sign && v > 0) || (!_sign && v < 0))
return ans;
ans.ChangeSign(false);
r = -r;
return ans;
}
public BigInt AbsDivide(int v, out int r)
{
var ans = new int[_arr.Count];//результат деления
r = 0;//остаток
int j = _arr.Count - 1;
while (j >= 0)
{
long cur = r * (long)(MyBase) + _arr[j];
ans[j] = (int)(cur / v);
r = (int)(cur % v);
j--;
}
return new BigInt(ans, true);
}
private static int Divide(out BigInt q, out BigInt r, BigInt u, BigInt v)
{
var ans = AbsDivide(out q, out r, u, v);
if ((u._sign && v._sign) || (!u._sign &&!v._sign))
return ans;
q.ChangeSign(!q._sign);
r.ChangeSign(!r._sign);
return ans;
}
public static int AbsDivide(out BigInt q, out BigInt r, BigInt u, BigInt v)
{
//начальная инициализация
int n = v._arr.Count;
int m = u._arr.Count - v._arr.Count;
var tempArray = new int[m + 1];
tempArray[m] = 1;
q = new BigInt(tempArray, true);
//Нормализация
int d = (MyBase / (v._arr[n - 1] + 1));
u = u.Multiply(d);
v = v.Multiply(d);
if (u._arr.Count == n + m) //аккуратная проверка на d==1
u._arr.Add(0);
//Начальная установка j
int j = m;
//Цикл по j
while (j >= 0)
{
//Вычислить временное q
var cur = u._arr[j + n] * (long)(MyBase) + u._arr[j + n - 1];
//нормализация помогает не выпрыгнуть за границу типа
var tempq = (int)(cur / v._arr[n - 1]);
var tempr = (int)(cur % v._arr[n - 1]);
do
{
if (tempq!= MyBase &&
tempq*(long) v._arr[n - 2] <= MyBase*(long) tempr + u._arr[j + n - 2])
break;
tempq--;
tempr += v._arr[n - 1];
}
while (tempr < MyBase);
//Умножить и вычесть
var u2 = new BigInt(u._arr.GetRange(j, n + 1), true);
u2 = u2.Substract(v.Multiply(tempq));
bool flag = false;
if (!u2._sign)//если отрицательные
{
flag = true;
var bn = new List<int>();
for (int i = 0; i <= n; i++)
bn.Add(0);
bn.Add(1);
u2.ChangeSign(true);
u2 = new BigInt(bn, true).Substract(u2);
}
//Проверка остатка
q._arr[j] = tempq;
if (flag)
{
//Компенсировать сложение
q._arr[j]--;
u2 = u2.Add(v);
if (u2._arr.Count > n + j)
u2._arr.RemoveAt(n + j);
}
//меняем u, так как все вычисления происходят с его разрядами
for (int h = j; h < j + n; h++)
{
if (h - j >= u2._arr.Count)
u._arr[h] = 0;
else
u._arr[h] = u2._arr[h - j];
}
j--;
}
q._arr = q.Normalize(q._arr);
//Денормализация
int unusedR;
r = new BigInt(u._arr.GetRange(0, n), true).Divide(d, out unusedR);
return 0;
}
public BigInt Mod(BigInt v)
{
if (AbsCompareTo(v) <= -1)
return this;
if (v._arr.Count == 1)
{
int tempr;
Divide(v._arr[0], out tempr);
return new BigInt(tempr.ToString());
}
BigInt r;
BigInt q;
Divide(out q, out r, this, v);
return r;
}
public BigInt Div(BigInt v)
{
BigInt q;
if (CompareTo(v) > -1)
{
if (v._arr.Count == 1)
{
int tempr;
return Divide(v._arr[0], out tempr);
}
BigInt r;
Divide(out q, out r, this, v);
}
else
return Zero;
return q;
}
public BigInt Pow(BigInt k, BigInt n)
{
var a = new BigInt(_arr, _sign);
var b = One;
while (k.CompareTo(Zero) > 0)
{
int r;
var q = k.Divide(2, out r);
if (r == 0)
{
k = q;
a = a.Multiply(a).Mod(n);// [ a = (a*a)%n; ]
}
else
{
k = k.Substract(One);
b = b.Multiply(a).Mod(n);// [ b = (b*a)%n; ]
}
}
return b;
}
public BigInt Inverse(BigInt n)
{
var a = new BigInt(ToString());
BigInt b = n, x = Zero, d = One;
while (a.CompareTo(Zero) == 1)//a>0
{
var q = b.Div(a);
var y = a;
a = b.Mod(a);
b = y;
y = d;
d = x.Substract(q.Multiply(d));
|
|
|
x = y;
}
x = x.Mod(n);
if (x.CompareTo(Zero) == -1) //x<0
x = (x.Add(n)).Mod(n);
return x;
}
}
}
Рекомендуемая литература
Основная:
Баричев С.Г., Серов Р.Е. Основы современной криптографии. Учебное пособие. - М.: Машиностроение, 2010. - 754 тc.: ил.
Брассар Ж. Современная криптология. Учебное пособие. - М.: ИЛ, 2010. - 362 тc.: ил.
Вакка Джон. Секреты безопасности в Internet. Учебное пособие. - К.: Диалектика, 2008. - 512 c.: ил.
Мельников В.В. Защита информации в компьютерных системах; Учебное пособие. - М.: Финансы и статистика; Электроинформ, 2012. - 368 тc.: ил.
Чирилло Д. Обнаружение хакерских атак. Учебное пособие. - СПб: Питер, 2012. - 864 тc.: ил.
Ярочкин В.И. Информационная безопасность. Учебное пособие. - М.: Академический Проект, 2008. - 544 тc.: ил.
Ященко В.В. Введение в криптографию. Учебное пособие. - М.: Огни, 2010. - 226 тc.: ил.
Дополнительная:
Завгородский В.И. Комплексная защита информации в компьютерных системах. Учебное пособие. - М.: Логос; ПБОЮЛ Н.А. Егоров, 2001.- 264 тс.: ил.
Зегжда Д.П., Ивашко А.М. Основы безопасности информационных систем. Учебное пособие. – М.: Горячая линия – Телеком, 2000.- 452 тс.: ил.
Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. Учебное пособие. - М.: Радио и связь, 2001.- 376 тс.: ил.
Нагда Б.Ю. Информационная безопасность и защита информации. Методические указания к лабораторным работам. - СОФ МИСиС, 2003.- 46 тс.
Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. Учебное пособие. - М.: КУДИЦ-ОБРАЗ, 2001.- 363 тс.: ил.
|
|
|
