כאשר formula_15 הוא הנורמה האוקלידית של העמודה formula_16 של formula_1. והיא מספקת כלי מדידה להערכה כמה קרובות עמודות B להיות אורתוגונליות (ניצבות) זו לזו. כאשר עמודות formula_1 אורתוגונליות formula_19. בסיס של סריג נחשב לבסיס "טוב" אם פונקציית פגם האורתוגונליות נמוכה, כלומר formula_1 אורתוגונלית או "כמעט" אורתוגונלית, כך שהפונקציה האמורה לא גדולה בהרבה מ-1.
בעיית הווקטור הקרוב ביותר היא בעיה קשה בתורת הסריגים שלה השלכות על תורת הקריפטוגרפיה. בהינתן בסיס formula_1 של סריג כמתואר לעיל ווקטור כלשהו formula_22, הבעיה היא למצוא וקטור אחר ב-formula_23 שהוא הקרוב ביותר ל-formula_22 בנורמה מסוימת. בעיה זו הוכחה כבעיית NP-קשה. לא ידוע על אלגוריתם שיכול אף למצוא קירוב טוב בפקטור פולינומי ב-formula_2 שהוא הממד. בעיה קשורה נוספת היא מציאת בסיס מינימלי (SBP), שגם היא קשה, אם ניתן למצוא בסיס כזה בזמן פולינומי אז אפשר גם לפתור את בעיית הווקטור הקצר ביותר. האלגוריתם הטוב ביותר הידוע כיום הוא LLL אלגוריתם לצמצום בסיס הסריג (lattice basis reduction) והוא אינו יעיל כאשר הסריג בעל ממד גדול. חישוב המפתח הפרטי מתוך המפתח הציבורי שקול לפתרון בעיה זו.
תיאור הצופן.
האלגוריתם מורכב משלושה חלקים; הכנה, הצפנה ופענוח כדלהלן:
להכנה המקבל בוחר שני בסיסים formula_1 ו-formula_27 המיוצגים כמטריצות מסדר formula_28 כאמור, כאשר formula_2 הוא פרמטר ביטחון (למשל formula_30). הבסיס formula_27 נבחר באופן אקראי באופן שיהיה בסיס "טוב" כלומר שהפונקציה formula_32 שלו נמוכה והוא משמש כמפתח פרטי ונשמר בסוד. המקבל מפרסם את המפתח הציבורי formula_1 שהוא גרסה "מסווית" של המפתח הפרטי. השיטה הישירה להסוות את formula_27 היא ערבוב של כל וקטורי formula_27 עם צירוף ליניארי של וקטורים אחרים, עם מקדמים בטווח formula_36. נוח לממש זאת באמצעות המכפלה formula_37 כאשר formula_10 הוא מטריצה אונימודולרית (unimodular) אקראית, כלומר מטריצה ריבועית במספרים שלמים שהדטרמיננטה שלה היא formula_39. והמקבל שומר גם את formula_10 בסוד.
להצפנת המסר formula_41 תחילה השולח ממיר את formula_42 בשיטה מוסכמת ובטוחה לנקודה בסריג, נניח הווקטור formula_22. לאחר מכן השולח מחשב את:
כאשר formula_46 הוא "וקטור שגיאה" אקראי קצר, כלומר שמקדמיו הם formula_47 בהסתברות שווה, עבור formula_48 ממשי (כגון formula_49). בחירת וקטור השגיאה בצורה זו גרמה לנקודת תורפה מהותית שאיפשרה התקפה יעילה נגד המערכת. נראה היה שלא ניתן למצוא פתרון יעיל שעוקף את הבעיה ורבים סברו לאור זאת ש-GGH אינה ראויה לשימוש כיום בשל כך. אולם במרוצת השנים נמצאו פתרונות (להלן) והסתבר ש-GGH הוספדה מוקדם מדי.
לצורך הפענוח המקבל משתמש בטכניקת קירוב של Babai (היעילה רק כאשר הבסיס נוח) כדי להפוך את פעולת ההצפנה. דהיינו מייצג את formula_45 כצירוף ליניארי של עמודות formula_27, מעגל את המקדמים של צירוף זה לשלמים הקרובים ביותר ומקבל נקודה בסריג. ייצוג הנקודה כצירוף ליניארי של עמודות formula_1 הוא הווקטור formula_22. ליתר דיוק אם formula_54 היא מטריצה יונימודולרית, המקבל מחשב את formula_22 ואת formula_46. כך:
מדוע זה עובד. היות שהמטריצה formula_60 היא יונימודולרית, הפונקציה ההפוכה להצפנה היא formula_61 וכן formula_62. כזכור formula_63 לכן מתקיים:
מכפילים את הביטוי האחרון ב-formula_12 כדי לבודד את formula_22, ממנו אפשר לחלץ את formula_42.
אלגוריתם בּבּאי מאפשר לצמצם את הביטוי formula_68 מהמשוואה האמורה בתנאי שהוא מספיק קטן, כלומר הכניסות שלו הם ערכים ממשיים הנמוכים מ-formula_69.
בהצעה המקורית, הובאו שתי שיטות להכנת בסיס הסריג formula_27 כך שייקרא "טוב". אחת היא לבחור מטריצה אקראית שהכניסות בה הם שלמים קטנים כלומר שהעמודות הן וקטורים בעלי מקדמים בטווח formula_71 והאחרת היא לבחור את formula_27 כך שמתקיים formula_73 כאשר formula_74 היא מטריצת היחידה מסדר formula_28 וכן formula_76 הוא שלם בגודל בינוני ו-formula_77 מטריצה אקראית המכילה וקטורים קטנים כמו בקודמת. כמו כן כדי להכין את המטריצה formula_10 הוצעו כמה דרכים כדי למנוע מצב שהמקדמים של formula_1 יתנפחו לממדים גדולים מדי מה שיגרום להתנפחות הצופן. טווח המסר הוא כל הקטורים ממעלה formula_2 עם מקדמים מהצורה formula_81 עבור formula_82 כלשהו. יש צורך בשיטה בטוחה סמנטית להמרת המסר formula_42 לוקטור האמור ולהפך.
חתימה דיגיטלית.
אם נתונה מערכת מפתח ציבורי של GGH המתאימה לשריג formula_84, באופן טבעי סכימת חתימה דיגיטלית תהיה כדלהלן:
נתון המסר formula_42 והתמצית שלו formula_86 שחושבה על ידי פונקציית גיבוב בטוחה כלשהי, החתימה היא חישוב הנקודה formula_87 בסריג האמור, הקרובה ביותר ל-formula_88. אימות החתימה מתבצע על ידי בדיקה שאכן formula_87 נמצא בסריג כלומר formula_90 וכן שהיא אכן נקודה קרובה כלומר formula_91 קטן מערך מפרמטר קרבה שנקבע כחלק מתהליך החתימה.
ב-2006 פרסמו עודד רגב ו-Phong Nguyen קריפטואנליזה של חתימת GGH ו-NTRU שמראה שאפשר לחשוף את המפתח הפרטי בזמן מאוד קצר תוך שימוש ב-400 חתימות בלבד. מסיבה זו חתימת GGH אינה בטוחה לשימוש מהיבט פרקטי.
ביטחון ויעילות.
תוצאת צופן GGH מתנפחת באופן משמעותי לעומת המסר המקורי בערך formula_92. הערכה מדויקת של מידת ההתנפחות תלויה בגודל הכניסות של formula_1 שבתורו תלוי בגודל הכניסות של formula_27 ו-formula_10. קיימות גרסאות של הצופן שמשפרות את המצב. Micciancio הציע להחליף את המפתח הציבורי formula_37 במפתח הציבורי המבוסס על הצורה הנורמלית של הרמיט (HNF) של formula_27 שהוא יותר קטן. שיפור נוסף הוא במקום להטמיע את המסר בנקודה בסריג אפשר להטמיעו בווקטור השגיאה formula_98 וכן אם עובדים עם מקבילון במקום עם המטריצה מקורית הטקסט המוצפן יהיה קטן משמעותית.
ההתקפות האפשריות נגד מערכת GGH הם:
ב-1999 חוקרים מצאו בעיות מהותיות בסכמה המקורית שהוצעה על ידי גולדרייך גולדווסר והלוי, שנראה היה שלא ניתן לפתור אותן. ב-2012 הציעו Yoshino ו-Kunihiro פתרון. בגרסה המשופרת נראה שהבעיות תוקנו. אולם פותחו חלופות מתקדמות יותר כמו גרסאות של NTRU שגם יותר בטוחות וגם מציעות ביצועים אופטימליים ומהוות מתחרים ראויים לאלגוריתמים התקניים כמו RSA ודיפי הלמן.
האטרקטיביות של שיטה זו ונגזרותיה, שמוצאת היום עניין רב מצד האקדמיה, היא השערת העמידות נגד קריפטואנליזה קוונטית. להערכת מומחים שיטות מפתח ציבורי כמו RSA ודיפי הלמן עומדות לצאת משימוש כאשר מחשבים קוונטיים כלליים בקנה מידה גדול יהיו זמינים. וההערכות הן שמדובר על סדר גודל של כחמש-עשרה שנה. מסיבה זו האקדמיה נמצאת בחיפוש נמרץ אחר שיטות מפתח ציבורי שתהיינה עמידות נוכח האיום הממשמש ובא. הוכח שכדי ש-GGH תהיה בטוחה נגד קריפטואנליזה עם אלגוריתם LLL אורך המפתחות צריך להיות עצום, מסיבה זו האלגוריתם אינו מתאים לשימוש מעשי בקנה מידה מסחרי.
דוגמה במספרים קטנים.
יהי formula_108 סריג אשר הבסיס שלו הוא המטריצה formula_109
וכן formula_110 כך שמתקבל formula_111
אם המסר הוא הווקטור formula_112 וכן וקטור השגיאה formula_113 כלומר formula_114. אז הצפנה היא:
formula_115
לפענוח המקבל מחשב את:
formula_116
יוצא ש-formula_117 וכן formula_118. אם מעגלים את התוצאה ל-formula_119 אפשר לחלץ את המסר formula_120.
מיקה
אוגיסט הירשאואר
גנרל של דיוויזיה אנדרה אוגיסט אדוורד הירשאואר (בצרפתית: André Auguste Édouard Hirschauer; 16 ביוני 1857 – 27 בדצמבר 1943) היה מפקד בכיר בצבא צרפת במלחמת העולם הראשונה.
ביוגרפיה.
תחילת דרכו.
הירשאואר נולד ב-16 ביוני 1857 בעיר סינט-אבול שבקיסרות הצרפתית השנייה. בשנת 1871 בעקבות מלחמת צרפת–פרוסיה, סופחה העיר לקיסרות הגרמנית, ומכיוון שמשפחתו בחרה לשמור על אזרחותה הצרפתית, היא אולצה לעקור לקאלה. בשנת 1874 התגייס לצבא צרפת, ולמד באקול פוליטקניק. הוא שרת באלג'יריה בשנת 1881, וב-1 באפריל 1904 הוא מונה למפקד הראשון של בטליון ההנדסה ה-25. הוא היה אחד מאבות חיל האוויר הצרפתי. במהלך פרשת דרייפוס, הוא היה מהקצינים שהאמינו באשמתו של אלפרד דרייפוס, ואף הסכים להעיד נגדו במשפט הערעור.
מלחמת העולם הראשונה.
עם פרוץ מלחמת העולם הראשונה בשנת 1914 הועלה הירשאואר לדרגת גנרל של דיוויזיה, והיה לסגנו של ז'וזף גליאני. בתחילת המלחמה הוא מילא בצבא תפקידי מטה, אולם בסופו של דבר התקבלו הפצרותיו לצאת לחזית, וב-31 בדצמבר של אותה שנה הוא קיבל פיקוד על הדיוויזיה ה-63. הוא פיקד על הדיוויזיה במהלך קרב האורסק ובקרב שמפאן השני. ב-20 ביוני 1916 קיבל פיקוד על הקורפוס ה-18, ופיקד עליו עד 22 באוגוסט 1917 עת קיבל פיקוד על הקורפוס ה-9. הוא לקח חלק בקרב ורדן.
ב-11 בדצמבר 1917 הוא קיבל פיקוד על הארמייה השנייה, ופיקד עליה עד 22 בנובמבר 1918.
אחריתו.
לאחר המלחמה הוא מונה למושל של שטרסבורג שנכבשה מחדש מידי גרמניה, ולאחר מכן הועבר לכוחות המילואים. הוא פרש מהצבא בשנת 1919. הייתה לו קריירה פוליטית קצרה במפלגת האיחוד הרפובליקני של לורן. הוא מת ב-27 בדצמבר 1943 בוורסאי שתחת הכיבוש הנאצי.
ווייז
צבי פייראיזן
כטמ&quot;ם
הקורפוס ה-21 (ורמאכט)
הקורפוס ה-21 (בגרמנית: XXI. Armeekorps) היה קורפוס של הורמאכט במהלך מלחמת העולם השנייה.
היסטוריה.
הקורפוס הוקם ב-10 באוגוסט 1939 בשם "הקורפוס ה-21", והועמד תחת פיקוד ניקולאוס פון פאלקנהורסט.