Algoritma RSA

RSA adalah algoritma untuk kriptografi kunci publik yang didasarkan pada kesulitan dugaan anjak bilangan bulat besar, masalah anjak piutang. RSA adalah singkatan dari Ron Rivest, Adi Shamir dan Leonard Adleman, yang pertama kali secara terbuka dijelaskan algoritma pada tahun 1977. Clifford Cocks, seorang matematikawan Inggris, telah mengembangkan sebuah sistem yang setara pada tahun 1973, tapi itu tidak dideklasifikasi sampai 1997.

Seorang pengguna RSA menciptakan dan kemudian menerbitkan produk dari dua bilangan prima besar, bersama dengan nilai tambahan, seperti kunci publik mereka. Faktor prima harus dirahasiakan. Siapapun dapat menggunakan kunci publik untuk mengenkripsi pesan, tetapi dengan metode saat ini diterbitkan, jika kunci publik cukup besar, hanya seseorang dengan pengetahuan tentang faktor prima dapat membuka pesan. Apakah melanggar enkripsi RSA adalah sekeras anjak adalah pertanyaan terbuka yang dikenal sebagai masalah RSA.

Sejarah

Adi Shamir, , salah satu penulis dari RSA : Rivest , Shamir dan AdlemanAlgoritma RSA adalah publik dijelaskan pada tahun 1977 oleh Ron Rivest , Adi Shamir , dan Leonard Adleman di MIT , huruf RSA adalah inisial nama keluarga mereka , tercantum dalam urutan yang sama seperti di atas kertas.

MIT diberikan US Patent 4.405.829 untuk " sistem komunikasi kriptografi dan metode " yang digunakan algoritma pada tahun 1983 . Paten akan berakhir pada tanggal 21 September 2000 ( jangka waktu paten adalah 17 tahun pada saat itu ) , tetapi algoritma ini dirilis ke dalam domain publik oleh RSA Security pada tanggal 6 September 2000, dua minggu sebelumnya . [ 4 ] Karena kertas yang menjelaskan algoritma telah diterbitkan pada bulan Agustus 1977 , [ 3 ] sebelum Desember 1977 tanggal pengajuan aplikasi paten , regulasi di sebagian besar sisa paten menghalangi dunia di tempat lain dan hanya paten AS diberikan . Telah bekerja Cocks ' sudah dikenal publik , hak paten di Amerika Serikat mungkin tidak mungkin terjadi , baik .

Dari abstrak DWPI tentang paten ,

Sistem ini mencakup saluran komunikasi digabungkan untuk setidaknya satu terminal memiliki perangkat encoding dan setidaknya satu terminal memiliki perangkat decoding . Pesan - to-be - ditransfer dienkripsi ke ciphertext di terminal pengkodean dengan pengkodean pesan sebagai M nomor dalam satu set yang telah ditentukan . Angka itu kemudian dinaikkan menjadi kekuatan yang telah ditentukan terlebih dahulu ( terkait dengan penerima yang dituju ) dan akhirnya dihitung . Sisanya atau residu , C, ... dihitung ketika jumlah exponentiated dibagi dengan produk dari dua bilangan prima yang telah ditentukan ( terkait dengan penerima yang dituju ) .Clifford Cocks , seorang matematikawan Inggris yang bekerja untuk badan intelijen Inggris GCHQ , dijelaskan sistem setara dalam dokumen internal pada tahun 1973 tetapi, mengingat komputer relatif mahal yang diperlukan untuk menerapkannya pada saat itu, itu sebagian besar dianggap keingintahuan dan , sejauh diketahui publik , tidak pernah digunakan . Penemuannya , bagaimanapun, tidak terungkap sampai 1998 karena klasifikasinya rahasia , dan Rivest , Shamir , dan Adleman dirancang RSA independen pekerjaan Cocks ' .

Operasi

Algoritma RSA melibatkan tiga langkah: pembangkitan kunci, enkripsi dan dekripsi.

pembangkitan kunci
RSA melibatkan kunci publik dan sebuah kunci pribadi . Kunci publik dapat diketahui oleh semua orang dan digunakan untuk mengenkripsi pesan . Pesan dienkripsi dengan kunci publik hanya dapat didekripsi dalam jumlah waktu yang wajar dengan menggunakan kunci pribadi . Kunci untuk algoritma RSA yang dihasilkan dengan cara berikut :

1. Pilih dua berbeda nomor perdana p dan q .

Untuk tujuan keamanan , bilangan bulat p dan q harus dipilih secara acak , dan harus menjadi serupa bit - panjang . Integer Perdana dapat efisien ditemukan menggunakan tes primality .

2. Hitung n = pq .

