LINEBURG


<< Пред. стр.

страница 2
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

n?0 ? Pn = qnPn-1 + Pn-2,
n?0 ? Qn = qnQn-1 + Qn-2.
Их вычисление удобно оформлять в виде таблицы:
n -2 -1 0 1 2 … k-1 k
… qk-1 qk
qn q0 q1 q2
Pn 0 1 P0 P1 P2 … Pk-1 Pk
Qn 1 0 Q0 Q1 Q2 … Qk-1 Qk
Но известно, что PkQk-1-Pk-1Qk=(-1)k-1 и a/m = Pk/Qk. Следовательно
(-1)k-1PkQk-1-Pk-1(-1)k-1Qk=1.
А так как НОД(a,m)=1, то Pk = a, Qk = m. Поэтому
(-1)k-1Qk-1a – m(-1)k-1Pk-1=1.
Другими словами, пара (x,y), где x=(-1)k-1Qk-1; y=(-1)k-1Pk-1,
являются целочисленным решением уравнения (2.1).

2.2. РЕШЕНИЕ СРАВНЕНИЯ ПЕРВОЙ СТЕПЕНИ

Чтобы найти решение сравнения ax?1(mod m), где НОД(a,m)=1,
обычно пользуются алгоритмом Евклида, и тогда x?(-1)k-1Qk-1(mod m),,
где Qk-1 – знаменатель предпоследней подходящей дроби разложения a/m
в цепную дробь, или теоремой Ферма-Эйлера, которая утверждает, что
если НОД(a,m)=1, то
12


a?(m)?1(mod m),
где ?(m) – функция Эйлера.
Следовательно
x?a?(m)-1(mod m).
Пример 7. Решить сравнение
7283*x?1(mod 190116)
Имеем
7283=190116*0+7283
190116=7283*26+758
7283=758*9+461
758=461*1+297
461=297*1+164
297=164*1+133
164=133*1+31
133=31*4+9
31=9*3+4
9=4*2+1
4=1*4+0
0 1 2 3 4 5 6 7 8 9 10
n
0 26 9 1 1 1 1 4 3 2 4
qn
010 1 9 10 19 29 48 221 711 1643 7283
Pn
101 26 235 261 496 757 1253 5769 18560 42889 190116
Qn
Действительно, k=10; x?(-1)9?42889 (mod 190116)= -42889 (mod 190116) =
= 147227(mod 190116); (7283*147227-1)/ 190116=5640 ¦

2.3. КРИПТОСИСТЕМА БЕЗ ПЕРЕДАЧИ КЛЮЧЕЙ

Пусть абоненты А, В, С, ... условились организовать секретную пе-
реписку между собой. Для этой цели они выбирают достаточно большое
простое число р и такое, что р-1 хорошо разлагается на не очень большие
простые множители. Если среди множителей такого числа кратных нет, то
число р-1 называют евклидовым. Каждый из абонентов независимо один
от другого выбирает случайное число, натуральное, взаимно простое с
числом р-1: А, В, С, ... – абоненты; а, b, c, ... – выбранные ими случайные
числа. Далее, абонент А находит число ? из условия
а???1(mod ?(p)), 0 < ? <р-1; (2.2)
абонент В находит число ? из условия
b???1(mod ?(p)), 0 < ? <р-1, (2.3)
где ?(p) – функция Эйлера, а, ? – секретные ключи абонента А; b, ? –
секретные ключи абонента В и т.д.
Пусть абонент А решает послать сообщение m абоненту В. Можно
предполагать, что 0 < m < р-1. Тогда он сначала зашифровывает это сооб-
щение своим первым секретным ключом, находит:
m1?mа(mod p), 0 < m1 < р (2.4)
13


