מבנים אלגבריים למדעי המחשב - ארז שיינר

ספר הקורס

ההרצאות מבוססות באופן כללי על הספר Abstarct Algebra - Theory and Applications by Thomas W. Judson

נושאי ההרצאות

הרצאה 1 הקדמה; הסבר על קידוד והצפנה, מבוא למבנים אלגבריים

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

הרצאה 2 חבורות ותת חבורות; פרקים 3,4 מהספר

• תזכורת לגבי חבורות, תכונת הצמצום.
• $\mathbb{Z},\mathbb{Z}_n,{GL}_n,{SL}_n,S_n$.
• תת חבורות; קווטרניונים, מעגל היחידה ושורשי יחידה, המרוכבים ללא אפס כתת חבורה של מטריצות ממשיות בגודל 2 על 2.

• קרטריון מקוצר לבדיקת תת חבורה:
• תת קבוצה H של חבורה G הינה תת חבורה אם ורק אם מתקיימים שני התנאים הבאים:
  • $e_G\in H$.
  • לכל שני איברים $a,b\in H$ מתקיים כי $ab^{-1}\in H$.

• כתיב אקספוננט $g^n=g\cdots g$ או כפל $ng=g+\cdots+g$ בהתאם לסימון פעולת החבורה.
• סדר של איבר, תת חבורה ציקלית, סדר האיבר הוא גודל החבורה הציקלית.

הרצאה 3 חבורת תמורות, סימן התמורה; פרק 5 מהספר

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

הרצאה 4 הומומורפיזמים, איזומורפיזמים, משפט קיילי, משפט לגראנג'; פרקים 9 ו6 מהספר

• הומומורפיזמים, איזומורפיזמים.
• תמונה של הומומורפיזם היא תת חבורה.
• משפט קיילי- כל חבורה איזומורפית לתת חבורה של חבורת תמורות.

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

• לפני הרצאה זו, חזרו בבקשה על הנושא של יחסי שקילות. ניתן לצפות בסרטון הבא:

הרצאה 5 חבורת אוילר, משפטי אוילר ופרמה; פרק 6 מהספר

• זוג מספרים שלמים $a,b$ נקראים שקולים מודולו n אם קיים שלם $q$ כך ש $a=b+q\cdot n$
• חלוקה עם שארית: לכל מספר טבעי a ולכל מספר שלם b קיים זוג שלמים יחיד $q,r$ כך ש $b=q\cdot a+r$ וגם $0\leq r < a$.
• המספר q נקרא מנת החלוקה והמספר r נקרא שארית החלוקה.
• יהיו שני טבעיים $a,b$ ויהיו $r_a,r_b$ השאריות שלהם בחלוקה בn. אזי $ab\equiv r_ar_b \mod n$

• לכל שני מספרים טבעיים $k<n$ מתקיים כי $gcd(n,k)=gcd(n-k,k)$
• לכל שני מספריים טבעיים $n,k$ קיימים מספרים שלמים $a,b$ כך ש $an+bk=gcd(n,k)$
• (הוכחה באינדוקציה על הגודל של n+k. אם n=k סיימנו, אחרת אם $k<n$ אזי $gcd(n,k)=gcd(n-k,k)=a(n-k)+bk=an+(b-a)k$)

• שני מספרים טבעיים n,k נקראים זרים אם $gcd(n,k)=1$
• ב$\mathbb{Z}_n$ עם פעולת הכפל מודולו n האיברים ההפיכים הם בדיוק המספרים הזרים ל n.
• עבור מספר טבעי $1<n$ קבוצת המספרים הטבעיים הזרים לn וקטנים ממנו מהווה חבורה ביחס לכפל מודולו n, היא נקראית חבורת אוילר ומסומנת $U_n$.
• $\mathbb{Z}_n$ עם פעולות חיבור וכפל מודולו n הוא שדה אם ורק אם n הינו מספר ראשוני.

• פונקצית אוילר $\phi(n)$ היא מספר המספרים הטבעיים שקטנים או שווים לn וזרים לו.
• משפט אוילר - יהיו שני מספרים טבעיים זרים $a<n$. אזי $a^{\phi(n)}\equiv 1$ מודולו n.
• המשפט הקטן של פרמה - יהי p ראשוני ומספר טבעי $a<p$ אזי $a^{p-1}\equiv 1$ מודולו p.
• בפרט, בתנאי המשפט, $a^p\equiv a$ מודולו p.
• למעשה התוצאה תקיפה לכל מספר טבעי $a$, כיוון ש $a^{\phi(n)}\equiv r^{\phi(n)} \mod n$, וגם השארית $r$ זרה ל $n$.

הרצאה 6 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), RSA; פרק 7 מהספר

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

• ההצפנה "המושלמת" - רצף בינארי אקראי באורך המידע המוסכם על שני הצדדים. ללא תלות במידע ובחוקיותו, חיבור בכל ביט (xor) של המידע עם הרצף ייצר תוכן שבו לכל ביט יש סיכוי שווה להיות 0 או 1.
• אם הרצף קצר מהמידע וחוזר על עצמו, חיבור שתי חתיכות שנשלחו יאפס את הרצף הסודי וישאיר לנו שתי חתיכות מידע גלוי המחוברות (זה כמעט מידע חשוף).

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

RSA

• אליס בוחרת שני ראשוניים גדולים $\{p,q\}$ זה הסוד שלה.
• אליס מחשבת את המכפלה $n=p\cdot q$
• אליס מחשבת את פונקצית אוילר $m=\phi(n)=(p-1)(q-1)$
• (הסבר - המספרים שאינם זרים לn מחלקים את אחד הראשוניים. $p,2p,3p,...,q\cdot p$ וגם $q,2q,3q,...,p\cdot q$. סה"כ $p+q-1$ כי $n=p\cdot q$ נספר פעמיים.)
• אליס בוחרת מספר כלשהו e כך שהוא זר לm.
• אליס מחשבת את ההופכי של e מודולו m, נקרא לו d. היא יודעת לעשות את זה כיוון שהיא הקשיבה בהרצאה קודמת על gcd ומציאת הופכי.
• אליס מפרסמת לכל העולם ואחותו את זוג המספרים $n,e$

• כעת בוב מעוניין לשלוח לאליס מידע שרק היא תוכל לפענח.
• בוב בעצם הולך "לנעול" את המידע באמצעות המנעול $e,n$ של אליס. כל אחד יכול לנעול אותו, ורק אליס יודעת לפתוח אותו.
• המידע שבוב מעוניין לשלוח הוא מספר $x<n$, בוב שולח את המידע המוצפן $x^e\mod n$
• אם בוב רוצה לשלוח יותר מידע, הוא יצטרך לפרק אותו לחתיכות. שימו לב שאם המנעול של אליס ישאר קבוע לחלוטין זה יהווה חולשה.

• אליס מקבלת את המידע המוצפן ומפענחת אותו באופן הבא: $x=\left(x^e\right)^d \mod n$
• הוכחה - נחלק לשני מקרים.
• אם $gcd(x,n)=1$:
  • נתון כי $de=km+1=k\phi(n)+1$.
  • $\left(x^e\right)^d=x^{de}=x^{k\phi(n)+1}=\left(x^{\phi(n)}\right)^k\cdot x\equiv x \mod n$
  • זה נכון כיוון שלפי משפט אוילר $x^{\phi(n)}\equiv 1 \mod n$
• אם $gcd(x,n)\neq 1$:
  • כיוון ש$n=p\cdot q$ אז x הוא כפולה של p או q. נוכיח במקרה שx מתחלק בp.
  • קיים $h<q$ עבורו $x=hp$ וכמו כן x זר לq (אחרת בשני המקרים יוצא ש $x\geq n$).
  • לכן לפי פרמה הקטן יוצא ש $x^{q-1}\equiv 1 \mod q$
  • לכן $x^{km}=x^{k(p-1)(q-1)}=\left(x^{q-1}\right)^{k(p-1)}\equiv 1 \mod q$
  • לכן $x^{de}=x^{km+1}=x^{km}x=(1+tq)x=x+tqhp=x+th\cdot n\equiv x \mod n$

• שימו לב: אמנם $4\equiv 3 \mod 1$ אך $2^4 \not\equiv 2 \mod 3$ כלומר לחשב את ההופכי של e מוד n זה אמנם קל, אך לא יעיל לשום דבר...

הרצאה 7 המשך הצפנה - בדיקת ראשוניות, דיפי הלמן, חתימה, חישוב חזקות;

שיטת מילר-רבין לבדיקת ראשוניות

• חלק מהותי בשיטות שאנו לומדים הוא מציאת ראשוניים גדולים. כיצד הדבר נעשה? האם יש רשימה גדולה של כל הראשוניים בעולם?
• ידוע שכמות הראשוניים עד המספר $n$ היא בערך $\frac{n}{\ln(n)}$.
• לכן הסיכוי בבחירת מספר אקראי עד $n$ שהוא יהיה ראשוני הוא בערך $\frac{1}{\ln(n)}$.
• אנו זקוקים למבחן ראשוניות - נגריל מספרים אקראיים ונבדוק האם הם ראשוניים, ומהר מאד נמצא אחד כזה בהתחשב בסיכוי הנ"ל.
• זכרו שפירוק לגורמים ראשוניים היא בעייה קשה (אחרת RSA מיותר ממילא).

• לפי משפט פרמה הקטן, אם $p$ ראשוני, אזי לכל $a<p$ מתקיים $a^{p-1}\equiv 1 \mod p$.
• האם ההפך נכון? כלומר, האם $a^{p-1}\equiv 1 \mod p$ רומז ש$p$ ראשוני?
• מספרי קרמייקל מקיימים את התכונה הזו כמעט לכל $a$ למרות שאינם ראשוניים.

• טענה: אם $p$ ראשוני, ו$x\in U_p$ איבר כך ש $x^2=1$ אזי $x=\pm 1$
• הוכחה:
  • נזכור ש$U_p$ הוא שדה כיוון שמדובר במספר ראשוני, ולכן אין בו מחלקי אפס.
  • $x^2=1$ אם"ם $(x-1)(x+1)=0$ אם"ם $x=\pm 1$

• בהנתן מספר $p$ נתאר מבחן הסתברותי הבודק האם הוא ראשוני
  • נבחר מספר $1<a<p$.
  • אם $a,p$ אינם זרים, אז $p$ אינו ראשוני בוודאות וסיימנו.
  • אחרת, לפי משפט פרמה הקטן $a^{p-1}\equiv 1 \mod p$.
  • המספר $p-1$ הוא זוגי (ביננו, אף אחד לא יבדוק האם $p=2$ ראשוני).
  • נחלק את $p-1$ ב2 שוב ושוב עד שנגיע למספר אי זוגי r ולכן $p-1=2^s\cdot r$
  • כעת נביט במספר $a^r \mod p$, ידוע שאם נעלה אותו בריבוע s פעמים נקבל 1 (אם p ראשוני כמובן).
  • כלומר אם נעלה אותו בריבוע שוב ושוב נקבל את סדרת המספרים $a^r,a^{2r},a^{4r},...,a^{2^s\cdot r}$ (מוד p כמובן).
  • אם אחד האיברים בסדרה אינו $\pm 1$ והבא אחריה הוא כן 1, סימן ש$p$ אינו ראשוני בוודאות וסיימנו.
  • אם אף אחד מהחזקות אינה 1 סימן ש$p$ אינו ראשוני בוודאות וסיימנו.
  • אחרת $a$ הינו עד חזק לראשוניות של $p$.

• אם $p$ ראשוני אזי כל המספרים $1<a<p$ הם עדים חזקים לכך.
• אם $p$ אינו ראשוני, ידוע שלכל היותר רבע מבין המספרים $a$ יכולים להיות עדים חזקים.
• לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע.
• אם נבחן k מספרים אקראיים שונים, הסיכוי שכולם יהיו עדים חזקים אך המספר אינו ראשוני הוא $\frac{1}{4^k}$ (נמוך מאד).

דיפי-הלמן

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

• אליס ובוב מתאמים מספר ראשוני גדול $p$ שאינו סודי כמובן.
• כמו כן הם מתאמים יוצר $g$ של $U_p$ (כלומר $U_p=<g>$), או לפחות איבר מסדר מאד גדול.
• כעת אליס בוחרת מספר אקראי סודי $a\leq p-1$ ושולחת לבוב את $g^a \mod p$.
• בוב בוחר מספר אקראי סודי $b\leq p-1$ ושולח לאליס את $g^b \mod p$.

• כעת אליס ובוב שניהם יכולים לחשב בקלות את הסוד המשותף $g^{ab}$.

• על מנת לשבור את ההצפנה צריך לחשב את $a$ בהנתן $g^a \mod p$, זו בעיית הלוגריתם הדיסקרטי שנחשבת לקשה.
• אם $g$ מסדר נמוך חישוב כל החזקות האפשריות שלו הוא קל.

• גישה פרקטית למשל:
  • נבחר את p להיות מספר ראשוני "בטוח", כלומר $p=2q+1$ כאשר $q$ ראשוני.
  • כעת ב$|U_p|=2q$ ולכן הסדר של כל איבר ב$U_p$ הוא אחד מבין $1,2,q,2q$.
  • נגריל איבר $g\neq 1$ כך ש$g^2\not\equiv 1 \mod p$ וגם $g^q\not\equiv 1 \mod p$.
  • האיבר שבחרנו הוא יוצר.

חתימה

• פונקציות גיבוב (hash) - מעבירות קלט בגודל אקראי לקלט באורך קבוע.
• התנגשות היא מצב בו שני קלטים מובילים לאותו ערך מגובב. לפי שובך היונים התנגשויות קיימות, אך בפונקציות גיבוב "טובות" הסיכוי לכך נמוך מאד.

• סיפרנו על אליס שייצרה מפתח פומבי $(n,e)$, ושמרה לעצמה את הערכים הסודיים $m,d$
• כעת בוב שרוצה לשלוח לה מידע ולהבטיח את זהותו ואת אמינות המידע, מייצר באופן דומה מפתח פומבי $(n',e')$ ושומר ערכים סודיים $m',d'$
• בוב מעביר את המידע שלו דרך פונקצית גיבוב ומקבל את הערך המגובב $a$
• בוב מחשב את $y=a^{d'} \mod n'$ ושולח לאליס בנוסף למידע.
• אפילו בהנתן $a$ לא ניתן לחשב את $d'$ (זו בעיית הלוגריתם הדיסקרטי).
• אף אחד אחר לא יכול לחשב את y כיוון ש $d'$ סודי.

• כעת אליס מחשבת את $a=y^{e'} \mod n'$ ומוודאת כי המידע שהיא קיבלה הוא המידע שבוב התכוון לשלוח עד כדי המקרה הבלתי סביר של התנגשות.
• אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לבוב.

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

חישוב חזקה

• שיטת הריבועים החוזרים לחישוב חזקה.
• לדוגמא, אנו מעוניינים לחשב את $x^{41} \mod n$ במעט פעולות
  • $41=2^5+2^3+1$
  • $x^{41}=x^{2^5}\cdot x^{2^3}\cdot x$
  • $x^{41}=\left(\left(\left(\left(x^2\right)^2\right)^2\right)^2\right)^2\cdot \left(\left(x^2\right)^2\right)^2 \cdot x$
  • סה"כ חישבנו את החזקה עם 8 העלאות בריבוע, ושלוש הכפלות, במקום 41 הכפלות.

הרצאות 8-9 משפט האיזומורפיזם; פרקים 10,11 מהספר

• תהי חבורה G ותהי תת חבורה N. תת החבורה N נקראת נורמלית אם לכל $a\in G$ מתקיים כי $aN=Na$.
• ברור שבחבורה אבלית כל חבורה היא תת חבורה נורמלית.
• דוגמא:
  • נביט בחבורה הסימטרית $G=S_3$ ובתת החבורה $N=<(1\ 2)>=\{(1),(1\ 2)\}$.
  • אזי $(1\ 3)N=\{(1\ 3), (3\ 1\ 2)\}$ אך $N(1\ 3)=\{(1\ 3),(2\ 1\ 3)\}$ וקל לראות כי $(1\ 3)N\neq N(1\ 3)$.
  • אזי N תת חבורה לא נורמלית!

• טענה תהי N תת חבורה נורמלית אזי $(aN)(bN)=abN$
• הוכחה - הכלה דו כיוונית:
  • יהי $anbk\in (aN)(bN)$ כיוון ש $bN=Nb$ אזי $anbk=abmk\in abN$.
  • יהי $abn\in abN$ כיוון ש $bN=Nb$ אזי $abn=amb=ambe\in (aN)(bN)$.

• תהיינה G חבורה וN תת חבורה נורמלית, אזי $G/N=\{aN|a\in G\}$ היא חבורה.

• יהי הומומורפיזם בין חבורות $\varphi:G\to H$. נגדיר את הגרעין $\ker(\varphi)=\{a\in G|\varphi(a)=e_H\}$.
• הגרעין הוא תת-חבורה נורמלית של $G$.
• הוכחה - נסמן $K=\ker(\varphi)$:
  • ראשית עלינו להוכיח שמדובר בתת-חבורה: אכן $e_G\in K$ ואם $a,b\in K$ אז $\varphi(ab^{-1})=\varphi(a)\left(\varphi(b)\right)^{-1}=e_H$.
  • כעת יהי $a\in G$ עלינו להוכיח כי $aK=Ka$. נעשה הכלה בכיוון אחד, הכיוון השני דומה.
  • יהי $ak\in aK$ רוצים למצוא $m\in K$ כך ש $ak=ma$.
  • לכן עלינו לבחור $m=aka^{-1}$, נותר להוכיח שאכן $m\in K$.
  • אכן $\varphi(m)=\varphi(aka^{-1})=\varphi(a)e_H\left(\varphi(a)\right)^{-1}=e_H$.

• משפט האיזומורפיזם הראשון. יהי $\varphi:G\to H$ איזומורפיזם בין חבורות. אזי $G/\ker(\varphi)\cong im(\varphi)$
• הוכחה:
  • לצורך הנוחות נסמן $K=\ker(\varphi)$ ו$M=im(\varphi)$.
  • עלינו להראות שקיים איזומורפיזם (כלומר הומומורפיזם חח"ע ועל) $f:G/K\to M$.
  • לכל $aK\in G/K$ נגדיר $f(aK)=\varphi(a)$.
  • ראשית, עלינו להוכיח כי מדובר בפונקציה מוגדרת היטב. כלומר, בהנתן $a,b\in G$, אם $aK=bK$ עלינו להוכיח כי $f(aK)=f(bK)$.
    • $a=ae\in aK$ ולכן $a\in bK$. כלומר קיים $k\in K$ כך ש $a=bk$.
    • $\varphi(a)=\varphi(bk)=\varphi(b)\varphi(k)=\varphi(b)$.
    • $f(aK)=\varphi(a)=\varphi(b)=f(bK)$.
  • כעת, עלינו להוכיח ש$f$ הינו הומומורפיזם.
    • $f\left((aK)(bK)\right)=f(abK)=\varphi(ab)=\varphi(a)\varphi(b)=f(aK)f(bK)$
  • עכשיו נוכיח ש$f$ על.
    • לכל איבר בתמונה $h\in M$ קיים מקור $g\in G$. לכן $f(gK)=\varphi(g)=h$.
  • ולבסוף, נוכיח ש$f$ חח"ע.
    • יהיו $aK,bK\in G/K$ כך ש $f(aK)=f(bK)$ עלינו להוכיח כי $aK=bK$.
    • נתון $\varphi(a)=\varphi(b)$ צ"ל $aK=bK$. שימו לב שלא צריך להוכיח כי $a=b$; אכן $\varphi$ לא חייב להיות חח"ע.
    • נראה הכלה בכיוון אחד, הכיוון השני דומה.
    • יהי $ak\in aK$ צ"ל $ak\in bK$.
    • קל לראות ש $ak=bb^{-1}ak$, עלינו להוכיח כי $b^{-1}ak\in K$.
    • אכן $\varphi(bb^{-1}k)=\left(\varphi(b)\right)^{-1}\varphi(a)\varphi(k)=\left(\varphi(a)\right)^{-1}\varphi(a)=e_H$

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

הרצאה 10 קידוד; פרק 8 מהספר

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

checksum בפרוטוקולי IP, TCP, UDP.

הרצאה 11 חוג הפולינומים; פרקים 16,17 מהספר

חלוקה עם שארית, אידיאלים.

הרצאה 12 קודים ציקליים; פרק 22 מהספר

השדה הבינארי, קודים פולינומיים.

CRC בשימוש פרוטוקול Ethernet.