צופן היל

בהצפנה קלאסית, צופן היל (באנגלית: Hill Cipher) הוא צופן החלפה פוליגרפי המבוסס על אלגברה ליניארית (כפל מטריצות) שהומצא ב-1929 על ידי לסטר היל (Lester S. Hill) והיה הצופן הפוליגרפי המעשי הראשון שהצפין שלוש אותיות ומעלה בבת אחת^[1]^[2].

תיאור הצופן

צופן היל פועל על האלפבית האנגלי המכיל 26 אותיות, כאשר כל אות מיוצגת על ידי מספר שלם מודולו 26. בדרך כלל $A=0,B=1,C=2$ וכן הלאה עד $Z=25$ אם כי אפשר למספר אותם בדרכים אחרות. צופן היל דומה למעשה לצופן החלפה מרובה אותיות, הוא מחליף בלוקים של אותיות בבלוקים אחרים בהתאם למפתח ההצפנה. כדי להצפין מסר, תחילה מחלקים אותו לבלוקים באורך $n$ אותיות. (אפשר לראות בכל בלוק כוקטור בעל $n$ קואורדינטות) ואז מצפינים את הבלוק על ידי הכפלה של הווקטור (עמודה) במטריצה הפיכה מסדר $n\times n$ (מודולו 26), לפענוח מכפילים כל בלוק במטריצה ההופכית. המטריצה המשמשת להצפנה נקראת מפתח ההצפנה, ואילו המטריצה ההופכית נקראת מפתח פענוח. אפשר להרחיב את הרעיון לכל אלפבית המכיל מספר אחר של אותיות או סמלים ובלבד שכל החישובים ייעשו מודולו מספר הסמלים באלפבית. אפשר להצפין בבת אחת כל מספר של אותיות, אך ממדי מטריצת ההצפנה גדלים באופן מעריכי.

בניסוח פורמלי להצפנה מבצעים:

{\boldsymbol {\mathbf {v} \longleftarrow A\cdot \mathbf {u} }}

לפענוח מחשבים את:

{\boldsymbol {\mathbf {u} \longleftarrow A^{-1}\cdot \mathbf {v} }}

כאשר $\mathbf {u}$ ו- $\mathbf {v}$ הם וקטורים באורך $n$ המייצגים את הטקסט המקורי והטקסט המוצפן בהתאמה. המטריצה $A$ מסדר $n\times n$ היא מפתח ההצפנה והמטריצה ההופכית שלה $A^{-1}$ היא מפתח הפענוח.

דוגמה

נקח את האלפבית העברי המכיל 22 אותיות (ללא סופיות), נניח שהאותיות ממוספרות במיספור הרגיל כמתואר בטבלה הבאה וכל החישובים הם מודולו 22.

א	ב	ג	ד	ה	ו	ז	ח	ט	י	כ	ל	מ	נ	ס	ע	פ	צ	ק	ר	ש	ת
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21

נניח ש- $n=3$ ומפתח ההצפנה הוא המחרוזת "הקוד הסודי" (תשע אותיות ללא הרווח), המפתח מתפרש משמאל לימין במטריצה הבאה:

A={\begin{pmatrix}4&18&5\\3&4&14\\5&3&9\end{pmatrix}}

אפשר להמיר את מחרוזת האותיות של המפתח למטריצה בכמה דרכים. נניח שהמסר להצפנה הוא האותיות "אבג", לפי המספור שנקבע מתקבל הווקטור (0,1,2) לכן ההצפנה היא הכפל הבא:

{\begin{pmatrix}4&18&5\\3&4&14\\5&3&9\end{pmatrix}}\cdot {\begin{pmatrix}0\\1\\2\end{pmatrix}}={\begin{pmatrix}28\\32\\21\end{pmatrix}}\equiv {\begin{pmatrix}6\\10\\21\end{pmatrix}}{\text{ (mod }}22).

הטקסט המוצפן שהתקבל הוא "זכת".

אפשר לראות שצופן היל משיג את אפקט הפיזור (diffusion) שתואר לראשונה על ידי שאנון, אם כי ברמה של $n$ אותיות בלבד. כלומר הפיזור מוגבל למספר האותיות שניתן להצפין בבת אחת. אפשר לראות שבגלל הכפל במטריצה כל אות משפיעה על $n-1$ האותיות האחרות, זאת בניגוד לצופן החלפה פשוט שבו כל אות מוחלפת באות אחרת ללא תלות באותיות אחרות. עובדה זו מקשה על ניסיון לשבור את הצופן באמצעות ניתוח סטטיסטי של תדירויות השפה.

פענוח

כדי לפענח את הטקסט המוצפן תחילה ממירים אותו בחזרה לוקטור ואז מכפילים במטריצה ההופכית המודולרית. מטריצה הופכית היא מטריצה המקיימת:

AA^{-1}=A^{-1}A=I_{n}

כאשר

I_{n}

היא מטריצת היחידה מסדר

n

.

כל הפעולות כאן הן מודולו מספר האותיות באלפבית. קיימות מספר שיטות יעילות לחישוב מטריצה הופכית כשהנפוצות ביותר הן אלינימציית גאוס-ג'ורדן ושיטת ניוטון-רפסון. חשוב לציין שלא כל מטריצה הפיכה. מטריצה ריבועית תהיה הפיכה רק אם הדטרמיננטה שלה גדולה מאפס ובמקרה של צופן היל בגלל החשבון המודולרי ניתן יהיה לחשב את מטריצת הפענוח רק אם הדטרמיננטה של מטריצת ההצפנה היא גם זרה למודולוס שהוא מספר האותיות באלפבית. קיימות מטריצות רבות שמקיימות את התנאים האמורים. במקרה של הדוגמה לעיל המטריצה המודולרית ההופכית היא:

A^{-1}={\begin{pmatrix}8&9&6\\5&11&7\\11&6&14\end{pmatrix}}

והיא מתאימה למחרוזת "טיזהלחלזס". בגלל שאם מחשבים את $AA^{-1}$ מתקבל:

{\begin{pmatrix}4&18&5\\3&4&14\\5&3&9\end{pmatrix}}\cdot {\begin{pmatrix}8&9&6\\5&11&7\\11&6&14\end{pmatrix}}={\begin{pmatrix}177&264&220\\198&155&242\\154&132&177\end{pmatrix}}\equiv {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}{\text{ (mod }}22).

לכן לפענוח מחשבים את:

{\begin{pmatrix}8&9&6\\5&11&7\\11&6&14\end{pmatrix}}\cdot {\begin{pmatrix}6\\10\\21\end{pmatrix}}={\begin{pmatrix}264\\287\\420\end{pmatrix}}\equiv {\begin{pmatrix}0\\1\\2\end{pmatrix}}{\text{ (nod 22}}).

מתקבל הטקסט המקורי "אבג".

ביטחון

במונחים של הצפנה מודרנית צופן היל אינו בטוח לשימוש כלל. הוא נחשב לצופן חלש ופגיע במיוחד לקריפטואנליזה המנצלת את הליניאריות הגבוהה שלו. אם מתקיף הצופן משיג $n^{2}$ זוגות טקסטים קריאים וטקסטים מוצפנים המתאימים להם, הוא יכול לחלץ את המפתח בעזרת מערכת משוואות ליניארית שניתנת לפתרון בזמן פולינומי בטכניקות פשוטות מתחום האלגברה הליניארית.

כפל מטריצות כשלעצמו אינו מספק סודיות ראויה בימינו ואין להשתמש בו לבדו כאלגוריתם הצפנה, אך הוא יכול להיות שימושי כ"פונקציית פיזור" יעילה, ובשילוב עם פונקציה אי-ליניארית אחרת יהיה אפשר להגיע לצופן חזק יותר. למעשה צפנים מודרניים עושים שימוש רב בכפל מטריצות. שלב MixColumns שאחראי על הפיזור בצופן AES מבוצע באמצעות כפל מטריצות.

אורך מפתח

