Memulai dengan Sistem Kripto SRVB

pengantar

Keamanan informasi adalah bidang pengetahuan yang menarik yang dapat melibatkan apa saja mulai dari ilmu komputer teoretis hingga rekayasa perangkat lunak, dan bahkan mengamati psikologi kesalahan manusia.

Kriptografi sekarang menjadi salah satu dari banyak pahlawan teknologi anonim dalam kehidupan kita sehari-hari. Jejaring sosial, perbankan web, intelijen militer, dan sistem informasi lainnya yang berhubungan dengan informasi sensitif semuanya sangat bergantung pada kriptografi. Kriptografi memungkinkan kita memiliki privasi, yang oleh sebagian orang dianggap sebagai hak asasi manusia ke-12.

Artikel ini akan memberi Anda pengenalan tentang prinsip-prinsip di balik kriptosistem kunci publik dan memperkenalkan Anda pada Santana Rocha-Villas Boas (SRVB), sebuah kriptosistem yang dikembangkan oleh penulis artikel dan Prof. Daniel Santana Rocha. Pada saat penulisan, penulis algoritme sedang menyiapkan kampanye yang menyertakan hadiah finansial bagi siapa saja yang berhasil memecahkan kode. Karena artikel ini akan membahas fungsionalitas algoritme secara terperinci, ini adalah tempat terbaik untuk memulai pengejaran hadiah. Informasi lebih lanjut tersedia di situs SRVB.

Apa Itu Kriptosistem?

Kriptografi adalah metode apa pun untuk menghambat penafsiran pesan, sementara masih memungkinkan cara untuk menafsirkannya secara layak selama instruksi khusus disediakan, yang biasanya disebut "kunci." Meskipun ini adalah definisi yang sangat luas yang mencakup bahkan teknik paling awal, perlu disebutkan bahwa ini tidak mencakup semua yang ada untuk keamanan informasi.

Perlombaan teknologi antara metode enkripsi dan cara untuk memecahkannya diperkirakan tidak akan pernah memiliki pemenang yang pasti. Setiap generasi baru diharapkan untuk meningkatkan standar keamanan informasi dan kriptanalisis, yang merupakan seperangkat teknik untuk menguraikan/memecah pesan terenkripsi secara sistematis, yaitu, melewati keamanan atau enkripsi.

Agar kriptosistem (teknik kriptografi tertentu) dianggap aman oleh penggunanya, ia harus mendapat persetujuan dari komunitas pakar internasional, dan dengan demikian diketahui publik, yang dikenal sebagai prinsip Kerckhoffs. Namun, kondisi ini membuat sistem menjadi sorotan dari komunitas kriptanalisis dunia, yang akan mencoba menemukan cara untuk memecahkan enkripsi secara sistematis.

Bagaimana seseorang dapat membuat proses enkripsi yang diberikan cukup rahasia sehingga hanya agen yang dituju yang dapat mendekripsinya, sementara pada saat yang sama cukup publik sehingga komunitas kriptanalisis dunia dapat membuktikan kekokohannya? Jawabannya adalah komponen yang merupakan elemen kunci Kriptologi: kuncinya. Kunci dari sistem kriptografi adalah parameter untuk algoritma enkripsi atau dekripsi, atau keduanya. Dengan menjaga kerahasiaan parameter, daripada keluarga algoritme, kedua persyaratan yang kontradiktif dapat dicapai. Asalkan keluarga parameter cukup besar (mungkin tak terbatas) dan masing-masing komponennya dapat dibuktikan memiliki properti yang memadai, penyerang tidak mungkin menentukan parameter hanya dengan inspeksi.

Terakhir, agar kunci dapat bekerja secara efektif, kunci tersebut harus mudah dibuat tetapi hampir tidak mungkin untuk ditebak. Dengan kekuatan komputasi komputer saat ini, komputer akan membutuhkan lebih sedikit waktu untuk menguraikan kunci yang dibuat manusia daripada yang perlu dibayangkan oleh manusia mana pun, di atas fakta bahwa menghasilkan kunci dengan cara itu juga tidak hemat biaya. Karena itu, kunci cenderung dihasilkan oleh suatu algoritma.

Algoritme pembangkit kunci tidak boleh membuat keluaran yang dapat diprediksi/direproduksi sebagai hasil dari penggunaan biasa. Sejak algoritma melakukan prosedur tanpa proses cerdas untuk itu, pertanyaannya menjadi bagaimana hal ini dapat dilakukan. Jawabannya adalah mengubah algoritme penghasil kunci menjadi peta yang mengubah sejumlah besar bit yang benar-benar acak menjadi kunci. Bit yang benar-benar acak dapat diperoleh dari sistem operasi, yang menghasilkannya dari ketidakpastian di alam semesta. Beberapa sumber akan menjadi gerakan mouse Anda, latensi paket jaringan, atau bahkan perangkat keras khusus, tergantung pada aplikasinya.

