GGH

הצפנת גולדרייך-גולדווסר-הלוי (בשמה המקוצר GGH^[1]) היא מערכת הצפנת מפתח ציבורי וחתימה דיגיטלית הראשונה שהייתה מבוססת על סריגים, שפותחה ב-1997 על ידי עודד גולדרייך, שפרירה גולדווסר ושי הלוי. הצפנת GGH מתבססת על הקושי המשוער שבפתרון בעיית הווקטור הקרוב ביותר (CVP) בתורת הסריגים והיא מזכירה במקצת את הצפנת מקאליס המבוססת על תורת הקודים. למערכת זו בעיקר חשיבות תאורטית והיא אינה מעשית היות שכדי להתגבר על קריפטואנליזה של הצופן על המפתחות להיות ארוכים מאוד.

פונקציה חד-כיוונית עם דלת מלכודת

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

סריג ובעיית הווקטור הקרוב ביותר

ערך מורחב – הצפנה מבוססת סריג

בהינתן קבוצה של $n$ וקטורים בלתי תלויים מעל $\mathbb {R} ^{n}$ , הסריג (Lattice) $L$ הנפרש על ידי $B=\{\mathbf {b} _{1},\mathbf {b} _{2},...,\mathbf {b} _{n}\}$ הוא קבוצת כל הצירופים הליניאריים האפשריים של הווקטורים $\mathbf {b} _{i}$ עם מקדמים שלמים, כלומר:

L(B)\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \left\{\sum _{i}k_{i}\mathbf {b} _{i}:k_{i}\in \mathbb {Z} {\text{ for all }}i\right\}

כל וקטור נקרא "נקודה" בסריג. נוח לייצג את הסריג באמצעות מטריצה לא סינגולרית (הפיכה) מסדר $n\times n$ שרכיביה הם מספרים ממשיים ועמודותיה הם וקטורי הבסיס $B$ . פרט חשוב בנוגע לסריגים הוא שלכל סריג בסיסים רבים שלהם אותה דטרמיננטה. למעשה, על ידי צירוף ליניארי (שלם) כלשהו של וקטורי הבסיס אפשר להגיע לבסיס אחר של אותו סריג. מזה נובע שבהינתן מטריצה $T$ (שרכיביה שלמים) כך שמתקיים $BT=C$ קיימת מטריצה אחרת $T^{-1}$ כך שמתקיים $CT^{-1}=B$ . תכונה נוספת וחשובה המשמשת בהצפנת GGH היא orthogonality defect (פונקציית אורתוגונליות פגומה) שהיא פונקציה המוגדרת כך:

\textstyle {\text{orth-defect}}(B)\ {\overset {\underset {\mathrm {def} }{}}{=}}\ {\frac {\prod _{i}||\mathbf {b} _{i}||}{|{\text{det}}(B)|}}

כאשר $||\mathbf {b} _{i}||$ הוא הנורמה האוקלידית של העמודה $i$ של $B$ . והיא מספקת כלי מדידה להערכה כמה קרובות עמודות B להיות אורתוגונליות (ניצבות) זו לזו. כאשר עמודות $B$ אורתוגונליות ${\text{orth-defect}}(B)=1$ . בסיס של סריג נחשב לבסיס "טוב" אם פונקציית פגם האורתוגונליות נמוכה, כלומר $B$ אורתוגונלית או "כמעט" אורתוגונלית, כך שהפונקציה האמורה לא גדולה בהרבה מ-1.

בעיית הווקטור הקרוב ביותר היא בעיה קשה בתורת הסריגים שלה השלכות על תורת הקריפטוגרפיה. בהינתן בסיס $B$ של סריג כמתואר לעיל ווקטור כלשהו $\mathbf {v}$ , הבעיה היא למצוא וקטור אחר ב- $L(B)$ שהוא הקרוב ביותר ל- $\mathbf {v}$ בנורמה מסוימת. בעיה זו הוכחה כבעיית NP-קשה. לא ידוע על אלגוריתם שיכול אף למצוא קירוב טוב בפקטור פולינומי ב- $n$ שהוא הממד. בעיה קשורה נוספת היא מציאת בסיס מינימלי (SBP), שגם היא קשה, אם ניתן למצוא בסיס כזה בזמן פולינומי אז אפשר גם לפתור את בעיית הווקטור הקצר ביותר. האלגוריתם הטוב ביותר הידוע כיום הוא LLL אלגוריתם לצמצום בסיס הסריג (lattice basis reduction) והוא אינו יעיל כאשר הסריג בעל ממד גדול. חישוב המפתח הפרטי מתוך המפתח הציבורי שקול לפתרון בעיה זו.

