Blowfish

Blowfish הוא צופן בלוקים סימטרי שפותח ב-1993 על ידי ברוס שנייר. זהו אלגוריתם הצפנה מהיר ובטוח מ-DES או IDEA ותומך במפתח בגודל משתנה בטווח של 32 עד 448 סיביות במטרה להכשירו לשימוש מקומי או לייצוא (בשל מגבלות הייצוא של ממשלת ארצות הברית על גודל מפתח ההצפנה). Blowfish אינו מוגן בפטנט או ברישיון כלשהו והוא חופשי לשימוש לכל מטרה. מאז המצאתו נבחן האלגוריתם על ידי מומחים רבים וקיבל הכרה כאלגוריתם חזק. חסרונותיו הם: גודל הבלוק, שנקבע ל-64 סיביות בלבד ועל כן אינו מתאים לתקן ההצפנה המתקדם שדורש לפחות 128 סיביות; תהליך הרחבת מפתח ארוך במידה ניכרת, דבר המאט את ביצועיו; כמו כן, התגלו מפתחות הצפנה חלשים שיש להימנע משימוש בהם.

מבנה Blowfish מזכיר רשת פייסטל בדומה ל-DES. בשל שלב ההכנה הארוך מן הרגיל ליצירת תת-מפתחות לכל סבבי ההצפנה, מתאים במיוחד כשאין צורך לשנות מפתח באופן תדיר כגון בהצפנת ארכיון קבצים או דיסק קשיח. גודל הבלוק נקבע ל-64 סיביות ואורך המפתח יכול להשתנות להשגת רמות שונות של ביטחון. הוא כולל שני שלבים עיקריים; הרחבת מפתח שבו מפתח בגודל מרבי של 448 סיביות מורחב לגודל כולל של 4,168 סיביות. ותהליך הצפנה - טרנספורמציה המבוצעת על מחצית מהקלט ב-16 סבבים לסירוגין וכוללת תמורה תלוית מפתח והחלפה תלוית מפתח, תוך שימוש בפעולות חיבור ו-XOR בלבד על מילים בגודל 32 סיביות. בנוסף לארבע פעולות נוספות של חיפוש בטבלה לפי אינדקס (lookup). האלגוריתם מכיל ארבע תיבות החלפה (S-box) דינאמיות תלויות-מפתח, המכילות 256 כניסות בגודל 32 סיביות והוא עושה שימוש בקבועים שהם חלק מספרות הערך פאי בייצוג בינארי.

תיאור האלגוריתם

מבנה סכימתי של יישום רשת פייסטל באלגוריתם Blowfish. הסמל

\oplus

מייצג XOR

הקלט הוא הערך $x$ (בלוק מידע המיועד להצפנה) בגודל 64 סיביות ומפתח מורחב (ראה תהליך הרחבת מפתח) המיוצג על ידי הטבלה $P$ המכילה 18 כניסות:

1. חוצים את הקלט לשני חצאים בגודל 32 סיביות $x_{L},x_{R}$ :

2. עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1,...,16} מבצעים:

2.1 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_L = x_L \oplus P_i} (הסמל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \oplus} מייצג XOR)

2.2 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_R = F(x_L) \oplus x_R}

2.3 החלף מקומות בין

x_{L}

ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_R}

3. החלף מקומות בין הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_L} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_R} (מבטל את ההחלפה מהסבב האחרון)

4. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_R = x_R \oplus P_{17}}

5. הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_L = x_L \oplus P_{18}}

6. חבר מחדש את $x_{L}$ ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_R} .

הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} מחלקת את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_L} לארבעה בתים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a, b, c, d} המשמשים כאינדקס לערך המתאים בתיבות ההחלפה (ראה להלן) ומחשבת כדלהלן:הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(x_L)=((S_{1,a} + S_{2,b}\mbox{ mod } 2^{32}) \oplus S_{3,c}) + S_{4,d} \mbox{ mod }2^{32}}

הרחבת מפתח

המפתח כולל טבלת תמורה P המכילה 18 כניסות של 32 סיביות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1, P_2,...,P_{18}} . ראשית מאתחלים את כל כניסות הטבלה בערכים קבועים שהם ספרות פאי לאחר הנקודה. להלן ארבעת הערכים הראשונים בייצוג הקסדצימלי:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_1= \mbox{243F6A88}}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_2 = \mbox{85A308D3}}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_3 = \mbox{13198A2E}}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_4 = \mbox{03707344}}

מוסיפים באמצעות XOR את המפתח הראשוני שמסופק על ידי המשתמש באופן מחזורי עד להשלמת כל הכניסות. לדוגמה אם המפתח מכיל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_1,...,K_4} מילים בגודל 32 סיביות (בסך הכול 128 סיביות) אזי מחשבים מ-1 עד 18 את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_i=P_i\oplus K_{((i-1)\mbox{ mod }4) \ + \ 1}} . בשלב השני מעדכנים באופן איטרטיבי את כל כניסות הטבלה באופן הבא; מתחילים בהצפנת מחרוזת אפסים ובכל שלב מחליפים את שתי הכניסות הבאות בתוצאת ההצפנה, את התוצאה חוזרים ומצפינים שוב עם המפתח המעודכן, מעדכנים את הכניסות הבאות בתוצאה וחוזר חלילה. להלן פסאודו קוד:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle dl=0,dr=0}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{For }i=1\mbox{ to }9\mbox{ Do:}}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (dl,dr)\leftarrow \mbox{Encipher}(dl,dr)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_{2i-1}=dl}

P_{2i}=dr

הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{Encipher(dl,dr)}} מתארת את תהליך ההצפנה המובא לעיל שלבים 1 עד 6.

תיבות החלפה

האלגוריתם כולל ארבע תיבות החלפה תלויות מפתח הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_1,..,S_4} הנקראות S-box. כל טבלת החלפה היא מערך של 256 מילים בגודל 32 סיביות והאינדקס לערך נתון הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{i,j}} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i=1,...,4} מייצג את הטבלה ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle j=1,...,256} מייצג את הכניסה. היות שתיבות ההחלפה תלויות במפתח יש לבנותם בשלב ההכנה באופן דומה להרחבת המפתח. מתחילים בהצבת הערכים הקבועים (אותם מכינים מראש מהערך פאי) לאחר מכן מצפינים אפסים ואת תוצאת ההצפנה חוזרים ומצפינים שוב כך 256 פעמים כאשר בכל סבב מציבים בשתי הכניסות הבאות של כל אחת מארבע הטבלאות את תוצאת ההצפנה, מחצית בכניסה הראשונה ומחצית בכניסה הבאה אחריה וחוזר חלילה. התהליך מתואר בפסאודו קוד הבא:

$dl=0,dr=0$
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{For }i=1\mbox{ to }4\mbox{ Do:}}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{For }j=1\mbox{ to }256\mbox{ Do: }}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (dl,dr)\leftarrow \mbox{Encipher}(dl,dr)}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{i,j}=dl}

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_{i,j+1}=dr}

נדרשים בסך הכול 521 סבבים של הצפנה לאתחול המפתח המורחב וכל תיבות ההחלפה.

פענוח

הפענוח מבוצע בדרך זהה למעט סדר הכניסות בטבלת התמורה $P$ שהוא הפוך מההצפנה.

ביטחון

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