Длинная арифметика (1Cv8)

Материал из КинтВики
Перейти к: навигация, поиск


Что это


Длинная арифметика — в вычислительной технике операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена только объёмом доступной памяти.


Источник: Длинная арифметика. Материал из Википедии — свободной энциклопедии


Реалиация

Примеры реализации:

Медиа:1Cv8_ДлиннаяАрифметика.dt

Модуль "ДлиннаяАрифметика"

--Павел Лазарев 13:08, 20 декабря 2009 (SAMT)


Использование объекта MSScriptControl.ScriptControl для запуска скриптов:

<source lang=1c> // --Павел Лазарев 13:00, 20 декабря 2009 (SAMT) //Источник: http://www.di-mgt.com.au/src/basModExp.bas.html

Функция ВСтроку16(мзЧисло) Экспорт

   строка = "";

Для индекс = 0 по мзЧисло.Количество() - 1 Цикл байт = мзЧисло[индекс]; ПерваяЦифра = Цел(байт/16); ВтораяЦифра = байт % 16; строка = строка + ШестнадцетиричнаяЦифра(ПерваяЦифра) + ШестнадцетиричнаяЦифра(ВтораяЦифра); КонецЦикла;

   Возврат строка;

КонецФункции

Функция ШестнадцетиричнаяЦифра(цифра) Возврат Сред("0123456789ABCDEF", цифра + 1, 1); КонецФункции

Функция ИзСтроки16(Знач строка) Экспорт КоличествоЦифр = СтрДлина(строка); КоличествоБайт = Цел(КоличествоЦифр / 2); Если КоличествоБайт * 2 < КоличествоЦифр Тогда строка = "0" + строка; КоличествоЦифр = СтрДлина(строка); КоличествоБайт = Цел(КоличествоЦифр / 2); КонецЕсли; Если КоличествоБайт = 0 Тогда Возврат Новый Массив; КонецЕсли;

строка = ВРег(строка); НомерБайта = 0; мзЧисло = Новый Массив(КоличествоБайт); Для НомерБайта = 0 по КоличествоБайт - 1 Цикл НомерЦифры = НомерБайта * 2 + 1; ПерваяЦифра = КодСимвола(строка, НомерЦифры); ВтораяЦифра = КодСимвола(строка, НомерЦифры + 1); мзЧисло[НомерБайта] = ШестнадцетиричноеЧисло(ПерваяЦифра) * 16 + ШестнадцетиричноеЧисло(ВтораяЦифра); КонецЦикла;

Возврат мзЧисло; КонецФункции

Функция ШестнадцетиричноеЧисло(Код) Если Код >= 48 И Код <= 57 Тогда Возврат Код - 48; ИначеЕсли Код >= 65 И Код <= 70 Тогда Возврат Код - 65 + 10; Иначе Возврат 0; КонецЕсли; КонецФункции

Процедура мзРазделитьНаДва(мзЧисло) Экспорт // Divides multiple-precision integer x by 2 by shifting to right by one bit //Dim d As Long //Dim i As Integer //d = 0 //For i = 0 To UBound(x) // d = d Or x(i) // x(i) = CByte((d \ 2) And &HFF) // If (d And &H1) Then // d = &H100 // Else // d = 0 // End If //Next

частное = 0; Для i = 0 To мзЧисло.Количество() - 1 Цикл частное = частное + мзЧисло[i]; мзЧисло[i] = Цел(частное / 2) % 256; Если (частное % 2) = 1 Тогда частное = 256; Иначе частное = 0; КонецЕсли; КонецЦикла;

КонецПроцедуры


Функция мзЭтоНуль(мзЧисло) Экспорт Для каждого байт из мзЧисло Цикл Если байт <> 0 Тогда Возврат Ложь; КонецЕсли; КонецЦикла; Возврат Истина; КонецФункции

Процедура мзВыровнятьДлину(мзЧислоА, мзЧислоБ, мзЧислоМ) Экспорт количество = Макс(мзЧислоА.Количество(), Макс(мзЧислоБ.Количество(), мзЧислоМ.Количество())) + 1; мзУстановитьДлину(мзЧислоА, количество); мзУстановитьДлину(мзЧислоБ, количество); мзУстановитьДлину(мзЧислоМ, количество); КонецПроцедуры

