Пусть p=83 - простое число. Найти первообразный корень по модулю по p. Вычислить открытый и секретный ключи по системе Эль-Гамаля за абонента B. Зашифровать абонента A и переслать абоненту B сообщение m=33. Расшифровать за абонента B это сообщение.
p = 83 – простое число
Выбираем CB<(83-1)
CB=11-случайное число (секретный ключ)
dB=aC mod p, a = 2 – первообразный корень
dB=211 mod 83 = 56 (открытый ключ)
Решение
Абонент A зашифровал и переслал сообщение m=33 абоненту B.
Выбираем k<(p-1)k= 5 – случайное число
r = ak mod p r = 25 mod 83 = 32 mod 83 = 32
e = m*dB5 mod pe = 33*565 mod 83 =73
Абонент B получает (32,73), вычисляет
m’ = e*rp-1-C mod p
m’ = 73*3283-1-11 mod 83 = 73*3271 mod 83= 73*5 mod 83 =365 mod 83 = 33
( 3271=3264*324*322*32
32 =32(mod 83)3216= 412=1681= 21 (mod 83)
322=1024 = 28 (mod 83)3232= 212=441= 26 (mod 83)
324= 282=784= 37 (mod 83)3264= 262=676= 12 (mod 83)
328= 372=1369= 41 (mod 83)3271=12*37*28*32= 397824 (mod 83) = 5)
Пусть p=83, q=11 - простые числа. Вычислить открытый и секретный ключи по системе RSA за абонента B. Зашифровать абонента A и переслать абоненту B сообщение m=333
. Расшифровать за абонента B это сообщение.
p=83, q=11- простые числа, m=333
NB=p*q=83*11=913
ΦB=(p-1)*(q-1) = 82*10 = 820
dB = 23 –случайное число (открытый ключ)
CB = 1 (mod ΦB)
CB = 1 (mod 820) = 107 (секретный ключ)
dB и NB - открытые ключи
CB - секретный ключ
Абонент B: NB=913dB=23CB=107
Абонент A:
m = 333
e = mdB (mod NB)
e = 33323mod 913=665
Абонент B расшифровал:
m’=eCB (mod NB)
m’=665107 (mod 913) = 333
Проверить тестом Миллера-Рабина с вероятностью 15/16 на простоту число 167.
1516≤1-14k=2, n = 167
n-1 = 166 = 2*83, r = 83
a83= 283≡1≡1(mod 167)
[283 = 264*216*22*2 = 49*72*4*2 = 28224≡1(mod 167)
22= 4 = 4 (mod 167)
216= 65536 = 72 (mod 167)
232= 722 = 5184= 7 (mod 167)
264= 72 = 49= 49 (mod 167)]
a2 = 3 – случайное число
a283 = 383 = 1≡1(mod 167)
167 –простое число
Проверить на простоту число 173 по теореме Поклингтона.
n = 173,
n-1 = 172 = 22*43
Q = 22= 4
R = 43
НОД (R, Q) = НОД (43, 4) = 1
a172≡1 (mod 173)
НОД (a172/2-1; 173) = 1
Найти простой делитель q для числа n-1 (172), q < n-1
q < 172
q < 172
q=2
a172≡1 (mod 173)
НОД (a172/2-1; 173) = НОД (a86-1; 173) = 1
НОД (a172/2-1; 173) = НОД (286-1; 173) = 1
173 – простое число
Проверить методом пробных делений на простоту число 4507.
4507<68
2,3,5,7,11,13,17 и другие простые числа <68
4507 не делится на простое число, которое меньше <68
Поэтому 4507 – простое число.
Разложить на простые сомножители методом пробных делений число 32367.
32367 <180
2, 3, 5, 11 и другие простые числа <180
32367: 3 =10789
10789 – простое число и дальше не разлагается
Поэтому 32367=3*10789
Вычислить при помощи бинарного алгоритма остаток 45500 mod 61
45500= 45256*45128*4564*4532*4516*454 = 16*57*22*12*22=5296896 = 22 (mod 61)
452 = 2025 = 12(mod 61)
454 =122 = 144 = 22(mod 61)
458 =222 = 484 = 57(mod 61)
4516 =572 = 3249 = 16(mod 61)
4532 =162 = 256 = 12(mod 61)
4564 =122 = 144 = 22(mod 61)
45128 =222 = 484 = 57(mod 61)
45256 =572 = 3249 = 16(mod 61)
Ответ: 45500 mod 61 = 22
Задать вопрос
на новый заказ в Автор24.
