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

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

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

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

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

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

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

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

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

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

התוקף מנסה למצוא קשר סטטיסטי בין (\Delta_X,\Delta_Y) כאשר

\Delta_Y = S(X) \oplus S(X \oplus \Delta_X)

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

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

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

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

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

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

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