Желі қателерді табу жане дұрыстау алгоритмдері

                                                  КІРІСПЕ

 

Курстық жұмыс тақырыбы: “Желідегі қатерлерді табу және дұрыстау алгоритмі”.

Мақсаты: Желідегі қатерлермен  жұмыс жасау оларды кодтау және дұрыстау болып табылады.

Өзектілігі:Циклдық артық  код бойынша таралған қатерлердің келесідей категорияларын табуды  оңайлатады. Біріншіден, аппаратураның ақаулығы кейде bit-тердің белгілі бір топтарын зақымдауды тудырады. Мысалы, ақауға ұшыраған символ бойынша кіріс-шығыс құрылғысы әр символдың екі бірінші мәні 0 мәніне теңестіріп тастауы мүмкін. Мұндай қатерлерді кейде тік деп атайды, өйткені олар тік бағанда жол түріндегі символ bit-терінің ауыстыруы кезіңде оңай байқалады. Циклдық артық кодтар тік қатерлерді бақылау сомасына қарағанда жақсы байқайды.

Екіншіден, циклдық артық кодтар әсіресе тасымалданатын деректер bit-терінің кішігірім жиынтығының бұрмалануымен пайда болған қатерлерді табу кезіңде өте ыңғайлы. Мұндай бұрмаланулар қатерлер дестесі деп атайды. Қатерлер дестесін табу өте маңызды, өйткені олар желілік аппараттық жабдықтаумен жойылуы тиісті көптеген проблемалар себебі болып табылады. Мысалы, қатерлер дестесі көбінесе айбарлы разрядтар сияқты электер бөгеулері әсерінен және сонымен қатар деректер тасымалданатын кабельмен электр двигательді іске қосқанда пайда болатын электр магниттік бөгеулер әсерінен туындайды.

Әдетте желілерде әр фрейммен бірге  қатерлерді табуға қажетті ақпарат  жіберіледі. Жіберуші бақылау сомасын  немесе циклдік артық кодты есептеп, оны фреймде жіберілген қызметтік  ақпаратпен салыстырады.

Ескеретін жағдай, фрейм  форматындағы soh, eot және esc символдарын алмастыру үшін деректерге байттар қосылады. CRC үшін байттарды қосу қажет пе?  Жауап қатерлерді табу тәсіліне байланысты. Циклдық артық код bit-тердің еркін жолдарын құрғандықтан, CRC-тегі бір немесе екі, сегіз биттік мән арнайы символға (soh, eot және esc)сайкес болуы мүмкін.

RC6 алгоритмі 1998 жылы  әйгілі RSA Data Security – RSA Laboratories фирмасының  Рональд Ривест (Ronald Rivest, RSA data Security ұйымының  негізін қалаушы), Мэт Робшоу (Matt Robshaw), Рэй Сидни (Ray Sidney), Икван Лайзон Ин (Yiqun Lisa Yin)  ғылыми бөлімінің мамандарымен арнайы AES конкурсына қатысу үшін құрылған болатын. Бұл алгоритм 1997 жылы Рональд Ривестпен құрылған 64 биттік RC5 блокты алгоритміне ұқсас болып келеді. Негізінен алгоритм екі принципиалды өзгеріске ұшыраған. Кеңейтілген кілт процедурасы:RC6 алгоритмінің кеңейтілген кілт процедурасы RC5-ке ұқсас, бірақ RC6 әлдеқайда көп генерацияланған ішкі кілттерді қажет етеді: 2R+4, яғни 20 раунд үшін K₀...K₄₃. AES конкурсына арналған нұсқасындағы  RC6 алгоритмі үшін берілген процедураны қарастырайық.

1 ЖЕЛІДЕГІ ҚАТЕРЛЕРДІ ТАБУ ЖӘНЕ ДҰРЫСТАУ АЛГОРИТМІ

1. Алгоритм құрылымы

 

RC5 алгоритміндегі сияқты RC6 алгоритмінің құрылымы да қарапайым:  алгоритмнің параметрлері (құпия кілтінен басқа) келесідей болады:

• сөздің өлшемі w, RC6 алгоритмі блок-блокпен, 4 сөзден шифрлайды;
• алгоритмнің раундтар саны R;
• құпия кілттің байттағы өлшемі b;

RC5 алгоритмдегідей, оның  нақты жүзеге асыратын  алгоритмінің  параметрлерін анықтау үшін RC6-w/R/b белгіленуі қолданылады. AES конкурсында 128 биттік блок міндетті болудың себебімен w мәні белгіленген және 32-ге тең болады. Алгоритмнің ерекшеліктерінде сонымен бірге раундтар саны да белгіленген: R = 20. AES конкурсы кілттің үш белгіленген өлшемін ескергендіктен алгоритмнің келесі үш нұсқасын қарастырайық: RC6-32/20/16, RC6-32/20/20, RC6-32/20/24. Алгоритмнің құрылымы 1-суретте көрсетілген.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                          1-сурет. RC6 алгоритмнің құрылымы

 

Жоғарыда айтылып кеткендей, алгоритмде 20 раунд қолданылады, және олардың алдында жарым-жарты кіріс әрекеттері орныдалады:

 

B = B + K₀ mod 2³², (1)

 

D = D + K₁ mod 2³², (1.1)

 

мұндағы A, B, C, D - өңделетін 32 биттік субблоктардың мәні, K₀ … K₄₃ – кеңейтілген кілттің фрагменттері.

Тура солай жарым-жарты шығыс әрекеттері де орындалады:

 

A = A + K₄₂ mod 2³², (1.2)

 

C = C + K₄₃ mod 2³². (1.3)

 

Алгоритмнің әр раундында  келесі әрекеттер орындалады:

 

t₁ = f (B) <<< 5, (1.4)

 

t₂ = f (D) <<< 5, (1.5)

 

A = (A Å t₁) + K_2i mod 2³², (1.6)

 

C = (C Å t₂) + K_2i+1 mod 2³², (1.7)

 

мұндағы, t₁ және t₂ – уақытша айнымалылар, айнымалы биттердің санына айналмалы биттердің саны параметрдің (t₁ немесе t₂) 5 кіші биттердің мәнімен анықталады. f() функциясы келесі квадраттық амалды орындайды:

 

f(x) = x * (2x + 1) mod 2³². (1.8)

 

Әр раундтың соңында  субблоктардың жылжуы орындалады. Дешифрлау кезінде ішкі кілттер кері тізбекте жұмыс істейді, кілттердің есептелуі 2³² модулі бойынша көбейту емес азайтумен орындалады. Субблоктардың жылжуы раундтың басында және кері жаққа қарай орныдалады. f() амалы ешқандай өзгертулерге ұшыраған жоқ 2-сурет. RC6 алгоритмімен дешифрлау көрсетілген.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                          2-сурет. RC6 алгоритмімен дешифрлау

  Алгоритмдерді құру кезіндегі қолданылатын критерийлер.әдетте симметриялық шифрлау алгоритмі келесі талаптарды орындау керек деп есептелінеді:

• Үлкен блоктардағы, 16 немесе 32 битті, деректерді манипуляциялау;
• 64 битті немесе 128  битті блоктар болу керек;
• 256 битке дейін үлкейетін кілт;
• Шағынпроцессорларда тиімді болатын қарапайым операцияларды қолдану;
• Жадыға минималды талаппен 8 битті процессорда алгоритмді жүзеге асыруға мүмкіндік;
• Алдын ала есептелінген ішкікілттерді қолдану. Үлкен жабы көлемі бар жүйелерде жұмыстың жылдамдығын арттыру үшін бұл ішкікілттер алдын ала есептелінуі керек;
• Мүмкіндігінше әлсіз кілттерді қолданбау. Егер бұл мүмкін болмаса, онда олардың санын азайту;
• Кілттің біржақты хэші болатын ішкікілттерді пайдалану. Бұл кілт ретінде үлкен құпиясөздерін қолдануға мүмкіндік береді т.б.

Блокты шифрлау алгоритмдердің көбісі Фейстель желісін қолдануда  негізделген. Барлығында бірнеше әлсіз  кілттердің болу мүмкіндігімен кілттердің жазық кеңістігі бар.

RC6 алгоритмі 1998 жылы  әйгілі RSA Data Security – RSA Laboratories фирмасының Рональд Ривест (Ronald Rivest, RSA data Security ұйымының негізін қалаушы), Мэт Робшоу (Matt Robshaw), Рэй Сидни (Ray Sidney), Икван Лайзон Ин (Yiqun Lisa Yin)  ғылыми бөлімінің мамандарымен арнайы AES конкурсына қатысу үшін құрылған болатын. Бұл алгоритм 1997 жылы Рональд Ривестпен құрылған 64 биттік RC5 блокты алгоритміне ұқсас болып келеді. Негізінен алгоритм екі принципиалды өзгеріске ұшыраған:

• RC5 алгоритмімен салыстырғанда, мұнда 2³² модулі бойынша көбейту орындалады;
• 32 биттік есептеулерді сақтау үшін шифрланатын деректер блогын (AES конкурсының принципиалды талабына сәйкес) екі 64 биттік субблокқа бөлудің орнына, төрт 32 биттік субблокқа бөліу орындалады және өңделуі сәл өзгертілген сұлба бойынша жүзеге асырылады.

Кеңейтілген кілт процедурасы:RC6 алгоритмінің кеңейтілген кілт процедурасы RC5-ке ұқсас, бірақ RC6 әлдеқайда көп генерацияланған ішкікілттерді қажет етеді: 2R+4, яғни 20 раунд үшін K₀...K₄₃. AES конкурсына арналған нұсқасындағы  RC6 алгоритмі үшін берілген процедураны қарастырайық.

Кілттің кеңейтілуі екі кезеңге бөлінеді:

1. K₀...K₄₃ кеңейтілген кілттер массивінің инициализациясы. Ол келесі түрде жүзеге асады:

 

K₀ = P₃₂, (1.9)

 

K_i+1 = K_i + Q₃₂ mod 2³², (2)

 

мұндағы, P₃₂ және Q₃₂ – псевдокездейсоқ константалар. Олар бөлшек бөліктің 2³² мәніне көбейтіп екі математикалық константаларының (e және f) ең жақын тақ бүтін санына дейін дөңгелектеу нәтижесінде құрылған:

 

P₃₂ = B7E15163, (2.1)

 
Q₃₂ = 9E3779B9,                                      (2.2)

 

Алгоритмнің авторлары  оның ерекшеліктеріне сәйкес жоғарыдағы константалардың мәндері сондай болуы маңызды емес деп тұжырымдайды. Себебі стандартты емес жағдайда P₃₂ и Q₃₂ мәндері басқа болатыны анық.

2. Келесі әрекеттер  циклді орындалады:

 

A = K_i = (K_i + A + B mod 2³²) <<< 3,      (2.3)

 
B = KI_j = (KI_j + A + B mod 2³²) <<< (A + B),                  (2.4)

 
i = i + 1 mod 44,                                                                (2.5)

 
j = j + 1 mod c,                                                                   (2.6)

 

мұндағы i, j, A және B – уақытша айнымалылар, олардың бастапқы мәндері нөлге тең. KI – 32 биттік сөзден алынған түрдегі бастапқы шифрлау кілті.

RC6 алгоритмінің құрылымы  қарапайым. Ал бұл алгоритмнің  қарапайым құрылымы оның талдауын  жеңілдетеді. Жалпы RC6 алгоритмінің  басқа шифрлау әдістерімен салыстырғанда біраз артықшылықтары бар. Одан басқа бұл алгоритм  AES  конкурсының   алдында   мұқият   зерттелініп   талдалынған. Өзінің ізашары RC5 алгоритмінің өңдеу мен өзгерту функцияларының бір бөлігін өзіне алған.32 биттік  платформаларды ең жылдамы. Шифрлау мен дешифрлау үрдістері бірдей дерлік жүреді.

2. Қатені табу

 

Код сөзінде x^j1,x^j2,…,x^jv позицияларында орналасқан v қате бар делік. Онда қате көпмүшелігін келесі түрде жазуға болады:

e(x)=e_j1x^j1+e_j2x^j2+…+e_jvx^jv. (2.7)

1,2,...,v индекстері- 1-ші, 2-ші, ..., v-ші қатені, j- қатенің орналасқан жерін білдіреді. Бұрмаланған код сөзін түзету үшін, қатенің  e_{j l} әрбір мәнін және орналасқан жерін x^jl анықтау керек, мұндағы l=1,2,...,v.

Қате локаторының нөмірін  α _l=b^jl деп белгілейік (локатор деп- қатесі бар позицияларды көрсететін өріс элементін айнады). Ары қарай синдромның n-k=2t  символын,  i=1,2,..., 2t кезіндегі, қабылданған көпмүшелікке bⁱ- ді қою арқылы шығарайық:

 

S₁=r(β)=e_j1α₁+e_j2α₂+…+e_jvα_v

S₂=r(β²)=e_j1α²₁+e_j2α₂²+…+e_jvα_v² (2.8)

……………………………….

S_2t=r(β^2t)=e_j1α₁^2t+e_j2α₂^2t+…+e_jvα_v^2t

 

Бізде 2t белгісіз (t қате мәндері мен t орналасулар) және 2t теңдеулер  жүйесі бар. Бұл 2t теңдеулер жүйесін  күнделікті жолмен шешуге болмайды. Бұл  жүйені шешу методикасын Рид- Соломон  декодерлеу алгоритімі деп атайды.

Егер синдромның нольдік емес векторы  есептеп шығарылса, ол қате қабылғандығын  білдіреді. Ары қарай қателердің орналасқан жерлерін табу керек. Қате локаторының көпмүшелегін келесі түрде  анықтауға болады:

 σ(x)=(1+β₁x)(1+β₂x)…(1+β_vx)=1+σ₁x+σ₂x²+…+σ_vx^v . (2.9)

σ(x) түбірлері 1/β₁, 1/β₂,...,1/β_v болып табылады. σ(x) түбірлеріне кері шамалар қате қате комбинацияның e(x) орналасу номерлерін көрсететін болады. Онда біз, бірінші t синдромдар келесі синдромды жорамалдау үшін пайдаланылатын, синдромдардан матрица құрамыз.

 

  (3)

 

Біз () авторегресионды моделін  пайдалана отырып, үш символды қатені түзететін (31,5) кодымыз үшін матрица 3×3 өлшемді болады және модель келесі түрде жазылады:

  (3.1)

 

                (3.2) 

 

σ(x) қате локаторы полиномының  σ₁ мен σ₂ коэффициенттерін табу үшін, () ы теңдік үшін кері матрицаны есептеп алуымыз керек.

 

   (3.3)

 

Яғни,  

 

 (3.4)

 

(3.5)

 

 

 

Бастапқы және кері матрицалардың көбейтіндісі бірлік матрицаны беру керек. 

Қателерді табуды қате локаторы полиномының коэффициенттерін есептеуден бастаймыз :

                          (3.6)

 

Соңғы теңдік арқылы келесіні аламыз:

 

σ(x)=β⁰+σ₁x+σ₂x²+σ₃x³=β⁰+β²⁸x+β¹¹x²+β⁷x³

 

σ(x) түбірлері қателердің орналасуына кері сандар болып табылады. Осы түбірлер табылғаннан кейін, біз қателердің орналасуын білеміз. Бұл түбірлерді σ(x) көпмүшелігінің барлық элементтерімен толық тексеру жолымен анықтайық. σ(x)=0 болатын кез- келген х элементі түбір болып табылады. Бұл қатенің орналасуын анықтауға мүмкіндік береді:

 

  σ(β⁰)=β⁰+β²⁸+β¹¹+β⁷ 0