תיאור הצופן

האלגוריתם מורכב משלושה חלקים; הכנה, הצפנה ופענוח כדלהלן: להכנה המקבל בוחר שני בסיסים $B$ ו- $R$ המיוצגים כמטריצות מסדר $n\times n$ כאמור, כאשר $n$ הוא פרמטר ביטחון (למשל $n\geq 200$ ). הבסיס $R$ נבחר באופן אקראי באופן שיהיה בסיס "טוב" כלומר שהפונקציה ${\text{dual-orth-defect}}$ שלו נמוכה והוא משמש כמפתח פרטי ונשמר בסוד. המקבל מפרסם את המפתח הציבורי $B$ שהוא גרסה "מסווית" של המפתח הפרטי. השיטה הישירה להסוות את $R$ היא ערבוב של כל וקטורי $R$ עם צירוף ליניארי של וקטורים אחרים, עם מקדמים בטווח $\{-1,0,1\}$ . נוח לממש זאת באמצעות המכפלה $B=TR$ כאשר $T$ הוא מטריצה אונימודולרית (unimodular) אקראית, כלומר מטריצה ריבועית במספרים שלמים שהדטרמיננטה שלה היא $\pm 1$ . והמקבל שומר גם את $T$ בסוד.

להצפנת המסר $m\in \mathbb {Z} ^{n}$ תחילה השולח ממיר את $m$ בשיטה מוסכמת ובטוחה לנקודה בסריג, נניח הווקטור $\mathbf {v}$ . לאחר מכן השולח מחשב את:

c=\mathbf {v} B+\mathbf {e}

ושולח למקבל את

c

.

כאשר $\mathbf {e}$ הוא "וקטור שגיאה" אקראי קצר, כלומר שמקדמיו הם $\{\sigma ,-\sigma \}$ בהסתברות שווה, עבור $\sigma$ ממשי (כגון $\sigma =3$ ). בחירת וקטור השגיאה בצורה זו גרמה לנקודת תורפה מהותית שאיפשרה התקפה יעילה נגד המערכת. נראה היה שלא ניתן למצוא פתרון יעיל שעוקף את הבעיה ורבים סברו לאור זאת ש-GGH אינה ראויה לשימוש כיום בשל כך. אולם במרוצת השנים נמצאו פתרונות (להלן) והסתבר ש-GGH הוספדה מוקדם מדי.

לצורך הפענוח המקבל משתמש בטכניקת קירוב של Babai (היעילה רק כאשר הבסיס נוח) כדי להפוך את פעולת ההצפנה. דהיינו מייצג את $c$ כצירוף ליניארי של עמודות $R$ , מעגל את המקדמים של צירוף זה לשלמים הקרובים ביותר ומקבל נקודה בסריג. ייצוג הנקודה כצירוף ליניארי של עמודות $B$ הוא הווקטור $\mathbf {v}$ . ליתר דיוק אם $T=B^{-1}R$ היא מטריצה יונימודולרית, המקבל מחשב את $\mathbf {v}$ ואת $\mathbf {e}$ . כך:

\mathbf {v} =TR^{-1}c,\mathbf {e} =c-B\mathbf {v}

. מהנקודה

\mathbf {v}

המקבל יכול לשחזר את המסר

m

.

מדוע זה עובד. היות שהמטריצה $T=B^{-1}R$ היא יונימודולרית, הפונקציה ההפוכה להצפנה היא $\mathbf {v} =TR^{-1}c$ וכן $\mathbf {e} =c-B\mathbf {v}$ . כזכור $c=B\mathbf {v} +\mathbf {e}$ לכן מתקיים:

cR^{-1}=(\mathbf {v} B+\mathbf {e} )R^{-1}=\mathbf {v} TRR^{-1}+\mathbf {e} R^{-1}=\mathbf {v} T+\mathbf {e} R^{-1}

מכפילים את הביטוי האחרון ב- $T^{-1}$ כדי לבודד את $\mathbf {v}$ , ממנו אפשר לחלץ את $m$ . אלגוריתם בּבּאי מאפשר לצמצם את הביטוי $eR^{-1}$ מהמשוואה האמורה בתנאי שהוא מספיק קטן, כלומר הכניסות שלו הם ערכים ממשיים הנמוכים מ- $1/2$ .

בהצעה המקורית, הובאו שתי שיטות להכנת בסיס הסריג $R$ כך שייקרא "טוב". אחת היא לבחור מטריצה אקראית שהכניסות בה הם שלמים קטנים כלומר שהעמודות הן וקטורים בעלי מקדמים בטווח $\{-4,-3,-2,-1,0,1,2,3,4\}$ והאחרת היא לבחור את $R$ כך שמתקיים $R=kI_{n}+E$ כאשר $I_{n}$ היא מטריצת היחידה מסדר $n\times n$ וכן $k>1$ הוא שלם בגודל בינוני ו- $E$ מטריצה אקראית המכילה וקטורים קטנים כמו בקודמת. כמו כן כדי להכין את המטריצה $T$ הוצעו כמה דרכים כדי למנוע מצב שהמקדמים של $B$ יתנפחו לממדים גדולים מדי מה שיגרום להתנפחות הצופן. טווח המסר הוא כל הקטורים ממעלה $n$ עם מקדמים מהצורה $\{-M,-(M-1),...,-1,0,1,M-1,M\}$ עבור $M\in \mathbb {N}$ כלשהו. יש צורך בשיטה בטוחה סמנטית להמרת המסר $m$ לוקטור האמור ולהפך.

חתימה דיגיטלית

אם נתונה מערכת מפתח ציבורי של GGH המתאימה לשריג $L\in \mathbb {Z} ^{n}$ , באופן טבעי סכימת חתימה דיגיטלית תהיה כדלהלן: נתון המסר $m$ והתמצית שלו $H(m)\in \mathbb {Z} ^{n}$ שחושבה על ידי פונקציית גיבוב בטוחה כלשהי, החתימה היא חישוב הנקודה $\mathbf {s}$ בסריג האמור, הקרובה ביותר ל- $H(m)$ . אימות החתימה מתבצע על ידי בדיקה שאכן $\mathbf {s}$ נמצא בסריג כלומר $\mathbf {s} (R)^{-1}\in \mathbb {Z} ^{n}$ וכן שהיא אכן נקודה קרובה כלומר $||\mathbf {s} -H(m)||$ קטן מערך מפרמטר קרבה שנקבע כחלק מתהליך החתימה.

ב-2006 פרסמו עודד רגב ו-Phong Nguyen קריפטואנליזה של חתימת GGH ו-NTRU^[2] שמראה שאפשר לחשוף את המפתח הפרטי בזמן מאוד קצר תוך שימוש ב-400 חתימות בלבד. מסיבה זו חתימת GGH אינה בטוחה לשימוש מהיבט פרקטי.

ביטחון ויעילות

תוצאת צופן GGH מתנפחת באופן משמעותי לעומת המסר המקורי בערך $O(n^{2}{\text{ log }}n)$ . הערכה מדויקת של מידת ההתנפחות תלויה בגודל הכניסות של $B$ שבתורו תלוי בגודל הכניסות של $R$ ו- $T$ . קיימות גרסאות של הצופן שמשפרות את המצב. Micciancio הציע להחליף את המפתח הציבורי $B=TR$ במפתח הציבורי המבוסס על הצורה הנורמלית של הרמיט (HNF) של $R$ שהוא יותר קטן. שיפור נוסף הוא במקום להטמיע את המסר בנקודה בסריג אפשר להטמיעו בווקטור השגיאה $e$ וכן אם עובדים עם מקבילון במקום עם המטריצה מקורית הטקסט המוצפן יהיה קטן משמעותית.

ההתקפות האפשריות נגד מערכת GGH הם:

ניחוש המפתח הפרטי $R$ מתוך המפתח הציבורי $B$ . לצורך כך אפשר להשתמש באלגוריתם LLL על המפתח הציבורי. אם האלגוריתם מצליח מתקבלת המטריצה $B'$ שיכול להיות שתהיה טובה מספיק כדי לפתור את בעיית הווקטור הקצר ואז לשבור את המערכת. כדי למנוע התקפה כזו חובה לבחור בסיס מספיק גדול כך ששימוש באלגוריתם LLL לא יהיה יעיל.
ניסיון לנחש מידע על הטקסט המקורי לאור העובדה שווקטור השגיאה קטן. אם $c=vB+e$ כאשר $e$ הוא וקטור השגיאה אם מקדמים קטנים, אפשר בהתקפת כוח גס לנסות את כל האפשרויות של $e$ . לצורך ההתקפה אפשר תחילה לחשב את $cB^{-1}$ ואז לבדוק עבור כל עמודה אם הנורמה קטנה תמיד. אם כן יש סבירות שהעמודה מייצגת את המקדם המתאים ב- $v$ . כדי למנוע התקפה זו סכימת ההמרה של המסר לנקודה בסריג חייבת להיות בטוחה או שאפשר לרפד את המסר בסכימת ריפוד תחילה.
ניסיון לפתור את בעיית הווקטור הקרוב ביותר בעזרת $B$ באמצעות אלגוריתם ידוע כמו הטכניקה של בבאי. הבעיה כאמור קשה כל עוד הפרמטרים מבטיחים שהסריג אינו מכיל תבנית כלשהי המקלה על פתרון וכן שהוא מספיק גדול.

ב-1999 חוקרים מצאו^[3] בעיות מהותיות בסכמה המקורית שהוצעה על ידי גולדרייך גולדווסר והלוי, שנראה היה שלא ניתן לפתור אותן. ב-2012 הציעו Yoshino ו-Kunihiro פתרון^[4]. בגרסה המשופרת נראה שהבעיות תוקנו. אולם פותחו חלופות מתקדמות יותר כמו גרסאות של NTRU שגם יותר בטוחות וגם מציעות ביצועים אופטימליים ומהוות מתחרים ראויים לאלגוריתמים התקניים כמו RSA ודיפי הלמן.

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

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

יהי $L\in \mathbb {R} ^{2}$ סריג אשר הבסיס שלו הוא המטריצה $B={\begin{pmatrix}17&0\\0&19\end{pmatrix}}$

וכן $T={\begin{pmatrix}2&3\\3&5\end{pmatrix}}$ כך שמתקבל $B=TR={\begin{pmatrix}34&57\\51&95\end{pmatrix}}$ אם המסר הוא הווקטור $v=(2,-5)$ וכן וקטור השגיאה $e=(1,-1)$ כלומר $\sigma =1$ . אז הצפנה היא:

$c=mBv+e=(-186,-362)$

לפענוח המקבל מחשב את:

$cR^{-1}\approx (-10.94,-19.05)$

יוצא ש- $vT=(-11,-19)$ וכן $eB^{-1}\approx (0.06,-0.05)$ . אם מעגלים את התוצאה ל- $(-11,-19)$ אפשר לחלץ את המסר $v=(-11,-19)T^{-1}=(2,-5)$ .

ראו גם

הערות שוליים

^ Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.
^ Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
^ Phong Q. Nguyen. Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.
^ M. Yoshino, N. Kunihiro, Improving GGH Cryptosystem for Large Error Vector. International Symposium on Information Theory and its Applications (2012) 416-420.

[1] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.

[2] Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures

[3] Phong Q. Nguyen. Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.

[4] M. Yoshino, N. Kunihiro, Improving GGH Cryptosystem for Large Error Vector. International Symposium on Information Theory and its Applications (2012) 416-420.

[1]

[2]

[3]

[4]