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

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

אטימולוגיה

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

היסטוריה

הראשונים לפרסם את הקריפטאנליזה הדיפרנציאלית היו עדי שמיר ואלי ביהם בסוף שנות ה-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 מייצג את המרכיב הלא-ליניארי של הצופן). קשרים סטטיסטיים בין ΔX ל-ΔY מאפשרים להבדיל בין טקסט מוצפן לטקסט אקראי ובכך להפחית את מספר הניסיונות הדרושים כדי לאתר את המפתח באמצעות כוח-גס.

עמידות של צפנים

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

ראו גם

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

לקריאה נוספת

Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. מסת"ב 0-387-97930-1, מסת"ב 3-540-97930-1.
Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES", Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991.

הערות שוליים

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

[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. {{cite journal}}: (עזרה) (subscription required)

[1]

[2]