Размещено на http://www.allbest.ru/

Формирование пароля с помощью однонаправленной функции

1. Выберите по номеру задания K диапазон чисел

2. Определите простое целое число p с помощью этого диапазона.

Последовательность действий по выбору простого числа следующая:

2.1 Выбирается случайное целое число с помощью стандартного датчика случайных чисел, которое затем тестируется на принадлежность к простому числу.

2.2 Для теста на принадлежность к простому числу выбранного целого числа используется тест Леманна или тест Рабина-Миллера (см. Приложение 1).

Для выполнения этого пункта задания используется программа GEN2. EXE, запускаемая с помощью меню ФАЙЛ программы, содержащейся в папке VIS1. По запросу программы вводятся параметры:

dn - левая граница диапазона задания;

dk - правая граница диапазона задания;

numb - количество итераций для проверки на простоту генерируемого числа (используется тест Леманна). Программа выводит результат - значение числа p.

3. Выберите целое число из диапазона

<

4. Выберите секретный пароль (целое число из диапазона

<).

5. Выберите открытый пароль по формуле

Для вычисления используйте алгоритм Приложения 2.

Для выполнения этого пункта задания используется программа MODN1. EXE,

запускаемая с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры a, x,p. Программа выводит результат - значение открытого пароля y.

6. Выберите защищаемую программу. Предусмотрите в этой программе запрос открытого пароля y, чисел a, p и секретного пароля x. Аутентификация пользователя и допуск к использованию программы определяется по совпадению открытого пароля y с вычисляемым в программе значением .

Для выполнения этого пункта задания можно использовать программу PAROLE14. EXE, запускаемую с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы PAROLE14. EXE вводятся параметры y, a, x,p. В случае совпадения y со значением программа выводит результат - надпись friend (друг), а при несовпадении - надпись enemy (враг).

Замечание. Для устранения опасности несанкционированного доступа (при подсматривании Ваших действий) целесообразно при каждом использовании программы применять новые открытые и секретные пароли.

Формирование пароля с помощью однонаправленной функции с потайным ходом (алгоритм проверки цифровой подписи RSA)

1. Выберите диапазон чисел

2. Определите два простых числа p и q с помощью этого диапазона.

Последовательность действий по выбору простого числа аналогична предыдущей лабораторной работе:

Для выполнения этого пункта задания используется программа GEN1. EXE, запускаемая с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры:

dn - левая граница диапазона задания;

dk - правая граница диапазона задания;

numb - количество итераций для проверки на простоту генерируемого числа

(используется тест Леманна). Программа выводит результат - значение простого числа.

3. Вычислите значение с помощью программы n. exe, запускаемой с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

.

4. Определение секретного e и открытого d паролей.

Вычислите значение. (Используйте программу n. exe, запускаемую с помощью меню ФАЙЛ программы, содержащейся в папке VIS1).

Выберите целое число e взаимно простое с функцией Эйлера (см. Приложение 3), т.е. число, для которого выполняется равенство и число d, обратное к e: .

Для выполнения этого пункта задания запускается программа FINDNOD1. EXE, с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры:

x = ;

dn = левая граница диапазона поиска чисел e и d;

dk = - правая граница диапазона поиска чисел e и d. Программа выводит значение x и результат: e (секретный ключ) и d (открытый ключ), а также значение наибольшего общего делителя чисел x и e - величину z (для контроля вычислений).

Величину dn < dk можно задавать произвольно, но если величина (dk - dn) окажется слишком малой, то правильные значения чисел e и d могут быть не найдены.

Контроль правильности выбора e контролируется значением z (z должно быть равно 1). Для контроля правильности выбора d необходимо убедиться в выполнении соотношения .

Для этого вначале получаем произведение с помощью программы n. exe, запускаемой с помощью меню ФАЙЛ программы, содержащейся в папке VIS1, а затем таким же образом с помощью программы OST - значение (оно должно быть равно 1).

Информация z={p,q,e} является информацией потайного хода (секретной информацией). Информация d и n является открытой и используется в защищаемом программном обеспечении. Итак закрытым ключом шифрования сообщения (цифровой подписи) является e, а открытым ключом являются числа d и n. Числа p и q в дальнейших расчетах не используются и надежно затираются.

5. Процедура идентификации пользователя происходит следующим образом.