אם המפתח נבחר באקראי מתוך הטווח המקסימלי אומרים שאורכו האפקטיבי הוא לוגריתם בבסיס 2 של מספר המפתחות האפשריים^[3]. במקרה של אלפבית המכיל 22 אותיות ו- $n=3$ קיימות $22^{3^{2}}\approx 10^{8}$ מטריצות הצפנה אפשריות מסדר $3\times 3$ . בגלל שלא כל המטריצות הפיכות החסם העליון על אורך המפתח הוא $\log _{2}(a^{n^{2}})$ במקרה של $a=22$ בערך $4.459n^{2}\approx 40$ סיביות. מטריצה תהיה הפיכה מודולו $a$ רק אם היא הפיכה מודולו הגורמים הראשוניים שלו וקל לחשב את מספר המטריצות ההפיכות מודולו הגורמים הראשוניים. מספר המטריצות ההפיכות מודולו 2 שווה לסדר של החבורה הליניארית הכללית $GL(n,\mathbb {Z} _{2})$ . לכן אפשר לחשב את מספר המטריצות ההפיכות הכולל על ידי משפט השאריות הסיני. בנוסף בשל העובדה שאפסים רבים במטריצת ההצפנה פוגעים ברמת הפיזור של הצופן, יש צורך להימנע באופן כללי ממטריצות המכילות הרבה אפסים, מה שמצמצם את טווח המפתח עוד יותר.

אם $n=2$ כלומר אם מצפינים רק זוגות של אותיות או "דיגרפים" בזה אחר זה. צופן היל יהיה חלש אפילו מצופן פלייפייר או כל צופן פולי-אלפביתי שמצפין דיגרפים (זוגות). מצד שני ככל ש- $n$ גדול יותר ההצפנה הופכת לטורח רציני אם היא מבוצעת בעט ונייר. עבור $n$ גדול מאוד מתקבל צופן חזק יותר מפלייפייר אך אינו פרקטי כי מאוד קשה ליישמו ידנית, לכן חוזקו בא לידי ביטוי בצורה מכנית. היל יישם את הצופן שלו עם $n=6$ במכונת הצפנה מסובכת שהכילה גלגלי שיניים ושרשראות (כמתואר בתרשים) ואף רשם עליה פטנט בארצות הברית ב-1929 אך לא הצליח למצוא לה ולו קונה אחד. נדמה שהיל עצמו היה מודע לפרדיגמה המודרנית של פיתוח צופן בטוח כפי שניסח זאת קלוד שאנון: "ערבוב ופיזור" (confusion/diffusion) וכן היה ער לעובדה שאפשר לפצח את הצופן עם "איזון זמן/זיכרון" ביעילות רבה יותר מכוח גס ולכן ניסה לשלב במכונה שלב אי-ליניארי. היות שתצורת הגלילים קבועה עבור כל מכונה, היה צורך לבצע מספר שכבות, שכבת ערבוב אי-לנארית התלויה במפתח ושכבת פיזור ליניארית ללא מפתח ולאחריה שוב, שכבת ערבוב אי-ליניארית. רעיונות אילו היוו בין היתר מקור השראה לצפנים מודרניים יותר שבאו אחריו.

ב-1966 כאשר צוות הפיתוח של IBM בראשות דון קופרשמידט החלו בפיתוח רעיונות למערכת הצפנה מודרנית משולבת מחשב שתתאים לשימוש בקנה מידה גדול, מה שנקרא מאוחר יותר תקן ההצפנה DES, נשקל בין היתר לעשות שימוש בגרסה משופרת של צופן היל. בסופו של דבר ההצעה נפסלה כי הצופן לא הציג חוזק מינימלי ולא היה ראוי להיות מועמד לתקן הצפנה בקנה מידה גדול^[4].

ראו גם

הערות שוליים

^ Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, June–July 1929, pp. 306–312
^ Lester S. Hill, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly Vol.38, 1931, pp. 135–154
^ Jeffrey Overbey, William Traves, and Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol.29, No.1, January 2005, pp59–72
^ Konheim, Alan G. (2007), Computer Security and Cryptography, John Wiley & Sons, p. 283, מסת"ב 9780470083970.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

22621123צופן היל

[1] Lester S. Hill, Cryptography in an Algebraic Alphabet, The American Mathematical Monthly Vol.36, June–July 1929, pp. 306–312

[2] Lester S. Hill, Concerning Certain Linear Transformation Apparatus of Cryptography, The American Mathematical Monthly Vol.38, 1931, pp. 135–154

[3] Jeffrey Overbey, William Traves, and Jerzy Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol.29, No.1, January 2005, pp59–72

[4] Konheim, Alan G. (2007), Computer Security and Cryptography, John Wiley & Sons, p. 283, מסת"ב 9780470083970.

[1]

[2]

[3]

[4]

צופן היל

תוכן עניינים