PENGANTAR KIRTOGRAFI MODERN - Algoritma untuk Komputasi Discrete Logaritma dan Bayi-Raksasa Langkah Algoritma.

www.uts.ac.id

FEBRIANSAH_17.01.071.035

TEKNIK INFORMATIKA
KRIPTOGRAFI
UNIVERSITAS TEKNOLOGI SUMBAWA

 8.2 Algoritma untuk Komputasi Discrete Logaritma

     Membiarkan G menjadi kelompok yang operasi kelompok dapat dilakukan dengan efisien.        Dengan hasil Bagian B.2.3, ini berarti bahwa eksponensial di G juga bisa dilakukan dengan efisien. Sebuah contoh dari masalah logaritma diskret mengambil bentuk berikut (lihat Bagian 7.3.2): diberikan g ∈ G dan y ∈ < g >, fi nd x seperti yang _{x =} y. ₄ Jawaban ini dilambangkan dengan log _g y, dan unik de fi ned modulo urutan g. Kita kadang-kadang mengacu g di sebuah instance dari masalah logaritma diskret sebagai mendasarkan.

Algoritma untuk menyerang diskrit masalah logaritma jatuh ke dalam dua kategori:

    ·  mereka yang bekerja untuk sewenang-wenang kelompok (algoritma tersebut kadang-kadang disebut umum) dan orang-orang yang bekerja untuk beberapa spesifik kelompok.

      ·    Untuk algoritma mantan jenis, kita sering bisa saja juga mengambil kelompok untuk menjadi < g > itu sendiri (sehingga mengabaikan unsur di G \ < g > kapan g bukan generator G). Ketika melakukan itu, kami akan membiarkan q menunjukkan urutan < g > dan menganggap bahwa q dikenal. Perhatikan bahwa pencarian brute-force untuk logaritma diskrit dapat dilakukan dalam waktu HAI( q) dan jadi kita hanya akan tertarik algoritma yang waktu berjalan lebih baik dari ini.

Kita akan membahas algoritma berikut yang bekerja dalam kelompok sewenang-wenang:

• Bayi-langkah / raksasa-langkah metode, karena Shanks, menghitung logaritma diskrit dalam kelompok agar q pada waktunya O (√ q · polylog ( q)).

• Pohlig-Hellman algoritma dapat digunakan ketika faktorisasi dari urutan kelompok q dikenal. Kapan q memiliki faktor kecil, teknik ini mengurangi logaritma contoh diskrit yang diberikan kepada beberapa contoh dari masalah logaritma diskrit dalam kelompok agar lebih kecil. Solusi untuk masing-masing yang terakhir dapat dikombinasikan untuk memberikan solusi yang diinginkan untuk masalah asli.

Pengantar modern Kriptografi

Kami melihat ke depan di komputasi logaritma diskrit dalam beberapa spesifik kelompok. Sebagai contoh ilustratif tapi sederhana, kita pertama melihat pertama pada masalah di (aditif) kelompok Z _N dan menunjukkan bahwa logaritma diskrit dapat dihitung dalam waktu polinomial dalam kasus ini.

   Inti dari latihan ini adalah untuk menunjukkan bahwa meskipun kelompok siklik pesanan q isomorfis untuk Z _{q (} cf. Contoh 7.58 di Bab 7), dan karenanya semua kelompok siklik dari urutan yang sama, dalam arti tertentu, “sama”,kekerasan masalah logaritma diskrit tergantung dengan cara penting pada khususnya perwakilan yang digunakan untuk grup.

      Memang, algoritma untuk menghitung logaritma diskrit dalam bahan tambahan kelompok Z_N akan bergantung pada fakta bahwa perkalian modulo N juga didefinisikan. pernyataan seperti tidak masuk akal dalam beberapa kelompok sewenang-wenang yang didefinisikan tanpa mengacu aritmatika modular.

      Algoritma bayi-langkah / raksasa-langkah diketahui optimal ( dalam hal waktu yang berjalan asymptotic) sejauh algoritma generik pergi. (Kami berkomentar, bagaimanapun, bahwa lebih banyak ruang-e FFI efisien algoritma generik dengan waktu berjalan sama diketahui.) Terbukti batas bawah pada kompleksitas fi nding logaritma diskrit ketika kelompok diperlakukan secara umum, bagaimanapun, mengatakan apa-apa tentang kekerasan fi nding diskrit logaritma dalam kelompok tertentu.

   Saat ini, algoritma paling terkenal untuk komputasi logaritma diskrit dalam Z ^*_{p (} untuk p Perdana) adalah Nomor umum lapangan saringan. ₅ Heuristik, algoritma ini berjalan dalam waktu 2 _HAI( n ^1/3 · ( catatan n) _2/3) rata-rata untuk menghitung logaritma diskrit dalam Z ^* _p kapan p memiliki panjang ‖ p ‖ = O ( n). Yang penting, pada dasarnya tidak ada non-generik algoritma yang saat ini dikenal untuk menghitung logaritma diskrit dalam kelompok-kelompok tertentu khusus dibangun elliptic curve (cf. Bagian 7.3.4). Ini berarti bahwa untuk kelompok-kelompok seperti, selama urutan kelompok perdana (sehingga menghalangi Pohlig-Hellman algoritma), hanya eksponensial-waktu algoritma untuk menghitung logaritma diskrit dikenal.

