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

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

שלב א' - השיטה באופן כללי

אם כן, נתחיל. שדה המשחק הבסיסי שלנו הוא החבורה הכפלית \( \mathbb{Z}^*_n \). לא אגיד בינתיים מה המשמעות המדוייקת של הדבר הזה - מה זו “חבורה”, למה כפלית, ומה זה הסימון המופרע הזה. לצרכנו מספיק לדעת שזוהי קבוצת המספרים בתחום \( 0\dots n-1 \) (ואפילו לא כולם, אבל גם לזה לא ניכנס עכשיו), ושאנו מדברים על פעולת כפל “מודולרית” שלהם. כפל מודולרי פירושו שבהינתן \( a,b \) ששייכים לקבוצה, אנו כופלים אותם, אבל אז מחלקים את התוצאה ב-\( n \) ומתעניינים רק בשארית. למשל, אם \( a=3,b=5,n=9 \) אז תוצאת הכפל המודולרי היא 6. שימו לב שחלוקה ב-\( n \) ולקיחת השארית תחזיר תמיד מספר שהוא בתחום \( 0\dots n-1 \) (מדוע?)

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

כעת אליס מגרילה את ה”מנעול” שלה - מספר \( e \) כלשהו. יש עליו מגבלות והוא נבחר מתוך תחום מסויים (גדול מאוד) של מספרים, אבל על זה ארחיב בהמשך. כעת היא משתמשת בידע שלה על הפירוק של \( n \) כדי למצוא מספר נוסף \( d \), כך שמתקיימת התכונה הנאה הבאה:

לכל \( x\in\mathbb{Z}^*_n \) מתקיים \( (x^e)^d=x \), כאשר החזקה מבוצעת מודולו \( n \) (זה בסך הכל כפל של \( x \) בעצמו מספר כלשהו של פעמים ולקיחת השארית כל הזמן). כלומר, העלאה בחזקת \( e \) והעלאה בחזקת \( d \) הן פעולות הופכיות זו לזו - האחת מבטלת את השנייה.

כעת אליס מפרסמת את \( e,n \) ושומרת את \( d \) סודי. כשבוב רוצה לשלוח לה הודעה, הוא מקודד אותה כמספר ב-\( \mathbb{Z}^*_n \), מעלה בחזקת \( e \), ושולח לאליס. מי שאינו יודע את \( d \) כנראה יתקשה לבטל את פעולת ההעלאה בחזקה הזו - אליס עושה זאת בקלות, באמצעות \( d \). זה הכל.

שתי הערות “פרקטיות” - ראשית, למרות שלכאורה מבצעים בהצפנה פעולות מטורפות - למשל, מחשבים את \( 5345345345^{345341235785} \) מודולו \( 89824342423 \) וכולי (מספרים מומצאים ואולי לא תקינים!), הרי שיש שיטות לא מסובכות כל כך לעשות זאת מהר. חשוב לזכור שאולי מדובר על מספרים גדולים ומפחידים, אבל בפועל הם מיוצגים על ידי מספר לא גדול של ספרות (כדי לייצג מפתח טיפוסי בימינו נדרשות 2048 סיביות - פחות מ-300 בתים) וסיבוכיות הזמן שנדרשת לבצע פעולות כמו כפל או העלאה בחזקה (כשעושים אותן נכון) היא ביחס ישר למספר הספרות, לא לגודל המספר. אם מכפילים את מספר הספרות פי 2, כל מה שקורה הוא שמכפילים פי 2 את הזמן שלוקח לבצע פעולות חשבון עליהן (אבל מבחינת הגדלת טווח המספרים, זו הגדלה אסטרונומית - מעלים בריבוע בערך את המספר שמיייצג את הטווח הנוכחי).

ההערה השנייה היא שלא הכי ברור איזה הודעות כבר אפשר לקודד בתור מספרים ב-\( \mathbb{Z}^*_n \). בסופו של דבר, למרות שהטווח נראה גדול, הרי שאפשר בסך הכל לקודד רק מספר קטן של בתים (כאמור, פחות מ-300) לפני שנסתכן ב”התנגשויות”. התשובה לכך היא שבדרך כלל משתמשים במפתח ציבורי כדי להצפין מפתח קטן שמשמש להצפנה סימטרית (בימינו גם הפרנואידים משתמשים רק במפתח של 32 בתים), ואת התקשורת האמיתית להצפין בצורה סימטרית (שהיא מהירה יותר וכנראה גם בטוחה יותר). בעזרת שיטות ההצפנה הסימטרית של ימינו, אפילו הודעות עצומות של מאות מגה בייט ניתנות להצפנה סבירה בעזרת מפתחות קטנים - כלומר, הצפנת המפתח הציבורי לא באה להחליף את הצפנת המפתח הסימטרי, אלא להשלים אותה.

יאללה, עכשיו למתמטיקה.

שלב ב' - איך בדיוק בוחרים את הערכים?

אמרתי שב-\( \mathbb{Z}^*_n \) אין את כל המספרים בטווח \( 0\dots n-1 \). לא אכנס כרגע לנימוק למה (כמובן, חוץ מהנימוק הטריוויאלי של: “על המספרים שמעיפים השיטה לא עובדת”), אבל כן אגיד את מי מעיפים: את כל מי שלא זר ל-\( n \). כלומר, כל מספר \( a \) כך שקיים איזה שהוא \( t>1 \) שמחלק גם את \( a \) וגם את \( n \). דוגמה: 18 ו-16 אינם זרים, שכן 2 מחלק את שניהם גם יחד.

בחירת \( e \) מסובכת יותר. אנחנו בוחרים אותו כך שיהיה זר ל-\( (p-1)(q-1) \). למה? כי זה הוא מספר האיברים שזרים ל-\( n \), ולכן הגודל של \( \mathbb{Z}^*_n \). למה צריך ש-\( e \) יהיה זר לגודל הזה? שוב, כי אחרת כל העסק לא היה עובד. שימו לב, אגב, ש-\( e=2 \) אף פעם לא יהיה זר ל-\( (p-1)(q-1) \), ולכן מה שמכונה “שיטת רבין” מתפצל ברגע זה מ-RSA.

דרך אחרת לכתוב את ה-\( (p-1)(q-1) \) היא לכתוב \( \varphi(n) \). קרי: “פונקצית אוילר של \( n \)”. הפונקציה מוגדרת בצורה פשוטה: עבור \( n \), היא שווה למספר המספרים הטבעיים שקטנים מ-\( n \) וזרים לו. תכונה חשובה שלה היא שהיא כפלית עבור מספרים זרים - כלומר, ש-\( \varphi(x)\varphi(y)=\varphi(xy) \) אם \( x,y \) זרים זה לזה. עוד דבר שקל להוכיח (נסו!) הוא שעבור ראשוני \( p \) מתקיים \( \varphi(p)=p-1 \). מכאן ברור למה אכן \( \varphi(n)=(p-1)(q-1) \).

ואיך בוחרים את \( d \)? מחפשים ומוצאים מספר כך שיתקיים \( e\cdot d=1(\text{mod} \varphi(n)) \). איך עושים זאת? בעזרת מה שמכונה “האלגוריתם האוקלידי המורחב”. עוד - בהמשך.

שלב ג' - למה הערכים הללו טובים לנו?

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

המשפט אומר כך: אם \( G \) חבורה עם \( k \) איברים, אז \( x^a=x^b \) אם \( a\equiv b(\text{mod}k) \). אין צורך כרגע להיכנס לשאלה “מהי חבורה” - מספיק להזכיר ש-\( \mathbb{Z}^*_n \) היא חבורה.

אם כן, מה יש לנו? יש לנו חבורה עם \( k=\varphi(n) \) איברים. יש לנו \( e,d \) שמקיימים \( ed\equiv 1(\text{mod}k) \), ולכן יש לנו ש- \( (x^e)^d=x^{ed}=x^1=x \). גמרנו.

שלב ד' - אז איך מוצאים את d?

האלגוריתם האוקלידי מתבסס על העובדה הבאה: המחלק המשותף הגדול ביותר של \( x,y \) הוא גם המחלק המשותף המקסימלי של \( y,r \), כאשר \( r \) היא השארית שמקבלים כשמחלקים את \( x \) ב-\( y \). תרגיל - להוכיח שזה נכון (רמז: מתקיים \( x=qy+r \) עבור \( q \) שלם כלשהו).

אם כן, האלגוריתם האוקלידי פשוט פועל כך (תוך הנחה ש-\( x\ge y \)):

אם \( y \) מחלק את \( x \), החזר את \( y \).
אחרת, חשב את \( r=x \% y \) (% הוא אופרטור נפוץ בשפות תכנות לציון שארית של חלוקה).
הצב \( x:=y, y:=r \).
חזור לשלב 1.

זה האלגוריתם האוקלידי הפשוט. האלגוריתם המורחב לא סתם מוצא את המחלק המשותף המקסימלי; הוא גם מוצא \( a,b \) כך ש-\( ax+by=d \) (כש-\( d \) הוא המחלק המדובר - זהירות, לא להתבלבל עם \( d \) שלנו, שעליו נדבר אחר כך).

הרעיון הוא כזה: נניח שגילינו ש-\( x=qy+r \), אז בפרט \( r=x-qy \). כלומר, אפשר להציג את \( r \) בתור צירוף לינארי של \( x,y \). זה כך גם בהמשך הדרך: אם \( x\prime=a_1x+b_1y \) ו-\( y\prime=a_2x+b_2y \) הם המשתנים של האיטרציה הנוכחית שלנו, אז:

\( r\prime=x\prime-qy\prime=(a_1x+b_1y)-(qa_2x+qb_2y)=(a_1-qa_2)x+(b_1-qb_2)y \)

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

