זה לא ראשוני, זה אפילו לא פריק

לגמרי במקרה נתקלתי בכתבה עתיקת יומין מ”הארץ” על אלגוריתם AKS המפורסם לבדיקת ראשוניות.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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