Ryukzak algoritmi

Shifrlash.
Berilgan xabar M harfi bilan belgilanadi. Shifrtekst esa, C bilan belgilanadi. Xabar bit ko’rinishida yozib olinadi (m₁, m₂, …, m_n):
( )mod q=c_i
formula yordamida shifrlanadi. Shifrtekst C = {c_1, c₂, …} ko’rinishida hosil bo’ladi. Shifrni ochish.
C = {c_1, c₂, …} ko’rinishidagi shifrtekstni
( r^-1 c_i )mod q=m_i
formula yordamida ochiladi. Ochilgan m_i larni yig’ib chiqib, M hosil qilinadi.
R.Merkl tizimni buzib ocha olgan odamga 100 AQSh dollari mukofoti berishini e‘lon qildi. 1982 yilda Adi Shamir bu mukofotga sazovor bo’ldi. U mahfiy kalitga teng bo’lmagan kalit yasab shifrlarni ocha oldi.
Misol.
O’suvchi ketma-ketlik w = {2, 3, 7, 15}, modul son q=28, q modul bilan o’zaro tub bo’lgan r=11, shifrlanadigan matn M=HA so’zi bo’lsin.
Shifrlash:

1. 
   HA so’zini ASCII jadvali yordamida bit ko’rinishga o’tkazamiz:
   

0100100001000001.

2. 
   b_i = (w_i * r) mod q formula orqali normal ketma-ketlik hosil qilamiz:
   

b₁ =(w_{1 *} r) mod q= (2*11) mod28=22
b₂ =(w_{2 *} r) mod q= (3*11) mod28=5
b3 =(w_{3 *} r) mod q= (7*11) mod28=21
b₄ =(w_{4 *} r) mod q= (15*11) mod28=25

3. 
   Ketma-ketlik hadlari 4 ta bo’lgani uchun matnni 4 bitdan bloklarga ajratamiz:
   

M₁={m₁, m₂, m₃, m₄}=0100, M₂={m₁, m₂, m₃, m₄}=1000,
M₃={m₁, m₂, m₃, m₄}=0100, M₄={m₁, m₂, m₃, m₄}=0001.

4. 
   ( )mod q =c_i formula yordamida shifrlaymiz:
   

c₁=( )mod q= (22*0+5*1+21*0+25*0)mod28=5
c₂=( )mod q=(22*1+5*0+21*0+25*0)mod28=22
c₃=( )mod q= (22*0+5*1+21*0+25*0)mod28=5
c₄=( )mod q= (22*0+5*01+21*0+25*1)mod28=25
5. Shifrtekst hosil bo’ladi: C={c₁, c₂, c₃, c₄}.
Shifrni ochish:
O’suvchi ketma-ketlik w = {2, 3, 7, 15}, modul son q=28, q modul bilan o’zaro tub bo’lgan r=11, C={5, 22, 5, 25} bizga ma‘lum.
1. r sonining q modul bo’yicha teskarisini topamiz: 11^-1mod28= 11¹¹mod28=(11(11² mod 28)⁵ )mod 28 = (11*9⁵ )mod 28 = (11*9(9² mod
28)² )mod 28 = (11 * 9 * 25² )mod 28 = 23
2. (r^-1c_i)mod q=m_i formuladan matnni topamiz: M = (23 *5) mod 28 = 3 =2*0 +3*1 + 7*0 + 15*0 , bundan M₁ = 0100 ekanligini aniqlaymiz.

3. 
   M = (23 *22) mod 28 = 2=2*1 +3*0 + 7*0 + 15*0, bundan M₂=1000 ekanligini aniqlaymiz.
   
4. 
   M = (23*5) mod 28 = 3=2*0 +3*1 + 7*0 + 15*0, bundan M₃ = 0100 ekanligini aniqlaymiz.
   
5. 
   M₄=(23 · 25) mod 28 = 15 = 2·0+3·0+7·0+15·1, bundan M₄=0001 ekanligini aniqlaymiz.
   
6. 
   Barcha M_i larni ketma-ket yozib harflarga o’tiladi:
   

M=0100100001000001
0100 1000 ₂ = 48 ₁₆ = H
0100 0001 ₂ = 41 ₁₆ = A
M = “HA”