ארכיון הקטגוריה: קריפטולוגיה

מה הקשר בין מספרים ראשוניים וקריפטוגרפיה?

פורסם בתאריך על ידי
15

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

מהו מספר ראשוני קל מאוד להגדיר: זה מספר טבעי גדול מ-1 שמתחלק רק ב-1 ובעצמו. למשל 2, או 17, או 131. לעומת זאת 57 אינו ראשוני כי הוא המכפלה של 3 ו-19. למה הראשוניים אמורים לעניין מישהו? ובכן, יש מספר סיבות. המיידית מביניהן היא שכל מספר טבעי גדול מ-1 ניתן להציג בתור מכפלה של ראשוניים באופן שהוא פחות או יותר יחיד. כך למשל את 57 אפשר לתאר בתור 3 כפול 19 או בתור 19 כפול 3, אבל פרט להיפוך הסדר הזה אין שום דבר שאפשר לעשות. כדי להבין מה מיוחד כאן כדאי לחשוב על מספר כמו 60, שאפשר להציג בתור 2 כפול 30 וגם בתור 4 כפול 15 – כלומר, שתי מכפלות שונות – אבל עדיין, הפירוק של 60 למכפלה של ראשוניים בלבד הוא יחיד (2 כפול 2 כפול 3 כפול 5). בשל התכונה הזו נהוג לומר על הראשוניים שהם "אבני הבניין" של כל המספרים הטבעיים. נראה בהמשך עוד תכונות של הראשוניים שהן מעניינות.

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

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

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

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

"כפל מודולו \(p\)" הוא דרך לתאר פעולת כפל רגילה של שני מספרים, שאחריה מחלקים את התוצאה ב-\(p\) ונשארים עם השארית. למשל, אם \(p\) הוא 17, אז 8 כפול 5 מודולו \(p\)יחזיר 6, שכן 8 כפול 5 הוא 40, וכשמחלקים ב-17 מקבלים מנה 2 ושארית 6. כפל מודולרי שכזה קל מאוד לממש במחשב, ויתרונו בכך שהוא נותן מבנה יפה לקבוצת המספרים מ-0 ועד \(p-1\), שאסמן מעתה ואילך ב-\(\mathbb{Z}_{p}\). מבחינה מתמטית המבנה הזה נקרא שדה, וזוהי דרך אחרת לומר שאפשר להגדיר עליהם פעולות של כפל וחיבור (גם חיבור מוגדר מודולו \(p\)) כך שכל כללי החשבון שאנחנו מכירים ואוהבים יתקיימו: כלל החילוף, כלל הקיבוץ וכלל הפילוג, ובנוסף לכך לכל איבר יהיה נגדי ביחס לחיבור (מספר שאם מחברים אותו למספר המקורי מקבלים 0; הנגדיים של המספרים הטבעיים ביחס לפעולת החיבור הרגילה הם המספרים השליליים) וחשוב מכל – לכל איבר יהיה הופכי ביחס לכפל, כלומר אפשר "לחלק". הנה דוגמה: אם אנחנו עובדים מודולו 17, אז כאשר כופלים את 5 ב-7 מקבלים 35, ואחרי חלוקה ב-17 ולקיחת שארית מקבלים 1. זה אומר ש-7 הוא ההופכי הכפלי של 5, ובמקום "לחלק ב-5" (פעולה שלא באמת מוגדרת עבור מספרים שלמים) אפשר לכפול ב-7.

עוד תכונה רלוונטית היא שלכל מספר ראשוני \(p\) קיים מספר \(g\) ששייך ל-\(\mathbb{Z}_{p}\) בעל התכונה שהחזקות \(g^{0},g^{1},\dots,g^{p-1}\), כשמסתכלים עליהן מודולו \(p\), הן בדיוק כל האיברים של \(\mathbb{Z}_{p}\) (למעט 0). מספר \(g\) כזה נקרא יוצר של \(\mathbb{Z}_{p}\).

עכשיו אפשר להסביר איך שיטת החלפת המפתחות של דיפי-הלמן עובדת: שני הצדדים, שאקרא להם אליס ובוב, מסכימים ביניהם על \(p\) ועל \(g\) מתאים עבורו (אין צורך לשמור אותם בסוד). אז אליס מגרילה לעצמה \(x\) ובוב מגריל לעצמו \(y\) ששניהם מספרים בין \(1\) ו-\(p-1\). עכשיו אליס מחשבת ושולחת לבוב את \(g^{x}\) ואילו בוב מחשב ושולח לאליס את \(g^{y}\). כעת כל אחד מעלה את המספר שהוא קיבל מהשני בחזקת המספר שהוא הגריל. למשל, אליס קיבלה את \(g^{y}\), אז היא תעלה את זה בחזקת \(x\), ומחוקי החזקות הרגילים, שמתקיימים גם עבור הכפל של \(\mathbb{Z}_{p}\) יתקיים \(\left(g^{y}\right)^{x}=g^{xy}\). באופן דומה החישוב של בוב יניב את \(\left(g^{x}\right)^{y}=g^{xy}\).

כך קרה שאליס ובוב מחזיקים כעת שניהם במספר משותף – \(g^{xy}\), אבל האם מישהו שציתת לתקשורת ביניהם יודע מהו? הוא יודע מהו \(g^{x}\) ומהו \(g^{y}\), אבל לא ברור איך לגלות מכך מהו \(g^{xy}\). על פניו, אפשר אולי לחשוב שאם התוקף יודע מהו \(g\) (זה הרי מידע פומבי) ויודע מהו \(g^{x}\) הוא יוכל לגלות מכך את \(x\), אבל זו בעיה קשה מבחינה חישובית, ואפילו יש לה שם – בעיית הלוגריתם הדיסקרטי. אפשר, כמובן, לנסות את כל הערכים האפשריים של \(x\) עד שמגיעים לאחד הנכון (להעלות את \(g\) בחזקה שלהם ולראות אם קיבלנו את \(g^{x}\)) ולכן חשוב שיהיו המון ערכים אפשריים של \(x\); כמו כן צריך להתגונן בפני שיטות חיפוש מחוכמות יותר (ויש כאלו) ולכן כדי שהשיטה של דיפי-הלמן תהיה בטוחה חייבים לעבוד עם מספר ראשוני \(p\) שהוא גדול יחסית – בן מאות ספרות (מספרים כמו 2048 ביטים או 4096 ביטים הם סדרי הגודל הנפוצים בימינו בדיבורים על ראשוניים בקריפטוגרפיה).

דיפי-הלמן ממחיש יפה איך ראשוניים עוזרים לנו בקריפטוגרפיה. לב-לבו של האלגוריתם הוא בכך שיש פונקציה שקל לחשב אבל קשה להפוך – העלאת \(g\) בחזקה, במקרה שלנו. התכונה היפה הזו קיימת ב-\(\mathbb{Z}_{p}\) אבל היא לחלוטין לא קיימת במספרים שלמים או ממשיים "רגילים". זו בדיוק הסיבה שהקריפטוגרפים נדחפו להשתמש במשהו כמו \(\mathbb{Z}_{p}\) – זה התגלה בתור "שדה משחק" מתאים לצרכים של הקריפטוגרפיה.

שנה אחרי דיפי והלמן התפרסם מאמר של ריבסט, שמיר ואדלמן (RSA) שהציג מערכת הצפנה פומבית של ממש. הרעיון של RSA היה שימוש בפונקציה מסוג שנקרא Trapdoor Function: פונקציה שקל לחשב ובאופן כללי קשה להפוך, אבל אם יש לך מידע (סודי) נוסף, היפוך שלה הופך לקל. באופן די מעניין, RSA עובד מעל \(\mathbb{Z}_{n}\) עבור \(n\) שאינו ראשוני, מה שאומר ש-\(n\) אינו שדה – לא תמיד אפשר לבצע בו חלוקה – אבל דווקא בגלל שהוא קצת "שבור" יש בו פונקציית מלכודת.

אם כן, הרעיון הוא כזה: נניח שאני רוצה להקים מערכת מפתח פומבי שבה כל העולם יוכל לשלוח לי דברים מוצפנים אבל רק אני אוכל לפענח. מה שאני עושה ראשית כל הוא למצוא שני מספרים ראשוניים גדולים \(p,q\). כעת אני כופל אותם ומקבל \(n=pq\). אחר כך אני מוצא זוג מספרים \(e,d\) בעלי התכונה ש-\(ed-1\) מתחלק ב-\(\left(p-1\right)\left(q-1\right)\). לא אסביר כעת את המתמטיקה המדויקת שמאחורי העניין, אך התכונה הזו של \(e,d\) מבטיחה שיתקיים הדבר הבא: \(\left(M^{e}\right)^{d}=M\), כאשר החשבון מבוצע מודולו \(n\).

כעת, אני מפרסם לעולם כולו את \(n\) ואת \(e\), אבל מותיר את \(d\) סודי. אם מישהו רוצה להצפין ולשלוח לי הודעה \(M\), הוא מחשב את \(M^{e}\) מודולו \(n\) ושולח לי. כדי לפענח, אני מעלה בחזקת \(d\) את מה שקיבלתי. פשוט להחריד. כאן פונקציית ה-Trapdoor היא פשוט העלאה בחזקת \(e\), וה"מידע נוסף" שהופך אותה לקלה להיפוך הוא \(d\).

כעת אנו מגיעים לנקודה שלדעתי גורמת לבלבול הגדול ביותר בקרב הטוקבקיסטים שציטטתי לעיל. כדי לבנות את מערכת ה-RSA, אחרי שמחליטים על \(n\) ועל \(e\) אפשר לחשב את \(d\) מתוך \(e\) ומתוך \(\left(p-1\right)\left(q-1\right)\). במילים אחרות, מי שמכיר את \(\left(p-1\right)\left(q-1\right)\) ואת \(e\) יכול לפרוץ את ההצפנה. קרוב לודאי שאתם מקבלים תחושה ש-RSA מאוד פגיעה בשל כך, אבל כדאי לזכור שב-RSA משתמשים כל הזמן, בכל מקום. אז למה זה עובד? כי גם אם יש לי את \(n=pq\), זה לא אומר שאני יכול לחשב מתוכו בקלות את \(\left(p-1\right)\left(q-1\right)\); הדרך הברורה לעשות זאת היא קודם כל לפרק את \(n\) לגורמים, כלומר למצוא את \(p,q\), אבל בעיית הפירוק לגורמים היא בעיה קשה. שימו לב: בעיית הפירוק לגורמים, לא בעיית בדיקת הראשוניות אלו שתי בעיות שונות, ובעיית הפירוק לגורמים מאז ומעולם נחשבה לקשה יותר.

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