и отправляет абоненту В. Абонент В, в свою очередь, зашифровывает
вновь это сообщение также своим первым ключом:
m2?m1b(mod p), 0 < m2 < р (2.5)
и пересылает его обратно абоненту А. Абонент А, получив обратно свое
дважды зашифрованное сообщение, шифрует его же в третий раз своим
вторым ключом:
m3?m2?(mod p), 0 < m3 < р (2.6)
и вновь отправляет его абоненту В. Последний расшифровывает эту шиф-
ротелеграмму при помощи своего второго ключа:
m4?m3?(mod p), 0 < m4 < р.
В самом деле, из сравнений (2.4) – (2.6) имеем:
m4?mk(mod p),
где k?a???b??(mod р-1).
В силу (2.2) и (2.3) k?1(mod ?(p)). Поэтому m4?m(mod p), а так как
каждое из них положительно и меньше p, то m4=m.
Пример 8. Пусть абоненты A и B решили установить между собой
скрытую связь без передачи ключей. Они выбрали для этого простое
число p = 9551. Тогда p-1=9550.
Абонент A выбирает случайное число a=8159, а абонент B –
b=7159. Абонент A решает сравнение: 8159???1(mod ?(9551)), 0<?< 9550
и находит ?= 6639, а абонент B решает сравнение: 7159???1(mod
?(9551)), 0<?<9550 и находит ?= 6139.
Абонент A решает послать секретное сообщение абоненту B
m=7032. Тогда он сначала шифрует сообщение своим первым ключом:
m1?mа(mod p)= 703281593(mod 9551)= 153.
Абонент B, получив это сообщение, шифрует его своим первым
ключом: m2?m1b(mod p)= 1537159(mod 9551)= 4896, и пересылает его або-
ненту А, который, получив зашифрованное сообщение, шифрует его же в
третий раз своим вторым ключом: m3?m2?(mod p) =48966639(mod 9551)=
7577 и отправляет его абоненту В, который расшифровывает эту шифро-
телеграмму при помощи своего второго ключа: m4?m3?(mod p)=
75776139(mod 9551)= 7032.¦
Пример 9. А теперь рассмотрим похожий пример, но с большими
числами, а именно пусть абоненты A и B выбирают случайное число p =3
6185027886661311069865932815214971204146870208012676262330495002
47285301313. Далее абонент A выбирает случайное число a=32910091146
42412084309938365114701009965471731267159726697218119, а абонент B
– b=72133456729194312009114642445656781208430934647938365165454
65843. Абонент A решает сравнение: 3291009114642412084309938365114
701009965471731267159726697218119???1(mod ?(3618502788666131106
986593281521497120414687020801267626233049500247285301313)), 0 < ?
< 36185027886661311069865932815214971204146870208012676262330495
00247285301312 и находит ?=7182890946724276712267540712060414209
14


95758405828622569613369504272231654775, а абонент B решает сравне-
ние: 721334567291943120091146424456567812084309346479383651654546
5843?? ?1(mod ?(119726214130147567059245861496117904970213993920
59391)), 0 < ? < 1197262141301475670592458614961179049702139939205
9390 и находит ?= 20507850089479826167721544736489099017840580106
89679595249365486507640220987.
Абонент A решает послать секретное сообщение абоненту B
m=16439530856237023359734047455621923453212389086. Тогда он снача-
ла шифрует сообщение своим первым ключом: m1?mа(mod p)= 164395308
562370233597340474556219234532123890863291009114642412084309938365114701009965
471731267159726697218119
(mod 3618502788666131106986593281521497120414687
020801267626233049500247285301313)=2340488471726089607124556756
26416933820229094970133 5616973062664572414115995.
Абонент B, получив это сообщение, шифрует его своим первым
ключом: m2?m1b(mod p)= 23404884717260896071245567562641693382022
9094970133561697306266457241411599572133456729194312009114642445656781208430934
64793836516545465843
(mod 361850278866613110698659328152149712041468702
0801267626233049500247285301313) =200847152309106133691890020899
3851807662985672512619192514870979350742436070, и пересылает его
абоненту А. Абонент А, получив зашифрованное сообщение, шифрует его
же в третий раз своим вторым ключом: m3?m2?(mod p) =200847152309106
13369189002089938518076629856725126191925148709793507424360707182
89094672427671226754071206041420995758405828622569613369504272231654775
(mod 3618502788666
131106986593281521497120414687020801267626233049500247285301313)
= 33742679560664044914439639213562036497523303647522251966113925
36160948437196 и отправляет его абоненту В, который расшифровывает
эту шифротелеграмму при помощи своего второго ключа: m4?m3?(mod p)=
3374267956066404491443963921356203649752330364752225196611392536
1609484371962050785008947982616772154473648909901784058010689679595249365486507640220987 (
mod 36185027886661311069865932815214971204146870208012676262330
49500247285301313)=164395308562370233597340474556219234532123890
86¦
15


