חתימת למפורט

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

מוטיבציה

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

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

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

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

$f:\{0,1\}^{n}\rightarrow \{0,1\}^{n}$

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

הפונקציה $f$ יכולה להיות כל צופן בלוקים כמו AES או פונקציית גיבוב תיקנית כמו SHA-2 או SHA-3 שמעצם הגדרתם הם מועמדים טובים לפונקציה חד-כיוונית (אם כי לא מוכחים). אם צופן הבלוקים אינו חד-כיווני, אין להשתמש בו בכל מקרה.

הכנה

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

$X=(x_{n-1}[0],x_{n-1}[1],...,x_{1}[0],x_{1}[1],x_{0}[0],x_{0}[1])\in _{R}\{0,1\}^{(n,2n)}$

אפשר להתייחס ל-$X$ כאל טבלה או מטריצה בינארית בגודל $n\times 2n$ כניסות. להכנת מפתח האימות הציבורי הוא מחשב את:

$Y=(y_{n-1}[0],y_{n-1}[1],...,y_{1}[0],y_{1}[1],y_{0}[0],y_{0}[1])\in \{0,1\}^{(n,2n)}$

כך ש-$y_{i}[j]=f(x_{i}[j])$ כאשר $0\leq i\leq n-1$ וכן $j\in \{0,1\}$. במילים אחרות עבור כל כניסה ב-$X$ הוא מחשב את הפונקציה החד-כיוונית שלה ואת התוצאה מציב בכניסה המתאימה ב-$Y$. לכן לצורך הכנת החתימה החותם צריך לבצע בסך הכול $2n$ הפעלות של הפונקציה $f$ ואורך המפתחות $X$ ו-$Y$ כל אחד הוא $n\times 2n$ סיביות. את המפתח הציבורי הוא רושם אצל צד שלישי באופן כזה שכל אחד יוכל להשתכנע שהוא הבעלים.

חתימה

אם נתון המסמך $D$ באורך שרירותי עליו רוצים לחתום, מקובל לחתום על תמצית המסמך שהיא הרבה יותר קצרה במקום על המסמך עצמו. לצורך תיאור חתימת למפורט נניח שנתונה פונקציית גיבוב כלשהי $g$ (כמו SHA-2) המפיקה מהמסמך תמצית באורך $n$ סיביות $d=g(D)$. כעת $d$ היא מחרוזת בינארית באורך $n$ סיביות $(d_{n-1},...,d_{0})$. החתימה הדיגיטלית על תמצית המסמך היא:

$\sigma =(x_{n-1}[d_{n-1}],...,x_{1}[d_{1}],x_{0}[d_{0}])\in \{0,1\}^{(n,n)}$

$\sigma$ היא רצף של $n$ מחרוזות בינאריות כל אחת באורך $n$ סיביות. במילים אחרות החותם חושף בפני המוודא את המפתחות הסודיים מהטבלה $X$ המתאימים לסיביות של $d$. עבור כל זוג ערכים $(x_{i}[0],x_{i}[1])$ בוחרים אחד מהם לפי ערכה של הסיבית המתאימה $d_{i}$.

אימות

תחילה ההנחה היא שהמאמת קיבל לידיו בדרך בטוחה את המפתח הציבורי $Y$ של החותם באופן שניתן להוכיח את בעלותו (כמו באמצעות צד שלישי). כדי לוודא שהחתימה $\sigma$ על התמצית $d$ תקפה הוא מחשב את:

$(f(\sigma _{n-1}),...,f(\sigma _{0}))=(y_{n-1}[d_{n-1}],...,y_{0}[d_{0}])$.

