Длинная арифметика (1Cv8)
Что это
Длинная арифметика — в вычислительной технике операции над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Частный случай — арифметика произвольной точности — относится к арифметике, в которой длина чисел ограничена только объёмом доступной памяти.
Источник: Длинная арифметика. Материал из Википедии — свободной энциклопедии
Реалиация
Примеры реализации:
- На VisualBasic: http://www.di-mgt.com.au/src/basModExp.bas.html
- На JavaScript: http://www-cs-students.stanford.edu/~tjw/jsbn/
Медиа:1Cv8_ДлиннаяАрифметика.dt
Модуль "ДлиннаяАрифметика"
--Павел Лазарев 13:08, 20 декабря 2009 (SAMT)
- реализация проста и работает правильно, но очень медленно
- возможные оптимизации
- использовать массив не 8-битных целых (байтовый) а 32-битных целых
- реализовать на основе http://www-cs-students.stanford.edu/~tjw/jsbn/, но там остро не хватает битовых операций..
- может быть поможет что-то из Общедоступные COM-объекты Windows
- может быть использовать реализацию http://www-cs-students.stanford.edu/~tjw/jsbn/ через Windows Script Host / JScript
- еще одна реализация на javascript: http://assl.sullof.com/assl/
- и еще: http://www.jcryption.org/
- также существуют реализации хэшей md5 на javascript: http://pajhome.org.uk/crypt/md5/index.html
Использование объекта MSScriptControl.ScriptControl для запуска скриптов:
- http://www.script-coding.info/MSScriptControl.html
- http://www.forum.mista.ru/topic.php?id=252049
- http://www.kb.mista.ru/article.php?id=66
- http://www.forum.mista.ru/topic.php?id=438082
- http://support.microsoft.com/kb/184740
<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)
- Если Клиент Тогда
Процедура Тест_ИзСтроки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", Ложь); Возврат спДоступныеТесты; КонецФункции
- КонецЕсли
</source>