3-Мавзу: Очиқ калитли шифрлаш алгоритмлари Криптология кафедраси

3-Мавзу: Очиқ калитли шифрлаш алгоритмлари

Криптология кафедраси

кат.ўқит., Мардиев У.Р.

Эллиптик эгри чизиқларга асосланган Диффи Ҳеллман алгоритми

Эллиптик эгри чизиқлар

• Эллептик эгри чизиқлар очиқ калитли криптотизимлар оиласининг аъзоси ҳисобланади. Кам сонли ҳисоблашлар асосида RSA ва Дискрет логарифм схемаларининг бардошлилигини таъминлайди (мос ҳолда 160-256 ва 1024-3072 бит калит узунлиги). Эллиптик эгри чизиқлар такомиллашган Дискрет логарифм муаммосига асосланган.

•  

Эллиптик эгри чизиқлар

Эллиптик эгри чизиқлар

• Амма биз учун эллиптик эгри чизиқ фақат қуйидаги тенглама билан тавсифланга нуқталар тўплами бўлиши қифоя:
• қайсики тенгликни қаноатлантирувчи ва ларда. Юқоридаги тенглама эллиптик эгри чиқилар учун Вейерштрасс формуласи деб аталади.

•  

Эллиптик эгри чизиқлар

Эллиптик эгри чизиқлар (нуқталарни қўшиш)

• Иккита нолга тенг бўлмаган ва симметрик бўлмаган нуқта оламиз:

ва

Ушбу икки нуқтадан ўтувчи ва эллиптик эгри чизиқни кесиб ўтувчи учинчи нуқта

:

ёки аналог сифатида

Шундай экан

тенг бўлади (чунки, )

•  

Эллиптик эгри чизиқлар

Мисол:

ва нуқталар эгри чизиқларга тегишли нуқталар. Уларнинг йиғиндиси

•  

Эллиптик эгри чизиқлар

Эллиптик эгри чизиқлар

Мисол:

ва нуқталар эгри чизиқларга тегишли нуқталар. Уларнинг йиғиндиси

•  

Эллиптик эгри чизиқлар

Эллиптик эгри чизиқлар

• тенг бўлган ҳолда тенгламалар қуйидагича ўзгаради:

Мисол:

•  

Эллиптик эгри чизиқлар

Эллиптик эгри чизиқлар (скаляр кўпайтириш)

• ушбу ҳолатда ҳисоблаш марта қўшишни амалга оширишни талаб этади, бу алгоритмни мураккаблигини олиб келади. Лекин бунданда тез ишлайдиган алгоритм мавжуд.
• Шулардан бири иккилантириш-қўшиш (Double-and-Add algorithm). Ушу ҳолатни қуйидаги мисолда қараб чиқамиз.

Масалан:

бўлган ҳолни қараб чиқамиз. ;

•  

n

Эллиптик эгри чизиқлар (скаляр кўпайтириш)

• Иккилантириш-қўшиш алгоритми қуйидаги жараёнларни ўз ичига олади.
• ни танлаш;
• ни ҳосил қилиш учун иккилантириш;
• ни ҳосил қилиш учун га ни қўшиш;
• ни ҳосил қилиш учун ни иккилантириш;
• ни ҳосил қилиш учун натижаларни қўшиш;
• ни ҳосил қилиш учун ни иккилантириш;
• ни ҳосил қилиш учун ни иккилантириш;
• ни ҳосил қилиш учун натижаларни қўшиш;

.

.

.

Натижада ни ҳисоблаган бўламиз.

•  

Эллиптик эгри чизиқлар (скаляр кўпайтириш)

Мисол:

Эллиптик эгри чизиқлар (скаляр кўпайтириш)

Мисол:

Эллиптик эгри чизиқлар чекли майдонда

• Чекли майдонда қуйидагича бўлади:

Эллиптик эгри чизиқлар чекли майдонда

• Ҳар бир учун максимал иккита нуқта мавжуд, шунингдек симметрия тўғри чизиқга нисбатан бўлади.

•  

Эллиптик эгри чизиқлар чекли майдонда

Мисол №1:

• ЭЭЧ ларнинг барча нуқталарини топинг?

бу бўлганда ва ни қийматларини топамиз.

•  

Эллиптик эгри чизиқлар чекли майдонда

• группада ва тенгликларни қаноатлантирадиган нуқталар

ва дан иборат бўлади.

• Симметрия тўғри чизиқга нисбатан бўлади.

•  

Эллиптик эгри чизиқлар чекли майдонда

Мисол №2:

• А) ; Б) ни гуруҳда ҳисобланг?
• бу

=(3,6).

•  

Эллиптик эгри чизиқлар чекли майдонда

б) ; нуқтани иккилантириш

(mod 11)

•  

Эллиптик эгри чизиқлар чекли майдонда

• гуруҳда бўлганда ни топинг?

•  

Асосий ва қўшимча адабиётлар учун тавсиялар

• Асосий адабиётлар
• Christof Paar·Jan Pelzl. Understanding Cryptography: A Textbook for Students and Practitioners. Verlag Berlin Heidelberg 2010.
• Keith M. Martin. Everyday Cryptography Fundamental Principles and Applications. United Kingdom, 2017
• Қўшимча адабиётлар
• Акбаров Д. Е. “Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланилиши” – Тошкент, 2008 – 394 бет.
• Stamp Mark. Information security: principles and practice. USA, 2011.

Саволлар???