RSA - Hold My Beer

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

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

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

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

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

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

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

יאללה בואו נתחיל. (אני מדבר לעצמי הצילו)

1.1 - מהי הצפנה ולמה היא קיימת

1.1.1 - הגדרת הצפנה

הצפנה היא תהליך של המרת מידע קריא (Plaintext) למידע בלתי קריא (Ciphertext) באמצעות אלגוריתם ומפתח. רק מי שמחזיק במפתח הנכון יכול להפוך את המידע חזרה לקריא - זה הפענוח.

בצורה פורמלית:

הצפנה: E(K, M) = C

פענוח: D(K, C) = M

כאשר K = מפתח, M = הודעה, C = טקסט מוצפן.

1.1.2 - למה הצפנה קיימת

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

ארבע מטרות עיקריות של הצפנה:

סודיות (Confidentiality) - רק הנמען המיועד קורא את ההודעה.

שלמות (Integrity) - ההודעה לא שונתה בדרך.

אותנטיקציה (Authentication) - אפשר לוודא מי השולח.

אי-הכחשה (Non-Repudiation) - השולח לא יכול להכחיש ששלח את ההודעה.

1.1.3 - הצפנה סימטרית מול א-סימטרית

הצפנה סימטרית - אותו מפתח להצפנה ולפענוח. שני הצדדים חייבים לשתף מפתח סודי מראש. למשל AES, DES, ChaCha20. מהיר מאוד אבל הבעיה היא איך מעבירים את המפתח בצורה בטוחה?

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

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

1.2 - הצפנה לפני RSA

1.2.1 - צופנים קלאסיים

צופן קיסר - הזזת כל אות במספר קבוע של מקומות. A→D, B→E וכו’. מפתח = מספר ההזזה. שבירה מיידית. רק 25 אפשרויות.

צופן ויז’נר (Vigenère) - הזזה משתנה לפי מילת מפתח חוזרת. נחשב “בלתי שביר” ל300 שנה. נשבר ב-1863 ע"י Kasiski באמצעות ניתוח דפוסים חוזרים.

אניגמה - מכונת הצפנה אלקטרו-מכנית של גרמניה הנאצית. רוטורים מסתובבים שיצרו החלפות מורכבות. נשברה ע"י הפולנים (Rejewski) ואח"כ ע"י הבריטים (Turing) בבלצ’לי פארק. הדגימה שגם מערכות מורכבות ביותר נשברות כשיש פגם במבנה או בשימוש.

המכנה המשותף: כולם סימטריים. אותו מפתח להצפנה ולפענוח.

1.2.2 - בעיית חילופי המפתחות

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

אם אליס ובוב רוצים לתקשר בצורה מוצפנת, הם צריכים איכשהו להעביר מפתח ביניהם. אבל אם יש להם ערוץ מאובטח להעביר מפתח — למה הם צריכים הצפנה בכלל?

בעולם של 2 אנשים זה עוד ניתן לפתרון (נפגשים פיזית). בעולם של n אנשים צריך n(n-1)/2 מפתחות — לא סקיילבילי. 1000 משתמשים = 499,500 מפתחות.

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

1.2.3 - Diffie-Hellman 1976

ב1976, Whitfield Diffie וMartin Hellman פרסמו את המאמר “New Directions in Cryptography”

הם הציגו שני רעיונות מהפכניים:

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

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

1.2.4 - מה חסר אחרי Diffie-Hellman

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

Diffie ו-Hellman תיארו את הקונספט של מערכת מפתח ציבורי מלאה - אבל לא בנו אחת בעצמם. הם הציבו אתגר פתוח: מצאו פונקציה חד-כיוונית עם דלת אחורית (Trapdoor One-Way Function) שתאפשר הצפנה ופענוח.

1.3 - הולדת RSA

1.3.1 - מי הם Rivest, Shamir וAdleman

Ron Rivest - מדען מחשב אמריקאי, MIT. המוח שהציע את הנוסחאות המתמטיות. חיפש בלי הפסקה פונקציה חד-כיוונית עם דלת אחורית. הציע עשרות רעיונות - Shamir וAdleman הפילו כל אחד מהם עד שאחד שרד.

Adi Shamir - מתמטיקאי ישראלי. תרם לניתוח וביקורת ההצעות. ידוע גם כיוצר Shamir’s Secret Sharing ותרומות ענק לקריפטוגרפיה (Differential Cryptanalysis עם Biham)

Leonard Adleman - מתמטיקאי אמריקאי, USC. תפקידו היה “השובר” - ניסה להפיל כל הצעה של Rivest. כשלא הצליח להפיל את ההצעה האחרונה - ידעו שיש להם משהו. מאוחר יותר חלוץ בDNA Computing.

