TASKS / OFFICIAL SOLUTIONS

Тапсырмалар және ресми шешімдер

Есеп шарттары қазақ тіліндегі LaTeX түпнұсқасынан сақталды. Шешімдер бөлек ашылады.

I тур · Теориялық

1-есеп (4 ұпай). \(88^{1986}\) санының бестік санау жүйесіндегі соңғы екі цифрын табыңыз.

1-есеп (4 ұпай). \(88^{1986}\) санының бестік санау жүйесіндегі соңғы екі цифрын табыңыз.

Ресми шешімін көрсету

Соңғы екі цифрды табу үшін \({100}_5=25\) бойынша қалдықты табамыз: \(88\equiv13\pmod{25}\), \(\varphi(25)=20\), сондықтан \(13^{1986}\equiv13^6\equiv9\pmod{25}\). \(9=1\cdot5+4={14}_5\). Жауабы: \(14_5\).

2-есеп (4 ұпай). Әрбір бит \(p\ (0

2-есеп (4 ұпай). Әрбір бит \(p\ (0

Ресми шешімін көрсету

Дұрыс қалпына келтіру қате саны бірден аспағанда болады: \[P=(1-p)^3+3p(1-p)^2=(1-p)^2(1+2p).\] Бір бит үшін ықтималдық \(1-p\). Салыстыру: \((1-p)^2(1+2p)>1-p\Longleftrightarrow p(1-2p)>0\). Демек, үш рет қайталау \(0

3-есеп (5 ұпай). \(f(x_1,x_2,x_3,x_4)\) бульдік функциясы берілген қасиеттерге ие. \(s_{k+4}=f(s_k,s_{k+1},s_{k+2},s_{k+3})\), алғашқы элементтер: \(0,0,1,1,0,1\). \(s_7,s_8\) табыңыз және функцияның сызықтылығын анықтаңыз.

3-есеп (5 ұпай). \(f(x_1,x_2,x_3,x_4)\) бульдік функциясы берілген қасиеттерге ие. \(s_{k+4}=f(s_k,s_{k+1},s_{k+2},s_{k+3})\), алғашқы элементтер: \(0,0,1,1,0,1\). \(s_7,s_8\) табыңыз және функцияның сызықтылығын анықтаңыз.

Ресми шешімін көрсету

Берілген қасиеттер \(f=x_1\oplus x_i\oplus x_4\oplus c\), \(i\in\{2,3\}\) түрін береді. \(s_5,s_6\) арқылы \(i=3,c=0\), яғни \(f=x_1\oplus x_3\oplus x_4\). Сондықтан \(s_7=0,s_8=0\). Айнымалылар көбейтіндісі жоқ болғандықтан, функция сызықты.

4-есеп (5 ұпай). 6 биттік кілт «00»-ден басталса (A), «11»-мен аяқталса (B) немесе дәл төрт бірлігі болса (C), әлсіз деп саналады. Әлсіз кілттер санын табыңыз.

4-есеп (5 ұпай). 6 биттік кілт «00»-ден басталса (A), «11»-мен аяқталса (B) немесе дәл төрт бірлігі болса (C), әлсіз деп саналады. Әлсіз кілттер санын табыңыз.

Ресми шешімін көрсету

Қосу-алу формуласы: \(|A|=16,|B|=16,|C|=\binom64=15\); қиылысулар \(4,1,6\), ал үштік қиылысу \(1\). \(N=16+16+15-(4+1+6)+1=37\). Жауабы: 37.

5-есеп (7 ұпай). \(p=2^{13}-1=8191\) — Мерсенн жай саны және \(p\equiv3\pmod4\). \(x^2\equiv2\pmod{8191}\) болатын \(x\) санын табыңыз. Лежандр символы 2 санының p модулі бойынша квадраттық қалдық екенін көрсетеді.

5-есеп (7 ұпай). \(p=2^{13}-1=8191\) — Мерсенн жай саны және \(p\equiv3\pmod4\). \(x^2\equiv2\pmod{8191}\) болатын \(x\) санын табыңыз. Лежандр символы 2 санының p модулі бойынша квадраттық қалдық екенін көрсетеді.

Ресми шешімін көрсету

\(p\equiv3\pmod4\) болғандықтан, \(x\equiv2^{(p+1)/4}=2^{2048}\pmod{8191}\). \(2^{13}\equiv1\), ал \(2048=13\cdot157+7\). Сондықтан \(x\equiv2^7=128\). Жауабы: \(x=128\).

II тур · Криптоанализ

1-есеп (10 ұпай). Ұзындығы 4 NLFSR: \(s_{t+4}=s_t\oplus(s_{t+1}s_{t+2})\oplus1\), \(z_t=s_t\oplus s_{t+1}\oplus(s_{t+2}s_{t+3})\). Алғашқы гамма \(Z=(0,1,1,1)\). Кілтті және \(z_4\) табыңыз.

1-есеп (10 ұпай). Ұзындығы 4 NLFSR: \(s_{t+4}=s_t\oplus(s_{t+1}s_{t+2})\oplus1\), \(z_t=s_t\oplus s_{t+1}\oplus(s_{t+2}s_{t+3})\). Алғашқы гамма \(Z=(0,1,1,1)\). Кілтті және \(z_4\) табыңыз.

Ресми шешімін көрсету

\(z_0=0\) шартынан \(s_2s_3=s_0\oplus s_1\), сондықтан \(s_5=\overline{s_0}\). Екі жағдайды тексеру арқылы \(K=(1,1,0,1)\) табылады. \(s_4=0,s_5=0,s_6=1,s_7=0\), сондықтан \(z_4=0\). Жауабы: \(K=(1,1,0,1),z_4=0\).

2-есеп (15 ұпай). Шифрлау формуласы \(C_i=(aP_i+b+F_{k+i-1})\pmod{26}\), \(\mathrm{ЕҮОБ}(a,26)=1\). Ашық мәтіннің алғашқы әріптері ART, шифрмәтін KLUGMNM. \(a,b,k\) табыңыз және хабарламаны ашыңыз.

2-есеп (15 ұпай). Шифрлау формуласы \(C_i=(aP_i+b+F_{k+i-1})\pmod{26}\), \(\mathrm{ЕҮОБ}(a,26)=1\). Ашық мәтіннің алғашқы әріптері ART, шифрмәтін KLUGMNM. \(a,b,k\) табыңыз және хабарламаны ашыңыз.

Ресми шешімін көрсету

Алғашқы үш әріптен \(17a+F_{k-1}\equiv1\) және \(2a+F_k\equiv9\pmod{26}\). \(a\)-ны жойғанда \(4F_k-2F_{k-1}\equiv8\), одан \(k=4\). \(2a+3\equiv9\) теңдеуінен және \(\mathrm{ЕҮОБ}(a,26)=1\) шартынан \(a=3\), ал \(b=7\). Кері аффиндік кілт \(3^{-1}=9\pmod{26}\). Дешифрлау нәтижесі: ARTEMIS.

3-есеп (10 ұпай). Эль-Гамаль жүйесінде \(p=23,g=5,y=13\), \(r=g^k\pmod p\), \(s=(h-xr)k^{-1}\pmod{p-1}\). Екі тізбекті қолтаңба: \((10,20,12)\), \((12,8,9)\), \(k_2=k_1+1\). Құпия \(x\)-ті табыңыз.

3-есеп (10 ұпай). Эль-Гамаль жүйесінде \(p=23,g=5,y=13\), \(r=g^k\pmod p\), \(s=(h-xr)k^{-1}\pmod{p-1}\). Екі тізбекті қолтаңба: \((10,20,12)\), \((12,8,9)\), \(k_2=k_1+1\). Құпия \(x\)-ті табыңыз.

Ресми шешімін көрсету

Қолтаңба теңдеуі: \(sk+rx\equiv h\pmod{22}\). Сондықтан \(12k_1+20x\equiv10\), \(9k_1+8x\equiv3\). \(k_1\)-ді жойсақ, \(6x\equiv18\pmod{22}\), яғни \(x=3\) немесе \(14\). Ашық кілтпен тексеру \(5^{14}\equiv13\pmod{23}\) теңдігін береді. Жауабы: \(x=14\).