התכונה נקראת "המשפט הקטן של פרמה" וקובעת שאם \(p\) הוא ראשוני ו-\(a\) הוא מספר כלשהו ב-\(\mathbb{Z}_{p}\), אז \(a^{p-1}=1\) (כשהחשבון הוא מודולו \(p\)). אם נתונים לנו \(p,a\) אז קל ומהיר למדי לבצע את החישוב של \(a^{p-1}\) (איך? זה עניין לפעם אחרת). אם נקבל משהו ששונה מ-\(1\), אז מובטח לנו ש-\(p\) לא היה ראשוני, למרות שאין לנו שום מחלק שלו. וזו רק תכונה אחת מני רבות. אנחנו מסתמכים כאן בצורה חזקה על כך שראשוניים הופכים מבנים מתמטיים ל"יפים", במובן זה שיש תכונות נחמדות מסויימות שמתקיימות בהם, ואם משהו משתבש לעתים קרובות קל לגלות זאת.

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

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

אפשר אולי עוד היה לקוות שגילוי הראשוני החדש יעיד על שיפור משמעותי ביכולת שלנו למצוא מספרים ראשוניים, אבל אפילו זה לא נכון. הראשוני הזה, כמו פחות או יותר כל הראשוניים הגדולים שהתגלו בעשורים האחרונים, הוא מצורה מאוד מיוחדת – \(2^{n}-1\) עבור ערך ספציפי של \(n\). ראשוני כזה נקרא ראשוני מרסן, וידועים בדיוק 48 כאלו – כמעט כלום. אם כן, איך קרה ה"מזל" הזה שהראשוני שנתגלה היה דווקא מהצורה הזו? כמובן שלא במקרה: יש אלגוריתם יעיל מאוד לבדיקה האם מספר מהצורה \(2^{n}-1\) הוא ראשוני או לא – יעיל משמעותית יותר מאלגוריתמים שמטפלים במספרים "כלליים", ולכן מוצלח יותר במציאת ראשוניים גדולים משמעותית מאלו שהשיטות הכלליות יודעות למצוא. אם כן, כדי למצוא "סתם" ראשוניים אקראים למערכת ההצפנה שלנו אין בכלל טעם להשתמש בו – אם אנחנו רוצים ראשוני שהוא מספר מרסן אנחנו פשוט יכולים לבחור מתוך הרשימה של הראשוניים הידועים, ואם חשוב לנו מספר אקראי, נצטרך להשתמש באלגוריתמים הרגילים.

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

ההרצאות שלי בפסטיבל אייקון 2012

פורסם בתאריך על ידי
6

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

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

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

אני מצרף גם את המצגות שהשתמשתי בהן בהרצאות.

 גיאומטריה לא אוקלידית: מלובצ'בסקי ועד קת'ולהו: מצגת ווידאו.

הצופן המדעי – קריפטוגרפיה במדע הבדיוני: מצגת ווידאו.

פנקס חד-פעמי – הצופן המושלם (?)

פורסם בתאריך על ידי
11

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

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

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

פנקס חד-פעמי היא שיטה פשוטה עד להפתיע. ראשית, בואו נחשוב שהכתב הגלוי הוא בסך הכל סדרה של ביטים: 0 ו-1. זה לא מופרך כמו שזה נשמע – כל קובץ טקסט במחשב מקודד כך, בסופו של דבר (בשיטה הפשוטה לייצג קבצי טקסט – ASCII – כל קבוצה של שמונה ביטים מייצגת תו בודד כלשהו). נניח שבכתב הגלוי יש בסך הכל \(n\) ביטים. ההצפנה שלו תשתמש במפתח שגם האורך שלו הוא \(n\) ביטים, ומה שנעשה יהיה לבצע פעולת XOR בין הביטים של הכתב הגלוי והביטים של המפתח.

מהי פעולת XOR? השם הוא קיצור של eXclusive-OR, אבל זה לא קריטי. הרעיון הוא שאם מבצעים XOR לשני ביטים בעלי אותו הערך התוצאה היא 0, ואם מבצעים אותו לשני ביטים בעלי ערך שונה התוצאה היא 1. כלומר, \(0\ \mbox{XOR }0=1\ \mbox{XOR }1=0\) ואילו \(1\ \mbox{XOR }0=0\ \mbox{XOR }1=1\).

דוגמה: נניח שהכתב הגלוי הוא \(0101\) והמפתח הוא \(1100\). אז ההצפנה מתבצעת על ידי לקיחת הביט הראשון של הכתב הגלוי (0) והביט הראשון של המפתח (1), ביצוע XOR והחזרת התוצאה (1) בתור הביט הראשון בכתב הסתר. לאחר מכן עושים אותו דבר לביט השני בכתב הגלוי (1) והמפתח (1) ומקבלים 0, וכן הלאה. תוצאת ההצפנה הסופית היא \(1001\). אפשר לכתוב את זה בפשטות בכתיב המתמטי הבא: \(0101\oplus1100=1001\).

באופן כללי, אם \(P\) הוא הכתב הגלוי, \(K\) הוא המפתח ו-\(C\) הוא כתב הסתר, אז הפעולה של פנקס חד-פעמי מתוארת על ידי \(C=P\oplus K\). עד כדי כך פשוט.

אפשר להכליל את השיטה הזו גם למקרה שבו \(P\) לא מורכב רק מאפסים ואחדים אלא, נאמר, מאותיות הא"ב. במקרה הזה נוח לחשוב על כל אות כמייצגת את המספר הסידורי שלה בא"ב פחות 1. למשל א' היא 0, ב' היא 1 ואילו ת' היא 21. כעת אפשר "לחבר" אותיות על ידי כך שמחברים את המספרים שלהן; אם התוצאה היא לפחות 22 פשוט נחסר ממנה 22. כלומר, \(21+1=22\) שהוא גדול מכדי לייצג אות ולכן נחשוב על התוצאה כעל \(21+1=0\) (ובדומה, \(17+9=4\), למשל). לחשבון המוזר הזה שבו אם חורגים מגבול כלשהו \(n\) פשוט מחסרים מהתוצאה \(n\) קוראים חשבון מודולרי ואומרים שזה חשבון מודולו \(n\) אם \(n\) הוא הגבול; אם תחשבו על זה, XOR הוא בעצם חשבון מודולרי מודולו 2.

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

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

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

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

בואו נסתכל על דוגמה, ועוד כזו שהיא הטריוויאלית ביותר שאפשר: הכתב הגלוי \(P\) יכול להיות או 0, או 1. כדי שיהיה מעניין, נניח שאנחנו יודעים שיש סיכוי של \(\frac{3}{4}\) שהוא יהיה 1 ורק סיכוי של \(\frac{1}{4}\) שהוא יהיה 0. כעת, המפתח \(K\) יכול להיות בעצמו או 0 או 1, עם הסתברות \(\frac{1}{2}\) לכל אחת מהאפשרויות.

