צופן בלוקים

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

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

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

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

הרעיון של שילוב מספר טרנספורמציות חלשות ליצירת צופן חזק ייושם לראשונה באלגוריתם DES שפורסם ב-1977 על ידי NIST. אלגוריתם זה היווה אבן דרך בתולדות ההצפנה המודרנית ושפך אור על התפישה המודרנית של פיתוח צופני גושים. למרות שאינו בטוח לשימוש כיום בשל המפתח הקצר, הרעיונות שיושמו בו עדיין מהווים בסיס תאורטי חשוב והוא בעל ערך אקדמאי שהשפיע רבות על התפתחות הקריפטואנליזה המודרנית, דיפרנציאלית ולינארית. למעשה ניתן לראות באלגוריתמים מודרניים רבים כמו AES או 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.

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

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

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

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

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

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

הגישה הישירה היא לחלק את המסר לגושים בגודל \ n סיביות, לרפד את הגוש האחרון באפסים, אם אורך המסר אינו מתחלק בדיוק ב-\ n ולהצפין כל גוש בנפרד כדלהלן:

הצפנה
עבור כל גוש \ i במסר \ x, בצע: \ c_i = E_K(x_i).
פענוח
אופן הפענוח זהה לחלוטין כאשר פונקציית הפענוח היא \ E^{-1}_K.

מצב זו מכונה Electronic codebook. מכיוון שעבור כל גוש מסר זהה ייווצר גוש צופן זהה, תאורטית ניתן להכין מראש טבלת קידוד המכילה טור אחד של כל גושי המסר האפשריים וטור מתאים של כל גושי הצופן המקבילים ולהצפין את המסר בעזרת הטבלה. הרעיון תאורטי היות שאם \ n = 64 כמות הכניסות בטבלה תהיה \ 2^{64} אולם מסביר את השם "ספר קוד" שניתן למצב זה. מצב זה נחשב לפחות בטוח ומומלץ במקרים מיוחדים בשל פגיעותו לניתוח סטטיסטי. יתרונו הוא בכך שאין בו כשל מצטבר. כשל בקריאת או הצפנת סיבית אחת או יותר, עלול לקרות במקרה של ערוץ התקשורת לקוי או קובץ פגום. במקרה זה, הגוש הפגום אינו משפיע על יתר הגושים.

תכונות ECB:

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

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

מצב הפעלה Cipher-Block Chaining או CBC מערב שימוש בוקטור אתחול באורך \ n סיביות המכונה \ \mbox{IV}. במצב זה גושי הצופן משורשרים אחד לשני בעזרת חיבור בינארי XOR המיוצג על ידי \ \oplus כדלהלן:

הצפנה
\ c_0 = \mbox{IV}, עבור כל גוש \ i במסר \ x בצע:
\ c_i = E_K (c_{i-1}) \oplus x_i
פענוח
הפענוח זהה לחלוטין למעט השימוש בפונקציה ההופכית \ E^{-1}_K.

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

תכונות CBC:

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

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

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

הצפנה
תחילה \ I_1 = \mbox{IV} כאשר \ I הנו אוגר זיזה.

עבור כל גוש במסר \ x בצע:

  1. \ O_j = E_K (I_j)
  2. עבור \ r נמוך מ-\ n, בצע: \ t_j שווה \ r הסיביות הגבוהות של \ O_j.
  3. \ c_j = x_j \oplus t_j (שדר \ r סיביות צופן כגוש \ c_j.
  4. \ I_{j+1} = 2^r * I_j + c_j \mbox{ mod } 2^n. (הזז את סיביות \ c_j למעלה \ r צעדים).
פענוח
תהליך הפענוח זהה:
  1. תחילה \ I_1 = \mbox{IV}. לאחר מכן עבור כל גוש j בצופן x מבצעים:
  2. \ x_j = c_j \oplus t_j, כאשר \ t_j, \ O_j, \ I_j מחושבים בדיוק כמו בתהליך ההצפנה עם הפונקציה ההופכית \ E^{-1}_K\}.