במילים, הוא מחשב את כל הפונקציות $f$ של ערכי $\sigma _{i}$ ומשווה עם ערכי המפתח הציבורי המתאימים $y_{i}$. אם כולם זהים המשמעות היא שהחתימה אמיתית. אחרת ייתכן שהמסמך השתנה או שהחתימה מזויפת. תהליך אימות החתימה דורש $n$ הפעלות של הפונקציה $f$. לכל מי שאינו מכיר את המפתח הפרטי $X$ יהיה מאוד קשה לחשב את החתימה על מסמך כלשהו ולטעון שהמסמך נחתם על ידי החותם הלגטימי, כלומר לזייף את החתימה. כי עבור כל סיבית עליו לחשב את המפתח הפרטי $X_{i}$ של החותם המתאים למפתח האימות הציבורי $Y_{i}$, שזה בעצם לחשב את הפונקציה ההופכית של $f$ ומעצם ההגדרה זו פעולה קשה.

קל לראות שכדי לאמת את החתימה החותם חושף את המפתחות $X_{i}[j]$ המתאימים לסיביות המסר. אם החותם השתמש באותו מפתח כדי לחתום על מסרים נוספים, המידע שהצטבר בידי המאמת מאפשר לו לחתום על מסמך אחר שנגזר מהמסמכים החתומים שקיבל, גם אם המסמך לא בעל משמעות כלשהי. יוצא שהמאמת הצליח לזייף חתימה על מסמך שהחותם הלגיטמי לא חתם עליו. מסיבה זו אסור לחתום על מסמכים נוספים עם אותו מפתח.

דוגמה

נתון $n=3$ ולמען הפשטות נניח שהפונקציה $f:\{0,1\}^{3}\rightarrow \{0,1\}^{3}$ מקבלת את $x$ באורך 3 סיביות ומחזירה את $x+1$ מודולו 8 (המודולו מבטיח שהתוצאה תישאר מספר שהייצוג הבינארי שלו באורך שלוש סיביות). ברור שהפונקציה הזו אינה בטוחה לשימוש כי קל להפוך אותה, היא מובאת כאן רק לשם המחשה. במציאות משתמשים בפונקציה חד-כיוונית קריפטוגרפית. וכן נתונה תמצית המסר $d=(1,0,1)$. נניח שהחותם בחר את המפתח הפרטי:

$X=(x_{2}[0],x_{2}[1],x_{1}[0],x_{1}[1],x_{0}[0],x_{0}[1])={\begin{pmatrix}1&0&0&1&1&0\\1&0&1&1&0&1\\1&0&1&0&1&0\end{pmatrix}}\in \{0,1\}^{(3,6)}$

כל זוג מפתחות $x_{i}[0],x_{i}[1]$ מיוצג על ידי זוג עמודות, למשל $x_{1}[0]=(0,1,1)=3,x_{1}[1]=(1,1,0)=6$. כעת הוא מחשב את המפתח הציבורי:

$Y=(y_{2}[0],y_{2}[1],y_{1}[0],y_{1}[1],y_{0}[0],y_{0}[1])={\begin{pmatrix}0&0&1&1&1&0\\0&0&0&1&1&1\\0&1&0&1&0&1\end{pmatrix}}\in \{0,1\}^{(3,6)}$

למשל המפתח הפרטי $x_{2}[0]=(1,1,1)$ שהוא 7 בבסיס עשרוני. לכן המפתח הציבורי המקביל הוא $y_{2}[0]=f(7)=7+1{\text{ mod }}8=(0,0,0)$.

החתימה על $d=(d_{2},d_{1},d_{0})=(1,0,1)$ היא:

$\sigma =(\sigma _{2},\sigma _{1},\sigma _{0})=(x_{2}[1],x_{1}[0],x_{0}[1])={\begin{pmatrix}0&0&0\\0&1&1\\0&1&0\end{pmatrix}}\in \{0,1\}^{(3,3)}$

כלומר החותם חושף את המפתחות הפרטיים (עמודות של $X$) המתאימים לערכי המסר, במקרה זה מימין לשמאל נבחרו העמודה הראשונה, הרביעית והחמישית בהתאמה. כדי לאמת את החתימה $\sigma$ המאמת משתמש במפתח הציבורי $Y$. למשל החתימה השלישית שקיבל היא $\sigma _{2}=x_{2}[d_{2}]=(0,0,0)$ וכן $d_{2}=1$. מה שנותר לו לבדוק שאכן מתקיים:

$y_{2}[d_{2}]=f(x_{2}[d_{2}])=y_{2}[1]$ ואכן

$f(x_{2}[1])=(0,0,0)+(0,0,1){\text{ mod }}8=(0,0,1)$.

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

לפי דוגמה זו נניח שהחותם חתם עם אותו מפתח על תמצית שני מסמכים שונים $d_{1}=(1,0,1)$ ו-$d_{2}=(1,1,0)$ כעת בידי המאמת המפתחות $x_{2}[1],x_{1}[0],x_{1}[1],x_{0}[0],x_{0}[1]$ אותם הוא השיג משילוב המידע משתי החתימות. כעת הוא יכול להשתמש במידע זה כדי לחתום על תמצית של מסמך אחר נניח $d_{3}=(1,1,1)$ והחתימה תהיה לגיטימית כי בידיו למעשה מספיק מפתחות כדי לשכנע אחרים שהמסמך חתום על ידי הבעלים של $X$ בעוד שלמעשה הוא החותם. אולם יש לשים לב שהוא אינו יכול לחתום על תמצית מסמך $d=(0,0,1)$ כי חסר לו הערך $x_{2}[0]$ אותו לא קיבל מהחותם הלגיטימי. אם ברצונו לזייף חתימה על המסמך האמור עליו לחשב את $x_{2}[0]$ מתוך $y_{2}[0]$ שבידו כלומר להפוך את הפונקציה החד כיוונית, כל עוד היא בטוחה הדבר לא יעלה בידו. כלומר התוקף יכול לזייף חתימה רק עבור מסמכים מסוימים ולא עבור כל מסמך שירצה. אפשר לעקוף בעיה זו על ידי הוספת בדיקת זוגיות.

גרסת וינטרניץ

רוברט וינטרניץ (Robert Steven Winternitz) הציע לקצר את מפתחות החתימה של אלגוריתם למפורט באופן משמעותי על חשבון עלייה בסיבוכיות זמן. הרעיון הוא לחתום על מספר סיביות של תמצית המסר בבת אחת. ההצעה של וינטרניץ הובאה לראשונה בתזה של רלף מרקל והיא פועלת כדלהלן:

נתון פרמטר ביטחון $n$ ופונקציה חד כיוונית $f$ בדיוק כמו בחתימת למפורט, בנוסף נתון פרמטר $w\geq 2$ המייצג את מספר הסיביות שאפשר לחתום עליהן בו-זמנית ושלושה פרמטרים נוספים $t,t_{1},t_{2}$ כך שמתקיים:

$t_{1}=\left\lceil {\frac {n}{w}}\right\rceil ,t_{2}=\left\lceil {\frac {\lfloor {\text{log}}_{2}\ t_{1}\rfloor }{w}}\right\rceil ,t=t_{1}+t_{2}$.

מפתח החתימה הוא:

$X=(x_{t-1},...,x_{1},x_{0})\in _{R}\{0,1\}^{(n,t)}$

כלומר המפתח הפרטי מורכב מ-$t$ מחרוזות אקראיות באורך $n$ סיביות. מפתח האימות הציבורי הוא:

$Y=(y_{t-1},...,y_{1},y_{0})\in \{0,1\}^{(n,t)}$, באופן כזה שעבור כל ערכי $x_{i}$ הערך המקביל הוא $y_{i}=f^{2^{w}-1}(x_{i})$.

שים לב שבניגוד לחתימת למפורט כאן הפונקציה $f$ מופעלת באופן רקורסיבי (הפונקציה מופעלת שוב ושוב על התוצאה שלה) $2^{w}-1$ פעמים עבור כל $x_{i}$ ובסך הכול מופעלת $t(2^{w}-1)$ פעמים. הרווח כאן הוא שהמפתחות $X$ ו-$Y$ קצרים יותר, ליתר דיוק באורך $t\cdot n$ סיביות כל אחד. אם $t$ קטן הושג כאן שיפור משמעותי לעומת $n\cdot 2n$ סיביות בחתימת למפורט.

תהליך החתימה

כמו בתהליך ההכנה לעיל, נתונה תמצית המסר $d=g(M)=(d_{n-1},...,d_{1},d_{0})$ באורך $n$ סיביות. תחילה מרפדים את $d$ באפסים מובילים לפי הצורך כדי שאורך המחרוזת יתחלק ב-$w$ ומחלקים את התוצאה ל-$t_{1}$ מחרוזות ($b_{t-1},...,b_{t-t_{1}}$) באורך $w$ סיביות כל אחת. מתייחסים למחרוזות $b_{i}$ כאל מספרים שלמים בטווח $\{0,1,...,2^{w}-1\}$ ומחשבים ספרת ביקורת כך:

$c=\sum _{i=t-t_{1}}^{t-1}(2^{w}-b_{i})$.

היות ש-$c\leq t_{1}2^{w}$ אורך הייצוג הבינארי של השלם $c$ אינו עולה על $\lfloor \log _{2}t_{1}\rfloor +w+1$ סיביות. מוסיפים ל-$c$ אפסים מובילים כנדרש כדי להשלימו למחרוזת באורך $t_{2}$ כניסות באורך $w$ סיביות כל אחת $b_{t_{2}-1},...,b_{0}$. המחרוזת המורחבת המתקבלת משרשור המחרוזות $d$ ו-$c$ יחד, מומרת למערך שלמים $b=b_{t-1},...,b_{t-t_{1}},b_{t_{2}-1},...,b_{0}$ המכיל $t_{1}+t_{2}$ מספרים באורך $w$ סיביות כל אחד. לבסוף החתימה היא:

$\sigma =(f^{b_{t-1}}(x_{t-1}),...,f^{b_{1}}(x_{1}),f^{b_{0}}(x_{0}))$.

כלומר על כל $x_{i}$ מפעילים את הפונקציה $f$ ברקורסיה $b_{i}$ פעמים. במקרה הגרוע כגון אם המסר מכיל מחרוזת של אחדים, הכנת החתימה דורשת $t(2^{w}-1)$ הפעלות של הפונקציה $f$ ואורך החתימה הוא $t\cdot n$ סיביות.

אימות החתימה

כאשר המאמת מקבל את תמצית המסמך $d$ והחתימה $\sigma$ תחילה מכין את מערך השלמים $b=b_{t-1},...,b_{0}$ בדיוק כמו בהתליך החתימה ואז בודק אם מתקיים:

$(f^{2^{w}-1-b_{t-1}}(\sigma _{n-1}),...,f^{2^{w}-1-b_{1}}(\sigma _{1}),f^{2^{w}-1-b_{0}}(\sigma _{0}))=(y_{n-1},...,y_{1},y_{0})$.

ביתר פירוט, היות שאם החתימה תקפה מתקיים $\sigma _{i}=f^{b_{i}}(x_{i})$ מזה נובע ש-$f^{2^{w}-1-b_{i}}(\sigma _{i})=f^{2^{w}-1}(x_{i})=y_{i}$. לדוגמה אם $w=4$ מפתח האימות $Y_{i}$ הופק על ידי קריאה רקורסיבית לפונקציה $f$ בסך הכול $2^{4}-1=15$ פעמים. כעת אם $b_{i}=5$ החתימה על $x_{i}$ היא $\sigma _{i}=f^{b_{i}}(x_{i})=f^{5}(x_{i})$ מזה נובע ש-$f^{2^{4}-1-b_{i}}(\sigma _{i})=f^{10}(f^{5}(x))=f^{15}(x_{i})=y_{i}$.

סיבוכיות האימות זהה לסיבוכיות החתימה.

דוגמה במספרים קטנים

נניח שנקבעו הפרמטרים הבאים: $n=3,w=2,t_{1}=2,t_{2}=2,t=4$. נתונה הפונקציה החד כיוונית $f:\{0,1\}^{3}\rightarrow \{0,1\}^{3}$ המחזירה עבור $x$ את $(x+1)$ מודולו $8$. נניח שהחותם בחר את המפתח:

$X=(x_{3},x_{2},x_{1},x_{0})={\begin{pmatrix}1&0&0&1\\1&0&1&1\\1&0&1&0\end{pmatrix}}\in \{0,1\}^{(3,4)}$

חישוב המפתח הציבורי יהיה:

$Y=(y_{3},y_{2},y_{1},y_{0})={\begin{pmatrix}0&0&1&0\\1&1&1&0\\0&1&0&1\end{pmatrix}}\in \{0,1\}^{(3,4)}$

אם נתונה תמצית המסמך $d=(d_{2},d_{1},d_{0})=(1,0,0)$ תחילה מוסיפים אפס בראש המחרוזת (משמאל) ומקבלים מחרוזת באורך 4 סיביות המחולקת לשני בלוקים באורך $w=2$ כדלהלן:

$d=01\ \|\ 00$

ספרת הביקורת לפי הנוסחה לעיל היא $c=(4-1)+4=7$ שהוא "111" בייצוג בינארי. את המחרוזת הזו מרפדים באפס מוביל ומתקבלת מחרוזת באורך 4 סיביות המחולקת לשני בלוקים:

$c=01\ \|\ 11$

כעת ממירים את ארבעת הבלוקים שהתקבלו למערך $b$ באורך 4 כניסות כאשר כל כניסה מכילה מספר שלם בין 0 ל-3 ומתקבל:

$b=(b_{3},b_{2},b_{1},b_{0})=(01\ \|\ 00\ \|\ 01\ \|\ 11)=(1,0,1,3)$

את החתימה מחשבים על ידי הפעלה של הפונקציה $f$ על כל $x_{i}$ במספר פעמים לפי הערך $b_{i}$. כלומר החתימה היא:

$\sigma =(\sigma _{3},\sigma _{2},\sigma _{1},\sigma _{0})=(f(x_{3}),x_{2},f(x_{1}),f^{3}(x_{0}))={\begin{pmatrix}0&0&1&1\\0&0&0&1\\0&0&0&1\end{pmatrix}}\in \{0,1\}^{(3,4)}$

(הערה: אם $b_{i}=0$ הפירוש הוא שהפונקציה $f$ אינה מופעלת כלל, במקום זאת מעתיקים את $x_{i}$ כמו שהוא). לאימות החתימה בודקים שמתקיים:

$(f^{2}(\sigma _{3}),f^{3}(\sigma _{2}),f^{2}(\sigma _{1}),\sigma _{3})={\begin{pmatrix}0&0&1&0\\1&1&1&0\\0&1&0&1\end{pmatrix}}\in \{0,1\}^{(3,4)}$.

למשל היות ש-$b_{3}=1$ בדיקת החתימה $\sigma _{3}$ מתבצעת על ידי חישוב הפונקציה $f$ שלה בדיוק $2^{w}-1-b_{3}=2$ פעמים. לכן $f^{2}(\sigma _{3})=y_{3}$.

בדומה לחתימת למפורט הבסיסית גם כאן אם החותם ישתמש באותו מפתח כדי לחתום על מסמכים נוספים נניח למשל שהוא חתם על תמצית המסמך $d_{1}=(1,0,0)$, $d_{2}=(1,1,1)$ לכן לפי הדוגמה המובאת החתימות שהצטברו בידי המאמת הן: $f(x_{3}),f^{3}(x_{2}),x_{2},f(x_{1}),f^{3}(x_{0}),x_{0}$. עם חתימות אילו הוא יכול לחתום על מסמך $d_{3}=(1,1,0)$. כלומר תוקף פוטנציאלי שמקבל מספר מרובה של חתימות על מסמכים שונים יכול להפיק חתימה שתראה אותנטית על מסמך אחר, גם אם לא בהכרח מסמך בעל משמעות כלשהי. בשל עובדה זו אין לחתום על מסמכים נוספים עם אותו מפתח.

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

ראו גם

• עץ מרקל
• חתימה דיגיטלית
• פונקציית גיבוב קריפטוגרפית