האם המספרים הראשוניים אינם אקראיים?

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

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

מספר ראשוני הוא מספר חיובי ושלם שאינו מתחלק בשום מספר חוץ מאחת וממנו עצמו. המספרים הראשוניים הקטנים ביותר הם 2, 3, 5, 7, 11, 13, 17. הגדרת המספרים הראשוניים קלה ופשוטה להבנה, אבל אל תיתנו לזה להטעות אתכם. הם נושא סבוך בעולם המחקר המתמטי, ועל אף הניסיונות הרבים לאפיין את המספרים הראשוניים, שאלות רבות נותרו פתוחות עד היום.

כבר בשנת 300 לפני הספירה הוכיח אוקלידס שיש אינסוף מספרים ראשוניים, אך ככל שהמספרים גדלים שכיחותם של המספרים הראשוניים יורדת. כך, למשל, עד 1,000 יש 168 מספרים ראשוניים, אך בין 1,000 ל-2,000 המספר יורד ל-135 מספרים ראשוניים. עד כה לא נמצאה תבנית ייחודית שתאפיין מתי מופיעים מספרים ראשוניים בסדר המספרים הכללי, לכן הם נחשבים אקראיים.

אחד הדברים הידועים לגבי המספרים הראשוניים הוא שמלבד 2 ו-5, כולם מסתיימים בספרות 1, 3, 7 ו-9. אם ההנחה שהמספרים הראשוניים מופיעים בצורה אקראית נכונה, נצפה שהמספר הבא בסדרת המספרים הראשוניים יסתיים בסיכוי זהה (25%) בכל אחת מארבע הספרות האלה. זה בדיוק מה שבדקו צמד החוקרים שהגישו את ממצאיהםלאחרונה לכתב העת המדעי Nature. הם בדקו במחקר יותר ממיליארד מספרים ראשוניים, וגילו חריגה מההתפלגות הזאת. אם יש מספר ראשוני המסתיים ב-1, רק ב-18 אחוז מהמקרים גם המספר הראשוני הבא יסתיים ב-1. לעומת זאת, 30 אחוז מהמספרים הראשוניים אחרי מספר המסתיים ב-1 יסתיימו ב-3 או ב-7, ורק 22 אחוז יסתיימו בספרה 9. כלומר, מספרים ראשוניים המסתיימים בספרה 1 נוטים שלא להופיע לפני מספרים המסתיימים באותה ספרה. תוצאות דומות התקבלו בעבור מספרים המסתיימים ב-3, 7 ו-9.

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

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

איך זה עובד?

נניח שמרדכי רוצה לשלוח מידע מוצפן לאסתר. שניהם צריכים להסכים מראש על פונקציה שקל מאוד להפעילה על מספר מסוים אך קשה לשחזר את המספר לאחר שהפעולה נעשתה. במקרה של RSAהפונקציה היא x^y mod N. הפונקציה modהיא חישוב השארית השלמה בפעולת חילוק, למשל: 5 mod 4 = 1, כלומר אחרי שמחלקים 5/4 השארית היא 1.

אסתר בוחרת שני מספרים ראשוניים, המכונים לצורכי נוחות pו-q, ומכפילה אותם זה בזה. התוצאה היא N. לדוגמה, 13x23=299. עכשיו אסתר מייצרת מספר נוסף, מהנוסחה הפשוטה: (p-1)x(q-1)=1. במקרה שלנו התוצאה היא 265 =12x22+1. נפלאות המתמטיקה קובעות שכל מספר שאינו ראשוני הוא מכפלה של מספרים ראשוניים, שניים או יותר. במספר כמו 265 אפשר לחשב די בקלות את הגורמים המרכיבים אותו, 5x53. אפשר גם להיעזר במחשבון פירוק לגורמים. לשני הגורמים האלה, אסתר קוראת rו-s. עכשיו הכול מוכן, ואסתר מפרסמת את המפתח הפומבי שלה להצפנה, שהוא המספר Nואחד משני הגורמים שחישבה. הגורם השני ידוע אך ורק לה, בדוגמה שלנו: N=299, r=53.

כשמרדכי רוצה לשלוח לאסתר מספר מוצפן, הוא משתמש בפונקציה המוסכמת. נניח שהוא רוצה לשלוח לה את הציון שקיבלה מאחשוורוש, 10. הוא מציב אותו במקוםx  בפונקציה,x^y mod N, ומשתמש בשני המספרים הפומביים שפרסמה אסתר ובמחשבון מדעי פשוט.10⁵³ mod 299=43  . את המספר 43 הוא שולח לאסתר, וגם אם המן במקרה יתפוס את השליח, המספר לא יאמר לו דבר. אסתר, לעומת זאת, לוקחת את המספר שקיבלה ממרדכי, מציבה אותו בפונקציה עם המתפח הפרטי שלה ומקבלת את המספר שהצפין מרדכי: 43⁵ mod 299 = 10. אתם יכולים לנסות את זה בעצמכם.

מספרים גדולים
בדוגמה הזאת השתמשנו במספרים ראשוניים קטנים למדי, ועדיין עברנו דרך מספרים גדולים כמו 10⁵³או 43⁵. לכן גם קל יחסית לפצח את ההצפנה. כל אחד יגלה בקלות ש-299 הוא מכפלה של שני המספרים הראשוניים 23x13. אבל כשמדובר במספרים הרבה הרבה יותר גדולים, לפעמים מאות ואלפי ספרות, דרושים חודשים ארוכים של חישובים כדי לזהות את המספרים הראשוניים ולפצח את הצופן, וזה חוזקה של שיטת RSA. לכן השיטה הזאת משמשת כיום כלי מרכזי במסחר אלקטרוני ובהצפנת מידע.

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

מירי אדלר, דוקטורנטית במכון ויצמן למדע

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