3. КРИПТОСИСТЕМА С ОТКРЫТЫМ КЛЮЧОМ
3.1. КРАТКАЯ ИСТОРИЯ ВОПРОСА
В 1976 году американцы Уитфилд Диффи и Мартин Хеллман (Diffi
W., Hellman M.) в статье "Новые направления в криптографии" предложи-
ли новый принцип построения криптосистем, не требующий не только пе-
редачи ключа принимающему сообщение, но даже сохранения в тайне ме-
тода шифрования. Эти шифры позволяют легко зашифровывать и дешиф-
ровать текст и их можно использовать многократно.
В 1978 г. Р. Ривест, А. Шамир и Л. Адлема (R.L.Rivest, A.Shamir,
L.Adleman) предложили пример функции, обладающей рядом замечатель-
ных свойств. На ее основе была построена реально используемая система
шифрования, получившая название по первым буквам фамилий авторов –
система RSA. Рассмотрим ее основные положения на примере криптосис-
темы с открытым ключом.

3.2. ОСНОВНЫЕ ПОЛОЖЕНИЯ КРИПТОСИСТЕМЫ С
ОТКРЫТЫМ КЛЮЧОМ

Пусть абоненты А и В условились организовать секретную пере-
писку между собой с открытым ключом. Тогда каждый из них, независи-
мо от другого, выбирает два достаточно больших простых числа, находит
их произведение, функцию Эйлера от этого произведения и выбирает
случайное число, меньшее этого вычисленного значения функции Эйлера
и взаимно простое с ним. Итак,
А:р1,р2, rА=р1р2, ?(rА), (a,?(rА))=1, 0 < a < ?(rА),
B:q1,q2, rB=q1q2, ?(rB), (b,?(rB))=1, 0 < b < ?(rB).
Затем печатается телефонная книга, доступная всем желающим,
которая имеет вид:
А: rА,a rА – произведение двух простых чисел, известных только А, a –
B: rB,b открытый ключ, доступный каждому, кто хочет передать секрет-
ное сообщение А, rB – произведение двух простых чисел, извест-
ных только B. b – открытый ключ, доступный каждому, кто хо-
чет передать секретное сообщение B.
Каждый из абонентов находит свой секретный ключ из сравнений
а???1(mod ?(rА)), 0 < ? < ?(rА), b???1(mod ?(rB)), 0 < ? < ?(rB),
Итак,
Абонент Открытые ключи Секретные ключи
?
rА, a
A
?
rB, b
B

Пусть абонент А решает послать сообщение m абоненту В:
16


