תמורה פסאודו-אקראית

בקריפטוגרפיה, תְּמוּרָה פְּסֵידוֹ-אקראית (Pseudorandom Permutation) בקיצור PRP היא פונקציה שלא ניתן להבחין בינה לבין תמורה אקראית שנבחרה בהתפלגות אחידה מתוך משפחת כל התמורות בעלות תחום דומה^[1]. במילים אחרות PRP היא משפחה של תמורות המדמות אורקל אקראי באופן שלא קיים אלגוריתם יעיל שיכול להבחין עם יתרון משמעותי לפי הפלט, בין תמורה שנבחרה ממשפחה זו לבין תמורה אקראית. ההבדל היחיד בין תמורה פסידו-אקראית לפונקציה פסידו-אקראית הוא שבתמורה תמיד קיימת פונקציה הופכית.

אובייקט תאורטי דומה נקרא תמורה בלתי צפויה (unpredictable permutation) בקיצור UP. על בסיס פונקציה בלתי צפויה, תמורה בלתי צפויה היא תמורה שלא קיים אלגוריתם אקראי יעיל שיכול לחזות את ערכיה בדיוק גבוה באופן משמעותי מניחוש אקראי^[2].

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

הגדרה

תהי $P:\{0,1\}^{*}\times \{0,1\}^{*}\longrightarrow \{0,1\}^{*}$ פונקציה יעילה, משמרת-אורך, עם מפתח. אפשר להתייחס אל $P$ כאל משפחה של תמורות, למשל הפונקציה $P_{k}(\cdot )$ היא תמורה אחת מתוך המשפחה, כך שעבור כל $k$ שנבחר באקראי $P_{k}$ היא תמורה עם מפתח של הקלט. כיוון שאורך הפלט זהה לאורך הקלט, מזה נובע שהיא חד-חד-ערכית ועל. היא נקראת יעילה אם קיים אלגוריתם יעיל שיכול להריץ את $P_{k}(x)$ בזמן פולינומי בהינתן $x$ ו- $k$ וכן קיים אלגוריתם יעיל שיכול לחשב את התמורה ההופכית $P_{k}^{-1}(y)$ בהינתן $y$ ו- $k$ . ההנחה המשתמעת מכאן שאורכי הקלט, הפלט והמפתח זהים אינה בהכרח מדויקת תמיד. למעשה הפלט חייב להיות כאורך הקלט אחרת היא לא תקרא תמורה, אולם המפתח יכול להיות באורך שונה. נהוג לכנות את אורך הקלט והפלט "בלוק" שאורכו הוא $n$ סיביות. וכן $n$ נקרא פרמטר ביטחון.

בדומה לפונקציה פסידו-אקראית, כדי שהתמורה $P_{k}$ תקרא פסידו-אקראית היא צריכה להיות בלתי ניתנת להבחנה מתמורה אקראית באורך זהה. למעשה ההבדל בין פונקציה פסידו-אקראית לבין תמורה פסידו-אקראית אינו גדול כי תמורה ופונקציה באורך זהה ניראות גם ככה דומות ולא ניתן לזהות הבדל ביניהן אלא אם כן מוצאים שני ערכים $x$ ו- $x'$ כך שמתקיים $f(x)=f(x')$ שאז אנחנו יודעים שהיא אינה תמורה. אולם ההסתברות שימצאו שני ערכים כאלה בזמן פולינומי כאשר $n$ גדול, זניחה.

למעשה הטענה הבאה נכונה: אם $P$ היא פרמוטציה פסידו-אקראית אז היא גם פונקציה פסידו-אקראית. אך מפני שבכל תמורה $P_{k}$ מחייבת שתהיה גם פונקציה הופכית $P_{k}^{-1}$ , עובדה זו יוצרת בעיה שלא קיימת בפונקציה פסידו-אקראית, כי כעת צריך לוודא שהתמורה תהיה בטוחה גם אם למבחין גישה לאורקל הפונקציה ההופכית. מעצם ההגדרה של פונקציה פסידו-אקראית לא בהכרח קיימת פונקציה הופכית. אם התמורה $P$ היא בעלת תכונה כזו היא תקרא תמורה פסידו-אקראית חזקה. בניסוח פורמלי:

תהי

P:\{0,1\}^{*}\times \{0,1\}^{*}\longrightarrow \{0,1\}^{*}

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

{\text{negl}}

כך שמתקיים

|\Pr[D^{P_{k}(\cdot ),P_{k}^{-1}(\cdot )}(1^{n})=1]-\Pr[D^{f(\cdot ),f^{-1}(\cdot )}(1^{n})=1]|\leq {\text{negl}}(n)

.

כאשר $k\leftarrow \{0,1\}^{n}$ הוא מפתח שנבחר באקראי בהתפלגות אחידה והפונקציה $f$ נבחרה באקראי מתוך קבוצת כל התמורות האפשריות באורך $n$ סיביות. האינטואיציה מאחורי הביטוי הזה היא שאם לא קיים אלגוריתם הבחנה פולינומי, שמיוצג כאן על ידי D שיכול לזהות לפי הפלט, הבדל כלשהו בין התמורה $P_{k}$ אפילו בהינתן התמורה ההופכית $P_{k}^{-1}$ , לבין תמורה אקראית אמיתית בהתסברות גבוהה משיעור זניח שנקבע על ידי פונקציית הזניחות אז היא נחשבת לתמורה פסידו-אקראית חזקה (מבחינה חישובית).

תמורה בלתי צפויה

תמורה בלתי צפויה היא הגדרה קצת יותר חלשה מתמורה פסידו-אקראית. היריב במקרה של תמורה בלתי צפויה הוא אלגוריתם הסתברותי שמקבל גישה לאורקל לשני הכיוונים, התמורה $P_{k}$ והתמורה ההופכית $P_{k}^{-1}$ . היריב מקבל אתגר $k$ והוא מתבקש לנחש מה יהיה פלט הפונקציה $P_{k}$ . הוא רשאי לבצע סדרה של שאילתות לאורקל למעט שאילתה בנוגע ל- $k$ .

הגדרה פורמלית

אלגוריתם אקראי פולינומי ייקרא תמורה בלתי צפויה אם עבור כל מבחין הסתברותי פולינומי $A$ שלא רשאי להגיש לאורקל שאילתה בנוגע לתחזית עצמה (התמורה), קיימת פונקציית זניחות כך שמתקיים:

\Pr[y=P_{k}(x)|k\leftarrow \{0,1\}^{c(n)};(x,y)\leftarrow A^{P_{k},P_{k}^{-1}}(1^{n})]={\text{negl}}(n)

תמורה פסידו-אקראית וצופן בלוקים

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

לדוגמה, רשת פייסטל היא מבנה קריפטוגרפי פופולרי, שמקבל פונקציה חד-כיוונית לא הפיכה וממנה מייצר תמורה הפיכה עם מפתח. רשת פייסטל היא מבנה איטרטיבי הפועל כדלהלן. הקלט באורך $2n$ סיביות מחולק לשני חצאים $R$ ו- $L$ (חצי ימני וחצי שמאלי בהתאמה) כל אחד באורך $n$ סיביות, בהינתן פונקציה פסידו-אקראית $f$ שמקבלת את $k$ וקלט באורך $n$ ומחזירה פלט פסידו-אקראי באורך $n$ מבנה פייסטל מתבצע כך:

L_{i}=R_{i-1},\ R_{i}=L_{i-1}\oplus f_{i}(k_{i},R_{i-1})

ברור שבמהלך הראשון המבנה המתואר אינו פסידו-אקראי אפילו ש- $f$ פסידו-אקראית כי החצי השמאלי הוא למעשה חצי הקלט הימני ללא שינוי. וכן במהלך השני אפשר להראות שהפלט אינו פסידו-אקראי כי קיים אלגוריתם פולינומי שיכול להבחין בינו לבין פלט אקראי. יש לזכור שבכל מהלך צריך מפתח שונה ובלתי תלוי במפתחות הקודמים. למרבה ההפתעה רשת פייסטל בשלושה מהלכים עם שלושה מפתחות שונים, נחשבת לפסידו-אקראית אך לא פסידו-אקראית חזקה. לעומת זאת הוכח שרשת פייסטל בארבעה מהלכים עם ארבעה מפתחות שונים נחשבת לתמורה פסידו-אקראית חזקה, בהנחה שהפונקציה הפנימית נחשבת פסידו-אקראית^[3].

צריך לזכור שצופן בלוקים כשלעצמו אינו בטוח לשימוש לבד, אלא הוא רק "אבן בניין" שאיתה ניתן לבנות מערכת הצפנה בטוחה. לצורך המחשה, אם משתמשים בצופן בלוקים ישירות במערכת הצפנה, למשל המצפין שולח את $c=P_{k}(m)$ למקבל, כאשר $P_{k}$ הוא צופן בלוקים שמקבל את המפתח $k$ איתו הוא מצפין את $m$ ומחזיר את $c$ (למשל AES). אפשר להוכיח שמערכת כזו לא תהיה עמידה נגד התקפת מוצפן-נבחר, מפני שהצפנה כזו היא דטרמיניסטית באופיה ולכן המתקיף יכול להבחין בקלות אם הוצפנו בלוקים זהים עם אותו מפתח. הבחנה זו חשובה ולא תמיד מושם עליה דגש כראוי. אחת הדרכים להתמודד עם חיסרון זה היא להשתמש בצופן הבלוקים במסגרת מצב הפעלה בטוח. קיימים מצבי הפעלה שונים של צופן בלוקים הכוללים בין היתר הצפנה מאומתת, כשכל אחד מהם מספק ביטחון בדרך שונה ובעל מאפיינים שונים בהתאם לסביבה, מידת האיום ואילוצי יעילות. במערכות הצפנה מודרניות נהוג לשלב אקראיות כדי לעמוד במודלים של ביטחון מחמירים יותר.

ראו גם

הערות שוליים

^ Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography (2nd edition).
^ New Design Criteria for Hash Functions and Block Ciphers.
^ Michael Luby, Charles Rackoff. "How to construct pseudo-random permutations from pseudo-random functions", 1985. [1] [2]

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

24767361תמורה פסאודו-אקראית

[1] Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography (2nd edition).

[2] New Design Criteria for Hash Functions and Block Ciphers.

[3] Michael Luby, Charles Rackoff. "How to construct pseudo-random permutations from pseudo-random functions", 1985. [1] [2]

[1]

[2]

[3]

תמורה פסאודו-אקראית

תוכן עניינים