Процедура мзУстановитьДлину(мзЧисло, количество) длина = мзЧисло.Количество(); Для индекс = длина по количество - 1 Цикл мзЧисло.Вставить(0, 0); КонецЦикла; КонецПроцедуры


Процедура мзДобавитьПоМодулю(мзЧислоА, мзЧислоБ, мзЧислоМ) Экспорт //' Computes a = (a + b) mod m // Dim i As Integer // Dim d As Long // ' 1. Add a = a + b // d = 0 // For i = nLen - 1 To 0 Step -1 // d = CLng(a(i)) + CLng(b(i)) + d // a(i) = CByte(d And &HFF) // d = d \ &H100 // Next // ' 2. If a > m then a = a - m // For i = 0 To nLen - 2 // If a(i) <> m(i) Then // Exit For // End If // Next // If a(i) >= m(i) Then // Call aSubtract(a, m, nLen) // End If // ' 3. Return a in-situ

// ' 1. Add a = a + b d = 0; nlen = мзЧислоА.Количество(); Для индекс = 1 по nlen Цикл i = nlen - индекс; d = мзЧислоА[i] + мзЧислоБ[i] + d; мзЧислоА[i] = d % 256; d = Цел(d / 256); КонецЦикла; // ' 2. If a > m then a = a - m

Для i = 0 по nlen - 2 Цикл Если мзЧислоА[i] <> мзЧислоМ[i] Тогда Прервать; КонецЕсли; КонецЦикла;

Если мзЧислоА[i] > мзЧислоМ[i] Тогда мзВычесть(мзЧислоА, мзЧислоМ); КонецЕсли;

КонецПроцедуры

Процедура мзВычесть(мзЧислоА, мзЧислоБ) Экспорт //' Computes a = a - b // Dim i As Integer // Dim borrow As Long // Dim d As Long ' NB d is signed // // borrow = 0 // For i = nLen - 1 To 0 Step -1 // d = CLng(a(i)) - CLng(b(i)) - borrow // If d < 0 Then // d = d + &H100 // borrow = 1 // Else // borrow = 0 // End If // a(i) = CByte(d And &HFF) // Next

   nlen = мзЧислоА.Количество();

borrow = 0; Для индекс = 1 по nlen Цикл i = nlen - индекс; d = мзЧислоА[i] - мзЧислоБ[i] - borrow; Если d < 0 Тогда d = d + 256; borrow = 1; Иначе borrow = 0; КонецЕсли; мзЧислоА[i] = d % 256; КонецЦикла;


КонецПроцедуры

Функция мзУмножитьПоМодулю(мзЧислоА, мзЧислоБ, мзЧислоМ) Экспорт //Private Function aModMult(abX() As Byte, abY() As Byte, abMod() As Byte, nLen As Integer) As Variant //' Returns w = (x * y) mod m // Dim w() As Byte // Dim x() As Byte // Dim y() As Byte // Dim nBits As Integer // // ' 1. Set w = 0, and temps x = abX, y = abY // ReDim w(nLen - 1) // x = abX // y = abY // ' 2. From LS bit to MS bit of X do: // For nBits = nLen * 8 To 1 Step -1 // ' 2.1 if x is odd then w = (w + y) mod m // If (x(nLen - 1) And &H1) <> 0 Then // Call aModAdd(w, y, abMod, nLen) // End If // ' 2.2 x = x / 2 // Call DivideByTwo(x) // ' 2.3 if x != 0 then y = (y + y) mod m // If aIsZero(x, nLen) Then Exit For // Call aModAdd(y, y, abMod, nLen) // Next // aModMult = w

   nlen = мзЧислоА.Количество();

w = Новый Массив(nlen); //-1 Для i = 0 по nlen - 1 Цикл // -2 w[i] = 0; КонецЦикла;


x = Новый Массив(nlen); y = Новый Массив(nlen); Для i = 0 по nlen - 1 Цикл x[i] = мзЧислоА[i]; y[i] = мзЧислоБ[i]; КонецЦикла;

