Алгоритмдер жєне деректер структурасы

Ұсынылған алгоритмнің қауіпсіздігі үлкен сандардың жай сандарға жіктеу есебінің қиындығына сүйенген. Басқа сөзбен айтқанда факторизация есебін шешуге болады, бірақ ол тым көп уақыт алады. Қазір келесі жіктеу алгоритмдері белгілі: (Number Field Sieve), QS (Quadratic Sieve), ECM (Elliptic Curve Method) және басқалары. Ең тез алгоритм болып бүгінше NSA саналады.

Есептеу қабілеттілігі MIPS–жылдарымен саналады. MIPS–жыл дегеніміз – секундына миллион операция (million instructions per second) орындайтын компьютердің жылдық жұмысы, яғни шамамен 3*10¹³операция. Мысалы, 1024-биттік сөзді NSA алгоритмімен жіктеу үшін 3*10⁷ MIPS жыл кетеді.

Кілттің ұзындығын дұрыс таңдап алу үшін керекті қауіпсіздік дәрежесін анықтау қажет және жаңадан жасалып жатқан жіктеу алгоритмдерінің мүмкіндіктерін ұмытпау қажет. Ашық кілтіңіздің ұзындығын 2048 бит етіп алсаңыз алдыңғы 20 жылға оған сенімді болуыңызға болады. Бірақ әрине мұндай болжаулар орындалмай кетуі де мүмкін.

Енді біз алгоритмнің өзін емес сол алгоритмді қолданып отырған криптографиялық протоколға жасалатын шабуыл мысалдарын келтірейік.

Мысал 1. Марат уысына Айгүлдің әлдебіреуге жіберген шифрланған с хабары түсті. Марат кездейсоқ r

x=r^e_a mod n_A,

y=xc mod n_A,

t=r^-1 mod n_A

Осыдан r^-1 x^d_a1(mod n_A) екендігі көрініп тұр. Сонымен қатар x^d_A=r^e_a^d_a mod n_A= r mod n _A.

Енді Марат Айгүлден у-ге қол таңба қоюды сұрайды да u=y^d_a mod n_Aмәнін табады. Марат бастапқы хабарды келесі есептеулерді жасап тауып алады:

tu mod n_A=r^-1y^d_a mod n_A=r^-1x^d_ac^d_a mod n_A=c^d_a mod n_A=m

Мысал 2. Марат Айгүлді m₁ және m₂ хабарларына қол қойып бер деп сұрайды, яғни m₁^d_a mod n_A және m₂^d_a mod n_A мәндерін алады. Енді ол

C=(m₁m₂)^d_a mod n_A

Мәнін есептесе Айгүл өзі ешқашан көрмеген m₃=m₁m₂ құжатына қол қойған болып шығады.

Мысал 3. Бұл мысал қол қою алгоритмінде орындалатын қадамдардың ретін бұзатын протоколдарға қалай шабуыл жасауға болатынын көрсетеді. Мысалы Айгүл Болатқа шифрланған және қол қойылған хабарды жіберсін. Бірақ алгоритмді қолданғанда Айгүл алдымен m хабарын Болаттың ашық кілтімен, ал соңынан өзінің жабық кілтімен қол қояды:

(m^e_b mod n_B)^d_amod n_A

Болат өзінің ашық кілті n_B-нің жіктелуін білетіндіктен, келесі теңдік орындалатындай х санын таба алады

(m’)^x=m mod n_B

Енді ол өзінің жаңа ашық кілттерін жариялайтын болса, Айгүл m’ құжатына қол қойды деп айта алады.

Кішкентай мәнді құжаттарды шифрлағанда тағыда бір қатерлікті атап өтейік. Мысалы, e=5 және m<√n болсын, онда c=m⁵ mod n=m⁵ . Бұзғыш Маратқа бастапқы хабарды тауып алу үшін √c мәнін есептеп алу жеткілікті.