קמליה (צופן)

קמליה - Camellia הוא צופן בלוקים סימטרי שפותח בשנת 2000 בשיתוף פעולה של מיצובישי ו-NTT על ידי צוות קריפטוגרפים בראשות מיצורו מצואי . הוצע לגופי תקינה רבים, נכלל ברשימת הצפנים המומלצים של פרויקט NESSIE האירופאי משנת 2003 ופרויקט CRYPTREC של ממשלת יפן, הוצע במזכר RFC 3713 של IETF כתוספת ל-IPSec, אושר על ידי ארגון התקינה הבינלאומי בתקן ISO/IEC 18033-3 ונכלל בפרוטוקולי אבטחה פופולריים רבים, ביניהם SSL, OpenPGP ו-S/MIME. ספריות אבטחה רבות מספקות תמיכה לקמליה, ביניהן Crypto++, GPG, OpenSSL. קמליה מוגן בפטנט והותר על ידי NTT לשימוש ברישיון חופשי.

הצופן מקבל בלוק מידע בגודל 128 סיביות ומפתח הצפנה בשלושה גדלים אפשריים 128, 192 או 256 סיביות והפלט הוא בלוק מוצפן בגודל 128 סיביות. הצופן בעל סגנון ייחודי - מעין רשת פייסטל רקורסיבית, בשמונה-עשר או עשרים וארבעה סבבים בהתאם לאורך המפתח ופועל ברמה של בתים. הפונקציה הפנימית מתנהגת כרשת החלפה-תמורה על שמונה בתים, שכבת ההחלפה מתבצעת במקביל באמצעות שמונה תיבות החלפה (S-box) בגודל 8x8 סיביות ושכבת התמורה היא קומבינציה של XOR בין בתי הקלט. בנוסף, בדומה לMISTY ו-KASUMI כולל גם שכבת טרנספורמציה ליניארית תלוית מפתח שמופעלת אחת לשישה סבבים.

ביטחון

צופן קמליה קיבל הכרה כצופן מודרני בטוח ואינו נופל ברמתו מ-AES. הוא זוכה לפופולריות רבה גם עקב פשטותו ויעילותו הרבה הן בחומרה והן בתוכנה. ההתקפות הטובות ביותר הידועות נגד הצופן הן התקפה שנקראת Square Attack על גרסה מצומצמת (תשעה סבבים) בסיבוכיות של ${\displaystyle 2^{202}}$ הצפנות ועם ${\displaystyle 2^{61}}$ טקסטים מוצפנים. התקפה אחרת שנקראת Rectangle Attack של Shirai מצליחה לשבור את הצופן בעשרה סבבים בסיבוכיות של ${\displaystyle 2^{241}}$ קריאות זיכרון עם ${\displaystyle 2^{127}}$ טקסטים נבחרים. התקפה נוספת שהיא סוג של התקפה דיפרנציאלית אינה טובה משמעותית מכוח גס. בכללות אילו התקפות תאורטיות שאינן מסכנות את ביטחון הצופן. יש לציין שהטרנספורמציה הליניארית הנוספת (להלן), אחראית בין היתר על חוזקו.

תיאור הצופן

