Tt va kt ” fakulteti 4 – bosqich ax-11-17 guruh talabasining

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI

“ TT va KT ” FAKULTETI

4 – BOSQICH AX-11-17 GURUH TALABASINING

“Kriptoanaliz usullari”

FANIDAN TAYYORLAGAN

AMALIY ISHI

Bajardi: Xudoyberdiyev B

Qabul qildi: Bekkamov F
QARSHI – 2020

5-амалий машғулот

Мавзу: Факторлаш муаммосининг мураккаблигига асосланган асимметрик криптотизимларнинг криптотаҳлили

Диксон усули

Фараз қилинсинки, n ни факторлаш лозим бўлсин. Агар Лежандр эътибор қаратган x²≡y² (mod n) таққосламани, яъни n га каррали бўлган, x ва y k0 учун x²-y²=kn, унда (x-y)(x+y)=kn бўлади. Агар кичик эҳтимоллик билан x- y=k ва x+y=n ҳосил қилинса, камида ½ эҳтимоллик билан n ни факторлаш мумкин бўлади. Агар EKUB(n, x-y) ва EKUB(n, x+y) бўлса, унда булар n нинг фош этилган факторлари бўлади.

Масалан, 100=9 (mod 91), унда 10²=3²(mod 91),

(10-3)(10+3) = (7)(13) =0 (mod 91), демак, 7*13=91.

Умумий ҳолда факторлар EKUB(n, x-y) ва EKUB(n, x+y) ларни ҳисоблаш орқали топилади. EKUB дан фойдаланиш зарурлигини кўриш учун фараз қилинсинки, x=34, y=8, булар 34²=8²(mod 91) таққосламани қаноатлантиради, чунки 34² (mod 91)=64 дир. Бу мисолда x-y=26 ва x+y=42, бинобарин, EKUB(91,26)=13, EKUB(91,42)=7.

EKUB О(log a)² дан кичик мураккабликка эга бўлган Евклид алгоритми асосида осон ҳисобланади, аммо x²≡y² (mod n) таққосламани қаноатлантирувчи ўзгарувчилар жуфтини топиш мураккаб масаладир. Бу масалани ечишни осонлаштириш учун таққосламани қаноатлантириш шартларини бироз ўзгартириш кифоя.

Масалан, 41²=32 (mod 1649) ва 43²=200 (mod 1649) бўлсин, бу ерда 32

ҳам, 200 ҳам квадратик чегирма эмас.

Бироқ, иккала тенгламадан кутилган таққослама

(41*43)²=80² (mod 1649) берувчи 41²43²=32*200=6400 (mod 1649) топилади.

Бу масалани ечиш учун фойдаланиладиган субэкcпоненциал мураккабликка эга бўлган алгоритмларда силлиқлик хусусиятига эга бўлган сонлардан фойдаланилади. Алгоритмлар мураккаблиги бу хусусиятдан фойдаланишга бўлган ёндашув билан фарқланади.

Факторлаш масаласини ечишда икки босқичда ҳисоблашлар амалга оширилади:

• 
  биринчи, тайёрланиш босқичида бирор чегара В танланади ва фактор базаси ҳамда бу база асосида тенгламалар системаси шакллантирилади. Фактор базаси деганда 2p_iLⁿ шартини қаноатлантирувчи k та туб сон p_i тушунилади, бу ерда L=e^{lognlodlogn} ва базанинг m²(mod n) синфида энг кичик номанфий чегирмаси Q(m) билан белгиланади;
  
• 
  иккинчи босқичда тенгламалар системасининг ечими топилади.
  

Одатда бошланғич ҳисоблашлар бир марта амалга оширилади, сўнгра факторлар топилади. Шундай қилиб, факторлаш тенгламалар системасини ечишга ўтилади.

Алгоритмнинг биринчи босқичини амалга оширишда, фактор базасини шакллантиришда 1_iшартини қаноатлантирувчи m₁… m_k+1 сонлар тасодифий тарзда изланади ва Q(m_i)=p_i^I,1… p_k^I,k (i=1,k+1) кўринишдаги сонлар шакллантирилади. Бу ерда m_i²= Q(m_i)(mod n) силлиқ сонлар (B-силлиқлик муносабати билан боғланган сонлар)дир, чунки улар унча катта бўлмаган туб сонларнинг кўпайтмаси сифатида ифодаланади.

Q(m_i) кўрсаткичлари векторини _i=(_I,1…_I,k)Z^k билан белгиланади, бу ерда Z^k – k узунликка эга бўлган вектор фазоси.

k ўлчамли Буль фазоси Z^k₂ да x₁_i+…+ x₁_i0 (mod 2) кўринишдаги тенгламалар системасини ечиб, x_1…. x_k+1{0.1} топилади, бу ерда x_1…. x_k+1 вектори нолга тенг вектордан фарқли. Бундай ечим мавжуд, чунки тенгламалар сони номаълумлар сонидан кичик.

Ҳисобланган қийматлар x_1…. x_k+1 учун, қуйидаги таққослама ўринлидир:

(m₁^x1*** m₁^xk+1)²p₁^c1 *** p_k^ck (mod n),

бу ерда c₁=^k+1_i=1x_i_i,1, c_k=^k+1_i=1x_i_i,k,

X=m₁^x1*** m₁^xk+1, Y=^k _j=1 p_j^ck/2, c_k - x_i таърифга кўра бутун сон.

Натижада X²Y²(mod n) таққосламасига эга бўлинади. Сўнгра 1(XY,n)текширилади, шарт бажарилса факторлар топилган бўлади, акс ҳолда алгоритм бошига қайтилади ва токи қониқарли ечим топилмагунча, бошқа m_i лар билан юқоридаги амаллар бажарилади.