Длинная арифметика (1Cv8) — различия между версиями

Текущая версия на 09:55, 7 октября 2010

Содержание

1 Что это
2 Реалиация
3 Модуль "ДлиннаяАрифметика"
4 Модуль тестирования

Что это

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

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

Реалиация

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

На VisualBasic: http://www.di-mgt.com.au/src/basModExp.bas.html
- http://www.di-mgt.com.au/crypto.html
На JavaScript: http://www-cs-students.stanford.edu/~tjw/jsbn/
- http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js

Медиа: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 для запуска скриптов:

// --[[Участник:Павел Лазарев|Павел Лазарев]] 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(мзРезультат);
КонецФункции

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

// --[[Участник:Павел Лазарев|Павел Лазарев]] 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", Ложь);
	Возврат спДоступныеТесты;
КонецФункции

#КонецЕсли

Длинная арифметика (1Cv8) — различия между версиями

Текущая версия на 09:55, 7 октября 2010

Содержание

Что это

Реалиация

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

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

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Продукты

Инструменты