Kriptosistem Kunci Publik

Bersiaplah untuk terkejut lagi, karena sekarang kami akan memperkenalkan sebuah konsep yang tampaknya bertentangan dengan apa yang baru saja kami katakan: kunci publik.

Sejauh ini, kita telah melihat penciptaan komunikasi yang aman setelah parameter rahasia (kunci) telah dipertukarkan dengan aman, tetapi masalah pertukaran parameter melalui saluran publik tetap ada. Saat ini, kami akan memperkenalkan konsep yang memecahkan masalah yang sedikit lebih gamblang: pembuatan saluran yang aman.

Misalkan Alice bekerja dengan Bob, dan mereka ingin menjaga interaksi kerja mereka tetap aman menggunakan enkripsi. Mereka dapat bertemu dan bertukar kunci enkripsi dengan saling memberikan USB flash drive dengan kunci mereka. Namun bagaimana jika Alice dan Bob berada di benua yang berbeda. Bagaimana cara membuat saluran aman di mana tidak ada saluran yang ada?

Mengirim kunci melalui email tidak akan menjadi pilihan, karena pesaing mereka Eve dapat mencegat pertukaran dan menggunakan kunci mereka untuk membaca semua data terenkripsi sesudahnya. Jika mereka memiliki saluran digital lain di mana mereka dapat mengirimkan data sensitif ini, maka mereka tidak memerlukan enkripsi, dan dengan demikian kunci, di tempat pertama. Mengirim kunci melalui surat fisik juga masih dapat disadap, karena itu memerlukan pertukaran informasi sensitif untuk memulai. Mengirim kunci steganografi dengan bersembunyi di dalam data lain akan menjadi pintar, tetapi tidak berguna kecuali pengirim yakin bahwa penerima, dan penerima saja, menyadari keberadaan pesan semacam itu dan tahu bagaimana mengekstraknya. Seperti yang terjadi, kesadaran akan keberadaan pesan bersama dengan deskripsi tentang cara mengekstrak kunci dari data adalah jenis kunci itu sendiri, yang membawa kita kembali ke titik awal.

Solusinya adalah merancang sistem kriptografi yang parameter enkripsinya tidak cukup untuk menafsirkan pesan asli secara layak ^[1] , dan menyimpan sendiri parameter yang memungkinkan penafsiran pesan. Kami menyebut parameter itu sebagai kunci pribadi. Berdasarkan kunci pribadi, seseorang dapat secara layak menghasilkan satu set parameter untuk alat enkripsi tanpa membuat parameter baru itu sendiri dapat mengungkapkan apa itu kunci pribadi. Kumpulan parameter tersebut dapat dibagikan secara publik, karena tidak terlalu penting siapa yang dapat mengenkripsi sesuatu, selama hanya satu orang yang dapat mendekripsinya. Karena set parameter untuk alat enkripsi ini dapat dipublikasikan, ini disebut kunci publik.

Kriptografi di mana kunci enkripsi dan dekripsi berbeda, dan yang pertama tidak dapat digunakan untuk menyimpulkan yang terakhir, disebut kriptografi asimetris, sedangkan kriptografi simetris adalah apa yang kita miliki ketika kunci-kunci itu sama, atau mudah disimpulkan satu sama lain.

Alice mengirimkan kunci publiknya kepada Bob, yang hanya dapat digunakan untuk mengenkripsi hal-hal yang hanya dapat dia dekripsi (dengan kunci pribadinya, yang dia simpan secara pribadi) dan, sebaliknya, Bob mengirimkan kunci publiknya kepada Alice, yang hanya dapat digunakan untuk mengenkripsi sesuatu. bahwa dia sendiri yang dapat mendekripsi (melalui kunci pribadinya, yang juga dia simpan secara pribadi). Tetapi bagaimana mungkin seseorang dapat mempublikasikan parameter untuk algoritma enkripsi yang darinya seseorang tidak dapat menyimpulkan algoritma kebalikan yang tepat?

Jawabannya terletak pada bidang matematika yang paling dekat hubungannya dengan pemrograman, yaitu teori kompleksitas komputasional. Siapapun yang telah mempelajari masalah matematika cukup dalam telah mendengar tentang transformasi yang mudah dilakukan dengan satu cara, tetapi sulit untuk melakukan kebalikannya. Dalam kalkulus, misalnya, menemukan turunan buku teks biasanya adalah latihan langsung, sementara melakukan kebalikannya (seperti memecahkan integral yang sedikit tidak sepele atau ODE atau PDE fisik buku teks, misalnya) memerlukan proses yang lebih investigasi dari hipotesis pertama keluarga fungsi yang dijamin (atau setidaknya masuk akal) untuk memuat solusi dan memecahkan masalah terbalik untuk menemukan solusi dari keluarga ini.

