Хилл Шифр гэж юу вэ?

Орлуулалтын шифрийн төрөлд Полиграфик шифр (Polygraphic substitution cipher)-ийн арга гэж байдаг. Энэ төрлийн шифрлэлтийн анхдагч нь 1929 онд Лестер Сандерс Хилл (Lester S. Hill) гэх эрхмийн бүтээсэн шифрлэлт бөгөөд түүний нэрээр "Хилл шифр" хэмээн нэрлэгджээ.

Энэ арга нь үсгүүдийг ганц ганцаар нь биш, хэсэг бүлгээр нь (блок) шифрлэдэг бөгөөд үүний тулд Матриц болон матрицын үржвэрийг ашигладаг.

Матриц гэж юу билээ?

Энэ мэтчилэн 2x2-оос эхлээд хязгааргүй хэмжээтэй байж болно.

Шифрлэлт

Хилл шифрээр хэрхэн шифрлэх вэ?

Хилл шифрээр мэдээллийг хэрхэн шифрлэдэг үйл явцыг илүү ойлгомжтой болгохын тулд "HELP" (Тусламж) гэдэг үгийг шифрлэх бодит жишээгээр алхам алхмаар дэлгэрэнгүй тайлбарлая.

Үүний тулд бидэнд нууц түлхүүр болох 2x2 хэмжээстэй Түлхүүр матриц (K) хэрэгтэй. Жишээ болгоод дараах матрицыг сонгоё:

[3, 3]
[2, 5]

Алхам 1: Үсгүүдийг тоонд хөрвүүлэх

Хамгийн түрүүнд бид үгсийнхээ үсэг бүрийг Англи цагаан толгойн дарааллын дагуу тоон утгад шилжүүлнэ. Компьютерын шинжлэх ухаанд тооллого ихэвчлэн 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

Алхам 2: Текстээ блокуудад хувааж, вектор үүсгэх

Бидний сонгосон түлхүүр матриц 2x2 хэмжээстэй байгаа тул бид текстээ 2, 2 үсгээр нь багцалж (блок болгож) хуваана. Хэрэв 3x3 матриц байсан бол 3 үсгээр хуваах байсан.

"HELP" гэдэг үг маань "HE" болон "LP" гэсэн хоёр хэсэгт хуваагдана.
Эдгээрийг баганан вектор (дээрээс доош цувруулж бичих) хэлбэрт оруулна:

Эхний вектор (HE):

[ 7 ]
[ 4 ]

Хоёр дахь вектор (LP):

[ 11 ]
[ 15 ]

Алхам 3: Түлхүүр матрицаар векторыг үржүүлэх

Одоо шугаман алгебрын матрицын үржүүлэх үйлдлийг хийнэ. Түлхүүр матрицын мөрүүдийг векторын баганатай харгалзуулан үржүүлж нэмнэ.

Эхний вектор "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] гарч ирлээ.

Алхам 4: 26-д хувааж үлдэгдлийг (mod 26) авах

Цагаан толгой ердөө 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 болох тусмаа үйлдэл нь илүү төвөгтэй болдог.

6. "HIAT"-ийг буцааж "HELP" болгох нь

Одоо бид урвуу матрицаа олсон тул шифрлэгдсэн "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) тул орчин үеийн шифрлэлтийн алгоритмуудын суурь санаа болж өгсөн байдаг.