בואו נניח שאנחנו מגרילים כתב גלוי ומפתח. מה ההסתברות שכתב הסתר יהיה 1, או בסימון מתמטי מהי \(\mbox{Pr}\left[C=1\right]\)? ובכן, \(C=1\) אם קורה אחד משניים: או ש-\(P\) מוגרל להיות 1 (בהסתברות \(\frac{3}{4}\)) ו-\(K\) מוגרל להיות 0 (בהסתברות \(\frac{1}{2}\)), או ש-\(P\) מוגרל להיות 0 (בהסתברות \(\frac{1}{4}\) ו-\(K\) מוגרל להיות 1 (בהסתברות \(\frac{1}{2}\)). בסך הכל נקבל \(\mbox{Pr}\left[C=1\right]=\frac{3}{4}\cdot\frac{1}{2}+\frac{1}{4}\cdot\frac{1}{2}=\frac{1}{2}\left(\frac{3}{4}+\frac{1}{4}\right)=\frac{1}{2}\) . באופן דומה נקבל שגם הסיכוי ל-\(C=0\) הוא \(\frac{1}{2}\).

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

נניח כעת שהתגלגל לידינו כתב סתר מוצפן, ונניח שהוא 1. מה ההסתברות, בהינתן המידע הזה, שהכתב הגלוי היה גם כן 1? בלשון מתמטית הסתברותית משתמשים במונח של הסתברות מותנית שתיארתי בעבר בבלוג. ההסתברות הזו היא ההסתברות שהכתב הגלוי יהיה 1 וגם כתב הסתר יהיה 1 (הסתברות זו היא \(\frac{3}{4}\cdot\frac{1}{2}\) – ההסתברות שהכתב הגלוי יהיה 1 כפול ההסתברות שיצא המפתח 0), חלקי ההסתברות שכתב הסתר יהיה 1. בניסוח מתמטי:

\(\mbox{Pr}\left[P=1\ |\ C=1\right]=\frac{\mbox{Pr}\left[P=1,C=1\right]}{\mbox{Pr}\left[C=1\right]}=\frac{\frac{3}{4}\cdot\frac{1}{2}}{\frac{1}{2}}=\frac{3}{4}=\mbox{Pr}\left[P=1\right]\)

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

כפי שאתם בוודאי מנחשים, התופעה הזו היא כללית, וזה גם הקריטיון של שנון כשהוא מנוסח פורמלי: צופן מושלם הוא צופן שבו מתקיים \(\mbox{Pr}\left[P=a\ |\ C=b\right]=\mbox{Pr}\left[P=a\right]\) לכל \(a,b\) שהם ערכים חוקיים שאותם \(P,C\) יכולים לקבל.

אם לכל כתב גלוי \(P=a\) וכתב סתר \(C=b\) קיים מפתח אחד ויחיד \(k_{a,b}\) שמעביר את \(a\) ל-\(b\), ואם הסתברות כל המפתחות שווה לאיזה ערך \(p_{K}\), אז ראשית כל

\(\mbox{Pr}\left[P=a,C=b\right]=\mbox{Pr}\left[P=a,K=k_{a,b}\right]=\mbox{Pr}\left[P=a\right]\cdot p_{K}\)

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

כעת, אם אשכנע אתכם ש-\(\mbox{Pr}\left[C=b\right]=p_{K}\) אסיים, כי ינבע מכך ש-\(\mbox{Pr}\left[P=a\ |\ C=b\right]=\frac{\mbox{Pr}\left[P=a,C=b\right]}{\mbox{Pr}\left[C=b\right]}=\frac{\mbox{Pr}\left[P=a\right]\cdot p_{K}}{p_{K}}=\mbox{Pr}\left[P=a\right]\) כנדרש. אם כן, אני רוצה להוכיח לכם שבלי תלות ב-\(P\), כתבי הסתר מתפלגים בצורה אחידה בדיוק כמו המפתחות.

ההוכחה הזו היא מה שכבר הזכרתי קודם וראינו איך הוא מתקיים במקרה הפשוט ביותר. בואו נסמן את הקבוצה של כל הכתבים הגלויים האפשריים ב-\(\mathcal{P}\). אז מתקיים:

\(\mbox{Pr}\left[C=b\right]=\sum_{a\in\mathcal{P}}\mbox{Pr}\left[P=a,K=k_{a,b}\right]=\sum_{a\in\mathcal{P}}\mbox{Pr}\left[P=a\right]\cdot p_{K}=p_{K}\cdot\left(\sum_{a\in\mathcal{P}}\mbox{Pr}\left[P=a\right]\right)=p_{K}\)

וזאת כי \(\sum_{a\in\mathcal{P}}\mbox{Pr}\left[P=a\right]=\mbox{Pr}\left[P\in\mathcal{P}\right]=1\), כי אנחנו יודעים בודאות ש-\(P\) מקבל ערך כלשהו מהקבוצה \(\mathcal{P}\).

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

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

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

וגם זה כנראה לא היה נורא ואיום לחלוטין אלמלא הדרישה מהמפתח הזה הייתה שהוא יהיה אקראי לגמרי. מפתח שאינו אקראי לגמרי, והתוקף יודע בערך למה לצפות מההתפלגות שלו, פותח פתח למתקפות על הצופן. זה לא אומר שחייבים מפתח אקראי לגמרי, אלא רק שאם לא משתמשים במפתח שהמקור שלו הוא אקראי לגמרי אז נשאלת השאלה איך מייצרים את המפתח הזה, ומדוע השיטה הזו בטוחה יחסית; בעצם, אפשר לחשוב על שיטת ייצור המפתח הזה בתור משהו שמגדיר צופן מסוג חדש, קצת יותר חלש מפנקס חד-פעמי ולכן גם לא מושלם. לצפנים כאלו קוראים צפני שטף (כי מה שהם עושים הוא לייצר "שטף" של מפתח אקראי שבעזרתו ניתן לבצע הצפנה דמויות פנקס חד-פעמי) וחלקם טובים מאוד – אבל הם לא מושלמים. אחד מה"גביעים הקדושים" של עולם הקריפטוגרפיה היא יצירה של מחולל מספרים פסאודו-אקראיים שיהיה בטוח קריפטוגרפית מבחינה תיאורטית (כיום יש הרבה מחוללים אבל אין הוכחה מתמטית לבטיחות שלהם), כי הוא יוביל ליצירת צופן שטף שאמנם לא יהיה מושלם, אבל גם מבחינה תיאורטית הוא לא יהיה ניתן לפיצוח (בקריפטוגרפיה מבדילים בין "בטוח מבחינת תורת האינפורמציה" – שזה מה שדיברנו עליו בפוסט עד כה – ובין "בטוח מבחינה חישובית" שזה המובן של "לא ניתן לפיצוח" כאן). כדאי להעיר שהוכחת קיום של מחולל כזה תגרור, בין היתר, ש-\(\mbox{P}\ne\mbox{NP}\). כלומר, הבעיה הזו קשה לפחות כמו הבעיה הפתוחה המרכזית במדעי המחשב.

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

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

דוגמה אחרת לבעייתיות שבשימוש בפנקס חד-פעמי באופן יומיומי היא מה שקורה כאשר אותם רוצים להצפין קובץ כלשהי במחשב שלכם – נאמר, קובץ ZIP או קובץ וורד שכתבתם. הרי אין לכם מפתח, אז מה עושים? משתמשים בססמא; אתם כותבים טקסט כלשהו שקל לכם לזכור, והמחשב ממיר אותו בדרך מסויימת למפתח שבו הוא משתמש לצורך ההצפנה והפענוח. אם הייתם רוצים להצפין עם פנקס חד פעמי, היה עליכם להשתמש בססמא שאורכה כאורך הדבר שאתם רוצים להצפין – אם כתבתם קובץ וורד של 1,000 אותיות, תצטרכו ססמא של 1,000 אותיות! ואם חשבתם על תעלול כמו לפתוח את המלט ולהעתיק את מה שקורה במערכה השניה, תשכחו מזה – המפתח לא יהיה אקראי לחלוטין ולכן ההצפנה לא תהיה מושלמת. אז איך בדיוק תוכלו לזכור 1,000 אותיות אקראיות? לא תוכלו, אתם תכתבו אותן אי שם – וססמא כתובה היא ססמא פגיעה, בעוד שססמא שזוכרים בראש היא פגיעה פחות. ההצפנה עצמה אמנם מושלמת, אבל זה לא אומר שאין סכנות "צדדיות" שיגרמו לפריצה שלה.

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

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

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

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

ושאינו יודע מה שאלו

פורסם בתאריך על ידי
14

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

הבעיה היא זו: נניח שיש לנו מסד נתונים מסויים, שלצורך פשטות נניח שהוא סדרה של \(n\) ביטים (ביט הוא יחידת מידע שהיא או 0 או 1 ותו לא). המידע שמור בשרת כלשהו, ואנו רוצים לדעת מהו הביט ה-\(i\). אנחנו יכולים לבקש מהשרת שישלח לנו את הביט ה-\(i\) וחסל – זה מה שקורה בדרך כלל במציאות – אבל יש כאן בעיה אבטחתית כלשהי: השרת (או מי שעוקב אחרי הגישה שלי לשרת) יודע בדיוק איזה מידע רציתי. זה מה שאנחנו רוצים למנוע.

אפשר לבלבל את האויב על ידי כך שאבקש גם את הביט ה-\(i\) וגם את הביט ה-\(j\) עבור איזה שהוא \(j\) שאני בוחר באקראי; אבל היריב שבצד השני עדיין מקבל מידע כלשהו – הוא יודע שאחד משני הביטים \(i,j\) מעניינים אותי. בקיצור, הוא למד משהו. אנחנו רוצים איכשהו לשלוף את המידע מהשרת בצורה כזו שבה היריב לא ילמד כלום. בלשון קצת יותר פורמלית, אנחנו רוצים בטיחות מושלמת, בטיחות במובן של תורת האינפורמציה. לא אציג כאן במדויק את ההגדרה הפורמלית (שאינה כה קשה) אבל הרעיון הוא שהתפלגות השאילתות שאני מפנה לשרת תהיה זהה בלי תלות בביט \(i\) שאני רוצה לקרוא.

איך עושים את זה?

טוב, הפתרון המיידי כנראה קופץ לרובכם לראש מייד – פשוט תבקש מהשרת את כל \(n\) הביטים ששמורים בו, וזהו; היריב לא לומד בכך כלום על זהות הביט \(i\) שאתם רוצים (הוא לומד, כמובן, שאתם רוצים ביט כלשהו מתוך ה-\(n\)-ים; אבל אם פניתם לשרת זה היה ברור מלכתחילה וזה לא משהו שאפשר לשפר). השיטה הזו היא בזבזנית למדי – סיבוכיות התקשורת שלה (כמות הביטים שנשלחים מצד לצד) היא \(O\left(n\right)\), וזו לא סיבוכיות טובה במיוחד (חשבו על סיטואציה שבה מסד הנתונים הוא בן כמה טרהבייטים של מידע ואנחנו צריכים לשאול כ-1,000 שאילתות ביום ויש עוד הרבה משתמשים כמונו). בפוסט הזה אני רוצה להציג שיפור שנובע מהקלה בכללי המשחק – נניח שיש יותר משרת אחד שבו מסד הנתונים מאוחסן, ונניח (וזו הנחה לא טריוויאלית) שאין קשר בין השרתים, דהיינו שהאויב המרושע שלנו מצותת רק לאחד מהם (במקרה הכי גרוע על כל שרת מתעלק אויב מרושע אחר, אבל כל אויב מרושע כזה יודע רק על מה שקורה בשרת "שלו"). האם עכשיו אפשר לשפר? התשובה היא שכן, משמעותית.

איך עושים את זה?

בואו נתחיל מהמקרה שבו יש לנו שני שרתים. הפתרון עדיין יהיה בעל סיבוכיות תקשורת \(O\left(n\right)\) אבל יהיה קל להכליל אותו אחר כך לפתרון שנותן שיפור משמעותי כשמספר השרתים גדול יותר. באופן די מפתיע, עכשיו יהיה די לנו בכך שכל שרת ישלח לנו ביט בודד, וסיבוכיות התקשורת תהיה טמונה בכך שאנחנו נצטרך לשלוח להם הרבה מידע. השיטה פשוטה: נגריל סדרה \(S_{0}\) של \(n\) ביטים כשהערך של כל ביט נבחר בהסתברות שווה בין 0 ו-1 ובאופן בלתי תלוי ביתר, נבנה סדרה \(S_{1}\) הזהה ל-\(S_{0}\) פרט לכך שהערך של הביט במקום ה-\(i\) הפוך, ונשלח את \(S_{0}\) לשרת הראשון ואת \(S_{1}\) לשרת השני. כל שרת יבצע פעולת XOR לביטים שהאינדקס שלהם בסדרה שהוא קיבל מסומן ב-1, וישלח חזרה את התוצאה. כשנקבל את התוצאה משני השרתים נבצע לה XOR, וגמרנו.

למי שלא מכיר, פעולת XOR בין שני ביטים (מלשון Exclusive Or) היא פעולה שלוקחת שני ביטים ומחזירה 1 רק אם ערכיהם שונים, ו-0 אם הם זהים (כלומר, \(0\oplus0=0\) ו-\(1\oplus1=0\) אבל \(1\oplus0=0\oplus1=1\)). הסיבה שבגללה השיטה עובדת היא שכל ביט \(j\) שאיננו הביט שרצינו או שמופיע ב-XOR של כל אחד משני השרתים ולכן שני המופעים שלו מבטלים זה את זה, או שהוא אינו מופיע כלל ולכן אינו משפיע. היחיד שבא לידי ביטוי באחד השרתים אבל לא בשני הוא הביט ה-\(i\). נסו זאת בעצמכם על מקרים פרטיים פשוטים (למשל \(n=3\)) ותראו שזה עובד.

הסיבה שזה גם בטוח היא פשוטה – \(S_{0}\) היא סדרה אקראית לחלוטין. לא קשה להראות שגם \(S_{1}\) מתפלגת באופן אחיד. מי שרואה רק את \(S_{0}\) או רק את \(S_{1}\) רואה, אם כן, רצף ביטים אקראי לגמרי; כדי להפיק מידע כלשהו הכרחי לראות את שניהם גם יחד. זו תופעה דומה לזו שיש בצופן פנקס חד פעמי, או בשיתוף סוד.

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

בואו נניח שיש לנו 4 שרתים. נניח גם, לצורך פשטות, ש-\(n\) הוא ריבוע של מספר טבעי כלשהו, כלומר \(n=k^{2}\) (תמיד אפשר להגדיל את \(n\) עד לריבוע הקרוב ביותר). כעת אפשר לחשוב על מסד הנתונים לא בתור שורה ארוכה של ביטים שלכל אחד אינדקס מ-1 ועד \(n\); במקום זה אפשר לחשוב על טבלה של ביטים שלכל אחד מהם שני אינדקסים – שורה ועמודה, ששניהם מספרים מ-1 ועד \(k\).

כעת לתעלול. נניח שאנחנו רוצים את הביט שבשורה ה-\(i\) ובעמודה ה-\(j\). אנחנו מגרילים שתי סדרות, \(S_{0}^{1},S_{0}^{2}\), בראשונה אנו הופכים את הביט שבמקום ה-\(i\), בשניה את הביט שבמקום ה-\(j\) ומקבלים שתי סדרות חדשות \(S_{1}^{1},S_{1}^{2}\). כעת אנו שולחים לשרת הראשון את \(\left(S_{0}^{1},S_{0}^{2}\right)\); לשרת השני את \(\left(S_{1}^{1},S_{0}^{2}\right)\); לשלישי את \(\left(S_{0}^{1},S_{1}^{2}\right)\) ולרביעי את \(\left(S_{1}^{1},S_{1}^{2}\right)\). אתם כבר מצליחים לנחש מה הם ישלחו בחזרה?

כל שרת שולח בחזרה את ה-XOR של הביטים שנמצאים בתת-הטבלה שמתקבלת אם מצטמצמים רק לאותן שורות ועמודות שהאינדקסים שלהן היו 1 בסדרה המוגרלת. כמקודם, כל ביט שאיננו במקום ה-\(\left(i,j\right)\) מופיע בפלטים ששולחים אלינו מספר זוגי של פעמים (לא בהכרח 4 או 0; נסו לבנות דוגמה שבה ביט שכזה נשלח בדיוק פעמיים), ואילו רק הביט במקום \(\left(i,j\right)\)נשלח פעם אחת בדיוק. לכן ביצוע XOR לכל הפלטים שקיבלנו מניב בדיוק את הביט שרצינו. הבטיחות נובעת מאליה מאותם שיקולים כמו קודם.

מה הסיבוכיות הפעם? ובכן, לכל שרת אנו שולחים שתי סדרות של \(k\) ביטים, ולכן בסך הכל אנו שולחים \(8k\) ביטים. אלא שכזכור, \(k^{2}=n\) ולכן סיבוכיות התקשורת שלנו היא \(O\left(\sqrt{n}\right)\) – וזה שיפור משמעותי מאוד ביחס ל-\(n\). אם מסד הנתונים הוא בגודל של טרהבייט, אנחנו שולחים רק 8 מגהבייט; אני משער שתסכימו שזה שיפור משמעותי ביותר.

אבל למה לעצור בדו מימד? אפשר להכליל את השיטה גם ל-\(d\) ממדים. אם עומדים לרשותנו \(2^{d}\) שרתים, אנו בונים שתי סדרות של סדרות \(\left(S_{0}^{1},\dots,S_{0}^{d}\right)\) ו-\(\left(S_{1}^{1},\dots,S_{1}^{d}\right)\), שולחים לשרתים את כל האפשרויות (כל האפשרויות לסדרה של \(d\) סדרות שהאיבר הראשון שלה הוא אחד מבין \(S_{0}^{1},S_{1}^{1}\), השני הוא אחד מבין \(S_{0}^{2},S_{1}^{2}\) וכן הלאה) ועושים XOR לתוצאה. כאן מתקיים \(n=k^{d}\) ולכן סיבוכיות התקשורת שלנו היא \(O\left(\sqrt[d]{n}\right)\). עם זאת, כדאי להתייחס גם ל-\(d\) כחלק מהפרמטר שמודד את הסיבוכיות, מכיוון שאי אפשר להגדיל את \(d\) באופן חופשי בלי מחיר – מספר השרתים קופץ משמעותית כשמגדילים את \(d\) (מוכפל פי שתיים בכל פעם שבה מגדילים את \(d\) ב-1) וכך גם סיבוכיות התקשורת גדולה – לכל שרת שולחים \(d\cdot k\) ביטים, ולכן בסך הכל הסיבוכיות היא \(O\left(d\cdot2^{d}\cdot\sqrt[d]{n}\right)\) ביטים.

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

אז מה הקטע עם המאגר הביומטרי?

פורסם בתאריך על ידי
43

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

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

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

ב-27 באוקטובר 2008 הגישה הממשלה לכנסת את הצעת חוק הכללת אמצעי זיהוי ביומטריים במסמכי זיהוי ובמאגר מידע, התשס"ט-2008 . הצעת החוק אושרה בקריאה הראשונה, והועברה לוועדת החוקה, חוק ומשפט, אך זו לא הספיקה לדון בה בטרם התפזרה הכנסת ה-17. ח"כ מאיר שטרית, שכשר הפנים קידם את הצעת החוק בכנסת ה-17, הגיש אותה מחדש, בנוסח זהה, כהצעת חוק פרטית בכנסת ה-18 אך על הצעת החוק הממשלתית הוחל דין רציפות, ולאחר שעברה בין מספר ועדות, הוחלט לבסוף כי הוועדה שתדון בה תהיה ועדה משותפת לוועדת המדע והטכנולוגיה ולוועדת הפנים, בראשותו של יושב ראש ועדת המדע, מאיר שטרית. בדצמבר 2009 אושר החוק, ונקבע שהוא ייכנס לתוקף ב-1 בינואר 2010 (או מאוחר יותר, לפי צו של שר הפנים), ובלבד שאושרו תקנות לפי סעיפים אחדים בו. נקבע שעל השר הממונה להגיש תקנות אלה לאישור ועדת הכנסת העוסקת בכך עד 15 באפריל 2010, אולם רק ב-16 במאי 2011 אישרה הממשלה את התקנות, וב-2 ביוני 2011 אושרו התקנות בוועדת המדע של הכנסת.

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

מה הבעיה שהמאגר בא לפתור?

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

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

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

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

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

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

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

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

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

ועוד שימוש אפשרי שמוזכר הוא זיהוי גופות:

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

מה היקף הבעיה הזו? ובכן:

מאיר שטרית: אגיד לך משהו שיזעזע אותך. במכון לרפואה משפטית יש דגימות של כ-‎250 או ‎400 איש שמתו בלתי מזוהים. יש דגימות שלהם ואף אחד לא יודע מי הם. 

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

לשטרית יש תשובה – לטענתו מהדיון כאן מה-7 ביולי 2009 – שבוע אחרי הדיון המרכזי שאני מצטט רוב הזמן:

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

אוקיי. הבה ונזכור זאת להמשך.

אילו פתרונות יש לעניין זיוף התעודות?

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

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

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

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

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

…

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

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

יורם אורן העיר ש"הבעיה הפרקטית האמיתית היא שלאותו אדם יש כמה מספרי תעודות זהות". האם יש פתרון לזה?

אלי ביהם: 

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

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

…

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

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

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

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

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

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

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

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

במה המאגר עדיף על האלטרנטיבות?

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

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

מהדיון של ה-30 ליוני:

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

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

…

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

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

…

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

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

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

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

מה הסיכון שהמאגר ידלוף?

כל שאלה שעוסקת באבטחת מידע חייבת להתחיל עם הקומיקס הבא:


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

אם כן, האם המאגר יהיה מאובטח מפני פריצה של האקר מחוכם שהוא גם גאון מחשבים וגם גאון בתורת המספרים וגם ג'יימס בונד? מהדיון של ה-7 ביולי, 2009:

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

…

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

…

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

…

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

…

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

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

…

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

…

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

…

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

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

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

מייק בלאס, בדיון של ה-30 ביוני:

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

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

אבל יורם אורן הוא חכם וחשב גם על זה – הפתרון שהוא מציע הוא הפרדת כוחות. המאגר יורכב מכמה חלקים. מה-12 ביולי 2009:

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

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

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

ונניח שרק המאגר עם המידע הביומטרי יודלף, מה אז? מהדיון של ה-7/7:

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

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

מה יקרה אם המאגר ידלוף?

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

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

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

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

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

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

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

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

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

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

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

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

…

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

מה יורם הזכיר? ובכן:

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

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

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

חזרה אל המאמר של אלי ביהם:

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

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

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

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

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

בקשר לאח הגדול…

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

אז איך באמת בודקים ראשוניות (בעזרת אלגוריתם מילר-רבין)?

פורסם בתאריך על ידי
28

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

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

הדרך הפשוטה לבדוק ראשוניות של מספר \(n\) היא לעבור אחד אחד על כל המספרים הקטנים מ-\(n\) אבל גדולים מ-1 ולבדוק אם הם מחלקים אותו ללא שארית. אם נמצא כזה, המספר אינו ראשוני (זו ההגדרה של ראשוני – מספר המתחלק רק בעצמו וב-1). לתעלול הזה יש אופטימיזציה פשוטה – אם \(a\) מחלק את \(n\), כך גם \(n/a\) (כי מה זה אומר ש-\(a\) מחלק את \(n\)? שקיים \(b\) כך ש-\(n=ab\), כלומר גם \(b=n/a\) מחלק את \(n\) ללא שארית), ואם \(a\) גדול מהשורש של \(n\), אז \(b\) יהיה קטן ממנו (כי אם \(a,b>\sqrt{n}\) אז \(n=a\cdot b>\sqrt{n}\cdot\sqrt{n}=n\) – סתירה). לכן מספיק לבדוק את המספרים הקטנים מ-\(n\) "עד השורש" של \(n\). זמן הריצה של האלגוריתם הזה יהיה \(O\left(\sqrt{n}\right)\), זמן ריצה שנחשב טוב מאוד כשמתעסקים באלגוריתמים (להשוואה, זמן הריצה של אלגוריתמי המיון הכלליים הוא \(O\left(n\log n\right)\)). אם כן, מה הבעיה?

הבעיה היא שבכל הנוגע למספרים, מה שחשוב הוא לא גודל המספר עצמו אלא גודל הייצוג שלו – מספר הביטים שדרושים כדי לאחסן אותו בזכרון. כדי לאחסן את \(n\), צריך \(\lg n\) ביטים (\(\lg\) הוא לוגריתם על בסיס 2 – אם \(\lg n=k\) זה אומר ש-\(n=2^{k}\); כמובן ש-\(k\) עשוי שלא להיות מספר שלם, אז נעגל למעלה כשנצטרך להתייחס אליו כשלם). הסיבה שגודל הייצוג הוא מה שחשוב היא שהזמן שלוקח לבצע פעולות חשבון בסיסיות על מספרים – חיבור, חיסור, כפל, חילוק, השוואה בין שני מספרים – נמדד ביחס ל-\(\lg n\), לא ל-\(n\). למשל, השוואה של שני מספרים דורשת \(\lg n\) פעולות (חשבו על הצורה שבה אתם משווים שני מספרים שנתונים בבסיס עשרוני – אתם פשוט משווים ספרה ספרה), חיבור שלהם דורש \(\lg n\) פעולות (מחברים "ספרה ספרה" ולכל היותר זוכרים בע"פ שצריך להוסיף 1 לתוצאת החיבור הבאה), כפל דורש (במימוש נאיבי, כמו זה שתלמידים בבית הספר לומדים לבצע) \(\lg^{3}n\) פעולות, וכדומה. זה אומר שקל לנו לבצע פעולות על מספרים ענקיים, בני 500 ספרות ויותר (וגם מספרים בני מיליון ספרות הם עדיין משהו שאפשר להתמודד איתו), בזמן שלעבור על כל המספרים בני 500 ספרות, אפילו "עד השורש", זה לחלוטין לא פרקטי. זו הייתה גם הנקודה המרכזית בפוסט הקודם שלי.

אם כן, אלגוריתם טוב לבדיקת ראשוניות צריך להיות בעל זמן ריצה שהוא לכל היותר חזקה כלשהי ב-\(\lg n\). כזה הוא מילר רבין, שזמן ריצתו חסום על ידי \(O\left(\lg^{3}n\right)\) (זמן ריצה מעולה עבור אלגוריתם שמבצע בדיקה של דבר מה "מסובך" כראשוניות). אלגוריתם AKS המפורסם לבדיקת ראשוניות – היחיד שידוע כיום שעובד באופן דטרמיניסטי ובזמן "סביר" לכל הראשוניים – דורש זמן ריצה של מעט יותר מ-\(O\left(\lg^{6}n\right)\), כלומר הוא פחות יעיל בכמה סדרי ממילר-רבין, ולכן עדיין מעדיפים את מילר-רבין בשימושים פרקטיים (דוגמת זה של הספריה OpenSSL שקישרתי אליה בפוסט הקודם). זה לא אומר שאין יישומים של AKS או שאי אפשר להשתמש בו אם רוצים לוודא ב-100 אחוזים סופר-דופר שמספר הוא ראשוני; אבל כמו שאסביר בהמשך (בפוסט נפרד), האקראיות של מילר-רבין נותנת 99 אחוזים (למעשה, אפילו יותר – אבל על כך בפוסט הבא) שלרוב הוא די והותר בשבילנו (ופרט ל-AKS יש עוד מבחנים שמוכיחים בודאות שמספר הוא ראשוני, אך לא מובטח שהם תמיד יעבדו בזמן פולינומי למרות שלעתים קרובות הם מהירים למדי, וגם על זה אפרט בעתיד).

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

אלא שהגישה הזו היא ללכת עם הראש בקיר, בראש ובראשונה כי היא לא מנסה לפתור את בעיית בדיקת הראשוניות אלא בעיה אחרת, קשה ממנה – בעית הפירוק לגורמים: בהינתן \(n\), למצוא מחלק לא טריוויאלי של \(n\) (ה"טריוויאליים" הם 1 ו-\(n\) עצמו). בעיית הפירוק לגורמים היא בעלת היסטוריה מרתקת משל עצמה ואלגוריתמים מחוכמים משל עצמה שפותרים אותה; אבל אף אחד מהם עדיין לא נחשב "יעיל" במובן זה שהוא פולינומי ב-\(\lg n\), וגם הם פועלים בצורה שונה מסתם בדיקה של מספרים שהם בעלי פוטנציאל לחלק את \(n\) (בתור התחלה, הם מסתמכים על כך שדי למצוא מספר \(m\) שאינו זר ל-\(n\) ואינו מתחלק על ידו, כלומר שיש להם מחלק משותף לא טריוויאלי שהוא גם מחלק לא טריוויאלי של \(n\); אם נמצא \(m\) כזה, קל למצוא את המחלק המשותף המדובר באמצעות האלגוריתם האוקלידי. על כל זה אפשר וכדאי להרחיב בפעם אחרת).

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

האתגר הוא כמובן למצוא תכונות "גלובליות" שכאלו, ומה שמילר-רבין עושה למעשה הוא להשתמש בשתי תכונות גלובליות שונות; כשהאחת נכשלת (במובן זה של "לא מספקת עדות טובה לכך שהמספר לא ראשוני"), מובטח שהשניה תעבוד לעתים קרובות; ומה שנחמד הוא שאפשר לבדוק את שתיהן גם יחד. נתחיל מהתכונה הראשונה – היא מתבססת על מה שמכונה "המשפט הקטן של פרמה" שהוא האבחנה שעבור כל מספר ראשוני \(p\) וכל מספר אחר \(a\) שאינו מתחלק בידי \(p\), מתקיים ש-\(a^{p-1}-1\) מתחלק על ידי \(p\). למשל, אם ניקח \(p=5\), נקבל שכל מספר \(a\) שאינו מתחלק ב-5 מקיים ש-5 מחלק את \(a^{4}-1\) (קחו \(a=2\); \(2^{4}-1=16-1=15\) שמתחלק ב-5, וכו' וכו'). בניסוח מודרני מסמנים זאת כ-\(a^{p-1}\equiv_{p}1\) (קראו את השוויון שבאמצע כ"שקול מודולו \(p\)" – המשמעות הפורמלית היא בדיוק שהפרש שני האגפים מתחלק ב-\(p\), או אם תרצו, שחלוקת כל אחד מהאגפים ב-\(p\) נותן את אותה שארית).

פרמה גילה את המשפט מתוך משחקים במספרים והעלאת השערות; אוילר הוכיח לאחר מכן גרסה כללית יותר שלו, התקפה לכל מספר \(n\) ולא רק לראשוניים; בגרסה זו, החזקה שבה מעלים את \(a\) היא שונה (היא \(\phi\left(n\right)\) – פונקצית אוילר של \(n\), למי שמכיר) והיא תהיה \(n-1\) אך ורק אם \(n\) ראשוני. אם כן, יש לנו קריטריון כלשהו לראשוניות: \(n\) אינו ראשוני אם \(a^{n-1}-1\) לא מתחלק על ידי \(n\). לכן אלגוריתם לבדיקת ראשוניות \(n\) (אלגוריתם אמיתי, שנקרא על שם פרמה) יעבוד כך: בהינתן \(n\), הגרל \(a\) שאינו מתחלק על ידי \(n\), חשב את \(a^{n-1}-1\) ובדוק אם הוא מתחלק ב-\(n\). אם לא, מובטח ש-\(n\) לא ראשוני. אם כן, בסבירות לא רעה \(n\) ראשוני (על עניין הסבירויות ארחיב בהמשך). מצאנו את האלגוריתם שרצינו.

האמנם?

צריך להיות זהירים פה. אמנם, המשפט של אוילר לא עובד עבור החזקה \(n-1\) אם \(n\) אינו ראשוני, אבל זה רק אומר שלא מובטח לנו שמתקיים \(a^{n-1}\equiv_{n}1\); זה בכל זאת עשוי לקרות לפעמים (למשל, אם \(a=1\) זה יקרה תמיד). מה שהיינו רוצים שיקרה הוא שתתקיים תוצאה כמו "אם \(n\) אינו ראשוני, אז יש המון ערכים של \(a\) שעבורם \(a^{n-1}-1\) אינו מתחלק ב-\(n\)" כי כל מספר \(a\) כזה "מוכיח" לנו ש-\(n\) אינו ראשוני. זה נכון לעתים קרובות; אלא שלרוע המזל, זה לא נכון תמיד. למעשה, יש מספרים פריקים שעבורם לכל \(a\) (שאין לו ול-n מחלקים משותפים, אבל הסיכוי להגריל \(a\) כזה הוא כמו הסיכוי לפרק לגורמים את \(n\) "במזל") מתקיים \(a^{n-1}\equiv_{n}1\), כלומר מספרים פריקים ש"בכל זאת" מקיימים את המשפט הקטן של פרמה ככתבו וכלשונו. למספרים הללו קוראים מספרי קרמייקל; הקטן ביותר שבהם הוא 561. התכונות שלהם ידועות לא רע – למשל, ניתן להוכיח די בקלות שכל מספר קרמייקל חייב להיות מכפלה של ראשוניים אי זוגיים שונים זה מזה (כלומר, מספר כמו \(3\cdot3\) או \(2\cdot3\) הוא מחוץ למשחק מראש); לא ניכנס לזה עכשיו. הנקודה היא שיש קבוצה ספציפית של מספרים "מרגיזים", עם אפיונים ספציפיים משל עצמה, שעבורם השיטה של משפט פרמה נכשלת לחלוטין.

אז מה עושים? מחפשים עוד קריטריון ש"מתקלקל" כש-\(n\) אינו ראשוני. לכאורה חזרנו לנקודת ההתחלה, אבל למעשה מצבנו טוב יותר מאשר קודם, כי המבחן של הקריטריון הנוכחי נותן לנו מוטיבציה לקריטריון הבא. לשם כך עלינו להסביר קודם כל איך בדיוק אפשר לבדוק את הקריטריון של פרמה. אמרתי קודם שהבדיקה פשוטה – מגרילים \(a\) ומחשבים את \(a^{n-1}-1\), אבל איך עושים את זה אם \(n\) עצום? יש כאן שתי בעיות מהותיות – ראשית, אם \(n\) עצום, גם \(a^{n-1}-1\) יהיה עצום – אבל עצום ברמה גדולה פי כמה, כך שלא יהיה שום סיכוי לשמור אותו במחשב; ושנית, זמן החישוב של \(a^{n-1}-1\) יהיה גם הוא עצום אם ננקוט בשיטה הנאיבית – לכפול את \(a\) בעצמו \(n-1\) פעמים. כבר עדיף לעבור על כל המספרים שקטנים מ-\(n\) וחסל. אם כן, מה עושים?

הפתרון לבעיה הראשונה פשוט. לא חייבים לחשב את \(a^{n-1}\) עצמו; אפשר להסתפק בחישוב השארית של \(a^{n-1}\) כשהוא מחולק ב-\(n\). הצורה שבה עושים זאת פשוטה – במהלך החישובים שלנו, בכל פעם שבה מתקבל מספר גדול מ-\(n\), פשוט מחלקים אותו ב-\(n\) ומשאירים רק את השארית. לא קשה לראות שזה עובד. בפועל מה שאנחנו עושים כאן הוא להפסיק לעבוד עם שלמים ולהתחיל לעבוד עם מה שנקרא "חוג השלמים מודולו \(n\)". לצורך העניין מספיק לחשוב עליהם בתור אוסף כל המספרים הטבעיים הקטנים מ-\(n\) עם פעולות החיבור והכפל הרגילות, פרט לכך שאחרי שהן מבוצעות מחלקים ב-\(n\) ולוקחים את השארית. מעכשיו בכל פעם שבה אכתוב משהו כמו \(a^{n-1}\) הכוונה יהיה לאיבר שמקבלים באותה חבורה אחרי ש-\(a\) מועלה בחזקת \(n-1\); ואם אכתוב \(-1\), הכוונה יהיה לאיבר המקביל לו בחבורה הזו, שהוא \(n-1\) (הם מייצגים את אותו האיבר שכן ההפרש שלהם מתחלק ב-\(n\)). מכיוון שכל המספרים שעובדים איתם הם קטנים מ-\(n\) (שהוא מספר "סביר" מבחינת זה שפעולות החשבון הרגילות קלות לביצוע עבורו), נפטרנו מהבעיה הראשונה.

כעת לבעיה השניה. האבחנה המרכזית כאן היא שלא חייבים לכפול את \(a\) בעצמו \(n-1\) פעמים כדי לחשב את \(a^{n-1}\). הנה דוגמה פשוטה לדרך שבה אפשר לבצע קיצורים: נניח שאני רוצה לחשב את \(a^{16}\) במעט פעולות כפל. מה שאעשה יהיה ראשית לכפול את \(a\) בעצמו ולקבל \(a^{2}\). כעת, במקום לכפול את התוצאה שוב ב-\(a\), אכפול את התוצאה בעצמה, כלומר אבצע את החישוב \(a^{2}\cdot a^{2}=a^{4}\). את התוצאה שוב אכפול בעצמה ואקבל \(a^{8}\), ואת זה שוב אכפול בעצמו ואקבל \(a^{16}\). סיימנו, וביצענו רק ארבע פעולות כפל במקום שש עשרה.

בואו ננסה משהו יותר מתוחכם. נניח שאנחנו רוצים לחשב את \(a^{13}\) עכשיו. מה עושים? פתרון פשוט הוא זה: כבר חישבנו לפני רגע את \(a^{4}\) ואת \(a^{8}\), אז פשוט נכפול אותם זה בזה וב-\(a\) ונקבל \(a\cdot a^{4}\cdot a^{8}=a^{13}\). כאן הסתמכנו על כך שניתן לכתוב את 13 כסכום של חזקות של 2: \(13=1+4+8\). מכיוון שאפשר לכתוב כל מספר באמצעות סכום של חזקות של 2 (זוהי פשוט ההצגה של המספר בבסיס בינארי), התעלול הזה עובד תמיד. הפאנץ' הוא שאם אנחנו רוצים להעלות בחזקת \(n\) מספר כלשהו, אנחנו צריכים לחשב רק \(\lg n\) איברים של \(a\) בחזקת חזקות של 2 (למה? כי אנחנו צריכים את כל החזקות מהצורה \(2^{i}\) עבורן \(2^{i}\le n\), כלומר \(i\le\lg n\)) ולכפול את החזקות הרלוונטיות.

מה שאלגוריתם מילר-רבין עושה הוא לחשב את \(a^{n-1}\) בצורה דומה מאוד אבל לא זהה לגמרי – יש עוד טוויסט אחד, שהוא זה שעושה את כל ההבדל. הנה עוד דוגמה – נניח שאנחנו רוצים לחשב את \(a^{24}\). אפשר לעשות זאת בשתי דרכים: או לחשב את \(a^{8}\) ו-\(a^{16}\) ולכפול אותם, כפי שכבר ראינו; אבל אפשר גם לחשב את \(a^{3}\) ואז להעלות אותו שוב ושוב בריבוע, עד שמגיעים ל-\(a^{24}\). כדי להבין למה זה עובד, נשים לב לכך ש-\(24=3\cdot2^{3}\). כלומר, אפשר לכתוב את המספר הזה בתור מכפלה של מספר אי זוגי וחזקה כלשהי של 2, ואז \(a^{24}=\left(a^{3}\right)^{2^{3}}\), כלומר ניתן לכתוב את \(a^{24}\) בתור העלאה בריבוע שלוש פעמים ברצף של \(a^{3}\). זה עובד גם באופן כללי, כמובן: כדי לחשב את \(a^{n-1}\) אפשר לכתוב \(n-1=m\cdot2^{k}\) כאשר \(m\) אי זוגי, ואז לחשב את \(a^{m}\), ואותו להעלות בריבוע \(k\) פעמים. כשמסיימים, בודקים אם קיבלנו 1 או לא.

אבל למעשה, אפשר לקצר את התהליך. נניח שחישבנו את \(a^{m}\) וקיבלנו 1; אז גם כשנעלה אותו בריבוע, ולא משנה כמה פעמים, נקבל 1. לכן אפשר לעצור כבר כאן ולהגיד שהמבחן הצליח (כלומר, נתן לנו תחושה טובה בבטן ש-\(n\) הוא ראשוני). באופן דומה, אם חישבנו את \(a^{m}\) וקיבלנו \(-1\) אפשר לעצור – אחרי העלאה אחת בריבוע נקבל 1, ומכאן ואילך נמשיך לקבל 1. באותו אופן, אם \(a^{m}\) לא היה לא \(1\) ולא \(-1\), היינו מצפים שמתישהו במהלך ההעלאות בריבוע שלו נקבל 1, וכאן נמצא לב לבו של מילר-רבין, והקריטריון הנכסף שלנו – איך מספר \(x\) שקודם לכן לא היה 1 הופך ל-1 אחרי שמעלים אותו בריבוע (מודולו \(n\))? מה \(x\) יכול להיות?

תשובת המחץ היא זו: אם \(n\) הוא ראשוני, \(x\) יכול להיות רק \(1\) (אבל אמרנו שהוא לא) או \(-1\) (שכזכור, מסמן את \(n-1\)). לעומת זאת, אם \(n\) אינו ראשוני, יכולים להיות ערכים נוספים שמקיימים זאת – "שורשים לא טריוויאליים של 1". לדוגמה, אם \(n=8\) אז מתקיים די בבירור \(7^{2}=49\equiv_{8}1\) (ו-\(7\) הוא בעצם מה שאנחנו מסמנים כ-\(-1\)) אבל מתקיים גם \(5^{2}=25\equiv_{8}1\), ולכן \(5\) הוא שורש לא טריוויאלי של 1. מכאן שבמהלך החישוב של מילר-רבין, עבור ערך "מוצלח" של \(a\), ה-1 המובטח בסוף הדרך יתקבל דרך שורש לא טריוויאלי של 1, ואז נדע בודאות ש-\(n\) אינו ראשוני.

נסכם: האלגוריתם של מילר-רבין בוחר באקראי \(a\) קטן מ-\(n\) וזר לו (אם הוא אינו זר לו, קל לגלות זאת בעזרת האלגוריתם האוקלידי, וזה גם יוכיח ש-\(n\) אינו ראשוני). הוא מחשב את \(a^{n-1}\) על ידי כך שהוא מפרק את \(n-1\) למכפלה \(n-1=m\cdot2^{k}\) (איך עושים זאת? מחלקים את \(n-1\) שוב ושוב ב-2 עד שמתקבל מספר אי זוגי), מחשב את \(a^{m}\) בצורה מהירה בשיטת קיבוץ החזקות של 2 שהראיתי (או בשיטות אחרות – יש כאלו), ואז מעלה אותו בריבוע \(k\) פעמים תוך שהוא בודק אם במהלך החישוב צץ לו שורש לא טריוויאלי של 1 (מספר שהיה שונה מ-1 ומ-\(-1\) אבל הפך ל-1 אחרי העלאתו בריבוע). אם צץ כזה שורש, או אם בסוף החישוב, כשהתקבל \(a^{n-1}\), התוצאה עדיין שונה מ-1, האלגוריתם דוחה; אחרת הוא אומר "סביר להניח ש-\(a\) ראשוני, אם כי אני לא בטוח".

וכאן נכנסת לתמונה השאלה האחרונה – כמה בטוחים אנחנו יכולים להיות? מה שרבין הוכיח (בהוכחה לא מסובכת אבל מעט טכנית שאני מעדיף לא להיכנס אליה) הוא שלכל \(n\) פריק שרק נרצה – בין אם הוא קרמייקל ובין אם לאו – לכל היותר רבע מה-\(a\)-ים שאנחנו עשויים לבחור יכולים להטעות אותנו; כל היתר אכן יגרמו לדחייה באחת מהדרכים המתוארות (או שבמהלך ריצת האלגוריתם עליהם יצוץ שורש לא טריוויאלי של 1, או ש-\(a^{n-1}\) לא יהיה 1). מבחינה היסטורית מילר קדם לרבין עם האלגוריתם (ואף לפניו הרעיון הכללי היה מוכר); ההבדל הוא בניתוחים שלהם – מילר הציג את האלגוריתם שלו כאלגוריתם דטרמיניסטי, שבודק \(a\)-ים בצורה סדרתית, והסתמך על השערת רימן המוכללת כדי לטעון שמספיק לבדוק תחום קטן יחסית של \(a\)-ים כדי שיובטח לנו שאחד מ-\(a\)-ים שנבדקו הוא כזה שהיה מפריך את היות \(n\) ראשוני במקרה שהוא פריק; לרוע המזל, השערת רימן המוכללת טרם הוכחה. מה שרבין עשה היה הפיכה של האלגוריתם להסתברותי, תוך הסתמכות על טענת ה"רבע" שהוא הוכיח.

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

למה RSA טרם נפרץ? (בגלל החשיבה המתמטית הלא פרקטית)

פורסם בתאריך על ידי
28

הצגתי כאן בעבר את שיטת ההצפנה RSA, שהיא ללא ספק אחת משיטות ההצפנה החשובות ביותר בעולם כיום, וגם אתם משתמשים בה ככל הנראה, לכל הפחות בצורה לא מודעת. הכוח של RSA נסמך על בעיה בסיסית בתורת המספרים שטרם נמצא לה פתרון יעיל – פירוק של מספר לגורמים. בהינתן מספר ששווה למכפלת שני מספרים ראשוניים (מספרים שמתחלקים רק ב-1 ובעצמם), \(n=pq\), יש למצוא את \(p\) ו-\(q\) (למשל, בהינתן המספר \(221\) יש להחזיר \(17,13\)).

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

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

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

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

בהמשך הלמו מפרט את הרעיון, ועושה זאת היטב. בבסיסו, הרעיון הוא כזה – נניח שאנחנו רוצים לחשב פונקציה מסובכת כלשהי, שזמן החישוב שלה ארוך. למה להסתבך? במקום שהמעבד יחשב אותה שוב ושוב ושוב, פשוט נשמור בצד טבלה עם כל הקלטים והפלטים האפשריים שלה. למשל, במקום לחשב את \(f\left(x\right)=x^{2}\) (נניח שזו פונקציה מסובכת), שומרים טבלה שבה ליד 1 כתוב 1, ליד 2 כתוב 4, ליד 3 כתוב 9 וכן הלאה. כך אנחנו מצמצמים את הבעיה של חישוב הפונקציה לבעיה של ביצוע חיפוש בטבלה. יתר על כן, אם אנחנו בונים את הטבלה כשהיא ממויינת על פי הקלטים, החיפוש יהיה מהיר מאוד – נשתמש בחיפוש בינארי (שעליו סיפרתי ממש לא מזמן) כדי למצוא את הפלט בטבלה, בזמן חיפוש שהוא לוגריתמי בגודל הטבלה (ובעברית – קטן משמעותית מגודל הטבלה). עד כאן – הכל אחלה. השיטה שהלמו מתאר היא אכן שימושית בפרקטיקה, במקרים מסויימים. באשר לתיאוריה המתמטית – עוד נגיע לזה.

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

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

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

אם כן, מה באמת קורה בעולם האמיתי? כל אחד יכול לקרוא בעצמו; לדוגמה, הספריה OpenSSL שמממשת פרוטוקולי הצפנה אמיתיים זמינה בקוד פתוח לכל ואפשר להציץ בה (כמובן, זה לא אומר שהקוד קריא במיוחד…). למי שמתעניין, הקובץ הרלוונטי הוא bn_prime.c בתת הספריה crypto/bn. בקצרה, הרעיון הבסיסי הוא כזה: מגרילים מספר גדול, בן מספר הספרות המבוקש (איך מבטיחים שמספר יהיה גדול? למשל, כשמגרילים את הביטים שלו מוודאים שהביט המשמעותי ביותר יהיה 1. מן הסתם יש דרכים נוספות). לאחר מכן בודקים שהוא ראשוני – ראשית בדיקת חלוקה נאיבית על אוסף קטן ונתון מראש של ראשוניים (2048 ראשוניים, שפשוט כתובים בטבלה בקובץ bn_prime.h) – עד כאן מזכיר את השיטה של איציק. אלא שכעת, לאחר הבדיקה הנאיבית הזו (שמסננת מספר עצום של מועמדים אקראיים להיות ראשוניים) מורץ אלגוריתם לבדיקת ראשוניות; לא אלגוריתם AKS המפורסם (והאיטי לצרכים פרקטיים), אלא אלגוריתם מילר-רבין ההסתברותי (והמהיר מאוד), שמורץ עם פרמטר בטיחות טוב דיו כדי להבטיח שההסתברות שיתקבל בטעות מספר שאינו ראשוני הוא אפסי. ארחיב על מילר-רבין ועל שיטות אחרות לבדיקת ראשוניות בפוסט אחר; לעת עתה אסתפק בלהגיד שבדומה לבעית הפירוק לגורמים, כך גם השיטה של מילר רבין היא מחוכמת (אם כי לא מתקרבת לרמת התחכום של אלגוריתמי הפירוק לגורמים) ואינה מתבססת על רעיונות נאיביים כמו "בדוק עבור הרבה מספרים אם הם מחלקים את המספר שאת ראשוניותו בודקים".

חזרה אל איציק והרעיון שלו. אחרי שהוא מסביר מהו חיפוש בינארי ולמה הוא יעיל, איציק אומר:

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

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

איציק מסביר שהבעיה כיום היא שאין מחשב חזק דיו כדי לבצע חישובים בפרק זמן סביר, אבל זיכרון יש בשפע, וכיום הוא זול מאוד בהשוואה לשנת 1977, השנה בה המציאו את הצפנת ה-.RSA איציק יודע גם להסביר שאם מפתח ההצפנה N הוא למשל בגודל 1024 ביט (שמתאים למספר עשרוני בן יותר מ-300 ספרות), אז כמות הזיכרון שצריך כדי לאחסן את המפתח הוא בסך הכל 128 בתים (מחלקים 1024 ביטים ב-8 כי בכל בית יש 8 ביטים). בנוסף יש צורך ב-128 בתים נוספים על מנת להחזיק את המספר הראשוני p וכן 128 בתים נוספים כדי להחזיק את המספר הראשוני q, שניהם מרכיבים את מפתח ההצפנה N.

החשבון כמובן נכון, אם כי מפתיע אותי שאיציק הפרקטי חושב שצריך לשמור גם את \(p\) וגם את \(q\); מספיק לשמור את \(p\) ולחשב את \(q\) על ידי חלוקת \(N\) ב-\(p\). זה מצמצם את גודל הטבלה בשליש. אם כן, הסכמנו שכל כניסה בטבלה היא קטנה מאוד – לוקחת 256 בתים. להשוואה – בעת כתיבת שורות אלו, הקובץ שבו הן נכתבות תופס כבר 25 אלף בתים. אם כן, הכל מושלם – אז למה RSA לא נפרצה? לאיציק הפתרונים:

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

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

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

יתרה מזאת: אם ישנם 10 בחזקת 100 מספרים ראשוניים ידועים, אז ישנם 10 בחזקת 200 מפתחות ציבוריים אפשריים. מספר הצעדים המקסימלי הנדרשים למצוא את הגורמים הראשוניים הוא פחות מ 800 צעדים.

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

וכאן נגמר המאמר.

לא אתווכח עם טענת ה"פחות מ-800 צעדים" – היא נכונה לגמרי. זו המחשה נהדרת לכוח העצום של החיפוש הבינארי. רק שאלה אחת לי אל איציק – איפה בדיוק תהיה שמורה אותה טבלה אגדית של \(10^{200}\) מפתחות ציבוריים אפשריים?

בואו נעשה לרגע את החשבון של איציק. כבר הסכמנו שכניסה בטבלה דורשת בסך הכל 256 בתים, שזה מספר זעום. כמה בתים לוקחת הטבלה כולה? במקרה הראשון, אמרנו שיש מיליון בחזקת 2 מפתחות ציבוריים אפשריים; כל מפתח שכזה מהווה כניסה בטבלה, ולכן דורש 256 בתים, ולכן בסה"כ נדרשים \(256\cdot10^{12}\) בתים. האם זה מספר גדול? ובכן, מדובר בכ-256 טרהבייטים (טרהבייט הוא 1000 ג'יגהבייט; בכל דיסק קשיח סטנדרטי בימינו יש כמה מאות ג'יגהבייטים וכבר מוכרים דיסקים קשיחים של טרהבייט בודד). כלומר, זה מספר קטן ומגוחך עבור סוכנויות הביון.

נפלא; ניתן לשער שגם במקרה השני מקבלים מספר קטן ומגוחך, אז אפשר ללכת לישון בשקט, נכון? הו, לא. אם יש \(10^{200}\) מפתחות אפשריים, התמונה משתנה באופן דרסטי; במקרה הזה צריך \(256\cdot10^{200}\) בתים כדי לאחסן את כולם. למי שטרם נתקל בחישובים במספרים כאלו זה עשוי להיראות סביר – \(200\) זה בסך הכל פי \(20\) מ-\(12\) (אפילו פחות), אז צריך רק להכפיל את המקום פי 20. אלא שזה לא נכון; לא צריך להכפיל את המקום פי 20, אלא פי \(10^{188}\). המספר הזה הוא עצום. עצום בצורה בלתי נתפסת. אם נניח שכל גרגר חול בעולם (נהיה לארג'ים ונניח שיש \(10^{100}\) כאלו) היה הופך לפתע פתאום לדיסק קשיח של קווינטיליון פטהבייטים (פטהבייט הוא 1000 טרהבייט), כמות הזיכרון שהיה אפשר לאכסן בכולם לא הייתה מתחילה אפילו לגרד את כמות הזכרון שהטבלה של איציק דורשת. במילים פשוטות – אין, לא הייתה אף פעם ולא תהיה אי פעם טבלה בגודל הזה. אם איציק הוא באמת פרקטי כמו שהוא טוען, היה עליו לדעת את זה.

אבל חמור מכך, אם איציק היה מזלזל קצת פחות בתיאורטיקנים ומקשיב להם, אולי הוא היה מבין שאפילו אם בדרך קסומה יצליחו לבנות את הטבלה העצומה הזו, על ידי רתימת כל הכוח של המין האנושי לפרוייקט הזה, זה עדיין לא היה מדגדג לקריפטוגרפים את קצה הזרת; הם פשוט היו מגדילים את המפתח, מ-1024 ביט ל-2048 ביט. תגידו – מה זה משנה? הרי אם קודם נדרשו 256 בתים בשביל כניסה אחת בטבלה, עכשיו יידרשו 512 בתים – בסך הכל הכפלנו את גודל הטבלה פי 2, לא משהו משמעותי. הבעיה כאן היא שאנחנו מתעלמים מהשאלה הבסיסית – מאיפה הראשוניים מגיעים וכמה כאלו יש?

אמרתי קודם שכדי למצוא מספרים ראשוניים פשוט מגרילים מספר גדול ובודקים אם הוא ראשוני. לא אמרתי מה עושים אם הבדיקה נכשלת – פשוט מגרילים מספר חדש ובודקים שוב (או שמשנים קצת את המספר הישן ובודקים שוב). השיטה הזו נשמעת מוזרה קצת במבט ראשון, כי מי מבטיח לנו שניפול אי פעם על ראשוני? אם כמות הראשוניים קטנה יחסית לכמות כל המספרים, אכלנו אותה – נגריל שוב ושוב מספר ולעולם לא ניפול על ראשוני. למרבה המזל, יש יחסית הרבה ראשוניים – זה בדיוק מה שמראה משפט המספרים הראשוניים שהזכרתי בחטף בפוסט הקודם. המשפט אומר (בערך) שבין \(1\) ל-\(n\) יש בערך \(\frac{n}{\ln n}\) מספרים ראשוניים (וככל ש-\(n\) גדול יותר ה"בערך" הזה מדוייק יותר) – זה אומר שההסתברות להגריל ראשוני בתחום הזה היא \(\frac{1}{\ln n}\). מכיוון ש-\(\ln n\) הוא בערך מספר הספרות שנדרשות כדי לייצג את \(n\), נובע מכך שכדי להגריל מספר ראשוני בן 100 ספרות צריך בערך 100 נסיונות, כדי להגריל מספר בן 200 ספרות צריך בערך 200 נסיונות, וכן הלאה – מספר הנסיונות הזה הוא קטן מאוד יחסית. זה גם מעיד על כך שמספר הראשוניים הוא גדול מאוד יחסית.

המספר הגדול ביותר שניתן לייצג עם \(1024\) ביט הוא \(2^{1024}\); זהו מספר בן 300 ספרות לערך שמן הסתם לא אכתוב פה (מי שרוצה לראותו – שיכתוב 1024**2 בפייתון או רובי). אם כן, כמה ראשוניים בני עד 1024 ביט יש? בערך \(\frac{2^{1024}}{1024}=\frac{2^{1024}}{2^{10}}=2^{1014}\) ראשוניים, וגם \(2^{1014}\) הוא מספר עצום, גם כן בעל בערך 300 ספרות (חדי העין בוודאי שמים לב שאני משתולל כאן עם הבסיס של הלוגריתם על ימין ועל שמאל – לא נורא, מותר לי). בקיצור, כבר ב-1024 ביט יש לנו הרבה יותר ראשוניים ממה שאיציק טוען; הוא מדבר על \(10^{100}\) ראשוניים, ואני אומר שכבר יש \(10^{300}\), מה שמוביל לטבלה בגודל של \(10^{600}\) – מספר בלתי נתפס.

אבל רגע, מה קורה אם אנחנו עוברים ל-2048 ביט? אז יהיו לנו בערך \(2^{2037}\) ראשוניים (למה?) וזה מספר בן 600 ספרות. הכפלה של מספר הביטים פירושה העלאה בריבוע של כמות הראשוניים הזמינים לנו (שבאה לידי ביטוי בהכפלה של מספר הספרות בתיאור הכמות שלהם). עכשיו הטבלה שלנו תצטרך להיות מגודל \(10^{1200}\) – לא "פי 2" יותר גדולה, אלא פי \(10^{600}\) יותר גדולה מקודם. בניסוח אחר – אם קודם היינו צריכים להשקיע את כל משאבי המין האנושי בטבלה אחת כזו, שכל תא בה מאכסן כמות זעומה של נתונים, כעת נצטרך לבנות מספר עצום של טבלאות שכאלו – טבלה לכל תא בטבלה המקורית. ואם המין האנושי ישיג את ההשיג הכביר והבלתי נתפס הזה, אז הקריפטוגרפים פשוט ימשכו בכתפיים ויעברו ל-4096 ביט, ושוב יעלו בריבוע את כמות הזיכרון הנדרשת. לקריפטוגרפים הגדלות כאלו של אורך המפתח אינן בעיה ממשית, כי כל מה שהן עושות הוא להגדיל פי 2 את הקושי של החישובים המעורבים (הגרלת מספרים, הצפנה וכו'). הגדלה פי 2 היא כאין וכאפס לעומת ההגדלה פי \(10^{600}\) שאיציק זקוק לה. כל זה הוא מקרה פרטי של האבחנה הכללית שבבסיס תורת הסיבוכיות התיאורטית – סיבוכיות אקספוננציאלית (שבה כשמגדילים את הקלט בביט אחד, הסיבוכיות מוכפלת פי 2, ולכן כשמכפילים את גודל הקלט, הסיבוכיות מועלה בריבוע) אינה משהו סביר, באופן כללי (כמובן שבעולם הפרקטי האמיתי, יש דוגמאות נגדיות).

אם כן, הטבלה של איציק איננה רעיון פרקטי; היא הרעיון הכי לא פרקטי שאפשר לחשוב עליו. ועוד לא אמרנו כלום על סוגיית הזמן שצריך כדי לבנות את הטבלה הזו מלכתחילה (ולמען האמת, גם לא ממש צריך). מה בעצם הייתה הטעות של איציק, חוץ מההתעלמות הגסה מהצורך לחשב כמה זכרון, בבתים, צריך בשביל הטבלה של ה-\(10^{100}\) ראשוניים שלו? לדעתי, חוסר ההבנה שלו את הגודל העצום של מרחב הראשוניים שעומדים לרשות הקריפטוגרפים הוא שבלבל אותו. הנקודה היא שלא צריך לבנות "רשימה שחושבה מראש של כל המספרים הראשוניים הידועים" כמו שאיציק תיאר, כדי שניתן יהיה להגריל ראשוניים – המרחב העצום של ה-\(10^{300}\) ראשוניים בני 1024 ביט זמין לנו בלי שנצטרך לאחסן אותו בשום מקום, בזכות אותו "אלגוריתם מתמטי" שאיציק התעקש שאיננו צריכים.

טוב, סיימנו עם זה, אבל אני עדיין רוצה להתייחס לטענת "כולם חושבים בצורה מתמטית ולא בצורה פרקטית כמו מתכנתים", בשתי צורות שונות – פרקטית, ומתמטית. מבחינה פרקטית, כדי לשכנע ש"כולם" דווקא כן חושבים בצורה פרקטית לפעמים (כש"כולם" מתייחס כאן לקריפטוגרפים) אני רוצה לתת דוגמה לתחום בקריפטוגרפיה שהוא מאוד "פרקטי" באופיו – התחום שעוסק ב-Side-Channel Attacks. מכיוון שהוא ראוי לפוסט נפרד, רק אגיד באופן כללי מהו – זה התחום שעוסק בתקיפת מערכות הצפנה לא על ידי תקיפת האלגוריתם שבבסיסן באופן תיאורטי, אלא על ידי שימוש במידע נוסף שמופק מכך שהאלגוריתם התיאורטי ממומש במערכת פיזית. דוגמאות לאפיקים שאפשר להפיק מהן מידע הן זמן החישוב שלוקח למעבד לבצע את האלגוריתם, כמות ההספק החשמלי שהוא צורך, החום שהוא פולט ואפילו הרעשים שהוא משמיע (התקפה פרקטית מהסוג האחרון הציע, בין היתר, עדי שמיר, ה-S שב-RSA; באופן כללי שמיר הוא דוגמה טובה למדען מחשב שיכול להיות גם מאוד מתמטי וגם מאוד פרקטי). ההתקפות הללו מזכירות את תעלול "קריאת המחשבות" הבא – אנחנו נותנים למישהו להחזיק מטבע של שקל ביד אחת, ושל חמישה שקלים ביד השניה, ומטרתנו היא לגלות באיזה יד נמצא איזה מטבע. אז אנחנו מבקשים מהמחזיק לכפול את מה שביד ימין ב-14, ואחר כך מבקשים ממנו לכפול את מה שביד שמאל ב-14, ואז אנחנו מבקשים ממנו לחבר את התוצאות ולהגיד לנו. מן הסתם הוא תמיד יגיד 84, אבל לעתים קרובות נוכל לנחש באיזו יד המטבע על ידי כך שנבחין איזה חישוב לקח לו זמן רב יותר (עם זאת, התעלול הזה יכול להיכשל כל כך בקלות שאף פעם לא העזתי לבצע אותו בעצמי).

כעת להתייחסות השניה, והחשובה יותר – גם מדעני מחשב שחושבים "בצורה מתמטית" יכולים לחשוב על השיטה שאיציק הציע, ולמעשה הם עשו את זה עוד הרבה לפני שאיציק הציע זאת. קיימים מודלים מתמטיים של חישוב שמטפלים בשיטה הזו באופן הרבה יותר כללי – כי מה שאיציק עושה הוא רק המקרה הקיצוני, והלא מעניין, של השיטה. באופן כללי אפשר לחשוב על אלגוריתמים שנעזרים במהלך החישוב שלהם ב"טבלה" של מידע שחושב מראש (אולי חישוב שדרש זמן רב; ולמעשה, אולי אפילו מידע שלא ניתן לחשב באופן אלגוריתמי – אבל כדי לפרט על זה, אני זקוק לפוסט נפרד), והמודל הפורמלי מכונה "מכונות שמקבלות 'עצה'" (ה"עצה" היא אותה טבלה). העובדה שכל פונקציה ניתנת לחישוב בקלות בהינתן עצה שהיא בעצם טבלה שבה לכל קלט כתוב הפלט המתאים לו היא אחת מהאבחנות הטריוויאליות הראשונות של חקר המודל הזה, כמו גם האבחנה שטבלה כזו היא אקספוננציאלית באורכה ולכן העסק לא כל כך מעניין. בדרך כלל עוסקים בטבלאות שגודלן הוא סביר – פולינומי – ביחס לגודל הקלט; מחלקת הסיבוכיות המרכזית בהקשר זה נקראת P/poly (ה-P מייצג חישוב בזמן יעיל, פולינומי; ה-poly מייצג עצות שהן פולינומיות בגודלן). פרט למודל הזה, מדעני מחשב עוסקים באופן כללי בשקלול זמן-מול-זיכרון (Space-Time tradeoff), כלומר בשאלה עד כמה ניתן לקצר את זמן הריצה של חישוב פונקציה מסויימת באמצעות שימוש רב יותר בזיכרון, אך גם על זה לא אפרט כרגע.

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

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

פורסם בתאריך על ידי
5

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

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

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

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

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

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

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

נניח שהתוכנית משתמשת במחולל האקראי האמיתי. מה ההסתברות שלה לפלוט 1? כמובן, 1/6. לכן אם אריץ אותה הרבה פעמים, אספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל מספר שקרוב ל-1/6. לעומת זאת, אם התוכנית משתמשת במחולל של xkcd, היא תמיד תחזיר 1, ולכן כשאספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל 1. ההבדלים כאן ברורים בצורה שאינה משתמעת לשתי פנים.

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

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

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

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

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

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

הסיבה לכך היא שאם P=NP, ניתן תמיד לבנות מבחין, עבור כל מחולל פסאודו אקראי, שפועל כמעט באופן זהה למבחין שבניתי עבור המחולל האווילי של xkcd. האבחנה הראשונה היא שתוכנית שמוציאה 1 על כל קלט שיכול להיווצר על ידי המחולל הפסאודו אקראי, ומוציאה 0 על קלטים אחרים, תמיד פולטת 1 כשהיא מופעלת על המחולל הפסאודו אקראי, אבל פולטת 1 בהסתברות שהיא לכל היותר חצי כאשר היא מופעלת על התפלגות אקראית "אמיתית". הסיבה לכך היא, כמו שראינו כבר, שמחולל פסאודו אקראי מכסה לכל היותר חצי ממרחב הערכים האקראיים האפשריים (זה במקרה שבו הניפוח שלו הוא של ביט בודד; עבור ניפוח גדול יותר הוא מכסה עוד פחות). מכאן שתוכנית שכזו היא המבחין האולטימטיבי. השאלה היא רק מה זמן הריצה של תוכנית שכזו. כמובן, זה תלוי בצורה שבה התוכנית מבצעת את החישוב שלה.

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

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

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

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

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

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

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

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

פורסם בתאריך על ידי
11

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

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

מה עכשיו?

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

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

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

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

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

התשובה היא חיובית, אם כי ההוכחה אינה בעלת ודאות של 100% כמו קודם. מה שהמוודא יעשה הוא לצעוק לי "ימינה" או "שמאלה", ואני, בהתאם לצעקה שלו, אצא דרך המסדרון הימני או השמאלי. אם הוא צעק "ימינה" ונכנסתי מראש למסדרון הימני, אני פשוט יוצא; אבל אם נכנסתי מראש למסדרון השמאלי, אני חייב לעבור דרך הקיר כדי שאוכל לצאת מהמסדרון הימני. מכיוון שהוא בוחר באקראי איזה מסדרון לצעוק, תמיד יש הסתברות של 50% שהוא יצעק את המסדרון שבו אני לא נמצא; ולכן, אם לא הייתי באמת יודע לעבור דרך קירות, הייתה לו הסתברות של 50% לתפוס את הבלוף שלי.

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

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

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

מה קורה כשמחלקים שרלטן באפס? כשזה פומבי זה נהיה מביך

פורסם בתאריך על ידי
8

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

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

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

Such are the accomplishments achieved by the men and women of Singularics. Standing on the shoulders of giants such as Albert Einstein and Bernhard Riemann, we have reached up through nature's veil and seen what lies hidden there more clearly than anyone else before us. Our discoveries have yielded a new mathematical framework, one that provides a profound understanding of nature's basic mechanics. We have discovered The Science of Singularics™, the study of the singularity.

We have already found a variety of important applications of Singularic Technology™, but perhaps the most immediately useful are Neutronic Encryption™, a new theoretically unbreakable public key encryption algorithm and Singularic Power™, a new form of clean power generation.

 

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

התשובה פשוטה: הביטוי "theoretically unbreakable public key encryption algorithm", שאינו שונה מהותית מ"ראשוני שמתחלק ב-7 ו-13" או "מעגל שניתן לרבע באמצעות סרגל ומחוגה". אנסה להסביר.

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

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

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

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

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

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

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

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

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

Today, there are areas of mathematics widely considered to be "undefined", for example where 1 is divided by 0. Just as Sir Isaac Newton once invented Calculus to accomplish the analysis of motion he needed to pursue his interests, so have we at Singularics developed a new branch of mathematics called Neutronics. This contribution to science represent a significant advance in human understanding and makes possible for the first time a method of analysis for the "undefined" point at the singularity.

Our Founder and CTO, Jeff Cook, has also used Neutronics to settle the long outstanding question of Riemann's Hypothesis and has shown conclusively that all non trivial zeros of the zeta function do indeed have Real part one half, ie. the hypothesis has been proven to be true. Click here to download a copy of Jeff Cook's purported proof of the Riemann Hypothesis, now in pre-print.

כמובן. אף טרחן שמכבד את עצמו לא יטען שלא הוכיח את השערת רימן, או דבר מה שקול. המאמר שאליו הוא מקשר הוא בן 63 עמודים – שיהיה בהצלחה למי שיטרח לקרוא אותו.