Монтгомери қисығы - Montgomery curve - Wikipedia

Жылы математика The Монтгомери қисығы формасы болып табылады эллиптикалық қисық, әдеттегіден өзгеше Вейерштрас формасы, енгізген Питер Л. Монтгомери 1987 ж.[1] Ол белгілі бір есептеу үшін, атап айтқанда әр түрлі есептеулер үшін қолданылады криптография қосымшалар.

Анықтама

Монтгомери теңдеуінің қисығы

Монтгомери қисығы а өріс Қ арқылы анықталады теңдеу

нақты A, BҚ және бірге B(A2 − 4) ≠ 0.

Жалпы бұл қисық а деп саналады ақырлы өріс Қ (мысалы, шекті өрісі үстінде q элементтер, Қ = Fq) бірге сипаттамалық 2-мен ерекшеленеді A ≠ ±2 және B ≠ 0, бірақ олар сонымен бірге қарастырылады ұтымды үшін бірдей шектеулер бар A және B.

Монтгомери арифметикасы

Арасында бірнеше «амалдар» жасауға болады ұпай қисық сызығының: екі нүктені «қосу» үшіншісін табудан тұрады осындай ; «екі еселеу» ұпай есептеуіштен тұрады (Операциялар туралы қосымша ақпаратты мына жерден қараңыз Топтық заң ) және төменде.

Нүкте Монтгомери формасындағы эллиптикалық қисықта Монтгомери координаттарында ұсынылуы мүмкін , қайда болып табылады проективті координаттар және үшін .

Нүктені ұсынудың мұндай түрі ақпаратты жоғалтатынына назар аударыңыз: шынымен де, бұл жағдайда, ешқандай айырмашылық жоқ аффиндік нүктелер және өйткені олардың екеуі де нүкте арқылы беріледі . Алайда, бұл ұсынудың көмегімен бірнеше нүктелерді алуға болады, яғни берілген , есептеу үшін .

Енді екі тармақты ескере отырып және : олардың сома нүктесі бойынша беріледі кімдікі координаттар мыналар:

Егер , содан кейін операция «екі еселенуге» айналады; координаттары келесі теңдеулермен берілген:

Жоғарыда қарастырылған бірінші операция (қосу ) уақыт шығыны 3 құрайдыМ+2S, қайда М екі жалпыға көбейтуді білдіреді элементтер эллиптикалық қисық анықталған өрістің, ал S білдіреді квадраттау өрістің жалпы элементі.

Екінші операцияның (екі еселенген) уақыт құны 2 құрайдыМ + 2S + 1Д., қайда Д. жалпы элементті а-ға көбейтуді білдіреді тұрақты; тұрақты болатындығын байқаңыз , сондықтан кішкентай болуы үшін таңдауға боладыД..

Алгоритм және мысал

Келесі алгоритм нүктенің екі еселенуін білдіреді Монтгомери формасындағы эллиптикалық қисықта.

Болжам бойынша . Бұл іске асыру құны 1M + 2S + 1 * A + 3add + 1 * 4 құрайды. Мұнда M қажетті көбейтуді, S квадратты, ал А-ға көбейтуді білдіреді.

Мысал

Келіңіздер қисық нүкте .Координаттарда , бірге , .

Содан кейін:

Нәтиже - нүкте осындай .

Қосу

Екі ұпай берілген , Монтгомери қисығында аффиндік координаттарда, нүкте ұсынады, геометриялық арасындағы қиылыстың үшінші нүктесі және өтетін сызық және . Координаттарын табуға болады туралы , келесі жолмен:

1) жалпы сызықты қарастыру аффиндік жазықтықта және оны өткізіп жіберіңіз және (шарт қою), осылайша біреу алады және ;

2) сызықты қисықпен қиып өту керек , ауыстыру қисық теңдеуіндегі айнымалы ; келесісі үшінші дәрежелі теңдеу алынған:

Бұрын байқалғандай, бұл теңдеудің үш-ке сәйкес келетін шешімдері бар координаттары , және . Атап айтқанда, бұл теңдеуді келесі түрде қайта жазуға болады:

3) Жоғарыда келтірілген екі бірдей теңдеудің коэффициенттерін, атап айтқанда, екінші дәрежелі мүшелердің коэффициенттерін салыстыра отырып, мыналар шығады:

.

Сонымен, тұрғысынан жазуға болады , , , , сияқты:

