לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
מבנים אלגבריים למדעי המחשב - ארז שיינר
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
==הרצאה 6 הצפנה סימטרית (מפתח פרטי), הצפנה אסימטרית (מפתח ציבורי), RSA; פרק 7 מ[http://abstract.ups.edu/aata/ הספר]== *הצפנה; העברת מידע בערוץ פומבי כך שרק המשתתפים בהצפנה יוכלו להבין אותו, הוכחה לזהות כותב המידע (בין היתר כותב המידע לא יוכל להתנער ממנו), הוכחה לאמינות ושלימות המידע (המידע אינו חלקי ואף אחד לא שינה אותו). *[https://he.wikipedia.org/wiki/%D7%A6%D7%95%D7%A4%D7%9F_%D7%A1%D7%99%D7%9E%D7%98%D7%A8%D7%99 הצפנה סימטרית] - הצפנה בה לשני הצדדים יש סוד משותף שהעבירו מראש בערוץ שאינו פומבי (משאית ברינקס, לנסוע לחנות לאסוף כרטיס sim). *[https://he.wikipedia.org/wiki/%D7%9E%D7%A4%D7%AA%D7%97_%D7%A6%D7%99%D7%91%D7%95%D7%A8%D7%99 הצפנה פומבית] - הצפנה ללא סוד מתואם מראש, באמצעות מפתחות פומביים (שכולם רואים). *[https://en.wikipedia.org/wiki/Transport_Layer_Security פרקטית] הצדדים מעבירים מפתח סודי באמצעות הצפנה פומבית, ואז עוברים להצפנה סימטרית. *ההצפנה "המושלמת" - רצף בינארי אקראי באורך המידע המוסכם על שני הצדדים. ללא תלות במידע ובחוקיותו, חיבור בכל ביט (xor) של המידע עם הרצף ייצר תוכן שבו לכל ביט יש סיכוי שווה להיות 0 או 1. *אם הרצף קצר מהמידע וחוזר על עצמו, חיבור שתי חתיכות שנשלחו יאפס את הרצף הסודי וישאיר לנו שתי חתיכות מידע גלוי המחוברות (זה כמעט מידע חשוף). *קוד חילוף אותיות - נשבר ע"י חקר סטטיסטיקת שכיחות האותיות. אם המידע עובר תהליך שגורם לו להראות אקראי - עדיף *מטא דטא - מידע על המידע שעשוי לעניין אותנו: **אם רצף נשלח פעמיים, גם אם אין אנו יודעים מהו, ייתכן שנסיק מההקשר. **הזמן שבו נשלח מסר (אמצע הלילה למשל). **הזמן שלקח למכונה להצפין את המידע. **עצם העובדה ששני צדדים מסוימים מדברים (רוסיה ונציגי קמפיין לנשיאות ארה"ב). **אורך המידע (בהנחה שהוא אינו מרופד באפסים). ===RSA=== מומלץ לקרוא ישירות את המאמר פורץ הדרך בו הוצגה השיטה: [https://people.cs.umass.edu/~emery/classes/cmpsci691st/readings/Sec/Rsapaper.pdf Rivest, Ronald L., Adi Shamir, and Leonard Adleman. "A method for obtaining digital signatures and public-key cryptosystems."] *אליס בוחרת שני ראשוניים גדולים <math>\{p,q\}</math> זה הסוד שלה. *אליס מחשבת את המכפלה <math>n=p\cdot q</math> *אליס מחשבת את פונקצית אוילר <math>m=\phi(n)=(p-1)(q-1)</math> *(הסבר - המספרים שאינם זרים לn מחלקים את אחד הראשוניים. <math>p,2p,3p,...,q\cdot p</math> וגם <math>q,2q,3q,...,p\cdot q</math>. סה"כ <math>p+q-1</math> כי <math>n=p\cdot q</math> נספר פעמיים.) *אליס בוחרת מספר כלשהו e כך שהוא זר לm. *אליס מחשבת את ההופכי של e מודולו m, נקרא לו d. היא יודעת לעשות את זה כיוון שהיא הקשיבה בהרצאה קודמת על gcd ומציאת הופכי. *אליס מפרסמת לכל העולם ואחותו את זוג המספרים <math>n,e</math> *כעת בוב מעוניין לשלוח לאליס מידע שרק היא תוכל לפענח. *בוב בעצם הולך "לנעול" את המידע באמצעות המנעול <math>e,n</math> של אליס. כל אחד יכול לנעול אותו, ורק אליס יודעת לפתוח אותו. *המידע שבוב מעוניין לשלוח הוא מספר <math>x<n</math>, בוב שולח את המידע המוצפן <math>x^e\mod n</math> *אם בוב רוצה לשלוח יותר מידע, הוא יצטרך לפרק אותו לחתיכות. שימו לב שאם המנעול של אליס ישאר קבוע לחלוטין זה יהווה חולשה. *אליס מקבלת את המידע המוצפן ומפענחת אותו באופן הבא: <math>x=\left(x^e\right)^d \mod n</math> *הוכחה - נחלק לשני מקרים. *אם <math>gcd(x,n)=1</math>: **נתון כי <math>de=km+1=k\phi(n)+1</math>. **<math>\left(x^e\right)^d=x^{de}=x^{k\phi(n)+1}=\left(x^{\phi(n)}\right)^k\cdot x\equiv x \mod n</math> **זה נכון כיוון שלפי משפט אוילר <math>x^{\phi(n)}\equiv 1 \mod n</math> *אם <math>gcd(x,n)\neq 1</math>: **כיוון ש<math>n=p\cdot q</math> אז x הוא כפולה של p או q. נוכיח במקרה שx מתחלק בp. **קיים <math>h<q</math> עבורו <math>x=hp</math> וכמו כן x זר לq (אחרת בשני המקרים יוצא ש <math>x\geq n</math>). **לכן לפי פרמה הקטן יוצא ש <math>x^{q-1}\equiv 1 \mod q</math> **לכן <math>x^{km}=x^{k(p-1)(q-1)}=\left(x^{q-1}\right)^{k(p-1)}\equiv 1 \mod q</math> **לכן <math>x^{de}=x^{km+1}=x^{km}x=(1+tq)x=x+tqhp=x+th\cdot n\equiv x \mod n</math> *שימו לב: אמנם <math>4\equiv 1 \mod 3</math> אך <math>2^4 \not\equiv 2 \mod 3</math> כלומר לחשב את ההופכי של e מוד n זה אמנם קל, אך לא יעיל לשום דבר...
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)