כתב: גדי אלכסנדרוביץ'
הצפנה היא כלי חשוב בשמירה על מידע. אחת מפריצות הדרך החשובות בנושא היא מפתחות ציבוריים ופרטיים, המאפשרים לשלוח מידע מוצפן גם בין אנשים שמעולם לא יצרו קשר מוקדם. אלגוריתם ההצפנה RSA, מהנפוצים כיום, משתמש בכלים בסיסיים של תורת המספרים להעברת מידע מאובטח בשיטה זו. חלק גדול מהפעולות היום יומיות שלנו, כמו רכישות באינטרנט, מבוססות על אלגוריתם זה.
כשאנחנו קונים באינטרנט, אנו שולחים למוכר את פרטי האשראי שלנו. המידע עובר דרך שרתים רבים; מי מבטיח לנו שגורמים זדוניים לא יגנבו את פרטי האשראי שלנו? יקראו את הדואר האלקטרוני, או יציצו להתכתבויות פרטיות?
הפתרון נקרא הצפנה: שינוי הודעה טרם שליחתה, כך שצד שלישי יראה אותה כחסרת משמעות, אבל הנמען יוכל לפענח אותה. הצפנה היא רעיון עתיק; נטען כי יוליוס קיסר השתמש בשיטת הצפנה (פשוטה) [1]. עם זאת, ההצפנה ברשת האינטרנט היא מסוג שהומצא רק בשנות ה-70 של המאה ה-20: "הצפנת מפתח פומבי", והשיטה הידועה ביותר מסוג זה היא RSA[2] , על שם ממציאיה - רונלד ריבסט, עדי שמיר (הישראלי) ולאונרד אדלמן.
בשיטות הצפנה "קלאסיות", המידע מוצפן ומפוענח בעזרת מידע סודי הידוע למצפין ולמפענח, ומכונה "מפתח": למשל, סיסמה משותפת או מספר גדול. הקושי בגישה זו הוא שעל המצפין והמפענח להסכים מראש על הסיסמה בצורה מאובטחת. עם זאת, כאשר אנו קונים בחנות אקראית באינטרנט, מעולם לא הסכמנו איתה על סיסמה קודם לכן. איך נוכל לשלוח אליה מידע מוצפן?
בשיטת המפתח הפומבי, החנות מכינה מראש שני מפתחות: פומבי ופרטי. את הפומבי מפרסמת ואת הפרטי שומרת בסוד. כדי להצפין, יש לדעת רק את המפתח הפומבי, אבל כדי לפענח אפשר להשתמש רק במפתח הפרטי - אפילו המצפין לא יכול לפענח את ההודעה שהצפין!
ניתן לדמיין זאת כך: החנות קונה אלפי מנעולים הנפתחים על ידי מפתח יחיד ומשגרת אותם לכל העולם. את המפתח שומרת לעצמה. מי שתרצה לשלוח לחנות משהו בצורה מאובטחת, לוקחת מנעול ונועלת את החבילה שהיא שולחת. מרגע שננעלה, רק החנות תוכל לפתוח את החבילה
הצפנת מפתח פומבי היא אחד מהחידושים הרבים של תחום ההצפנה המודרני, העוסק באתגרים רבים של אבטחת מידע [3] - למשל חתימות דיגיטליות (דרך לאימות זהות שולח מידע) וחישובים מבוזרים [4].
למרות פשטותו היחסית, הרעיון הוצע רק ב-1976 במאמר של ויטפילד והלמן[5], ללא מימוש אפשרי. בשנת 1977 פרסמו ריבסט, שמיר ואדלמן את שיטת RSA, המימוש הפומבי הראשון של הרעיון. למה פומבי? נטען כי ארגון הביון הבריטי וה-NSA גילו את השיטה קודם לכן. היבט מעניין הוא שהשיטה נסמכת על תוצאות בסיסיות בתורת המספרים, שעד אז נחשבה לתחום "לא שימושי". שיטות הצפנה פומביות שפותחו לאחר מכן מתבססות על תורת המספרים [6].
היבט נחמד של שיטת RSA הוא הפשטות: ראשית מקודדים הודעה כמספר גדול שנסמן כ-X. המפתח הפומבי כולל שני מספרים - מספר גדול N (בן כמה מאות ספרות) ומספר e שיכול להיות קטן יותר, אבל עדיין גדול. ההצפנה היא בסך הכל להעלות את X בחזקת המספר e, לחלק ב-N ולהחזיר את השארית (הדבר דורש חישובים במספרים גדולים, אבל במחשבים מודרניים חישובים שכאלו מתבצעים בחלקיקי שניות). במשוואה נהוג לכתוב:
y=x^e mod N
הפענוח פשוט במידה דומה: המפתח הפרטי הוא בסך הכל מספר d שמחושב מתוך N ו-e בצורה שמבטיחה שאם y היא הודעה מוצפנת, אחרי העלאת y בחזקת d וחלוקה ב-N, השארית תהיה בדיוק ההודעה x שממנה התחלנו. במשוואה:
x=y^d mod N
אם כן, מערכת ההצפנה מסתמכת על שלושת המספרים N,e,d; כיצד ניתן לייצר אותם? כאן נכנסת לתמונה "פונקציית φ (פי) של אוילר" [7], המחזירה לכל מספר את כמות המספרים הקטנים ממנו שאין להם גורם משותף עימו [8]. משפט בסיסי של אוילר קובע שלכל מספר טבעי a, אם נעלה את x בחזקת a*φ(N)+1, נחלק ב-N וניקח את השארית, נקבל שוב את x. כעת, אם φ(N) ידועה, קל למצוא e,d שהמכפלה שלהם תהיה מהצורה a*φ(N)+1 עבור a כלשהו; הקושי היחיד הוא בחישוב φ(N), שהיא בעיה קשה מבחינה חישובית אם N e וd הם מספרים גדולים. הקושי הזה הוא בדיוק היתרון של שיטת ההצפנה! אם זה היה קל, כל מי שהיה מכיר את N ו-e היה יכול לחשב את d. במילים אחרות, כל מי ששולח לחנות חבילות יכול לפתוח חבילות של אחרים.
איך בוחרים את מספרי מערכת ההצפנה? כאן נכנס לתמונה מידע נוסף שיש לבונה המערכת. אם N נבחר כמכפלה של שני מספרים ראשוניים N=pq אז φ היא פשוטה:(φ(N)=(p-1)(q-1. כעת ניתן לבנות את מערכת ההצפנה: מגרילים שני מספרים ראשוניים p,q (כל אחד בן מאות ספרות, בכדי למנוע פיצוח בעזרת חישובים). מכפילים אותם לקבלת N, וממשיכים למצוא e, d בעזרת הידע הנוסף שלנו על φ(N). לבסוף מפרסמים בפומבי את N ו-e. המספרים הראשוניים  p, q נזרקים ונשכחים, שכן הם לא דרושים עוד.
כיצד למצוא מספרים ראשוניים בני מאות ספרות, הדרושים לבניית המערכת? לבעיה מסובכת לכאורה זו קיים פתרון מתמטי פשוט (אלגוריתם מילר-רבין [9]) אך זה נושא לפוסט נפרד.
עוד נציין כי למרות הרושם כאילו ההצפנה המודרנית מתבססת על תורת המספרים, בפועל היא תחום רחב עם שיטות מתחומים שונים של המתמטיקה ומדעי המחשב
קשה לדמיין כיצד רשת האינטרנט הייתה מסוגלת להתנהל ללא אבטחת מידע. לפעמים, גם שיטות מתמטיות שנחשבו בעבר כחסרות שימוש, יכולות לשנות את חיי היום שלנו.
 
[1] על הצופן של יוליוס קיסר:
https://en.wikipedia.org/wiki/Caesar_cipher
[2] על הRSA:
https://brilliant.org/wiki/rsa-encryption/
[3] על האתגרים של אבטחת מידע (מאתר צ'ק פוינט):
https://www.checkpoint.com/smb/help/utm1/8.0/7068.htm
[4] על חישובים מבוזרים:
https://he.wikipedia.org/wiki/%D7%97%D7%99%D7%A9%D7%95%D7%91_%D7%9E%D7%91%D7%95%D7%96%D7%A8
[5] על פרוטוקול דיפי -הלמן:
https://he.wikipedia.org/wiki/%D7%A4%D7%A8%D7%95%D7%98%D7%95%D7%A7%D7%95%D7%9C_%D7%93%D7%99%D7%A4%D7%99-%D7%94%D7%9C%D7%9E%D7%9F
[6] על תורת המספרים:
https://he.wikipedia.org/wiki/%D7%AA%D7%95%D7%A8%D7%AA_%D7%94%D7%9E%D7%A1%D7%A4%D7%A8%D7%99%D7%9D
[7] על הפונקצייה של אויילר:
https://en.wikipedia.org/wiki/Euler%27s_totient_function
[8] על גורם משותף גדול ביותר:
https://en.wikipedia.org/wiki/Greatest_common_divisor
[9] על אלגוריתם מילר רבין:
https://he.wikipedia.org/wiki/%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D_%D7%9E%D7%99%D7%9C%D7%A8-%D7%A8%D7%91%D7%99%D7%9F