Anjak piutang dan Komputasi Discrete Logaritma 

logaritma di Z*_p di sekitar 2 ^{512 1/3}  · 9 ^2/3 ≈ 2 ^{8 · 4} ₌ 2 ³² Langkah. Hal ini sesuai dengan waktu yang dibutuhkan untuk menghitung logaritma diskrit menggunakan yang terbaik algoritma generik dalam grup kurva eliptik pesanan q, dimana q adalah 64-bit perdana, sejak saat itu √q ≈ 2^64/2 = 2^{32 .} 

Kami melihat bahwa grup kurva eliptik fi signi cantly lebih kecil, dengan bersamaan cepat operasi kelompok, dapat digunakan tanpa mengurangi di FFI culty dari masalah logaritma diskrit (setidaknya sehubungan dengan terbaik teknik saat ini dikenal). Secara kasar, kemudian, dengan menggunakan kelompok kurva eliptik di tempat Z _{* p} kita memperoleh skema kriptografi yang lebih e FFI efisien bagi para pemain yang jujur, tapi itu sama-sama sulit bagi musuh untuk istirahat.

8.2.1  The Baby-Langkah / Raksasa-Langkah Algoritma

        Algoritma bayi-langkah / raksasa-langkah, karena Shanks, menghitung logaritma diskrit dalam kelompok agar q pada waktunya O (√ q · polylog ( q)). Idenya sederhana. Diberikan sebagai masukan g dan y ∈ < g >, kita bisa membayangkan unsur-unsur < g > ditata dalam lingkaran sebagai
1 = g ⁰, g ¹, g ²,....... g ^{q - 2}, g ^{q - 1}, g ^q = 1,

dan kita tahu bahwa y harus berbaring di suatu tempat di lingkaran ini. Komputasi dan menuliskan semua titik pada lingkaran ini akan mengambil setidaknya Ω ( q) waktu. Sebaliknya, kita “mark off” lingkaran pada interval   ukuran t=^def[√q]  menghitung dan merekam [q/t] + 1 = O (√ q) elemen

                                     g⁰, g^t, g^2t,…………..,g^[q/t].t

  

(Ini adalah “langkah raksasa”.) Perhatikan bahwa “kesenjangan” antara setiap “tanda” berturut-turut pada lingkaran yang paling banyak t. Selanjutnya, kita tahu bahwa y = g^x kebohongan di salah satu kesenjangan ini. Kami dengan demikian dijamin bahwa salah satu t elemen

y · g ⁰ = g ^x, y · g ¹ = g  ^{x +1} ,          y · g ^t = g ^{x + t},

akan sama dengan salah satu poin kami telah ditandai o ff. (Ini adalah “langkah-langkah bayi”.) Say y · gⁱ₌ g^k.t _. Kita bisa dengan mudah memecahkan ini untuk mendapatkan y = g^kt-i atau login _g y = [kt - i mod q]. Psuedocode untuk algoritma ini diberikan berikutnya.

        Algoritma memerlukan O (√ q) eksponensial dan perkalian di G dan masing-masing eksponensial dapat dilakukan dalam waktu HAI( polylog ( q)) menggunakan e FFI efisien algoritma eksponensial. (Sebenarnya, selain fi nilai rst g_{1 =} g ^t_, setiap nilai g _saya dapat dihitung dengan menggunakan perkalian tunggal sebagai

      

                              g_{i =} g_{i - 1} · g_1.).

menyortir O (√ q) pasang ( IG _saya) dapat dilakukan dalam waktu O (√ q · catatan q), dan kita kemudian dapat menggunakan pencarian biner untuk memeriksa apakah y _saya sama dengan beberapa g _k pada waktunya

HAI( catatan q). Algoritma keseluruhan sehingga berjalan dalam waktu O (√ q · polylog ( q)).

