|
” mavzusida tayyorlangan individual loyiha 1
|
| bet | 9/10 | | Sana | 14.05.2024 | | Hajmi | 210,72 Kb. | | #232165 |
2- usul. Bu usulda nuqta koordinatalari (x; y) va tenglamaning bitta a –koeffisiyentini fiksirlab: (a; x; y R) , b= -ax (6) formula orqali b–koeffisiyent hisoblab topiladi va uning asosida tenglama quriladi. Elliptik egri chiziq koeffisiyentlarini olingan rasional koordinatali nuqta orqali aniqlashning bunday usuli samarali hisoblanadi.
Elliptik egri chiziqlarning rasional nuqtalarini qo‘shish
Ushbu
E : bx c
elliptik egri chiziqda P Q, nuqtalar berilgan bo‘lsin. Bu nuqtalar orqali to‘g‘ri chiziq o‘tkaziladi. U holda o‘tkazilgan chiziq, Ye - egri chiziqni uchinchi nuqtada kesib o‘tadi. Bu B nuqtaniOx - o‘qiga simmetrik ko‘chiriladi va hosil bo‘lgan: B` P Q nuqta P va Q nuqtalarning elliptik egri chiziq ustid a yig‘indisi deb elon qilinadi:
Bu grafik bx c 0 tenglama bitta yechimga ega bo‘lgan hol uchun keltirildi. Yuqorida elliptik egri chiziqda koordinatalari har xil bo‘lgan, ya’ni P Q 0 bo‘lgan nuqtalar yig‘indisini P Q topish ko‘rib chiqildi. Endi P P ? qanday amalga oshirilishi haqida to‘xtab o‘tiladi. Buning uchun elliptik egri chiziqdagi P -nuqta orqali urinma to‘g‘ri chiziq o‘tkaziladi. Bu urinma elliptik egri chiziq grafigidagi ikkinchi qismni (giperbola qismida) biror nuqtada kesib o‘tadi. Ana shu kesib o‘tgan nuqta Ox -o‘qiga nisbatan simmetrik ko‘chiriladi va bu nuqta 2P deb elon qilinadi:
So‘ngra, [3]P ni topish uchun, [3]P=[2]P+P, shu kabi [4]P=[3]P+P, [5]P=[4]P+P va hokazolar amalga oshiriladi. Har doim ham P va Q nuqtalar orqali o‘tuvchi to‘g‘ri chiziq elliptik egri chiziqni uchinchi nuqtada kesib o‘tavermaydi. Masalan, P va Q nuqtalardan o‘tuvchi to‘g‘ri chiziq Ox -o‘qiga perpendikulyar bo‘lib, u elliptik egri chiziqni uchinchi nuqtada kesib o‘tmaydi:
Bunday holda o‘tkazilgan to‘g‘ri chiziq elliptik egri chiziqni cheksizlikda kesib o‘tadi deb qabul qilinib, cheksizlikdagi barcha nuqtalar bitta nol nuqtaga birlashtirilgan deb hisoblanadi, ya’ni cheksizlikdagi barcha nuqtalar, elliptik egri chiziq nuqtalari ustida aniqlangan qo‘shish amaliga nisbatan, haqiqiy sonlarni qo‘shishdagi nol qiymati kabi xossaga ega. Haqiqatan ham, P va Q nuqtalardan o‘tuvchi to‘g‘ri chiziq Ox -o‘qiga perpendikulyar bo‘lib, u elliptik egri chiziqni uchinchi nuqtada kesib o‘tmay, cheksizlikdagi 0E nuqtaga yo‘naladi.
Cheksizlikdagi 0E nuqta bilan P -nuqtani qo‘shishni 0E + P shaklida ko‘rib chiqadigan bo‘lsak, bu nuqtalardan o‘tuvchi to‘g‘ri chiziq Ox -o‘qiga perpendikulyar bo‘lib, elliptik egri chiziqni Q nuqtada kesib o‘tadi, so‘ngra 0E + P -yig‘indini ifodalovchi nuqtani topish uchun bu Q nuqta Ox - o‘qiga simmetrik akslantirilsa, P - nuqta bilan ustmaust tushadi, ya’ni kiritilgan qo‘shish amali qoidasiga ko‘ra 0E + P = P tenglik o‘rinli bo‘ladi. Bu 0E nuqtaOx - o‘qiga nisbatan akslantirilsa, yana qarama-qarshi tomon cheksizligidagi (-0E) nuqtaga yo‘naladi. Ammo, cheksizlikdagi barcha nuqtalar bitta nol nuqtaga birlashtirilganda (-0E)+ P = P tenglikning o‘rinli bo‘lishiga keltirilgan fikr-mulohozalar asosida ham ishonch hosil qilish mumkin.
Elliptik egri kriptografiya (ECC) cheklangan maydon Fp (bu erda p asosiy va p > 3) yoki F2m (bu erda maydonlar o‘lchami p = 2_m_) ustidagi elliptik egri chiziqlardan foydalanadi. Bu shuni anglatadiki, maydon p x p o‘lchamdagi kvadrat matritsadir va egri chiziqdagi nuqtalar faqat maydon ichidagi butun son koordinatalari bilan cheklangan. Maydondagi barcha algebraik amallar (masalan, nuqta qo‘shish va ko‘paytirish) maydon ichida boshqa nuqtaga olib keladi. Cheklangan maydon Fp ustidagi elliptik egri tenglama quyidagi modulli shaklni oladi:
≡ + 7 (mod p)
Tegishli ravishda, "Bitcoin egri" secp256k1 quyidagi shaklni oladi:
≡ + 7 (mod 17)
RSA dan farqli o‘laroq, [0...p-1] (maydon Zp) oralig'idagi butun sonlarni ishlatadi, ECC Galois maydonidagi 𝔽p (bu erda x va y) {x, y} nuqtalaridan foydalanadi. [0...p-1] oralig'idagi butun sonlar).Cheklangan maydon Fp ustidagi elliptik egri chiziq quyidagilardan iborat:0 ≤ x, y < p bo‘ladigan {x, y} butun son koordinatalari to‘plami
elliptik egri chiziqda qolish: ≡ + 7 (mod 17) cheklangan maydon ustidagi elliptik egri chiziqqa misol:
≡ + 7 (mod 17)
F17 ustidagi bu elliptik egri chiziq quyidagicha ko‘rinadi:
≡ + 7 (mod 17)
E'tibor bering, ≡ + 7 (mod 17) cheklangan maydon ustidagi elliptik egri chiziq yuqoridagi rasmdagi ko‘k nuqtalardan iborat, ya'ni amalda kriptografiyada ishlatiladigan "elliptik egri chiziqlar" klassik emas, balki "kvadrat matritsadagi nuqtalar to‘plamidir" "chiziqlar".
Yuqoridagi egri chiziq "ta'lim" dir. U juda kichik kalit uzunligini (4-5 bit) beradi. Haqiqiy dunyoda ishlab chiquvchilar odatda 256 bit yoki undan ko‘p egri chiziqlardan foydalanadilar.
Cheklangan maydonlar ustidagi elliptik egri chiziqlar: hisob-kitoblar
Muayyan nuqta cheklangan maydon ustidagi ma'lum elliptik egri chiziqqa tegishli yoki yo‘qligini hisoblash juda oson. Masalan, {x, y} nuqta , ≡ + 7 (mod 17) egri chizig‘iga quyidagi hollarda tegishli bo‘ladi:
+ 7 - ≡ 0 (mod 17)
P {5, 8} nuqta egri chiziqqa tegishli, chunki (5**3 + 7 - 8**2) % 17 == 0. {9, 15} nuqta egri chiziqqa tegishli emas, chunki (9) **3 + 7 - 15**2) % 17 != 0. Bu hisoblar Python uslubida. Yuqorida keltirilgan elliptik egri chiziq va {5, 8} va {9, 15} nuqtalari quyida tasvirlangan.
Elliptik egri chiziq ustidagi ikkita nuqta (EC nuqtalari) qo‘shilishi mumkin va natija boshqa nuqtadir. Ushbu operatsiya EC nuqtasini qo‘shish deb nomlanadi. Agar G nuqtani o‘ziga qo‘shsak, natija G + G = 2 * G. Agar natijaga yana G ni qo‘shsak, biz 3 * G ni olamiz va hokazo. EC nuqtasini ko‘paytirish shunday aniqlanadi.
Cheklangan maydon ustidagi elliptik egri chiziq ustidagi G nuqtasini (EC nuqtasi) butun k songa ko‘paytirish mumkin va natijada xuddi shu egri chiziqdagi boshqa EC nuqtasi P bo‘ladi va bu operatsiya tezdir:
P = k * G
Yuqoridagi operatsiya ba'zi formulalar va o‘zgarishlarni o‘z ichiga oladi, ammo soddaligi uchun biz ularni o‘tkazib yuboramiz. Bilish kerak bo‘lgan muhim narsa shundaki, EC nuqtasini butun songa ko‘paytirish bir xil egri chiziqdagi boshqa EC nuqtasini qaytaradi va bu operatsiya tezdir. EC nuqtasini 0 ga ko‘paytirish "cheksizlik" deb nomlangan maxsus EC nuqtasini qaytaradi.
Egri chiziqni ko‘paytirishning turli shakllari uchun ECni ko‘paytirish formulalari farqlanadi. Ushbu misolda klassik Weierstrass shaklida elliptik egri chiziqdan foydalanamiz.
Masalan, chekli ≡ + 7 (mod 17) maydoni ustidagi elliptik egri chizig‘idagi G = {15, 13} EC nuqtasini olaylik va uni k = 6 ga ko‘paytiramiz. P = {5, 8 EC nuqtasini olamiz. }:
P = k * G = 6 * {15, 13} = {5, 8}
Quyidagi rasmda EC nuqtasini ko‘paytirishning ushbu misoli tasvirlangan:
Cheklangan maydonlar ustidagi elliptik egri chiziqlar uchun ECC kriptotizimlari generator nuqtasi G (asosiy nuqta) deb ataladigan maxsus oldindan belgilangan (doimiy) EC nuqtasini belgilaydi, bu esa G ni ba'zi bir butun songa ko‘paytirish orqali elliptik egri chiziq ustidagi kichik guruhdagi istalgan boshqa nuqtani hosil qilishi mumkin. [0...r] oralig'ida. R raqami tsiklik kichik guruhning "tartibi" deb ataladi (kichik guruhdagi barcha nuqtalarning umumiy soni).
Kofaktor = 1 bo‘lgan egri chiziqlar uchun faqat bitta kichik guruh mavjud va egri chiziqning n tartibi (egri chiziq ustidagi turli nuqtalarning umumiy soni, shu jumladan cheksizlik) r soniga teng.
G va n sinchkovlik bilan tanlanganda va kofaktor = 1 bo‘lsa, egri chiziqdagi barcha mumkin bo‘lgan EC nuqtalari (shu jumladan maxsus nuqta cheksizligi) G generatoridan uni [1...n] oralig'ida butun songa ko‘paytirish orqali hosil bo‘lishi mumkin. . Bu n butun son "egri chiziq tartibi" deb nomlanadi.
Shuni bilish kerakki, ma'lum EC generator nuqtasi G dan olingan kichik guruhning r tartibi (bu egri chiziq tartibidan farq qilishi mumkin) ushbu egri chiziq uchun barcha mumkin bo‘lgan shaxsiy kalitlarning umumiy sonini belgilaydi: r = n / h. (egri chiziq kofaktoriga bo‘lingan egri tartibi). Kriptograflar ma’lum kriptografik kuch uchun kalit maydoni etarlicha katta bo‘lishini ta'minlash uchun elliptik egri domen parametrlarini (egri tenglama, generator nuqtasi, kofaktor va boshqalar) ehtiyotkorlik bilan tanlaydilar.
Xulosa qilib aytadigan bo‘lsak, ECC kriptografiyasida EC nuqtalari generator nuqtasi G bilan birgalikda tsiklik guruhlarni (yoki tsiklik kichik guruhlarni) hosil qiladi, bu r sonining mavjudligini bildiradi (r > 1), r * G = 0 * G = cheksizlik va kichik guruhdagi barcha nuqtalarni G ni [1...r] oralig‘ida butun songa ko‘paytirish orqali olish mumkin. R raqami guruh (yoki kichik guruh) tartibi deb ataladi.
Elliptik egri kichik guruhlar odatda ko‘plab generator nuqtalariga ega, ammo kriptograflar ulardan birini diqqat bilan tanlaydilar, bu butun guruhni (yoki kichik guruhni) hosil qiladi va hisob-kitoblarda ishlashni optimallashtirish uchun mos keladi. Bu "G" nomi bilan tanilgan generator.
Ma’lumki, ba'zi egri chiziqlar uchun turli generator nuqtalari turli tartibdagi kichik guruhlarni hosil qiladi. Aniqroq qilib aytadigan bo‘lsak, agar guruh tartibi n bo‘lsa, har bir tub d bo‘luvchi n uchun, shunday Q nuqta mavjudki, d * Q = cheksizlik. Bu shuni anglatadiki, bir xil egri chiziq uchun generator sifatida ishlatiladigan ba'zi nuqtalar boshqalarga qaraganda kichikroq kichik guruhlarni yaratadi. agar guruh kichik bo‘lsa, xavfsizlik zaifdir. Bu "kichik kichik guruh" hujumlari sifatida tanilgan. Shuning uchun kriptograflar odatda r kichik guruh tartibini tub son sifatida tanlashadi.
Kofaktor h > 1 bo‘lgan elliptik egri chiziqlar uchun turli tayanch nuqtalar egri chiziqda EC nuqtalarining turli kichik guruhlarini hosil qilishi mumkin. Muayyan generator nuqtasini tanlab, biz egri chiziqdagi nuqtalarning ma’lum bir kichik guruhida ishlashni tanlaymiz va aksariyat EC nuqtasi operatsiyalari va ECC kripto algoritmlari yaxshi ishlaydi. Shunga qaramay, ba’zi hollarda, alohida e’tibor berilishi kerak, shuning uchun faqat tasdiqlangan ECC dasturlari, algoritmlari va dasturiy paketlardan foydalanish tavsiya etiladi.
Xulosa
Kriptografiyada qo‘llaniladigan asosiy matematik tushunchalardan biri modulli arifmetikadir. Modulli arifmetika raqamlarni bo‘lishda qoldiq bilan shug‘ullanadi. Kriptografiyada modulli arifmetika shifrlash va shifrni ochish algoritmlari uchun asos bo‘lib xizmat qiladi. Mashhur misollardan biri RSA algoritmi bo‘lib, uning ixtirochilari Rivest, Shamir va Adleman nomi bilan atalgan. RSA algoritmi shifrlash va shifrni ochish uchun xavfsiz kalitlarni yaratish uchun tub sonlar va modulli arifmetikaning xususiyatlaridan foydalanadi. Shifrlash jarayoni xabarni quvvat moduliga katta kompozit raqamga ko‘tarishni o‘z ichiga oladi, shifrni ochish jarayoni esa shifrlangan xabarni boshqa quvvat moduliga bir xil raqamga ko‘tarishni o‘z ichiga oladi. RSA xavfsizligi katta kompozit raqamlarni faktoring qilish qiyinligiga tayanadi, bu esa hisoblash qiyin deb hisoblangan muammodir.
Matematikaning raqamlarning xossalari va munosabatlari bilan shug‘ullanuvchi bo‘limi bo‘lgan sonlar nazariyasi kriptografiyada ham keng qo‘llaniladi. Eylerning totient funksiyasi va Xitoy qoldiqlari teoremasi kabi raqamlar nazariyasi tushunchalari turli shifrlash algoritmlarida qoʻllaniladi. Eylerning totient funksiyasi RSA da shifrlash ko‘rsatkichi qiymatini hisoblash uchun ishlatiladi, Xitoy qoldiqlari teoremasi esa hisoblarni tezlashtirish uchun ba’zi shifrlash tizimlarida qo‘llaniladi.
Xulosa qilib aytganda, matematika kriptografiya uchun asos yaratadi. Xavfsiz aloqa va nozik ma'lumotlarni himoya qilish modulli arifmetika, tub sonlar, raqamlar nazariyasi, chiziqli algebra, ehtimollar nazariyasi va axborot nazariyasi kabi matematik tushunchalar va tamoyillarga tayanadi. Ushbu matematik vositalardan foydalangan holda kriptografik algoritmlar ma'lumotlarning maxfiyligi va yaxlitligini ta’minlaydi, bu bizga tobora raqamli dunyoda ma’lumotni xavfsiz uzatish imkonini beradi.
|
| |
