חתימה דיגיטלית רבין

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

אלגוריתם חתימה דיגיטלית של רבין דומה לאלגוריתם חתימה דיגיטלית RSA ובנוי ממודולוס $\ n=pq$ כאשר $\ p$ ו-$\ q$ הם ראשוניים (גדולים), אולם כאן המעריך הפומבי $\ e$ הוא שלם זוגי קטן $\ e=2$ (בגרסה בסיסית). המפתח הפרטי של החותם הוא צמד הגורמים $\ (p,q)$, המפתח הפומבי הוא $\ n$. החתימה על המסר היא בעצם השורש הריבועי של המסר (לאחר המרתו למספר שלם בדרך מוסכמת) ואילו אימות החתימה הוא הבדיקה שאכן ערך זה הוא שורש ריבועי. הבדיקה האם שלם כלשהו הוא שורש ריבועי מודולו $\ n$ קלה למדי בעוד שהפעולה ההפוכה קרי, מציאת שורש ריבועי מודולו $\ n$ קשה מאוד, אם הגורמים הראשוניים שלו אינם ידועים.

מרחב החתימה של המסר מוגבל לקבוצה $\ Q_{n}$ (קבוצת השאריות הריבועיות מודולו $\ n$). כלומר המסר חייב לייצג מספר שלם כזה שקיים עבורו שורש ריבועי מודולו $\ n$. הבעיה היא שלא כל מסר עונה על דרישה זו, יכול להיות מסר שעבורו יהיה בלתי אפשרי לחשב שורש ריבועי מודולו $\ n$. ניתן להתגבר על בעיה זו על ידי שרשור ערך אקראי קטן כלשהו למסר בתקווה שהתוצאה תהיה מספר שקיים עבורו שורש ריבועי מודולו $\ n$. בממוצע מספר הניסיונות הדרושים עד שיימצא ערך כזה הוא 2. בשל חסרון מהותי זה אלגוריתם רבין הבסיסי המתואר להלן אינו מעשי כל כך. להלן מתוארת גרסה משופרת של אלגוריתם רבין המבוססת על אלגוריתם וויליאמס (H. C. Williams) המבטלת בעיה זו.

בדומה ל-RSA גם אלגוריתם חתימה דיגטלית של רבין מחייב שימוש בפונקציית יתירות בשל קיומה של בעיה מהותית הקרויה Existential forgery, כיוון שכל שלם $\ s\in \mathbb {Z} _{n}^{*}$ הוא חתימה תקפה עבור המסר $\ s^{2}\ {\mbox{mod }}n$, זאת ללא ידיעת המפתח הפרטי של החותם. בשל כך תוקף פונטנציאלי עלול לזייף ערך כלשהו ולטעון כי בידו חתימה תקפה עליו. למרות שלתוקף לא תהיה שליטה מלאה על תוכנו של המסר החתום, עובדה זו מהווה איום בלתי מבוטל.

פירוט האלגוריתם הבסיסי

תהליך הכנה

• החותם מכין מודולוס $\ n=pq$ כאשר $\ p$ ו-$\ q$ הם ראשוניים שונים וגדולים (ראו להלן).
• המפתח הפומבי הוא $\ n$
• המפתח הפרטי הוא הצמד $\ (p,q)$.

תהליך החתימה על המסר m

• מחשבים את $\ {\bar {m}}=R(m)$ (כאשר $\ R$ היא פונקציית יתירות בטוחה כלשהי, ראו להלן)
• מחשבים את השורשים הריבועיים של $\ {\bar {m}}{\mbox{ mod }}n$, התוצאות הן $\ s_{1},s_{2},s_{3},s_{4}$.
• בוחרים אחד מארבעת הערכים האמורים כחתימה תקפה על המסר.

תהליך אימות ושחזור המסר המקורי m

בהינתן המפתח הפומבי $\ n$ והחתימה $\ s$ בודקים כדלהלן:

• מחשבים את $\ {\bar {m}}=s^{2}{\mbox{ mod }}n$.
• בודקים אם $\ {\bar {m}}$ נמצא בטווח המתאים (כלומר נמצא בטווח של פונקציית היתירות).
• משחזרים את המסר $\ m=R^{-1}({\bar {m}})$ (כלומר על ידי הפעלת הפונקציה ההפוכה של פונקציית היתרות $\ R$).

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

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

יהיו הפרמטרים הבסיסיים: $\ p=199$, $\ q=223$, שניהם שקולים ל-$\ 3$ מודולו $\ 4$, ויהיה $\ n=pq=44377$. מפתח החתימה אם כן הוא $\ (199,223)$ מפתח האימות הוא $\ 44377$. כדי לחתום על המסר $\ m=9604$, החותם מחשב את השורשים הרבועיים של $\ 9604$ שהם: $\ s_{1}=98,s_{2}=5673,s_{3}=44279,s_{4}=38704$. החותם בוחר אחד מהם נניח $\ s_{3}=44279$. כדי לאמת את החתימה המאמת מחשב את $\ m'=s^{2}{\mbox{ mod }}n=44279^{2}{\mbox{ mod }}44377=9604$. כיוון ש-$\ m'=m$ החתימה מתקבלת.

בטיחות

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

פונקציית יתירות

כאמור פונקציית יתירות היא מרכיב קריטי באלגוריתם רבין. על כן ישנה חשיבות רבה בבחירת פונקציית יתירות בטוחה ככל האפשר. תקן איזו ISO/IEC 9796 מפרט פונקציה כזו. הרעיון הוא שימוש בפונקציה Shaddow function אשר מבצעת תמורה על שני חלקי כל בית במסר (ארבע סיביות כנגד ארבע סיביות) לפי טבלה קבועה. תוצאת הפונקציה משולבת בין בתי המסר לסירוגין. קיימות מספר שיטות הוספת יתירות עבור חתימה דיגיטלית.

גרסה משופרת של האלגוריתם

בשל החסרון האמור לעיל, פותחה גרסה משופרת של אלגוריתם רבין המבוססת על אלגוריתם וויליאמס, שמאפשרת לבנות את המסרים כך שיענו על הדרישה האמורה באופן דטרמיניסטי, כלומר שלכל מסר אפשרי יהיה שורש ריבועי מודולו $\ n$. גרסה זו הושאלה מגרסת הצפנת מפתח פומבי שהציע לשיפור RSA שלדבריו מספקת בטיחות מוכחת. שיטה זו אומצה בתקן איזו ISO/IEC 9796. הרעיון של וויליאמס הוא שעבור כל שלם $\ x\in Q_{n}$ הערך $\ x^{(n-p-q+5)/8}{\mbox{ mod }}n$ הנו שורש ריבועי של $\ x$ מודולו $\ n$. לכן אם $\ d=x^{(n-p-q+5)/8}$ אזי $\ x^{2d}\equiv x\ ({\mbox{mod }}n)$. אם $\ x$ אינו שארית ריבועית מודולו $\ n$ אזי $\ x^{2d}{\mbox{ mod }}n=n-x$. עובדה זו מאפשרת שיפור אלגוריתם החתימה של רבין כדלהלן.

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

מרחב המסר המיועד לחתימה הוא $\ \{m\in Z_{n}:m\equiv 6\ ({\mbox{mod }}16)\}$ כמו כן $\ m$ חייב להיות קטן מ-$\ (n-6)/16$. כאשר פונקציית היתירות היא: $\ R(m)=16m+6$.

תהליך הכנה

• בוחרים ראשוניים $\ p$ ו-$\ q$ המקיימים $\ p\equiv 3\ ({\mbox{mod }}8)$ וכן $\ q\equiv 7\ ({\mbox{mod }}8)$
• מחשבים את $\ n=pq$.
• המפתח הפומבי הוא $\ n$.
• המפתח הפרטי הוא $\ d=(n-p-q+5)/8$.

תהליך חתימה על המסר m

• מחשבים את $\ {\bar {m}}=R(m)=16m+6$.
• מחשבים את סימן יעקובי $J=\left({\frac {\bar {m}}{n}}\right)$.
• אם $\ J=1$ מחשבים את $\ s={\bar {m}}^{d}{\mbox{ mod }}n$.
• אם $\ J=-1$ מחשבים את $\ s=({\bar {m}}/2)^{d}{\mbox{ mod }}n$.
• החתימה על המסר היא $\ s$.

הערה: מעשית הסיכוי ש-$\ J$ יהיה שווה אפס נמוך ביותר מאחר שמשמעות הדבר היא ש-$\ {\mbox{gcd}}({\bar {m}},n)$ הוא אחד הגורמים הראשוניים של $\ n$.

תהליך אימות החתימה ושחזור המסר המקורי m