צופן קמליה (על שם צמח התה) הוא ממשיכו של E2 שהיה מהמועמדים ל-AES והסגנון הייחודי שלו מבוסס עליו במידה רבה. הפעולות בצופן הן בעיקר פעולות החלפה ופעולות לוגיות OR, XOR ו-AND על מילים או בתים. כאשר המרות ממילים לבתים וההפך הן לפי סדר בתים גדול (למשל אם המילה מכילה את הערך 0x01234567 (בבסיס הקסדצימלי) בהמרה לבתים הבית הראשון יכיל 0x01, השני 0x23, השלישי 0x45 והרביעי 0x67). בגרסת מפתח 128 סיביות, בלוק המידע עובר 18 סבבים של טרנספורמציה במבנה פייסטל בנוסף לשכבות הטרנספורמציה הליניארית ${\displaystyle FL}$ והטרנספורמציה ההופכית ${\displaystyle FL^{-1}}$ לאחר הסבב השישי והסבב השנים-עשר (כמתואר בתרשים משמאל). פונקציית הרחבת המפתח מקבלת את המפתח הסודי המסופק על ידי המשתמש ומייצרת ממנו תת-מפתחות מורחבים לכל הסבבים שהם ארבעה מפתחות הלבנה המסומנים ${\displaystyle kw_{t}}$ כאשר ${\displaystyle t=1,2,3,4}$, שמונה עשר מפתחות סבבים ${\displaystyle k_{u}}$ כאשר ${\displaystyle u=1,2,...,18}$ וכן ארבעה מפתחות ${\displaystyle kl_{v}}$ (עבור הפונקציות הליניאריות) כאשר ${\displaystyle v=1,2,3,4}$, כולם מילים באורך 64 סיביות. תחילה בלוק הטקסט ${\displaystyle M}$ מחובר ב-XOR (המסומן כאן ב-${\displaystyle \oplus }$) עם שני המפתחות הראשונים ${\displaystyle kw_{1},kw_{2}}$ בהתאמה, פעולה זו נקראת הלבנה. התוצאה מחולקת לשני חצאים ${\displaystyle L}$ ו-${\displaystyle R}$ ואז הפעולות הבאות מבוצעות ${\displaystyle r}$ פעמים כאשר ${\displaystyle r=1,...,18}$ למעט הסבבים 6 ו-12:

${\displaystyle L_{r}=R_{r-1}\oplus F(L_{r-1},k_{r})}$,

${\displaystyle R_{r}=L_{r-1}}$.

עבור הסבבים 6 ו-12 מבצעים כדלהלן:

${\displaystyle L_{r}^{'}=R_{r-1}\oplus F(L_{r-1},k_{r})}$,

${\displaystyle R_{r}^{'}=L_{r-1}}$,

${\displaystyle L_{r}=FL(L_{r}^{'},kl_{2r/6-1})}$,

${\displaystyle R_{r}=FL^{-1}(R_{r}^{'},kl_{2r/6})}$.

לבסוף התוצאות האחרונות ${\displaystyle R_{18}}$ ו-${\displaystyle L_{18}}$ עוברים שוב הלבנה עם המפתחות ${\displaystyle kw_{3},kw_{4}}$ בהתאמה. במילים אחרות פלט הצופן הוא ${\displaystyle C=(R_{18}\oplus kw_{3}\ \|\ L_{18}\oplus kw_{4})}$.

מפתחות 192 ו-256 סיביות

כאשר נבחר מפתח באורך 192 או 256 סיביות יחולו השינויים הבאים. יהיו שישה מפתחות עבור הפונקציות הליניאריות כלומר נוספו שני מפתחות ${\displaystyle kl_{5},kl_{6}}$. יהיו 24 מפתחות ${\displaystyle k_{u}}$ במקום 18 וכן קוראים לטרנספורמציה הליניארית והטרנספורמציה ההופכית שלה שלוש פעמים; בסבבים 6, 12 ו-18. כל היתר זהה.

פענוח

הפענוח בקמליה זהה להצפנה למעט היפוך סדר תת-המפתחות. אם המפתח הוא באורך 128 סיביות, תחילה מבטלים את ההלבנה על ידי חיבור ב-XOR עם המפתחות ${\displaystyle kw_{3},kw_{4}}$ בהתאמה ומתקבלים החצאים ${\displaystyle L_{18},R_{18}}$ מהסבב האחרון של ההצפנה ואז מבצעים עבור ${\displaystyle r=18}$ עד ${\displaystyle r=1}$ בסדר יורד למעט הסבבים 13 ו-7 כדלהלן:

${\displaystyle R_{r-1}=L_{r}\oplus F(R_{r},k_{r})}$,

${\displaystyle L_{r-1}=R_{r}}$.

בסבבים 13 ו-7 מבצעים:

${\displaystyle R_{r-1}^{'}=L_{r}\oplus F(R_{r},k_{r})}$,

${\displaystyle L_{r-1}^{'}=R_{r}}$,

${\displaystyle R_{r-1}=FL(R_{r-1}',kl_{2(r-1)/6})}$,

${\displaystyle L_{r-1}=FL^{-1}(L_{r-1}^{'},kl_{2(r-1)/6-1})}$.

הטקסט הקריא יהיה ${\displaystyle M=(L_{0}\oplus kw_{1}\ \|\ R_{0}\oplus kw_{2})}$.

אם המפתח הנבחר הוא באורך 192 או 256 סיביות, ההבדלים הם שמתבצעים בסך הכול 24 סבבים בסדר יורד והטרנספורמציה הליניארית מתבצעת בסבבים 19, 13 ו-7.

הכנת מפתח

הכנת המפתח נעשית באמצעות גרסה מצומצמת של רשת פייסטל כמתואר בתרשים משמאל. תחילה מגדירים שני משתנים מקומיים ${\displaystyle K_{L},K_{R}}$ באורך 128 סיביות כל אחד בהם מציבים את המפתח המסופק על ידי המשתמש. לכל משתנה אפשר להתייחס כאל מילה אחת באורך 128 סיביות או שתי מילים באורך 64 סיביות המייצגים את שני החצאים של משתנה האב, צד ימין של ${\displaystyle K_{L}}$ ייקרא ${\displaystyle K_{LR}}$ וצד שמאל ${\displaystyle K_{LL}}$ וכן לגבי ${\displaystyle K_{R}}$, בסך הכול ארבעה רבעים ${\displaystyle K_{LL},K_{LR},K_{RL}}$ ו-${\displaystyle K_{RR}}$ באורך 64 סיביות כל אחד. כאשר המפתח המסופק על ידי המשתמש הוא באורך 128 סיביות מציבים אותו ב-${\displaystyle K_{L}}$ ואילו המילה ${\displaystyle K_{R}=0}$. את המפתח המסופק על ידי המשתמש טוענים למשתנים הפנימיים כך שהכללים הבאים מתקיימים:

• עבור מפתח 128 סיביות; המפתח בחצי השמאלי ${\displaystyle K_{L}}$ ואילו החצי הימני ${\displaystyle K_{R}=0}$. שים לב ש- ${\displaystyle K_{LL}}$ ו-${\displaystyle K_{LR}}$ מכילים את שני חצאי ${\displaystyle K_{L}}$ בהתאמה.
• עבור מפתח 192 סיביות; המפתח מחולק כך ש-${\displaystyle K=K_{L}\ \|\ K_{RL},K_{RR}={\overline {K_{RL}}}}$. הסמל ${\displaystyle {\overline {x}}}$ הוא המשלים ל-1 של ${\displaystyle x}$ (אותו אפשר לקבל על ידי חיבור XOR עם וקטור של 64 אחדים). המפתח מתפרס על פני ${\displaystyle K_{L}}$ ומחצית מ-${\displaystyle K_{R}}$ - כלומר ${\displaystyle K_{RL}}$ ואילו החלק האחרון ${\displaystyle K_{RR}}$ מכיל את המשלים של ${\displaystyle K_{RL}}$.
• עבור מפתח 256 סיביות; המפתח מחולק כך ש-${\displaystyle K=K_{L}\ \|\ K_{R}}$.
• עבור כל המפתחות; ${\displaystyle K_{L}=K_{LL}\ \|\ K_{LR}}$ וכן ${\displaystyle K_{R}=K_{RL}\ \|\ K_{RR}}$.

בנוסף מגדירים שני משתנים ${\displaystyle K_{A}}$ ו-${\displaystyle K_{B}}$ באורך 128 סיביות כל אחד, אותם מאתחלים כדלהלן. תחילה מבצעים ${\displaystyle K_{L}\oplus K_{R}}$, את התוצאה מצפינים בהצפנה מקוצרת ברשת פייסטל בשני סבבים עם הפונקציה ${\displaystyle F}$ המתוארת להלן כאשר הערכים ${\displaystyle \Sigma _{1},\Sigma _{2}}$ מתוך הטבלה להלן משמשים כמפתחות הצפנה. את התוצאה מחברים ב-XOR עם ${\displaystyle K_{L}}$ ושוב מצפינים עם ${\displaystyle \Sigma _{3}}$ ו-${\displaystyle \Sigma _{4}}$ והתוצאה האחרונה תהיה ${\displaystyle K_{A}}$. את ${\displaystyle K_{A}}$ מחברים שוב ב-XOR עם ${\displaystyle K_{R}}$ ומצפינים עם ${\displaystyle \Sigma _{5},\Sigma _{6}}$ והתוצאה האחרונה היא ${\displaystyle K_{B}}$. התהליך מומחש בתרשים משמאל.

ערכי הקבועים הם 16 ספרות החל מהספרה השנייה ועד הספרה ה-17 של הייצוג ההקסדצימלי של חלק השבר של השורש הריבועי של ששת המספרים הראשוניים הראשונים.

מתוך המשתנים ${\displaystyle K_{L},K_{R},K_{A},K_{B}}$ גוזרים תת-מפתחות ${\displaystyle (kw_{t},k_{u},kl_{v})}$ כל אחד באורך 64 סיביות. כל מפתח נגזר מהחלק השמאלי או הימני של הזזה מעגלית של אחד מהמשתנים האמורים לפי הטבלה הבאה. למשל אם המפתח הנבחר הוא 192 או 256 סיביות אזי לפי הטבלה הימנית, ערכו של תת-המפתח ${\displaystyle k_{8}}$ עבור הסבב השמיני הוא החצי הימני של ${\displaystyle K_{B}}$ המסומן בטבלה ${\displaystyle K_{BR}}$ לאחר הזזה מעגלית 30 פוזיציות לשמאל.

הביטוי ${\displaystyle x\lll y}$ פירושו כאן הזזה מעגלית של ${\displaystyle x}$ במספר סיביות המצוין על ידי ${\displaystyle y}$ בגבולות מילה באורך 64 סיביות. לדוגמה אם המשתנה באורך 8 סיביות (בית), והוא מכיל את הערך 169 או 'A9' (בבסיס בינארי "10101001") לאחר הזה מעגלית לשמאל שלוש סיביות יתקבל 53 או '35' ("110101").

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

פונקציות עזר

להלן תיאור הפונקציות המרכיבות את הצופן מהגדול לקטן. הפונקציה ${\displaystyle F}$ המופיעה בתרשים משמאל מוגדרת כדלהלן:

${\displaystyle {\boldsymbol {F(X,k)\longmapsto Y=P(S(X\oplus k)}}}$

הפונקציה מקבלת שני פרמטרים, ערך ${\displaystyle X}$ וקטע מתאים מהמפתח המורחב ${\displaystyle k}$ באורך 64 סיביות כל אחד ומחזירה את ${\displaystyle Y}$ גם הוא באורך 64 סיביות תוך שימוש בפונקציות ${\displaystyle S}$ ו-${\displaystyle P}$ המייצגות החלפה ותמורה בהתאמה בנוסף לחיבור עם ${\displaystyle k}$.

הפונקציה FL

הפונקציה הליניארית ${\displaystyle FL}$ מקבלת שני פרמטרים; ${\displaystyle X}$ באורך 64 סיביות המחולק לצד ימין וצד שמאל ${\displaystyle X_{L}}$ ו-${\displaystyle X_{R}}$ בהתאמה ואת ${\displaystyle kl}$ המחולק גם הוא לשני חצאים ${\displaystyle kl_{L},kl_{R}}$ ומחזירה את ${\displaystyle Y}$ באורך 64 סיביות כדלהלן:

${\displaystyle FL(X_{L}\ \|\ X_{R},kl_{L}\ \|\ kl_{R})\longmapsto Y_{L}\ \|\ Y_{R}}$

כאשר

${\displaystyle Y_{R}=((X_{L}\land kl_{L})\lll 1)\oplus X_{R}}$,

${\displaystyle Y_{L}=(Y_{R}\lor kl_{R})\oplus X_{L}}$.

הסימן ${\displaystyle \land }$ מייצג את האופרטור הלוגי AND והסימן ${\displaystyle \lor }$ מייצג את האופרטור הלוגי OR.

הפונקציה הליניארית ההופכית

הפונקציה ההופכית מוגדרת כך:

${\displaystyle FL^{-1}(Y_{L}\ \|\ Y_{R},kl_{L}\ \|\ kl_{R})\longmapsto X_{L}\ \|\ X_{R}}$

כאשר

${\displaystyle X_{L}=(Y_{R}\lor kl_{R})\oplus Y_{L}}$,

${\displaystyle X_{R}=((X_{L}\land kl_{L})\lll 1)\oplus Y_{R}}$.

התרשים משמאל מתאר את שתי הפונקציות הליניאריות.

הפונקציה S

פונקציית ההחלפה מקבלת קלט ${\displaystyle l}$ באורך 8 בתים ונעזרת בארבע טבלאות החלפה ${\displaystyle s_{1},s_{2},s_{3}}$ ו-${\displaystyle s_{4}}$ להלן כדי להחליף את ערכי הבתים בבתים שבטבלה לפי אינדקסים - בכל טבלה בסך הכול 256 ערכים אפשריים. כדלהלן:

${\displaystyle l_{1}=s_{1}(l_{1}),l_{2}=s_{2}(l_{2}),l_{3}=s_{3}(l_{3}),l_{4}=s_{4}(l_{4})}$

${\displaystyle l_{5}=s_{2}(l_{5}),l_{6}=s_{3}(l_{6}),l_{7}=s_{4}(l_{7}),l_{8}=s_{1}(l_{8})}$

לדוגמה אם ערכו של הבית ${\displaystyle l_{1}=12}$, התוצאה לפי הטבלה הראשונה היא ${\displaystyle l_{1}=s_{1}(12)=234}$.

תיבות ההחלפה

תיבות ההחלפה של קמליה (s-box) הן ערכי שקילות אפינית של פונקציות הופכיות מעל השדה ${\displaystyle GF(2^{8})}$. בהצגה אלגברית:

${\displaystyle s_{1}(x)\longmapsto \mathbf {h} (\mathbf {g} (\mathbf {f} ({\text{0xc5}}\oplus x)))\oplus {\text{0x6a}}}$

${\displaystyle s_{2}(x)\longmapsto s_{1}(x)\lll 1}$

${\displaystyle s_{3}(x)\longmapsto s_{1}(x)\ggg 1}$

${\displaystyle s_{4}(x)\longmapsto s_{1}(x\lll 1)}$

הפונקציה ${\displaystyle \mathbf {f} }$ היא צירוף ליניארי של סיביות הקלט לפי הנוסחה:

${\displaystyle b_{1}=a_{6}\oplus a_{2},b_{2}=a_{7}\oplus a_{1},b_{3}=a_{8}\oplus a_{5}\oplus a_{3},b_{4}=a_{8}\oplus a_{3}}$,

${\displaystyle b_{5}=a_{7}\oplus a_{4},b_{6}=a_{5}\oplus a_{2},b_{7}=a_{8}\oplus a_{1},b_{8}=a_{6}\oplus a_{4}}$.

הפונקציה ${\displaystyle \mathbf {g} }$ מוגדרת כך:

${\displaystyle (b_{8}+b_{7}\alpha +b_{6}\alpha ^{2}+b_{5}\alpha ^{3})+(b_{4}+b_{3}\alpha +b_{2}\alpha ^{2}+b_{1}\alpha ^{3})\beta }$

${\displaystyle =1/((a_{8}+a_{7}\alpha +a_{6}\alpha ^{2}+a_{5}\alpha ^{3})+(a_{1}+a_{3}\alpha +a_{2}\alpha ^{2}+a_{1}\alpha ^{3})\beta )}$

כאשר ${\displaystyle \beta }$ מקיים ${\displaystyle \beta ^{8}+\beta ^{6}+\beta ^{5}+\beta ^{3}+1=0}$ וכן ${\displaystyle \alpha =\beta ^{238}=\beta ^{6}+\beta ^{5}+\beta ^{3}+\beta ^{2}}$ הוא אלמנט בשדה ${\displaystyle GF(2^{4})}$ המקיים ${\displaystyle \alpha ^{4}+\alpha +1=0}$.

הפונקציה ${\displaystyle \mathbf {h} }$ מוגדרת בסיביות עבור הקלט ${\displaystyle a=a_{1}a_{2}a_{3}a_{4}a_{5}a_{6}a_{7}a_{8}}$ כך:

${\displaystyle b_{1}=a_{5}\oplus a_{6}\oplus a_{2},b_{2}=a_{6}\oplus a_{2},b_{3}=a_{7}\oplus a_{4},b_{4}=a_{8}\oplus a_{2}}$

${\displaystyle b_{5}=a_{7}\oplus a_{3},b_{6}=a_{8}\oplus a_{1},b_{7}=a_{5}\oplus a_{1},b_{8}=a_{6}\oplus a_{3}}$

אפשר לראות שערכי התיבות ${\displaystyle s_{2},s_{3}}$ ו-${\displaystyle s_{4}}$ למעשה נגזרות מהתיבה הראשונה. לכן אם הזיכרון מוגבל כמו בכרטיס חכם, אפשר לאחסן בזיכרון רק את הטבלה הראשונה ולחשב את ההחלפה במקום על ידי הנוסחאות המתוארות. למשל אם ${\displaystyle x=20}$ החלפה של ${\displaystyle x}$ לפי טבלה 3 היא: ${\displaystyle \textstyle s_{1}(20)\ggg 1=69\ggg 1=162}$.

להלן ערכי תיבות ההחלפה:

${\displaystyle \mathbf {s_{1}} }$

${\displaystyle \mathbf {s_{2}} }$

${\displaystyle \mathbf {s_{3}} }$

${\displaystyle \mathbf {s_{4}} }$

הפונקציה P

הפונקציה ${\displaystyle P}$ מקבלת מערך של שמונה בתים ${\displaystyle z_{1},...,z_{8}}$ ומחזירה את התמורה שלהם לפי:

דרך אחרת להציג זאת היא על ידי כפל מטריצות:

כאשר

קוד לדוגמה

להלן קוד שלם בשפת ++C של הצפנת קמליה לפי RFC 3713:

ראו גם

• צופן בלוקים
• KASUMI
• ARIA

הערות שוליים

1. קמליה מרושתת
2. קימלה
3. MISTY (צופן)
4. צופן החלפה
5. צופן שחלוף
6. צופן ויז'נר
7. צופן פלייפייר
8. צופן בלוקים
9. צופן קיסר
10. צופן אתב"ש
11. ARIA (צופן)
12. צופן בלוקים בר-התאמה
13. הלבנה (קריפטוגרפיה)
14. FEAL
15. אופן הפעלה של צופן בלוקים
16. צופן סימטרי
17. צופן זרם
18. צופן ורנם
19. צופן היל
20. Hummingbird (צופן)