ЭЦП Фиата-Шамира. Алгоритм и реализация на 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#.

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++