זמן לחתום (בתמצות) את סאגת אליס ובוב

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

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

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

כדאי להעיר מראש שיש שיטות להבטחת שלמות שאינן מתבססות על מפתח ציבורי - הן נקראות MAC (ראשי תיבות של Message Authentication Code), וגם להן יש שימושים לא מעטים. החסרון הבסיסי ב-MAC הוא החסרון הבסיסי של שיטות הצפנה שאינן מבוססות מפתח ציבורי - שני הצדדים, הן השולח והן המקבל, צריכים להחזיק במפתח משותף, ולכן צריכים שיטה כלשהי לשיתוף מפתח. יתר על כן, למרות שאפשר להשתמש ב-MAC כדי לאמת שקיבלת את ההודעה ממישהו שמכיר את המפתח, ושהיא לא שונתה בדרך (על ידי מישהו שלא מכיר את המפתח), יכולת אי-ההכחשה אובדת: גם אליס וגם בוב מחזיקים באותו מפתח, ולכן בוב יכול לחתום “בתור אליס” על הודעה (כי יש לו את כל המידע הסודי שיש לאליס).

אם כן, נחזור לחתימות ונעסוק רק בהן. הרעיון הבסיסי הוא פשוט ונאה למדי: אם פונקצית ההצפנה (הציבורית, זו שכל אחד יודע לעשות) היא \( E \), ופונקצית הפיענוח (הסודית, זו שרק בוב יודע לעשות) היא \( D \), אז הדרישה המיידית מהן היא שהן יקיימו \( D(E(x))=x \), אחרת הן לא שוות הרבה (מה הטעם בפונקצית פיענוח שלא מצליחה לפענח?). אבל אם כן, אז בפרט \( E(D(E(x)))=E(x) \), ומכאן קצרה הדרך לכך ש-\( E(D(x))=x \) (איזו הנחה חסרה כאן כדי להצדיק את המעבר האחרון? למה זו הנחה סבירה?). כלומר, פונקצית ההצפנה מסוגלת “לפענח” הודעות שקודם כל “הוצפנו” על ידי הפעלת פונקצית הפענוח עליהן.

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

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

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

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

קשה להמעיט בחשיבות כל המנגנון הזה. בלעדיו, כל מושג ה-Certificates שהזכרתי בפוסט הקודם לא היה יכול להתקיים: גם אם היה לך אישור לנכונות של מפתח פומבי שכתוב בו למעלה “המפתח הזה באמת שייך לבוב! אמת דיברתי תעשיות בע”מ” עדיין אי אפשר היה להיות בטוחים שזה לא אוסקר הנודניק שכתב את ה”אמת דיברתי” הזה. לעומת זאת, אם ה-Certificate חתום בידי “אמת דיברתי בע”מ”, זה כבר סיפור שונה לגמרי - כאן אפשר להיות בטוחים שזה באמת הם (והם לא יוכלו להכחיש אם נתבע אותם על כך שהם חתמו על Certificate שקרי).

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

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

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

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

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

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

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

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

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

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

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

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