n digunakan sebagai modulus untuk kedua kunci publik dan swasta . Panjangnya , biasanya dinyatakan dalam bit , adalah panjang kunci.

3. Hitung φ ( n ) = φ ( p ) φ ( q ) = ( p - 1 ) ( q - 1 ) , di mana φ adalah fungsi totient Euler.
4. Pilih e bilangan bulat sehingga 1 < e < φ ( n ) dan gcd ( e , φ ( n ) ) = 1 , yaitu e dan φ ( n ) adalah coprime .

e dilepaskan sebagai eksponen kunci publik .
e memiliki Hamming hasil berat bit - panjang dan kecil pendek enkripsi yang lebih efisien - paling sering 216 + 1 = 65.537 . Namun, nilai yang lebih kecil dari e (seperti 3 ) telah terbukti kurang aman dalam beberapa pengaturan . [ 5 ]

5. Tentukan d sebagai d - 1 ≡ e ( mod φ ( n ) ) , yaitu , d adalah invers perkalian dari e ( Modulo φ ( n ) ) .

Hal ini lebih jelas dinyatakan sebagai memecahkan d diberikan d ⋅ e ≡ 1 ( mod φ ( n ) )
Hal ini sering dihitung dengan menggunakan algoritma Euclidean diperpanjang .
d disimpan sebagai eksponen kunci pribadi .

Dengan konstruksi, d ⋅ e ≡ 1 ( mod φ ( n ) ) . Kunci publik terdiri dari n modulus dan masyarakat ( atau enkripsi ) eksponen e . Kunci pribadi terdiri dari n modulus dan swasta ( atau dekripsi ) eksponen d , yang harus dirahasiakan . p , q , dan φ ( n ) juga harus dirahasiakan karena mereka dapat digunakan untuk menghitung d .

Sebuah alternatif , yang digunakan oleh PKCS # 1 , adalah memilih d pencocokan de ≡ 1 ( mod λ ) dengan λ = lcm ( p - 1 , q - 1 ) , di mana lcm adalah beberapa yang paling umum . Menggunakan λ bukan φ ( n ) memungkinkan lebih banyak pilihan untuk d . λ juga dapat didefinisikan menggunakan fungsi Carmichael , λ ( n ) .

ANSI X9.31 standar mengatur , IEEE 1363 menjelaskan , dan PKCS # 1 memungkinkan , bahwa p dan q sesuai persyaratan tambahan : menjadi bilangan prima yang kuat , dan menjadi cukup berbeda bahwa Fermat faktorisasi gagal .

Enkripsi

Alice mentransmisikan kunci publik-nya (n, e) Bob dan menjaga rahasia kunci pribadi. Bob kemudian ingin mengirimkan pesan M untuk Alice.

Dia pertama kali ternyata M ke integer m, sedemikian sehingga 0 ≤ m <n dengan menggunakan protokol yang disepakati reversibel dikenal sebagai skema bantalan. Dia kemudian menghitung ciphertext c sesuai dengan
$c \equiv m^e \pmod{n} .$

Hal ini dapat dilakukan dengan cepat menggunakan metode exponentiation dengan cara mengkuadratkan. Bob kemudian mengirimkan c untuk Alice.

Dekripsi
Alice dapat memulihkan m dari c dengan menggunakan kunci pribadi eksponen d melalui komputasi
$m \equiv c^d \pmod{n} .$
Mengingat m, dia dapat memulihkan pesan M asli dengan membalik skema bantalan.

(Dalam prakteknya, ada metode yang lebih efisien menghitung c^d menggunakan nilai precomputed di bawah ini.)

Menggunakan algoritma sisa Cina

Untuk efisiensi banyak perpustakaan kripto populer (seperti OpenSSL, Java dan NET.) Menggunakan optimasi berikut untuk enkripsi dan penandatanganan didasarkan pada teorema sisa Cina. Nilai-nilai berikut precomputed dan disimpan sebagai bagian dari kunci pribadi :

p dan q: bilangan prima dari pembangkitan kunci,
$d_P = d\text{ (mod }p - 1\text{)}$
$d_Q = d\text{ (mod }q - 1\text{)}$
$q_\text{inv} = q^{-1}\text{ (mod }p\text{)}$

Nilai-nilai ini memungkinkan penerima untuk menghitung eksponensial m = c^d (mod pq) lebih efisien sebagai berikut:

$m_1 = c^{d_P}\text{ (mod }p\text{)}$
$m_2 = c^{d_Q}\text{ (mod }q\text{)}$
$h = q_\text{inv}(m_1 - m_2)\text{ (mod }p\text{)}$ jika ( $m_1 < m_2$ kemudian beberapa librarie menghitung h sebagai $q_\text{inv}(m_1 + p - m_2)\text{ (mod }p\text{)}$ ).
$m = m_2 + hq\,$

