קריפטואנליזה דיפרנציאלית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

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

אטימולוגיה[עריכת קוד מקור | עריכה]

המילה "קריפטואנליזה" היא הלחם של המילים קריפטוגרפיה ואנליזה, שפירושה "ניתוח". המילה "דיפרנציאלית" משמעותה "שינויים".

היסטוריה[עריכת קוד מקור | עריכה]

הראשונים לפרסם את הקריפטואנליזה דיפרנציאלית היו עדי שמיר ואלי ביהם בסוף שנות ה-80[1]. שמיר וביהם פרסמו מספר התקפות קריפטוגרפיות שהשתמשו בשיטה זו ובהן חולשה בפרוטוקול DES ששימש באותה תקופה כתקן ההצפנה של ממשלת ארצות הברית. בשנת 1994, פרסם דון קופרסמית', ממפתחי DES, מאמר בו טען שקריפטואנליזה דיפרנציאלית הייתה ידועה למפתחי DES ב-IBM כבר משנת 1974‏[2]. ככל הנראה, לאחר שמדעני IBM פיתחו את הקריפטואנליזה דיפרנציאלית הם עידכנו את אנשי ה-NSA ובעצה אחת החליטו שני הגופים לשמור את דבר קיום השיטה בסוד כדי לשמור על היתרון הטכנולוגי של ארצות-הברית בתחום הקריפטאנליזה.

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

השיטה[עריכת קוד מקור | עריכה]

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

התוקף מנסה למצוא קשר סטטיסטי בין כאשר:

( מייצג את או המוציא ו-(S(X מייצג את המרכיב הלא-ליניארי של הצופן). קשרים סטטיסטיים בין ΔX ל-ΔY מאפשרים להבדיל בין טקסט מוצפן לטקסט אקראי ובכך להפחית את מספר הניסיונות הדרושים כדי לאתר את המפתח באמצעות כוח-גס.

עמידות של צפנים[עריכת קוד מקור | עריכה]

כאמור, קריפטואנליזה דיפרנציאלית הייתה ידועה למדעני IBM בעת פיתוח צופן ה-DES ועמידות בפני השיטה הייתה אחת ממטרות התכנון של האלגוריתם. משום כך, צופן זה עמיד באופן יחסי בפני התקפת זו. למרות זאת, באמצעות שימוש בקריפטואנליזה דיפרנציאלית ניתן להפחית את טווח המפתחות לחיפוש מ- ל-. הרחבה של הצופן DES-X מגדילה את מספר הפעולות הדרוש ל-. AES וצפנים מודרניים שפורסמו לאחר פרסום השיטה נדרשו להוכיח עמידות בפני השיטה.

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

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Biham, E. and A. Shamir, "Differential Cryptanalysis of DES-like Cryptosystems", Advances in Cryptology – CRYPTO '90, Springer-Verlag, 1990.
  2. ^ Coppersmith, Don (מאי 1994). "The Data Encryption Standard (DES) and its strength against attacks" (PDF). IBM Journal of Research and Development 38 (3): 243.  (subscription required)