Для nBits = 1 по nlen * 8 Цикл Если x[nlen -1] % 2 <> 0 Тогда мзДобавитьПоМодулю(w, y, мзЧислоМ); КонецЕсли;

мзРазделитьНаДва(x);

Если мзЭтоНуль(x) Тогда Прервать; КонецЕсли;

мзДобавитьПоМодулю(y, y, мзЧислоМ);

КонецЦикла;

Возврат w; КонецФункции

Функция мзСтепеньПоМодулю(мзЧислоА, мзЧислоБ, мзЧислоМ) Экспорт //' Computes a = b^e mod m and returns the result in a byte array as a VARIANT // Dim a() As Byte // Dim e() As Byte // Dim s() As Byte // Dim nBits As Long // // ' Perform right-to-left binary exponentiation // ' 1. Set A = 1, S = b // ReDim a(nLen - 1) // a(nLen - 1) = 1 // ' NB s and e are trashed so use copies // s = abBase // e = abExponent // ' 2. While e != 0 do: // For nBits = nLen * 8 To 1 Step -1 // ' 2.1 if e is odd then A = A*S mod m // If (e(nLen - 1) And &H1) <> 0 Then // a = aModMult(a, s, abModulus, nLen) // End If // ' 2.2 e = e / 2 // Call DivideByTwo(e) // ' 2.3 if e != 0 then S = S*S mod m // If aIsZero(e, nLen) Then Exit For // s = aModMult(s, s, abModulus, nLen) // DoEvents // Next // // ' 3. Return(A) // aModExp = a //

   nlen = мзЧислоА.Количество();

a = Новый Массив(nlen); Для i = 0 по nlen - 1 Цикл a[i] = 0; КонецЦикла; a[nlen - 1] = 1;

s = Новый Массив(nlen); e = Новый Массив(nlen); Для i = 0 по nlen - 1 Цикл s[i] = мзЧислоА[i]; e[i] = мзЧислоБ[i]; КонецЦикла;

Для nBits = 1 по nlen * 8 Цикл Если e[nlen -1] % 2 <> 0 Тогда a = мзУмножитьПоМодулю(a, s, мзЧислоМ); КонецЕсли;

мзРазделитьНаДва(e);

Если мзЭтоНуль(e) Тогда Прервать; КонецЕсли;

s = мзУмножитьПоМодулю(s, s, мзЧислоМ);

КонецЦикла;

Возврат a;

КонецФункции

Процедура мзУдалитьВедущиеНули(мзЧисло) Экспорт Пока мзЧисло.Количество() > 0 Цикл Если мзЧисло[0] = 0 Тогда мзЧисло.Удалить(0); Иначе Возврат; КонецЕсли; КонецЦикла; КонецПроцедуры


// А ^ Б mod М Функция СтепеньПоМодулю(стрЧислоА, стрЧислоБ, стрЧислоМ) Экспорт мзЧислоА = ИзСтроки16(стрЧислоА); мзЧислоБ = ИзСтроки16(стрЧислоБ); мзЧислоМ = ИзСтроки16(стрЧислоМ);

мзВыровнятьДлину(мзЧислоА, мзЧислоБ, мзЧислоМ); мзРезультат = мзСтепеньПоМодулю(мзЧислоА, мзЧислоБ, мзЧислоМ); мзУдалитьВедущиеНули(мзРезультат);

Возврат ВСтроку16(мзРезультат); КонецФункции

</source>

Модуль тестирования

<source lang=1c> // --Павел Лазарев 13:00, 20 декабря 2009 (SAMT)

  1. Если Клиент Тогда

Процедура Тест_ИзСтроки16() Экспорт мзЧисло = ДлиннаяАрифметика.ИзСтроки16(""); Тестирование.ПроверитьРавенство(0, мзЧисло.Количество());

мзЧисло = ДлиннаяАрифметика.ИзСтроки16("1"); Тестирование.ПроверитьРавенство(1, мзЧисло.Количество()); Тестирование.ПроверитьРавенство(1, мзЧисло[0]);

мзЧисло = ДлиннаяАрифметика.ИзСтроки16("ffe"); Тестирование.ПроверитьРавенство(2, мзЧисло.Количество()); Тестирование.ПроверитьРавенство(15, мзЧисло[0]); Тестирование.ПроверитьРавенство(254, мзЧисло[1]);


мзЧисло = ДлиннаяАрифметика.ИзСтроки16("FfeE01"); Тестирование.ПроверитьРавенство(3, мзЧисло.Количество()); Тестирование.ПроверитьРавенство(255, мзЧисло[0]); Тестирование.ПроверитьРавенство(238, мзЧисло[1]); Тестирование.ПроверитьРавенство(1, мзЧисло[2]);

мзЧисло = ДлиннаяАрифметика.ИзСтроки16("deadbeef"); Тестирование.ПроверитьРавенство(4, мзЧисло.Количество()); Тестирование.ПроверитьРавенство(222, мзЧисло[0]); Тестирование.ПроверитьРавенство(173, мзЧисло[1]); Тестирование.ПроверитьРавенство(190, мзЧисло[2]); Тестирование.ПроверитьРавенство(239, мзЧисло[3]); КонецПроцедуры

Процедура Тест_ВСтроку16() Экспорт мзЧисло = Новый Массив;

Тестирование.ПроверитьРавенство("", ДлиннаяАрифметика.ВСтроку16(мзЧисло));

мзЧисло.Очистить(); мзЧисло.Добавить(1); Тестирование.ПроверитьРавенство("01", ДлиннаяАрифметика.ВСтроку16(мзЧисло));

мзЧисло.Очистить(); мзЧисло.Добавить(255); мзЧисло.Добавить(238); мзЧисло.Добавить(1); Тестирование.ПроверитьРавенство("FFEE01", ДлиннаяАрифметика.ВСтроку16(мзЧисло));

мзЧисло.Очистить(); мзЧисло.Добавить(222); мзЧисло.Добавить(173); мзЧисло.Добавить(190); мзЧисло.Добавить(239); Тестирование.ПроверитьРавенство("DEADBEEF", ДлиннаяАрифметика.ВСтроку16(мзЧисло)); КонецПроцедуры

Процедура Тест_мзРазделитьНаДва() Экспорт мзЧисло = ДлиннаяАрифметика.ИзСтроки16("ffee"); ДлиннаяАрифметика.мзРазделитьНаДва(мзЧисло); Тестирование.ПроверитьРавенство("7FF7", ДлиннаяАрифметика.ВСтроку16(мзЧисло));

мзЧисло = ДлиннаяАрифметика.ИзСтроки16("5518f65d"); ДлиннаяАрифметика.мзРазделитьНаДва(мзЧисло); Тестирование.ПроверитьРавенство("2A8C7B2E", ДлиннаяАрифметика.ВСтроку16(мзЧисло));

мзЧисло = ДлиннаяАрифметика.ИзСтроки16("5518f65dFFEE01DEADBEEF"); ДлиннаяАрифметика.мзРазделитьНаДва(мзЧисло); Тестирование.ПроверитьРавенство("2A8C7B2EFFF700EF56DF77", ДлиннаяАрифметика.ВСтроку16(мзЧисло)); КонецПроцедуры

Процедура Тест_мзЭтоНуль() Экспорт мзЧисло = ДлиннаяАрифметика.ИзСтроки16("ffee"); Тестирование.ПроверитьРавенство(Ложь, ДлиннаяАрифметика.мзЭтоНуль(мзЧисло));

мзЧисло = ДлиннаяАрифметика.ИзСтроки16(""); Тестирование.ПроверитьРавенство(Истина, ДлиннаяАрифметика.мзЭтоНуль(мзЧисло));

мзЧисло = ДлиннаяАрифметика.ИзСтроки16("00000000000000000000000000000000000000"); Тестирование.ПроверитьРавенство(Истина, ДлиннаяАрифметика.мзЭтоНуль(мзЧисло));

мзЧисло = ДлиннаяАрифметика.ИзСтроки16("00000000000000000000000000000030000000"); Тестирование.ПроверитьРавенство(Ложь, ДлиннаяАрифметика.мзЭтоНуль(мзЧисло)); КонецПроцедуры

