Сборник докладов республиканской научно-технической конференции значение информационно-коммуникационных

ЭЛЛИПТИК ЭГРИ ЧИЗИҚЛАРГА АСОСЛАНГАН КАЛИТЛАРНИ 
ТАҚСИМЛАШ АЛГОРИТМЛАРИ ВА ПРОТОКОЛЛАРИ 
У.Р.Мардиев (катта ўқитувчи, Муҳаммад ал-Хоразмий номидаги ТАТУ) 
Кўплаб очиқ калитли криптографик маҳсулотлар ва стандартлар деярли 
анъанавий мавқега эришган RSA ва Эль Гамал алгоритмларига асосланган [1-
3].Сўнгги вақтларда криптотаҳлил усулларининг ва ҳисоблаш техникасининг 
кескин ривожланиши тизимларнинг ишончли ҳимояси учун калит битлари 
сонининг ҳам катта бўлишига олиб келди, бу эса анъанавий тизимларни 
қўлловчи тизимлар иловасини юкланиш вақтининг ортишига олиб келди. Бу 
ўз навбатида катта транзакцияларни ҳимоялаш талаб этиладиган, электрон 
тижоратга ихтисослашган алоқа тугунларида кўплаб муаммоларни келтириб 

---

365 
чиқарди. Шу боис анъанавий мавқега эришган тизимларга рақиб - эллиптик 
эгри чизиқларга асосланган криптография вужудга келди [4-8]. 
Эллиптик эгри чизиқларга асосланган криптографик тизимларнинг 
анъанавий тизимларга нисбатан афзаллиги, уларда фойдаланиладиган калит 
узунлиги разряди кичик бўлганда ҳам, эквивалент ҳимоя билан 
таъминлашидадир. Бу эса қабул қилувчи ва узатувчи мослама процессор-
ларининг юкланиш вақтини камайтиради. 
Эллиптик эгри чизиқларга асосланган калитлар тақсимотида Диффи- 
Хеллман схемаси аналоги. 
Калит тақсимотининг эллиптик эгри чизиқлардаги 
аналоги қуйидаги кўринишда бўлади: аввал катта туб 
р
сон ва эллиптик эгри 
чизиқ учун 
𝑎, 𝑏
параметрлар танланади [9-11]. Бу эллиптик нуқталар гуруҳи 
Е
р
(𝑎, 𝑏)
ни беради. Сўнгра 
Е
р
(𝑎, 𝑏)
да генерацияловчи нуқта 
𝐺 = (𝑥, 𝑦)
танланади. 
𝐺
ни танлаганада 
𝑛𝐺 = 0
шартни қаноатлантирувчи n нинг энг 
кичик қиймати жуда ҳам катта туб сон бўлиши муҳим. Криптотизимнинг 
𝐺
ва 
Е
р
(𝑎, 𝑏)
параметрлари барча иштирокчиларга маълум параметр 
ҳисобланади.
 
Месси – Омур схемаси бўйича калит тақсимлаш протоколи. 
Фараз 
қилайлик 
Е − 𝑛
 
тартибли эллиптик эгри чизиқ, 
е
 
эса
 
(е, 𝑛)

1
, 
1

е

𝑛
 