Contoh yang sebenarnya digunakan dalam kriptosistem RSA adalah mengalikan bilangan prima besar versus memfaktorkan produk yang dihasilkan tanpa mengetahui faktornya. Melakukan perkalian adalah hal yang sepele, tetapi pemfaktoran mengharuskan Anda untuk secara acak ^[2] menebak faktor prima, yang memiliki ratusan digit. Sebuah properti penting dari operasi adalah kebutuhan untuk itu untuk skala yang baik. Menambahkan beberapa digit pada ukuran bilangan prima di RSA akan menghasilkan kunci yang membutuhkan ribuan kali lebih banyak operasi untuk dipecahkan sambil menambahkan sedikit peningkatan kompleksitas pada proses enkripsi. Secara kasar, produk bilangan prima digunakan untuk enkripsi, sedangkan pasangan faktor prima digunakan untuk mendekripsi.

Dengan mengingat semua ini, mari kita lihat bagaimana sistem kriptografi SRVB bekerja.

Algoritma yang Mendasari - Melihat ke SRVB

Soal Jumlah Subset

Seperti kriptosistem kunci publik lainnya, SRVB bergantung pada kesulitan memecahkan masalah tertentu yang mudah dibuat. Dalam kasus SRVB, ini adalah masalah jumlah subset, yang dapat dijelaskan sebagai berikut:

Diketahui bilangan bulat $w$ dan $v_1, \cdot \cdot \cdot, v_N \in Z$ cari barisan $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, sehingga $ \sum_ {i = 1}^{N} v_i b_i = w $.

Jelas, masalah ini dapat dihasilkan dengan memilih N bilangan bulat secara acak, secara acak memilih subset dari mereka dan menjumlahkan subset ini - yang sepele.

Pencarian brute-force akan memiliki kompleksitas $ O( N * 2^N ) $, menghitung untuk setiap kombinasi nilai dari $b$s. Pendekatan yang lebih efisien diberikan oleh Horowitz dan Sahni pada tahun 1972, dengan kompleksitas $O ( N * 2 ^ {N / 2} ) $. Masalahnya setidaknya sama sulitnya jika kita mengganti $b$s dan $w$ dengan vektor bilangan bulat berdimensi $k$. Akan tetapi, bidang di mana masalah yang lebih sulit ini harus diselesaikan, juga harus memiliki isomorfisme dengan cincin di mana versi yang lebih mudah dari masalah yang sama terjadi, seperti yang akan kita lihat di bawah. Untuk alasan ini, SRVB mengeksploitasi masalah jumlah subset dalam bilangan bulat Gaussian, di mana $ k = 2 $.

Ada kasus khusus di mana masalah ini menjadi mudah dihitung melalui penggunaan algoritma serakah. Jika kita mengurutkan faktor penskalaan barisan $v_1, \cdot \cdot \cdot, v_N $ di mana setiap bilangan bulat dalam barisan tersebut lebih besar dari jumlah semua bilangan bulat yang datang sebelumnya ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), seseorang dapat menggunakan pendekatan serakah untuk menemukan barisan b dalam waktu linier. Sebuah barisan dengan sifat-sifat yang dijelaskan disebut barisan superincreasing .

Berikut adalah deskripsi sederhana dari solusi serakah untuk kasus ini:

1. Mulailah dengan $ i = N $, faktor yang diamati saat ini, dan $ w' = w $, sisa $w$

2. Jika faktor penskalaan saat ini terlalu besar untuk dimasukkan ke dalam sisa $w$, artinya $v_i > w'$, atur $b_i = 0$ dan lanjutkan ke langkah berikutnya. Jika tidak, kita tahu bahwa faktor penskalaan harus dalam urutan (karena faktor lainnya lebih kecil dari $v_i$) dan kita menetapkan $b_i = 1$.

3. $ w' \Panah kiri w' - v_i * b_i$, $i \Panah kiri i - 1$. Jika $i > 0$, kembali ke langkah 2.

4. Verifikasi bahwa, sekarang, $w' == 0$, jika tidak, masalahnya rusak

