Tambahan pada Kurva Elliptic
Penafian: Ini tidak adil pada topik kaya kurva elips. Ini banyak disederhanakan. Karena kurva eliptik baru-baru ini mendapat banyak perhatian media dalam konteks enkripsi, saya ingin memberikan beberapa wawasan kecil bagaimana "menghitung" pada kurva eliptik benar-benar berfungsi.
pengantar
Kurva berbentuk bulat panjang adalah set poin (x,y)
di bidang bentuk y^2 = x^3+Ax+B
. (Selain itu, 4A^3+27B^2 ≠ 0
untuk menghindari singularitas buruk.) Anda dapat mempertimbangkan kurva ini di bidang apa pun. Jika Anda menggunakan bidang bilangan real, kurva dapat divisualisasikan dan terlihat seperti ini:
Hal khusus tentang kurva ini adalah bahwa mereka telah sebuah dibangun di operasi aritmatika yang merupakan analog dari penambahan. Anda dapat menambah dan mengurangi poin, dan operasi ini bersifat asosiatif dan komutatif (grup abelian).
Bagaimana cara kerja penambahan?
Catatan: penambahan titik pada kurva elips tidak intuitif. Penambahan semacam ini didefinisikan sebagaimana adanya karena memiliki sifat-sifat bagus tertentu. Aneh, tapi berhasil.
Sebagai kurva eliptik membentuk grup, ada identitas aditif yang setara dengan 0. Artinya, menambahkan 0
titik apa pun tidak akan mengubah hasilnya. Identitas aditif ini adalah "titik" di infinity. Semua garis di pesawat termasuk titik ini hingga tak terbatas, jadi menambahkannya tidak ada bedanya.
Katakanlah setiap garis memotong kurva pada tiga titik, yang mungkin 0
, dan bahwa jumlah dari ketiga titik ini adalah 0
. Ingatlah itu, lihat gambar ini.
Sekarang, pertanyaan alami adalah, apa itu P+Q
? Nah, jika P+Q+R = 0
, lalu P+Q = -R
(atau ditulis sebagai R'
). Dimana -R
? Ini adalah di mana R + (-R) = 0
, yang di sisi lain dari sumbu x dari R
sehingga garis melalui mereka adalah vertikal, berpotongan hanya R
, -R
, dan 0
. Anda dapat melihat ini di bagian pertama gambar ini:
Hal lain yang dapat Anda lihat dalam gambar-gambar ini adalah jumlah titik dengan dirinya sendiri berarti garis bersinggungan dengan kurva.
Cara menemukan persimpangan garis dan kurva eliptik
Dalam hal dua titik berbeda
Umumnya hanya ada satu garis melalui dua titik P=(x0,y0), Q=(x1,y1)
. Dengan asumsi itu tidak vertikal dan dua titik berbeda, kita dapat menuliskannya sebagai y = m*x+q
. Ketika kita ingin menemukan titik-titik persimpangan dengan kurva elips kita bisa menulis
0 = x^3+Ax+B-y^2 = x^3+Ax+B-(m*x+q)^2
yang merupakan polinomial tingkat ketiga. Ini umumnya tidak mudah untuk dipecahkan, tetapi kita sudah tahu dua nol dari polinomial ini: Dua- x
koordinat x0, x1
dari dua poin yang ingin kita tambahkan!
Dengan begitu kita memfaktorkan faktor-faktor linier (x-x0)
dan (x-x1)
dan dibiarkan dengan faktor linier ketiga yang akarnya adalah x
-koordinat titik R
. ( -R
juga karena simetri. Perhatikan bahwa jika R = (x2,y2)
demikian -R = (x2,-y2)
. Ini -
dari grup; itu bukan minus vektorial.)
Dalam hal menambahkan satu titik P
ke dirinya sendiri
Dalam hal ini kita harus menghitung garis singgung kurva pada P=(x0,y0)
. Kami dapat langsung menulis m
dan q
dalam hal A,B,x0,y0
:
3*x0^2 + A
m = ------------
2*y0
-x0^3 + A*x0 + 2*B
q = --------------------
2*y0
Kami mendapatkan persamaan y = m*x+q
dan dapat melanjutkan dengan cara yang sama seperti pada paragraf di atas.
Pohon kasus lengkap
Ini adalah daftar lengkap cara menangani semua kasus tersebut:
Membiarkan P,Q
menjadi poin pada kurva elips (termasuk titik "tak terbatas" 0
)
- Jika
P = 0
atauQ = 0
, kemudianP+Q = Q
atauP+Q = P
, masing-masing - Lain
P ≠ 0
danQ ≠ 0
, jadi biarkanP = (x0,y0)
danQ = (x1,y1)
:- Jika
P = -Q
(artinyax0 = x1
dany0 = -y1
) makaP+Q = 0
- Lain
P ≠ -Q
- Jika
x0 = x1
kemudian kita milikiP=Q
dan kita menghitung garis singgung (lihat bagian di atas) untuk mendapatkanR
. KemudianP+Q = P+P = 2P = -R
- Lain: Kita dapat membuat garis formulir
y = m*x+y
melalui dua titik (lihat bagian di atas) untuk menghitungR
. KemudianP+Q=-R
- Jika
- Jika
Bidang terbatas
Untuk tantangan ini, kami hanya akan mempertimbangkan bidang ukuran di p
mana p
prima (dan karena beberapa detail p ≠ 2, p ≠ 3
). Ini memiliki keuntungan yang bisa Anda hitung dengan mudah mod p
. Aritmatika di bidang lain jauh lebih rumit.
Ini dalam contoh ini kita atur p = 5
dan semua persamaan di sini adalah kongruensi mod 5
.
2+4 ≡ 6 ≡ 1
2-4 ≡ -2 ≡ 3
2*4 ≡ 8 ≡ 3
2/4 ≡ 2*4 ≡ 3 because 4*4 ≡ 16 ≡ 1, therefore 1/4 ≡ 4
Tantangan
Dengan parameter A,B
kurva eliptik, karakteristik bidang utama, p
dan dua titik P,Q
pada kurva eliptik, kembalikan jumlahnya.
- Anda dapat mengasumsikan bahwa parameter
A,B
sebenarnya menggambarkan kurva elips, itu artinya4A^3+27B^2 ≠ 0
. - Anda dapat mengasumsikan bahwa
P,Q
sebenarnya adalah titik pada kurva eliptik atau0
-poin. - Anda dapat menganggap itu
p ≠ 2,3
prima.
Uji Kasus
Saya membuat implementasi (tidak terlalu elegan) di MATLAB / Octave, yang dapat Anda gunakan untuk kasus uji Anda sendiri: ideone.com Saya harap itu benar. Setidaknya itu mereproduksi beberapa perhitungan yang saya buat dengan tangan.
Perhatikan kasus uji sepele yang bekerja untuk semua kurva yang kami pertimbangkan di sini:
Menambahkan nol: P+0 = P
Menambahkan invers:(x,y) + (x,-y) = 0
Untuk p = 7, A = 0, B = 5
dua titik P = (3,2)
dan Q = (6,2)
berada pada kurva elips. Kemudian memegang berikut:
2*Q = Q+Q = P
2*P = P+P = (5,2)
3*P = P+P+P = (5,2)+P = (6,5)
4*P = P+P+P+P = (5,2)+(5,2) = (6,5)+(5,2) = Q
Semua poins pada kurva elips adalah (3,2),(5,2),(6,2),(3,5),(5,5),(6,5),0
Untuk p = 13, A = 3, B = 8
kita dapatkan
(1,8)+(9,7) = (2,10)
(2,3)+(12,11) = (9,7)
2*(9,6) = (9,7)
3*(9,6) = 0
Untuk p = 17, A = 2, B = 2
dan P=(5,1)
kita dapatkan
2*P = (6,3)
3*P = (10,6)
4*P = (3,1)
5*P = (9,16)
6*P = (16,13)
7*P = (0,6)
8*P = (13,7)
9*P = (7,6)
10*P = (7,11)
Jika Anda benar-benar ambisius, ambillah
p = 1550031797834347859248576414813139942411
A = 1009296542191532464076260367525816293976
x0 = 1317953763239595888465524145589872695690
y0 = 434829348619031278460656303481105428081
x1 = 1247392211317907151303247721489640699240
y1 = 207534858442090452193999571026315995117
dan mencoba mencari nomor alami n
sedemikian rupa n*(x0,y0) = (x1,y1)
. Informasi lebih lanjut di sini.
Lampiran
Pertama-tama, terima kasih banyak kepada @ El'endiaStarman untuk meninjau dan mengedit konsep saya!
Mengapa kurva elips?
Yah itu mungkin tampak seperti semacam persamaan arbitrer, tetapi tidak, itu cukup umum: Secara umum kita menganggap "bentuk" geometris di bidang proyektif (di situlah "infinity" berasal. Di sana kita menganggap semua homogen polinomial tingkat tiga. (Yang lebih rendah atau lebih tinggi akan terlalu sulit atau hanya sepele untuk diperiksa.) Setelah menerapkan beberapa batasan untuk mendapatkan properti bagus yang kita inginkan, dan setelah melakukan dehomogenisasi polinomial tersebut (memproyeksikan ke salah satu dari tiga pesawat affine ) kita berakhir dengan persamaan sepertiy^2+a*x*y+b*y = x^3+c*x^2+d*x+e
Ini adalah kurva elips dalam bentuk Weierstrass yang panjang. Ini pada dasarnya adalah kurva yang sama seperti yang kami pertimbangkan, tetapi hanya agak miring. Dengan transformasi koordinat linier, Anda dapat dengan mudah membuat persamaan Weierstras pendek dari itu. contoh , yang masih menyimpan semua properti menarik.
Mengapa kami mengecualikan p=2,3
?
Ini ada hubungannya dengan fakta bahwa untuk bentuk Weierstrass pendek kita perlu pembatasan 4A^3+27B^2 ≠ 0
untuk menghindari singularitas (lebih lanjut tentang itu di bawah). Dalam bidang karakteristik 2 yang kita miliki 4 = 0
dan dalam bidang karakteristik 3 yang kita miliki 27 = 0
, ini tidak memungkinkan untuk memiliki kurva dalam bentuk kelas pendek untuk jenis bidang tersebut.
Apa itu singularitas?
Jika persamaan tersebut 4A^3+27B^2=0
berlaku, kita memiliki singularitas seperti berikut: Seperti yang Anda lihat pada titik-titik itu Anda tidak dapat menemukan turunan dan karenanya tidak bersinggungan, yang "membunuh" operasi. Anda mungkin melihat persamaan y^2 = x^3
atauy^2 = x^3-3*x+2
Mengapa mereka disebut kurva eliptik ?
Alasannya adalah bahwa persamaan bentuk ini muncul di integral elips, misalnya yang Anda dapatkan ketika Anda ingin mengkombinasikan misalnya panjang gelombang dari sebuah elips. Tayangan slide singkat tentang asal usul nama.
Apa yang harus mereka lakukan dengan kriptografi?
Ada cara untuk menghitung dengan nP = P+P+...+P
sangat efisien. Ini dapat digunakan misalnya dalam pertukaran kunci Diffie Hellman . Aritmatika modular dapat diganti dengan penambahan pada subkelompok torsi, ini hanya titik-titik pada kurva yang memiliki urutan terbatas. (Itu artinya mP = 0
bagi sebagian orang m
, yang pada dasarnya hanya menghitung mod m
).
y^2 = x^3 + x
adalah kurva elips yang valid dan(0,0) ≠ 0
merupakan titik pada kurva!)B = 0
dan bertanya-tanya bagaimana cara0
kerjanya ... dan kemudian saya melupakannya. Saya pikir saya berasumsiB
tidak mungkin menjadi 0 di beberapa titik tadi malam. Apakah Anda memiliki saran tentang apa yang harus input untuk ini? Mungkin jikaB = 0
, lalu definisikan0 = (-1, -1)
? Saya senang menyesuaikan kode saya untuk menanganinya, saya hanya berpikir akan lebih baik jika standar untuk kiriman lainnya juga ...[0]
(hanya satu koordinat) adalah titik tak terhingga, atau yang serupa!nP
? Bisakah Anda mengarahkan saya ke sumber daya apa pun pada subjek untuk mendapatkan pemikiran mengalir? Saya kesulitan menemukan apa pun yang dicari Google. Terima kasih!Python 3,
193191 byteSebuah solusi berdasarkan jawaban Pyth Rhyzomatic dan logika Python mereka. Khususnya. Saya suka bagaimana mereka menemukan akar ketiga polinomial kubik monic
x^3 + bx^2 + cx + d
ketika Anda memiliki dua akarx_1
danx_2
dengan mencatat itub == x_1 + x_2 + x_3
dan mengurangi sesuai. Saya berencana untuk menambahkan penjelasan, mainkan ini, dan mungkin mengubahnya menjadi Ruby, jika ternyata Ruby lebih pendek.Tidak melakukan pelanggaran:
sumber