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

RSA היופי שבמסובכות

הוכן על ידי אלי כהן (דקל וילנאי, מעלה אדומים), שמוליק שוורץ (מקיף גבעת ברנר), ואהובה תקוותי (מעלה הבשור)

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

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

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

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

 

מטרת הפעילות היא הכרות תוך התנסות עם אלגוריתם ההצפנה RSA.

הפעילות כוללת שישה שלבים (ועוד אחד...).

מומלץ לבצע אותם לפי הסדר, אך ניתן גם לדלג בהתאם לרצונכם.

 

השלבים המומלצים:

       1.         הכרות כללית עם הצפנת RSA.

       2.         התנסות באלגוריתם המייצר את המפתח הציבורי בעזרת קובץ אקסל ובמקביל להוראות מילוליות.

       3.         התנסות באלגוריתם המפענח/מפצח בעזרת קובץ אקסל.

       4.         תרגול בהצפנת אות בודדת בעזרת שיטת RSA ובעזרת קובץ אקסל.

       5.         תרגול בפענוח אות בודדת בעזרת שיטת RSA ובעזרת קובץ אקסל. (למי שיש את המפתח הפרטי).

       6.         תרגול בפיצוח אות בודדת בעזרת שיטת RSA ובעזרת קובץ אקסל. (למי שאין את המפתח הפרטי).

       7.         כתיבת תכנית פסקל או C לפיצוח אותיות מוצפנות.

 

שלב 1. הכרות כללית עם הצפנת RSA.

ההסבר המוצג כאן הוא בסיסי אבל מספק.

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

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

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

 

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

 

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

למשל אם אני רוצה להצפין את האות ח' שערכה הוא 8, בעזרת המפתח הציבורי 36 אז אני מבצע 36 div 8  ושולח את ההודעה 4.

מההודעה שנשלחה לא ניתן לדעת שהצפנתי את האות ח' שכן גם האות ט (9) תיתן את אותה תוצאה.

 

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

הסיבה הראשונה היא שהאויב יכול לפענח את ההודעה בעזרת ניסוי וטעייה.

ניקח למשל המילה "טנק" שמשמעותה לפני קידוד היא 9 (ט) 14 (נ) 19 (ק).

המילה "טנק" תקודד כ-  4 2 1 והפירושים האפשריים הם :

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ט

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

ח

4

צ

צ

צ

צ

פ

פ

פ

פ

ע

ע

ע

ע

ס

ס

ס

ס

נ

נ

נ

נ

מ

מ

מ

מ

צ

צ

צ

צ

פ

פ

פ

פ

ע

ע

ע

ע

ס

ס

ס

ס

נ

נ

נ

נ

מ

מ

מ

מ

2

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

ת

ש

ר

ק

1

 

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

כנראה שמה שהועבר בקשר היה שזיהינו טנק ולא חמר למשל.

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

הסיבה השלישית היא הזמן הנדרש לפענוח, הוא זהה גם לידיד וגם לאויב.

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

 

שלב 2. התנסות באלגוריתם המייצר את המפתח הציבור בעזרת קובץ אקסל ובמקביל להוראות מילוליות.

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

התחילו לקרוא מהכותרת "המתמטיקה של הצפנת RSA". http://www.halemo.com/edoar/0014/rsamath.html
(אם הכיתה אינה מחוברת לאינטרנט רצוי
לשמור את הדף בתיקייה של דף זה)
פיתחו במקביל את קובץ האקסל
המצורף קובץ עזר לחישוב  (ניתן להוריד כאן גם קובץ מכווץ)

תוכלו למצוא שם מימוש של האלגוריתם.

עקבו אחר השלבים ונסו להבין איך זה עובד.

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

 

שלב 3. התנסות באלגוריתם המפענח/מפצח בעזרת קובץ אקסל.

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

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

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

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

 

שלב 4. תרגול בהצפנת אות בודדת בעזרת שיטת RSA ובעזרת קובץ אקסל.

פיתחו את קובץ האקסל המצורף כאן  (ניתן להוריד כאן גם קובץ מכווץ).

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

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

 

שלב 5. תרגול בפענוח אות בודדת בעזרת שיטת RSA ובעזרת קובץ אקסל. (למי שיש את המפתח הפרטי).

זהו זה, אתם לבדכם...

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

 

שלב 6. תרגול בפיצוח אות בודדת בעזרת שיטת RSA ובעזרת קובץ אקסל. (למי שאין את המפתח הפרטי).

עכשיו מתחיל האקשן...

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

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

הכנו לכם גיליון עזר לחישוב מספרים ראשוניים עד 4000000, אבל כדי לא לעבוד שעות רבות מידי מומלץ לקבוע תיקרה, למשל שלא משתמשים במספרים הגדולים מ- 70 או משהו כזה.

 

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

N=114,381,625,757,888,867,669,235,779,976,146,612,010,218,296,721,242,362,562,561,842,935,706,935245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541.

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

כל אחד מהם בדק מחלקים בטווח מסוים.

בשנת 1994 הם הודיעו שמצאו את המספרים הראשוניים שיצרו את N ופיצחו את הקוד.

שימו לב ש- N הוא מספר מסדר גודל של 10129 ולקח 17 שנה לפצח אותו.

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

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

 

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

 

שלב 7. כתיבת תכנית פסקל או C לפיצוח אותיות מוצפנות.

כאן אין הנחיות, כל אחד לפי ראות עיניו.

יש בעיה עם מספרים שלמים אז זה רק מוסיף לסיבוכיות/עניין שיש במטלה.

שילחו את התוכניות למפתחי המטלה והם יושמו באתר לשימוש תלמידים אחרים.

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

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