Сообщение m, которым может быть, например, серийный номер программы (serial number - s/n), сначала разбивается на цифровые блоки размерами меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть, если p и q являются 100-разрядными простыми числами, то n будет содержать 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n). Зашифрованное сообщение c будет состоять из блоков той же самой длины. Формула шифрования выглядит просто:

(Используется алгоритм Приложения 2).

Шифрованное сообщение передается в программу, в которой происходит расшифрование сообщения по формуле

(Используется алгоритм Приложения 2).

Так как

, все по (mod n),

то формула восстанавливает сообщение.

Сравнение в программе исходного сообщения (оно передается программе) и расшифрованного позволяет правильно идентифицировать пользователя программного обеспечения, так как секретный ключ шифрования e знает только истинный пользователь.

Небольшой пример, возможно, поможет пояснить работу алгоритма. Если p=47 и q=71, то n=pq=3337.

Ключ e не должен иметь общих множителей с числом (p-1) (q-1) =46 x 70 =3220.

Выберем (случайным образом) e равным 79.

В этом случае, используя порядок действий п.4, определяем d:

Параметры d и n будем использовать в программе для идентификации, параметры p и q отбросим (уничтожим).

Пусть сообщение (например, s/n) имеет вид

m= 6882326879666683.

Сначала разделим его на маленькие блоки. Для нашего случая подойдут блоки из трех цифр. Сообщение разбивается на шесть блоков :

Первый блок шифруется как . Выполним такие же операции для последующих блоков, и создадим шифротекст сообщения

с = 1570 2756 2091 2276 2423 158, который передадим в программу вместе с исходным сообщением m, ключом d=1019 и параметром n=3337.

Для расшифрования криптограммы с в защищаемой программе нужно выполнить такое же возведение в степень с использованием ключа расшифрования 1019:

Аналогично восстанавливается оставшаяся часть сообщения. Восстановленное сообщение сравнивается с исходным сообщением и при их совпадении программа запускается.

6. Процедура идентификации пользователя при использовании разработанных программ.

В этом случае в качестве сообщения (цифровой подписи) выбирается число m из диапазона задания и определяется ее криптограмма по формуле

Для этого вычисления применяется программа MODN1. EXE,

запускаемая с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры a = m, x= e, а в качестве параметра p вводится значение n. Программа выводит результат - значение криптограммы c=y.

Для моделирования процесса идентификации пользователя можно использовать программу PAROLE15. EXE, запускаемую с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы PAROLE15. EXE вводится открытая информация: открытый ключ d, параметр n, цифровая подпись m и ее криптограмма c. Программа определяет значение и при совпадении y со значением m программа выводит результат - надпись friend (друг), а при несовпадении - надпись enemy (враг).

Данная система аутентификации пользователя является более безопасной по сравнению с предыдущей лабораторной работой, так как в этом случае в программу не нужно передавать секретный ключ e - отсутствует риск его “подсматривания”.

Формирование пароля с помощью однонаправленной функции с потайным ходом (алгоритм проверки цифровой подписи Эль-Гамаля)

1. Выберите диапазон чисел

2. Определите простое число p с помощью этого диапазона.

Последовательность действий по выбору простого числа аналогична предыдущей лабораторной работе:

Для выполнения этого пункта задания используется программа GEN1. EXE, запускаемая с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры:

dn - левая граница диапазона задания; dk - правая граница диапазона задания; numb - количество итераций для проверки на простоту генерируемого числа (используется тест Леманна). Программа выводит результат - значение простого числа.

3. Определите два случайных числа g и x меньших p из диапазона

<p <p

Для определения этих чисел используйте либо программу RAND. EXE, запускаемую с помощью меню ФАЙЛ программы, содержащейся в папке VIS1, либо выберите самостоятельно.

По запросу программы RAND. EXE вводятся параметры:

dn <dk левая граница поиска чисел;

dk =p-1 правая граница диапазона;

Программа выводит результат - значение случайного числа.

4. Вычислите значение .

Для выполнения этого пункта задания применяется программа MODN1. EXE,

запускаемая с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры a = g, x, p. Программа выводит результат - значение y.

Открытым ключом являются параметры y, g, p. Секретным ключом является x.

5. Выберите цифровую подпись M (Число из диапазона < p). Чтобы подписать сообщение M сначала выбирается случайное число k из диапазона < (p-1) взаимно простое с (p-1). Для определения взаимной простоты k и (p-1) используется алгоритм Евклида Приложения 4.

Для выполнения этого пункта задания запускается программа FINDNOD1. EXE, с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры:

x = (p-1) - число, для которого определяется взаимно простое число;

dn <dk - левая граница поиска числа k взаимно простого к (p-1);

dk =p-2 - правая граница диапазона поиска числа k взаимно простого к (p-1);

Программа выводит значение x и результат: e=k и d= (число обратное k по модулю (p-1)), а также значение наибольшего общего делителя чисел x и e=k - величину z (для контроля вычислений).

Величину dn < dk можно задавать произвольно, но если величина (dk - dn) окажется слишком малой, то правильные значения чисел e и d могут быть не найдены.

Контроль правильности выбора k контролируется значением z (z должно быть равно 1). Для контроля правильности выбора необходимо убедиться в выполнении соотношения .

Для этого вначале получаем произведение k с помощью программы n. exe, запускаемой с помощью меню ФАЙЛ программы, содержащейся в папке VIS1, а затем таким же образом с помощью программы OST - значение (оно должно быть равно 1).

6. Затем вычисляется параметр a:

.

Для выполнения этого пункта задания применяется программа MODN1. EXE,

запускаемая с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы вводятся параметры a = g, x=k, p. Программа выводит результат - значение y=a.

Далее относительно параметра b решается уравнение:

,

то есть b определяется из соотношения

Для вычисления можно использовать один из двух методов Приложения 3:

а) используется вариант расширенного алгоритма Евклида Приложения 5, примененный в программе FINDNOD1. EXE;

б) используется обобщение Эйлера малой теоремы Ферма:

В последнем случае для определения и для вычисления b применяется алгоритм Приложения 2.

С учетом последнего соотношения выражение для параметра b можно переписать в виде

Это соотношение используется для определения параметра b с помощью программы B. EXE, содержащейся в папке B, и запускаемой с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

Программа запрашивает параметры M,x, a, k, p. Программа выводит на экран значение параметра b.

Случайное значение k и ключ x должны держаться в секрете. Подписью являются два параметра a и b.

7. Процедура идентификации пользователя при использовании разработанных программ.

В защищаемую программу передаются параметры y, g, a, b, p и сообщение M.

Для проверки подлинности пользователя в программе проверяется равенство:

При его выполнении пользователь допускается к использованию программного обеспечения.

Для моделирования процесса идентификации пользователя можно использовать программу PAROLE16. EXE, запускаемую с помощью меню ФАЙЛ программы, содержащейся в папке VIS1.

По запросу программы PAROLE16. EXE вводятся параметры y, g, a, b, p,m.

Программа определяет значение и сравнивает его с величиной . При совпадении этих величин программа выводит результат - надпись friend (друг), а при несовпадении - надпись enemy (враг).

Замечание 1. Сообщение M может быть разбито на блоки меньшей длины (см. предыдущую лабораторную работу).

В этом случае параметр b и контролирующее равенство вычисляются для каждого блока.

Замечание 2. Случайный параметр k определяется при каждой аутентификации пользователя.

Поясняющий пример. Выберем p= 11 и g=2, а закрытый ключ x=8. Вычислим

Чтобы подписать сообщение M=5, сначала выберем случайное число k=9. Убеждаемся, что НОД (9,10) =1. Вычислим

Определяем , например, с помощью обобщения Эйлера малой теоремы Ферма:

Определяем параметр b:

(Напоминаем, что в модулярной арифметике при получении отрицательного числа необходимо добавлять столько раз значение mod пока не получится первый раз положительный результат - он и будет окончательным значением)

Для проверки подписи убедимся, что:

Данный метод обладает по сравнению с методом RSA большей криптостойкостью

Шифрование с одноразовым блокнотом

При шифровании с одноразовым блокнотом (при его правильном применении) получаются криптограммы, не поддающиеся криптоанализу и принципиально не раскрываемые.

Порядок действий.

1. Определите массив A символов, которые будут использованы в сообщении, размером T символов. Пример такой таблицы размером T = 72 символа приведен в следующей таблице.

НОМЕР	1	2	3	4	5	6	7	8	9
СИМВОЛ	A	B	C	D	E	F	G	H	I
КОД (ДЕС.)	65	66	67	68	69	70	71	72	73
НОМЕР	10	11	12	13	14	15	16	17	18
СИМВОЛ	J	K	L	M	N	O	P	Q	R
КОД (ДЕС.)	74	75	76	77	78	79	80	81	82
НОМЕР	19	20	21	22	23	24	25	26	27
СИМВОЛ	S	T	U	V	W	X	Y	Z	a
КОД (ДЕС.)	83	84	85	86	87	88	89	90	97
НОМЕР	28	29	30	31	32	33	34	35	36
СИМВОЛ	B	c	d	e	f	G	h	i	j
КОД (ДЕС.)	98	99	100	101	102	103	104	105	106
НОМЕР	37	38	39	40	41	42	43	44	45
СИМВОЛ	K	l	m	n	o	P	q	r	s
КОД (ДЕС.)	107	108	109	110	111	112	113	114	115
НОМЕР	46	47	48	49	50	51	52	53	54
СИМВОЛ	T	U	v	w	x	Y	z	Пер. ст	В. кар.
КОД (ДЕС.)	116	117	118	119	120	121	122	10	13
НОМЕР	55	56	57	58	59	60	61	62	63
СИМВОЛ	Проб.	(	)	,	-	.	:	;	0
КОД (ДЕС.)	32	40	41	44	45	46	58	59	48
НОМЕР	64	65	66	67	68	69	70	71	72
СИМВОЛ	1	2	3	4	5	6	7	8	9
КОД (ДЕС.)	49	50	51	52	53	54	55	56	57

2. Cоставьте сообщение M в виде последовательности номеров символов массива A.

Пример. Пусть требуется зашифровать сообщение:

Hello, students. (Можно использовать любые, в том числе и русские символы, так как их коды здесь не используются).

Составляем из данной таблицы таблицу из 12 используемых символов (T=12).

НОМЕР	1	2	3	4	5	6	7	8	9
СИМВОЛ	H	e	l	o	,	Проб.	s	t	u
НОМЕР	10	11	12
СИМВОЛ	d	n	.

Исходное сообщение M в виде последовательности из 16 номеров запишется так (N=16):

K = 1 2 3 3 4 5 6 7 8 9 10 2 11 8 7 12

3. Зашифруйте сообщение M:

Для каждого текущего номера K случайно (по равномерному в интервале (1, T) закону распределения) выберите номер символа ключевой последовательности и определите номера символов С криптограммы следующим образом:

Пример ключевой последовательности :

= 9 8 5 10 8 6 9 11 7 7 4 1 8 1 4 7

В этом случае криптограмма C имеет вид

10 10 8 1 12 11 3 6 3 4 2 3 7 9 11 7

Сохраните символы криптограммы C и ключа .

4. Для расшифрования C достаточно сделать операцию (используйте алгоритм Приложения 2):

(Если M получается равным нулю, то следует к этому результату добавить T)

Нетрудно убедиться, что в нашем примере эта операция восстанавливает исходную последовательность номеров сообщения.

5. По M, используя массив A, восстановите сообщение в виде последовательности символов.

Данный алгоритм реализован в программе на VISUAL BASIC, содержащейся в папке VIS1 (подменю ЛАБОРАТОРНАЯ РАБОТА 4 меню РЕШЕНИЕ).

Замечание 1. Ключевую последовательность не следует использовать повторно, так как при повторном использовании последовательность символов ключа и исходные сообщения могут быть восстановлены с помощью криптоанализа.

Замечание 2. Криптостойкость шифрования с одноразовым блокнотом определяется качеством датчика случайных чисел: если распределение вырабатываемых датчиком случайных чисел достаточно близко к равномерному и выполняется условие замечания 1, криптограммы этого метода шифрования не поддаются криптоанализу при достаточно большой длительности сообщения и большом объеме алфавита символов T. (Абсолютный метод шифрования).

Приложение 1. Генерация простых чисел

Тест Леманна

Последовательность действий при проверке простоты числа р:

1. Выберите случайное число а, меньшее р.

Вычислите

Если или , то число р определенно не простое.

Если или , вероятность того, что число р не простое превышает 50 %.

И опять же, вероятность того, что случайное число окажется свидетелем составной природы числа р, составляет не менее 50 %. Повторите тест раз. Если результат вычислений равен I или - 1, но не всегда равен 1, то р - простое число с вероятность ошибки .