Ini berhasil karena kita tahu bahwa semua pengganda yang lebih kecil dari yang diamati saat ini tidak dapat secara kolektif menutupi (sub)jumlah $ w' $ sebanyak yang dapat dilakukan oleh pengganda saat ini. Jadi, jika jumlah sisa lebih besar dari faktor saat ini, kita tahu pasti bahwa semua faktor berikut bersama-sama akan gagal menjumlahkannya tanpa bantuan faktor saat ini. Di sisi lain, karena semua pengganda adalah positif, jika faktor sekarang $ v_i $ lebih besar dari jumlah sisa $ w' $, menambahkan faktor lain akan membuat hasilnya melampaui $ w' $ bahkan lebih.

Mari kita membuat notasi untuk sisa artikel. Kami memilih $v_1, \cdot \cdot \cdot, v_n $ dan $w$ sebagai faktor dan jumlah dari barisan superincreasing, sedangkan $ u_1, \cdot \cdot \cdot, u_n $ dan $y$ akan menjadi publik tersedia parameter yang disediakan untuk memulihkan $ b_1, \cdot \cdot \cdot, b_n $.

Dengan urutan $ u_1, \cdot \cdot \cdot, u_n $ dipilih sehingga tidak bertambah besar, dan nomor $y$ tersedia untuk umum, tidak cukup informasi yang disediakan untuk umum untuk memulihkan urutan $ b_1, \cdot \cdot \cdot , b_n $. Namun, jika ada barisan superkenaikan $ v_1, \cdot \cdot \cdot, v_n $ yang dapat menggantikan barisan $ u_1, \cdot \cdot \cdot, u_n $, seseorang dapat menggunakan barisan ini untuk menyelesaikan masalah dengan pendekatan serakah.

Di bawah ini kami akan menunjukkan cara kerjanya.

Penggunaan Jumlah Subset dalam Cryptosystem Sebelumnya

Pada tahun 1978, Ralph Merkle dan Martin Helman, menemukan cara untuk mengeksploitasi kedua paradigma knapsack dan linearitas operasi modulus untuk membangun hubungan antara dua urutan yang dijelaskan di bagian sebelumnya - sehingga menghasilkan Kriptosistem Kunci Publik. Idenya adalah untuk mengubah ransel mudah (yang terdiri dari vektor bilangan bulat yang bertambah besar) menjadi yang sulit (yang tidak memiliki properti ini) melalui operasi linier (modulus) dengan operan rahasia. Transformasi terdiri dari mengalikan setiap $v_i$ dengan $\theta$ dan mengambil sisa dari produk ini dengan $\alpha$, di mana $\alpha \gt \sum_{i=1}^N v_i$ dan $\gcd (\alpha, \theta) = 1$ (dua batasan yang akan segera dibenarkan). Hasilnya, barisan $u_1, \ldots, u_N$, tidak bertambah lagi, dan dapat dianggap sebagai hard knapsack .

Permutasi acak dari urutan $u_1, \ldots, u_N$ akan diberikan kepada pihak yang ingin mengenkripsi dan mengirim pesan kepada kami. Permutasi dilakukan agar pihak ketiga lebih sulit menebak urutan superincreasing aslinya. Blok bit pesan digunakan sebagai koefisien $b_1, \ldots, b_N$. Enkripsi dilakukan dengan mengalikan urutan kunci dengan urutan koefisien ini, dan menjumlahkan perkalian menjadi hasil, yang akan kita beri label $y$. Hanya pemilik kunci pribadi yang dapat mengubah $y$ menjadi $w$ yang sesuai yang akan diperoleh jika blok $b_1, \ldots, b_N$ yang sama ini akan dikalikan dengan bilangan bulat mudah (urutan $v_1, \ldots , v_N$). Itu dilakukan dengan cara mengalikan $y$ dengan $\theta^{-1}$, invers perkalian dari $\theta$ modulus $\alpha$ (yang keberadaannya bergantung pada kondisi $\gcd(\alpha, \ theta) = $1). Dengan kata lain, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Setelah itu, kita hitung $w = (y * \theta^{-1}) \bmod a$. Alasan ini dijamin untuk bekerja adalah linearitas modulus , yaitu, bahwa kombinasi linier dari sisa sama dengan sisa kombinasi linier.

Jika kita secara berurutan menerapkan definisi $u$, ring hasil bagi, dan properti linearitas dari operator modulus, kita melihat korespondensi:

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ kiri[ \sum_{i=1}^N b_i * v_i \kanan] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

Dan dengan demikian jumlah mudah $w$ dapat diperoleh kembali dengan mengalikan kedua ruas dengan $\theta^{-1}$ dan mengambil modulus dengan $\alpha$. Untuk melakukannya, seseorang harus mengetahui $\alpha$ dan $\theta$ (yang memungkinkan seseorang untuk dengan mudah menghitung $\theta^{-1}$), yang harus dijaga kerahasiaannya sebagai bagian dari kunci pribadi.

