ЭЦП Фиата-Шамира. Алгоритм и реализация на C#

C#   3 Июль 2013  Автор статьи:  

Подготовка

1) Выбираем однонаправленную хеш-функцию, в данном случае SHA-1. Полученный 160-битный хеш, представленный в виде массива байт, запишем в виде последовательности символов в кодировке Base64, длина которой m=28. Исходное сообщение обозначим как M.

2) Выбираем случайные простые числа p и q,подсчитываем n=p*q. В качестве секретного (закрытого ключа) каждый пользователь должен сгенерировать последовательность различных случайных чисел {a_1,a_2,a_3,…,a_m} ∈ Z_n, взаимно простых с m.

На основе закрытого ключа считается открытый ключ следующим образом: формируется последовательность чисел {b_1,b_2,b_3,…,b_m} ∈ Z_n таких, что b_i=(a_i^(-1))^2 mod n, i=1…m.

Подпись
Алгоритм подписи

Для проверки подлинности подписи сообщения M пользователь на другой стороне использует открытый ключ b_1,b_2,b_3,…,b_m и пару (s,t).

Проверка подписи
Алгоритм проверки подписи
Существует некоторые модификации, которые позволяют улучшить данный алгоритм. Рассмотрим одну из них, а именно улучшение Сильвио Микали и Ади Шамира. Оно заключается в том, чтобы в качестве открытого ключа {b_1,b_2,b_3,…,b_m} берутся первые m простых чисел, то есть: b_1=1,b_2=3,b_3=5 и т.д. Последовательность закрытого ключа {a_1,a_2,a_3,…,a_m} ∈ Z_n состоит из квадратных корней, определяемых как: a_i=sqrt(b_i^(-1)) mod n.
В этой версии у каждого участника должен быть свой модуль n,по которому вычисляется секретный ключ. Такая модификация облегчает проверку подписей, не влияя на время генерации подписей и их безопасность.
Далее представлена реализация алгоритма на языке C#.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
internal class Signature
{
private static SHA1CryptoServiceProvider sha1;
private int m = 28; // длина дайджеста (хэша), генерируемого SHA1
public int N        // собственно сам mod
{
get;
private set;
}
// случайный число, указанное выше в алгоритме
public int P
{
get;
private set;
}
// случайный число, указанное выше в алгоритме
public int Q
{
get;
private set;
}
static Signature()
{
sha1 = new SHA1CryptoServiceProvider();
}
public Signature()
{
Prime prime = new Prime();
do
{
this.P = prime.GetPrime();
this.Q = prime.GetPrime();
this.N = this.P * this.Q;
} while (N < Prime.Limit); // ищем число n как большее, чем рассматриваемые        
}
public Signature(int n)
{
this.N = n;
this.P = 0;
this.Q = 0;
}
// получение секретного ключа
public BigInteger[] GetSecretKey()
{
BigInteger[] secret = new BigInteger[m];
for (int i = 0; i < secret.Length; i++)
{
do
{
secret[i] = Prime.GetCoprime(2, N - 1, N); // получение взаимно простого числа с N в диапазоне от 2 до N-1
} while (secret[i] == 0);
}
return secret;
}        
// получение открытого ключа
public BigInteger[] GetOpenKey(BigInteger[] secret)
{
BigInteger[] open = new BigInteger[m];
Mod mod = new Mod(N);
for (int i = 0; i < open.Length; i++)
{
open[i] = mod.GetSquareMod(mod.GetReverseMod(secret[i]));
}
return open;
}
// получение подписи
public BigInteger GetSignature(BigInteger[] secret, string text, out string hash)
{
Random rnd = new Random();
int r = 0;
do
{
r = rnd.Next(1, N - 1);
} while (r < Prime.Limit);
Mod mod = new Mod(N);
BigInteger u = mod.GetSquareMod(r);
Encoding encoding = Encoding.GetEncoding(1251);
byte[] textBytes = encoding.GetBytes(text + u.ToString());
sha1.ComputeHash(textBytes);
hash = Convert.ToBase64String(sha1.Hash);
BigInteger t = r;
for (int i = 0; i < secret.Length; i++)
{
    t = mod.MultiplyMod(t, mod.PowMod(secret[i], hash[i]));
}
return t;
}
// проверка подписи
public string CheckSignature(BigInteger[] open, string text, string hash, BigInteger t)
{
Mod mod = new Mod(N);
BigInteger w = mod.GetSquareMod(t);
for (int i = 0; i < open.Length; i++)
{
    w = mod.MultiplyMod(w, mod.PowMod(open[i], hash[i]));
}
Encoding encoding = Encoding.GetEncoding(1251);
byte[] textBytes = encoding.GetBytes(text + w.ToString());
sha1.ComputeHash(textBytes);
return Convert.ToBase64String(sha1.Hash);
}
}
}

Следует отметить следующие методы и значения:

GetPrime() — получение простого числа
GetCoprime(int a, int b, int x) — получение взаимно простого числа с x в диапазоне от a до b
GetSquareMod(BigInteger x) — возведение в квадрат в кольце вычетов по mod nMultiplyMod(
MultiplyMod(BigInteger a, BigInteger b) — умножение по mod двух чисел a и b
PowMod(BigInteger a, BigInteger e) — возведение в степень
GetReverseMod(BigInteger a) — получение обратного элемента в кольце вычетов по mod n
Все данные методы реализованы с помощью класса BigInteger и алгоритмов, которые вы можете посмотреть в других статьях на нашем сайте, посвященных работе с простыми числами.
Prime.Limit — максимальное число, до которого ищутся простые числа (в данной задаче бралось как 10 000)
Также наиболее правильно будет разделить проверку подписи и ее получение на разные классы, что тут не делалось для удобства.

————————
Используемые источники:
1. Алферов А. П. Основы криптографии / А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. – М.: Гелиос АРФ, 2002. – 480 с.: ил. – ISBN 5-85438-025-0.
2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнайер. – М.: Триумф, 2012. – ISBN 5-89392-055-4.
3. Электронная цифровая подпись/ Википедия – свободная энциклопедия [Электронный ресурс]. – URL: http://ru.wikipedia.org/wiki/Электронная_цифровая_подпись. – 26.04.13. – Загл. с экрана.

Научиться программировать

  • на Delphi

  • на Java

  • на C++