А: m > В и пусть 0 < m < rB, иначе текст делят на куски длины rB.
Сначала А зашифровывает сообщение открытым ключом абонента
В, который есть в телефонной книге, и находит:
m1?mb(mod rB), 0 < m1 < rB,
и отправляет абоненту В. Абонент В, расшифровывает это сообщение
своим секретным ключом:
m2?m1?(mod rB), 0 < m2 < rB,
и получает m4=m.
В самом деле:
m2?m1??(m?)b?mb?(mod rB).
Но b???1(mod ?(rB)), следовательно m2? m(mod rB). Но так как
0<m<rB, 0<m2<rB то m2=m.
Пример 9. Пусть абоненты A и B решили установить между собой
скрытую связь с открытым ключом.
Абонент A выбрал простые числа р1=7643 и р2=8753, их произведе-
ние rА=66899179, функцию Эйлера ?(rA) =р1р2(1-1/р1)(1-1/р2)=66882784.
Затем он выбирает случайное число a=9467 (открытый ключ) и находит
секретный ключ из решения сравнения: а???1(mod ?(rА))=9467???1(mod
66882784), 0<?<?(rА), т.е. ?=30993427.
Абонент B выбрал простые числа q1=7481 и q2=9539, их произведе-
ние rB=71361259, функцию Эйлера ?(rB) =rB(1-1/q1)(1-1/q2)=71344240.
Затем он выбирает случайное число b=74671 (открытый ключ) и находит
секретный ключ из решения сравнения: b???1(mod ?(rB))=74671???1(mod
71344240), 0<?<?(rB), т.е. ?=33289711.
Следовательно имеется таблица:
Абонент Открытые ключи Секретные ключи
66899179, 9467 30993427
A
71361259, 74671 33289711
B
Абонент A решает послать cверхсекретное сообщение абоненту B
m=95637. Тогда он шифрует сообщение открытым ключом абонента B:
m1?mb(mod rB)= 9563774671(mod 71361259)= 25963634.
Абонент B, получив это сообщение, расшифровывает его своим
секретным ключом:
m2?m1?(mod p)= 2596363433289711(mod 71361259)= 95637.¦
Пример 10. А теперь рассмотрим похожий пример, но с большими
числами, а именно: р1=7643 и р2=8753, их произведение rА=66899179,
?(rA) =р1р2(1-1/р1)(1-1/р2)=66882784, a=9467 и ?=30993427. Далее,
q1=170141183460469231731687303715884105727, q2=103507944310551623
86718619237468234569, b=18268770466636286477546060408953537745699
1567871. Тогда имеем: rB=1761096414255759626214007376557990993955
085697884921213758143162998032276663, ?(rB) =rB(1-1/q1)(1-1/q2)= 176109
6414255759626214007376557990993774593719993396819639737240044679
936368. Находим секретный ключ из решения сравнения: b???1(mod
17


?(rB))=182687704666362864775460604089535377456991567871???1(mod
1761096414255759626214007376557990993774593719993396819639737240
044679936368), 0<?<?(rB), т.е. ?=165135868322368842056118800995582
3597594847807953854259478179905981879730111.
Таким образом имеется таблица:
Абонент Открытые ключи Секретные ключи
66899179, 9467 30993427
A
17610964142557596262140073 165135868322368842056118
B
7655799099395508 569788492 800995582359759484780795
1213758143162998032276663, 385425947817990598187973
18268770466636286477546060 0111
408953537745699 1567871
Абонент A решает послать cверхсекретное сообщение абоненту B
m=9563712352348897672389641396218609567172. Тогда он шифрует со-
общение открытым ключом абонента B: m1?mb(mod rB)=956371235234889
7672389641396218609567172182687704666362864775460604089535377456991567871(mod 176
1096414255759626214007376557990993955085697884921213758143162998
032276663)=83255471600987219023332593780878672784122613750592044
594478223942973656948.
Абонент B, получив это сообщение, расшифровывает его своим се-
кретным ключом: m2?m1?(mod p)=8325547160098721902333259378087867
27841226137505920445944782239429736569481651358683223688420561188009955823597
594847807953854259478179905981879730111
(mod 1761096414255759626214007376557990
993955085697884921213758143162998032276663)=95637123523488976723
89641396218609567172.¦

3.3. НАДЕЖНОСТЬ СИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ

В рассмотренной криптосистеме с открытым ключом для перехва-
та сообщения m необходимо найти секретный ключ ?. Это возможно в
двух случаях:
1) если известно разложение rB на простые множители;
2) если известен модуль ?(rB) сравнения b???1(mod ?(rB)).
Но так как rB=q1q2, то ?(rB)=?(q1)?(q2)=(q1-1)(q2-1)=q1q2-(q1+q2)+1 и
(q1-q2) =q12+q22-2q1q2=(q1+q2)2-4q1q2.
2

Следовательно мы имеем равенства:
?(rB)=rB-(q1+q2)+1,
(q1-q2)2=(q1+q2)2-4q1q2,
а значит, зная ?(rB), можно решить эту систему и найти q1 и q2, а зная q1 и
q2, легко вычислить ?(rB). Таким образом, оба подхода определения ключа
? эквивалентны, т.е. задачи одной сложности.
В теории чисел, несмотря на многолетнюю ее историю и на очень
интенсивные поиски в течение последних 30 лет, эффективный алгоритм
18


разложения натуральных чисел на множители так и не найден. Конечно,
можно, перебирая все простые числа до (rB)1/2 , и деля на них rB, найти
требуемое разложение. Но учитывая, что количество простых чисел в
этом промежутке асимптотически равно 2?(rB)1/2?(ln rB)-1, находим, что при
rB, записываемом 100 десятичными цифрами, найдется не менее 4?1042
простых чисел, на которые придется делить rB при разложении его на мно-
жители, что при современных возможностях вычислительной техники за-
тянется на долгие годы.
Известны и более эффективные алгоритмы разложения целых чи-
сел на множители, чем простой перебор простых делителей, но и они
работают очень медленно.
19


4. ЭЛЕКТРОННАЯ ПОДПИСЬ

Криптосистема "открытый ключ" неудобна в том смысле, что по-
лучатель сообщения не знает, кто является отправителем сообщения. Это-
го недостатка лишены протоколы "электронной подписи". Рассмотрим их
основную идею.
Пусть имеется банкир A и несколько вкладчиков – B1, B2, B3, ….
Банкир и каждый из вкладчиков независимо друг от друга выбирают два
больших простых числа и держат их в секрете. Пусть P и Q – простые
числа банкира, pi и qi – простые числа вкладчика Bi, i = 1, 2, 3, … . Пусть
далее R = PQ, ri = qipi, i = 1, 2, 3, … . И пусть банкир выбирает случайно
целое число S с условиями 0 < S < ?(R), (S, ?(R))=1, а каждый из вклад-
чиков также случайно и независимо друг от друга выбирает число si с
условиями 0 < si < ?(ri), (si, ?(ri))=1, i = 1, 2, 3, … . После этого публикует-
ся всем доступная телефонная книга:
A: R, S
B1: r1, s1
B2: r2, s2
…………….
Далее каждый из них, и банкир и вкладчики, находят свои секрет-
ные T, ti ключи из условий:
S?T?1(mod ?(R)), 0 < T < ?(R),
si?ti?1(mod ?(ri)), 0 < ti < ?(ri), i = 1, 2, 3, … .
Пусть вкладчик Bk собирается дать распоряжение m банкиру A, и
пусть
0 < rk < R.
Последнее неравенство существенно для дальнейшего. Положим
для удобства записи B=Bk, r=rk, t=tk, s=sk. Будем считать m < r и (m, r)=1.
Вкладчик B шифрует распоряжение m сначала своим секретным ключом:
m1?mt(mod r), 0 < m1 < r,
а потом открытым ключом банкира:
m2?m1S(mod R), 0 < m2 < R.
Банкир A, получив шифрованную телеграмму m2, расшифровывает
ее пользуясь сначала своим секретным ключом T:
m3?m2T(mod R), 0 < m3 < R.
а потом открытым ключом s вкладчика:
m4?m3s(mod r), 0 < m4 < r,
и получает m4 =m.
Действительно, так как m3?m2T(mod R), а m2?m1S(mod R), то
m3?m1TS(mod R), где S?T?1(mod ?(R)). Если (m1, R)=1, то по теореме
Ферма-Эйлера m1TS?m1(mod R), т.е. m3?m1(mod R). Но 0 <m3 < R,
20


0 < m1 < r < R, следовательно m3?m1. Имеем m4?m3s?m1s?mst(mod r),
s?t?1(mod ?(r)) и (m,r)=1, а значит m4?m(mod r), но каждое из них меньше
r и больше 0. Следовательно, эти числа равны, т.е. m4?m1. Таким образом,
банкир A получит распоряжение m от вкладчика B.
Пример 11. Пусть банкир A выбирает простые числа 10243 и
57037. Вкладчик B выбирает простые числа 175261 и 817549. Таким
образом, R=10243?57037=584229991 и r=175261?817549=143284455289.
Пусть 381259693 и 3387425143 – открытые ключи банкира и
вкладчика соответственно.
Находим секретный ключ банкира из условия:
S?T?1(mod ?(R))=381259693?T?1(mod ?(584229991)), 0 < T < 584162712.
Откуда T=182938789.
Далее находим секретный ключи вкладчика из условия:
s?t?1(mod ?(r))=3387425143?t?1(mod ?(143284455289)), 0<t<143283462480
Откуда t=111788667367.
Тогда открытая телефонная книга имеет вид:
A: 584229991, 381259693;
B: 143284455289, 3387425143.
Вкладчик B дает поручение m=134645771 своему банкиру A и
замечая, что R<r, шифрует его сначала открытым ключом банкира, а по-
том своим секретным ключом:
m1=134645771381259693?116030491(mod 584229991),
m2=116030491111788667367?38467700641(mod 143284455289).
Банкир A, получив шифрованную телеграмму m2 = 38467700641, и
замечая, что R<r, расшифровывает ее пользуясь сначала открытым клю-
чом s вкладчика, а потом своим секретным ключом T:
m3=384677006413387425143?116030491(mod 143284455289),
m4=116030491182938789?134645771(mod 584229991).
А так как 134645771<584229991, то банкир делает вывод, что
134645771 и есть распоряжение вкладчика. ¦
Пример 12. А теперь рассмотрим похожий пример, но с большими
числами, а именно пусть банкир A выбирает простые числа P=194266889
2225729070919461906823518906642406839052139521251812409738904285
205208498221 и Q=1989292945639146568621528992587283360401824603
189390869761855907572637988050133502132777. Вкладчик B выбирает

<< Пред. стр.

страница 2
(всего 3)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign