קריפטוגרפיה: פעילויות העשרה לתלמידי תיכון הלומדים מדעי המחשב

הצפנת SwapMethod והצפנת השבלול

הוכן על ידי וליד ח'ליפה, נזירות סנט ג'וזף נצרת

כל הפעילויות והחומרים באתר זה פותחו ע"י מורים מובילים שהשתתפו בסמינר קיץ 2003.

ניתן להשתמש בחומרים האלה לצורך הוראת הנושא לתלמידי תיכון.

לא ניתן לעשות בחומר כל שימוש מסחרי ללא רשות בכתב מראש מיוצרי החומרים.

מורים שיעשו שימוש בחומרים מתבקשים למלא את הטופס המצורף ולשלוח אותו אלינו.

 

רקע היסטורי לקריפטולוגיה

המילה קריפטוגרף מקורה יווני מהמילים Kryptos ו- graphein אשר פירושן "נסתר" ו- "לכתוב" בהתאמה (כמובן מקור המילה קריפטולוגיה אף הוא יווני ואפשר לפרשו כ"מדע המסתורין"). קריפטוגרף הוא אומנות ומדע התקשורת המובנת אך ורק למקבל המסר. קריפטולוגיה היא אומנות או מדע של תכנון ופענוח מערכות סודיות. מקור הכתיבה המסתורית הייתה לפני ארבעת אלפים שנה בכתיבה ההירוגרפית במצרים. במשך מלחמת העולם השניה היו נסיונות הצפנה ופיצוח האניגמה הגרמנית (ע"י אלן טיורינג ושותפיו) שיחק תפקיד חשוב בהכרעת המלחמה. 

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

קיימת שיטת קידוד שנקראת cipherplus שמתבססת על הזזה של כל אות כמספר נתון (אם יודעים את המספר אז יהיה ניתן לפענח את הטקסט). שיטת הקידוד הנפוצה היום נקראת RSA והיא מתבססת על שימוש במשפטים יסודיים בתורת המספרים (אם נדע את המפתח הפומבי יהיה ניתן לפענח את הטקסט בזמן סביר).

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

 

מושגי יסוד במטריצות

המטריצה מורכבת מאיברים המסודרים בשורות ועמודות.

מטריצה נקראת ריבועית אם מספר השורות בה שווה למספר העמודות.

המטריצה הבאה בעלת n עמודות ו- m שורות:

א. פעולת החלפת השורות בעמודות נקראת המטריצה המוחלפת (Transpose) ונקבל  AT:

פעולה זו הנה פעולה הופכית, אם נפעיל אותה בפעם השנייה נקבל את המטריצה המקורית    T A=(AT).

 

ב. מטריצה ריבועית A תיקרא הפיכה, אם קיימת מטריצה B כך ש- AB=I=BA, כאשרI  היא מטריצת היחידה (הזהות). המטריצה ההופכית תסומן ב- A-1. המטריצה ההופכית למטריצה A, באם קיימת, היא יחידה. ניתן לסדר את הטקסט במטריצה ולהשתמש בהכפלה במטריצה הפיכה, בשלב הפענוח נכפיל במטריצה ההופכית ונקבל את המטריצה המקורית.

 

ג. ניתן להגדיר העתקות חד חד ערכיות על מטריצות אשר ישמשו בהגדרת קודים תוך שימוש במטריצות.

למשל ניתן להגדיר את ההעתקה הבאה:

תהי X מטריצה מסדר nxn והמטריצה Y אף היא מסדר nxn . את Y מקבלים ע"י: 

1. החלפת הערכים הנמצאים מעל האלכסון הראשי ומעל האלכסון המשני עם האברים

הנמצאים מתחת לאלכסון הראשי ומתחת לאלכסון המשני.

2. החלפת הערכים הנמצאים מתחת לאלכסון הראשי ומעל האלכסון המשני עם האברים

הנמצאים מעל האלכסון הראשי ומתחת לאלכסון המשני.

3. החלפת הערכים הנמצאים באלכסון הראשי עם האברים הנמצאים באלכסון המשני.

 לשיטה זו נקרא – SwapMethod. אם הפעולה תבוצע פעמיים אנו נקבל את המטריצה המקורית.

נניח שיש לנו את ההודעה הבאה:

Never cut a rose from a garden even if ther is 9

הודעה זו הינה באורך 49 תווים. אם נסדר אותה במטריצה 7x7 , נקבל את מטריצה X הבאה:

 

 

1

2

3

4

5

6

7

1

N

E

V

E

R

 

C

2

U

T

 

A

 

R

O

3

S

E

 

F

R

O

M

4

 

A

 

G

A

R

D

5

E

N

 

E

V

E

N

6

 

I

F

 

T

H

E

7

R

E

 

I

S

 

9

 

אם נבצע את ההעתקה בשיטת SwapMethod נקבל:

 

 

1

2

3

4

5

6

7

1

C

E

 

I

S

 

N

2

O

R

F

 

T

T

U

3

M

O

R

E

 

E

S

4

D

R

A

G

 

A

 

5

N

E

V

F

 

N

E

6

E

H

 

A

 

I

 

7

9

E

V

E

R

 

R

 

הדפסה של המטריצה תיתן:      ce is norf tthmore es drag a nevf neeh a I 9ever r

כמובן שביצוע חוזר של אותן פעולות יתן את המקור.

 

רעיון אחר הוא סידור מחדש של האיברים במטריצה לפי עקרון השבלול (חילזון).

 

 

1

2

3

4

5

6

7

1

N

E

V

E

R

 

C

2

 

G

A

R

D

E

U

3

A

T

H

E

R

N

T

4

 

 

 

9

E

 

 

5

M

F

S

I

 

E

A

6

O

I

 

N

E

V

 

7

R

f

 

E

s

O

R

 

 

הדפסת המטריצה תיתן:    never c gardeuathernt   9e  mfsi eaoi nev rf esor

אם קיימת הודעה בתוך קובץ באורך 49 תווים, ניתן לקרוא את ההודעה מהקובץ ותוך כדי הקריאה לסדר את התווים במטריצה לפי שיטת השבלול. פענוח ההודעה יתבצע תוך כדי מעבר על המטריצה בשיטת השבלול רק במקום לקלוט ערכים למטריצה נדפיס את הערך.

קיימות כאן N/2 לולאות, כאשר בכל לולאה נעבור על שורה ראשונה, עמודה אחרונה, שורה תחתונה – הפוך (מהסוף להתחלה), עמודה ראשונה הפוך (מהסוף להתחלה) אחר כך נבצע אותו דבר על המטריצה שנשארת בלי אלה שכבר עברנו עליהם.

 

פעילות

מוצע בזאת לפתח עם התלמידים את המימוש של שיטות ההצפנה SwapMethd, שבלול (Snail), ומטריצה מוחלפת.

לאחר מכן, מומלץ לדון בנושאים הבאים:

א. מה החסרונות של שיטת השבלול ושל שיטת SwapMethod?

ב. מה היתרונות של שיטות אלה?

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

ד. הצע שתי שיטות חדשות לקידוד ופענוח וממש אותן.

 

תוכלו למצוא כאן תוכנית בשפת C הממשת את הקידוד והפענוח בשיטת השבלול  וה- SwapMethod.

התוכנית מקבלת כקלט הודעה באורך 49 תווים (N=7) הנמצאת בתוך הקובץ in.dat

איך תשנו את התוכנית אם אורך ההודעה לא ידוע? (ניתן להיעזר בקובץ שבו תושם ההודעה המוצפנת.)

 

חזרה לאתר הצפנה