4) табу үшін нүктенің координаты мәнді ауыстыру жеткілікті жолда . Мұның мәні болмайтынына назар аударыңыз тікелей. Шынында да, осы әдіс арқылы нүктенің координаттарын табуға болады осындай , бірақ егер арасындағы қосындыдан алынған нүкте қажет болса және , содан кейін мыналарды ескеру қажет: егер және егер болса . Сонымен, нүкте берілген , табу керек , бірақ мұны белгісін -ге өзгерту арқылы оңай жасауға болады координаты . Басқаша айтқанда, белгісін өзгерту қажет болады мәнді ауыстыру арқылы алынған координат түзудің теңдеуінде.

Жалғастыру, нүктенің координаттары , мыналар:

Екі еселену

Нүкте берілген Монтгомери қисығында , нүкте геометриялық қисық пен жанама түзудің қиылысуының үшінші нүктесін білдіреді ; Сонымен, нүктенің координаталарын табу үшін қосу формуласында келтірілген бірдей әдісті ұстану жеткілікті; дегенмен, бұл жағдайда сызық ж = лх + м қисыққа жанама болуы керек , сондықтан, егер бірге

онда мәні л, білдіреді көлбеу жолдың тізбегі:

бойынша жасырын функция теоремасы.

Сонымен және нүктенің координаттары , мыналар:

Эдвардс қисықтары бар эквиваленттілік

Келіңіздер сипаттамасы 2-ден өзгеше өріс болыңыз.

Келіңіздер Монтгомери түрінде эллиптикалық қисық болыңыз:

бірге ,

және рұқсат етіңіз бұралған Эдвардс түріндегі эллиптикалық қисық болыңыз:

бірге

Келесі теорема эквиваленттілік Монтгомери қисықтары арасында және бұралған Эдвардс қисығы:[2]

Теорема (i) Әрбір бұралған Эдвардс қисығы Монтгомери қисығына эквивалентті түрде тең . Атап айтқанда, бұралған Эдвардс қисығы Монтгомери қисығына эквивалентті қайда , және .

The карта:

-ден туындайтын эквиваленттік болып табылады дейін , кері:

:

Назар аударыңыз, бұл екі қисық арасындағы эквивалент барлық жерде жарамсыз: карта нүктелерінде анықталмаған немесе туралы .

Вейерштрасс қисықтарымен эквиваленттілік

Кез-келген эллиптикалық қисықты Вейерштрасс түрінде жазуға болады. Атап айтқанда, Монтгомери формасындағы эллиптикалық қисық

:

келесі жолмен түрлендірілуі мүмкін: теңдеудің әрбір мүшесін арқылы , және айнымалыларды ауыстырыңыз х және ж, бірге және сәйкесінше, теңдеуді алу үшін

Осы жерден қысқа Weierstrass формасын алу үшін оны ауыстыру жеткілікті сен айнымалымен :

ақырында, бұл теңдеуді береді:

Демек, картаға түсіру келесідей берілген

:

Керісінше, базалық өрістегі эллиптикалық қисық Вейерштрасс түрінде

:

оны Монтгомери формасына ауыстыруға болады, егер ол болса төртке бөлінетін тәртібі бар және келесі шарттарды қанағаттандырады:[3]

  1. кем дегенде бір түбірі бар ; және
  2. квадраттық қалдық болып табылады .

Осы шарттар орындалған кезде, онда бізде картографиялау бар

:
.

Сондай-ақ қараңыз

Ескертулер

  1. ^ Питер Л. Монтгомери (1987). «Факторизация поллард және эллиптикалық қисық әдістерін жылдамдату». Есептеу математикасы. 48 (177): 243–264. дои:10.2307/2007888. JSTOR  2007888.
  2. ^ Бернштейн Даниэль, Питер Биркнер, Марк Джой, Таня Ланге және Christiane Peters (2008). «Twisted Edwards Curves». Криптологиядағы прогресс - AFRICACRYPT 2008 ж. Информатика пәнінен дәрістер. 5023. Springer-Verlag Берлин Гейдельберг. 389–405 бб. дои:10.1007/978-3-540-68164-9_26. ISBN  978-3-540-68159-5.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)
  3. ^ Кацуюки Окея, Хироюки Куруматани және Коуичи Сакурай (2000). Монтгомери-формасы бар эллиптикалық қисықтар және олардың криптографиялық қосымшалары. Ашық кілт криптографиясы (PKC2000). дои:10.1007/978-3-540-46588-1_17.CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)

Әдебиеттер тізімі

Сыртқы сілтемелер