Решение заданий

Решение заданий по теории чисел
Задание 1.1
Выписать все простые числа до 45, затем найти все простые множители числа N.
Исходные данные
N=90.
Задание 1.2
Проверить являются ли числа A и B взаимно простыми.
Исходные данные
A= 90; B= 131.
Задание 1.3
Найти значение числа A по модулюN(AMODN).
Исходные данные
A= 200; N= 7.
Задание 1.4
Найти обратное значение для числа A по модулю N(т.е. найти A^(-1)).
Исходные данные
A= 90; N= 7.
Задание 1.5
Для простого числа P найти хотя бы одно значение G(G меньше P), являющееся образующей по модулю P. Приведите доказательство того, что G является образующей дляP.
Исходные данные
P=59.
Задание 1.6
Возьмите случайное число P длиной 8 бит, старший и младший бит заполните единицами, остальные биты заполните произвольно. Затем число перевести в десятичный вид. ...

Решение заданий по теории чисел
Задание 1.1
Выписать все простые числа до 45, затем найти все простые множители числа N.
Исходные данные
N=90.
Задание 1.2
Проверить являются ли числа A и B взаимно простыми.
Исходные данные
A= 90; B= 131.
Задание 1.3
Найти значение числа A по модулюN(AMODN).
Исходные данные
A= 200; N= 7.
Задание 1.4
Найти обратное значение для числа A по модулю N(т.е. найти A^(-1)).
Исходные данные
A= 90; N= 7.
Задание 1.5
Для простого числа P найти хотя бы одно значение G(G меньше P), являющееся образующей по модулю P. Приведите доказательство того, что G является образующей дляP.
Исходные данные
P=59.
Задание 1.6
Возьмите случайное число P длиной 8 бит, старший и младший бит заполните единицами, остальные биты заполните произвольно. Затем число перевести в десятичный вид.Используя известные вам критерии проверки числа на простоту, оцените, будет ли Ваше число простым. Приведите результаты проверок. Если проверка один раз прошла успешно, то выполните ее еще несколько раз с другими параметрами. Оцените вероятность того, что число все равно не простое. Если первая проверка, что число P не является простым, тогда найдите ближайшее к нему простое число.

Исходные данные
P = 〖10000011〗_2=〖131〗_10.
Решение заданий по алгоритмам с открытыми ключами
Задание 2.1
Опишите процесс шифрования исходного текста M, используя алгоритм RSA, для следующих значений параметров P,q и d. Определите значение недостающего параметра e. Каким будет зашифрованный текст C? Проверьте, что при расшифровке исходный текст M будет восстановлен. Приведите расчет проверки.
Исходные данные
P= 5; q= 13;d= 5; M= 9.
Задание 2.2
В криптосистеме, использующей RSA, вы перехватили зашифрованный текст C и открытый ключ (e,N). Определите, каким был исходный текст и личный ключ.
Исходные данные
C=3; e= 13;N=119.
Задание 2.3
Опишите процесс создания и проверки электронной подписи по схеме Эль-Гамаля для следующих значений параметров:P, g, k исходного текстаM. Определите значение открытого ключа и значения электронной подписи(a,b). Приведите результаты проверки электронной подписи.
Исходные данные
P= 17;g= 3; x= 11; M=7; k= 3 (т.к. НОД(3,16)=1).
Задание 2.4
Опишите процесс создания и проверки электронной подписи по алгоритму DSA для следующих значений параметров: P, q, gи известномхэше исходного текстаH(M). Ваш секретный ключx тоже задан. Определите значения открытого ключа и значения электронной подписи(r,s). Приведите результаты проверки электронной подписи, а также значения промежуточных результатов:k^(-1), s^(-1), w,u_1,u_2,v.
Исходные данные
P= 23;q= 11;g=4; x= 10; H(M)= 11; k= 3.
Задание 2.5
Для найденной в Задании 1.5 образующей Gдля простого числа P рассчитать общий ключ по схеме Диффи-Хеллмана, взявслучайные числа X_a и X_b в диапазоне от 3 до 10. Написать также значения обоих открытых ключей.
Исходные данные
P= 59; G= 2; X_a= 6;X_b= 7.
Решение заданий по симметричной системе шифрования
Решение заданий по генераторам псевдослучайных чисел
Задание 3.1
Для одного из полиномов построить схему побитового шифрования потока данных на основе регистра сдвига с обратной связью и определить период генерации псевдослучайных чисел (ПСЧ).
Исходные данные
P(x)=1+x+x^2+x^3+x^5.
Задание 3.2
Для линейного конгруэнтного генератора проверить достигается ли максимальный период при использовании в качестве коэффициентов следующих значений:
A=№ в журнале;
C= A+1;
Формула линейного конгруэнтного генератора:
T_(i+1)=(A∙T_i+C)MOD 16;
Привести значения A и C, при которых генератор имеет максимальный период, написать чему он равен. Ответить на вопрос: - Для чего используется линейный конгруэнтный генератор?
Исходные данные
A=9; C= 10; m= 16.
Решение задания по блочным шифрам
Задание 3.3
Опишите процесс шифрования и дешифрования по алгоритму Файстеля. В виде данных возьмите число: 128 + № в журнале. Представьте полученное число в двоичном виде, разбейте это число на два блока по четыре бита. Возьмите подключK_1=1010 и подключK_2=1001. Выполните два раунда шифрования. В виде функции – использовать сложение по модулю 2 с подключом.
Исходные данные
N=128+9=〖137〗_10=〖10001001〗_2, K_1=1010, K_2=1001.
Решение заданиям по хэш-функциям
Задание 4(Вариант 2)
Даны три блока открытого текста M_1, M_2, M_3. Как будет выглядеть в общем виде формула хэш-функции, если при ее построении использовался блочный алгоритм, выполняющий преобразование над блоком E_k (M_i )в режиме CFB (CipherFeedBack - обратная связь по шифротексту). Предположим, что использовался нулевой вектор инициализации (IV).
Исходные данные
Блоки открытого текста: M_1, M_2, M_3; IV= 0.

