СОДЕРЖАНИЕ ВВЕДЕНИЕ 3 1. АССИМЕТРИЧНЫЕ СИСТЕМЫ ШИФРОВАНИЯ. КРИПТОСИСТЕМА ЭЛЬ-ГАМАЛЯ 3 1.1 ПОЯВЛЕНИЯИ РАЗВИТИЕ ДАННОГО АЛГОРИТМА 3 1.2 ОПИСАНИЕ АЛГОРИТМА 3 1.3 ДОСТОИНСТВА И НЕДОСТАТКИ 3 1.4 ПРИМЕНЕНИЕ АЛГОРИТМА НА ПРАКТИКЕ 3 1.5 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ 3 2. ЭЛЕКТРОННАЯ ЦИФРОВАЯ ПОДПИСЬ. СХЕМА БЫСТРОЙ ЦИФРОТОВОЙ СИГНАТУРЫ ШАМИРА 3 2.1 ПОЯВЛЕНИЯИ РАЗВИТИЕ ДАННОГО АЛГОРИТМА 3 2.2 ОПИСАНИЕ АЛГОРИТМА 3 2.3 ДОСТОИНСТВА И НЕДОСТАТКИ 3 2.4 ПРИМЕНЕНИЕ АЛГОРИТМА НА ПРАКТИКЕ 3 5.5 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ 3 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 3
ВВЕДЕНИЕ Криптографическая система с открытым ключом (или асимметричное шифрование, асимметричный шифр) — система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в осно-ве HTTPS), в SSH. Также используется в PGP, S/MIME [5]. Схема Эль-Гамаля — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94) [10]. Цели использования метода Эль-Гамаля: безопасность системы, которая основывается на усложненности вычисления дискретных логарифмов в конечном поле. Области применения метода Эль-Гамаля: используется для контроля доступа к данным, подтверждения личности пользователя, аутентификации данных, подписания «реальных документов», т.е. в межбанковских расчетах, при работе банка с физическими лицами; электронная коммерция, электронные переводы, электронные деньги и др [4, с. 117-120]. Быстрая цифровая подпись – вариант цифровой подписи, использую-щий алгоритм с гораздо меньшим (в десятки раз) числом вычислений модульной арифметики по сравнению с традиционными схемами ЭЦП. Схема быстрой электронной подписи, как и обычная, включает в себя алгоритм генерации ключевых пар пользователя, функцию вычисления подписи и функцию проверки подписи [2]. Схема быстрой цифровой сигнатуры Шамира – схема разделения секрета, широко используемая в криптографии, которая позволяет реализовать (k, n) - пороговое разделение секретного сообщения между n сторонами так, что только любые k и более строн (k<=n) могли восстановить секрет. При этом любые k-1 и менее сторон не смогут восстановить секрет [9]. Цели использования данной схемы: обеспечение совершенной секретности против попытки вычисления секрета, а также защита секретной информации от потери и компрометации. Область применения данной схемы: применение в аппаратных криптогра-фических модулях, где она используется для многопользовательской авторизации в инфраструктуре открытых ключей; цифровая стенография для скрытой передачи в цифровых изображениях. Также схема Шамира может осуществлять нанесение цифрового водяного знака при передаче цифрового видео и генерации персонального криптографического ключа, используемого в биометрических системах аутентификации [12, с. 588-589].
1. АССИМЕТРИЧНЫЕ СИСТЕМЫ ШИФРОВАНИЯ. КРИПТОСИ-СТЕМА ЭЛЬ-ГАМАЛЯ 1.1 ПОЯВЛЕНИЕ И РАЗВИТИЕ АЛГОРИТМА Египетский криптограф Тахер Эль-Гамаль в 1985 году опубликовал статью «Криптосистема с открытым ключом и схема цифровой подписи на основе дискретных логарифмов». Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации [7]. В 1984 году Тахер Эль-Гамаль получил степень PhD в Стэнфордском университете. Его исследованием была разработка «цифровой подписи по схеме Эль-Гамаля». Так этот стандарт впервые назвал Джим Омур — основатель компании Cylink. Он пытался лоббировать в правительстве придание этой криптосистеме статус государственного стандарта. Но правительство не хотело проводить лицензирование продукта, а взяло его за основу для цифрового стандарта подписи (DSS). Тахер Эль-Гамаль не мог запатентовать алгоритм, поскольку был иностранным студентом-выпускником. По правилам он должен был оставаться студентом до выдачи патента. Вместо поисков обхода этих правил, он решил опубликовать своё исследование. Это стало достоянием общественности, и многие тысячи людей написали публикации на эту тему. Благодаря этому шагу его имя стало известно всему миру. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллма.
1.2 ОПИСАНИЕ АЛГОРИТМА Данный алгоритм является альтернативой алгоритму RSA и, при равном значении ключа, обеспечивает ту же криптостойкость. Стойкость алгоритма Эль-Гамаля основана на трудности вычисления дискретных логарифмов. Участники информационного процесса выбирают простое число р и про-извольное целое число q, являющееся первообразным корнем по модулю р. Сторона А генерирует секретный ключ ka<р и вычисляет открытый ключ Уа = qka (mod р). Сторона B выбирает число kb<р и с его помощью зашифровывает пере-даваемое сообщение Мследующим образом: Yb = qkb (mod р) и С = M (Yakb (mod р)). Величина М представляет собой последовательность двоичных символов, передаваемых в канал связи. Величина Yakb (modр)перед суммированием пре-образуется в последовательность двоичных символов. Сторона A, получив сообщение в виде Yb и С, восстанавливает его: М = (Ybka (mod р)) С . Рисунок 1 – Алгоритм Эль-Гамаля Алгоритм Эль-Гамаля - первый криптографический алгоритм с открытым ключом, используемый для шифрования сообщений и цифровых подписей, применение которого не ограничено патентами США.
1.3 ДОСТОИНСТВА И НЕДОСТАТКИ По сравнению с методом RSA данный метод имеет целый ряд преимуществ: 1. При заданном уровне стойкости алгоритма цифровой подписи целые числа, с которыми приходится проводить вычисления, имеют запись на 25% короче, что соответственно уменьшает сложность вычислений почти в 2 раза и позволяет заметно сократить объем используемой памяти; 2. При выборе параметров достаточно проверить всего два достаточно легко проверяемых условия; Недостатки: 1. В частности, при том же уровне стойкости он оперирует с целыми числами на 25% короче, чем RSA, но длина подписи получается в 1,5 раза больше, что увеличивает время ее вычисления и ужесточает требования к надежности канала связи [1].
1.4 ПРИМЕНЕНИЕ АЛГОРИТМА НА ПРАКТИКЕ Алгоритм криптосистем Эль-Гамаля применяется в компании Vindicia, которая является поставщиком платежных услуг. Примечательно, что Тахер Эль-Гамаль состоит в совете директоров данной компании.
1.5 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ Для программной реализации использован язык Java. В приложении А к данной контрольной работы представлен код, который шифрует и дешифрует сообщение криптосистемой Эль-Гамаля.
2.1 ПОЯВЛЕНИЕИ РАЗВИТИЕ АЛГОРИТМА Понятие электронной подписи появилось в середине 1970-х годов. В 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман разработали первый в мире криптографический алгоритм – RSA, который без дополнительных модификаций можно использовать для создания примитивных цифровых подписей.Вскоре после RSA были разработаны другие ЭЦП, такие как алгоритмы цифровой подписи Рабина, Меркле [3]. На самом деле алгоритм RSA был придуман еще в 1973 Клиффордом Коксом, но его исследования были мгновенно зашифрованы, поэтому на суд общественности была предложена работа Ривеста, Шамира и Адлемана [13].В основе их работы лежала теория, что Источнику1 достаточно отправить Источнику2 сообщение, которым Источник2 может закрыть послание и вернуть обратно Источнику1. Получается, что ключей должно быть два — ключ шифрования и ключ дешифровки.
2.2 ОПИСАНИЕ АЛГОРИТМА ZN обозначает кольцо целых чисел по модулю N, t и p — параметры безопасности, обычно Роль центра аутентификации ключей (ЦАК): ЦАК выбирает: случайные простые числа p и q так, чтобы однонаправленную хэш-функцию h: свои собственные секретный и открытый ключи. ЦАК публикует и открытый ключ. Секретный ключ ЦАК используется для подписи создаваемых им открытых ключей. Для создания таких подписей ЦАК может использовать любую безопасную схему ЭЦП. Генерация пользовательских ключей. Каждый пользователь выбирает секретный ключ , состоящий из случайных чисел si, которая меняется от 1 до N таких, что НОД(si,N)=1 для всех s от 1 до k. Создание подписи может быть ускорено, если выбирать в каче-стве s1,...,sk небольшие целые числа. Безопасность такой схемы основана на предположении о том, что вычисление корней 2t mod N является трудным [2]. Регистрация пользователей. ЦАК проверяет соответствие пользователя, создаёт строку {\displaystyle \ I} , содержащую имя, адрес и т. д. и создаёт подпись {\displaystyle \ S} для пары {\displaystyle \ (I,v)} , состоящую из {\displaystyle \ I} и открытого ключа пользователя {\displaystyle \ v} . Создание подписи. Входное сообщение {\displaystyle \ m} , секретный ключ {\displaystyle \ s=(s_{1},\cdots \,s_{k})} и {\displaystyle \ N} — модуль, по которому проводят вычисления. 1. Выбирается случайное число {\displaystyle \ r} из диапазо-на {\displaystyle \ [1,N]} , вычисляется {\displaystyle \ x=r^{2^{t}}} . 2. Вычисляется {\displaystyle \ e=(e_{1}1,\cdots \,e_{t}k)=h(x,m)} . 3. Вычисляется {\displaystyle \ y=r\prod \nolimits _{j=1}^{k}s_{j}^{\sum \nolimits _{i=1}^{t}e_{ij}*2^{i-1}}\mod \ N} . Подписью на выходе является пара {\displaystyle \ (e,y)} . Создание подписи требует не более {\displaystyle \ {k*t+t-1}} операций умножения по модулю, а в среднем для случайного {\displaystyle \ e} требуется только {\displaystyle \ t(k+2)/2+1} операций умножения. Проверка подписи. Входные данные — подпись {\displaystyle \ (e,y)} , сообще-ние{\displaystyle \ m} , {\displaystyle \ v=(v_{1},\cdots \,v_{k})} , {\displaystyle \ I,S,N} . 1. Проверяется подпись {\displaystyle \ S} для {\displaystyle \ (I,v)} . 2. Вычисляется {\displaystyle \ z=y^{2^{t}}\prod \nolimits _{j=1}^{k}v_{j}^{\sum \nolimits _{i=1}e_{ij}*2^{i-1}}\mod \ N} . 3. Проверяется, что {\displaystyle \ e=h(z,m)} . Для проверки подписи требуется в среднем для случайного {\displaystyle \ e} {\displaystyle \ t(k+2)/2+1} операций умножения по модулю, макси-мум {\displaystyle \ {k*t+t}} . Безопасность подписи. Чтобы подделать подпись сообщения {\displaystyle \ m} , криптоаналитик должен решить уравнение {\displaystyle \ e=h(y^{2^{t}}\prod \nolimits _{j=1}^{k}v_{j}^{\sum \nolimits _{i=1}^{t}e_{i,j}*2^{i-1}},m)\mod \ N} для {\displaystyle \ e} и {\displaystyle \ y} . В настоящее время неизвестно алгоритмов для решения этого уравнения.
2.3 ДОСТОИНСТВА И НЕДОСТАТКИ Достоинства: возможность выработки цифровых подписей для нескольких различных сообщений с использованием одного секретного ключа; сравнительная простота алгоритмов вычисления и проверки подписей; хорошая изученность алгоритмов факторизации с полиномиальной сложностью [8]. Недостатки большая длина ключа (определяется числом m) [11].
2.4 ПРИМЕНЕНИЕ АЛГОРИТМА НА ПРАКТИКЕ Данный алгоритм применяется в электронном документообороте. Также алгоритм используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении он применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании. Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах.
2.5 ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ Для программной реализации использован язык С#. В приложении Б к данной контрольной работы представлен код, который шифрует и дешифрует сообщение криптосистемой Эль-Гамаля
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Алгоритма цифровой подписи Эль-Гамаля, преимущества по сравнению с методом RSA, недостатки [Электронный ресурс]. – Режим доступа: http://5fan.ru/wievjob.php?id=28565. – Дата доступа: 4.12.2016. 2. Быстрая цифровая подпись [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Быстрая_цифровая_подпись. – Дата доступа: 4.12.2016. 3. История электронной подписи [Электронный ресурс] // Сертисфера: все об электронной подписи. – Режим доступа: http://www.certisfera.ru/page/istoriya-elektronnoy-podpisi. – Дата доступа: 6.12.2016. 4. Коляда, М. Г. Технология криптосистемы Эль-Гамаля с помощью пакета компьютерной алгебры «Mathematіca» / М. Г. Коляда // Научные труды Донецкого национального технического университета. Серия “Информатика, кибернетика и вычислительная техника” (ИКВТ-2010). Выпуск 12 (165). – Донецк: ГВУЗ “ДонНТУ”, 2010. – С. 117-120. 5. Криптосистема с открытым ключом [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Криптосистема_с_открытым_ключом. – Дата доступа: 4.12.2016. 6. Мао, В. Современная криптография: теория и практика / Венбо Мао. – М.: Издательский дом Вильямс, 2005. – 768 с. 7. Практическое применение алгоритма асинхронного шифрования Эль-Гамаля и его реализация для обмена сообщениями // Молодежный научный фо-рум: Технические и математические науки: электр. сб. ст. по материалам XXXIV студ. междунар. заочной науч.-практ. конф. – М.: «МЦНО». – 2016. – № 5 (34) [Электронный ресурс]. – Режим доступа. – http://nauchforum.ru/archive/MNF_tech/5(34).pdf. – Дата доступа: 4.12.2016. 8. Савельева, А. А. Исследование эффективности алгоритмов дискретного логарифмирования, использующих факторную базу [Электронный ресурс] / А. А. Савельева. – Режим доступа: https://www.hse.ru/data/202/314/1234/Савельева.pdf. – Дата доступа: 6.12.2016. 9. Схема разделения секрета Шамира [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Схема_разделения_секрета_Шамира. – Дата доступа: 4.12.2016. 10. Схема Эль-Гамаля [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Схема_Эль-Гамаля. – Дата доступа: 4.12.2016. 11. Цифровая подпись Эль-Гамаля. Схема RSA [Электронный ресурс] // Студопедия. – Режим доступа: http://studopedia.org/4-95478.html. – Дата доступа: 6.12.2016. 12. Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Брюс Шнайер. – М.: Триумф, 2002. – 816 с. 13. Электронная подпись. История появления и развития [Электронный ресурс]. – Режим доступа: https://habrahabr.ru/post/242675. – Дата доступа: 6.12.2016.
Приложение А. Криптосистема Эль-Гамаля packagejavaapplication8; importjava.math.*; importjava.util.*; importjava.security.*; import java.io.*; importjava.util.Scanner; public class algo { public static void main(String[] args) throws IOException { Scanner scan = new Scanner(System.in); BigInteger p, b, c, secretKey; Random sc = new SecureRandom(); secretKey = new BigInteger("1234"); // // public key calculation // System.out.println("secretKey = " + secretKey); p = BigInteger.probablePrime(64, sc); b = new BigInteger("3"); c = b.modPow(secretKey, p); System.out.println("p = " + p); System.out.println("b = " + b); System.out.println("c = " + c); // // Encryption // System.out.print("Введите сообщение (большое число) -->"); String s = scan.next(); BigInteger X = new BigInteger(s); BigInteger r = new BigInteger(64, sc); BigInteger EC = X.multiply(c.modPow(r, p)).mod(p); BigIntegerbrmodp = b.modPow(r, p); System.out.println("Сообщение = " + X); System.out.println("целоечисло r такое, что 1 < r < (p в€’ 1) ---> r = " + r); //System.out.println("EC = " + EC); System.out.println("Перваячастьзашифрованногосообщенияb^r mod p = " + brmodp); BigIntegercrmodp = brmodp.modPow(secretKey, p); BigInteger d = crmodp.modInverse(p); BigInteger ad = d.multiply(EC).mod(p); System.out.println("Втораячастьзашифрованногосообщенияc^r mod p = " + crmodp); System.out.println("Дешифрованное сообщение: " + ad);
} }
Приложение Б. Цифровая подпись Шамира using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms; using System.Numerics; using System.Text.RegularExpressions;
namespace Shamir { public partial class Form1 : Form { public Form1() { InitializeComponent(); }
// read secret from textbox BigInteger my_secret = new BigInteger(); my_secret = BigInteger.Parse(textBox1.Text);
// read square from textbox( MUST BE A PRIME NUMBER ) BigInteger my_square = new BigInteger(); my_square = BigInteger.Parse(textBox2.Text);
// reading N - total people // reading K - people that can recovery secrets by shades. int n = 0, k = 0;
k = Convert.ToInt32(textBox3.Text); n = Convert.ToInt32(textBox4.Text);
//dictionary for keep shades, and creating that shades by secret, square, n, k, and is need random x? Dictionary<BigInteger,BigInteger> my_dict = Shamir(my_secret, my_square, n, k, (checkBox1.Checked ? true : false ));
int i = 0; foreach(KeyValuePair<BigInteger, BigInteger> kv in my_dict) { richTextBox1.Text += "[" + (i + 1) + "] (" + kv.Key + ", " + kv.Value + ")\n"; i++; }
}
//update polynomial text in top. Can be bugged when k too big. private void update_f() { if (textBox3.Text == "") return;
string line = "( "; for (int j = 1; j < Convert.ToInt32(textBox3.Text); j++) { line = line + "a[" + j + "]*x^" + (Convert.ToInt32(textBox3.Text) - j) + " + "; // some magic here ._. }
line = line + textBox1.Text + " ) mod P"; lagrange.Text = line; // lagrange - label that keep polynomial form. Only for beauty of programm view :3 }
// Recovery secret by shades in <richTextBox1.Text>. Something like external buffer. // Need to have shades, right square(P). private void button2_Click(object sender, EventArgs e) { Dictionary<BigInteger, BigInteger> a = SplitPair(richTextBox1.Text);
// Tracks if Square, Secret, K or N changed, and recreating polynomial view. private void textBox_TextChanged(object sender, EventArgs e) { update_f(); }
//-------------------------------------------------------------- // Shamir secret sharing //-------------------------------------------------------------- private Dictionary<BigInteger, BigInteger> Shamir(BigInteger secret, BigInteger p, int n, int k, bool is_random_x) { BigInteger[] Koeff = new BigInteger[k - 1]; BigInteger[] rand_x = new BigInteger[n];
Dictionary<BigInteger, BigInteger> total_keys = new Dictionary<BigInteger, Big-Integer>(); Random rnd = new Random();
// -------------------------------------- // Creating random koeff a[i]. That will be deleted after creating of shades // -------------------------------------- for (int i = 0; i < k - 1; i++) // gets random a(n), n = 1 ... (k - 1) Koeff[i] = MathMod(BigInteger.Abs(getRandom((i + 1) * 2)), p) ;
// -------------------------------------- // creating random X-part of shades ( N times, for N peoples) // -------------------------------------- if (is_random_x) { for (int i = 0; i < n; i++) // gets random x, x count = n rand_x[i] = MathMod(rnd.Next(1, int.MaxValue - 1), p); // p - BigInt, rand_x[i] - int, can't be rnd.Next of 2 type of value :c } else { for (int i = 0; i < n; i++) // such non-random! rand_x[i] = MathMod((i + 1), p); }
// -------------------------------------- // starting Shamir secret sharing // -------------------------------------- BigInteger result = new BigInteger(); BigInteger powered = new BigInteger();
for (int i = 0; i < n; i++) { result = result + secret;
for (int j = 1; j < k; j++) // calculate polynomial function for current i, where i = 1 .. n { powered = BigInteger.Pow(rand_x[i], k - j); result += Koeff[j - 1] * powered; }
result = MathMod(result, p);
if (!total_keys.ContainsKey(rand_x[i])) total_keys.Add(rand_x[i], result);
result = 0; // set null for next calculates } return total_keys; // return pair of (x, y) points }
//-------------------------------------------------------------- // Recovering secret by some shades // for theoretical GO TO WIKIPEDIA, reference - shamir secret sharing, lagrange inter-polation //-------------------------------------------------------------- private BigInteger deShamir(Dictionary<BigInteger, BigInteger> kv_pairs, BigInteger p) { int k = kv_pairs.Count;
BigInteger secret = new BigInteger(0); BigInteger high_part = new BigInteger(1); // high part of lagrange intepolation BigInteger low_part = new BigInteger(1); // low part of lagrange interpolation
// first_kv - shade number 1 // second_kv - shade number 2 foreach (KeyValuePair<BigInteger, BigInteger> first_kv in kv_pairs) { foreach (KeyValuePair<BigInteger, BigInteger> second_kv in kv_pairs) { if (first_kv.Key != second_kv.Key) { high_part = high_part * ((-1) * second_kv.Key); // -1 caused that we need x - xj, but our x = 0, that now (-xj) low_part = low_part * (first_kv.Key - second_kv.Key); // calculate low part } }
// Lagrange interpolation have division, but we need only integer numbers, so // a * a^(-1) = 1 // but we can make some fun and: // a * a^(-1) = 1 (mod p) // so, when we have modulo, we can change a^(-1) to another number, that give us similar result ^.^ // a * b = 1 (mod p). // b can be calculated by Evklid algorithm in form 'ax + by = gcd(a,b)' (*1) // so we set 2 numbers, a = low_part and b = p, and gets gcd and 2 numbers, x and y. // We know that gcd(prime_number, any_number) = 1, so change (*1) to our rules: // low_part * x + p*y = 1 // In this form y always be the '0' (ave MATH!), so we get // low_part*x = 1 // where x - our (low_part)^(-1) // MAGIIIIIIIIIIC! iVector temp = Evklid(low_part, p);
low_part = MathMod(temp.y, p);
high_part = MathMod((high_part * low_part), p); // let high part temporary storage all lart of 'li' (see lagrange interpolation)
secret += high_part * first_kv.Value; // summ_all( y * li ) high_part = 1; low_part = 1; } secret = MathMod(secret, p); // Let restrict out sercet by out square. return secret; // Done. You are delicious }
//-------------------------------------------------------------- // Other Help Functions //--------------------------------------------------------------
// Allow to get from string KV-pair of shades private Dictionary<BigInteger, BigInteger> SplitPair(string input_string) { Dictionary<BigInteger, BigInteger> return_value = new Dictionary<BigInteger, Big-Integer>();
Regex a = new Regex(@"\[\d*\]\s|\(|\)"); // remove '[<number>] ' from string and remove '(' and ')' input_string = a.Replace(input_string, "");
a = new Regex(@"\n"); // split big string by '\n' string[] arr = a.Split(input_string);
a = new Regex(@"\,\s"); // split one pair by ','
// Save all shades(points) for dictionary. foreach (string str in arr) { if (str != "") { string[] kv = a.Split(str); BigInteger key = BigInteger.Parse(kv[0]); BigInteger value = BigInteger.Parse(kv[1]); return_value.Add(key, value); } }
return return_value; }
// Getting random BigInteger value. Careful, one length = one number! // Function bugged, need to rewrite it ._. public BigInteger getRandom(int length) { Random random = new Random(); random.Next(); byte[] data = new byte[length]; random.NextBytes(data); return new BigInteger(data); }
// Mathematical modulo, that caused by C# modulo(%) is work wrong for mathematical needs. public static BigInteger MathMod(BigInteger a, BigInteger b) { return (BigInteger.Abs(a * b) + a) % b; }
public iVector Evklid(BigInteger a, BigInteger b) { iVector u = new iVector(a, 1, 0); iVector v = new iVector(b, 0, 1); iVector T = new iVector(0, 0, 0); BigInteger q = 0;
while (v.x != 0) { q = u.x / v.x;
T.x = MathMod(u.x, v.x);
T.y = u.y - q * v.y; T.z = u.z - q * v.z;
u.set(v); // u = v, but we need to CHANGE value, not CHANGE POINTER. v.set(T); // u = v, but we need to CHANGE value, not CHANGE POINTER. }
return u; } }
//Some abstract type of vector created for clearness of Evklid algorithm. public class iVector { public BigInteger x; public BigInteger y; public BigInteger z;
