צופן בלוקים

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

כדי לאפשר פענוח נכון של המסר, על הפונקציה האמורה $\ E$ , להיות 1-1 (כלומר ניתנת להיפוך). עבור כל גושי טקסט וצופן אפשריים, בגודל $\ 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$ . לפענוח נכון כאמור, חובה שעבור כל מפתח $\ K$ מהקבוצה $\ \mathcal{K}$ , הפונקציה $\ E(P,K)$ ניתנת להיפוך . אפשר לייצג את פונקציית ההצפנה $\ E_ K(P)$ ואילו המיפוי ההופכי $\ E^{-1} _K$ יהיה $\ D_ K(C)$ .

תהליך ההצפנה:: $\ C = E_ K (P)$

C נוצר מהפעלת הפונקציה E עם הפרמטר K על המסר P.

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

P משחוזר מהצופן C על ידי הפעלת הפונקציה ההופכית D, עם אותו מפתח K.

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

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

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

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

[עריכה] מצבי הפעלה

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

[עריכה] מצב ECB

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

הצפנה: עבור כל גוש i במסר x, בצע: $\ c_i = E_K(x_i)$ .

פענוח: אופן הפענוח זהה לחלוטין כאשר פונקציית הפענוח היא $\ E^{-1}_K$ .

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

תכונות ECB:

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

[עריכה] מצב CBC

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

הצפנה: $\ c_0 = \mbox{IV}$ , עבור כל גוש $\ i$ במסר $\ x$ בצע:

$\ c_i = E_K (c_{i-1}) \oplus x_i$

פענוח: הפענוח זהה לחלוטין למעט השימוש בפונקציה ההופכית $\ E^{-1}_K$ .

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

תכונות CBC:

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

[עריכה] מצב CFB

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

הצפנה: תחילה $\ I_1 = \mbox{IV}$ כאשר $\ I$ הנו $Shift register$ .

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

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

פענוח: תהליך הפענוח זהה:

תחילה $\ I_1 = \mbox{IV}$ . לאחר מכן עבור כל גוש j בצופן x מבצעים:
$\ x_j = c_j \oplus t_j$ , כאשר $\ t_j$ , $\ O_j$ , $\ I_j$ מחושבים בדיוק כמו בתהליך ההצפנה עם הפונקציה ההופכית $\ E^{-1}_K\}$ .

תכונות CFB:

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

[עריכה] מצב OFB

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

הצפנה: תחילה: $\ I_1 = \mbox{IV}$ , ועבור כל גוש $\ j$ במסר $\ x$ בצע:

$\ O_j = E_K(I_j)$ . (חשב את בלוק הצופן הבא).
עבור $\ r$ כלשהו, $\ r \le n$ , בצע: $\ t_j$ שווה $\ r$ הסיביות הגבוהות של $\ O_j$ .
$\ c_j = x_j \oplus t_j$ (הצפן ושדר את $\ r$ הסיביות הנוכחיות).
$\ I_{j+1} = O_j$ . (עדכן את הגוש הבא. שים לב לשימוש במפתח להזנת הרגיסטר).

פענוח: בדומה להצפנה,

תחילה $\ I_1 = \mbox{IV}$ ועבור כל גוש $\ j$ בצופן $\ x$ בצע:
$\ x_j = c_j \oplus t_j$ כאשר $\ t_j$ , $\ O_ j$ , $\ I_j$ מחושבים בדיוק כמו בתהליך ההצפנה עם הפונקציה ההופכית $\ E^ {-1}_ {K}$ .

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

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

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