Ini lebih efisien daripada komputasi m ≡ c^d (mod pq) meskipun dua eksponensial modular harus dihitung. Alasannya adalah bahwa kedua eksponensial modular baik menggunakan eksponen kecil dan modulus yang lebih kecil.

Sebuah Contoh Pekerjaan

Berikut adalah contoh dari enkripsi dan dekripsi RSA. Parameter yang digunakan di sini adalah artifisial kecil, tetapi kita juga bisa menggunakan OpenSSL untuk menghasilkan dan memeriksa pasangan kunci nyata.

Pilih dua bilangan prima yang berbeda, seperti

$p = 61$ dan $q = 53$ .
Hitung n = pq memberikan

$n = 61 \times 53 = 3233.$

Hitunglah totient dari produk sebagai φ (n) = (p - 1) (q - 1) memberikan $\varphi(3233) = (61 - 1)(53 - 1) = 3120$
Pilih angka 1 <e <3120 yang coprime ke 3120. Memilih bilangan prima untuk e meninggalkan,kita hanya untuk memeriksa bahwa e bukan pembagi dari 3120. Let $e = 17.$
Hitung d, yang perkalian invers modular e (mod φ (n)) menghasilkan

$d = 2753.$

Kunci publik adalah (n = 3233, e = 17). Untuk pesan plaintext m mengisi, fungsi enkripsi adalah
$c(m) = m^{17} \text{ (mod } 3233\text{)}.$
Kunci pribadi (n = 3233, d = 2.753). Untuk dienkripsi ciphertext c, fungsi dekripsi c²⁷⁵³(mod 3233).
$m(c) = c^{2753} \text{ (mod } 3233\text{)}.$
misalnya, dalam proses enkripsi m = 65, kita hitung
$c \equiv 65^{17} \text{ (mod } 3233\text{)} \equiv 2790 \$
untuk mendekripsi c = 2790, kita hitung
$m \equiv 2790^{2753} \text{ (mod } 3233\text{)} \equiv 65 \$
Kedua perhitungan tersebut dapat dihitung secara efisien menggunakan persegi dan kalikan algoritma untuk eksponensial modular. Dalam situasi kehidupan nyata bilangan prima yang dipilih akan jauh lebih besar, dalam contoh kita akan sepele faktor n, 3233 (diperoleh dari kunci publik tersedia secara bebas) kembali ke bilangan prima p dan q. Mengingat e, juga dari kunci publik, kita kemudian bisa menghitung d sehingga memperoleh kunci pribadi.

Implementasi praktis menggunakan teorema sisa Cina untuk mempercepat perhitungan menggunakan modulus faktor (mod pq menggunakan mod p dan mod q).

nilai-nilai d_p, d_q dan q_inv,yang merupakan bagian dari kunci pribadi adalah sebagai berikut:

$d_p = d\text{ (mod }(p-1)\text{)} = 2753 \text{ (mod } (61-1)\text{)} = 53$

$d_q = d\text{ (mod }(q-1)\text{)} = 2753 \text{ (mod } (53-1)\text{)} = 49$

$q_\text{inv} = q^{-1} \text{ (mod } p\text{)} = 53^{-1} \text{ (mod } 61\text{)} = 38$
(karenanya $q_\text{inv} \times q \text{ (mod } p\text{)} = 38 \times 53 \text{ (mod } 61\text{)} = 1$ )
Berikut adalah bagaimana d_p, d_q and q_inv digunakan untuk mengefisiensi dekripsi. (Enkripsi efisien dengan pilihan eksponen publik e)
$m_1 = c^{d_p} \text{ (mod } p\text{)} = 2790^{53} \text{ (mod } 61\text{)} = 4$
$m_2 = c^{d_q} \text{ (mod } q\text{)} = 2790^{49} \text{ (mod } 53\text{)} = 12$
$h = (q_{Inv} \times (m_1 - m_2)) \text{ (mod } p\text{)} = (38 \times -8) \text{ (mod } 61\text{)} = 1$
$m = m_2 + h \times q = 12 + 1 \times 53 = 65$ (sama seperti di atas, tetapi dihitung lebih efisien).

NB:
Mohon maaf apabila ada kalimat atau kata yang tidak dimengerti, karena sebagian referensi berasal dari terjemahan google transleter.

Sumber : http://en.wikipedia.org/wiki/RSA_%28algorithm%29

Monday 2 September 2013

Algoritma RSA

Sejarah

Operasi

No comments:

Post a Comment