Решение заданий по теории чисел
Задание 1.1
Выписать все простые числа до 45, затем найти все простые множители числа N.
Исходные данные
N=90.
Задание 1.2
Проверить являются ли числа A и B взаимно простыми.
Исходные данные
A= 90; B= 131.
Задание 1.3
Найти значение числа A по модулюN(AMODN).
Исходные данные
A= 200; N= 7.
Задание 1.4
Найти обратное значение для числа A по модулю N(т.е. найти A^(-1)).
Исходные данные
A= 90; N= 7.
Задание 1.5
Для простого числа P найти хотя бы одно значение G(G меньше P), являющееся образующей по модулю P. Приведите доказательство того, что G является образующей дляP.
Исходные данные
P=59.
Задание 1.6
Возьмите случайное число P длиной 8 бит, старший и младший бит заполните единицами, остальные биты заполните произвольно. Затем число перевести в десятичный вид. Используя известные вам критерии проверки числа на простоту, оцените, будет ли Ваше число простым. Приведите результаты проверок. Если проверка один раз прошла успешно, то выполните ее еще несколько раз с другими параметрами. Оцените вероятность того, что число все равно не простое. Если первая проверка, что число P не является простым, тогда найдите ближайшее к нему простое число.

Исходные данные
P = 〖10000011〗_2=〖131〗_10.
Решение заданий по алгоритмам с открытыми ключами
Задание 2.1
Опишите процесс шифрования исходного текста M, используя алгоритм RSA, для следующих значений параметров P,q и d. Определите значение недостающего параметра e. Каким будет зашифрованный текст C? Проверьте, что при расшифровке исходный текст M будет восстановлен. Приведите расчет проверки.
Исходные данные
P= 5; q= 13;d= 5; M= 9.
Задание 2.2
В криптосистеме, использующей RSA, вы перехватили зашифрованный текст C и открытый ключ (e,N). Определите, каким был исходный текст и личный ключ.
Исходные данные
C=3; e= 13;N=119.
Задание 2.3
Опишите процесс создания и проверки электронной подписи по схеме Эль-Гамаля для следующих значений параметров:P, g, k исходного текстаM. Определите значение открытого ключа и значения электронной подписи(a,b). Приведите результаты проверки электронной подписи.
Исходные данные
P= 17;g= 3; x= 11; M=7; k= 3 (т.к. НОД(3,16)=1).
Задание 2.4
Опишите процесс создания и проверки электронной подписи по алгоритму DSA для следующих значений параметров: P, q, gи известномхэше исходного текстаH(M). Ваш секретный ключx тоже задан. Определите значения открытого ключа и значения электронной подписи(r,s). Приведите результаты проверки электронной подписи, а также значения промежуточных результатов:k^(-1), s^(-1), w,u_1,u_2,v.
Исходные данные
P= 23;q= 11;g=4; x= 10; H(M)= 11; k= 3.
Задание 2.5
Для найденной в Задании 1.5 образующей Gдля простого числа P рассчитать общий ключ по схеме Диффи-Хеллмана, взявслучайные числа X_a и X_b в диапазоне от 3 до 10. Написать также значения обоих открытых ключей.
Исходные данные
P= 59; G= 2; X_a= 6;X_b= 7.
Решение заданий по симметричной системе шифрования
Решение заданий по генераторам псевдослучайных чисел
Задание 3.1
Для одного из полиномов построить схему побитового шифрования потока данных на основе регистра сдвига с обратной связью и определить период генерации псевдослучайных чисел (ПСЧ).
Исходные данные
P(x)=1+x+x^2+x^3+x^5.
Задание 3.2
Для линейного конгруэнтного генератора проверить достигается ли максимальный период при использовании в качестве коэффициентов следующих значений:
A=№ в журнале;
C= A+1;
Формула линейного конгруэнтного генератора:
T_(i+1)=(A∙T_i+C)MOD 16;
Привести значения A и C, при которых генератор имеет максимальный период, написать чему он равен. Ответить на вопрос: - Для чего используется линейный конгруэнтный генератор?
Исходные данные
A=9; C= 10; m= 16.
Решение задания по блочным шифрам
Задание 3.3
Опишите процесс шифрования и дешифрования по алгоритму Файстеля. В виде данных возьмите число: 128 + № в журнале. Представьте полученное число в двоичном виде, разбейте это число на два блока по четыре бита. Возьмите подключK_1=1010 и подключK_2=1001. Выполните два раунда шифрования. В виде функции – использовать сложение по модулю 2 с подключом.
Исходные данные
N=128+9=〖137〗_10=〖10001001〗_2, K_1=1010, K_2=1001.
Решение заданиям по хэш-функциям
Задание 4(Вариант 2)
Даны три блока открытого текста M_1, M_2, M_3. Как будет выглядеть в общем виде формула хэш-функции, если при ее построении использовался блочный алгоритм, выполняющий преобразование над блоком E_k (M_i )в режиме CFB (CipherFeedBack - обратная связь по шифротексту). Предположим, что использовался нулевой вектор инициализации (IV).
Исходные данные
Блоки открытого текста: M_1, M_2, M_3; IV= 0.

Определим параметр m из равенства P-1= 2b∙m. Тогда выражение для определения m имеет вид: m=P-12b. Подставив в выражение значения параметров P и b, получим, что m=65.Вычислим значение выражения amMODPпри a=2:265MOD131= 232MOD131∙233MOD131MOD131==117∙103MOD 131=12051 MOD 131=130.Т.к. значение выражения равно P-1, то число P=131 – простое с вероятностью ошибки Pош, равной 0,25.Рассчитаем значение выражения amMODP при a=3иa=4.a=3: 365MOD 131= 332MOD 131∙333MOD 131MOD 131==100∙38MOD 131=3800 MOD 131=1.a=4:465MOD131= 265MOD131∙265MOD131MOD131==130∙130MOD 131=16900 MOD 131=1.Т.к. значение выражения amMODP при P=131, m=65и a=2,3,4 равно либо 1, либо P-1, то число P=131 – простое с вероятностью ошибки Pош, равной (0,25)n=(0,25)3≈0,016 (n – число повторений тестапри различных значениях параметра a).Вывод: Число P=131 – простое с вероятность ошибки, равной 0,125 по тесту Леманна и 0,017 по тесту Рабина-Миллера.Решение заданий по алгоритмам с открытыми ключамиЗадание 2.1Опишите процесс шифрования исходного текста M, используя алгоритм RSA, для следующих значений параметров P,q и d. Определите значение недостающего параметра e. Каким будет зашифрованный текст C? Проверьте, что при расшифровке исходный текст M будет восстановлен. Приведите расчет проверки.Исходные данныеP= 5; q= 13;d= 5; M= 9.РешениеЗначение недостающего параметра e определим из следующей системы уравнений:НОДe,P-1∙q-1=1; e∙d MOD P-1∙q-1=1. (5)В результате решения системы (5), получим, что параметр e принимает значение 29.Пара параметров (e,N) является открытым ключом, а пара параметров (d,N) – закрытым ключом. Открытый ключ используется для шифрования исходного текста M, а закрытый ключ – для расшифровки зашифрованного текста C.Зашифруем исходный тест M= 9 открытым ключом (29,65):C=MeMOD N=929MOD 65=329MOD 65∙329MOD65MOD 65==48∙48MOD 65=29.Таким образом, зашифрован текст C будет 29.ПроверкаИспользуя закрытый ключ (5,65) расшифруем зашифрованный текст C:M'=CdMOD N=295MOD 65=9=M.Вывод: При расшифровке зашифрованного текста C=29 закрытым ключом (5,65) был восстановлен исходный текст M.Задание 2.2В криптосистеме, использующей RSA, вы перехватили зашифрованный текст C и открытый ключ (e,N). Определите, каким был исходный текст и личный ключ.Исходные данныеC=3; e= 13;N=119.РешениеОпределим простые множители числа N:Получаем, что простыми множителями числа N= 119 являются числа 7 и 17.Значение параметра d определим из равенстваe∙d MOD P-1∙q-1 = 1, где P-1∙q-1=6∙16=96.В результате получим, что параметр d принимает значение 37, а закрытым ключом будет пара (37,119).Используя закрытый ключ, расшифруем текст C:M'=337MOD 119=318MOD 119∙319MOD 119MOD 119==43∙10MOD 119=73.ПроверкаИспользуя открытый ключ (13,119) зашифруем текст M':C'=7313MOD 119=736MOD 119∙737MOD 119MOD 119==36∙10MOD 119=3=C.Вывод: При расшифровке зашифрованного текста C=3 закрытым ключом (37,119) был восстановлен исходный текст M.Задание 2.3Опишите процесс создания и проверки электронной подписи по схеме Эль-Гамаля для следующих значений параметров:P, g, k исходного текстаM. Определите значение открытого ключа и значения электронной подписи(a,b). Приведите результаты проверки электронной подписи.Исходные данныеP= 17;g= 3; x= 11; M=7; k= 3 (т.к. НОД(3,16)=1). РешениеОткрытый ключ (g,y,P)используется для проверки чужой электронной подписи. Недостающий параметр ключа определим из выражения:y=gxMOD P. (6)Подставив в выражение (6) значения параметров g, xи P, получим y=311MOD 17=7.Таким образом, открытым ключом является (3,7,17).Значения параметров электронной подписи a и b определим из следующей системы уравнений:a=gkMOD P; M=x∙a+k∙bMODP-1 . (7)В результате решения системы (7), получим, что a= 10, b=3. Тогда электронной подписью будет пара (10,3).ПроверкаДля проверки подлинности подписи, произведем вычисления левой и правой сторон равенства ya∙abMOD P=gMMOD P и сравним результат.ya∙abMOD P= 710∙103MOD 17==710MOD 17∙103MOD17MOD 17= 2∙14MOD 17=11.gMMOD P=37MOD 17=2187 MOD 17=11.Вывод: Т.к. значение левой и правой сторон выражения совпадают, то подпись является подлинной.Задание 2.4Опишите процесс создания и проверки электронной подписи по алгоритму DSA для следующих значений параметров: P, q, gи известномхэше исходного текстаH(M). Ваш секретный ключx тоже задан. Определите значения открытого ключа и значения электронной подписи(r,s). Приведите результаты проверки электронной подписи, а также значения промежуточных результатов:k-1, s-1, w,u1,u2,v.Исходные данныеP= 23;q= 11;g=4; x= 10; H(M)= 11; k= 3.РешениеОпределим обратное значение k-1 параметра kпо модулюq:k-1= kq-2MODq= 39MOD11=16983MOD11=4.Значения параметров электронной подписи r и