Mengapa bilangan prima penting dalam kriptografi?

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.

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.

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.

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.

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.

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.

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

• http://research.microsoft.com/en-us/groups/crypto/firstcrypto.aspx

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.

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.

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.

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.

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.

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.

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 :)

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.

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