• מחשבים את $\ m'=s^{2}{\mbox{ mod }}n$.
• אם $\ m'\equiv 6\ ({\mbox{mod }}8)$ אזי $\ {\bar {m}}=m'$.
• אם $\ m'\equiv 3\ ({\mbox{mod }}8)$ אזי $\ {\bar {m}}=2m'$.
• אם $\ m'\equiv 7\ ({\mbox{mod }}8)$ אזי $\ {\bar {m}}=n-m'$.
• אם $\ m'\equiv 2\ ({\mbox{mod }}8)$ אזי $\ {\bar {m}}=2(n-m')$.
• מוודים ש-$\ {\bar {m}}$ בטווח פונקציית היתירות, אם לא דוחים את החתימה.
• המסר משוחזר על ידי $\ m=R^{-1}({\bar {m}})$ (ההופכית לפונקציית היתירות) כלומר $\ m=({\bar {m}}-6)/16$.

דוגמה במספרים קטנים לאלגוריתם המשופר

יהיו הפרמטרים הבסיסיים: $\ p=227$ וכן $\ q=223$ כאשר שניהם מקיימים את התנאים האמורים לעיל. ויהיה $\ n=pq=50621$. מפתח האימות הוא אם כן $\ 50621$ ומפתח החתימה הוא $\ d=50621-227-223+5/8=6272$. נניח שהמסר המיועד לחתימה הוא $\ m=1148$ ולאחר הפעלת פונקציית היתירות: $\ {\bar {m}}=R(1148)=16\cdot 1148+6=18374$. בחישוב סימן יעקובי מתקבל $\ J=\left({\frac {18374}{50621}}\right)=-1$. החתימה על המסר היא אם כן: $\ s=(18374/2)^{6272}{\mbox{ mod }}50621=11621$. כדי לאמת את החתימה הבודק מחשב את $\ m'=11621^{2}{\mbox{ mod }}50621=41434$, כיוון ש-$\ m'\equiv 2\ ({\mbox{mod }}8)$ התוצאה תהיה $\ {\bar {m}}=2\cdot (50621-41434)=18374$, הפעלת הפונקציה ההופכית נותנת $\ m'=R^{-1}({\bar {m}})=(18374-6)/16=1148$, כיוון ש-$\ m'=m$ החתימה מתקבלת.

בטיחות

האלגוריתם המשופר מציע יתרון ברור על פני האלגוריתם המקורי בכך שהוא מציע דרך דטרמיניסטית לבניית המסר באופן שתמיד יהיה שורש ריבועי עבורו אולם עם אלגוריתם זה אין לחתום על מסר שלו סימן יעקובי $\ -1$ מאחר שזה מאפשר פירוק המודולוס לגורמיו. בטיחות אלגוריתם זה זהה לגרסה הבסיסית, בכך שניתן להוכיח כי הוא עמיד כפירוק לגורמים. וכמו בגרסה הבסיסית גם אלגוריתם זה סובל מ-Existential forgery כלומר קל למצוא $\ s$ כלשהו אשר אחד מהערכים $\ s^{2},n-s^{2},2s^{2},2(n-s^{2})$ מודולו $\ n$ שקול ל-$\ 6$ מודולו $\ 16$ ואז $\ s$ יהיה חתימה תקפה עבור $\ m=s^{2}{\mbox{ mod }}n$.

הגרסה המשופרת של אלגוריתם רבין מצריכה חישוב סימן יעקובי מלבד חישוב שורש ריבועי מודולו $\ n$ ועל כן יעילה מעט פחות מהאלגוריתם הבסיסי. אולם מאפשרת שימוש במעריך שונה מ-2 בתנאי ש-$\ {\mbox{gcd}}(e,(p-1)(q-1)/4)=1$ שאז בדומה ל-RSA העלאה בחזקת $\ e$ תהיה תמורה ב-$\ Q_{n}$ מה שמאפשר שחזור הערך המקורי בהינתן $\ d$.

ראו גם

• חתימה דיגיטלית
• הצפנת רבין

קישורים חיצוניים

• פונקציית הצפנה וחתימה דיגיטלית עמידה כפירוק לגורמים, פרופסור מיכאל רבין, המכון הטכנולוגי של מסצ'וסטס, 1979.
• הספר Handbook of Applied Cryptography, לשימוש פרטי בלבד.
• H.C. Williams, A modification of the RSA public-key encryption procedure, IEEE Trans. Information Theory, IT-26, 726-729 (1980).