Процедура Тест_мзВыровнятьДлину() Экспорт мзЧислоА = ДлиннаяАрифметика.ИзСтроки16("FFEE"); мзЧислоБ = ДлиннаяАрифметика.ИзСтроки16("5518f65d"); мзЧислоМ = ДлиннаяАрифметика.ИзСтроки16("FFEEDD");

ДлиннаяАрифметика.мзВыровнятьДлину(мзЧислоА, мзЧислоБ, мзЧислоМ); Тестирование.ПроверитьРавенство(5, мзЧислоА.Количество()); Тестирование.ПроверитьРавенство(5, мзЧислоБ.Количество()); Тестирование.ПроверитьРавенство(5, мзЧислоМ.Количество());

Тестирование.ПроверитьРавенство("000000FFEE", ДлиннаяАрифметика.ВСтроку16(мзЧислоА)); Тестирование.ПроверитьРавенство("005518F65D", ДлиннаяАрифметика.ВСтроку16(мзЧислоБ)); Тестирование.ПроверитьРавенство("0000FFEEDD", ДлиннаяАрифметика.ВСтроку16(мзЧислоМ)); КонецПроцедуры

Процедура Тест_мзВычесть() Экспорт мзЧислоА = ДлиннаяАрифметика.ИзСтроки16("5518f65d"); мзЧислоБ = ДлиннаяАрифметика.ИзСтроки16("FFEE"); мзЧислоМ = ДлиннаяАрифметика.ИзСтроки16("");

ДлиннаяАрифметика.мзВыровнятьДлину(мзЧислоА, мзЧислоБ, мзЧислоМ); ДлиннаяАрифметика.мзВычесть(мзЧислоА, мзЧислоБ);

Тестирование.ПроверитьРавенство("005517F66F", ДлиннаяАрифметика.ВСтроку16(мзЧислоА)); КонецПроцедуры


Процедура Тест_мзДобавитьПоМодулю() Экспорт мзЧислоА = ДлиннаяАрифметика.ИзСтроки16("FFEE"); мзЧислоБ = ДлиннаяАрифметика.ИзСтроки16("5518f65d");//5519F64B мзЧислоМ = ДлиннаяАрифметика.ИзСтроки16("550FEEDD"); //a = (a+b) mod m ДлиннаяАрифметика.мзВыровнятьДлину(мзЧислоА, мзЧислоБ, мзЧислоМ); ДлиннаяАрифметика.мзДобавитьПоМодулю(мзЧислоА, мзЧислоБ, мзЧислоМ); Тестирование.ПроверитьРавенство("00000A076E", ДлиннаяАрифметика.ВСтроку16(мзЧислоА));


мзЧислоА = ДлиннаяАрифметика.ИзСтроки16("FFEE"); мзЧислоБ = ДлиннаяАрифметика.ИзСтроки16("5518f65d");//5519F64B мзЧислоМ = ДлиннаяАрифметика.ИзСтроки16("32A8C7B2EF"); //a = (a+b) mod m ДлиннаяАрифметика.мзВыровнятьДлину(мзЧислоА, мзЧислоБ, мзЧислоМ); ДлиннаяАрифметика.мзДобавитьПоМодулю(мзЧислоА, мзЧислоБ, мзЧислоМ); Тестирование.ПроверитьРавенство("00005519F64B", ДлиннаяАрифметика.ВСтроку16(мзЧислоА)); КонецПроцедуры

Процедура Тест_мзУмножитьПоМодулю() Экспорт мзЧислоА = ДлиннаяАрифметика.ИзСтроки16("FFEE"); мзЧислоБ = ДлиннаяАрифметика.ИзСтроки16("5518f65d");//5512FA9BAD76 мзЧислоМ = ДлиннаяАрифметика.ИзСтроки16("550FEEDD"); //(a*b) mod m ДлиннаяАрифметика.мзВыровнятьДлину(мзЧислоА, мзЧислоБ, мзЧислоМ); мзЧислоАА = ДлиннаяАрифметика.мзУмножитьПоМодулю(мзЧислоА, мзЧислоБ, мзЧислоМ); // Тестирование.ПроверитьРавенство("000E2F47B1", ДлиннаяАрифметика.ВСтроку16(мзЧислоАА));

КонецПроцедуры


Процедура Тест_СтепеньПоМодулю() Экспорт

