Mengapa bilangan prima penting dalam kriptografi?

191

Satu hal yang selalu mengejutkan saya sebagai non-cryptographer: Mengapa begitu penting untuk menggunakan bilangan prima? Apa yang membuat mereka begitu istimewa dalam kriptografi?

Adakah yang punya penjelasan singkat dan sederhana ? (Saya sadar bahwa ada banyak primer dan bahwa Kriptografi Terapan adalah Alkitab, tetapi seperti yang dikatakan: Saya tidak ingin menerapkan algoritma kriptografi saya sendiri, dan hal-hal yang saya temukan hanya membuat otak saya meledak - tidak ada 10 halaman rumus matematika silahkan :))

Terima kasih atas semua jawabannya. Saya telah menerima salah satu yang membuat konsep aktual paling jelas bagi saya.

Michael Stum
sumber
Beberapa pengamatan: 1. Orang-orang di bawah ini menyebutkan bahwa "faktorisasi utama jumlah besar memakan waktu lama". Sebenarnya, hal yang sama berlaku untuk faktorisasi apa pun. Yang penting adalah bilangan bulat mana saja! = 0 memiliki faktorisasi unik sebagai produk bilangan prima (termasuk 1, yang memiliki dekomposisi panjang 0).
TT_
1
2. Silakan periksa penjelasan saya mengapa bilangan prima penting untuk fungsi-hash: stackoverflow.com/questions/1145217/... Hal ini terkait dengan properti polinomial dengan koefisien yang dimiliki suatu bidang (yang mungkin bukan penjelasan singkat).
TT_
2
Penjelasan singkat terlalu sederhana → Memecahkan: a * b = 91. Sekarang, memecahkan: 13 * 7 = x. Persamaan kedua jauh lebih cepat untuk dipecahkan (untuk manusia atau komputer).
Dem Pilafian

Jawaban:

204

Penjelasan paling mendasar dan umum: kriptografi adalah semua tentang teori bilangan , dan semua bilangan bulat (kecuali 0 dan 1) terdiri dari bilangan prima, sehingga Anda banyak berurusan dengan bilangan prima dalam teori bilangan.

Lebih khusus lagi, beberapa algoritma kriptografi penting seperti RSA secara kritis bergantung pada fakta bahwa faktorisasi utama dalam jumlah besar membutuhkan waktu lama. Pada dasarnya Anda memiliki "kunci publik" yang terdiri dari produk dari dua bilangan prima besar yang digunakan untuk mengenkripsi pesan, dan "kunci rahasia" yang terdiri dari dua bilangan prima yang digunakan untuk mendekripsi pesan. Anda dapat membuat kunci publik menjadi publik, dan semua orang dapat menggunakannya untuk mengenkripsi pesan kepada Anda, tetapi hanya Anda yang mengetahui faktor utama dan dapat mendekripsi pesan tersebut. Semua orang harus memperhitungkan bilangan, yang membutuhkan waktu terlalu lama untuk praktis, mengingat keadaan terkini teori bilangan.

Michael Borgwardt
sumber
7
Ketika kita memasuki era kuantum komputasi tampaknya tepat untuk catatan bahwa faktorisasi bilangan prima menggunakan komputer kuantum dapat dicapai dalam waktu polinomial usiong Shor Algoritma en.wikipedia.org/wiki/Shor%27s_algorithm Kemungkinan bahwa komputer sudah ada yang bisa mendekripsi enkripsi kunci publik seperti RSA
stujo
16
@stujo: Anda melebih-lebihkan keadaan komputasi kuantum secara besar-besaran. Faktanya tidak ada komputer seperti itu. Jumlah terbesar yang telah difaktorkan menggunakan Algoritma Shor dan upaya penelitian berdarah dalam perangkat keras kuantum adalah 21. Itu bukan 21 bit, tetapi angka 21, faktor prima 3 dan 7.
Michael Borgwardt
1
Saya tidak yakin data apa saat ini, sulit untuk mendapatkan info tentang karya terbaru, saya percaya itu kembali pada tahun 2012, artikel ini berasal dari 2014 ( m.phys.org/news/2014-11-largest-factored- quantum-device.html ) Sudahkah kita melihat data publik mulai tahun 2016? Tidak mengecualikan apa yang mungkin diklasifikasikan. Meskipun tidak dapat menjalankan Algoritma Shors, D-Wave sekarang lebih dari 1000 qbits
stujo
1
@stujo: prinsip yang sama akan menentukan kapan kita semua menggunakan CPU Quantum, karena bilangan prima dapat terus bertambah, semua tentang menemukan yang lebih besar, tidak praktis untuk CPU kuantum, masalahnya ada jika beberapa menggunakan CPUS biasa untuk membuat kunci, dan beberapa menggunakan CPU Quantum untuk hancurkan mereka. Kekuatan CPU kuantum, seperti yang saya pahami adalah bahwa ia menggunakan qbits, setiap qbit dapat memiliki 3 nilai, sehingga teknologi baru adalah basis 3 bukan basis 2. CPU 64 qbits akan memiliki 3 ^ 64 kombinasi kata. Tidak tahu bagaimana ini memengaruhi kinerja.
juanmf
5
@ juanmf: pemahaman Anda tentang komputasi kuantum benar - benar salah. Sama sekali tidak ada hubungannya dengan memiliki 3 nilai, yang akan sama sekali tidak menarik. Detailnya sangat kompleks, tetapi efeknya adalah bahwa beberapa algoritma kuantum dapat menyelesaikan masalah dalam kompleksitas Big-O yang lebih rendah daripada algoritma "normal" pada perangkat keras non-kuantum.
Michael Borgwardt
137

Sederhana? Ya.

Jika Anda mengalikan dua bilangan prima besar, Anda mendapatkan bilangan non-prima besar dengan hanya dua faktor prima (besar).

Anjak angka itu adalah operasi non-sepele, dan fakta itu adalah sumber dari banyak algoritma Kriptografi. Lihat fungsi satu arah untuk informasi lebih lanjut.

Tambahan: Hanya sedikit penjelasan. Produk dari dua bilangan prima dapat digunakan sebagai kunci publik, sedangkan bilangan prima sebagai kunci pribadi. Operasi apa pun yang dilakukan pada data yang hanya dapat dibatalkan dengan mengetahui salah satu dari dua faktor akan menjadi non-sepele untuk tidak dienkripsi.

pengguna54650
sumber
2
Juga perlu dicatat bahwa, di samping masalah faktorisasi, banyak crypto modern juga (atau sebaliknya) bergantung pada masalah logaritma diskrit. Keduanya adalah fungsi "satu arah": mudah untuk mengambil input yang dikenal dan menghitung jawaban, tetapi sulit untuk mengambil jawaban dan menghitung input tersebut.
nezroy
4
Mengaitkan penjelasan ini dengan istilah "fungsi satu arah" akan sangat membantu: en.wikipedia.org/wiki/One-way_function
Chris Conway
Tetapi jika kunci publik dapat digunakan untuk mengenkripsi mengapa itu tidak dapat digunakan untuk melakukan yang sebaliknya?
jayarjo
45

Ini adalah contoh yang sangat sederhana dan umum.

The algoritma enkripsi RSA yang umum digunakan dalam situs web perdagangan aman, didasarkan pada kenyataan bahwa adalah mudah untuk mengambil dua (sangat besar) bilangan prima dan kalikan mereka, sementara itu sangat sulit untuk melakukan hal yang sebaliknya - yang berarti: take a jumlah yang sangat besar, mengingat yang hanya memiliki dua faktor utama, dan menemukannya.

Yuval Adam
sumber
30
Hanya FYI, nomor yang Anda dapatkan dari mengalikan dua bilangan prima disebut semi-prime.
Matthew Brubaker
15

Bilangan prima itu sendiri tidak begitu penting, tetapi algoritma yang bekerja dengan bilangan prima. Secara khusus, menemukan faktor-faktor nomor (nomor apa pun).

Seperti yang Anda tahu, angka berapa pun setidaknya memiliki dua faktor. Bilangan prima memiliki sifat unik karena memiliki dua faktor: 1 dan diri mereka sendiri.

Alasan anjak sangat penting adalah ahli matematika dan ilmuwan komputer tidak tahu bagaimana faktor angka tanpa hanya mencoba setiap kombinasi yang mungkin. Yaitu, pertama-tama coba bagi dengan 2, kemudian oleh 3, lalu oleh 4, dan seterusnya. Jika Anda mencoba memfaktorkan bilangan prima - terutama bilangan prima - Anda harus mencoba (pada dasarnya) setiap kemungkinan angka antara 2 dan bilangan prima yang besar itu. Bahkan pada komputer tercepat, perlu bertahun-tahun (bahkan berabad-abad) untuk memperhitungkan jenis bilangan prima yang digunakan dalam kriptografi.

Itu adalah fakta bahwa kita tidak tahu bagaimana faktor efisien sejumlah besar yang memberikan algoritma kriptografi kekuatan mereka. Jika, suatu hari, seseorang mengetahui cara melakukannya, semua algoritma kriptografi yang saat ini kami gunakan akan menjadi usang. Ini tetap merupakan area penelitian terbuka.

Barry Brown
sumber
10
Anda sebenarnya hanya perlu menguji bilangan prima hingga akar kuadrat dari bilangan yang Anda coba faktorkan.
Matthew Brubaker
3
Aku tahu. Itu adalah detail yang saya "abaikan" atas nama kesederhanaan.
Barry Brown
@MatthewBrubaker Maukah Anda menjelaskan mengapa ini? Saya tidak begitu mengerti.
Kartik Chugh
4
@KartikChugh ヅ katakan nbukan prima & n = a * b. Jika a > sqrt(n), bharus lebih kecil dan sebaliknya, a * b > nitu sendiri yang akan meniadakan klaim awal kami. Jadi untuk memeriksa prime, kami hanya memeriksa hingga sqrt.
Abhinav Gauniyal
13

Karena tidak ada yang tahu algoritma cepat untuk memfaktorkan bilangan bulat menjadi faktor prima. Namun, sangat mudah untuk memeriksa apakah satu set faktor utama berlipat ganda ke bilangan bulat tertentu.

nes1983
sumber
1
Cukup menarik, sudah mungkin dalam waktu cepat untuk mengetahui JIKA nomor prima.
nes1983
Ada yang hilang "jika faktor prima besar" di sini.
Ben Voigt
@ Ben: Itu tidak hilang. Masalahnya sulit pada umumnya. Perhatikan bahwa masalah yang sulit secara umum mungkin memiliki kasus mudah. Dalam hal ini, bilangan prima kecil bukanlah satu-satunya kasus yang mudah.
nes1983
2
Tidak ada yang tahu "di depan umum". Mungkin saja badan-badan intelijen dari berbagai pemerintah dunia memiliki teknik yang tidak mereka bagi. Mereka mempekerjakan sejumlah besar lulusan matematika. Misalnya NSA secara diam-diam mempromosikan generasi perdana acak oleh "Dual EC_DRBG", yang mereka tahu lemah, sebagai bagian dari skema kripto standar untuk penggunaan publik. bits.blogs.nytimes.com/2013/09/10/...
don bright
don: dokumen-dokumen snowden tampaknya mengungkapkan bahwa bukan itu masalahnya. mereka menggambar gambar yang cukup konklusif bahwa (pada umumnya, mungkin ada sudut), NSA tidak dapat mendekripsi data terenkripsi melalui sihir matematika khusus hanya mereka yang tahu. Schneier membahas masalah ini secara luas.
nes1983
12

Ada beberapa sumber yang bagus untuk meningkatkan crypto. Ini dia:

Dari halaman itu:

Dalam sistem kriptografi kunci publik yang paling umum digunakan, ditemukan oleh Ron Rivest, Adi Shamir, dan Len Adleman pada tahun 1977, baik kunci publik dan privat diturunkan dari sepasang bilangan prima besar menurut rumus matematika yang relatif sederhana. Secara teori, dimungkinkan untuk mengambil kunci privat dari kunci publik dengan mengerjakan rumus mundur. Tetapi hanya produk dari bilangan prima yang besar adalah publik, dan jumlah anjak sebesar itu menjadi bilangan prima begitu sulit sehingga bahkan superkomputer paling kuat di dunia tidak dapat memecahkan kunci publik biasa.

Buku Bruce Schneier, Applied Cryptography, adalah buku lain. Saya sangat merekomendasikan buku itu; itu menyenangkan membaca.

Brian Clapper
sumber
9

Untuk menjadi sedikit lebih konkret tentang bagaimana RSA menggunakan properti bilangan prima, algoritma RSA sangat tergantung pada Teorema Euler , yang menyatakan bahwa untuk bilangan yang relatif prima "a" dan "N", a ^ e kongruen dengan 1 modulo N, di mana e adalah fungsi total Euler dari N.

Di mana bilangan prima datang ke sana? Untuk menghitung fungsi total Euler dari N secara efisien perlu mengetahui faktorisasi utama N. Dalam kasus algoritma RSA, di mana N = pq untuk beberapa bilangan prima "p" dan "q", maka e = (p - 1) (q - 1) = N - p - q + 1. Tetapi tanpa mengetahui p dan q, perhitungan e sangat sulit.

Secara lebih abstrak, banyak protokol crypotgraphic menggunakan berbagai fungsi pintu jebakan , fungsi yang mudah untuk dihitung tetapi sulit untuk dibalik. Teori bilangan adalah sumber yang kaya dari fungsi pintu jebakan tersebut (seperti penggandaan bilangan prima yang besar), dan bilangan prima sangat penting bagi teori bilangan.

Sam Hasler
sumber
7

Saya akan menyarankan buku A Mathematical Journey In Code . Buku ini memiliki perasaan turun ke bumi yang bagus, yang mengejutkan, karena ini tentang kriptografi. Buku ini merangkum perjalanan Sarah Flannery dari belajar teka-teki sebagai anak-anak hingga menciptakan algoritma Cayley-Purser (CP) pada usia 16 tahun. Buku ini memberikan penjelasan yang luar biasa terperinci tentang fungsi satu arah, teori angka, dan bilangan prima serta bagaimana kaitannya dengan kriptografi.

Apa yang membuat buku ini lebih spesifik untuk pertanyaan Anda adalah Sarah mencoba menerapkan algoritma kunci publik baru menggunakan matriks. Itu jauh lebih cepat daripada menggunakan bilangan prima tetapi lubang loop ditemukan yang bisa memanfaatkannya. Ternyata algoritmanya lebih baik digunakan sebagai mekanisme enkripsi pribadi. Buku ini adalah bukti hebat untuk menggunakan bilangan prima untuk enkripsi karena telah teruji oleh waktu dan tantangan individu yang sangat cerdas.

Jason Rowe
sumber
6

Satu lagi sumber untuk Anda. Keamanan Sekarang! episode 30 (~ 30 menit podcast, tautannya ke transkrip) berbicara tentang masalah kriptografi, dan menjelaskan mengapa bilangan prima penting.

Bill the Lizard
sumber
6

Saya bukan ahli matematika atau cryptician, jadi inilah pengamatan luar dalam istilah awam (tidak ada persamaan mewah, maaf).

Seluruh utas ini diisi dengan penjelasan tentang BAGAIMANA bilangan prima digunakan dalam kriptografi, sulit untuk menemukan siapa pun dalam utas ini menjelaskan dengan cara mudah MENGAPA bilangan prima digunakan ... kemungkinan besar karena semua orang mengambil pengetahuan itu begitu saja.

Hanya dengan melihat masalah dari luar dapat menghasilkan reaksi seperti; tetapi jika mereka menggunakan jumlah dua bilangan prima, mengapa tidak membuat daftar semua jumlah yang mungkin dihasilkan oleh dua bilangan prima?

Di situs ini ada daftar 455.042.511 primes, di mana primes tertinggi adalah 9.987.500.000 ( 10 digit).

Perdana dikenal terbesar (pada Februari 2015) adalah 2 pangkat 257.885.161 - 1 yang 17.425.170 digit.

Ini berarti bahwa tidak ada gunanya menyimpan daftar semua bilangan prima yang diketahui dan apalagi jumlah yang mungkin. Lebih mudah untuk mengambil nomor dan memeriksa apakah itu prima.

Menghitung bilangan prima besar dalam dirinya sendiri adalah tugas yang monumental, jadi menghitung mundur dua bilangan prima yang telah dikalikan satu sama lain baik kriptografer dan matematikawan akan katakan cukup sulit ... hari ini.

Tenang
sumber
3
Hanya paragraf terakhir Anda yang benar-benar valid. Argumen penjumlahan dapat dikatakan untuk setiap nomor komposit juga (ada kisaran besar [secara teknis tak terhingga besar], penyimpanan semua jumlah tidak layak / bodoh). Juga jumlah bilangan prima tidak memiliki banyak relevansi dalam kriptografi, lebih penting (biasanya, seperti dalam kasus RSA) adalah produk mereka. Juga, dengan menghitung terbalik Anda mungkin berarti anjak piutang . Itu mungkin akan membantu dengan maksud Anda di sana.
initramfs
4

Algoritme kriptografi umumnya mengandalkan keamanannya karena memiliki "masalah yang sulit". Sebagian besar algoritma modern tampaknya menggunakan anjak angka yang sangat besar sebagai masalah sulit mereka - jika Anda mengalikan dua angka besar bersama-sama, menghitung faktor-faktor mereka "sulit" (yaitu memakan waktu). Jika kedua angka tersebut adalah bilangan prima, maka hanya ada satu jawaban, yang membuatnya semakin sulit, dan juga menjamin bahwa ketika Anda menemukan jawabannya, itu adalah jawaban yang tepat, bukan jawaban lain yang kebetulan memberikan hasil yang sama.

gkrogers
sumber
4

Saya pikir apa yang penting dalam kriptografi tidak prima itu sendiri, tetapi itu adalah kesulitan dari masalah faktorisasi prima

Misalkan Anda memiliki bilangan bulat yang sangat sangat besar yang dikenal sebagai produk dari dua bilangan prima m dan n, tidak mudah untuk menemukan apa yang m dan n. Algoritma seperti RSA tergantung pada fakta ini.

Omong-omong, ada makalah yang diterbitkan tentang algoritma yang dapat "memecahkan" masalah faktorisasi utama ini dalam waktu yang dapat diterima menggunakan komputer kuantum. Jadi algoritma yang lebih baru dalam kriptografi mungkin tidak bergantung pada "kesulitan" faktorisasi utama ini lagi ketika komputer kuantum datang ke kota :)

Gant
sumber
3

Karena algoritma faktorisasi mempercepat dengan setiap faktor ditemukan. Membuat kedua kunci pribadi menjadi prima memastikan faktor pertama yang ditemukan juga akan menjadi yang terakhir. Idealnya, kedua kunci pribadi juga akan bernilai hampir sama karena hanya kekuatan dari masalah kunci yang lebih lemah.

Michael
sumber
Ini terlihat agak berlebihan bagi saya. Bagian dari bagian kunci yang lebih lemah yang dapat dikomentari dengan jawaban teratas :)
Ulysse BN
-1

Bilangan prima terutama digunakan dalam kriptografi karena menghabiskan banyak waktu dalam menentukan apakah angka yang diberikan adalah bilangan prima atau tidak. Untuk peretas jika algoritma apa pun membutuhkan banyak waktu untuk memecahkan kode itu menjadi tidak berguna bagi mereka

Chengappa BS
sumber
7
Mencari tahu apakah suatu bilangan prima itu murah dan kita membutuhkannya menjadi murah. Bagaimana lagi kita tahu bahwa kita memilih bilangan prima sebagai faktor utama kita dalam RSA atau bilangan prima sebagai modulus dalam kripto bidang terbatas? Yang mahal adalah memfaktorkan sejumlah besar komposit menjadi faktor prima yang besar.
CodesInChaos