#abstract_algebra #computer_science

RSA

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

בר רוצה לשלוח מסר $x$ לאילן.
נתאר את התרחיש הבא-
יצירת המפתח:

אילן מכין ״מנעול״ שיישלח לבר. הוא בוחר 2 ראשוניים גדולים (בקירוב של $2^{1024}$ ). נסמנם $p, q$ .
אילן מחשב $n = p q$ .
אילן מחשב בנוסף $m = φ (n) = (p - 1) (q - 1)$ .
אילן מגריל $e$ שזר ל $m$
אילן מחשב את $d = e^{- 1} \in U_{m}$

הפצת המפתח:

אילן מפרסם לבר באופן אמין אך לא בהכרח מוצפן את הזוג $(n, e)$
$d$ הוא מפתח סודי והוא שומר אותו לעצמו.

הצפנה:

בר שולחת מסר $1 \leq x < n$ . $x$ הוא מספר אבל הוא יכול להוות מוסכמה על מסר כלשהו $M$ זה כבר תלוי במידע שרוצים להעביר.
בר שולחת $y = x^{e} \mod n$ לאילן.

פענוח:
אילן מחלץ את המספר על ידי החישוב הבא $x = y^{d} \mod n$

דוגמה להצפנה

אילן מגריל את $p = 61$ ו $q = 53$
כעת מתקיים

n = p q = 3233

φ (n) = (p - 1) (q - 1) = 3120

אילן מגריל בנוסף $e = 17$ (הוא ראשוני ולכן זר לנ״ל) ויתקיים שהמפתח הסודי הוא

d \equiv_{3120} e^{- 1} \equiv_{3120} 2753

כעת אילן מפרסם את $(3233, 17)$ ומחכה...
בר רוצה לשלוח את $x = 65$ לאילן. היא מחשבת את ההודעה המוצפנה

y = x^{17} m o d 3233 = 2790

בר שולחת את $y$ לאילן... והוא מחלץ את המידע באמצעות $d$ כלומר

x = 2790^{2753} \equiv_{3233} 65

ישנן כמה שאלות שעולות לנו

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

נכונות

כדי להראות נכונות נוכיח שתי טענות מרכזיות
טענה 1 : $φ (n) = m$
אנחנו יודעים שהמשמעות של פונקציית אוילר היא סדר של חבורה אוילר כלומר כל המספרים שזרים ל $n$ ב $Z_{n}$ . כיוון ש $n = p q$ כלומר מכפלת שתי ראשוניים שקטנים ממנו אז נצטרך להסיך מהטווח $[n]$ את כל המספרים שהם מחלקים של $n$ שזה בעצם $1, q, p, n$ . כיוון שנרצה להשאיר רק את מי שזר ל $n$ הרי שכל המספרים ש $p, q$ מחלקים נצטרך להוריד גם אותם. אלו בעצם יהיו

{i q | i \in [p]} {j p | j \in [q]}

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

| [n] | - (p + q - 1) = n - (p + q - 1) = p q - p - q + 1 = (p - 1) (q - 1)

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

טענה 2 : $y^{d} \equiv_{n} x$
מתקיים $d = e^{- 1} \in U_{m}$ ולכן $d e \equiv_{m} 1$ כלומר $d e = 1 + k \cdot m$ . נשים לב גם ש $y^{d} = (x^{e})^{d} = x^{e d} \in Z_{n}$ כאשר פעולת החזקה היא עם מודולו $n$ .
נחלק למקרים:

אם $x$ זר ל $n$ - כלומר $x \in U_{n}$ ולכן $x^{φ (n)} = 1$ ממשפט אוילר כלומר יתקיים סך הכל

y^{d} = (x^{e})^{d} = x^{e d} = x^{1 + k m} = x \cdot (x^{m})^{k} = x \cdot (x^{φ (n)})^{k} \equiv_{n} x

אם $x$ לא זר ל $n$ אז $q | x$ או $p | x$ , בלי הגבלת הכלליות נניח $x = t \cdot p$ . מההנחה הזאת אנחנו יודעים ש $(x, q) = 1$ אחרת $p q | x$ כלומר $n$ מחלק של מספר קטן ממנו, מצב לא אפשרי . מהמשפט הקטן של פרמה מתקיים $x^{q - 1} \equiv_{q} 1$ וסך הכל...

x^{k m} = x^{k (p - 1) (q - 1)} = (x^{q - 1})^{k (p - 1)} \equiv_{q} 1

לכן, $x^{k m} = h q + 1$ ואם נציב ב $y$ נקבל

y^{d} = x^{1 + k m} = x x^{k m} = x (h q + 1) = x + h q x = x + h q t p = x + n h p \equiv_{n} x

העלאה מהירה בחזקה

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

נניח שנרצה לחשב את $x^{17}$ נשים לב שמתקיים $17 = 16 + 1$ כלומר נוכל לחשב את $x^{16}$ באופן הבא

x, x^{2}, (x^{2})^{2}, (x^{4})^{2}, (x^{8})^{2}

ולהכפיל את התוצאה ב $x$ . ביצענו פחות פעולות ואחרי כל העלאה בריבוע נבצע mod אם צריך וככה גם נעבוד עם מספרים נמוכים יותר.

אלגוריתם מילר רבין

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

עובדה

כמות הראשוניים עד $n$ היא בערך $\frac{n}{\log n}$ . כלומר הסיכוי שמספר אקראי עד $n$ הוא ראשוני יהיה $\frac{1}{\log n}$ .

האלגוריתם הינו אלגוריתם הסתברותי לאס וגאס ובבסיסו עומד המשפט הקטן של פרמה שאומר שעבור $p$ ראשוני אז $a^{p - 1} \equiv_{p} 1$ . הבעיה עם המשפט הזה היא שיש מספרים לא ראשוניים שמקיימים אותו לכל $a$ ולכן צריך לפתור את זה באופן הסתברותי ולצמצם את אחוז השגיאות. לפני שניגש לאלגוריתם מספר טענות חשובות

טענה 1 יהי $p$ ראשוני ו $x \in Z_{p}$ אזי $x^{2} = 1 \leftrightarrow x = \pm 1$ . כלומר $x = 1 \lor x = p - 1$ .

הוכחה-
בכיוון הראשון ברור שאם $x$ הוא אחד מהערכים הנ״ל אז העלאה שלו בריבוע תיתן $1$ .
בכיוון השני מתקיים ש $x^{2} - 1 = 0 \to (x - 1) (x + 1) = 0$
אמרנו כבר ש $Z_{p}$ הוא שדה ולכן אין מחלקי $0$ ולכן $x - 1 = 0$ או $x + 1 = 0$ .

הבחנה חשובה

אם $p$ ראשוני גדול מ 2 אז $2 | p - 1$ ולכן $p - 1 = 2^{s} \cdot r$ מכאן כבר אנחנו יכולים להבין לאן האלגוריתם הולך... נבטא את $a^{p - 1}$ כ $a^{2^{s} \cdot r}$ ונתחיל לחשב את השורשים. בהמשך נראה בידיוק איך זה יעבוד

עד חזק לראשוניות
יהי $n > 1$ טבעי (ואי זוגי, אחרת הוא בוודאות לא ראשוני) ויהי $a \in [n]$ . נסמן $n - 1 = 2^{s} \cdot r$ ו
$a$ ייקרא עד חזק לראשוניות של $n$ אם אחד מהתנאים הבאים מתקיים

$a^{r} \equiv_{n} 1$
$a^{2^{j} r} \equiv_{n} - 1$ כאשר $j \in {0, \dots, s - 1}$

כעת נשים לב שאם $p$ ראשוני מפרמה הקטן כל $a$ יהיה עד חזק. אם $p$ אינו ראשוני אז לכל היותר $\frac{1}{4}$ מבין ערכי $a$ יהיו עדים חזקים.

כעת נבין את הרעיון לפי דוגמה $p = 41$ . לפי פרמה $a^{40} \equiv_{41} 1$ וכעת מתקיים $a^{20} \equiv \pm 1$ אם הוא $1$ נוכל להמשיך אחרת נעצור... ולכן זאת הסיבה שמספר $a$ יהיה עד חזק לראשוניות אם הוא יעמוד בתנאים הנ״ל. במקרה של הדוגמה הנ״ל אם נמשיך נקבל $r = 5$ אם הוא היה $1$ אז סיימנו והוא עד חזק, אחרת ממשיכים לעלות בחזקת $2$ עד שמקבלים $- 1$ בחזקה כלשהי או שיקרה אחד מהשניים:

אם המספר שהגענו אליו שקול מודולו $n$ ל $1$ אז שום העלאה בריבוע שנעשה לא תוביל אותנו לשקילות מודולו של $- 1$ ונוכל לצאת מהלולאה.
אם הגענו לחזקה אחת לפני $p - 1$ וקיבלנו $1$ גם נוכל לצאת ולהחזיר פריק.

האלגוריתם:
Pasted image 20230228202832.png

חישוב ההופכי

חישוב ההופכי אפשר לעשות בקלות לפי אלגוריתם אוקלידס המורחב . נניח שיש לנו $x \in U_{n}$ עבורו נרצה לחשב את $x^{- 1}$ בחבורת אוילר $U_{n}$ . אם כן אנחנו יודעים שמתקיים

x \cdot x^{- 1} \equiv_{n} 1

כלומר $n$ מחלק את הביטוי

\begin{matrix} n | (x x^{- 1} - 1) \end{matrix}

המשמעות ש $n$ מחלק את הביטוי היא שקיים $k$ כלשהו כך ש

n k = x x^{- 1} - 1 \to x x^{- 1} - n k = 1

נשים לב ש $g c d (x, n) = 1$ כי $x \in U_{n}$ כלומר הוא זר ל $n$ ולכן הביטוי הנ״ל הוא צירוף ליניארי מינימלי עבור הgcd כלומר נוכל להשתמש באלגוריתם אוקלידס המורחב לחשב את $(n, k)$ ולהציב כדי להגיע למקדמים האלו. באלגוריתם שלנו מדובר ב $d$ שנמצא ב $U_{m}$ אבל הצעדים זהים.

דיפי-הלמן

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

א) נבחר $p$ ראשוני גדול מאוד.
ב) בוחרים $g \in U_{p}$ מפורסם.
ג) אילן בוחר $a$ בר בוחרת $b$ .
ד) אילן שולח לבר את $g^{a} \mod p$ .
ה) בר שולחת לאילו את $g^{b} \mod p$ .
ו) כל אחד מהם מעלה בחזקת המספר שבחר והם מקבלים $g^{a b} \equiv_{p} g^{b a}$ . הסוד המשותף הוא $g^{a b} \mod p$ .

הרעיון הוא שלחלץ את $a$ או את $b$ היא בעצם קשורה לפתרון של בעיית הלוג הדיסקרטי שזאת בעייה מאוד קשה. ב RSA הקושי בפתרון הוא למעשה בעובדה ש $d$ הוא סודי והעלאה בחזקה מאוד גבוהה דיסקרטית היא גם בעיה מאוד קשה חישובית.

הבחנה

אלגוריתם זה הוא הבסיס להצפנה סימטרית