Тестирование.ПроверитьРавенство("5B56", ДлиннаяАрифметика.СтепеньПоМодулю("3c", "03", "face")); Тестирование.ПроверитьРавенство("6A35DDD3C9CF", ДлиннаяАрифметика.СтепеньПоМодулю("beef", "03", "1000000000000")); Тестирование.ПроверитьРавенство("C9CF", ДлиннаяАрифметика.СтепеньПоМодулю("beef", "03", "10000"));

//' Do a mini-RSA encryption with 32-bit key: //' Public key (n, e) = (0x5518f65d, 0x11) //' Private key d = 0x2309cd31 //' Message m = 0x35b9a3cb //' Encrypt c = m^e mod n = 35b9a3cb^11 mod 5518f65d = 528C41E5 //' Decrypt m' = c^d mod n = 528C41E5^2309cd31 mod 5518f65d = 35B9A3CB Тестирование.ПроверитьРавенство("528C41E5", ДлиннаяАрифметика.СтепеньПоМодулю("35b9a3cb", "11", "5518f65d")); Тестирование.ПроверитьРавенство("35B9A3CB", ДлиннаяАрифметика.СтепеньПоМодулю("528C41E5", "2309cd31", "5518f65d"));

КонецПроцедуры

//' An example of an RSA calculation using mpModExp from //' "Some Examples of the PKCS Standards", //' An RSA Laboratories Technical Note, //' Burton S. Kaliski Jr., November 1, 1993. //' RSA key is 508 bits long. //' WARNING: this may take some time! Процедура Тест_RSA508() Экспорт


strMod = "0A66791DC6988168 |DE7AB77419BB7FB0 |C001C62710270075 |142942E19A8D8C51 |D053B3E3782A1DE5 |DC5AF4EBE9946817 |0114A1DFE67CDC9A |9AF55D655620BBAB"; strExp = "010001"; strPri = "0123C5B61BA36EDB |1D3679904199A89E |A80C09B9122E1400 |C09ADCF7784676D0 |1D23356A7D44D6BD |8BD50E94BFC723FA |87D8862B75177691 |C11D757692DF8881"; strMsg = "1FFFFFFFFFFFF |FFFFFFFFFFFFFFFF |FFFFFFFFFFFFFFFF |FFFFFFFFFF003020 |300C06082A864886 |F70D020205000410 |DCA9ECF1C15C1BD2 |66AFF9C8799365CD"; strOK = "6DB36CB18D3475B |9C01DB3C78952808 |0279BBAEFF2B7D55 |8ED6615987C85186 |3F8A6C2CFFBC89C3 |F75A18D96B127C71 |7D54D0D8048DA8A0 |544626D17A2A8FBE";

//' Sign, i.e. Encrypt with private key, s = m^d mod n strSig = ДлиннаяАрифметика.СтепеньПоМодулю(strMsg, strPri, strMod); Тестирование.ПроверитьРавенство(strOK, strSig);

//' Verify, i.e. Decrypt with public key m' = s^e mod n strVer = ДлиннаяАрифметика.СтепеньПоМодулю(strSig, strExp, strMod); Тестирование.ПроверитьРавенство(strVer, strMsg);

КонецПроцедуры

Процедура Тест_RSA1() Экспорт

// пример с http://ru.wikipedia.org/wiki/Rsa //' Do a mini-RSA encryption //' Public key (n, e) = (8BF9FF, 3) //' Private key (n, d) = (8BF9FF, 5D415B) //' Message m = 1B207 //' Encrypt c = m^e mod n = 1B207^3 mod 8BF9FF = 3DD329 //' Decrypt m' = c^d mod n = 3DD329^5D415B mod 8BF9FF = 1B207 Тестирование.ПроверитьРавенство("3DD329", ДлиннаяАрифметика.СтепеньПоМодулю("1B207", "3", "8BF9FF")); Тестирование.ПроверитьРавенство("01B207", ДлиннаяАрифметика.СтепеньПоМодулю("3DD329", "5D415B", "8BF9FF"));

КонецПроцедуры

Процедура Тест_Diffie_Hellman() Экспорт //' A very simple example of Diffie-Hellman key exchange. //' CAUTION: Practical use requires numbers of 1000-2000+ bits in length //' and other checks on suitability of p and g. //' EXPLANATION OF SIMPLE DIFFIE-HELLMAN //' 1. Both parties agree to select and share a public generator, say, g = 3 //' and public prime modulus p = 0xc773218c737ec8ee993b4f2ded30f48edace915f //' 2. Alice selects private key x = 0x849dbd59069bff80cf30d052b74beeefc285b46f //' 3. Alice's public key is Ya = g^x mod p. Alice sends this to Bob. //' 4. To send a concealed, shared secret key to Alice, Bob picks a secret random number //' say, y = 0x40a2cf7390f76c1f2eef39c33eb61fb11811d528 //' 5. Bob computes Yb = g^y mod p and sends this to Alice. //' 6. Bob can computes the shared key k = Ya^y mod p, //' to use for further communications with Alice //' 7. Alice can compute the same shared key k = Yb^x mod p, //' to use for further communications with Bob. //' Note: k = Ya^y = (g^x)^y = g^(xy) = Yb^x = (g^y)^x = g^(xy) mod p //' An eavesdropper only sees g, p, Ya and Yb. //' It is easy to compute Y=g^x mod p but it is //' difficult to compute x given g^x mod p. //' This is the discrete logarithm problem.


//' Alice computes Ya = g^x mod p Ya = ДлиннаяАрифметика.СтепеньПоМодулю("3", "849dbd59069bff80cf30d052b74beeefc285b46f", "c773218c737ec8ee993b4f2ded30f48edace915f"); //' Bob computes Yb = g^y mod p Yb = ДлиннаяАрифметика.СтепеньПоМодулю("3", "40a2cf7390f76c1f2eef39c33eb61fb11811d528", "c773218c737ec8ee993b4f2ded30f48edace915f"); //' Alice computes the secret key k = Yb^x mod p Ka = ДлиннаяАрифметика.СтепеньПоМодулю(Yb, "849dbd59069bff80cf30d052b74beeefc285b46f", "c773218c737ec8ee993b4f2ded30f48edace915f"); //' Bob computes the secret key k = Ya^y mod p Kb = ДлиннаяАрифметика.СтепеньПоМодулю(Ya, "40a2cf7390f76c1f2eef39c33eb61fb11811d528", "c773218c737ec8ee993b4f2ded30f48edace915f");

Тестирование.ПроверитьРавенство(Ka, Kb); КонецПроцедуры

Процедура ПередВыполнениемТеста() Экспорт

КонецПроцедуры

Процедура ПослеВыполненияТеста() Экспорт КонецПроцедуры

Функция ДоступныеТесты() Экспорт спДоступныеТесты = Новый СписокЗначений; спДоступныеТесты.Добавить("Тест_ВСтроку16", "ВСтроку16", Истина); спДоступныеТесты.Добавить("Тест_ИзСтроки16", "ИзСтроки16", Истина); спДоступныеТесты.Добавить("Тест_мзРазделитьНаДва", "мзРазделитьНаДва", Истина); спДоступныеТесты.Добавить("Тест_мзЭтоНуль", "мзЭтоНуль", Истина); спДоступныеТесты.Добавить("Тест_мзВыровнятьДлину", "мзВыровнятьДлину", Истина); спДоступныеТесты.Добавить("Тест_мзВычесть", "мзВычесть", Истина); спДоступныеТесты.Добавить("Тест_мзДобавитьПоМодулю", "мзДобавитьПоМодулю", Истина); спДоступныеТесты.Добавить("Тест_мзУмножитьПоМодулю", "мзУмножитьПоМодулю", Истина); спДоступныеТесты.Добавить("Тест_СтепеньПоМодулю", "СтепеньПоМодулю", Истина); спДоступныеТесты.Добавить("Тест_RSA508", "RSA508", Ложь); спДоступныеТесты.Добавить("Тест_RSA1", "RSA Пример 1", Истина); спДоступныеТесты.Добавить("Тест_Diffie_Hellman", "Diffie_Hellman Пример 1", Ложь); Возврат спДоступныеТесты; КонецФункции

  1. КонецЕсли

</source>