Translate buku Tugas Kriptografi

Nama : Adrian Julian Pratama
Nim    :17.01.071.006
MK     :KRIFTOGRAFI
Prodi  : Teknik Informatika
http://www.uts.ac.id


12.5 Skema Tanda Tangan Lamport Sekali Pakai
Meskipun definisi 12.2 adalah definisi standar keamanan untuk digital skema tanda tangan, definisi yang lebih lemah juga telah dipertimbangkan. Skema tanda tangan yang memenuhi definisi-definisi yang lebih lemah ini mungkin tepat untuk tertentu aplikasi terbatas, dan juga dapat berfungsi sebagai \ blok bangunan "berguna untuk skema tanda tangan memuaskan definisi keamanan yang lebih kuat.
Di bagian ini, kami mendefinisikan skema tanda tangan satu kali yang, secara informal, adalah \ secure "selama mereka digunakan untuk menandatangani hanya satu pesan. Kami kemudian menunjukkan konstruksi, karena Lamport, skema tanda tangan satu kali dari siapa pun fungsi satu arah. (Di bagian ini, kami hanya mengandalkan definisi satu arah fungsi yang diberikan dalam Bagian 7.4.1, dan tidak memerlukan bahan apa pun yang dikembangkan dalam Bab 6.) Kami akan menggunakan skema tanda tangan satu kali di bagian berikut untuk membangun skema tanda tangan yang memuaskan Definisi 12.2.


(Ingat ini berarti, secara informal, bahwa f mudah untuk dihitung tetapi sulit untuk dibalik; lihat Definisi 7.66.) Kunci publik akan terdiri dari 2 3 = 6 elemen y1; 0, y1; 1, y2; 0, y2; 1, y3; 0, y3; 1 dalam kisaran f; kunci pribadi akan berisi pra-gambar yang sesuai x1; 0, x1; 1, x2; 0, x2; 1, x3; 0, x3; 1 di bawah f. Kunci-kunci ini dapat divisualisasikan sebagai array dua dimensi:


12.6 Tanda tangan dari Hashing Tahan Tabrakan
Kami belum melihat skema tanda tangan yang secara eksistensial tidak dapat dikalahkan di bawah serangan pesan pilihan adaptif (lih. Definisi 12.2). Disini kita menunjukkan konstruksi yang relatif tidak efisien yang pada dasarnya yang paling sederhana dikenal berdasarkan asumsi kriptografi yang telah kami perkenalkan sejauh ini. Konstruksi hanya bergantung pada keberadaan fungsi hash yang tahan benturan, dan terutama berfungsi sebagai bukti kelayakan untuk merealisasikan definisi 12.2.
Kami berkomentar bahwa skema tanda tangan yang memenuhi definisi 12.2 adalah, secara umum, cukup sulit untuk dibangun, dan bahkan hari ini hanya beberapa skema yang efisien dapat dibuktikan memuaskan definisi ini diketahui. Dalam Bab 13, kita akan membahas skema tanda tangan yang sangat efisien yang dapat dibuktikan aman dalam suatu hal Model "ideal" yang diperkenalkan dan dibahas secara luas di sana tetap terbuka untuk mengembangkan skema tanda tangan efisien lainnya yang dapat dibuktikan aman dalam model \ standard "yang telah kami gunakan sampai sekarang.



Kami membangun konstruksi akhir kami secara bertahap. Dalam Bagian 12.6.1 kita mendefinisikan gagasan skema tanda tangan stateful, dan menunjukkan bagaimana membangun stateful skema tanda tangan yang memenuhi definisi 12.2. Dalam Bagian 12.6.2 kita membahas a varian skema ini yang lebih efisien (yang masih jelas) dan menunjukkan bahwa ini, juga, secara eksistensial tidak dapat dikalahkan di bawah serangan pesan pilihan yang adaptif. Kita kemudian jelaskan bagaimana konstruksi ini dapat dibuat tanpa kewarganegaraan, untuk memulihkan a skema tanda tangan seperti aslinya didefinisikan.

12.6.1 Tanda Tangan Berbasis Rantai
Kami pertama-tama menggunakan skema tanda tangan yang memungkinkan penandatangan mempertahankan beberapa nyatakan bahwa diperbarui setelah setiap tanda tangan diproduksi.
DEFINISI 12.10 Skema tanda tangan stateful adalah tuple dari probabilistic algoritma polinomial-waktu (Gen; Masuk; Vrfy) memenuhi berikut ini:
Algoritma generasi kunci mengambil sebagai input parameter keamanan 1n dan output (pk,sk,s0). Ini disebut kunci publik, kunci pribadi, dan keadaan awal, masing-masing. Kami berasumsi pk ≥ n, dan n itu bisa ditentukan dari pk.
Algoritma penandatanganan Sign mengambil sebagai input sk kunci pribadi, nilai si􀀀1,dan pesan m. Ini menghasilkan tanda tangan bersama dengan nilai si, dan kami menulis ini sebagai (; si) Signsk; si􀀀1 (m).
Algoritma verifikasi deterministik Vrfy mengambil sebagai input kunci public pk, pesan m, dan tanda tangan. Ini menghasilkan sedikit b, dan kami menulis ini sebagai b: = Vrfypk (m;).

Kami menekankan bahwa negara tidak perlu memverifikasi tanda tangan. Tanda tanganskema yang tidak mempertahankan negara kadang-kadang disebut stateless to membedakannya dari skema stateful. Keberadaan unforgeability di bawah serangan pesan pilihan adaptif untuk kasus skema tanda tangan negara didefinisikan dengan cara yang persis analog untuk definisi 12.2, dengan satu-satunya seluk beluk adalah bahwa penandatanganan oracle saja





12.6.2 Tanda Tangan Berbasis Pohon
Penanda tangan dalam skema berbasis rantai pada bagian sebelumnya dapat dilihat sebagai memelihara pohon (berakar pada kunci publik pk1) tingkat 1 dan kedalaman sama dengan jumlah pesan yang ditandatangani sejauh ini (lih. Gambar ??). Alami cara untuk meningkatkan efisiensi dari pendekatan ini adalah dengan menggunakan pohon biner di mana setiap node memiliki derajat 2. Seperti sebelumnya, tanda tangan akan sesuai dengan yang disertifikasi " jalan di pohon dari daun ke akar; perhatikan bahwa selama pohon itu memilikinya kedalaman polinomial (bahkan jika memiliki ukuran eksponensial!), verifikasi masih bisa dilakukan dalam waktu polinomial.
Secara konkret, untuk menandatangani pesan dengan panjang n kita akan bekerja dengan pohon kedalaman n memiliki 2n daun. Seperti sebelumnya, penanda tangan akan menambahkan node ke pohon \ pada y, " sesuai kebutuhan. Berbeda dengan skema berbasis rantai, hanya menyisakan (dan bukan internal nodes) akan digunakan untuk mengesahkan pesan. Setiap daun pohon akan sesuai dengan salah satu pesan panjang yang mungkin n.

12.7 Sertifikat dan Infrastruktur Kunci Publik
Kami menyimpulkan bab ini dengan diskusi singkat tentang salah satu aplikasi utama tanda tangan digital: distribusi aman kunci publik. Ini membawa kita lingkaran penuh dalam diskusi kita tentang kriptografi kunci publik: dalam hal ini dan tiga bab sebelumnya kita telah tampak bagaimana menggunakan kriptografi kunci public begitu kunci publik didistribusikan secara aman; sekarang kami menunjukkan bagaimana kunci public kriptografi itu sendiri dapat digunakan untuk mendistribusikan kunci publik secara aman. Ini mungkin terdengar melingkar, tetapi tidak karena pada dasarnya apa yang akan kami tunjukkan adalah sekali kunci publik tunggal (milik pihak tepercaya) didistribusikan secara aman mode, kunci ini dapat digunakan untuk \ boot - strap "distribusi aman dari sewenang-wenang-banyak kunci publik lainnya. Dengan demikian, masalah kunci publik aman distribusi kunci hanya perlu dipecahkan satu kali (secara teori, setidaknya).
Ide kuncinya adalah gagasan tentang sertiikat, yang hanya mengikat tanda tangan beberapa entitas ke kunci publik. Untuk menjadi nyata, katakanlah pesta Charlie menghasilkan sepasang kunci (pkC; skC) untuk skema tanda tangan digital yang aman (dalam hal ini bagian, kami hanya akan peduli dengan skema tanda tangan yang memuaskan Definisi 12.2). Asumsikan lebih jauh bahwa Bob juga telah membuat pesta pasangan-kunci (pkB; skB) (dalam diskusi ini, ini mungkin merupakan kunci untuk a skema tanda tangan atau skema enkripsi kunci publik), dan yang diketahui Charlie pkB itu adalah kunci publik Bob. Kemudian Charlie dapat menghitung tanda tangan.

dan berikan tanda tangan ini kepada Bob. Sertifikat tanda tangan ini! B disebut sertifikat untuk kunci Bob yang dikeluarkan oleh Charlie. Kami berkomentar bahwa dalam praktiknya sertifikat harus secara jelas mengidentifikasi partai yang memegang kunci publik tertentu dan jadi istilah yang lebih deskriptif daripada \ Bob "akan digunakan, misalnya, Bob alamat email