ויקיפדיה

צופן סימטרי – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
בן-שלמה (שיחה | תרומות)
436 עריכות
מ הגהה
Matanyabot (שיחה | תרומות)
475,756 עריכות
מ בוט החלפות: לעיתים, \1ליניארי
שורה 30:
 
==היסטוריה==
צופן סימטרי קיים ב[[קריפטוגרפיה]] מראשית ימיה. [[הצפנה קלאסית|הצפנים הקלאסיים]] מוגדרים כצפנים סימטריים. לדוגמה: [[צופן החלפה]], [[צופן קיסר]], [[צופן ויז'נר]], [[צופן היל]] ו[[פנקס חד-פעמי]], הם צפנים סימטריים כאשר <math>d = e</math>, כלומר ההצפנה והפענוח נעשים באמצעות אותו מפתח לעתיםלעיתים באותה טרנספורמציה או בטרנספורמציה הופכית. אלגוריתם [[DES]] הוא דוגמה לצופן הסימטרי המודרני הראשון שפותח. הפונקציה ליצירת מפתח הפענוח מכינה את בתי המפתח בסדר הפוך. ההצפנה נקראת סימטרית, מאחר שכל שנדרש הוא ידיעת המפתח הסודי. כאשר המפתח הסודי ידוע, תהליך הפקת מפתח הפענוח הוא פונקציה פשוטה.
 
דוגמאות לצופנים סימטריים מודרניים נוספים: [[Twofish]], [[MARS]], [[סרפנט (צופן)|סרפנט]], [[AES]], [[Blowfish]], [[CAST5]], [[RC4]], [[RC6]], [[DES]] וכן [[IDEA]].
שורה 60:
 
===קידוד===
למען הנוחות, מפתח ההצפנה, הטקסט הגלוי והטקסט המוצפן מומרים באמצעות שיטת [[קידוד תווים|קידוד]] מוסכמת ליחידות מידע בסיסיות. בדרך כלל נוח להתייחס אל המידע כאל מספרים, אחרי הכול ההצפנה מבוצעת על מחשב (בדרך כלל). בניגוד להצפנה שיטת קידוד היא דרך להמרת מידע כלשהו מפורמט אחד לאחר באופן גלוי ומוסכם ובאופן שיהיה קל לביצוע על ידי כל אחד. כל הצפנה חייבת להשתמש בשיטת קידוד כלשהי כאשר השיטה הבסיסית ביותר היא השיטה הבינארית. שיטת ההצפנה יכולה להצפין את המידע סיבית אחר סיבית או אם נבחרה שיטת קידוד אחרת (כמו בתים או מילים) יחידת מידע אחת אחרי השנייה, בדרך זו השולח מצפין ומעביר באמצעות ערוץ התקשורת יחידות מידע מוצפנות בזו אחר זו ללא תלות אחת בשנייה ומבלי לדעת מה אורך המידע המיועד להצפנה. לעתיםלעיתים כאשר קיימת כמות גדולה של מידע ואורכו ידוע מראש כמו [[קובץ]] במחשב, נוח לחלקו לבלוקים באורך קבוע בהם מטפלים בזה אחר זה. היתרון בשיטה זו שאפשר להתייחס לבלוק בודד <math>m</math> כאל מספר שלם בטווח <math>0\le m\le 2^{B-1}</math>. בדרך זו סיביות הבלוק הן ספרות בבסיס בינארי של מספר שלם כלשהו לפי הכלל:
<center>
:<math>(m_0,m_1,m_2,...,m_{B-1}) \longrightarrow (m_{B-1}\cdot 2^{B-1}+\cdots + m_2\cdot 2^2+m_1\cdot 2 + m_0)</math>.
שורה 143:
 
דוגמאות לפעולות שניתן לשלבן כדי להגיע לצופן סימטרי חזק:
* '''תיבות תמורה''' Permutation Box (בקיצור P-box); הן אוסף פונקציות טרנספוזיציה או [[צופן שחלוף|שיכול]], שרק משנות את מיקומן של סיביות הקלט באמצעות פונקציות תמורה קבועה או משתנה. הפונקציות ניתנות לייצוג כטבלת [[תמורה (מתמטיקה)|תמורה]]. הפונקציות טובות להשגת אפקט פיזור (diffusion) ולכן מתאימות רק בשילוב עם תיבות החלפה או פעולות אי-לינאריותליניאריות אחרות.
* '''תיבות החלפה''' Substitution Box (בקיצור S-box); הן אוסף פונקציות החלפה לא לינאריותליניאריות המיוצגות על ידי טבלאות סטטיות או תלויות מפתח. הוצגו לראשונה בצופן לוציפר של הורסט פייסטל ולמעשה הן הפונקציות האי-לינאריותליניאריות היחידות בצופן DES, בלעדיהן הצופן היה קל לשבירה. אם ערכיהן נבחרו בקפידה הן טובות במיוחד לסיכול [[קריפטאנליזה דיפרנציאלית|התקפה דיפרנציאלית]].
*[[טרנספורמציה לינאריתליניארית]] עם פעולות [[אריתמטיקה|אריתמטיות]] בסיסיות על [[סיבית|סיביות]] כמו [[AND]], [[או מוציא|XOR]] ושילוב שלהן. פעולת XOR ידועה בכך שהיא משמרת אקראיות (חיבור XOR של הקלט עם ערך אקראי יפיק תוצאה אקראית, ראה [[פנקס חד פעמי]]), פעולה זו מכונה לעתיםלעיתים גם [[הלבנה (קריפטוגרפיה)|הלבנה]].
*[[פעולות על סיביות#סיבוב ללא סחיבה|הזזה מעגלית]] (cyclic shift או rotation); הזזת סיביות ימינה או שמאלה כך שהסיביות הנפלטות מצד אחד מוחזרות מהצד השני.
*פעולות [[אלגברה|אלגבריות]] ב[[פולינום|פולינומים]] מעל [[שדה סופי|שדות סופיים]] כגון <math>\text{GF}(2^{128})</math>. כאשר פעולות כפל מבוצעות מודולו [[פולינום פרימיטיבי]] בעל [[מרחק המינג|משקל בינארי]] נמוך. בצופן AES נעשה שימוש נרחב בפעולות מסוג זה.
*כפל [[מטריצה|מטריצות]], שהן מיפוי לינאריליניארי מעל [[וקטור (אלגברה)|וקטורים]]. הכפלה במטריצה בדרך כלל נעשית עם פולינום פרימיטיבי מתאים. למשל מטריצה המתאימה במיוחד להצפנה נקראת MDS קיצור של maximum distance separable בה נעשה שימוש בצופן [[Twofish]].
* [[חשבון מודולרי|אריתמטיקה מודולרית]]; פעולות חיבור וכפל ב[[חבורה (אלגברה)|חבורות]] מודולו <math>n</math>.
 
שורה 168:
===שיטות קריפטואנליטיות===
*'''[[כוח גס]] (Brute Force)''': ניסוי של לפחות מחצית מטווח המפתחות האפשריים במקרה הממוצע עד למציאת המפתח שאיתו נעשה שימוש. סיבוכיותה אינה מעשית ברוב המקרים, אולם עם מספיק זמן וכוח חישוב מובטחת בסופו של דבר תוצאה. למעשה ההוכחה שאלגוריתם מסוים ניתן לשבירה אך ורק באמצעות כח גס מהווה הוכחת איכות, כיוון שניתן לשלוט במידת בטיחותו על ידי בחירה מושכלת של גודל המפתח בסיביות. לשם המחשה, כוח גס כנגד צופן DES מצריך סריקה של לפחות <math>2^{55}</math> מפתחות במקרה הממוצע. עד 1998 שבירת צופן DES הייתה אפשרית רק על ידי חומרה ייעודית שעלותה יקרה ונמשכה בדרך כלל מספר ימים. ב-2008 פרסמה חברת {{קישור כללי|כותרת=SciEngines|כתובת=http://sciengines.com/}} שרת ייעודי יחיד עם חומרה מותאמת, בעל תפוקה של 26 מיליארד מפתחות בשנייה, המסוגל לפרוץ את DES בפחות מיום אחד. ניתן ליישם כח גס גם באמצעות חישוב מבוזר, גיוס זמן בטלה של מעבדים על בסיס התנדבותי, הזמין כיום באמצעות רשת האינטרנט. ב-1999 נפרץ DES ב-23 שעות בלבד באמצעות 100,000 מחשבים ביתיים.
*'''קריפטאנליזה לינאריתליניארית''': שיטת שבירת צופן המיוחסת לקריפטוגרף היפני [[מיצורו מצואי]]. בשיטה זו ניתן לפצח את DES עם <math>2^{43}</math> טקסטים מוצפנים שמקורם ידוע. קריפטאנליזה לינאריתליניארית היא התקפת גלוי ידוע, המתמקדת בחיפוש אחר קירובים לינארייםליניאריים היעילים ביותר המתאימים למספר ספציפי של סבבים בצופן המותקף, עם שיעור הצלחה גבוה מחצי, תוך ניצול חולשות בתיבות ההחלפה (S-box) של האלגוריתם. כל ביטוי כזה מאפשר לחלץ סיבית מפתח אחת באמצעות תהליך הסתברותי של חיפוש התאמות בכמות גדולה של טקסט מוצפן ומקור ידועים ובסופו של תהליך ניחוש המפתח כולו. אף על פי שזהו שיפור משמעותי לעומת כח גס, השיטה אינה יעילה עבור מחשב ממוצע בהתחשב בכמות הטקסט הדרושה.
*'''קריפטאנליזה דיפרנציאלית''': הומצאה על ידי אלי ביהם ועדי שמיר (מכון ויצמן למדע 1980). שיטה רבת עוצמה לניתוח אלגוריתמים סימטריים מכל סוג כמעט, בה נבחנת מידת ההשפעה של הבדלים בקלט על פלט הצופן. בשיטה זו ניתן לפצח את DES ב-<math>2^{47}</math> ניסיונות, אף בלא ידיעת מקור הצופן. בשיטה זו נפרצו ב-1989 וב-1991 כל וריאציות צופן [[FEAL]]. הוכח גם שגרסאות מתקדמות יותר של האלגוריתם FEAL-N וכן FEAL-NX שפותחו עקב כך ניתנות לשבירה (עד 31 סבבים) בפחות מהזמן הדרוש לכוח גס. ובכך הקיץ הקץ על האלגוריתם.
 
אוחזר מתוך "https://he.wikipedia.org/wiki/צופן_סימטרי"