Нөлдік криптографияны қадағалаңыз - Trace zero cryptography

Бұл мақалада бірнеше мәселе бар. Өтінемін көмектесіңіз оны жақсарту немесе осы мәселелерді талқылау талқылау беті. (Бұл шаблон хабарламаларын қалай және қашан жою керектігін біліп алыңыз) Бұл мақала үшін қосымша дәйексөздер қажет тексеру. Өтінемін көмектесіңіз осы мақаланы жақсарту арқылы дәйексөздерді сенімді дерек көздеріне қосу. Ресурссыз материалға шағым жасалуы және алынып тасталуы мүмкін. Дереккөздерді табу: «Нөлдік криптографияны бақылау»  – жаңалықтар  · газеттер  · кітаптар  · ғалым  · JSTOR (Наурыз 2011) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз) The осы мақаланың жетекші бөлімі қайта жазу керек болуы мүмкін. Пайдаланыңыз қорғасынды орналастыру жөніндегі нұсқаулық бөлімнің Уикипедия нормаларына сәйкес келуін қамтамасыз ету үшін және барлық маңызды бөлшектерден тұрады. (Маусым 2019) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз) (Бұл шаблон хабарламасын қалай және қашан жою керектігін біліп алыңыз)

1998 жылы Герхард Фрей бірінші кезекте қолдануды ұсынды нөлдік сорттарды іздеу криптографиялық мақсатта. Бұл сорттар - а-да анықталған төменгі тұқымды гипереллиптикалық қисықтағы бөлгіш класының топшалары ақырлы өріс. Бұл топтарды құру үшін пайдалануға болады асимметриялық криптография пайдаланып дискретті логарифм криптографиялық қарабайыр мәселе.

Іздеудің нөлдік сорттары эллиптикалық қисықтарға қарағанда скалярлық көбейтудің жақсы сипаттамасына ие. Бұл эллиптикалық қисықтармен салыстырғанда есептеулерді 3 коэффициентімен жеделдетуге және осыдан криптожүйені жылдамдатуға мүмкіндік беретін осы топтарда жылдам арифметика жасауға мүмкіндік береді.

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

Нөлдік әртүрліліктің элементін ұсыну үшін эллиптикалық немесе гипереллиптикалық қисықтардың элементтерімен салыстырғанда көбірек биттер қажет. Тағы бір кемшілігі - бұл TZV қауіпсіздігін төмендетуге болатындығы ¹/₆^мың жабу шабуылын қолданатын бит ұзындығының.

Математикалық білім

A гипереллиптикалық қисық C тұқымдас ж қарапайым өріс үстінде ${displaystyle mathbb {F} _ {q}}$ қайда q = бⁿ (б жай) тақ сипаттамасы ретінде анықталады

${displaystyle C: ~ y ^ {2} + h (x) y = f (x),}$

қайда f моник, град (f) = 2ж + 1 және градус (сағ) ≤ г. Қисықта кем дегенде біреу болады ${displaystyle mathbb {F} _ {q}}$- рационалды Weierstraßpoint.

The Якобия әртүрлілігі ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ туралы C барлық соңғы кеңейтуге арналған ${displaystyle mathbb {F} _ {q ^ {n}}}$ идеалды класс тобына изоморфты ${displaystyle операторының аты {Cl} (C / mathbb {F} _ {q ^ {n}})}$. Бірге Мумфорд өкілдігі элементтерін ұсынуға болады ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ жұп көпмүшелермен [u, v], қайда сен, v ∈ ${displaystyle mathbb {F} _ {q ^ {n}} [x]}$.

The Фробениус эндоморфизмі σ элементте қолданылады [u, v] туралы ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ сол элементтің әрбір коэффициентінің қуатын дейін көтеру q: σ ([u, v]) = [сен^q(x), v^q(х)]. Осы эндоморфизмнің тән көпмүшесі келесі түрге ие:

${displaystyle chi (T) = T ^ {2g} + a_ {1} T ^ {2g-1} + cdots + a_ {g} T ^ {g} + cdots + a_ {1} q ^ {g-1} T + q ^ {g},}$

қайда а_мен in

Бірге Хассе-Вейл теоремасы кез-келген кеңейту өрісінің топтық тапсырысын алуға болады ${displaystyle mathbb {F} _ {q ^ {n}}}$ күрделі тамырларды қолдану арқылы τ_мен of (Т):

${displaystyle | J_ {C} (mathbb {F} _ {q ^ {n}}) | = prod _ {i = 1} ^ {2g} (1- au _ {i} ^ {n})}$

Келіңіздер Д. элементі болу ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ туралы C, онда эндоморфизмді анықтауға болады ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$, деп аталатын D ізі:

${displaystyle операторының аты {Tr} (D) = қосынды _ {i = 0} ^ {n-1} sigma ^ {i} (D) = D + sigma (D) + cdots + sigma ^ {n-1} (D )}$

Осы эндоморфизмге сүйене отырып, Jacobian әртүрлілігін кіші топқа дейін азайтуға болады G әрбір элементтің нөлдік ізі болатын қасиетімен:

${displaystyle G = {Din J_ {C} (mathbb {F} _ {q ^ {n}}) ~ | ~ {ext {Tr}} (D) = {extbf {0}}}, ~~~ ({ extbf {0}} {ext {бейтарап элемент in}} J_ {C} (mathbb {F} _ {q ^ {n}})}$

G бұл эндоморфизмнің ізі, демек G деп аталатын топ болып табылады нөлдік (кіші) әртүрлілікті іздеу (TZV) ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$.

Қиылысы G және ${displaystyle J_ {C} (mathbb {F} _ {q})}$ өндіреді n-ның айналу элементтері ${displaystyle J_ {C} (mathbb {F} _ {q})}$. Егер ең үлкен ортақ бөлгіш болса ${displaystyle gcd (n, | J_ {C} (mathbb {F} _ {q}) |) = 1}$ қиылысы бос және топтың ретін есептеуге болады G:

${displaystyle | G | = {dfrac {| J_ {C} (mathbb {F} _ {q ^ {n}}) |} {| J_ {C} (mathbb {F} _ {q}) |}} = {dfrac {prod _ {i = 1} ^ {2g} (1- au _ {i} ^ {n})} {prod _ {i = 1} ^ {2g} (1- au _ {i})} }}$

Криптографиялық қосымшаларда қолданылатын нақты топ кіші топ болып табылады G₀ туралы G үлкен бұйрық л. Бұл топ болуы мүмкін G өзі.^[1][2]

TZV үшін криптографиялық маңыздылықтың үш түрлі жағдайы бар:^[3]

• ж = 1, n = 3
• ж = 1, n = 5
• ж = 2, n = 3

Арифметика

TZV тобында қолданылатын арифметика G₀ бүкіл топқа арналған арифметикаға негізделген ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$, Бірақ қолдануға болады Фробениус эндоморфизмі σ скалярлық көбейтуді жеделдету үшін. Мұны мұрағаттауға болады, егер G₀ арқылы жасалады Д. тәртіп л содан кейін σ (D) = sD, кейбір бүтін сандар үшін с. Берілген TZV жағдайлары үшін с келесідей есептеуге болады, қайда а_мен Фробениус эндоморфизміне тән полиномнан шығады:

• Үшін ж = 1, n = 3: ${displaystyle s = {dfrac {q-1} {1-a_ {1}}} {mod {ell}}}$
• Үшін ж = 1, n = 5: ${displaystyle s = {dfrac {q ^ {2} -q-a_ {1} ^ {2} q + a_ {1} q + 1} {q-2a_ {1} q + a_ {1} ^ {3} -a_ {1} ^ {2} + a_ {1} -1}} {mod {ell}}}$
• Үшін ж = 2, n = 3: ${displaystyle s = - {dfrac {q ^ {2} -a_ {2} + a_ {1}} {a_ {1} q-a_ {2} +1}} {mod {ell}}}$

Мұны біле отырып, кез-келген скалярлық көбейтуді ауыстыруға болады mD (| m | ≤ l / 2) бірге:

${displaystyle m_ {0} D + m_ {1} sigma (D) + cdots + m_ {n-1} sigma ^ {n-1} (D), ~~~~ {ext {here}} m_ {i} = O (ell ^ {1 / (n-1)}) = O (q ^ {g})}$

Осы трюк көмегімен бірнеше скалярлық өнімді шамамен 1 / (дейін азайтуға болады)n − 1)^мың есептеу үшін қажетті қосарланған қосындылар mD, егер болжанатын тұрақтылар жеткілікті аз болса.^[3][2]

Қауіпсіздік

Іс қағаздарының нәтижелері бойынша нөлдік субварияларға негізделген криптографиялық жүйелердің қауіпсіздігі^[2][3] гиперлиптикалық қисықтардың қауіпсіздігімен салыстыруға болады g ' аяқталды ${displaystyle mathbb {F} _ {p '}}$, қайда p ' ~ (n − 1)(г / г ' ) үшін | G | ~ 128 бит.

Жағдайлары үшін n = 3, ж = 2 және n = 5, ж = 1 қауіпсіздікті ең көп дегенде 6 битке төмендетуге болады, мұнда | G | ~ 2²⁵⁶, өйткені бұған сенімді бола алмаймыз G 6-тектегі қисық Якобиянда бар. Ұқсас өрістер үшін 4-текті қисықтардың қауіпсіздігі онша қауіпсіз емес.

Нөлдік крипто-жүйеге шабуыл жасау

Жылы жарияланған шабуыл^[4]2-ден 3-ке дейінгі сипаттамалық ақырлы өрістерге және 2-ден 3-ке дейінгі өрістің кеңеюіне нөлдік топтардың іздеуіндегі DLP 0-ден 0-ге дейінгі класс тобында DLP-ге айналуы мүмкін екендігін көрсетеді. негізгі өріс. Осы жаңа класс тобында DLP-ге индексті есептеу әдістерімен шабуыл жасауға болады. Бұл бит ұзындығының қысқаруына әкеледі ¹/₆^мың.

Ескертулер

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

• Винеке, Мальте; Паар, Кристоф (2008 ж. 17 ақпан). Нөлдік іздер бойынша криптография (PDF). Бухумдағы Рур университеті.
• Сазерленд, Эндрю В. (2007). «Нөлдік 101 пайдалы іздер». Массачусетс технологиялық институты.