
Симметрик шифрлэлтийн аргууд: Хилл Шифр (Hill Cipher) ба Модулийн урвуу матриц

М.Энх
Багш


М.Энх
Багш
Криптограф нь математикийн шинжлэх ухаантай нягт холбоотой байдаг. Өнөөдрийн дугаараар бид математик, тэр дундаа шугаман алгебр дээр суурилсан маш сонирхолтой шифрлэлтийн арга болох Хилл Шифр (Hill Cipher) болон түүнийг тайлахад ашиглагддаг Модулийн урвуу матриц-тай танилцацгаая. Мөн сануулж хэлэхэд нийтлэлийг маань ойлгохын тулд бага зэргийн суурь мэдлэг хэрэг болох байх шүү. Модулийн арифметик-н талаар мэддэггүй бол энэ рүү ороод судлачихаад ирээрэй. Амжилт!

Орлуулалтын шифрийн төрөлд Полиграфик шифр (Polygraphic substitution cipher)-ийн арга гэж байдаг. Энэ төрлийн шифрлэлтийн анхдагч нь 1929 онд Лестер Сандерс Хилл (Lester S. Hill) гэх эрхмийн бүтээсэн шифрлэлт бөгөөд түүний нэрээр "Хилл шифр" хэмээн нэрлэгджээ.
Энэ арга нь үсгүүдийг ганц ганцаар нь биш, хэсэг бүлгээр нь (блок) шифрлэдэг бөгөөд үүний тулд Матриц болон матрицын үржвэрийг ашигладаг.
Юун түрүүнд "матриц" (Matrix) гэж юу болохыг сануулъя.
👈🏿Энэ биш шүү!
[a, b]
[c, d] 👈🏿 энэ 😅
Энгийнээр бол тоонуудыг мөр, баганад байрлуулсан хүснэгт гээд ойлгож болно. Жишээ нь 2x2 хэмжээстэй матриц дараах хэлбэртэй байна:
[5, 8]
[3, 7]
Энэ мэтчилэн 2x2-оос эхлээд хязгааргүй хэмжээтэй байж болно.
Хилл шифрээр мэдээллийг хэрхэн шифрлэдэг үйл явцыг илүү ойлгомжтой болгохын тулд "HELP" (Тусламж) гэдэг үгийг шифрлэх бодит жишээгээр алхам алхмаар дэлгэрэнгүй тайлбарлая.
Үүний тулд бидэнд нууц түлхүүр болох 2x2 хэмжээстэй Түлхүүр матриц (K) хэрэгтэй. Жишээ болгоод дараах матрицыг сонгоё:
[3, 3]
[2, 5]
Хамгийн түрүүнд бид үгсийнхээ үсэг бүрийг Англи цагаан толгойн дарааллын дагуу тоон утгад шилжүүлнэ. Компьютерын шинжлэх ухаанд тооллого ихэвчлэн 0-ээс эхэлдэг тул A=0, B=1 гэх мэтээр Z=25 хүртэл дугаарлана.
A=0, B=1, C=2, D=3, E=4 ... Z=25
Бидний шифрлэх үг: H E L P
Дээрх дугаараас хөөж бодвол:
H = 7
E = 4
L = 11
P = 15
Бидний сонгосон түлхүүр матриц 2x2 хэмжээстэй байгаа тул бид текстээ 2, 2 үсгээр нь багцалж (блок болгож) хуваана. Хэрэв 3x3 матриц байсан бол 3 үсгээр хуваах байсан.
"HELP" гэдэг үг маань "HE" болон "LP" гэсэн хоёр хэсэгт хуваагдана.
Эдгээрийг баганан вектор (дээрээс доош цувруулж бичих) хэлбэрт оруулна:
Эхний вектор (HE):
[ 7 ]
[ 4 ]
Хоёр дахь вектор (LP):
[ 11 ]
[ 15 ]
Одоо шугаман алгебрын матрицын үржүүлэх үйлдлийг хийнэ. Түлхүүр матрицын мөрүүдийг векторын баганатай харгалзуулан үржүүлж нэмнэ.
Эхний вектор "HE"-ийг үржүүлэх нь:
Дээд талын тоо: (3 × 7) + (3 × 4) = 21 + 12 = 33
Доод талын тоо: (2 × 7) + (5 × 4) = 14 + 20 = 34
Шинэ вектор: [33, 34] гарч ирлээ.
Хоёр дахь вектор "LP"-ийг үржүүлэх нь:
Дээд талын тоо: (3 × 11) + (3 × 15) = 33 + 45 = 78
Доод талын тоо: (2 × 11) + (5 × 15) = 22 + 75 = 97
Шинэ вектор: [78, 97] гарч ирлээ.
Цагаан толгой ердөө 26 үсэгтэй (0-25) тул 25-аас давсан тоонуудыг буцаагаад үсэг рүү хөрвүүлэх боломжгүй. Тиймээс гарсан тоо бүрийг 26-д хувааж, гарсан үлдэгдлийг нь авдаг.
Эхний хэсэг:
33 mod 26 = 7 (33-ыг 26-д хуваахад 1 гараад, 7 үлдэнэ)
34 mod 26 = 8 (34-ийг 26-д хуваахад 1 гараад, 8 үлдэнэ)
Гарсан тоо: [7, 8]. Хүснэгтээс харвал 7=H, 8=I. "HE" гэдэг үг маань "HI" болж шифрлэгдлээ.
Хоёр дахь хэсэг:
78 mod 26 = 0 (78-ыг 26-д хуваахад 3 гараад, үлдэгдэл гарахгүй буюу 0)
97 mod 26 = 19 (97-г 26-д хуваахад 3 гараад, 19 үлдэнэ)
Гарсан тоо: [0, 19]. Хүснэгтээс харвал 0=A, 19=T. "LP" гэдэг үг маань "AT" болж шифрлэгдлээ.
Бидний анхны илгээх гэж байсан "HELP" гэдэг үг Хилл шифрийн аргаар "HIAT" болон хувирч, амжилттай нууцлагдлаа! Тэгвэл энэхүү нууцлагдсан зурвасыг хүлээж авсан хүн яаж буцааж унших вэ?
Шифрлэхдээ бид анхны текстийг Түлхүүр матрицаар үржүүлсэн. Тэгвэл буцааж тайлахын тулд шифрлэгдсэн текстийг тухайн түлхүүр матрицын Модулийн урвуу матрицаар (Modular Inverse Matrix) үржүүлэх шаардлагатай болдог. Бидний ашигласан түлхүүр матриц (K):
[3, 3]
[2, 5]
Энэхүү матрицын модулийн урвууг (mod 26) хэрхэн олохыг алхам алхмаар харцгаая.
Алхам 1: Тодорхойлогч (Determinant) олохdet(K) = (3 × 5) − (3 × 2) = 15 − 6 = 9.
Тодорхойлогч нь 9 гарлаа. 9 болон 26 нь харилцан анхны тоо тул урвуу матриц олдоно.
Алхам 2: Тодорхойлогчийн модулийн урвууг олох
Бидэнд 9 × x ≡ 1 (mod 26) байх x-ийг олох шаардлага гарна.
Хэрэв 9-ийг 3-аар үржүүлбэл 27 гарах бөгөөд 27 mod 26 = 1 байна.
Иймд тодорхойлогчийн модулийн урвуу нь 3 байна.
Алхам 3: Матрицын алгебрын нэмэлт (Adjugate Matrix) бүтээх
Анхны матрицын диагональ элементүүдийг (3 ба 5) сольж, нөгөө диагоналийн тэмдгийг эсрэгээр солино:
[ 5, -3 ]
[ -2, 3 ]
Алхам 4: Модулийн урвуу матрицыг тооцоолох
Одоо олсон 3 гэсэн тоогоо Adjugate матрицын элемент бүрээр үржүүлж, гарсан тоо бүрээс mod 26 авна.
5 × 3 = 15 ≡ 15 (mod 26)
(-3) × 3 = -9 ≡ 17 (mod 26) (Сөрөг тоог mod 26 руу оруулахдаа 26-г нэмнэ: -9 + 26 = 17)
(-2) × 3 = -6 ≡ 20 (mod 26) (-6 + 26 = 20)
3 × 3 = 9 ≡ 9 (mod 26)
Ингээд бидний хайсан Урвуу матриц бэлэн боллоо:
[15, 17]
[20, 9]
Энэхүү олдсон урвуу матрицыг ашиглан шифрлэгдсэн текстийг үржүүлснээр анхны мэдээллийг амжилттай сэргээж (тайлж) чадах юм. 2x2 хэмжээстэй матриц дээр үйлдэл хийхэд ийм байна. Харин 3x3, 4x4 болох тусмаа үйлдэл нь илүү төвөгтэй болдог.
Одоо бид урвуу матрицаа олсон тул шифрлэгдсэн "HIAT" үгээ буцааж тайлъя.
"HI" = [7, 8], "AT" = [0, 19]
Эхний вектор "HI"-ийг урвуу матрицаар үржүүлэх:
Дээд: (15 × 7) + (17 × 8) = 105 + 136 = 241
Доод: (20 × 7) + (9 × 8) = 140 + 72 = 212 Үлдэгдэл авах:
241 mod 26 = 7 (H)
212 mod 26 = 4 (E)
Хоёр дахь вектор "AT"-ийг урвуу матрицаар үржүүлэх:
Дээд: (15 × 0) + (17 × 19) = 0 + 323 = 323
Доод: (20 × 0) + (9 × 19) = 0 + 171 = 171 Үлдэгдэл авах:
323 mod 26 = 11 (L)
171 mod 26 = 15 (P)
Гайхалтай биш гэж үү? Бидний шифрлэсэн "HIAT" гэдэг үг математикийн гайхамшгаар ганц үйлдлийн дараа буцаад "HELP" болон сэргэлээ!
Хилл шифр нь криптограф болон математикийн гайхалтай хослол юм. Хэдийгээр орчин үед дангаараа ашиглагдахад аюулгүй байдлын хувьд сул талтай ч, матрицын үржвэр нь мэдээллийг маш сайн хольж сарниулдаг (diffusion) тул орчин үеийн шифрлэлтийн алгоритмуудын суурь санаа болж өгсөн байдаг.