השם RSA = האותיות הראשונות של שמות משפחתם: Rivest, Shamir, Adleman.

1.3.2 - הסיפור מאחורי הגילוי

1977, MIT. אחרי קריאת המאמר של Diffie-Hellman, Rivest הבין שצריך למצוא מערכת מפתח ציבורי מעשית. הוא עבד עם Shamir וAdleman בלופ:

Rivest מציע מערכת, Shamir וAdleman מנסים לשבור, נשבר ,חוזרים להתחלה

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

1.3.3 - הפרסום המדעי

אפריל 1977 - דו"ח טכני MIT/LCS/TM-82: “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”.

פברואר 1978 - פורסם רשמית בCommunications of the ACM.

המאמר הציג:

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

שלושתם קיבלו את פרס טיורינג ב2002 על עבודה זו.

1.3.4 - ההיסטוריה הסודית - GCHQ

מה שלא היה ידוע עד 1997: סוכנות המודיעין הבריטית GCHQ הגיעה לרעיונות אלה קודם אבל בסיווג מלא.

1969-1970 - James Ellis (GCHQ) הגה את הרעיון של הצפנה א-סימטרית, שקרא לה “Non-Secret Encryption”. כתב מסמך פנימי שהוכיח שזה אפשרי תיאורטית אבל לא מצא פונקציה מתאימה.

1973 - Clifford Cocks, מתמטיקאי צעיר בGCHQ, מצא תוך פחות מ30 דקות פונקציה שעובדת - בדיוק המערכת שהיא RSA. חזקה מודולרית, מכפלת ראשוניים, הכל. 4 שנים לפני Rivest-Shamir-Adleman.

1974 - Malcolm Williamson (GCHQ) המציא באופן עצמאי את מה שהוא Diffie-Hellman Key Exchange - שנתיים לפני Diffie-Hellman.

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

1.3.5 - חברת RSA Security

1982 - Rivest, Shamir וAdleman ייסדו את RSA Data Security, Inc. כדי למסחר את האלגוריתם.

מוצרים מרכזיים:

• BSAFE - ספריית הצפנה
• SecurID - טוקני אימות דו-שלבי
• RSA Conference - הפך לכנס אבטחת המידע הגדול בעולם (מעניין ללכת)

2006 - RSA Security נרכשה ע"י EMC ב2.1 מיליארד דולר. EMC נרכשה ע"י Dell ב2016. (משתלם)

פרשת 2013 - Edward Snowden חשף שהNSA שילם לRSA Security כ10 מיליון דולר כדי שתשתמש בDual_EC_DRBG (מחולל מספרים אקראיים עם דלת אחורית חשודה של הNSA) כברירת מחדל בBSAFE. פגיעה אדירה באמינות החברה.

1.3.6 - פטנט RSA

פטנט מספר 4,405,829. הוגש 1977, אושר 1983. MIT החזיקה בפטנט והעניקה רישיון בלעדי לRSA Data Security.

השלכות:

• שימוש מסחרי בRSA בארה"ב דרש רישיון בתשלום
• PGP של Phil Zimmermann נקלע לבעיות משפטיות בגלל זה
• מחוץ לארה"ב הפטנט לא היה תקף - שימוש חופשי
• זה דחף פיתוח חלופות כמו ElGamal וDSA (שנבחר על ידי NIST בחלקו כדי לעקוף את הפטנט)

ב6 בספטמבר 2000 הפטנט פקע. RSA הפך לחופשי לשימוש בכל מקום. שבועיים לפני תפוגת הפטנט, RSA Security שחררה את האלגוריתם לרשות הציבור.

ועכשיו מתחיל הכאב ראש האמיתי יאיי...

2.1 - חלוקה, חלוקות ומחלקים

2.1.1 - מושג החלוקה (Divisibility)

כשאומרים “a מתחלק בb”,הכוונה היא שa חלקי b יוצא מספר שלם בלי שארית.

דוגמאות:

12 ÷ 3 = 4 יצא מספר שלם. 12 מתחלק ב3

12 ÷ 5 = 2.4 לא מספר שלם. 12 לא מתחלק ב5

סימון מתמטי:

כותבים b | a (b מחלק את a).

3 | 12 ✓ (3 מחלק את 12)
5 | 12 ✗ (5 לא מחלק את 12)

במילים אחרות b | a אם קיים מספר שלם k כך ש a = b × k

• 12 = 3 × 4 אז 3 | 12
• אין מספר שלם k שעבורו 12 = 5 × k. אז 5 לא מחלק 12

“מחלקים” של מספר = כל המספרים שהוא מתחלק בהם:

המחלקים של 12 הם 1, 2, 3, 4, 6, 12

המחלקים של 15 הם 1, 3, 5, 15

סבבה קל

2.1.2 - מחלק משותף גדול ביותר (GCD)

