צופן בלוקים

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

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

בין צופני הבלוקים המודרניים אפשר למנות את DES, AES, MARS, סרפנט, Blowfish, Twofish, CAST5, RC6 וכן IDEA.


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

מראה רשת פייסטל בסיסית. הסימן \oplus מייצג XOR

הצופנים הקלאסיים כמו צופן ויז'נר נקראים צופן בלוקים, כאשר גודל הבלוק הוא כגודל אות אחת. אולם פונקציית הצפנה כמו פרמוטציה או החלפה על 26 אותיות פשוטה מדי וקלה לשבירה מכמה סיבות; מספר האפשרויות למפתח הצפנה מוגבל מאוד ולעתים חלק מהתכונות הסטטיסטיות של הטקסט המקורי זולגות לתוך הטקסט המוצפן. כמעט כל הצפנים הקלאסיים למעט פנקס חד-פעמי, פגיעים להתקפת ניתוח תדירויות. הידע הקיים כיום בנושא צופני בלוקים מודרניים בטוחים, מתבסס על עבודתו של קלוד שאנון ב-1949 בנושא תקשורת וסודיות‏[1]. הוא הציע ליצור צופן חזק על ידי הרכבה וצירוף של מספר טרנספורמציות חלשות כמו החלפה (שיכול) או פרמוטציה (תמורה) במספר מרובה של סבבים. הטרנסופרמציות הללו נבחרות כך שיושגו שתי תכונות החיוניות בכל צופן כדי שייקרא בטוח, קרי, פיזור (diffusion) וערבוב (confusion). הפיזור נועד להבטיח שהמפתח והטקסט הקריא ישפיעו על כל סיביות הצופן במידה שווה וערבוב נועד לגרום לקשר בין הצופן למקור או המפתח להיות מסובך ורחוק ככל האפשר. הטרנסופרמציות מבוצעות בכל סבב על בלוק המידע כולו או על חלקו, תוך שימוש במפתח ההצפנה.

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


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

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

אפשר להתייחס לצופן בלוקים כאל צופן החלפה המופעל על תווים 'גדולים'. טרנספורמצית ההצפנה אותה מסמנים ב-\ E מקבלת פרמטר \ K מתוך תת-קבוצה \mathcal{K} של מרחב כל מפתחות האפשריים \ V_k ובלוק מידע קריא בגודל \ n סיביות וממירה אותו לבלוק צופן מתאים. בדרך כלל בלוקי המידע והצופן זהים בגודלם למניעת התנפחות לא רצויה. לביטחון מרבי ההנחה היא ש-\ K סודי ונבחר באופן אקראי על ידי המצפין. אלגוריתם ההצפנה \ E יכול להיות טרנספורמציה הפיכה כלשהי של המפתח או סדרה של טרנספורמציות מוגדרות היטב, אך אינו חייב להיות סודי. סודיות ההצפנה נשענת אך ורק על סודיות המפתח.

עבור כל בלוקי טקסט וצופן אפשריים, בגודל \ n סיביות ומפתח \ K בגודל מתאים, פונקציית ההצפנה חייבת להיות חד-חד ערכית והתוצאה תהיה תמורה ייחודית מעל וקטור של \ n סיביות. מספר המפתחות האפשריים הוא |\mathcal{K}|. גודל המפתח האפקטיבי הוא \ \mbox{log}|\mathcal{K}|; פירושו שאם \ K שווה כל טווח המפתחות האפשריים, כלומר \ \mathcal{K} = V_k אזי \ \mbox{log}|\mathcal{K}| = |\mathcal{K}|. אם כל מפתח נבחר בהסתברות זהה וכל מפתח מגדיר תמורה שונה, האנטרופיה של המפתח גם היא \ \mbox{log}|\mathcal{K}|. את אלגוריתם הצפנה אפשר לייצג כפונקציה:

\ E : V_n \times K \rarr V_n

למען הנוחות אפשר לסמן את פונקציית ההצפנה \ E_ K כאשר \ K הוא המפתח ואילו המיפוי ההופכי \ E^{-1} _K אפשר לסמן ב-\ D_ K, שים לב שהמפתח זהה בשני המקרים. הגדרה כללית של צופן בלוקים:

תהליך ההצפנה:
\ C = E_ K (P)
תהליך הפענוח:
\ P = D_ K (C)

תאורטית צופן בלוקים אמור ליישם את כל התמורות האפשריות מתוך טווח המפתחות. כלומר כדי לקבל בלוק צופן אקראי אמיתי על הפונקציה להיות ערך כלשהו, מתוך טווח כל \ 2^n! התמורות האפשריות, מעל \ 2^n אלמנטים. אולם הבעיה היא שכדי לייצג מפתח אקראי (אמיתי) בסדר גודל של \ n סיביות, יהיה צורך ב- \ \mbox{log} ( 2^n !) שזה בערך \ 2^n פעמים סיביות בלוק המסר בקירוב. על כן מקובל שפונקציית הצפנה המתאימה למפתח אקראי כלשהו, "תראה" מבחינה חישובית כאקראית. את המפתח באורך הרצוי מפיקים מתוך מפתח קצר, בתהליך הנקרא הרחבת מפתח, באופן כזה שאינו מאפשר תאורטית (או בכל אופן קשה מאוד מבחינה חישובית), ניחוש המפתח המורחב ללא ידיעת \ K.

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

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

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

ככל שהמפתח גדול מושג ביטחון רב יותר. אם למשל המפתח כאורך המסר המיועד להצפנה בטחון הצופן במקרה זה יהיה מקסימלי, אולם מצד שני יעילות הצופן תרד באופן דרסטי, מלבד העובדה שיצירת מפתח כזה ארוך קשה ומסובכת (ראה פנקס חד-פעמי). במציאות בדרך כלל מתפשרים על מפתח קצר אותו מרחיבים באמצעות פרוצדורה המדמה אקראיות ומסוגלת לייצר ערך פסאודו-אקראי באורך הרצוי. השיקול תלוי ביכולת טכנולוגית, דרישות הביטחון ובמאפייני האלגוריתם. DES הסתפק במפתח בגודל 64 סיביות כאשר מתוכם רק 56 סיביות השפיעו על ההצפנה היתר שימשו לבדיקת זוגיות, כיום מפתח באורך כזה ניתן לשבירה במאמץ קל. נכון לשנת 2014 מפתחות הצפנה בגודל 128 עד 512 סיביות מספקים ביטחון הולם לכל צורך מעשי. ההמלצה היא לעבור למפתחות 256 סיביות לטווח של עשר השנים הקרובות. מרבית האלגוריתמים הסימטריים המודרניים פועלים על בלוקים בגודל 128 - 256 סיביות. כמו כן כל אלגוריתם סימטרי מודרני חייב להיות עמיד מלבד כנגד כוח גס, כנגד קריפטאנליזה דיפרנציאלית ולינארית.

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

Postscript-viewer-shaded.png ערך מורחב – מצב הפעלה של צופן בלוקים

בדרך כלל המידע המיועד להצפנה עולה על גודל הבלוק שאלגוריתם ההצפנה מקבל. היות שצופן בלוקים דטרמיניסטי באופיו במובן שהפעלת פונקציית ההצפנה על בלוק נתון פעם נוספת עם מפתח זהה תניב בלוק צופן זהה, יש סבירות גבוהה שבלוקי מידע יחזרו על עצמם במסר הגלוי ובכך יחזרו על עצמם גם הטקסטים המוצפנים המקבילים. במקרים מסוימים עובדה זו עלולה להוות נקודת תורפה, כיוון שמידע על שכיחות בלוקי צופן זהים עשוי לעזור למתקיף הצופן בחשיפת מידע חלקי אודות המערכת. כאשר המסר גדול מיישמים את הצופן במה שקרוי מצב הפעלה (Modes of operation) בטוח. השיטות הבסיסיות כוללות את ECB ,CBC ,CFB ,OFB ו-CTR. שיטות אילו למעט ECB מתמודדות בעיקר - ברמה כזו או אחרת במצב של שגיאת שידור והתאוששות אך אינן מספקות הגנה מפני שינוי זדוני. קיימות שיטות בטוחות מתקדמות יותר המספקות גם הבטחת שלמות כמו שילוב עם קוד אימות מסרים ביניהן ניתן למנות את: XCBC,IACBC,IAPM,OCB,EAX,CWC מצב העפלה,CCM ו-GCM.

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

Handbook of Applied Cryptography

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