Satu kendala tunggal, $\alpha \gt \sum_{i=1}^N v_i$, dibiarkan tidak dibenarkan dan inilah penjelasannya: Persamaan antara baris kedua dan ketiga terdiri dari kesetaraan antara kelas residu dari hasil bagi cincin bilangan bulat modulo $\alpha$. Dengan kata lain, itu hanya menyatakan kesetaraan sisa anggota ketika dibagi dengan $\alpha$, yang bukan merupakan kondisi yang cukup untuk kesetaraan anggota itu sendiri . Akibatnya, lebih dari satu vektor dengan nilai $b$ dapat dipetakan menjadi satu $y$, yang dicegah dengan membatasi subsum maksimum yang mungkin (yaitu jumlah semua paket $v_i$) $w_{max}$ menjadi lebih kecil dari $\alpha$ untuk setiap kombinasi nilai $b$.

Sama seperti contoh kehidupan sehari-hari lainnya, pengetahuan lengkap tentang semua hipotesis seringkali tidak mungkin dan tidak pernah mudah. Akibatnya, kita harus mengandalkan intuisi matematis saat menilai apakah sistem kripto aman untuk digunakan, yang tidak memberikan jaminan nyata kepada kita. Enam tahun setelah pembuatannya, kriptosistem MH rusak dengan serangan oleh A. Shamir. Ada beberapa upaya lagi untuk menghidupkan kembali MH, banyak di antaranya juga gagal.

The Santana Rocha - Sistem Kripto Villas Boas (SRVB)

Pada tahun 2016, setelah beberapa kali bertukar pikiran dengan penulis artikel ⁱⁿⁱ tentang kemungkinan terinspirasi yang berbeda dari sebuah sistem kripto, Daniel Santana Rocha memiliki ide untuk mengganti $\theta$ dan $\alpha$ dengan Gaussian Integers. Untuk alasan yang lebih teknis, pendekatan ini mengarah pada perlawanan terhadap serangan Shamir yang disebutkan di atas.

Dia juga menyusun blok bit yang terdiri dari banyak langkah dari kombinasi linier yang dijelaskan sebelumnya dari ransel keras . Di masing-masing dari mereka, bilangan bulat (Gaussian) baru, setara dengan satu, lebih tinggi dari jumlah semua sebelumnya akan ditambahkan di akhir urutan, sedangkan yang terkecil saat ini akan dibuang.

Batasan analog yang berbeda namun elegan berlaku untuk $\alpha$, yang sekarang merupakan bilangan bulat Gaussian. Kami membutuhkan $w_{max} \leq \vert\alpha\vert^2$. Alasannya sangat sulit untuk diformalkan, tetapi untungnya dapat dengan mudah diilustrasikan dari deskripsi yang elegan:

Bayangkan sebuah kisi persegi pada bidang bilangan kompleks, yang sisinya merupakan sisi miring dari segitiga siku-siku catheti a dan b, sejajar dengan sumbu nyata dan imajiner. Contoh kisi tersebut diberikan di bawah ini. Bilangan bulat guassian modulo $\alpha = a + bi$ dapat diwakili oleh titik-titik yang terletak di dalam kisi tersebut. Dalam kisi seperti itu ada $\vert\alpha\vert^2$ titik yang berbeda. Jika kita memilih $\alpha$ yang cukup besar, kita dapat memasukkan semua kombinasi linear dari easy knapsack.

Ini adalah representasi grafis dari isomorfisme $f : Z/n \rightarrow Z[i]/(\alpha)$, di mana $n = 13$ dan $\alpha = a + bi = 3 + 2i$ (perhatikan bahwa $ n$ dan $\alpha$ memang memuaskan $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ sesuai kebutuhan). Titik-titik mewakili bilangan bulat Gaussian, yaitu bilangan kompleks $a + bi$, di mana $a$ dan $b$ adalah bilangan bulat. Seperti biasa, sumbu horizontal mewakili bagian nyata, sedangkan vertikal mewakili bagian imajiner. Jadi, memindahkan satu titik ke kanan atau kiri sama dengan menambahkan +1 atau -1 ke nilai saat ini, masing-masing. Demikian juga, memindahkan satu titik ke atas atau ke bawah sesuai dengan penambahan +i atau -i, masing-masing.

Titik-titik merah setara dengan $0 \bmod(\alpha)$. Selain itu, kami juga mewarnai 4 pasang titik lagi.

Isomorfisme $f$ didefinisikan oleh transformasi elemen ke $i$ dari barisan siklik $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ ke dalam elemen $i$ dari deret juga siklik dari titik-titik pada gambar, yang mengikuti aturan berikut:

1. Itu dimulai dari titik merah baris pertama;
2. Ini mengikuti panah kanan horizontal; kecuali itu
3. Saat mengikuti panah memimpin urutan di luar kisi, itu akan mencapai salah satu titik non-hitam. Alih-alih pergi ke titik itu, ia melompat ke titik berwarna yang sama (yaitu, titik ekivalen modulo $\alpha$) di dalam kotak yang sama; dan akhirnya
4. Ketika titik non-hitam ini kebetulan berwarna merah (yang terjadi setelah semua warna lain dilewati), urutannya melompat ke titik merah paling atas, sehingga memulai kembali siklus;

Untuk memetakan setidaknya $Y$ bilangan bulat alami, seseorang harus mengambil persegi dengan luas $\vert\alpha\vert^2$ (di mana $\vert\alpha\vert = \sqrt{a^2 + b^2} $ adalah, menurut teorema Pythagoras, ukuran sisinya) setidaknya sama tingginya.

Perhatikan bahwa setiap “lompatan” mengubah nomor baris $r$ menjadi $r \leftarrow (r + b)(mod a + b)$ jika seseorang menghitung baris dari atas ke bawah, dan, secara ekuivalen, menjadi $r \leftarrow (r + a)(mod a + b)$ jika dihitung dari bawah ke atas. Oleh karena itu, syarat perlu dan cukup untuk setiap baris (dan titik) untuk dijelajahi tepat satu kali pada setiap siklus adalah bahwa ukuran lompatan sama dengan jumlah baris, atau, dengan kata lain, $gcd(a,a + b) = gcd(b,a + b) = 1$. Karena sifat-sifat operator pembagi persekutuan terbesar, keduanya ekuivalen dengan $gcd(a,b) = 1$.

YS Villas Boas memperhatikan perlunya koprimalitas $a$ dan $b$. Untuk mempertahankan superincreasingness, setiap bilangan bulat baru $w$ yang ditambahkan di akhir urutan harus melampaui jumlah semua bilangan bulat saat ini ($w > \sum_{i=1}^k v_i$). Dia mengamati bahwa untuk mencapai ini, koefisien perkaliannya $b_i$ harus setidaknya 1, dan dengan demikian, setiap bit tidak dapat dipetakan ke dalam koefisien 0 dan 1. Jika koefisiennya 0 dan 1, hanya blok hanya terdiri dari yang akan memenuhi superincreasingness. Untuk alasan ini, bit 0 dan 1 kemudian dipetakan masing-masing ke koefisien perkalian 1 dan 2.

Akhirnya, dan yang lebih sepele: selama setiap langkah decoding, satu bilangan bulat baru $v_1$ akan ditemukan sebagai solusi dari persamaan $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$, di mana semua $v_i$ dan $b_i$ diketahui $1 < i \leq n$. Karena kita juga tidak mengetahui $b_1$, kita mendapatkan sistem dengan satu persamaan dan dua variabel, yang memberikan kita satu derajat kebebasan. Untuk memperbaiki ini, kita harus menengahi satu nilai positif (demi kesederhanaan, 1) untuk selalu ditetapkan ke $b_1$, sehingga menghilangkan ambiguitas. Jadi, karena koefisien pertama ditetapkan ke 1, untuk mengkodekan $n$ bit pada setiap langkah, barisan bilangan bulat kita harus terdiri dari elemen $n + 1$.

Satu teknis terakhir yang harus diselesaikan adalah kasus di mana ukuran dalam byte pesan bukan kelipatan dari ukuran blok. Dengan kata lain, apa yang harus dilakukan dengan kemungkinan byte yang tersisa dari blok data terakhir sehingga, setelah blok data dipulihkan, semua byte dari konten asli dipertahankan, tetapi tidak lebih dari itu? Kami memecahkannya dengan mengulangi byte terakhir dari pesan satu kali. Salinan ini, kemudian, diikuti oleh urutan acak di mana setiap komponen hanya perlu berbeda dari yang sebelumnya. Jadi, ketika blok data diambil, blok terakhir atau, dalam kasus terburuk, blok sebelum yang terakhir terpotong dalam pengulangan byte terakhir. ^[4]

Sekarang mari kita tunjukkan contoh sistem kriptografi SRVB.

Kami mulai dengan parameter:

$k = 4$;

$m = 4$;

yang menghasilkan panjang blok $l = 4 * 4 = 16$, dan barisan superkenaikan $k + 1 = 5$ bilangan bulat alami, yang dioperasikan— yaitu, gabungan linier, ditambahkan dengan hasil kombinasi linier ini, dan dikurangi menjadi elemen $k + 1$ terakhir —$m = 4$ kali;

