החומר המופיע בעמוד זה פורסם לראשונה בכתב העת "הבטים בהוראת מדעי המחשב" גליון יוני 2003, עמודים 7-9

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

פרס טיורינג לפרופ' עדי שמיר ועמיתיו לפיתוח אלגוריתם RSA

המאמר מבוסס על מספר מקורות ברשת האינטרנט
ריכוז החומר ועריכתו: תמי לפידות וד"ר דלית לוי
 

ההכרזה על הפרס

בתאריך 14.4.03 הכריז ארגון ACM שזוכי פרס טיורינג לשנת 2002 יהיו יוצריו של האלגוריתם הידוע בשם RSA - פרופ' עדי שמיר מהפקולטה למדעי המחשב ומתימטיקה שימושית במכון ויצמן למדע, ועמיתיו פרופ' ריבסט ופרופ' אדלמן.

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

כאמור, הפרס ניתן לשמיר ועמיתיו עבור תרומה מקורית ומשמעותית לתיאוריה וליישום של הצפנה על-ידי מפתח ציבורי, ובמיוחד עבור האלגוריתם שהם פיתחו בשנת 1977 ונקרא על שמם RSA (ראשי התיבות של שמות המשפחה שלהם Rivest-Shamir-Adelman).

ד"ר רוברט קאהן, נשיא CEO ו- CNRI, שעמד בראש ועדת הפרס לשנת 2002, ציין שהועדה התרשמה במיוחד מהשילוב של התרומה התיאורטית והיישום הנרחב של עבודה זו בתחומים רבים.

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

 

על מקבלי הפרס

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

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

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

 

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

 

אלגוריתם RSA

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

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

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

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

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

 

תורת ההצפנה (קריפטוגרפיה)

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

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

להצפנה יש ארבע מטרות עיקריות:

1) שמירת הסודיות של ההודעה: רק הנמען המקורי של ההודעה יוכל לפענח אותה וכן לא יהיה ניתן ללמוד מידע כלשהו על תוכן ההודעה (כמו התפלגות סטטיסטית של אותיות מסוימות בתוך ההודעה);

2) שלמות (מקבל ההודעה צריך להיות מסוגל לקבוע האם שיגור ההודעה הסתיים והוא יכול להתחיל בפענוחה);

3) אימות (המקבל צריך להיות מסוגל לזהות את השולח ולוודא שהוא אכן שלח את ההודעה);

4) מניעת הכחשה (כדי למנוע מהשולח להכחיש ששלח את ההודעה).

 

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

 

קריפטוגרפיה קלסית:

השימוש המוקדם ביותר נעשה בקריפטוגרפיה כבר בהירוגליפים המצריים (לפני כ- 3,500 שנים), למרות שהמטרה שם לא היתה הסתרת מידע אלא יצירת מסתורין ואולי אף שעשוע.

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

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

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

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

 

קריפטוגרפיה מודרנית:

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

בשנת 1976 חלו שתי התפתחויות חשובות בתחום:

הראשונה – פרסום DES (סטנדרט לקידוד מידע) שפותח על-ידי IBM ו- NSA במטרה לאפשר תקשורת בטוחה לעסקים כמו למשל בין בנקים. פרסום DES המריץ להתעניינות ציבורית ואקדמית בתחום הקריפטוגרפיה.

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

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

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

מעניין לציין שמתימטיקאי בריטי בשם קליפורד קוקס, תאר מערכת דומה ל- RSA כבר בשנת 1973. אלא שתגליתו נותרה חסויה עקב האופי הסודי של הפרויקט עליו עבד ב- GCHO.

 

קריאה נוספת בנושא ורשימת מקורות

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

 

http://wis-wander.weizmann.ac.il/site/EN/weizman.asp?pi=372&doc_id=3174

1) הודעת מכון ויצמן

http://www.ynet.co.il/articles/1,7340,L-2567193,00.html

2) אתר YNET

http://www.acm.org/announcements/turing_2002.html

3) אתר ACM 

http://www.usc.edu/dept/engineering/news/2003_stories/2003_04_14_adleman.html

4) אונ' דרום קליפורניה

http://www.wikipedia.org/wiki/Cryptography

5) Wikipedia - הצפנה

http://www.wikipedia.org/wiki/RSA

6) Wikipedia על RSA

http://searchsecurity.techtarget.com/sDefinition/

7) אתר 

 

אתר המרכז הארצי

אתר הבטים

גליון יוני 2003

חזרה לתחילת העמוד