Тест Рабина-Миллера

Широко используется простой алгоритм, разработанный Майклом Рабином.

Выберите для тестирования произвольное число р. Вычислите Ь - число делений р - I на 2 (т.е.2^Ь - это наибольшая степень числа 2, на которую делится р - I). Затем вычислите т, такое, что .

Выберите случайное число а, меньшее р

Установите j = 0 и z = a^m mod p.

Если z = 1 или если z = р-1, то р проходит тест и может быть простым числом.

Если j > 0 и z = 1, то р не относится к простым числам.

Установите j = j + 1. Если j<b и , установите и вернитесь:

на этап 4. Если z = p-1, то р проходит тестирование и может быть простым числом

Если j = Ь и , то р не относится к простым числам.

Вероятность прохождения этого теста составным числом убывает быстрее, чем в предыдущих тестах. Гарантируется, что составное число ошибочно пройдет t тестов с вероятностью не более, где t - число итераций.

Приложение 2. Определение

Этот прием называют аддитивной цепочкой (addition chain), или методом двоичных квадратов и умножений. В нем используется простая и очевидная аддитивная цепочка, основанная на двоичном представлении числа. На языке С это выглядит следующим образом:

unsigned long qe2 (unsigned long x, unsigned long y, unsigned long n) {

unsigned long s, t, u;

int i;

s=l; t=x; u=y;

while (u) {

if (u&l) s= (s*t) %n;

u"=l;

t= (t*t) %n;

}

return (s);

}

Вот еще один, рекурсивный, алгоритм:

unsigned long fast_exp (unsigned long x, unsigned long y, unsigned long N) {

unsigned long tmp;

if (y==l) return (x % N);

if ( (y&1) ==0) {

tmp = fast_exp{x,y/2,N);

return ( (tmp*tmp) %N);

}

else {

tmp = fast_exp (x, (y-l) /2,N);

tmp = { tmp*tmp) %N;

tmp = (tmp*x) %N;

return (tmp);

}

}

пароль безопасный алгоритм генерация цифровая подпись

Приложение 3. Сведения из теории чисел

Простые числа

Простым называют целое число, больше единицы, единственными множителями которого является 1 и оно само. Простое число не делится ни на одно другое число. Скажем, число 2 - простое число. К простым числам относятся также 73, 2521, 2365347734339 и . Количество простых чисел бесконечно велико. В криптсмрафии, особенно криптографии с открытым ключом, нередко используют большие простые числа (512 бит и даже больше).

Наибольший общий делитель

Два числа называют взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, если наибольший общий делитель чисел а и п равен 1, эти числа называют взаимно простыми. Это записывается следующим образом:

НОД (а, п) = 1

Например, числа 15 и 28 взаимно просты. Числа 15 и 27 не являются взаимно простыми, а числа 13 и 500 - являются. Простое число взаимно просто со всеми другими числами, кроме чисел, кратных данному простому числу.

Один из способов вычисления наибольшего общего делителя двух чисел использование алгоритма Евклида. Евклид описал этот алгоритм в своей книге "Элементы", датированной 300 годом до н.э. Однако алгоритм создан не Евклидом. Историки полагают, что алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, дошедший до наших дней, и он все еще в ходу. Реализация алгоритма Евклида содержится в Приложении 4.

Обратные значения по модулю.

Помните, что такое обратные значения? Обратное значение числа 4 равно 1/4, поскольку 4*1/4 =1. В мире модулей это понятие несколько сложнее:

Это уравнение эквивалентно поиску таких значений х и k, что:

где x и k - целые числа.

Общая задача состоит в определении такого значения х, что:

1 = (а * x) mod n

Последнее равенство можно также записать в виде:

Задача вычисления обратных значений по модулю немного труднее обычной. Иногда у нее есть решение, иногда - нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14,В общем случае, уравнение имеет единственное решение, если и взаимно просты. Если а и п не являются взаимно простыми числами, то решений не имеет. Если п - простое число, то любое число от 1 до п - 1 взаимно просто си имеет только одно обратное значение по модулю п.

Для определения обратного значения по модулю n можно использовать два метода. Во-первых, обратное значение по модулю п можно вычислить с помощью расширенного алгоритма Евклида, содержащегося в Приложении 5.

Для определения второго способа потребуется еще несколько определений из теории чисел.

В модулярной арифметике если , то при некотором целом k. Если a неотрицательно, а b находится между 0 и n, можно рассматривать b как остаток от деления a на n. Иногда b называют вычетом по модулю n, а иногда называют сравнимым с b по модулю n (знак тождества обозначает сравнимость). Множество целых чисел от 0 до n-1 образует так называемую полную систему вычетов по модулю n. Это означает, что для любого целого числа a, его вычет по модулю n равен некоторому числу от 0 до n-1. Операция обозначает вычет от a, равный некоторому целому числу от 0 до n-1. Эта операция называется приведением по модулю.

Приведенной системой вычетов по модулю п называют подмножество полной системы вычетов, члены которого взаимно просты с п. Например, приведенную систему вычетов по модулю 12 составляют числа {1, 5, 7, 11}. Если п - простое число, в приведенную систему вычетов по модулю п входит всё множество чисел от 1 до и - 1. Для любого п, не равного 1, число 0 никогда не входит в приведенную систему вычетов.

Функция Эйлера (Euler totient function), которую иногда называют функцией "фи" Эйлера и записывают как, указывает число элементов в приведенной системе вычетов по модулю п. Иными словами, - это количество положительных целых чисел, меньших п и взаимно простых с п (для любого п, большего 1). (Леонард Эйлер (Leonhard Euler), швейцарский математик, 1707 - 1783).

Если п - простое число, то = п-\. Если n=pq, где р и q - простые числа, то = (p-1) (q-1). Эти числа используют в некоторых алгоритмах с открытым ключом.

В соответствии с обобщением Эйлера малой теоремы Ферма, если НОД = 1, то:

Приложение 4. Алгоритм Евклида для определения наибольшего общего делителя чисел на языке С

Алгоритм Евклида для двух чисел

/* Возвращает НОД х и у */

int god (int x, int у) {

int g;

if (x < 0)

x = - x;

if (y < 0)

у = - у;

if (x + у == 0)

ERROR;

g = y;

while (x > 0) {

g = x;

x = у % x;

у = g;

}return g;

}

Приложение 5. Расширенный алгоритм Евклида для определения обратного значения к v по модулю u на языке С (v < u). Параметрами командной строки функции main являются

3 god значение (v) значение (u).

#define isEven (x) ( (x & 0x01) == 0)

#define isOdd (x) (x & 0x01)

#define swap (x,y) (x^= у, у^= x, x^= y)

void ExtBinEuclid{int *u, int *v, int *ul, int *u2, int *u3) {

// предупреждение: u и v будут переставлены, если u<v

int k, tl, t2, t3;

if (*u < *v) swap (*u,*v);

for (k = 0; isEven (*u) && iaEven{*v); ++k) {

*u"= 1; *v"=1;

}

*ul = 1; *u2 = 0; *u3 = *u; tl = *v; t2 = *u - 1; t3 = *v;

do {

do {

if (isEven (*u3)) {

if (isOdd (*ul) | | isOdd (*u2)) {

*u1+= *v; *u2 += *u;

}

*ul"= 1; *u2"= 1; *u3"= 1;

}

if (isEven (t3) | | *u3 < t3) {

swap (*ul,tl); swap (*u2, t2); swap (*u3, t3);

}

} while (isEvan (*u3));

while (*ul < tl | | *u2 < t2) {

*u1+= *v; *u2 += *u;

}

*ul - = tl; *u2 - = t2; *u - = t3;

} while (t3 > 0);

while (*ul >= *v && *u2 >= *u) {

*ul-= *v; *u2-= *u;

}

*ul"= k; *u2"= k; *u3"= k;

}

main (int atgc, char **argv) {

int a, b, gcd;

if (argc < 3) {

cerr " "Использование: xeuclid u v" " endl;

return - 1;

}

int u = atoi (argv [1]);

int v = atoi (argv [2]);

if (u <= 0 || v <= 0) {

Cerr " "Аргументы должны быть положительными!" " end1;

return - 2;

}

// предупреждение: u и v будут переставлены, если u < v

ExtBinEuclid (&u, &v, &a, &b, &gcd);

cout " a "" * " " u " " + (-"

" b " ") * " " v " " = " " gcd " endl;

if (gcd == 1)

cout " "Обратное значение " " v " " mod " " u " " равно

”" u - b " endl;

return 0;

}

Размещено на Allbest.ru

...