Untuk mempermudah, biarkan berikut ini menjadi vektor (superincreasing) dari $v_i$:

$(1,2,4,8,16)$

Memang, urutan dari lima pangkat pertama dari 2, hanya karena ini adalah urutan yang meningkat dengan lima elemen dan nilai-nilai positif terkecil yang mungkin (sehingga menghindari 0 di kunci publik, yang secara sepele akan memberikan koresponden 0 dari mitranya ).

Seperti yang kami katakan sebelumnya, untuk $\alpha = a + bi$, bilangan bulat $a$ dan $b$ harus coprime, dan menurut batasan baru yang kami sebutkan, kami harus meminta $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Perhitungan cepat menghasilkan $W = 1590$. Karena $\sqrt{1590} \simeq 39.8$, $\alpha$ yang sangat cocok untuk dipilih adalah $\alpha = 39 + 40i$, karena cukup besar untuk mengakomodasi isomorfisme dengan ring bilangan bulat dengan at setidaknya 1590 komponen, sementara juga memenuhi $gcd(a,b)=1$. Juga, kita perlu memilih $\theta$ sedemikian rupa sehingga $gcd(a,\theta)=1$ ^[5] dan sebaiknya tidak terlalu rendah, sehingga $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (juga untuk menghindari memberikan informasi). $\theta = 60$ berhasil, menghasilkan:

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

Mari kita mengotori tangan kita, kalau begitu. Ambil pesan Hello Toptal! . Pertama kami memetakannya ke dalam array byte menurut ASCII dan konvensi kami untuk memotong blok data:

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

Karena blok data kami panjangnya 16 bit = 2 byte, dan pesan kami memiliki 13 karakter, kami mendapatkan 7 blok data masing-masing 2 byte, di mana yang terakhir berisi dua kali representasi bit karakter '!' . Mari kita mengenkripsi blok pertama langkah demi langkah. Perhatikan baik-baik karena bit dari setiap byte diambil dalam urutan signifikansinya.

$m=01001000 01100101$

• Nibble pertama dari byte pertama: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Nibble kedua dari byte pertama: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Nibble pertama dari byte kedua: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Nibble kedua dari byte kedua: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

Dan dengan demikian, kami baru saja memetakan

“Dia” $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

Sisa dari pesan terenkripsi adalah sebagai berikut:

“ll” $\Rightarrow(12-12i,21-2i,61-3i,185-31i,367-59i)$

“o “ $\Panah Kanan(12-12i,25+33i,65+32i,111+44i,244+124i)$

“Ke” $\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

“pt” $\Rightarrow(12-12i,3+16i,46+12i,73+23i,201+49i)$

“al” $\Rightarrow(12-12i,4+54i,44+53i,117+193i,231+389i)$

”!!” $\Rightarrow(12-12i,4+54i,32+65i,63+92i,121+247i)$

Sekarang, untuk dekripsi, kita memiliki $\theta^{-1}=60^{-1}=27+i$:

$($”Dia” $\Panah Kanan)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93,223.527)$

Sekarang, datanglah algoritma serakah:

Pertama, kita kurangi setiap faktor yang berkontribusi dikalikan dengan satu, karena mereka diketahui berkontribusi setidaknya sekali untuk yang terakhir, menghasilkan:

• Nibble kedua dari byte kedua:

$T \leftarrow (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = false \Panah kanan b_1=0 ; T \panah kiri (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = true \Panah kanan b_2 = 1; T \panah kiri (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = true \Rightarrow b_3 = 1; T \panah kiri (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = false \Panah kanan b_4 = 0; T \panah kiri (T - 0 * 16) = 8$

Hasil: 0110;

Sisa: 8 (ditambahkan ke awal urutan sebagai elemen terendah baru);

Jatuhkan 527 dari akhir urutan saat ini;

• Nibble pertama dari byte kedua:

$T \panah kiri (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = false \Panah kanan b_1 = 0; T \panah kiri(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = true \Panah kanan b_2 = 1; T \panah kiri (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = false \Panah kanan b_3 = 0; T \panah kiri (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = true \Rightarrow b_4 = 1; T \panah kiri (T - 0 * 12) = 4$

Hasil: 0101;

Sisa: 4 (ditambahkan ke awal urutan sebagai elemen terendah baru);

Jatuhkan 233 dari akhir urutan saat ini;

• Nibble kedua dari byte pertama:

$T \panah kiri (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = false \Panah kanan b_1 = 0; T \panah kiri (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = true \Panah kanan b_2 = 1; T \panah kiri (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = false \Panah kanan b_3 = 0; T \panah kiri (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = false \Panah kanan b_4 = 0; T \panah kiri (T - 0 * 4) = 2$

Hasil: 0100;

Sisa: 2 (ditambahkan ke awal urutan sebagai elemen terendah baru);

Jatuhkan 93 dari akhir urutan saat ini;

• Nibble pertama dari byte pertama:

$T \panah kiri (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = true \Panah kanan b_1 = 1; T \panah kiri (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = false \Panah kanan b_2 = 0; T \panah kiri (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = false \Panah kanan b_3 = 0; T \panah kiri (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = false \Panah kanan b_4 = 0; T \panah kiri (T - 0 * 2) = 1$

Hasil: 1000;

Sisa: 1 (ditambahkan ke awal urutan sebagai elemen terendah baru);

Jatuhkan 47 dari akhir urutan saat ini;

Sebagai hasilnya, kami telah memulihkan blok data: "01001000 01100101" yang berisi dua karakter pertama "Dia", dari pesan kami. Tidak hanya itu, kami juga telah mengambil dengan benar urutan superincreasing private-key kami $(1,2,4,8,16)$.

Peta blok data lainnya berjalan dengan cara yang sama.

Perbandingan dengan Kriptosistem Kunci Publik Utama

SRVB adalah:

1. Benar-benar gratis dan umum;

2. Jauh lebih sederhana dan lebih mudah untuk dipahami dan diimplementasikan daripada ECC ^[7] ;

3. Berlimpah pada kunci dan karenanya hampir tanpa biaya, sebaliknya, misalnya, untuk RSA, yang bergantung pada bilangan prima, yang mahal.

Kami sudah dapat meringkas kerentanan yang paling mungkin. Sejak SRVB turun dari MH, mudah untuk menduga itu akan rentan terhadap generalisasi serangan Shamir, atau beberapa lainnya yang merusaknya. Meskipun penulis memiliki alasan untuk percaya bahwa ini tidak akan terjadi, belum ada konfirmasi yang dilakukan (yang sangat khas ketika berhadapan dengan cryptosystems).

Apa berikutnya?

Rocha mengamati beberapa generalisasi untuk cincin hasil bagi yang akan digunakan, yang mungkin dapat menyebabkan peningkatan kompleksitas kriptanalisis. Kami akan menyelidiki kemungkinan ini juga.

Pengaburan Aljabar Linier

Seperti yang terjadi, selama pengembangan dan dokumentasi SRVB, Villas Boas datang dengan pendekatan lain untuk meningkatkan konsep kriptosistem kunci publik knapsack yang tidak akan dijelaskan secara rinci di sini, agar artikel ini tidak menjadi terlalu panjang. dan melelahkan, tapi di sini adalah skimming itu. Jika Anda tidak berhasil memahaminya, jangan khawatir, tunggu saja rilis artikel kami berikutnya, di mana kami akan masuk ke detail lebih teliti: Lihat subset sum $y$, dari, katakanlah, $N$ elemen cincin hasil bagi $u_i$ (yang secara isomorfis berkorespondensi dengan bilangan bulat positif $v_i$ dari barisan supernaik, seperti sebelumnya) sebagai perkalian dari vektor baris $u_i$ ini dengan vektor kolom $B$ ( untuk biner) dari nol dan satu ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

di mana $b_i \dalam {0,1}$

Sekarang, bayangkan bahwa, alih-alih vektor $u_i$ ini, Anda memiliki, di sebelah kiri $n$ oleh $N$ (dengan $n < N$) matriks V, memiliki $v_i$ (bilangan bulat dari superincreasing urutan) vektor sebagai (tanpa kehilangan keumuman) baris pertama dan semua entri lainnya diisi dengan noise. Perhatikan bahwa, sekarang, mengalikan V dengan bit yang sama vektor B memberi Anda vektor kolom W yang memiliki $w$ sebagai entri pertama dan noise di yang lain. Sekarang, ambil matriks V ini dan kalikan dengan matriks acak ^[9] n dengan n R di sebelah kiri, dengan mendefinisikan matriks n dengan N P:

P = RV

Idenya adalah Bob menggunakan P sebagai kunci publik barunya. Karena keacakan R, vektor

$Y = PB = RV B = RW$

memiliki informasi $w$ yang dikaburkan oleh noise di baris V lainnya. Bob juga menghitung terlebih dahulu dan menyimpan vektor baris S yang memenuhi:

$R^TS^T = e_1$

Ketika, Alice mengirim Y ke Bob, dia hanya menemukan SY, karena:

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(sejauh ini hanya definisi)

${e_1}^T (VB)={e_1}^TW = w$

(Sekarang, memanfaatkan associativity untuk membatalkan Rs)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

ucapan terima kasih

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

Glosarium

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.