шартни 
қаноатлантирувчи сон. Инвертлаш алгоритмидан фойдаланиб 
𝑑 ≡ 𝑒
−1
𝑚𝑜𝑑 𝑛
ни топамиз. Бутун сонлар устидаги модул арифметикаси қонунлари билан 
эллиптик эгри чизиқ нуқталари устидаги модул арифметикаси қонунлари бир 
хил бўлгани учун, эллиптик эгри чизиқнинг ихтиёрий 
Р
нуқтасини қуйидаги 
формулалар ёрдамида ҳисоблаш мумкин: 
𝑄 = 𝑒𝑃, 𝑅 = 𝑑𝑄.
Месси – Омур протоколи эллиптик эгри чизиқнинг берилган нуқтасини 
базавий нуқтага нисбатан скаляр кўпайтувчисини аниқлаш муаммосининг 
ечилишига, яъни эллиптик эгри чизиқларда дискрет логарифм масаласини 
ечишга асосланган [9-11]. 
Менезес-Кью-Ванстоннинг калит тақсимлаш схемаси. 
Менезес-Кью-
Ванстоннинг калит тақсимлаш схемаси, яъни 
𝑀𝑉𝑄
- протоколи аввал 
келтирилганларидан фарқ қилади [12-14]. Аввалги келтирилган протоколлар 
“воситачи” ҳужумидан ҳимояланмаган эди. Воситачи деганда, 
А
ва 
В
иштирокчиларнинг очиқ алоқа каналини бошидан бошқариб турувчи ва 
уларнинг нормал мулоқотига ҳалақит берувчи криптотаҳлилчи назарда 
тутилади. Воситачи очиқ канал орқали ўтувчи хабарларни тутиб қолиш, 
А
ва 
В
иштирокчиларга ўзининг хабарларини юбориш, қонуний иштирокчиларда 
уларнинг ҳар бири воситачи билан бевосита мулоқот қилаётган бўлсада, 
протоколнинг нормал ишлаётган тассуротини ҳосил қилиш имкониятига эга. 
Фаол криптотаҳлилчининг фаолиятини йўқотиш учун масалан Месси-
Омур протоколида қисқа муддатли 
𝑒
𝐴
𝑃, 𝑒
𝐵
𝑃
калитларнинг аутентификацияси 
зарур. Бунинг учун 
𝑑
𝐴
𝑃
ва 
𝑑
𝐵
𝑃
калитларни очиқ эълон қилишдан 
фойдаланилади. Бунда бегона шахс дискрет логарифлаш масаласи қийин 
ечиладиган муаммо бўлгани сабабли воситачи бўла олмайди. Протоколда 
қисқа муддатли очиқ калит узоқ муддатлиси билан функционал боғланган 

---