בסיכומו של דבר, מה שיקרה הוא הדבר הבא: מכיוון ש-\( e \) נבחר במפורש כך שיהיה זר ל-\( \varphi(n) \), אז המחלק המשותף המקסימלי שלהם הוא 1, כלומר קיימים \( a,b \) כך ש-\( ae+b\varphi(n)=1 \) - ואנחנו יודעים למצוא אותם די מהר. למה זה טוב? כי אם נסתכל על המשוואה הזו מודולו \( \varphi(n) \), אנחנו נקבל \( ae\equiv 1(\text{mod}\varphi(n)) \) (למה?) ולכן \( d \) שרצינו הוא בעצם המקדם \( a \).

שלב ה' - אז למה המשפט ה"עמוק" נכון?

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

סגירות: אם \( x,y\in G \) אז גם \( x\cdot y\in G \)
אסוציאטיביות: \( x\cdot(y\cdot z)=(x\cdot y)\cdot z \)
קיום איבר יחידה: קיים איבר \( 1\in G \) כך ש-\( x\cdot 1=1\cdot x=x \).
קיום איבר הופכי: לכל \( x\in G \) קיים \( x^{-1}\in G \) כך ש-\( x\cdot x^{-1}=x^{-1}\cdot x=1 \).

זה הכל.

דוגמאות לחבורות: המספרים הרציונליים בלי 0, המספרים השלמים כשפעולת ה”כפל” היא בעצם חיבור, וגם \( \mathbb{Z}^*_n \). הוכחה שאלו אכן חבורות - עזבו. לא עכשיו.

ועכשיו, מה אומר משפט לגראנז’? שבחבורה עם \( n \) איברים, כל תת קבוצה של החבורה שבעצמה מקיימת את ארבע האקסיומות של החבורה (לדבר כזה קוראים “תת-חבורה”) מכילה מספר איברים שמחלק את \( n \). למשל, אם יש לנו חבורה מסדר 6 (“סדר” של חבורה הוא מילה אחת ל”מספר האיברים שבחבורה”), תת החבורות היחידות האפשריות הן מסדר 1 (תת החבורה שמכילה רק את היחידה), 2, 3 ו-6 (“תת” החבורה שהיא בעצם החבורה עצמה). במילים אחרות - לא ייתכן שיש תת חבורות מסדר 4 או 5.

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

איך משפט לגראנז’ מתקשר למה שאנחנו עוסקים בו? בצורה הבאה. אם יש לנו איבר \( x\in G \) בחבורה מסדר \( n \), נתחיל להסתכל על האיברים \( x,x^2,x^3 \) וכן הלאה. מכיוון שיש אינסוף חזקות אפשריות של \( x \) ורק מספר סופי של איברים בחבורה, עולה מכך (בגלל עיקרון שובך היונים) שחייב להתקיים \( x^a=x^b \) עבור איזה שהם \( a,b \) טבעיים. מזה נובע שמתקיים \( x^a\cdot x^{-b}=1 \), או בסימון אחר: \( x^{a-b}=1 \) (צריך להוכיח שכל מה שאני עושה כאן נכון - כמובן שלא אעשה זאת כאן). במילים אחרות - קיימת חזקה של \( x \) שמעבירה אותו ל-1. לחזקה הטבעית הקטנה ביותר שמקיימת זאת קוראים הסדר של \( x \). הקשר ל”סדר של חבורה” אינו מקרי, כמובן; הסדר של \( x \) הוא בדיוק הסדר של תת החבורה שמקבלים על ידי לקיחת כל החזקות שלו (למה? ולמה בעצם כל החזקות הן חבורה?)

אם כן, על פי לגראנז’, הסדר של \( x \) מחלק את סדר החבורה, \( n \). על כן, \( x^n=1 \) (למה?) וזה כבר מביא אותנו ממש אל מה שרצינו להוכיח. בואו ניזכר מה זה היה: אם \( G \) חבורה עם \( n \) איברים, אז \( x^a=x^b \) אם \( a\equiv b(\text{mod}n) \)

אם כן, נניח כי \( a\equiv b(\text{mod}n) \). מה זה אומר? זה אומר שקיים \( t \) כלשהו כך ש-\( a-b=t\cdot n \). על כן, \( x^{a-b}=x^{tn}=(x^n)^t=1^t=1 \). על ידי העברת אגף מקבלים \( x^a=x^b \), וזהו זה.

שלב ו' - אז למה משפט לגראנז' נכון?

עלה בידי מישהו/מישהי לשרוד עד עכשיו?

ההוכחה של משפט לגראנז’ אינה מסובכת, אך גם היא דורשת קצת עבודה מוקדמת. הדרך הנכונה ללמוד אותה היא באמצעות ספר, ואני סתם אתן רמז: בהינתן חבורה \( G \) מסדר \( n \) ותת חבורה \( H \) שלה, הביטו ביחס השקילות המוגדר על ידי “\( x \) שקול ל-\( y \) אם ורק אם \( xy^{-1}\in H \). הוכיחו שזה אכן יחס שקילות, ולכן משרה חלוקה של \( G \), ושכל מחלקת שקילות מכילה אותו מספר של איברים (מחלקת שקילות שכזו מכונה “קוסט”). למה זה מסיים את ההוכחה?

נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ: