Indeks Kebetulan Bersama

Saat ini saya mencoba memecahkan Caesar Cipher tanpa mengetahui kuncinya. Saya akan mendekati masalah ini dengan menggunakan indeks kebetulan bersama untuk menentukan apa kuncinya. Saya telah memecahkan masalah dengan metode lain menggunakan sifat statistik bahasa Inggris tetapi saya ingin mencoba masalah tersebut menggunakan metode ini juga.

Saya baru mengetahui bahwa indeks kebetulan dan indeks kebetulan timbal balik adalah dua hal yang berbeda. Mengingat sandi mono-abjad, indeks kebetulan akan selalu menghasilkan ~0,067 (untuk bahasa Inggris). Namun, sepertinya tidak demikian halnya dengan apa yang diberikan kepada saya.

Saya memerlukan bantuan untuk memahami cara menyusun algoritme untuk mengidentifikasi indeks kebetulan bersama berdasarkan rumusnya

Rumus MIC

Mengingat bahwa masukkan deskripsi gambar di sini di mana fi adalah kemunculan huruf ke-i dalam alfabet dan N adalah panjang teks dan qi+k

Dari apa yang saya pahami (saya buruk dalam Matematika), saya harus mengulangi i dari 0-25 dan mendapatkan indeks indeks kebetulan timbal balik maksimum di antara 25 dan itu akan memberi saya kunci untuk sandi tersebut. Untuk melakukan itu, saya harus mengalikan pi dengan qi+k. Namun, jika pi kira-kira sama dengan qi+k untuk semua i, bukan berarti pi? Dengan demikian, bukankah persamaan tersebut merupakan penjumlahan dari pi kuadrat?


encryption algorithm math caesar-cipher
person Jon K    schedule 11.07.2020    source sumber
comment
Saya berasumsi p_i adalah frekuensi huruf yang diharapkan (diberikan oleh analisis frekuensi teks bahasa Inggris). Saya pikir Anda melewatkan beberapa kata. Saya kira teks aslinya mengatakan bahwa Anda harus mencari k (dari 0 hingga 25) sedemikian rupa sehingga setiap p_i kira-kira sama dengan q_{i+k} untuk setiap i. Indeks kebetulan timbal balik adalah salah satu ukuran seberapa dekat dua vektor (pada dasarnya setara dengan kesamaan kosinus), sehingga k dengan MIC tertinggi merupakan kandidat yang baik untuk kunci asli.   -  person Paul Hankin    schedule 11.07.2020
comment
Ya, menurut saya Anda benar dalam mencari k (0-25) sehingga setiap p_i kira-kira sama dengan q_{i+k} untuk setiap i, meskipun pertanyaannya hanya menyatakan semua i. Saya tidak yakin apakah saya kehilangan detail lagi dari pertanyaan tersebut (semoga tidak), tetapi saya agak bingung bagaimana cara mulai mendapatkan MIC untuk setiap k.   -  person Jon K    schedule 11.07.2020
comment
Apa masalah spesifik Anda? Sudahkah Anda menghitung 26 frekuensi q[i]? Apakah Anda memiliki (saya kira bahasa Inggris) frekuensi huruf p[i]?   -  person Paul Hankin    schedule 11.07.2020
comment
Dalam kode saya, saya telah berhasil mendapatkan frekuensi huruf pada semua karakter untuk setiap kunci dari 0 hingga 25. Tapi saya tidak yakin bagaimana cara mendapatkan MIC dari sana. Saya berasumsi bahwa p_i q_{i+k} berarti (f_{i+k} / N) * (f_{i+k} /N) dijumlahkan tetapi saya menyadari bahwa keduanya adalah hal yang sama (dan tidak memberi saya a tutup MIC sih) jadi saya pasti salah saat mencoba membuat rumus menghitung MIC untuk setiap k.   -  person Jon K    schedule 11.07.2020
comment
Hmm, p[i] seharusnya berupa vektor yang terlihat seperti [0.082, 0.014, 0.028, ...] (frekuensi huruf untuk bahasa Inggris dari en.wikipedia.org/wiki/). q[i] harus berupa vektor yang menyimpan frekuensi pengamatan setiap huruf dalam teks tersandi, dibagi dengan panjang teks tersandit.   -  person Paul Hankin    schedule 11.07.2020
comment
MIC[k] adalah sum(p[i] * q[(i+k)%26] for i in range(26)) dengan python.   -  person Paul Hankin    schedule 11.07.2020
comment
Rumus yang diberikan sudah benar, terima kasih banyak! @PaulHankin   -  person Jon K    schedule 12.07.2020

Jawaban (1)


arrow_upward
0
arrow_downward

Terima kasih banyak kepada Paul Hankin atas klarifikasinya. P_i dalam hal ini sebenarnya bukan q_{i+k} melainkan probabilitas kemunculan setiap huruf dalam bahasa Inggris (yang bersifat tetap) dan q_{i+k} mengacu pada kemunculan setiap huruf yang digeser dengan kunci dalam cipherteks.

Solusi yang diberikan oleh Paul di mana MIC[k] adalah sum(p[i] * q[(i+k)%26] untuk i dalam rentang(26)) adalah benar - hasil persamaan harus dibagi dengan N untuk mendapatkan indeks kebetulan timbal balik.

person Jon K    schedule 12.07.2020