GCD = Greatest Common Divisor = המחלק המשותף הגדול ביותר

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

דוגמה:

מחלקי 12: {1, 2, 3, 4, 6, 12}
מחלקי 18: {1, 2, 3, 6, 9, 18}

מחלקים משותפים: {1, 2, 3, 6}

הגדול ביותר: 6

אז GCD(12, 18) = 6

עוד דוגמאות:

GCD(8, 12) = 4
GCD(7, 13) = 1
GCD(100, 75) = 25

כשהGCD הוא 1, אומרים שהמספרים “זרים זה לזה” (coprime / relatively prime) זה אומר שאין להם שום מחלק משותף חוץ מ1.

GCD(8, 15) = 1 - 8 ו15 זרים זה לזה
GCD(9, 14) = 1 - זרים

GCD חשוב לRSA כי בבחירת e (חלק מהמפתח הציבורי) צריך לוודא ש-GCD(e, φ(n)) = 1. אם הם לא זרים - המפתח לא יעבוד. בנוסף, מציאת ההופכי הכפלי (שזה d - המפתח הפרטי) נעשית דרך אלגוריתם שמבוסס על GCD.

מובן

שיטת כוח גס למציאת GCD:

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

2.1.3 - אלגוריתם אוקלידס (Euclidean)

אוקלידס כתב אותו בסביבות 300 לפנה"ס. והוא עדיין בשימוש היום. וואו

במקום לרשום את כל המחלקים יש קיצור דרך

הכלל:

GCD(a, b) = GCD(b, a mod b)

מה זה mod? פעולת mod (מודולו) נותנת את השארית של חלוקה.

12 mod 5 = 2 (כי 12 ÷ 5 = 2 שארית 2)
17 mod 3 = 2 (כי 17 ÷ 3 = 5 שארית 2)
10 mod 2 = 0 (כי 10 ÷ 2 = 5 שארית 0)
7 mod 4 = 3 (כי 7 ÷ 4 = 1 שארית 3)

חוזרים על GCD(a, b) = GCD(b, a mod b) עד שהשארית מגיעה ל0.
כשb = 0, התשובה היא a.

דוגמה: GCD(252, 105)

GCD(252, 105)
252 mod 105 = 42 - GCD(105, 42)
105 mod 42 = 21 - GCD(42, 21)
42 mod 21 = 0 - GCD(21, 0)

התשובה: 21

נפרט:

• 252 ÷ 105 = 2, שארית 252 - 210 = 42
• 105 ÷ 42 = 2, שארית 105 - 84 = 21
• 42 ÷ 21 = 2, שארית 42 - 42 = 0 ← עצור

דוגמה נוספת: GCD(48, 18)

48 mod 18 = 12 - GCD(18, 12)
18 mod 12 = 6 - GCD(12, 6)
12 mod 6 = 0 - GCD(6, 0)

התשובה: 6

דוגמה עם זרים: GCD(17, 5)

17 mod 5 = 2 - GCD(5, 2)
5 mod 2 = 1 - GCD(2, 1)
2 mod 1 = 0 - GCD(1, 0)

התשובה: 1 הם זרים זה לזה.

למה זה עובד? אם מספר d מחלק גם את a וגם את b, אז הוא בהכרח מחלק גם את (a mod b). ולכן הGCD לא משתנה כשעושים את ההחלפה. כל צעד מקטין את המספרים עד שאחד מהם הוא 0.

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

2.1.4 אלגוריתם אוקלידס המורחב

בנוסף למציאת GCD(a, b) הוא מוצא שני מספרים x וy כאלה ש:

a·x + b·y = GCD(a, b)

כלומר הוא מבטא את הGCD כצירוף ליניארי של a וb.

דוגמה: נמצא x, y כך ש 252·x + 105·y = GCD(252, 105) = 21

שלב 1 אלגוריתם אוקלידס הרגיל:

252 = 2 × 105 + 42
105 = 2 × 42  + 21
42  = 2 × 21  + 0

שלב 2 עבודה אחורה (Back Substitution):

מהשורה השנייה:

21 = 105 - 2 × 42

מהשורה הראשונה: 42 = 252 - 2 × 105. נציב:

21 = 105 - 2 × (252 - 2 × 105)
21 = 105 - 2×252 + 4×105
21 = 5×105 - 2×252

אז:

252 × (-2) + 105 × 5 = 21  ✓

x = -2, y = 5

בדיקה: 252 × (-2) + 105 × 5 = -504 + 525 = 21 ✓

מימוש טבלאי:

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

מתחילים עם:

r₀ = a,   x₀ = 1,   y₀ = 0
r₁ = b,   x₁ = 0,   y₁ = 1

בכל צעד:

q = r₀ ÷ r₁ (חלוקה שלמה — בלי שארית)
r₂ = r₀ - q × r₁
x₂ = x₀ - q × x₁
y₂ = y₀ - q × y₁

ואז מזיזים: r₀-r₁, r₁-r₂, וכן הלאה.

דוגמה: a=252, b=105

עצירה כאשר r = 0. השורה הקודמת נותנת:

GCD = 21, x = -2, y = 5

252 × (-2) + 105 × 5 = 21 ✓

כשצריך למצוא את d כך ש e·d ≡ 1 (mod φ(n)), מה שבעצם מחפשים זה x במשוואה e·x + φ(n)·y = 1. אלגוריתם אוקלידס המורחב מוצא את הx הזה וזה d, המפתח הפרטי.

2.1.5 - זהות בזו (Bézout’s Identity) שם נוראי

לכל שני מספרים שלמים a וb (שלא שניהם 0), קיימים מספרים שלמים x וy כך ש:

a·x + b·y = GCD(a, b)

ויותר מזה: GCD(a,b) הוא המספר החיובי הקטן ביותר שאפשר לבטא בצורה a·x + b·y.

דוגמאות:

GCD(12, 8) = 4:

12 × 1 + 8 × (-1) = 4  ✓

GCD(7, 5) = 1:

7 × 3 + 5 × (-4) = 21 - 20 = 1  ✓

GCD(35, 15) = 5:

35 × 1 + 15 × (-2) = 35 - 30 = 5  ✓

נקודה קריטית לRSA:

אם GCD(a, b) = 1 (כלומר a ו-b זרים), אז תמיד קיימים x, y כך ש:

a·x + b·y = 1

זה מבטיח שאם e וφ(n) זרים (וזה דרישה של RSA), בהכרח קיים d כזה ש e·d + φ(n)·y = 1, שזה אותו דבר כמו e·d ≡ 1 (mod φ(n)). כלומר המפתח הפרטי תמיד קיים כל עוד בחרנו e נכון.

x וy אינם יחידים. יש אינסוף זוגות שעובדים. אם (x₀, y₀) הוא פתרון, אז גם (x₀ + kb/GCD, y₀ - ka/GCD) לכל מספר שלם k.

יותר מידי השלמות חומר במתמטיקה...

2.2 - מספרים ראשוניים

2.2.1 - הגדרת מספר ראשוני

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

• 2 - מתחלק רק ב1 וב2 - ראשוני
• 3 - מתחלק רק ב-1 וב-3 - ראשוני
• 4 - מתחלק ב1, 2, 4 - לא ראשוני (כי 2 מחלק אותו)
• 5 - רק 1 ו5 - ראשוני
• 6 - מתחלק ב1, 2, 3, 6 - לא ראשוני
• 7 - ראשוני
• 9 - מתחלק ב3 - לא ראשוני
• 11 - ראשוני
• 13 - ראשוני

מספר שאינו ראשוני (וגדול מ1) נקרא “פריק” (Composite) - כי אפשר “לפרק” אותו למכפלה של מספרים קטנים ממנו.

מקרים מיוחדים

• 1 - לא ראשוני ולא פריק. הוא בקטגוריה לבד. הוחלט על כך מוסכמה מתמטית.
• 2 - הראשוני הזוגי היחיד. כל ראשוני אחר הוא אי-זוגי (כי כל זוגי אחר מתחלק ב2).

כל RSA מתחיל מבחירת שני מספרים ראשוניים גדולים p וq. אם הם לא באמת ראשוניים - האלגוריתם נשבר לגמרי.

2.2.2 - משפט היסוד של האריתמטיקה

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

זה אומר שהראשוניים הם “אבני הבניין” של כל המספרים. כל מספר מורכב מראשוניים, בדיוק כמו שכל מולקולה מורכבת מאטומים.

דוגמאות — פירוק לגורמים ראשוניים:

12  = 2 × 2 × 3         = 2² × 3
30  = 2 × 3 × 5
100 = 2 × 2 × 5 × 5     = 2² × 5²
84  = 2 × 2 × 3 × 7     = 2² × 3 × 7
360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5
17  = 17                  (ראשוני — הוא עצמו הפירוק)

“בדרך יחידה” זה החלק הקריטי. אין שתי דרכים שונות לפרק מספר לראשוניים. 12 תמיד יהיה 2² × 3 אין אפשרות אחרת.

מתחילים לחלק בראשוני הקטן ביותר (2) ממשיכים עד שלא מתחלק, עוברים ל3, אחר כך 5, 7, וכו’.

פירוק 180:

180 ÷ 2 = 90
90  ÷ 2 = 45
45  ÷ 3 = 15
15  ÷ 3 = 5
5   ÷ 5 = 1   ← סיימנו

180 = 2² × 3² × 5

RSA מבוסס על העובדה ש:

• לכפול שני ראשוניים גדולים - קל. p × q = n, חישוב מהיר.
• לפרק n בחזרה לp וq - קשה מאוד כשהמספרים גדולים.

זה כל הבסיס של RSA. משפט היסוד מבטיח שהפירוק קיים ויחיד - אז p וq מוגדרים היטב. אבל למצוא אותם זו הבעיה.

כמה קשה? עם מספרים בני 300+ ספרות (1024 ביט), אין שום מחשב קלאסי שיכול לפרק אותם בזמן סביר. זה ייקח יותר זמן מגיל היקום.

2.2.3 - אינסוף המספרים הראשוניים - הוכחת אוקלידס

יש אינסוף מספרים ראשוניים. הרשימה לא נגמרת לעולם.

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

ההוכחה (אוקלידס, ~300 לפנה"ס):

נניח בשלילה שיש מספר סופי של ראשוניים למשל

p₁, p₂, p₃, ..., pₖ

זו כביכול כל הרשימה. אין יותר.

עכשיו ניצור מספר חדש

N = p₁ × p₂ × p₃ × ... × pₖ + 1

כלומר נכפיל את כולם ונוסיף 1.

מה קורה עם N?

נחלק את N בכל ראשוני מהרשימה:

• N ÷ p₁ - שארית 1 (כי N = p₁ × [כל השאר] + 1)
• N ÷ p₂ - שארית 1
• N ÷ p₃ - שארית 1
• … וכן לכל ראשוני ברשימה

אז N לא מתחלק באף ראשוני מהרשימה.

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

סתירה! הנחנו שהרשימה כוללת את כולם.

מסקנה: אי אפשר שתהיה רשימה סופית. יש אינסוף ראשוניים.

נניח שהראשוניים היחידים הם 2, 3, 5.

N = 2 × 3 × 5 + 1 = 31

31 הוא ראשוני. מצאנו ראשוני חדש שלא ברשימה.

ראשוניים 2, 3, 5, 7.

N = 2 × 3 × 5 × 7 + 1 = 211

211 הוא ראשוני. שוב מצאנו חדש.

N לא חייב להיות ראשוני בעצמו. הוא רק חייב להכיל ראשוני שלא ברשימה. לדוגמה: 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509. שניהם ראשוניים שלא ברשימה המקורית.

2.2.4 - Prime Number Theorem

ידענו שיש אינסוף ראשוניים. אבל כמה צפופים הם? כמה ראשוניים יש עד מספר מסוים?

סימון: π(n) = מספר הראשוניים שקטנים או שווים לn.

π(10)  = 4      (הראשוניים: 2, 3, 5, 7)
π(100) = 25
π(1000) = 168
π(1,000,000) = 78,498

המשפט (הוכח ב1896):

π(n) ≈ n / ln(n)

כאשר ln הוא הלוגריתם הטבעי (לוגריתם בבסיס e ≈ 2.718).

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

כמה ראשוניים בני 1024 ביט יש?

מספר בן 1024 ביט הוא בין 2¹⁰²³ ל-2¹⁰²⁴. זה מספר עם כ-308 ספרות עשרוניות.

ההסתברות שמספר אקראי בגודל הזה יהיה ראשוני

1 / ln(2¹⁰²⁴) ≈ 1 / 710 ≈ 0.14%

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

מספיק לנסות כמה מאות מספרים אקראיים עד שמוצאים ראשוני. זה מהיר. אין בעיה למצוא ראשוניים גדולים כי יש המון מהם, גם בגדלים עצומים. מספר הראשוניים בני 512 ביט (שזה חצי מ1024) הוא בערך 10¹⁵⁰ שהוא מספר מטורף שגדול ממספר האטומים ביקום (כ-10⁸⁰).

2.2.5 - Mersenne Primes

מספר מרסן הוא מספר מהצורה

Mₚ = 2ᵖ - 1

כאשר p הוא ראשוני.

M₂ = 2² - 1 = 3        ← ראשוני ✓
M₃ = 2³ - 1 = 7        ← ראשוני ✓
M₅ = 2⁵ - 1 = 31       ← ראשוני ✓
M₇ = 2⁷ - 1 = 127      ← ראשוני ✓
M₁₁ = 2¹¹ - 1 = 2047 = 23 × 89  ← לא ראשוני ✗
M₁₃ = 2¹³ - 1 = 8191   ← ראשוני ✓

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

• הם המספרים הראשוניים הגדולים ביותר שידועים לנו. נכון ל2024, הראשוני הגדול ביותר הידוע הוא 2⁸²,⁵⁸⁹,⁹³³ - 1 (כ-24.8 מיליון ספרות). הוא מספר מרסן.
• יש מבחן ראשוניות יעיל במיוחד עבורם (Lucas-Lehmer) שהוא הרבה יותר מהיר מהמבחנים הכלליים.
• פרויקט GIMPS מחפש אותם באופן מבוזר.

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

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

2.3 - אריתמטיקה מודולרית

2.3.1 - הגדרת חפיפה (Congruence)

כל חישוב בRSA - הצפנה, פענוח, יצירת מפתחות - הכל קורה “במודולו”.

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

הפעולה mod נותנת את השארית.

17 mod 5 = 2    (כי 17 ÷ 5 = 3, שארית 2)
23 mod 5 = 3    (כי 23 ÷ 5 = 4, שארית 3)
10 mod 5 = 0    (כי 10 ÷ 5 = 2, שארית 0)

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

סימון:

a ≡ b (mod n)

נקרא: “a חופף לb מודולו n”

17 ≡ 2 (mod 5)    כי שניהם נותנים שארית 2 כשמחלקים ב-5
23 ≡ 3 (mod 5)    כי שניהם נותנים שארית 3
17 ≡ 12 (mod 5)   כי 17 mod 5 = 2, ו-12 mod 5 = 2 — אותה שארית
38 ≡ 14 (mod 12)  כי 38 mod 12 = 2, ו-14 mod 12 = 2

הגדרה שקולה: a ≡ b (mod n) אם ורק אם n מחלק את (a - b).

17 ≡ 12 (mod 5) כי 17 - 12 = 5, ו-5 מתחלק ב-5
38 ≡ 14 (mod 12) כי 38 - 14 = 24, ו-24 מתחלק ב-12

אנלוגיה - שעון:

שעון הוא אריתמטיקה מודולו 12. אחרי 12 חוזרים ל0.

שעה 15 = שעה 3      (15 ≡ 3 mod 12)
שעה 25 = שעה 1      (25 ≡ 1 mod 12)
שעה 0 = שעה 12      (0 ≡ 12 mod 12... אבל בשעון כותבים 12)

באריתמטיקה מודולו n, יש רק n ערכים אפשריים: 0, 1, 2, …, n-1. כל מספר “נופל” על אחד מהם.

מודולו 5 - כל המספרים נופלים על 0,1,2,3,4:

0, 5, 10, 15, 20, ...  → כולם ≡ 0 (mod 5)
1, 6, 11, 16, 21, ...  → כולם ≡ 1 (mod 5)
2, 7, 12, 17, 22, ...  → כולם ≡ 2 (mod 5)
3, 8, 13, 18, 23, ...  → כולם ≡ 3 (mod 5)
4, 9, 14, 19, 24, ...  → כולם ≡ 4 (mod 5)

2.3.2 - חוקי חיבור חיסור וכפל במודולו

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

חיבור:

(a + b) mod n = ((a mod n) + (b mod n)) mod n

(17 + 23) mod 5

40 mod 5 = 0

(17 mod 5) + (23 mod 5) = 2 + 3 = 5, ואז 5 mod 5 = 0

חיסור:

(a - b) mod n = ((a mod n) - (b mod n)) mod n

(23 - 17) mod 5

6 mod 5 = 1

3 - 2 = 1, ואז 1 mod 5 = 1

אם יוצא שלילי
(17 - 23) mod 5 = -6 mod 5 = ?

בחיסור אם יוצא שלילי מוסיפים n עד שמגיעים לטווח 0…n-1:

-6 + 5 = -1 → עדיין שלילי
-1 + 5 = 4

אז -6 mod 5 = 4

-6 ≡ 4 (mod 5) כי -6 - 4 = -10, ו-5 מחלק את -10

כפל:

(a × b) mod n = ((a mod n) × (b mod n)) mod n

(17 × 23) mod 5

391 mod 5 = 1

(17 mod 5) × (23 mod 5) = 2 × 3 = 6, ואז 6 mod 5 = 1 ✓

בRSA מחשבים דברים כמו mᵉ mod n, כאשר m, e, n הם מספרים עם מאות ספרות. אם היינו מחשבים קודם את mᵉ (מספר עם מיליוני ספרות) ורק אז עושים mod - המחשב היה מתפוצץ. אבל בזכות הכלל הזה, אפשר לעשות mod אחרי כל כפל, ולשמור את המספרים קטנים לאורך כל הדרך.

חילוק - הלפ

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

6 / 2 = 3 בחשבון רגיל. אבל במודולו:
6 ≡ 1 (mod 5), ו-2 ≡ 2 (mod 5)
1 / 2 = 0.5 ← לא מספר שלם, אין טעם

במקום חילוק משתמשים בהופכי כפלי זה בעצם “חילוק מודולרי”

2.3.3 - שאריות ומחלקות שקילות

מחלקת שקילות - קבוצה של כל המספרים שנותנים אותה שארית.

מודולו 5 - חמש מחלקות שקילות:

[0] = {..., -10, -5, 0, 5, 10, 15, 20, ...}
[1] = {..., -9, -4, 1, 6, 11, 16, 21, ...}
[2] = {..., -8, -3, 2, 7, 12, 17, 22, ...}
[3] = {..., -7, -2, 3, 8, 13, 18, 23, ...}
[4] = {..., -6, -1, 4, 9, 14, 19, 24, ...}

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

כשעובדים מודולו n, בעצם עובדים עם n מחלקות. הסימון:

ℤₙ = {0, 1, 2, ..., n-1}

ℤ₅ = {0, 1, 2, 3, 4}

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

למשל מודולו 5, נחבר את [2] ו-[4]:

ניקח נציגים 2 + 4 = 6 ≡ 1 (mod 5) → תוצאה [1]

ניקח נציגים אחרים 7 + 9 = 16 ≡ 1 (mod 5) → עדיין [1]

ניקח נציגים אחרים 12 + 14 = 26 ≡ 1 (mod 5) → עדיין [1]

זה תמיד עובד זו תכונה שנקראת “מוגדר היטב” (Well-Defined).

2.3.4 - פתרון משוואות ליניאריות במודולו

הבעיה היא למצוא x כך ש:

a·x ≡ b (mod n)

יש פתרון כשלמשוואה a·x ≡ b (mod n) יש פתרון אם ורק אם GCD(a, n) מחלק את b.

מקרה פשוט - GCD(a, n) = 1:

אם a וn זרים, יש פתרון יחיד (מודולו n).

למשל 3x ≡ 2 (mod 5)

GCD(3, 5) = 1 ✓ → יש פתרון יחיד.

x = 0, 1, 2, 3, 4:

x=0: 3×0 = 0  ≡ 0 (mod 5) ✗
x=1: 3×1 = 3  ≡ 3 (mod 5) ✗
x=2: 3×2 = 6  ≡ 1 (mod 5) ✗
x=3: 3×3 = 9  ≡ 4 (mod 5) ✗
x=4: 3×4 = 12 ≡ 2 (mod 5) ✓

x = 4

מקרה שאין פתרון

2x ≡ 3 (mod 4)

GCD(2, 4) = 2, ו2 לא מחלק 3 → אין פתרון.

x=0: 0 mod 4 = 0 ✗
x=1: 2 mod 4 = 2 ✗
x=2: 4 mod 4 = 0 ✗
x=3: 6 mod 4 = 2 ✗

רק 0 ו2 אפשריים - לעולם לא 3.

מקרה עם מספר פתרונות

פתור 2x ≡ 4 (mod 6)

GCD(2, 6) = 2, ו-2 מחלק 4 → יש פתרון. בעצם יש GCD = 2 פתרונות.

x=0: 0 mod 6 = 0 ✗
x=1: 2 mod 6 = 2 ✗
x=2: 4 mod 6 = 4 ✓
x=3: 6 mod 6 = 0 ✗
x=4: 8 mod 6 = 2 ✗
x=5: 10 mod 6 = 4 ✓

פתרונות: x = 2, x = 5

המשוואה e·d ≡ 1 (mod φ(n)) היא בדיוק מהסוג הזה. כי GCD(e, φ(n)) = 1 (זו הדרישה), ו1 מתחלק ב1, אז בהכרח יש פתרון יחיד - והוא d, המפתח הפרטי.

2.3.5 - Chinese Remainder Theorem

משפט עתיק מסין (מאות 3-5 לספירה). מתמטיקאי סיני בשם סון דזה שאל

איזה מספר נותן שארית 2 כשמחלקים ב3, שארית 3 כשמחלקים ב5, ושארית 2 כשמחלקים ב7?

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

אם כל המודולואים זרים זה לזה בזוגות (GCD של כל זוג = 1), אז למערכת יש פתרון יחיד מודולו המכפלה של כולם.

כאן 3, 5, 7 זרים בזוגות. אז יש פתרון יחיד מודולו 3 × 5 × 7 = 105.

פתרון

x ≡ 2 (mod 3) → x יכול להיות: 2, 5, 8, 11, 14, 17, 20, 23, …

מתוכם, x ≡ 3 (mod 5) → סינון: 8, 23, 38, 53, 68, 83, 98, …

מתוכם, x ≡ 2 (mod 7) → סינון: 23, 128, …

x = 23 (ו-23 + 105 = 128, ו-23 + 210 = 233, וכו’)

23 mod 3 = 2 ✓
23 mod 5 = 3 ✓
23 mod 7 = 2 ✓

פתרון שיטתי

נסמן N = 3 × 5 × 7 = 105

לכל משוואה i, נגדיר:

Nᵢ = N / nᵢ    (המכפלה של כל המודולואים חוץ מהנוכחי)

N₁ = 105 / 3 = 35
N₂ = 105 / 5 = 21
N₃ = 105 / 7 = 15

עכשיו מוצאים את ההופכי של כל Nᵢ מודולו nᵢ:

35 × y₁ ≡ 1 (mod 3) → 35 mod 3 = 2, אז 2 × y₁ ≡ 1 (mod 3) → y₁ = 2
21 × y₂ ≡ 1 (mod 5) → 21 mod 5 = 1, אז 1 × y₂ ≡ 1 (mod 5) → y₂ = 1
15 × y₃ ≡ 1 (mod 7) → 15 mod 7 = 1, אז 1 × y₃ ≡ 1 (mod 7) → y₃ = 1

הפתרון

x = (a₁ × N₁ × y₁ + a₂ × N₂ × y₂ + a₃ × N₃ × y₃) mod N
x = (2 × 35 × 2  +  3 × 21 × 1  +  2 × 15 × 1) mod 105
x = (140 + 63 + 30) mod 105
x = 233 mod 105
x = 23 ✓

יש לcrt שני שימושים עיקריים:

1) פענוח מהיר (CRT-RSA): במקום לחשב m = cᵈ mod n ישירות (n ענק), מחשבים בנפרד:

m₁ = cᵈ mod p
m₂ = cᵈ mod q

ואז משחזרים את m מm₁ וm₂ באמצעות CRT

2) הוכחת נכונות RSA: בהוכחה שmᵉᵈ ≡ m (mod n), מוכיחים בנפרד mod p וmod q, וCRT מאחד את התוצאות.

2.3.6 - הוכחת CRT

יהיו n₁, n₂, …, nₖ מספרים זרים בזוגות (GCD(nᵢ, nⱼ) = 1 לכל i ≠ j).

אז למערכת

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)

יש פתרון יחיד מודולו N = n₁ × n₂ × … × nₖ.

הוכחה

בונים את הפתרון בצורה מפורשת. לכל i מגדירים Nᵢ = N/nᵢ. כיוון ש-nᵢ זר לכל שאר ה-nⱼ, הוא זר גם ל-Nᵢ (שהוא מכפלת כל השאר). לכן GCD(Nᵢ, nᵢ) = 1, ולכן (לפי זהות בזו) קיים הופכי yᵢ כך ש-Nᵢ × yᵢ ≡ 1 (mod nᵢ). ואז:

x = Σ(aᵢ × Nᵢ × yᵢ) mod N

נסתכל על הרכיב aᵢ × Nᵢ × yᵢ מודולו nⱼ:

• אם j = i: Nᵢ × yᵢ ≡ 1 (mod nᵢ), אז הרכיב ≡ aᵢ (mod nᵢ) ✓
• אם j ≠ i: Nᵢ הוא מכפלה שכוללת nⱼ, אז Nᵢ ≡ 0 (mod nⱼ), אז כל הרכיב ≡ 0 (mod nⱼ)

אז כשמסתכלים על x מודולו nᵢ, כל הרכיבים מתאפסים חוץ מה-i-י שנותן aᵢ. בול.

נניח x₁ וx₂ שניהם פתרונות. אז x₁ - x₂ מתחלק בכל nᵢ. כיוון ש-nᵢ זרים בזוגות, x₁ - x₂ מתחלק ב-N (מכפלת כולם). אז x₁ ≡ x₂ (mod N). הפתרון יחיד מודולו N.

x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)

N = 2 × 3 × 5 = 30

N₁ = 30/2 = 15,  N₂ = 30/3 = 10,  N₃ = 30/5 = 6

הופכיים

15 × y₁ ≡ 1 (mod 2) → 15 mod 2 = 1, אז y₁ = 1
10 × y₂ ≡ 1 (mod 3) → 10 mod 3 = 1, אז y₂ = 1
6  × y₃ ≡ 1 (mod 5) → 6 mod 5 = 1,  אז y₃ = 1

x = (1×15×1 + 2×10×1 + 3×6×1) mod 30
x = (15 + 20 + 18) mod 30
x = 53 mod 30
x = 23

בדיקה

23 mod 2 = 1 ✓
23 mod 3 = 2 ✓
23 mod 5 = 3 ✓

נניח n = p × q = 5 × 7 = 35. וצריך לחשב m = 8ᵈ mod 35.

במקום לחשב ישירות אפשר לחשב

m₁ = 8ᵈ mod 5
m₂ = 8ᵈ mod 7

ואז CRT נותן

x ≡ m₁ (mod 5)
x ≡ m₂ (mod 7)

פתרון יחיד מודולו 35 - וזה m.

כאן פרשתי