Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti kriptologiya kafedrasi Kriptografiya 2

Xatolarni tuzatish

Shunday qilib, xatolarni tuzatish amaliyotining maqsadi Alisa va Bobning bir xil bit lentalaridan butunlay bir xil bo'lishini ta'minlashdir. Bu klassik protsedura, chunki u faqat klassik bit va ochiq aloqa kanallari bilan ishlaydi.
Eng samarali xato tuzatish amaliyoti tasodifiy kodlardan foydalanishga qisqartirilgan. Q xatosi ehtimolligi bilan klassik kanalning o'tkazuvchanligi.
C_clas (Q)  1 h(Q),
bu yerda h(Q) - Shennonning binar entropiyasi. Kanaldagi xatolar ehtimolini
bilish va ketma-ket nomlar uzunligi n ^ - parametr n katta qiymatlari uchun kichik

amalga oshirilishi mumkin.
₂n(C_clas  )
tasodifiy so`z kodini hosil qilinadi va Alisa

bir bit ketma-ketlikni qo'shadi, so'ngra Bob so'z kodi majmuyini ochadi (va shu sababli ular Yeva bilan ma'lum bo'ladi), so`z kodi natijasida ro'yxatdan Bob ehtimoli Alisaning bit satrni tanlaydi, so'zlar kodi bilan bu tanlov, kanal shovqini uchun teoremani kodlashtirishga ko'ra, Xemming metrikasi ketma-ketlikda yaqin tanlaydi. Shunga qaramasdan, amaliyotda to'liq tasodifiy kodlarni amalda bajarish oson emas, chunki ularni qo'llashda xotirada kattaroq (n qator uzunliklariga qarab) kod so'zlari soni saqlanishi kerak. Odatda real chizmalarda boshqa dizayn kodlari qo'llaniladi, ularning samaradorligi past bo'ladi.

Maxfiylikni oshirish

Ushbu bosqichda Alisa va Bob Yevaga loyiq ma'lumotlarning bit lentalariga va smetasiga ega. Ushbu taxmin "pishloq" kalitidagi xatoliklar sonidan berilgan (bu xatoliklar aloqa kanalida aralashuvlar bilan bog'liqligini va ularning hammasi Yevaning faoliyati bilan bog'liqligini eslang.) Uning ma'lumotlarini qanday baholaysiz, ammo xatolarning soni keyinroq ko'rsatiladi.
Maxfiylik bosqichining vazifasi qisman maxfiy bitdan olishdir. Alisa va Bobning Yeva sirli kalitiga mutlaqo noma'lum bo'lgan satrlari. Odatda, bunday operatsiya davomida kalit uzunligi sezilarli darajada kamayadi. Maxfiylikni oshirishga imkon beradigan asosiy usul - universal xesh funktsiyalarining klassi G[4]. Ushbu funktsiya shunday m-bit satrlari to'plamining m-bit satr A to`plamini

^{ko'rsatadi, bir tasodifiy tanlangan hesh funktsiya} g G ^va
a₁, a₁  A
har qanday

tengsiz elementlar uchun, tasvirlar
g(a₁ )  g(a₂ )
tasodifiy ehtimoli 1/2 B dan

oshmasligi kerak. Bu vazifa B ning ikkita elementi prototiplarini topib, ro'yxatga olish yoki taxmin qilish orqali yanada samarali hal etilmaydi.Yevaning yakuniy kalit haqida qisman maxfiy kalit va dastlabki kalit uzunligi haqidagi dastlabki ma'lumotlari orqali taxmin qilinayotgan teorema mavjud: