ПОӘК 042-18.39.1.206/01-2013
10.09.2013 ж. № 1 басылым
81 беттің 31
Ашық кілттер e=7, n=187 жариялап, жабық кілтті d=23 құпияда сақтаймыз. Қолайлылық
үшін бастапқы мәтін ретінде M=9 деп алып, С шифрланған мәтінін табамыз.
C=9
7
mod 187 =((9
2
)
3
*9) mod 187=(((81)
2
mod 187)*(729 mod 187)) mod 187=(16 mod
187)*(168 mod 187 ) mod 187) mod187=70
Шифрлау кезінде өте үлкен сандармен жұмыс істемеу үшін сандарды біртіндеп алдымен
квадраттап нәтижені n модулі бойынша алады. Сонда n
2
санынан артық сан пайда болмайды. Бұл
тәсілді «квадраттау да, көбейту» (ағылшынша «square-and-multiply») деп атайды.
Хабарды алушы оны дешифрлау үшін d жабық кілтін қолданады:
70
23
mod 187=((70
2
)
11
*70) mod 187=9.
Алгоритм RSA-ді шифрлау үшін ғана емес қолтаңба алу үшін ғана емес қолтаңба алу үшін
де қолдануға болады. Айгүл (А) жолдасы (Б) қол таңба қойылған шифрланған хабарды жіберу
керек болсын. Айгүл мен Болат өздерінің ашық және жабық кілттерін табады.
A: Public n
A
,e
A
, Private d
A
B: Public n
B
, e
B
, Private d
B
m c= m
d
A
mod n
A
=c
e
B
mod n
B
=
dB
mod n
B
=c
eBdB
mod n
B
= v
(nB)k+1
mod n
B
=(c
k
)
(nB)
c mod n
B
=c
Бұл есептеулерді орындай отырып Болат жіберілген хабардың иесі шынымен Айгүл
екендігіне қол жеткізеді, ал Айгүл кейіннен бұл құжаттан бас тарта алмайды, өйткені құжатта
оның электрондық қолы қойылған.
Шабуыл жасау
Ұсынылған алгоритмнің қауіпсіздігі үлкен сандардың жай сандарға жіктеу есебінің
қиындығына сүйенген. Басқа сөзбен айтқанда факторизация есебін шешуге болады, бірақ ол тым
көп уақыт алады. Қазір келесі жіктеу алгоритмдері белгілі: (Number Field Sieve), QS (Quadratic
Sieve), ECM (Elliptic Curve Method) және басқалары. Ең тез алгоритм болып бүгінше NSA
саналады.
Есептеу қабілеттілігі MIPS–жылдарымен саналады. MIPS–жыл дегеніміз – секундына
миллион операция (million instructions per second) орындайтын компьютердің жылдық жұмысы,
яғни шамамен 3*10
13
операция. Мысалы, 1024-биттік сөзді NSA алгоритмімен жіктеу үшін 3*10
7
MIPS жыл кетеді.
Кілттің ұзындығын дұрыс таңдап алу үшін керекті қауіпсіздік дәрежесін анықтау қажет
және жаңадан жасалып жатқан жіктеу алгоритмдерінің мүмкіндіктерін ұмытпау қажет. Ашық
кілтіңіздің ұзындығын 2048 бит етіп алсаңыз алдыңғы 20 жылға оған сенімді болуыңызға болады.
Бірақ әрине мұндай болжаулар орындалмай кетуі де мүмкін.
Енді біз алгоритмнің өзін емес сол алгоритмді қолданып отырған криптографиялық
протоколға жасалатын шабуыл мысалдарын келтірейік.
Мысал 1. Марат уысына Айгүлдің әлдебіреуге жіберген шифрланған с хабары түсті. Марат
кездейсоқ r
x=r
e
a
mod n
A
,
y=xc mod n
A
,
t=r
-1
mod n
A
Осыдан r
-1
x
d
a
1(mod n
A
) екендігі көрініп тұр. Сонымен қатар x
d
A
=r
e
a
d
a
mod n
A
= r mod n
A
.
Енді Марат Айгүлден у-ге қол таңба қоюды сұрайды да u=y
d
a
mod n
A
мәнін табады. Марат
бастапқы хабарды келесі есептеулерді жасап тауып алады:
tu mod n
A
=r
-1
y
d
a
mod n
A
=r
-1
x
d
a
c
d
a
mod n
A
=c
d
a
mod n
A
=m
Мысал 2. Марат Айгүлді m
1
және m
2
хабарларына қол қойып бер деп сұрайды, яғни m
1
d
a
mod n
A
және m
2
d
a
mod n
A
мәндерін алады. Енді ол
C=(m
1
m
2
)
d
a
mod n
A
Мәнін есептесе Айгүл өзі ешқашан көрмеген m
3
=m
1
m
2
құжатына қол қойған болып
шығады.
ПОӘК 042-18.39.1.206/01-2013
10.09.2013 ж. № 1 басылым
81 беттің 32
Мысал 3. Бұл мысал қол қою алгоритмінде орындалатын қадамдардың ретін бұзатын
протоколдарға қалай шабуыл жасауға болатынын көрсетеді. Мысалы Айгүл Болатқа шифрланған
және қол қойылған хабарды жіберсін. Бірақ алгоритмді қолданғанда Айгүл алдымен m хабарын
Болаттың ашық кілтімен, ал соңынан өзінің жабық кілтімен қол қояды:
(m
e
b
mod n
B
)
d
a
mod n
A
Болат өзінің ашық кілті n
B
-нің жіктелуін білетіндіктен, келесі теңдік орындалатындай х
санын таба алады
(m’)
x
=m mod n
B
Енді ол өзінің жаңа ашық кілттерін жариялайтын болса, Айгүл m’ құжатына қол қойды деп
айта алады.
Кішкентай мәнді құжаттарды шифрлағанда тағыда бір қатерлікті атап өтейік. Мысалы, e=5
және m<√n болсын, онда c=m
5
mod n=m
5
. Бұзғыш Маратқа бастапқы хабарды тауып алу үшін √c
мәнін есептеп алу жеткілікті.
Алгоритм Диффи-Хеллмана. Тарихи Диффи-Хеллмана алгоритмі бірінші ашық кілтті
алгоритм болды. Оның қауіпсіздігі арқылы өрісте дискреттік логарифм есептеу есебінің
қиындығына сүйенген.
Яғни, егер y=a
x
mod n мінін берілген х арқылы оңай таба алсаңыз, берілген у арқылы х-тің
мәнін табу қиынға түседі.
Төменде Диффи-Хеллмана кілт ауыстыру протоколы көрсетілген. Айгүл мен Марат алдын
ала үлкен жай p мен n модулі бойынша примитивтік түбір g сандары туралы келісіп алады.
Протокол:
1. Айгүл кездейсоқ үлкен бүтін х санын таңдап алып,
=g
x
mod p мәнін Болатқа жібереді.
2. Болат кездейсоқ үлкен бүтін у санын таңдап алып,
=g
y
mod p мәнін Айгүлге жібереді.
3. Айгүл k=
x
mod p мәнін есептейді.
4. Болат k’=
y
mod p мәнін есептейді.
Табылған k және k’ мәндері g
xy
mod p санына тең. Сонда Айгүл мен Болат ортақ бір кілтке
ие болады. Бұзғыш Марат ашық каналды жасырын қадағалап отырса да қолына түсетін сандар
арқылы құпия кілтті анықтай алмайды.
Гибрид криптожүйелер. Практикада RSA алгоритмі хабарды шифрлау үшін
қолданылмайды. Алгоритмнің жылдамдығы DES алгоритмімен салыстырғанда 1000 есе баяу.
Сондықтан көбінесе гибрид криптожүйелер қолданылады. Гибрид криптожүйелер ашық кілтті
және жабық кілтті алгоритмдерді бірдей қолданады. Мұндай алгоритмнің орындалу реті
келесідей болуы мүмкін. Жабық K кілтін RSA алгоритмінің көмегімен шифрлауға болады.
Бастапқы құжаттар блоктық немесе ағында алгоритмімен К құпия кілтімен шифрланады. Сонда
RSA алгоритмін бір рет қана орындауға болады. Симметриялық алгоритмдердің кемшілігі –
құпия кілт ауысу процедурасы болып табылады. Төменде бұл есеп шешуінің қарапайым жолын
келтірдік. Болат ашық каналмен Айгүлге К құпия кілтін былай жібереді.
Жіберуші (Болат):
1. Кездейсоқ х санын {0,...,2’-1}диапазонынан таңдап алады, мұндағы l 2’
орындалатын ең үлкен сан.
2. Құпия кілт K=h(x) мәнін h хэш-функция көмегімен табады.
3. Айгүлдің ашық кілтімен х-ты шифрлап, оны Айгүлге c=x
e
mod n жібереді.
Алушы (Айгүл):
1. Жабық кілтінің көмегімен Айгүл x=c
d
mod n санын тауып алады.
2. Хэш-функция көмегімен Болатпен екеуіне ортақ K=h(x) құпия кілтін табады.
Бекіту сұрақтары:
1. AES дегеніміз не?
2. Ашық кілтті криптожүйені қалай түсінесіз?
3. RSA криптожүйесі дегеніміз не?
4. Алгоритм Диффи-Хеллмананың жұмысы қандай?
5. Гибрид криптожүйелер туралы не білесіз?
