לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
מבנים אלגבריים למדעי המחשב - ארז שיינר
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
==הרצאה 7 המשך הצפנה - בדיקת ראשוניות, דיפי הלמן, חתימה, חישוב חזקות;== ===שיטת מילר-רבין לבדיקת ראשוניות=== *חלק מהותי בשיטות שאנו לומדים הוא מציאת ראשוניים גדולים. כיצד הדבר נעשה? האם יש רשימה גדולה של כל הראשוניים בעולם? *ידוע שכמות הראשוניים עד המספר <math>n</math> היא בערך <math>\frac{n}{\ln(n)}</math>. *לכן הסיכוי בבחירת מספר אקראי עד <math>n</math> שהוא יהיה ראשוני הוא בערך <math>\frac{1}{\ln(n)}</math>. *אנו זקוקים למבחן ראשוניות - נגריל מספרים אקראיים ונבדוק האם הם ראשוניים, ומהר מאד נמצא אחד כזה בהתחשב בסיכוי הנ"ל. *זכרו שפירוק לגורמים ראשוניים היא בעייה קשה (אחרת RSA מיותר ממילא). *לפי משפט פרמה הקטן, אם <math>p</math> ראשוני, אזי לכל <math>a<p</math> מתקיים <math>a^{p-1}\equiv 1 \mod p</math>. *האם ההפך נכון? כלומר, האם <math>a^{p-1}\equiv 1 \mod p</math> רומז ש<math>p</math> ראשוני? *[https://he.wikipedia.org/wiki/%D7%9E%D7%A1%D7%A4%D7%A8_%D7%A7%D7%A8%D7%9E%D7%99%D7%99%D7%A7%D7%9C מספרי קרמייקל] מקיימים את התכונה הזו כמעט לכל <math>a</math> למרות שאינם ראשוניים. *טענה: אם <math>p</math> ראשוני, ו<math>x\in U_p</math> איבר כך ש <math>x^2=1</math> אזי <math>x=\pm 1</math> *הוכחה: **נזכור ש<math>\mathbb{Z}_p</math> הוא '''שדה''' כיוון שמדובר במספר ראשוני, ולכן אין ב<math>U_p=\mathbb{Z}/\{0\}</math> מחלקי אפס. **<math>x^2=1</math> אם"ם <math>(x-1)(x+1)=0</math> אם"ם <math>x=\pm 1</math> *הגדרה: **בהנתן מספר n, ונסמן <math>n-1=2^s\cdot r</math> עבור r אי זוגי. אומרים שהמספר <math>1\leq a <n</math> הוא '''עד חזק''' לראשוניות של n אם אחד מהתנאים הבאים מתקיים: ***<math>a^r\equiv 1 \mod n</math> ***<math>a^{2^kr}\equiv n-1 \mod n</math> עבור <math>1\leq k \leq s-1</math>. *שימו לב: <math>n-1\equiv -1 \mod n</math> *אם <math>p</math> ראשוני אזי כל המספרים <math>1<a<p</math> הם עדים חזקים לכך. **הוכחה: ***לפי אוילר <math>a^{p-1}\equiv 1 \mod p</math> . ***אם נעלה את <math>a^r</math> בריבוע s פעמים נקבל <math>a^{2^s\cdot r}=a^{p-1}\equiv 1 \mod p</math>. ***לכן אם <math>a^r\not \equiv 1 \mod p</math>, בשלב כלשהו נעלה מספר שאינו 1 בריבוע ונקבל 1, לכן מספר זה חייב להיות <math>-1</math>. *אם <math>p</math> אינו ראשוני, ידוע שלכל היותר רבע מבין המספרים <math>a</math> יכולים להיות עדים חזקים. *לכן הסיכוי שמצאנו עד חזק למרות שהמספר שאנו בודקים אינו ראשוני הוא רבע. *אם נבחן k מספרים אקראיים שונים, הסיכוי שכולם יהיו עדים חזקים אך המספר אינו ראשוני הוא <math>\frac{1}{4^k}</math> (נמוך מאד). ===דיפי-הלמן=== מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה: [http://ee.stanford.edu/%7Ehellman/publications/24.pdf Diffie, Whitfield, and Martin E. Hellman. "New directions in cryptography."] *למדנו שבעזרת RSA ניתן להעביר פיסת מידע באופן בטוח בערוץ פומבי, ולרוב נרצה להעביר מפתח סודי לצורך הצפנה סימטרית. *אלגוריתם דיפי-הלמן הוא שיטה לתיאום מפתח סודי בלבד ולא להעברת מידע. *אליס ובוב מתאמים מספר ראשוני גדול <math>p</math> שאינו סודי כמובן. *כמו כן הם מתאמים יוצר <math>g</math> של <math>U_p</math> (כלומר <math>U_p=<g></math>), או לפחות איבר מסדר מאד גדול (בהמשך יש הסבר כיצד אפשר לעשות זאת). *כעת אליס בוחרת מספר אקראי סודי <math>a\leq p-1</math> ושולחת לבוב את <math>g^a \mod p</math>. *בוב בוחר מספר אקראי סודי <math>b\leq p-1</math> ושולח לאליס את <math>g^b \mod p</math>. *כעת אליס ובוב שניהם יכולים לחשב בקלות את הסוד המשותף <math>g^{ab}</math>. *על מנת לשבור את ההצפנה צריך לחשב את <math>a</math> בהנתן <math>g^a \mod p</math>, זו בעיית הלוגריתם הדיסקרטי שנחשבת לקשה. *אם <math>g</math> מסדר נמוך חישוב כל החזקות האפשריות שלו הוא קל. *גישה פרקטית למשל: **נבחר את p להיות מספר ראשוני "בטוח", כלומר <math>p=2q+1</math> כאשר <math>q</math> ראשוני. **כעת ב<math>|U_p|=2q</math> ולכן הסדר של כל איבר ב<math>U_p</math> הוא אחד מבין <math>1,2,q,2q</math>. **נגריל איבר <math>g\neq \pm 1</math> (לכן <math>g^2\not\equiv 1 \mod p</math>) וגם <math>g^q\not\equiv 1 \mod p</math>. **האיבר שבחרנו הוא יוצר. ===חתימה=== *פונקציות גיבוב (hash) - מעבירות קלט בגודל אקראי לקלט באורך קבוע. *התנגשות היא מצב בו שני קלטים מובילים לאותו ערך מגובב. לפי שובך היונים התנגשויות קיימות, אך בפונקציות גיבוב "טובות" הסיכוי לכך נמוך מאד. *סיפרנו על אליס שייצרה מפתח פומבי <math>(n,e)</math>, ושמרה לעצמה את הערכים הסודיים <math>m,d</math> *כעת אליס רוצה להבטיח את זהותה ואת אמינות המידע, היא מעבירה את המידע שלה דרך פונקצית גיבוב ומקבלת את הערך המגובב <math>a</math>. *אליס מחשבת את <math>y=a^{d} \mod n</math> ושולחת אותו בנוסף למידע. *אפילו בהנתן <math>a</math> לא ניתן לחשב את <math>d</math> (זו בעיית הלוגריתם הדיסקרטי). *אף אחד אחר לא יכול לחשב את y כיוון ש <math>d</math> סודי. *כעת בוב שרוצה לוודא את אמינות המידע מחשב את <math>a=y^{e} \mod n</math> ומוודא כי המידע שהוא קיבל הוא המידע שאליס התכוונה לשלוח עד כדי המקרה הבלתי סביר של התנגשות. *אף אחד אחר לא יכל ליצור את הוכחת אמינות המידע הזו פרט לאליס. *שימו לב שעל מנת למנוע תקיפת 'אדם באמצע' באמצעות חתימה המפתחות הפומביים צריכים להיות מאומתים על פני ערוץ מאובטח (מקודדים בתוך הדפדפן למשל). ===חישוב חזקה=== *[http://abstract.ups.edu/aata/section-method-of-repeated-squares.html שיטת הריבועים החוזרים] לחישוב חזקה. *לדוגמא, אנו מעוניינים לחשב את <math>x^{41} \mod n</math> במעט פעולות **<math>41=2^5+2^3+1</math> **<math>x^{41}=x^{2^5}\cdot x^{2^3}\cdot x</math> **<math>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</math> **סה"כ חישבנו את החזקה עם 8 העלאות בריבוע, ושלוש הכפלות, במקום 40 הכפלות.
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)