RSA алгоритмын хэрэглээний тухай Сонирхолтой байх үүднээс бид Бат болон Дулмаа гэсэн хоорондоо огт уулзалдах боломжгүй байгаа боловч бие биедээ дурласан хосуудыг авч үзье. Дулмаа Батад сэтгэлээ илчлэхийг хүссэн бөгөөд үүнийгээ зөвхөн Батад мэдүүлэхийг хүсчээ. Тиймээс тэр хайрын захиагаа шифрлээд Батруу илгээв. Гэтэл Батад шифрийг тайлах түлхүүр байхгүй бол энэ нь ямар ч хэрэггүй зүйл болно. Тэгэхээр Дулмаа дахиад Батруу түлхүүрийг явуулсан гэвэл магадгүй энэ нь Батын хартай хуучин найз охин Цэцгээд мэдэгдэх аюултай.
За тэгвэл энэ асуудлыг арай өөр аргаар шийдэх гээд үзье. Бат Дулмаагаас нууц захиа ирнэ гэдгийг мэддэг гэж үзье. Тиймээс тэр бүгд нэг түлхүүрээр онгойдог хайрцагнууд худалдаж авав. Тэгээд тэр энэ хайрцагнуудаа бүгдийг нь онгойлгоод нийтэд ил тавьсан ба түлхүүрээ өөртөө сайн хадгалжээ. Хэрвээ Дулмаа Батруу нууц захиа бичих бол эдгээр онгорхой хайрцагнуудын нэгэнд захиагаа хийгээд цоожлоод Батруу илгээхэд болно. Энэ мэдээж аюулгүй яагаад гэвэл Батад л ганц түлхүүр байгаа учраас. Гэхдээ энэ арга нь дэндүү төвөгтэй. Нууц захиа хүлээн авах хүн нийтэд ил хайрцаг бэлдэх, хүлээн авсан захиа нь яг Дулмаагаас ирсэн үү гэх мэт асуудал гарна. Дээрхи арга бол одоо бидний хэрэглэдэг имайлийн нууцлалтай зарчимын хувьд адил бөгөөд бидний имайл Цэцгээгээр хянуулж байгаа юу гэдгийг мэдэж чадахгүй.
Тиймээс RSA алгоритмын аргыг үзье.
Энэ арга нь доорхи 2 баримтад үндэслэнэ:
- Компьютер 2 том анхны тооны үржвэрийг хялбараар олж чадна. (google энийг дор нь хийж өгч чадна)
- Харин маш том тоог компьютерт оруулахад түүний үржигдэхүүн болж байгаа 2 том анхны тоог олж чадахгүй гацдаг (хангалттай их хугацаа зарцуулна).
Дээрхийг “trapdoor” гэдэг. Өөрөөр хэлбэл нэг талдаа амархан (үржүүлэх) боловч нөгөө талдаа (үржигдэхүүнийг олох) маш хүнд.
RSA нь доорхи зарчмаар ажиллана:
Эхлээд бид маш том p, q гэсэн 2 анхны тоог сонгоно (сонгосон 2 анхны тоо тус бүр дор хаяж 100 оронтой байх хэрэгтэй). Дараа нь энэ 2 анхны тооны үржвэр болох N олно. Мөн (p-1)(q-1) тэй харилцан анхны байхаар e тоог сонгоно. (N,e) хос бол бидний нийтэд ил түлхүүр юм. Энд байгаа N-ийг дэлхийн хамгийн хурдан компьютер ч үржвэрт задлахад хангалттай их хугацаа зарцуулах ёстой.
Энэ аргаа бүр сайн ойлгомжтой болгох үүднээс Бат, Дулмаа 2 дээрээ авч үзье. Тооцоололыг хялбар байлгах үүднээс маш бага тоонуудыг сонгож авлаа.
Дулмаа Батаас захиа ирнэ гэж мэдэж байгаа учраас Дулмаа эхлээд 2 анхны тоо сонгов. Тэр p=17, q=29 гэж сонгосон гэж үзье. (бодит байдал дээр асар томыг сонгох ёстой). Дараа нь тэр үржвэр N=p*q=17*29=493 гэж олов. Одоо тэр e тоог сонгох ёстой. (p-1)*(q-1) = 448 тул 448 тэй харилцан анхны 5-ыг тэр e-ээр сонголоо. Ингээд Дулмаа N=493, e=5 гэж Батруу явуулав.
Одоо Бат (493, 5)-ыг ашиглаад өөрийн захиагаа шифрлэх хэрэгтэй. Тэр Дулмааруу өөрийн насаа 42 гэж явуулахаар болсон гэе. Үүний тулд Бат 42-оо 5 зэрэгт дэвшүүлээд гарсан тоог 493т хуваагаад үлдэгдлийг олоход болно. 42^5=42 x 42 x 42 x 42 x 42 = 130,691,232 ба 493т хуваахад үлдэгдэл 383 гарна. Тиймээс Батын Дулмааруу явуулах шифр 383 болно.
Дулмаа Батаас 383 гэж хүлээн авсан ба үүнийг тайлж уншихын тулд эхлээд тэр d гэсэн тоог олох ёстой. Энэ d гэсэн тоо нь ямар тоо вэ гэхээр: e*d=(p-1)*(q-1)*z+1 байхаар олно (e тоог (p-1)(q-1) тэй харилцан анхны байхаар сонгосон тул d заавал олдоно). e=5, (p-1)*(q-1) = 448 гэдгийг санавал d=269 гэж гарна (5*269=448*3+1). Одоо 383 гэдгийг тайлж уншихдаа Дулмаа 383-ыг d буюу 269 зэрэгт дэвшүүлээд гарсан тоогоо N=493т хуваахад гарах үлдэгдлийг олоход болно. Мэдээж энэ үлдэгдэл 42 гарна.
RSA нь нийтэд ил түлхүүртэй кодчлолын (public key cryptography) одоо байгаа хамгийн сайн арга билээ.
Эх сурвалж: https://ganbat2009.wordpress.com
No comments:
Post a Comment