מדע בזיוני

מעניין. אולי זה אפילו נכון.

הבלוג של אורן צור-

אורן הוא:
-עוד קורבן של הסטטיסטיקה
-נכשל במבחן טיורינג

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

1. ובו יסופר קצת על עדי שמיר

עדי שמיר, כיום במכון וויצמן קנה את עולמו ופרסומו עם פיתוח אלגוריתם ה-RSA (S -Shamir). את האלגוריתם הוא פיתח בשנת 1977 במהלך פוסט-דוקטורט ב-MIT ביחד עם רונלד ריווסט ולאונרד אדלמן. ה-RSA הוא אחד מאלגוריתמי ההצפנה השימושיים ביותר ואפשר לומר שהוא שינה את פני אבטחת המידע והשפיע עמוקות על התפתחות המסחר האלקטרוני וכל הג'אז האינטרנטי. שמיר לא נח על שמרי הפרסום של ה-RSA והוא חתום גם על, למשל, היסודות לפיצוח מפתח ה-WEP של רשתות אלחוטיות. בשנת 2002 הוא זכה בפרס טיורינג הלא-הוא המקבילה של מדעי המחשב לפרס הנובל. ועכשיו, כאמור, הוא זוכה גם בפרס ישראל. מגיע לו. מגיע לנו.

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

הנה ריווסט, שמיר ואדלמן בתמונה מימי MIT העליזים. נחשו נא מי הישראלי מהשלושה…
rsa2.jpg

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

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

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

(עמ' 351, סודות ההצפנה, סיימון סינג. כאן תוכלו לקרוא את הפרק הראשון)

אדלמן, אגב, חשב שזה יהיה "המאמר הכי פחות מעניין שהשם שלי יופיע בו אי פעם" וביקש להסיר את שמו מהמאמר. ריווסט ושמיר לא הסכימו, אדלמן נשאר ברשימת המחברים וה-RSA הפך לאלגוריתם ההצפנה החשוב ביותר בהצפנה המודרנית. והנה, בשביל ההיסטוריה, המאמר המקורי: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems . (PDF)

2. ובו יסופר איך הפכתי קריפטוגרף וזכיתי בימבה כסף

זה היה בעיצומו של קיץ. בתיבת האימייל נחת אימייל מל', תחקירנית ב-1 נגד 100 ובו היא מספרת שהם הולכים להרכיב קבוצה הומוגנית של בלשנים ושאלה אם אני מוכן להשתתף. לא רציתי. אני גם לא בלשן. "למה לא?" אמרה האישה, יהיה קטעים. עוד זו מדברת ובתיבת הדוא"ל נוחת אימייל נוסף מל' (ל' אחרת) גם היא תחקירנית ב-1 נגד 100. "אנחנו מרכיבים קבוצה של קריפטוגרפים" (או אולי מפצחי צפנים) היא אמרה, "אתה רוצה להשתתף?" האמת שלא רציתי. אני גם לא קריפטוגרף. אבל על הישנות האימייל פעמיים ובעקבות ההפצרות של האישה החלטתי להיענות.
"אני מסכים לבוא," אמרתי לתחקירנית, "אבל את צריכה לדעת שאני בכלל לא קריפטוגרף. איך הגעת אלי בכלל?" שאלתי. מסתבר שבעקבות מאמר שפרסמתי פעם בגלילאו: על שירי איגיון ופיענוח צפנים הוא נקרא. המאמר בכלל עוסק במודלים התסברותיים לשפה והצפנים הוספו בכותרת (ובפסקה קטנה בגוף המאמר) רק כדי להוסיף קצת נופך סקסי. לתחקירנית זה הספיק. בתוכנית ציוותו אותי, דוקטורנט צעיר לבלשנות חישובית, לשלושה קריפטוגרפים מדופלמים – דוקטורים ותיקים מהטכניון. הם, בניגוד אליי, באמת עסקו בתורת ההצפנה. הטעות בזיהוי (של התחקירנית) ושיג ושיח שהיה לי, הקריפטוגרף המדומה, עם אלו האמיתיים העלו כמה הרהורים על מהות ההצפנה ועל הצפנה בכלל מול תורת ההצפנה המודרנית. (למי שמתעניין במעללי הטלוויזיוניים רק אומר שזכיתי ל-15 מילי-שניות של תהילה, גיליתי שאני כנראה אלרגי לאיפור וזכיתי ב-826 שקלין טבין ותקילין).

3. על ההבדל בין פיענוח צפנים לקריפטולוגיה המודרנית

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

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

4. ובו יסופר על הצופן הראשון

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

יח וַיֹּאמֶר-לוֹ יְהוֹנָתָן, מָחָר חֹדֶשׁ; וְנִפְקַדְתָּ, כִּי יִפָּקֵד מוֹשָׁבֶךָ. יט וְשִׁלַּשְׁתָּ, תֵּרֵד מְאֹד, וּבָאתָ אֶל-הַמָּקוֹם, אֲשֶׁר-נִסְתַּרְתָּ שָּׁם בְּיוֹם הַמַּעֲשֶׂה; וְיָשַׁבְתָּ, אֵצֶל הָאֶבֶן הָאָזֶל. כ וַאֲנִי, שְׁלֹשֶׁת הַחִצִּים צִדָּה אוֹרֶה, לְשַׁלַּח-לִי, לְמַטָּרָה. כא וְהִנֵּה אֶשְׁלַח אֶת-הַנַּעַר, לֵךְ מְצָא אֶת-הַחִצִּים: אִם-אָמֹר אֹמַר לַנַּעַר הִנֵּה הַחִצִּים מִמְּךָ וָהֵנָּה, קָחֶנּוּ וָבֹאָה כִּי-שָׁלוֹם לְךָ וְאֵין דָּבָר–חַי-יְהוָה. כב וְאִם-כֹּה אֹמַר לָעֶלֶם, הִנֵּה הַחִצִּים מִמְּךָ וָהָלְאָה–לֵךְ, כִּי שִׁלַּחֲךָ יְהוָה. כג וְהַדָּבָר–אֲשֶׁר דִּבַּרְנוּ, אֲנִי וָאָתָּה: הִנֵּה יְהוָה בֵּינִי וּבֵינְךָ, עַד-עוֹלָם.

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

24 תגובות עבור “סודות ההצפנה: פרס ישראל לעדי שמיר”

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

    בטח עוד אחזור לבקר.

    לאו

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

    רואה שחורות

  3. […] צור כותב על הזוכה בפרס ישראל למדעי המחשב, פרופסור עדי שמיר, על קריפטוגרפיה (תורת ההצפנה), ועל […]

    The Daily Dolly 20/02/2008 at The Daily Dolly

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

    MuyaMan

  5. אורן, זה מעניין מאוד. תודה שכתבת. וחיברת יפה בין "הוא" ל"אני".

    דרור שניר

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

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

    אורן

  7. אכן, פוסט משובח.

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

    יואב

  8. פוסט נפלא.

    אינני אשורולוג, אך ראו כאן:
    http://www.isi.edu/natural-language/mt/decipher06.pdf

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

    יואב

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

    אני משאיר גם את התגובה השניה – זו שמתלוננת על זה שאין לינקים, כדי שיבינו מה קורה.
    אז ככה – באופן עקרוני, כל תגובה שיש בה יותר ב-n (כרגע 3) לינקים מועברת באופן אוטומאטי למודרציה כדי שאבדוק שזה לא ספינג או סתם ספאם.
    חוצמזה – אני משתמש בפלאגין שלAKISMET http://akismet.com/ כדי לסנן ספאם. בדרך כלל הוא ממש בסדר והתגובה של יואב (לעיל) זו הפעם הראשונה שזה פישל. אני לא יודע אם זה שינוי באלגוריתם שלהם (לחסום תגובות קצרות עם לינק אפילו אם הלינק הוא לפדפ?!) או שפשוט היה שם משהו שעורר את זה. אם יהיה לי זמן אני אנסה לבדוק.

    אורן

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

    יובל

  11. יובל,
    לא כתבתי אף פעם על אלגוריתם לסינון ספאם ממש, כתבתי ממש קצת על דרכים לסינון תגובות לפי כל מני קריטריונים אחרים. הכי קרוב שהגעתי לספאם ממש זה כאן – ספלוג וספינג: http://www.notes.co.il/oren/32766.asp

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

    אורן

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

    MuyaMan

  13. מויה –
    וואו, תודה על הלינק, לא הכרתי את הבלוג הזה. זה אחד הבלוגים היותר מושקעים (ותובעניים) שראיתי בעברית.

    אורן

  14. נודניק.
    ראיתי עכשיו שנתת אות חיים.
    התיחסתי שם.

    תמיר

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

    אורן

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

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

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

    תמיר

  17. המשפחה שלה ברישום (נניח), אבל המשפחה שלו מדרון אנריקה.

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

    אורן

  18. *שלו*?!
    יעני התחתנה?
    כדמו"י?!

    אני בשוק….
    אני בסופר…
    אני במכולת!

    לגבי התמונות, דווקא יותר חשבתי על זה:
    http://images.google.co.il/images?um=1&hl=iw&client=firefox-a&rls=org.mozilla%3Aen-US%3Aofficial&q=ugly&btnG=%D7%97%D7%A4%D7%A9+%D7%AA%D7%9E%D7%95%D7%A0%D7%95%D7%AA

    תמיר

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

    אורן

  20. אח, איזו דרך מעודנת להגיד: "בחיאת תמיר, עשה טובה ואל תעשה לי בושות בבלוג המעונב שלי"

    מת עליך!
    (-:

    תמיר

  21. מינוס כל – מעודנות זה שמי השני…

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

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

    ושלישית, התגובה הקודמת היא לא דוגמא ל"אל תעשה *לי* בושות" אלא ל"אל תעשה *לה* בושות".

    אורן

  22. לה, לי, בחייאת. להחליף נ' ב-מ', זאת הצפנה?

    בכככל מקרההה,

    א. פוסט מצויין

    ב. אחד ההישגים הגדולים של עדי שמיר היא ההוכחה ש- IP=PSPACE
    (שבפרט אומרת שבעזרת מספר שאלות פולינומיאלי ליריה כל-יכול אפשר לבדוק אם השחור יכול לנצח במשחק שח על לוח בגודל n על n כאשר המצב ההתחלתי נתוך כקלט)

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

    אלעד

  23. להחליף נ' ב-מ' נקרא מבטא…
    א. תודה.

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

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

    אורן

  24. Talking about me behind my back? You'd think I wouldn't read it late…

    Neta

להוספת תגובה