תכונות CFB:

  1. שרשור. וקטור האתחול משבש את הקשר בין המסר המקורי לצופן וגורם לכך שגושי הצופן יהיו שונים גם אם גושי המסר זהים. אין צורך שוקטור האתחול יהיה סודי, אם כי רצוי במקרים מסוימים.
  2. תלות הדדית. בדומה ל-CBC כל גוש צופן, תלוי בגוש המסר המקביל ובגושי צופן קודמים. סידור מחדש של גושי צופן משפיע על הפענוח. ליתר דיוק, כל גוש צופן תלוי ב-\ n/r גושי הצופן קודמים.
  3. כשל מצטבר. סיבית אחת או יותר שגויים, בגוש נתון עשויים להשפיע על פענוח \ \ n/r הגושים הבאים. כלומר עד אשר \ n סיביות צופן עובדו והגוש השגוי הוזז לגמרי מתוך הרגיסטר.
  4. התאוששות עצמית. מצב CFB מכיל סנכרון עצמי בדומה לשיטת CBC, אולם רק לאחר \ n/r גושי צופן.
  5. הספק. במצב זה ההספק נמוך בהשוואה למצבים האחרים אם \ r < n, בפקטור של \ n/r. במובן שכל הרצה של פונקציית ההצפנה, מניבה רק \ r סיביות מוצפנות לעומת \ n.

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

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

הצפנה
תחילה: \ I_1 = \mbox{IV}, ועבור כל גוש \ j במסר \ x בצע:
  1. \ O_j = E_K(I_j). (חשב את בלוק הצופן הבא).
  2. עבור \ r כלשהו, \ r \le n, בצע: \ t_j שווה \ r הסיביות הגבוהות של \ O_j.
  3. \ c_j = x_j \oplus t_j (הצפן ושדר את \ r הסיביות הנוכחיות).
  4. \ I_{j+1} = O_j. (עדכן את הגוש הבא. שים לב לשימוש במפתח להזנת הרגיסטר).
פענוח
בדומה להצפנה,
  1. תחילה \ I_1 = \mbox{IV} ועבור כל גוש \ j בצופן \ x בצע:
  2. \ x_j = c_j \oplus t_j כאשר \ t_j, \ O_ j, \ I_j מחושבים בדיוק כמו בתהליך ההצפנה עם הפונקציה ההופכית \ E^ {-1}_ {K}.


תכונות OFB דומות ל-CFB למעט הבדלים קלים:

  1. שרשור. וקטור האתחול אחראי לכך שגושי מסר זהים יוצפנו לגושי צופן שונים.
  2. תלות הדדית. זרם המפתח עצמאי לגמרי ואינו תלוי במסר. משמעות הדבר שווקטור האתחול חייב להיות שונה, אם משתמשים באותו מפתח להצפנת מסר אחר.
  3. כשל מצטבר. במצב זה אין כשל מצטבר. סיבית אחת או יותר, שגויים, בגוש צופן כלשהו ישפיעו אך ורק על אותם סיביות בגוש המסר המקביל. כאשר סיביות אלו במסר המפוענח יהפכו למשלימים של סיביות המסר המקורי באותם מקומות.
  4. התאוששות עצמית. מצב OFB אינו מסוגל להסתנכרן באופן עצמאי. בשל כך, כשל בקריאת גוש צופן אחד או יותר, משבש את התיאום בין הגושים לבין זרם המפתח ותוצאת הפענוח מנקודה זו ואילך תהיה שגויה. על כן יש צורך בהתערבות חיצונית לסנכרון מחדש.
  5. הספק. אם \ r < n כמו בגרסאות מסוימות של OFB, הספק הפונקציה נמוך, בדיוק כמו ב-CFB. אולם מאחר שזרם המפתח אינו תלוי בגושי המסר או הצופן, ניתן לחשבו מראש (בהינתן וקטור אתחול כלשהו ומפתח K), מה שמייעל משמעותית את תהליך ההצפנה. להשגת בטיחות מרבית מומלץ לא להשתמש ב-\ r < n. כמו כן, כאשר \ r = n הספק הפונקציה לינארי ביחס לקלט.

אפשר ליישם את מצב OFB בעזרת מונה כך ש: \ I_{j+1} = I_j + 1 במקום שימוש בפידבק כמתואר לעיל. אופן זה יעיל יותר לעתים ומספק רמת בטיחות זהה ובמיוחד התאוששות מהירה במקרה של כשל, מכיוון ששיטה זו מאפשרת גישה אקראית, במילים אחרות אין צורך לחשב את הגוש הקודם כדי לשחזר גוש נוכחי.
לסיכום ניתן לראות בבירור כי מצב OFB וכן CFB למעשה מיישמים הצפנת בלוקים באופן הדומה לצופן זרם, בכך שהם מייצרים זרם מפתח ייחודי, התלוי בפרמטרים אחרים כגון גושי צופן קודמים או המפתח עצמו ובעזרת וקטור אתחול. בעיקרון אפשר בדרך זו, להתייחס לכל צופן בלוקים כאל צופן זרם.

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

Handbook of Applied Cryptography

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