contoh 8.6

Kami menunjukkan aplikasi dari algoritma dalam kelompok siklik Z _{* 29} order

q = 29 - 1 = 28. Mengambil g = 2 dan y = 17. Kami set t = 5 dan menghitung

2 ⁰ ₌ 1, 2 ⁵ ₌ 3, 2 ¹⁰ ₌ 9, 2 ¹⁵ ₌ 27, 2 ²⁰ ₌ 23, 2 ²⁵ ₌ 11.

Pengantar modern Kriptografi

ALGORITMA 8.5

Bayi-langkah / raksasa-langkah algoritma

Memasukkan: elemen g ∈ G dan y ∈ < g >; pesanan q dari g

Keluaran: log_g y

t= [ √q]

untuk i = 0 untuk [q/t]:

menghitung g _i :₌ g^i-t

menyortir pasangan ( i,gi) oleh komponen kedua mereka

untuk i = 0 untuk t:

menghitung y _{i: =} y · g _saya

jika y_{i =} g _k untuk beberapa k, kembali [ kt - i mod q]

(Kami menghilangkan “mod 29” karena dipahami bahwa operasi adalah dalam kelompok Z _* 29.) kemudian menghitung

17 · 2 ⁰ = 17, 17 · 2 ¹ = 5, 17 · 2 ² = 10, 17 · 2 ³ = 20, 17 · 2 ⁴ = 11, 17 · 2 ⁵ = 22,

dan pemberitahuan bahwa 2²⁵ ₌ 11 = 17 · 2⁴_. Dengan demikian kita memiliki log ₂ 17 = 25 - 4 = 21. 

Transformasi " INDONESIA " Ke- 3 Metode Plaint Text dan Chiper Text

Contoh kalimat Transformasi dari Plain Text ke Chiper Text - Mata Kuliah Kriptografi

Dasar Sistem Teknologi Informasi-UTS

                                                                               BAB I
                                                       DASAR TEKNOLOGI INFORMASI

1.1. Pengertian Teknologi Informasi
Teknologi Informasi adalah gabungan antara Teknologi Komputer dan Teknologi
Telekomunikasi. Teknologi Informasi adalah teknologi yang berhubungan dengan
komputer termasuk peralatan-peralatannya seperti ; printer, pembaca sidik jari, dan bahkan
CD-ROM. Program adalah deretan instruksi yang digunakan untuk mengendalikan komputer.
Data adalah bahan mentah bagi computer yang dapat berupa angka maupun gambar.
Informasi adalah bentuk data yang telah diolah sehingga dapat menjadi bahan yang berguna
untuk mengambil keputusan. Teknologi Telekomunikasi (teknologi komunikasi) adalah
teknologi yang berhubungan dengan komunikasi jarak jauh. Yang dapat dikategorikan
teknologi komunikasi ini adalah : Telepon, Radio, TV, dll.

1.2. Pengelompokan Teknologi Informasi
Teknologi Informasi dibagi menjadi 6 :
1. Teknologi Komunikasi
2. Teknologi Masukan (Input Technology)
Adalah teknologi yang berhubungan dengan peralatan untuk memasukan ke
dalam sistem komputer, seperti : keyboard dan mouse.
3. Teknologi Keluaran (Output Technology)
Adalah Teknologi yang berfungsi untuk menyajikan informasi hasil pengolahan
sistem, seperti : Monitor dan Printer.
4. Teknologi Perangkat Lunak (Software)
Adalah deretan instruksi yang digunakan untuk mengendalikan computer.
5. Teknologi Penyimpanan
Dibagi menjadi 2, yaitu :
- Memori Internal ; ROM (Read Only Memory) dan RAM (Random Access
Memory)
- Memori Eksternal ; Eksternal Storage.
6. Teknologi Pemroses
Atau yang biasa kita kenal dengan CPU (Central Processing Unit),
mikroprocessor, atau prosesor. Adalah pusat pengolahan data dengan cara
menjalankan program yang mengatur pengolahan tersebut. Contoh prosesor untu
PC ; Celeron, Core i7, Xeon, Pentium, dan Core Duo. Intel dan AMD adalah
perusahaan yang menghasilkan prosesor.

1.3. Komponen Sistem Teknologi Informasi
Komponen penting di Sistem Teknologi Informasi itu ada 3 :
a. Hardware (Perangkat Keras)
b. Software (Perangkat Lunak)
c. Brainware
1.4. Klasifikasi Sistem Teknologi Informasi
1. Menurut Fungsi Sistem
Dibedakan atas :
 Embedded IT System, Sistem Teknologi Informasi yang melekat pada produk lain.
Contohnya VCR (Video Casette Recorder) memiliki Teknologi Informasi yang
memungkinkan pemakai dapat merekam tayangan televise.
 Dedicated IT System, Sistem Teknologi Informasi yang dirancang untuk
melakukan tugas-tugas khusus. Contoh ATM dirancang khusus untuk melakukan
transaksi keuangan bagi nasabah bank.
 General Purpose IT System, Sistem Teknologi Informasi yang dapat digunakan
untuk melakukan berbagai aktivitas yang bersifat umum. Contohnya PC.
2. Menurut Ukuran
Ukuran dalam pengklasifikasian Sistem Teknologi Informasi tidak harus berupa ukuran
fisik, tetapi lebih cenderung didasarkan pada :
 Ukuran informasi yang dapat ditampung
 Kemampuan sistem yang ditawarkan
 Kecepatan pemroses
 Berdasarkan jumlah orang yang menggunakan system secara bersamaan.
Kelompok ini yaitu ;
 Mikrokomputer, lebih dikenal dengan PC (Personal Computer) dibedakan atas Dekstop
PC, Tower PC, Laptop, Notebook, Palmtop, dan PDA.
 Workstation, merupakan jenis computer yang lebih ampuh daripada kebanyakan PC.
Istilah workstation seringkali membingungkan, pada system yang menggunakan Novell
Netware, workstation berarti PC yang berkedudukan sebagai client.
 Minikomputer, disebut juga dengan Midrange computer, biasa digunakan pada
perusahaan berskala menengah sebagai server.
 Mainframe Komputer, jenis komputer yang digunakan pada perusahaan-perusahaan
berskala besar untuk menangani pemrosesan data dengan volume yang sangat besar. IBM
system/360 merupakan mainframe yang pertama dibuat pada tahun 1964. Digunakan
pada computer History Museum Carlifornia. Dan mampu melakukan perhitungan sampai
1 juta instruksi per detik.
 Super Komputer, adalah sebuah computer yang memimpin didunia dalam kapasitas
proses, terutama kecepatan perhitungan, pada awal pengenalannya. Di kenalkan pada
tahun 1960an, didesain oleh Seymour Cray di Control data Corporation (CDC),
memimpin dipasaran pada tahun1970an sampai cray berhenti untuk membentuk
perusahaannya sendiri, Cray Research. Digunakan untuk prakiraan cuaca, riset iklim,
simulasi fisik.

1.5. Peranan Teknologi Informasi
A. TI dalam Dunia Perbankan
Pihak bank menyedian layanan yang memudahkan nasabah seperti :
 ATM (Automatic Teller Machine), memudahkan nasabah dalam melakukan
transaksi tanpa harus tergantung oleh jam kerja bank.
 Layanan transaksi menggunakan telepon, seperti memeriksa saldo
 Layanan transaksi menggunakan internet, mentransfer uang dimana saja dan kapan
saja.
B. TI dalam Dunia Pendidikan
Sistem pengajaran dengan berbasis multimedia ( teknologi yang melibatkan teks, gambar,
suara dan video) dapat menjadikan masalah menjadi menarik, tidak monoton dan
memudahkan penyampaian isi materi. Sudah banyak sekali software yang tergolong
sebagai edutaiment yang merupakan perpaduan antara education (pendidikan) dan
entertainment (hiburan).
C. TI dalam Dunia Medis
TI juga diterapkan pada peralatan medis, misalnya CT-scan. Dan juga untuk menangani
transaksi yang berhubungan dengan karyawan, juru medis, dan pasien. Seperti contoh
misalnya system informasi digunakan untuk mencatat rekaman medis pasien secara
elektronis.
D. TI dalam Dunia Kepolisian.
Sistem Informasi yang digunakan oleh Kepolisian adalah untuk pembuatan SIM,
teknologi kompresi gambar yang memungkinan sidik jari dapat tersimpan secara
elektronis,
E. TI dalam Dunia Pedagangan Elektronik
e-commerce merupakan model perdagangan yang lahir berkat kemajuan Internet.
Organisasi bisnis dapat menyediakan situs web untuk mempromosikan produk atau jasa
yang ditawarkan dan memberikan fasilitas untuk melakukan transaksi.
F. TI untuk Perancangan Produk
Merancang produk dengan teknologi informasi merupakan sesuatu yang telah umum
dilakukan, misalnya pembuatan mobil atau pesawat menggunakan software CATIA. Dan
melakukan perancangan yang lain tanpa harus menggunakan kertas.