366 
ҳолда ташкил этилади, бу эса учинчи шахснинг иккита иштирокчи орасида 
воситачи бўлишининг олдини олади. Мақсадига эришиш учун воситачи ҳам 
қисқа вақтли ҳам узоқ вақтли калитларнинг узатилиш жараёнига суқилиб 
кириши, 
А
ва 
В
иштирокчилар орасида узатилган узоқ муддатли калит-
ларнинг тўғрилигини текширишга монеълик қилиши зарур. 
Бу протоколнинг математик асосини модул арифметикаси асосида, 
бажарилиш (имплементация) жараёнини эллиптик эгри чизиқ нуқталари 
қисмгруппасининг циклик хоссасига асосланиб амалга ошириш мумкин 
Эллиптик эгри чизиқларга асосланган криптотизимлар учун Эль Гамал 
протоколи. 
RSA криптотизимида Эль Гамал протоколининг қўлланилиши 
қуйидагича бўлади. 
𝑛
туб сон ва ихтиёрий 
𝑝 < 𝑛
ва 
𝑞 < 𝑛
сонлар танланади. 
Очиқ калит сифатида (
𝑛, 𝑝, 𝑝
𝑞
𝑚𝑜𝑑𝑛 = 𝑦
) учлик, махфий калит сифатида эса 
𝑞
дан фойдаланилади.
Очиқ 
𝑚
матнни шифрлаш учун 
𝑎 ≡ 𝑝
𝑘
(𝑚𝑜𝑑 𝑛), 𝑏(𝑚) ≡ (𝑦
𝑘
𝑚)(𝑚𝑜𝑑 𝑛)
ҳисоблаш керак бўлади, бунда 
𝑘
- ихтиёрий 
𝑛
билан ўзаро туб бўлган сон. 
𝑎, 𝑏(𝑚)
жуфтлик шифрматн бўлади. Равшанки, матнни шифрини очиш учун 
𝑚 = (
𝑏(𝑚)
𝑎
𝑞
) 𝑚𝑜𝑑 𝑛
ҳисобланади. 
Эллиптик эгри чизиқнинг мультипликатив группасини қўлловчи Эль 
Гамал протоколининг модификацияси қуйидагича. 
Фараз қилайлик, М очиқ матн Е эллиптик эгри чизиқнинг нуқтаси 
бўлсин. Агар очиқ матн бир қанча нуқталар тўпламидан иборат бўлса, қуйида 
келтириладиган алмаштиришлар ҳар бир нуқта учун алоҳида бажарилади. 
Криптотизимнинг 
А
ва 
В
иштирокчилари Диффи-Хеллман протоколи 
бўйича 
𝑘
𝐴
𝑄
ва 
𝑘
𝐵
𝑄
калит қисмларини алмаштиришди. 
А
иштирокчи 
иштирокчига М хабарни юбормоқчи бўлса, 
𝑙
махфий сонни танлайди ва 
В
иштирокчига эллиптик эгри чизиқнинг 
𝐸 = (𝑙𝑄, 𝑀 + 𝑙(𝑘
𝐵
𝑄))
нуқталар 
жуфтини юборади. Олинган ахборотни шифрини очиш учун 
В
иштирокчи 
𝑇 = 𝑘
𝐵
(𝑙𝑄)(𝑙(𝑘
𝐵
𝑄))
ни ҳисоблаши керак. Бунда 
𝑀 = 𝑀 + 𝑙(𝑘
𝐵
𝑄) − 𝑇
. 
Эътиборли жиҳати шундаки, 
𝑙𝑄
нуқта шифрни йиғиш функциясини 
бажаради ва демак, бирон бир 
𝑄
нуқта икки марта ишлатилиши мумкин эмас. 
Агар икки марта ишлатилса, икки хил шифрматнни таққослаш натижасида 
нафақат шифрматннинг шифрини синдириш, балки тизимнинг махфий 
компоненталарини аниқлашнинг ҳам имкони туғилади. 
Фодйланилган адабиётлар рўйҳати: 
1. 
US Patent, Rivest R., Shamir A. and Adleman L.: Cryptographic Communications System and 
Method. 4,405,829, 1983. 
2. 
ElGamal T., A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, 
IEEE Transactions on Information Theory, 1985, vol. IT-31, p. 469-472. 
3. 
T. El Gamal, A Public-key Cryptosystem and a Signature Based on Discrete Logarithms. IEEE 
Trans. Inform. Theory, Vol. IT-31, pp.469-472, July 1985. 
4. 
Miller V. Use of elliptic curves in cryptography // Advances in cryptology — CRYPTO’85 (Santa 
Barbara, Calif., 1985). 1986. (Lecture Notes in Comput. Sci.; V. 218).
5. 
Koblitz N. and Vanstone S. The state of elliptic curve cryptography // Designs, Codes and 
Cryptography, 19 (2000).
6. 
Отчет о НИР «Разработка алгоритма электронной цифровой подписи на эллиптических 
кривых на основе алгебры параметров», ГУП «UNICON.UZ», 2009. 

---

367 
7. 
MenezesA.J.Elliptic Curve Public Key Cryptosystems,Kluwer Academic Publishers,1993 
8. 
N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, vol. 48, pp. 203-209, 1987. 
9. 
Элементы теории чисел и криптозащита: учеб. пособие /Б.И. Воронков, А.С. Шеголеватых – 
ИПЦ ВГУ, 2008г. 
10. 
Н. Смарт, Криптография. -Москва.- Техносфера, 2005. 528 с. 
11. 
С. В. Запечников Криптографические протоколы 
и их применение в финансовой и 
коммерческой деятельности, Москва Горячая линия - Телеком 2007. 
12. 
Menezes A., van Oorschot Р., Vanstone S. Handbook of Applied Cryptography. - CRC Press, 
1996. – 780 рр. 
13. 
Menezes A., Okamoto T. & Vanstone S. Reducing elliptic curve logarithms to logarithms in a 
finite field // IEEE Transactions on Information Theory, 39 (1993). – Рр. 1639-1660.
14. 
Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. Springer-Verlag 
New York, Inc. 2004.-456 рр.