tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
הקשר לסריג הוא הקונבולוציה המודולרית, אפשר לראות שקיים הומומורפיזם בין הפולינומים בחוג R ומטריצה מעגלית בגודל עם מקדמים שלמים.
הוכחת בטיחות האלגוריתם אינה לפי סיבוכיות המקרה הגרוע כמו במקרה של סריגים, ולמעשה קיימות מספר חולשות באלגוריתם שמאפשרות התקפת מוצפן-נבחר בגרסה המקורית.
סריגים בתורת המספרים שנקראים גם "הגאומטריה של המספרים" (הרמן מינקובסקי), ניתנים להגדרה בכמה דרכים.
בניסוח לא רשמי סריג הוא אוסף סדור של נקודות במרחב -ממדי.
בניסוח אחר, קבוצת כל הקומבינציות הליניאריות השלמות של וקטורים בלתי תלויים ליניארית מעל , כלומר אם הם קבוצת וקטורים בלתי תלויים ליניארית אזי ייקרא סריג והווקטורים נקראים בסיס הסריג.
בניסוח פורמלי אם נתונים , שני וקטורים ו- מעל המספרים הממשיים ויהי מכפלה אוקלידית של עם כך שמתקיים וכן יהי הנורמה האוקלידית של כאשר .
קבוצת הווקטורים נקראת בלתי תלויה ליניארית מעל אם ורק אם תמיד מתקיים .
סריג היא תת-קבוצה כך שמתקיים כל עוד וכן קיים מספר ממשי כך ש- ו- ו-.
לפי הגדרות אלו הוא סריג כש-.
וכן כל תת-קבוצה של סריג היא סריג.
בשל הדמיון למרחב הווקטורי תורת הסריגים מקבילה בכמה מובנים לאלגברה ליניארית.
בסיס הסריג אינו ייחודי, כלומר עבור סריג מסדר ישנם אין סוף בסיסים עם ממד זהה.
Shortest Vector Problem היא בעיית הסריג המפורסמת ביותר.
בהינתן סריג המיוצג על ידי בסיס , בעיית SVP היא למצוא את הווקטור הקצר ביותר ב- שאינו אפס.
הבעיה יכולה להיות ביחס לכל נורמה המסומנת ב- אך הנורמה האוקלידית הכי נפוצה.
גרסה אחרת של הבעיה היא לחשב רק את אורכו המסומן ב- של הווקטור הקצר ביותר מבלי בהכרח למצוא את הווקטור עצמו הבעיה מסומנת על ידי .
כאשר הבעיה ניתנת לפתרון בזמן פולינומי אולם כאשר האלגוריתם הטוב ביותר הידוע לפתרון בעיה זו הוא בסיבוכיות של .
בעיית SVP נחקרה על ידי מתמטיקאים עשרות שנים בשל הקרבה שלה לבעיות שונות בתורת המספרים והיא משוערת כבעיית NP-קשה.
המשפט הראשון של מינקובסקי הוא משפט מפתח בתורת הסריגים שאומר שאורכו המקסימלי של כל וקטור הקצר ביותר שאינו אפס בכל סריג מממד הוא כאשר הוא קבוע אבסולוטי שתלוי רק בממד ו- הוא הדטרמיננטה של הסריג.
הגבול העליון של מינקובסקי צמוד למדי אך ישנם סריגים שבהם קיים וקטור קצר הרבה יותר.
מינקובסקי לא סיפק אלגוריתם שמוצא וקטור כזה.
אלגוריתם שמוצא וקטור קצר ביותר בסריג דו-ממדי היה ידוע כבר לגאוס במאה ה-19 אולם למקרה הכללי לא היה פתרון (קירוב של פתרון) עד תחילת שנות השמונים של המאה הקודמת עם המצאת LLL.
האלגוריתם LLL יכול לבצע קירוב עד פקטור של כאשר הוא ממד הסריג.
אלגוריתם אחר עם פקטור קירוב טוב יותר שהוא תת-מעריכי בזמן פולינומי הוא של שנור שנקרא Block Korkine-Zolotarev.
לא קיים אלגוריתם פולינומי יעיל המחשב את אורך הווקטור הקצר ביותר בסריג (שלא לדבר על מציאת וקטור כזה) והיא משוערת כבעיה NP-קשה בטווח קירוב פחות מפקטור של .
בעיית ההכרעה של CVP הנקראת GapCVP היא כדלקמן: נתון סריג עם בסיס וקטור ו- הפלט צריך להיות 1 אם או 0 אם .
בעיית ההכרעה היא בהינתן סריג דומה להחזיר 1 אם או 0 אם .
בעיית GapCVP היא NP-שלמה ברדוקציה מבעיית התרמיל.
הצפנה לא-קומוטטיבית היא תת-תחום של הצפנה המשתמש בכלים מתורת החבורות הלא-קומוטטיבית כדי להציג פרוטוקולי הצפנה.
זהו תחום המשלב שלושה תחומים ממתמטיקה ומדעי המחשב - תורת החבורות הקומבינטורית, קריפטוגרפיה וסיבוכיות.
המחקר בתחום גם תורם לתורת החבורות כתחום בפני עצמו.
פרוטוקולים לא-קומוטטיביים מכלילים מספר פרוטוקולים קומוטטיביים ידועים (כמו RSA ו-פרוטוקול דיפי-הלמן) ומספר רעיונות העומדים מאחוריהם.
הפרוטוקולים הקומוטטיביים הופיעו היסטורית כשני עשורים קודם, ואף על פי שרוב מערכות ההצפנה כיום מבוססות עליהם, תורת ההצפנה הלא-קומוטטיבית היא תחום רחב העומד בפני עצמו, ולו מספר יתרונות (וגם חסרונות) על פני הצפנה קומוטטיבית.
להלן מספר פרוטוקולים קלאסיים המבוססים על חבורות לא-קומוטטיביות.
הפרוטוקולים גם מעידים על אופיו של התחום, ובעזרתם ניתן להבין כיצד מוכללים רעיונות מהמקרה הקומוטטיבי.
בפרוטוקולים לעיל יש שני גורמים, אליס ובוב, שרוצים לתקשר באופן בטוח על פני קו לא בטוח, עליו יושבת אוולין ורואה כל מה שהם משדרים.
מידע ציבורי: חבורה ושתי תתי-חבורות שאיבריהם מתחלפים (היינו ).
אליס בוחרת באקראי איבר ושולחת אל בוב את .
בוב בוחר באקראי איבר ושולח אל אליס את .
המפתח המשותף שלהם הוא .
אליס בוחרת מילה באיברים , ושולחת אל בוב את האיברים .
בוב בוחר מילה באיברים , ושולח אל אליס את האיברים .
המפתח המשותף הוא הקומוטטור .
בוב ואליס אכן יכולים לחשב את הקומוטטור - למשל אליס יודעת את המבנה של המילה שבחרה, ולכן יכולה לחשב את (כי היא יודעת את ההצמדה של כל היוצרים), ואז להכפיל ב- משמאל ולקבל את הקומוטטור.
מידע ציבורי: חבורה , איבר .
אליס בוחרת איברים ושולחת .
בוב בוחר איברים ושולח .
חבורה ספציפית שהוצעה על ידי המחברים היא חבורת תומפסון, ראו בהמשך לפרטים.
פרוטוקול שלושת המעברים של Shamir
פרוטוקול זה הוא פרוטוקול שליחת מפתח (Key transport protocol), כלומר פרוטוקול בו אחד הצדדים מעביר מפתח אל האחר (הם לא מחליפים מפתח ביניהם).
הפרוטוקול נקרא על שמו של עדי שמיר.
מידע ציבורי: חבורה ושתי תתי-חבורות שאיבריהם מתחלפים.
כדי לשלוח מילה אל אליס, בוב ואליס יפעלו כך:
בוב בוחר שני איברים ושולח אל אליס את האיבר .
אליס בוחרת שני איברים ושולחת אל בוב את האיבר .
בוב מכפיל בהפכיים של האיברים שלו ושולח אל אליס: (בגלל החילופיות).
אליס מכפילה בהפכיים של האיברים שלה, ומקבלת את המפתח: .
בטיחות הפרוטוקולים השונים לעיל תלויה בקיומם את הבעיות הבאות:
בעיית חיפוש המצמיד (Conjugator Search Problem)- בבעיה זו, שואלים האם בהינתן שני האיברים: , ניתן למצוא איבר שיצמיד את אל , כלומר כך ש-.
לעיתים דורשים תנאים נוספים על המצמיד, למשל שהוא יבוא מתת-חבורה נתונה כלשהי, כמו בפרוטוקולים לעיל.
סיבת הבטיחות בפרוטוקולים רבים היא בדיוק בעיית חיפוש המצמיד, ועל כן יש לבחור חבורות בהן הבעיה קשה.
גרסה נוספת של הבעיה היא בעיית חיפוש המצמיד הסימולטני - בהינתן ההצמדות והאיברים , למצוא את המצמיד .
בבעיה זו ניתן יותר מידע, ויש בה שימוש למשל בפרוטוקול AAG' אך גם היא מתגלה כקשה מספיק בפלטפורמות הנכונות.
בעיית הפירוק (Decomposition Problem)- בעיה זו ניתן לנסח גם בתורה הקומוטטיבית.
ניסוח הבעיה הוא: בהינתן שני האיברים , למצוא איברים מתוך חבורה נתונה מראש , כך ש-.
בעיה זו היא הסיבה לבטיחות של פרוטוקול Shpilrain-Ushakov.
כעת נסביר מהן התכונות שהחבורות צריכות לקיים, ונציג מספר הצעות קלאסיות, מתקדמות וספציפיות לחבורות בעזרתן ניתן ליישם הלכה למעשה את הפרוטוקולים הלא-קומוטטיביים.
פרט לדרישה שבחבורות לא יהיו פתרונות פשוטים לבעיות לעיל, יש לדרוש כי לחבורה תהיה בעיית מילה פשוטה.
בעיית מילה - בעיית המילה היא בעיית ההכרעה, בה יש להכריע האם שתי מילים בחבורה הנתונות בהצגות שונות הן זהות.
לכל חבורה התממש פרוטוקול כלעיל, חייבת להיות בעיית מילה פתירה ביעילות - שכן על שני הצדדים להחליף איברים בעלי הצגות שונות, אך בסופו של דבר להחזיק באותו האיבר.
אחת הדרכים הנפוצות לפתור את בעיית המילה והעברת איברי חבורות אבסטרקטיות בצורה יעילה היא הצגת צורה נורמלית (Normal Form) עבור החבורה.
זוהי תבנית בה ניתן להציג את כל איברי החבורה באופן יחיד.
בהינתן צורה נורמלית יעילה, בעיית המילה פתירה בקלות - בהינתן שתי מילים, מחשבים את הצורה הנורמלית של כל אחת מהן ובודקים האם מתקבלת אותה צורה.
מציאת צורה נורמלית תלויה במידה רבה במבנה החבורה ואיברים מיוחדים.
כעת, כשאמרנו לעיל 'יש לשלוח את האיבר...', מה שבאמת שולחים הוא צורה נורמלית של האיבר'''.
אם בוחרים חבורה טובה אפשר לחשב אותה ביעילות, לעיתים קל להכפיל איברים בעזרתה, וקל לזהות שתי מילים בעזרתה.
עם זאת, לעיתים צורות נורמליות נותנות יותר מדי מידע ומהוות פרצה להתקפות, כדוגמת התקפות מבוססות אורך או התקפות על בעיית הפירוק.
דרך נוספת לפתור את בעיית המילה ולהכפיל איברי חבורות אבסטרקטיות היא בעזרת מציאת הצגה נאמנה, כלומר בחירת חבורה ליניארית.
הצגה נאמנה היא שיכון של החבורה אל חבורת מטריצות מעל שדה - בחבורה כזו קל מאוד להשוות בין איברים ויחסית קל להכפיל אותם ולשלוח אותם.
כעת יוצגו מספר דוגמאות קלאסיות וספציפיות, ויוסבר בקצרה מדוע הן מתאימות לפרוטוקולים לעיל.
אחת החברות שעלו כמומעד טבעי לפרוטוקולים לעיל היא חבורת הצמות.
לחבורה זו שתי צורות נורמליות יעילות, מבניות ונוחות במיוחד, וכן בעיית חיפוש המצמיד בה נחשבת לקשה.
יש בה גם חבורות גדולות המתחלפות איבר איבר.
לחבורה זו יש גם הצגה ליניארית, ולכן יש דרך נוספת לפתור את בעיית המילה ולהכפיל ולשלוח את איבריה.
לחבורת הצמות שימושים רבים בתחומים שונים של המתמטיקה והן חבורות נחקרות ומפורסמות מאוד.
ניתן לראות בכך חיסרון, משום שאם החבורה נחקרת באופן נרחב ממספר נקודות מבט שונות יכול להיות שיתגלו דרכים שונות להתקיף את הפרוטוקולים עליה, אך יש בכך גם יתרון - המחקר הרב סביב הבעיות השונות מראה עד כמה הן קשות, ולכן מראה שהחבורה היא מועמד טוב לפרוטוקולים.
חבורות ארטין מהוות הכללה של חבורת הצמות: בהן יש יחסים בסגנון דומה לאלו של חבורת הצמות, אך חבורות ארטין יכולות להיות מסובכות יותר.
הן הוצעו באופן טבעי לאחר שמספר התקפות נמצאו על חבורת הצמות.
משפחות מסוימות של חבורת ארטין הן ליניאריות.
חבורת תומפסון גם היא חבורה בעלת שימושים במספר תחומים במתמטיקה, כמו טופולוגיה וגאומטריה.
יש לה את ההצגה האינסופית הבאה:
לחבורה זו יש גם הצגות סופיות, אך דווקא בעזרת ההצגה האינסופית הזו ניתן להציג צורה נורמלית שלה - כל איבר ניתן לרשום ביחידות בצורה , כאשר האינדקסים מסודרים בסדר עולה, ואם שניהם מופיעים, אז גם או .
צורה זו ניתן לחשב בסיבוכיות זמן ריצה , כאשר הוא אורך המילה הנתונה.
שתי תתי-חבורות מתחלפות של חבורת תומפסון שהוצעו על ידי המחברים הן: .
חבורות מטריצות מעל חוג חילופי סופי אף הן חבורות לא-קומוטטיביות שהוצעו במספר פרוטוקולים.
הדרישה להיותו של חוג הבסיס קומוטטיבי וסופי היא כדי שיהיה אפשר להשתמש בבעיית הפירוק.
דוגמאות מפורשות הן חוג מטריצות מעל - אך צריך לבחור גבוה במיוחד.
הצעה נוספת היא להשתמש בשדות סופיים, להן מימוש יעיל בהינתן פולינום אי פריק מהמעלה הרצויה.
ניתן גם להשתמש בחוגים עם נילפוטנטים, כדוגמת .
לאור האמור לעיל ניתן להצביע על מספר רעיונות מרכזיים של ההצפנה הלא-קומוטטיבית.
רעיונות אלו במידה מסוימת הפוכים לתורה הקומוטטיבית ומשדרגים אותה.
הפרוטוקולים ישימים מעל חבורות לא-קומוטטיביות בהכרח.
החבורות הן בדרך כלל לא סופיות.
בטיחותם מבוססת על בעיות קשות מתורת החבורות הקומבינטורית (בניגוד לבטיחות בתורה הקומוטטיבית, המבוססת בעיקר על בעיות מתורת המספרים).
מימוש הפרוטוקולים הלכה למעשה דורש הצגה צורה נורמלית יעילה (או דרך חלופית אחרת); בפרט, הוא איננו טריוויאלי ודורש עבודה בתורת החבורות (בניגוד למימוש במקרה הקומוטטיבי, שם הוא טריוויאלי ופשוט).
המקרה הקומוטטיבי איננו חסין מפני התקפות הנעזרות במחשב קוונטי.
בניגוד לכך, נכון לעכשיו'' לא ידועות התקפות קוונטיות יעילות (לא אקספוננציאליות) על הפרוטוקולים לעיל.
בקריפטוגרפיה ובטכנולוגיית מידע, הצפנת דיסקים הוא שם כולל לשיטות הצפנת קבצים המאוחסנים במדיה דיגיטלית כמו דיסק קשיח לצורך גישה ישירה.
מהיבט תאורטי סיטואציה כזו מציבה מספר דרישות מיוחדות:
(א) הקבצים חייבים להיות מוצפנים באופן שלא ייווצר מצב ששני בלוקים זהים יוצפנו באותו מפתח.
(ב) הגישה לקבצים צריכה להיות מהירה, ללא קשר איך הוצפן הקובץ או באיזה סקטור הוא נמצא.
(ג) הקבצים המוצפנים לא אמורים לבזבז שטח אחסון, כלומר שהקובץ המוצפן לא יהיה גדול יותר מהקובץ המקורי.
בגלל המגבלות יש צורך לחלק את הדיסק למקטעים או סקטורים בגודל קבוע ולהצפינם בנפרד ללא תלות באחרים.
לכן הדרך הטובה ביותר היא צופן בלוקים או צופן בלוקים בר התאמה.
כדי לשנות בית מסוים בקובץ מסוים צריך לפענח את הסקטורים בהם מצוי הקובץ, לבצע את השינוי ולהצפינם מחדש.
גודל הסקטור נקבע בהתאם למספר מאפיינים.
סקטורים גדולים מדי מקשים על גישה ישירה כי צריך לפענח כמות גדולה יותר של מידע בכל פעולת שינוי, לעומתם סקטורים קטנים מאטים את ההצפנה.
דרישה (א) מוגדרת בהתאם לסוג האיום.
ההנחה הבסיסית היא שליריב גישה לאמצעי האחסון והוא מסוגל לקרוא מידע מוצפן בכל רגע נתון אך אין לו גישה למפתחות ההצפנה, מסיבה זו רצוי שלא תהיה לו יכולת לזהות בלוקים זהים, כלומר עמידות כנגד התקפת גלוי-נבחר.
בהגדרה מחמירה יותר מניחים שהיריב מסוגל לבקש הצפנה של כל קובץ לפי בחירתו ואחסונו בכונן מבלי לראות את מפתח ההצפנה (למשל אם התוקף שם ידו על חומרה בתוכה מוטמע המפתח באופן שלא ניתן לחשיפה והוא יכול להפעילה כקופסה שחורה), הגדרה זו מתאימה להתקפת מוצפן-נבחר.
הגדרה יותר מחמירה מציבה אתגר נוסף, היריב מסוגל לפענח סקטורים באזורים מסוימים במדיית האחסון, לכן יש למנוע מצב שבו התוקף פשוט יעתיק סקטור מוצפן שנמצא באזור בו אין לו יכולת פענוח לאזור אחר בדיסק שבו הוא יכול לבקש פענוח.
בהצפנת דיסקים קיימות מגבלות מובנות שלא ניתנות לפתרון והם:
בגלל דרישה (ג) אין אפשרות לאחסן מידע נוסף מלבד הקובץ המוצפן עצמו לכן במקרה זה לא מתאימה הצפנה הסתברותית או צופן זרם.
צופן זרם מחייב שימוש בווקטור אתחול שונה עבור כל הצפנה (סקטור או בלוק).
יתרה מזו, אם המשתמש משנה תוכנו של קובץ מוצפן יש צורך לשנות את גם את וקטור האתחול אחרת ייווצר מצב ששני בלוקים שונים יוצפנו עם מפתח זהה, שכאמור בצופן זרם מהווה שבירה מוחלטת של הצופן.
עובדה זו מאלצת אחסון ערכים בנוסף לקבצים מה שמפר את דרישה (ג).
מאותה סיבה אין אפשרות להוסיף אימות ולכן לא ניתן לאתר שינויים זדוניים בטקסט המוצפן.
אפשר להחליף בין סקטורים שלמים מבלי שהדבר יתגלה.
את הבעיה הזו אפשר למנוע חלקית על ידי קונטקסט כלשהו כמו מספר סידורי (הוספת מידע כלשהו כמו תאריך לא תועיל כי אין דרך למפענח לדעת אם הוא נכון).
בלוקים זהים שהוצפנו עם מפתח ווקטור אתחול זהים, תמיד יפיקו טקסט מוצפן זהה.
כלומר קשה להבטיח הגנה מוחלטת מפני התקפת מוצפן-נבחר.
מצבי ההפעלה הרגילים כמו ECB, CBC, OFB או CTR אינם מתאימים מפני כמה סיבות:
ב-CBC הצפנת בלוק אחד תלויה בבלוקים אחרים ולכן בפענוח בלוק ספציפי חייבים לפענח בלוקים אחרים באותו סקטור.
מאותה סיבה לא ניתן להאיץ ביצועים על ידי יישום מקבילי.
אפשר להעביר סקטורים שלמים והפענוח יהיה נכון חוץ מהבלוק הראשון בתוך הסקטור בגלל וקטור האתחול ולכן כפי שתואר לעיל אם נניח שקיים אזור בדיסק שבו מותר למתקיף לפענח כל סקטור שהוא רוצה, הוא יכול פשוט להעתיק לשם את הסקטור המותקף.
שגיאה בסיבית אחת גוררת אחריה שיבוש של כל או חלק מהבלוקים המוצפנים ומחייבת להצפינם מחדש.
במצב מונה ניתן לבצע מניפולציה בסיביות שמשפיעה רק על הסיביות המקבילות בטקסט המקור.
בשל החסרונות האמורים ישנן שלוש התקפות עיקריות נגד הצפנת דיסקים שתמיד ניתנות לביצוע:
ניתן לנטר את התקשורת בין התקן ההצפנה לבין מדיית האחסון ולהבחין בשינויים אם בוצעו בטקסט המקור (כי כאמור בלוק זהה עם אותו מפתח ואותו וקטור אתחול יפיק טקסט מוצפן זהה), מה שמאפשר התקפות מסוימות, כגון חילוץ מידע על ידי הבחנה בדפוסי התנהגות, סיבתיות או הקשר.
אם לתוקף גישה ברמת קריאה/כתיבה למדיית האחסון, הוא תמיד יכול להעתיק תכולה של סקטורים, לאתר סקטור שבוצע בו שינוי ולהחליפו בסקטור הקודם, לפני השינוי.
היות שאין אימות, תוקף עם גישה לדיסק גם אם אינו יכול לפענח את המידע המצוי בו יכול לפחות לשבשו על ידי החלפתו בג'יבריש כדי לנתח את אופן ההתמודדות עם טקסט "בלתי צפוי".
ביטחון הצפנת דיסקים הוא לכל היותר כמו מצב ECB עם מפתח שונה עבור כל בלוק.
או לחלופין אפשר להציג זאת כצופן בלוקים שבו הבלוק הוא בדיוק באורך הסקטור.
אם הסקטור גדול מהבלוק שהצופן מקבל מחלקים את הסקטור לבלוקים בגודל הרצוי ומפעילים את ההצפנה על כל הבלוקים באופן איטרטיבי באופן ששני בלוקים זהים יפיקו תוצאה מוצפנת שונה.
כדי להבטיח את דרישה (א) יש להצפין כל סקטור עם מפתח אחר.
במקום לאחסן מפתחות רבים אפשר להשתמש במפתח 'מאסטר' יחיד ממנו מפיקים מפתחות הצפנה ככל שיידרש, למשל על ידי הצפנה של ערך ייחודי וחד פעמי עבור כל סקטור שנקרא tweak המשרת כמו וקטור אתחול, ה-tweak לא חייב להיות אקראי או סודי, למשל המספר הסידורי של הסקטור יספיק.
החיסרון בזה הוא שכעת יש צורך להפעיל את צופן הבלוקים פעמים עבור סקטורים.
עבור כל סקטור צריך תחילה להצפין את ה-tweak ממנו מייצרים מפתח הצפנה ואיתו מצפינים את הסקטור.
בגלל השימוש ב-XOR לא רצוי מטעמי ביטחון להשתמש ב-tweak עצמו ישירות כמפתח לפונקציית ה-PRP אלא מקובל להצפינו תחילה, לכן משמשים בשני מפתחות הצפנה נפרדים.
כלומר עבור כל סקטור תחילה מצפינים את ה-tweak (מספר הסקטור) עם מפתח ההצפנה הראשון, מהתוצאה מייצרים מפתחות מיסוך עבור כל הבלוקים שהסקטור מכיל ובאמצעות המפתח השני מצפינים את כולם עם צופן הבלוקים.
זו השיטה המועדפת מהיבט של ביטחון ויעילות.
הפעלת צופן הבלוקים מתבצעת רק פעמים ופונקציית ה-PRP מהירה כך שהיא זניחה ביחס לצופן הבלוקים.
מספר מצבי הפעלה עוצבו בשיטה זו, ביניהם אפשר לציין את: LRW, XEX ו-XTS.
מצב ההפעלה LRW שהוצע על ידי ליסקוב, ריבסט ווגנר הוא פרימיטיב קריפטוגרפי שמיישם את רעיון צופן בלוקים שניתן להתאמה.
הצופן מקבל מפתח הצפנה וכן "tweak" המשרת בערך כמו וקטור אתחול או Nonce.
כאשר היא פונקציה כלשהי בשדה סופי , המתפקדת מעין פונקציית גיבוב.
תקן IEEE P1619 אימץ את מצב ההפעלה XTS-AES (לפי שיטת XEX - כלומר "XOR/ENCRYPTION/XOR" כשההצפנה היא עם AES), מצב הפעלה זה פותח במיוחד להצפנת סקטורים גדולים במדייה דיגיטלית.
השיטה נקראת teawkable במובן שהיא משתמשת בווקטור אתחול שנקרא tweak בגודל 128 סיביות (16 בתים) כאן מסומן ב-.
ה-tweak משתנה בכל סקטור והוא יכול להיות מספר רץ של הסקטור.
בשיטה זו כל בלוק מוצפן פעמיים.
המפתח מחולק לשני מפתחות כל אחד בגודל הדרוש לצופן הבלוקים, תחילה מצפינים את וקטור האתחול עם המפתח הראשון ולאחר מכן מפעילים פונקציה פסאודו-אקראית פשוטה ומצפינים את התוצאה מחוברת עם בלוק הטקסט הקריא באמצעות המפתח השני.
הבלוק נקרא כאן ו- הוא מונה המייצג את מספרו הסידורי של הבלוק בתוך הסקטור.
הנוסחה להצפנת בלוק אחד שנקראת כאן כמוצג בתרשים היא:
הפעלת הצופן בשורה הראשונה מתבצעת רק פעם אחת כיוון ש- אינו עולה על בלוק אחד.
בפענוח מחליפים בשורה השנייה את הקריאה לפונקציית ההצפנה בפונקציית הפענוח .
ההכפלה ב- היא כפל של הבלוק המוצפן, אותו רואים כפולינום מעל השדה הבינארי המורחב בחזקות של הפולינום או בייצוג הקסדצימלי, מודולו .
לצורך הצמצום המודולרי משתמשים בפולינום הפרימיטיבי כדי שהתוצאה תישאר אלמנט בשדה.
מבחינה פרקטית פעולת הכפל בשדה יכולה להתבצע על ידי רקורסיה של הזזות (shift) השקולות לכפל ב- וצמצום מודולרי באמצעות פעולת XOR מותנת (כאשר הסיבית הגבוהה היא '1') עם הערך או בייצוג הקסדצימלי .
אפשר לראותה כפעולה חיסור במודולוס הדרושה כאשר מתרחשת גלישה (להסבר נוסף ראה OMAC), אפשר להכין את הערכים הללו מראש או להשתמש בטבלאות חיפוש, בהתאם לאופי היישום והחומרה, אך צריך להביא בחשבון התקפת ערוץ צדדי שמודדת את זמני הביצוע השונים.
להלן דרך בטוחה לביצוע פעולת הכפל בשדה בחלוקה ל-16 בתים המסומנים :
הכפל מתבצע בית אחר בית, הכפל ב-2 אינו אלא הזזה לשמאל והחילוק ב-128 הוא הזזה לימין 8 פוזיציות.
הפעולה מעבירה את סיבית הגלישה לבית הבא.
ואין צורך לבצע מודולו 128 אפשר לעשות במקום.
להצפנת סקטור שלם במשתמשים בטכניקה שנקראת גנבת טקסט-מוצפן.
תחילה מחלקים אותו ל- בלוקים בגודל המתאים לצופן הבלוקים.
כלומר אם הסקטור הוא אז .
כאשר הוא השלם הגדול ביותר כך שמתקיים .
יש לשים לב ש- הבלוקים הראשונים מלאים ואילו הבלוק חלקי או ריק לגמרי (מכיל רק אפסים).
ההצפנה של הסקטור מתחלקת לשני מקרים כדלהלן, אם הבלוק האחרון ריק, כלומר ההצפנה של כל הסקטור מתבצעת ישירות כך; עבור כל בלוק כאשר מחשבים את והבלוק המוצפן האחרון יהיה ריק.
אם בלוק הטקסט הקריא האחרון אינו ריק דהיינו אזי מבצעים 'שיכול' בין שני הבלוקים האחרונים כדלהלן; תחילה מחשבים את , הבלוק יהיה הסיביות הראשונות של ואז משרשרים את הסיביות הנותרות של לבלוק הטקסט הקריא האחרון ומתקבל בלוק חדש אותו מצפינים כך והתוצאה האחרונה תהיה הבלוק .
שים לב שהבלוק עשוי להיות חלקי.
לכן הטקסט המוצפן נשאר באורך זהה לטקסט המקורי.
הוכח על ידי רוגאווי שביטחון השיטה הוא בסיבוכיות כלומר הביטוי משקף את היתרון שבידי התוקף בהבחנה בין הטקסט המוצפן לבין מחרוזת אקראית כלשהי, כאשר הוא מספר השאילתות האקראיות לאורקל (בהקשר מעשי - מספר הבלוקים שהוא יכול להצפין) ו- מייצג את "היתרון" שלו או אפשר לומר טווח השגיאה.
בגלל התקפת יום הולדת קיים חסם עליון שהוא שמחייב שלאחר גבול זה התנגשויות חייבות להופיע, לכן כאשר מתקרב לערך זה יש סבירות משמעותית ש"התקפת הבחנה" תצליח.
כלומר שיימצא זוג המקיים עבור שני אינדקסים שונים כאשר הוא הטקסט הקריא ו- הוא ה-tweak.
במקרה זה הטקסטים המוצפנים המתאימים יהיו זהים אחרי חיבור עם ה-tweak של כל אחד מהם בהתאמה.
כלומר התרחשה התנגשות שמאפשרת לתקוף להבחין בין ההצפנה בשיטה זו לבין טקסט רנדומלי לחלוטין.
התקפת הבחנה אינה תאורטית בלבד, באמצעותה התוקף יכול לבצע שינויים בסיביות ספציפיות בטקסט המקורי שמתאים לטקסט המוצפן שהוא תוקף וזאת מבלי לפענחו, בדרך הבאה:
עבור כלשהו הוא מחשב את במיקום ומחליף את הטקסט המוצפן באופן הבא: והטקסט המוצפן החדש יהיה , במילים אחרות התוקף הצליח לשנות סיביות מסוימות של הבלוק מבלי שהמותקף יבחין בכך.
קיימות טכנולוגיות הצפנת דיסקים ברמת חומרה הנקראת FDE (קיצור של full-disk encryption) כמו BitLocker או ברמת תוכנה כמו Truecrypt.
עקב תופעה פיזיקלית ידועה, המידע בזיכרון המחשב נותר שלם בחלקו למספר דקות לאחר הכיבוי.
היות שמערכת ההפעלה צריכה לאחסן את מפתח ההצפנה היכן שהוא בזיכרון בזמן הצפנה/פענוח, קשה למנוע סוג כזה של התקפה גם אם משתמשים במערכת הפעלה בטוחה ברמה של חומרה כמו TMP.
כמו כן סכימת הצפנת דיסקים בעייתית גם כאשר המחשב נגנב כשהוא במצב "רדום" אם כאשר מעירים אותו לא מתבצע אתחול דרך BIOS.
כמו כן הצפנת דיסקים ברמת תוכנה חשופה למספר התקפות ערוץ צדדי כמו קריפטואנליזה אקוסטית או רישום הקשות.
הצפנה פּוֹסְט-קְוַנְטִית היא פיתוח של אלגוריתמים קריפטוגרפיים חסינים בפני פיצוח על ידי מחשבים קוואנטיים.
שיטות ההצפנה הא-סימטריות (שבהן יש מפתח ציבורי גלוי ומפתח אישי סודי), כדוגמת הצפנה RSA והצפנת-ECC, מתבססות על הקושי של מחשב לפצח אותן בזמן סביר.
אלה השיטות המקובלות אבל מחשב קוואנטי עתידי יוכל לפצח אותן בשבריר מהזמן הזה.
האלגוריתמים הסימטריים להצפנה שנהוגים נחשבים חסינים גם בפני מחשב קוואנטי.
חברות וארגונים מתכוננים ליום תאורטי - המכונה QDay - שבו יהיו מחשבים קוואנטיים גדולים מספיק שיוכלו לפצח את ההצפנות הנהוגות.
האלגוריתמים האסימטריים הנפוצים בשימוש מעשי כיום, מבוססים ברובם בעיקר על שתי בעיות מתורת המספרים הנחשבות "קשות" ונגזרותיהן; בעיית פירוק לגורמים ובעיית הלוגריתם הבדיד.
כשהאחרונה מתחלקת לשני תחומים מתמטיים, שדה סופי ועקום אליפטי.
ב-1994 הראה פיטר שור שאפשר לפרק לגורמים מספר גדול באמצעות אלגוריתם קוונטי, הנקרא על שמו אלגוריתם שור, בסיבוכיות זמן של , היעילה באופן דרמטי לעומת השיטות הידועות במחשב קלאסי.
ב-1996 המציא לוב גרובר אלגוריתם קוונטי שנקרא אלגוריתם גרובר לחיפוש במבנה נתונים לא ממויין בזמן של .
ההשלכה שלו מרחיקה לכת ויש לה השפעה עצומה על תורת ההצפנה, במיוחד על הצפנה א-סימטרית אך גם על הצפנה סימטרית.
כאשר מחשב קוונטי גדול יהפוך למציאות, וישתמשו בו עם האלגוריתמים המנויים, שבירת המערכות הללו יכולה להתרחש בזמן פולינומי, שזה נמוך בהרבה מהאלגוריתם הטוב ביותר הידוע כיום הנקרא נפת שדה מספרים שהוא תת-מעריכי.
משמעות הדבר שפרוטוקול דיפי-הלמן, RSA וכן כל נגזרותיהם המסתמכים על בעיות דומות יצאו מכלל שימוש.
בשנים האחרונות חלה התקדמות בפיתוח מחשבים קוונטיים.
באוגוסט 2015 הכריזה חברת D-Wave הקנדית על מחשב קוונטי "אנלוגי" מעשי הנקרא D-Wave 2X בקנה מידה של +1000 קיוביטים.
באותה עת פורסם שהמחשב הותקן בהצלחה במעבדת הבינה המלאכותית הקוונטית השייכת למיזם משותף של נאס"א וגוגל.
מחשב קוונטי מסוג זה אינו מתאים לשימוש כללי ואינו רלוונטי לקריפטואנליזה, הוא מתאים בעיקר לפתרון בעיות מיוחדות בתחום אופטימיזציה, ביואינפורמטיקה וכדומה.
אף על פי שהמחשבים הקוונטיים הדיגיטליים המיוצרים, נכון לשנת 2016, עדיין קטנים מדי מכדי לבצע באמצעותם התקפה מלאה נגד האלגוריתמים האסימטריים עם מפתחות באורכים המומלצים על ידי התקנים הבינלאומיים, ישנן הערכות שמחשבים קוונטיים בהיקף מלא עומדים להיות זמינים בתוך כעשור, זאת בניגוד להערכות קודמות.
מסיבה זו הקהילה הקריפטוגרפית נערכת בתקופה זו למעבר לעידן קוונטי והעניין בנושא גובר מצד האקדמיה והתעשייה בעיקר דרך כנסים של PQCrypto המתקיימים אחת לשנה מאז 2006 וכן קבוצות מחקר של ארגונים כמו ETSI ו-IEEE.
הצפנה פוסט-קוונטית לעומת הצפנה קוונטית
יש להבדיל בין הצפנה פוסט-קוונטית לבין הצפנה קוונטית.
האחרונה משמשת בעיקר להכנה והעברה של מפתחות הצפנה סודיים לצורך הצפנה בשיטת פנקס חד פעמי בדומה לצופן זרם, אך בניגוד אליו אינה מנצלת "תהליך מתמטי" כדי להסתיר את העברת המפתח מעיני היריב אלא מסתמכת על תופעה פיזיקלית כדי למנוע ציתות על ידי איתור וחשיפה.
לאור זאת יש מי שחושש שבעידן הפוסט-קוונטי יחזרו לשיטות הישנות של הסתרת מידע באמצעות כספות, תיקים נעולים אזוקים בשלשלאות לזרוע או מפגשים אישיים חשאיים.
אולי מכיוון שקל לטעות בין הצפנה פוסט-קוונטית לבין הצפנה קוונטית.
המציאות היא שכנראה הקריפטוגרפיה לא תשתנה במידה ניכרת והמעבר יהיה די חלק.
בניגוד להצפנה אסימטרית, האיום הקוונטי אינו ממשי כלפי אלגוריתמים סימטריים כמו AES ופונקציות גיבוב כמו SHA-3, כיוון שלא ניתן ליישם את אלגוריתם שור לשבירתם, ואף על פי שאלגוריתם גרובר מהווה איום משמעותי הוא אינו יעיל במידה ניכרת מהשיטות הקלאסיות.
בשל תכונת הסופרפוזיציה הקוונטית ניתן לבצע חיפוש ממצה של כל האפשרויות של המפתח בפעולה אחת, אבל תיוותר הבעיה כיצד לחלץ את המפתח הנכון.
אלגוריתם גרובר מאפשר לעשות זאת בעזרת פעולות קוונטיות, כאשר הוא טווח החיפוש.
מזה נובע שבפתרון בעיית חיפוש למחשב הקוונטי יתרון ריבועי על פני מחשב קלאסי אך לא יותר מכך.
אף על פי שתמיד קיים החשש שנמצאה פריצת דרך סודית, לדעת מרבית המומחים, כל שיש לעשות כדי להתמודד מול האיום הקוונטי הוא להכפיל את אורך המפתח של הצופן הסימטרי.
אלגוריתמים אחדים ישרדו את העידן הפוסט-קוונטי ואחרים לא.
RSA, DSA, ECC ודומיהם לא ישרדו.
לעומתם קיימים מזה שנים רבות אלגוריתמים טובים הבטוחים הן בפני איום קלאסי והן בפני איום קוונטי.
הסיבה שלא משתמשים בהם כיום נובעת אך ורק משקולי יעילות.
המעבר לעידן הפוסט-קוונטי מחייב שימוש באלגוריתמים שכיום אינם יעילים במונחי מחשוב ואינם מתאימים לשימוש מאסיבי, אם כי המחקר עדיין בעיצומו וייתכנו שיפורים מרחיקי לכת.
אלגוריתמים פוסט-קוונטיים שהדיעה הרווחת לגביהם שהם עמידים נגד קריפטואנליזה קוונטית קיימים אך חלקם לא יעילים, חלקם ללא הוכחה מתמטית מוצקה וחלקם צעירים מאוד.
אפשר לבסס הצפנה פוסט-קוונטית על מספר בעיות מתמטיות קשות שמהן ניתן להכין פונקציה חד-כיוונית המתאימה לצורך קריפטוגרפי ואשר הדעה הרווחת לגביהן שהן יוותרו בטוחות גם נוכח איום מחשב קוונטי, מהן ניתן למנות את:
הצפנה מבוססת גיבוב: הדוגמה הקלאסית למערכת כזו היא חתימה דיגיטלית מבוססת עץ גיבוב משנת 1979 של רלף מרקל מחלוצי הצפנת מפתח ציבורי, המבוססת על חתימת למפורט.
הצפנה מבוססת קוד: הדוגמה הטובה ביותר היא הצפנת מקאליס משנת 1978 של רוברט מקאליס המבוססת על תורת הקודים.
הצפנה מבוססת משוואה רבת משתנים: הדוגמה המבטיחה ביותר היא גרסאות של אלגוריתם חתימה דיגיטלית HFE של Jacques Patarin משנת 1996.
הצפנה מבוססת סריג: סריגים נחקרו במשך שנים לטובת הצפנה, הדוגמה הידועה והמעשית ביותר היא אלגוריתם NTRU משנת 1996 של Jeffrey Hoffstein, Jill Pipher ו-Joseph Silverman.
הצפנה מבוססת איזוגניה: שיטת הצפנה חדשה יחסית המבוססת על איזוגניות בין יריעות אלגבריות ובפרט בין עקומים אליפטים, לדוגמה פרוטוקול שיתוף המפתח SIDH משנת 2011.
הצפנה סימטרית או הצפנת מפתח סודי: הדוגמה הטובה ביותר היא תקן AES אך קיים מאגר עשיר של אלגוריתמים יעילים ובדוקים כמו Salsa20 או SNOW 3G ועוד רבים שנבחנו במשך שנים ולא נמצאו בהם חולשות משמעותיות.
חלקם בטוחים יותר וחלקם פחות, כל אחד מהם מתאים לשימוש בהתאם לסיטואציה, חשיבות היעילות, פוטנציאל האיום, קונפיגורציה וכדומה.
נכון להיום מרבית האלגוריתמים הבטוחים יעמדו במבחן האיום הקוונטי עם מפתחות באורך כפול מהאורך הנוכחי בלבד.
עובדה זו מאפשרת מציאת חלופות להצפנה אסימטרית כמו העברת מפתח מבוססת הצפנה סימטרית של קרברוס.
חתימה דיגיטלית מבוססת פונקציית גיבוב מסתמכת על התכונה של פונקציית הגיבוב שהיא חסינת התנגשויות.
הוכח שתכונה זו לבדה מספקת כדי להכין ממנה חתימה דיגיטלית.
האלגוריתם הראשון המבוסס על פונקציית גיבוב הוא חתימת למפורט הפועלת כך: אליס משתמשת במחולל פסאודו-אקראי כדי לייצר טבלה של 256 זוגות מספרים אקראיים באורך 256 סיביות כל אחד, סך הכול 16 קילובייט של מידע פרטי.
את כל הערכים בטבלה היא מגבבת ושולחת לבוב את התוצאות כמפתח ציבורי.
כדי לחתום על מסר תחילה מגבבת את המסר ומקבלת 256 סיביות של תוצאת הגיבוב, אותם היא מחליפה סיבית אחר סיבית בערכים מהטבלה בהתאם לערכה של כל סיבית כלומר אם הסיבית הנוכחית היא "0" מוחלפת בערך הראשון בזוג המתאים בטבלה ואם היא "1" מוחלפת בשני וכן הלאה.
כך נוצרים 256 ערכים של חתימה שאורכה הכולל הוא 8 קילובייט.
כדי לאמת את החתימה בוב מבצע פעולה דומה, מגבב את המסר, את התוצאה מחליף סיבית אחר סיבית בהתאם לערכה בערכים מהמפתח של אליס, הוא מבצע גיבוב של 256 הערכים של החתימה שקיבל ומשווה ביניהם.
אליס אינה משתמשת שוב במפתח הפרטי שלה לחתימה על מסרים אחרים (מכאן השם).
כדי לחתום על מסרים נוספים עם אותו מפתח פרטי ניתן לבצע "שרשור".
כלומר כל מסר יכיל בנוסף לחתימה שלו מפתח ציבורי חדש שישמש לחתימה על המסר הבא וכן הלאה.
כך החתימה על המסר האחרון תכיל עותק של כל המסרים שנחתמו קודם עם אותו מפתח.
אפשר לבצע שיפורים אחדים כמו צימצום המפתח הפרטי על ידי אחסון הגרעין ההתחלתי בלבד וכן עץ הגיבוב של מרקל שמאפשר התנפחות בסדר גודל לוגריתמי.
אך בעיקרון מעבר לשאלת הביטחון אפשר לראות את החסרונות של מערכת כזו, היא אינה מתאימה להצפנה וכן בשל האורך המוגזם של מפתחות החתימה והאימות (בסך הכול 32 קילובתים לעומת מפתח RSA שהוא בערך 4 קילובתים).
היות שביטחון השיטה נובע מהחד-כיווניות של פונקציית הגיבוב אפשר לראות מדוע היא הופכת אטרקטיבית בעידן הפוסט קוונטי, גם אלגוריתם גרובר אינו יעיל במיוחד למציאת התנגשויות בפונקציות גיבוב קריפטוגרפיות ומבחינת האקדמיה, לא ידוע על אלגוריתמים יותר יעילים.
הרעיון מאחורי הצפנה מבוססת קוד הוא בעיית פענוח סינדרומי, אם נתונה מטריצה מסדר (כאשר הוא פרמטר ביטחון, ו-) עם מקדמים מ- ומסר , ההצפנה היא הכפלת המסר במטריצה .
כדי לשחזר את המסר יש צורך להפוך את הפעולה כלומר באמצעות אלגברה ליניארית למצוא וקטור המקיים , הבעיה היא שקיים מספר עצום של וקטורים מתוכם אפשר לבחור את ומציאת וקטור כזה בעל משקל היא בעיה קשה מאוד.
המקבל יכול לפענח את המסר או לשחזר את הקוד על ידי הסתרה של מטריצת בדיקת זוגיות סודית כמו קוד גופה או קוד אחר בתוך המטריצה כך שיהיה פתרון פולינומי לבעיה על ידי אלגוריתם כמו אלגוריתם פטרסון.
האלגוריתם המתואר הוא וריאציה של הצפנת מקאליס והמטריצה היא בעצם כפולה של שלוש מטריצות שונות , כאשר היא מטריצת זוגיות של "גופה" וכדי להסתירה מעיני היריב מכפילים אותה ב- שהיא מטריצה אקראית הפיכה ו- פרמוטציה כלשהי.
הפענוח מתבצע על ידי חישוב ופענוח כדי לקבל את ואז .
אף על פי שהומצאה לפני כשלושים שנה, נותרה מערכת מקאליס בטוחה והיא יעילה מאוד, אך סובלת מבעיה מהותית והיא מפתחות עצומים (תקציר אורכי המפתחות של האלגוריתמים השונים מובא בטבלה להלן).
הצפנה מבוססת משוואה רבת משתנים
אלגוריתם HFE (קיצור של Hidden Fields Equations) הוא מערכת הצפנה רבת משתנים (multivariate cryptography) המבוססת על מערכת משוואות ריבועיות מרובות נעלמים, שהדיעה הרווחת שהיא תהיה עמידה נגד התקפת מחשב קוונטי.
הרעיון הבסיסי העומד מאחורי הצפנה כזו הוא הקושי שבפתרון מערכת משוואות פולינומיות מרובת משתנים ממעלה שנייה או יותר, מעל שדה סופי שהיא בעיה NP-קשה או בעיית NP-שלמה.
נכון להיום הניסיונות לפתח מערכת הצפנה מבוססת משוואות ריבועיות מרובות משתנים לא צלחו.
ז'ק פטרין המציא ב-1997 חתימה דיגיטלית אסימטרית מעשית בשיטת Oil and Vinegar (הסתרת משוואות ריבועיות ב- נעלמים הנקראים "שמן" ו- נעלמים הנקראים "חומץ" מעל שדה סופי עם פונקציות ליניאריות סודיות, כאשר ).
שמיר וקיפניס הוכיחו שהיא אינה בטוחה.
וריאציה אחרת שלה הנקראת "Unbalanced Oil and Vinegar" שבה טובה יותר וביטחונה הוא שאלה פתוחה.
הבעיות מרכזיות בתורת הסריגים להן ישנן שימושים בקריפטוגרפיה הן בעיית הווקטור הקצר ביותר (shortest vector problem) ובעיית הווקטור הקרוב ביותר (closest vector problem).
אלגוריתם ההצפנה NTRU, אשר פותח בשנת 1996, הוא המוכר ביותר ומבוסס על בעיית הווקטור הקצר ביותר.
בשנת 2005 עודד רגב הגדיר את בעיית "למידה עם טעויות" (learning with errors) והוכיח כי בהינתן מחשב קוונטי, הבעיה שקולה אסימפטוטית למספר בעיות בתורת הסריגים, הנחשבות לבעיות קשות.
הרעיון הכללי הוא לבסס מערכת הצפנת מפתח ציבורי על הקושי בהבחנה בין פונקציות ליניאריות אקראיות המוסתרות על ידי כמות מועטה של "רעש" מפונקציות אקראיות אמיתיות.
רגב בנה פרוטוקול הצפנה באותו השם המבוסס על בעיה זו.
בעיית הלמידה עם טעויות ניתנת להכללה מעל מודולים, והמקרה הפרטי המעניין ביותר הוא מעל חוגים (ring learning with errors), מקרה נוסף בו ישנה הוכחה קוונטית לשקילות הבעיה לבעיות קשות בתורת הסריגים.
פרוטוקולי הצפנה מעניינים במיוחד הם פרוטוקול שיתוף מפתח ring learning with errors key exchange ואלגוריתם החתימה הדיגיטלית ring learning with errors signature.
חתימה דיגיטלית BLISS שפותחה ב-2015 אף היא מבוססת על הצפנת סריגים ונחשבת אך לא מוכחת כבטוחה בהנחה שבעיית הווקטור הקרוב ביותר קשה והיא מועמדת טובה להצפנה פוסט קוונטית.
הצפנה מבוססת איזוגניה היא נושא חדש שנמצא במחקר ועוסק במועמדים טובים להצפנת מפתח ציבורי פוסט-קוונטית המבוססת על הקושי בחישוב איזוגניה בין שני עקומים אליפטיים נתונים (ובאופן כללי, בין שני עקומים הייפר-אליפטים).
ישנם מספר מועמדים לפרוטוקולי שיתוף מפתח מבוססי איזוגניות.
תחילה הוצע להשתמש בעקומים אליפטיים רגילים (ordinary), אך הפרוטוקול איננו יעיל (מהיר) מספיק וכמו כן נמצא אלגוריתם קוונטי למציאת איזוגניות בין עקומים רגילים בעל סיבוכיות זמן תת-מעריכית.
כעת המחקר מתמקד בעקומים סופר-סינגולרים, המאפשרים פרוטוקל יעיל יותר וכן זמן הריצה של האלגוריתמים הידועים לשבירת הצופן הוא מעריכי.
ב-2011 פותח אלגוריתם Supersingular isogeny Diffie–Hellman (בקיצור SIDH) הדומה לפרוטוקול העברת מפתח דיפי-הלמן הנפוץ כיום בשימוש במערכות אבטחה רבות בשתי גרסאות DHE ו-ECDHE (בעקום אליפטי).
האלגוריתם פותח מתוך מטרה שיהיה מועמד ראוי להחלפת הפרוטוקולים הקודמים ובעל תכונות טובות כמו מפתח קצר וביטחון לפנים (forward secrecy).
פרוטוקול נוסף הצובר עניין הוא CSIDH המוגדר מעל עקומים סופר-סינגולרים מיוחדים החולקים מספר תכונות עם עקומים רגילים.
פרוטוקול זה יעיל מאוד הן בזמן ריצתו והן בגודל המפתחות.
בטבלה הבאה מובאים אורכי מפתחות ציבוריים ופרטיים של מספר אלגוריתמים פוסט-קוונטיים:
מהיבט של יעילות העברת מפתח ציבורי ברשת האינטרנט האלגוריתמים SIDH, LWE ו-NTRU עדיפים.
לעומתם מקאליס ו-Rainbow אינם יעילים במיוחד בסביבה בה יש צורך להעביר מפתח.
מתוך האלגוריתמים המנויים רק LWE ו-SIDH תומכים בביטחון לפנים.
גם בהנחה שמחשבים קוונטיים לא יהיו מעשיים בחמש עשרה השנים הבאות, קיימות שלוש סיבות טובות מדוע לרכז מאמצים כיום בפיתוח אלגוריתמים פוסט-קוונטיים:
יעילות עשויה להיות אופציונלית עבור יחידים אך לא באה בחשבון עבור ארגונים גדולים.
העובדה שגוגל מעבירה לפעמים בקשות חיפוש ב-HTTPS לתקשורת לא מאובטחת מעידה יותר מכל כמה בעיית היעילות קריטית.
דרוש זמן מחקר ופיתוח לגילוי שיטות חדשות בטוחות ויעילות יותר, על מנת שהמערכות הללו יתאימו לשימוש מאסיבי.
חלק מהאלגוריתמים המוצעים חדש יחסית וחלקם התגלו כלא בטוחים.
כדי לרכוש את אמון הציבור בהם יש צורך שקריפטואנליסטים יחקרו את האלגוריתמים המוצעים לאורך זמן רב, יגלו התקפות, יישמו לקחים, יבצעו שיפורים וחוזר חלילה ולשם כך יש צורך להכיר את נושא המחשבים הקוונטיים היטב.
בדרך כלל פרימיטיבים קריפטוגרפיים אינם ראויים לשימוש כשלעצמם אלא רק כחלק ממערכת שלמה ובטוחה.
הניסיון המר מלמד ששיטות הצפנה אפילו שהיו בטוחות כשלו רק בשל יישום לקוי.
דרוש זמן לקהילה הקריפטוגרפית כדי לפתח, לתקנן, לקודד ולהשמיש מערכות אבטחה פוסט-קוונטיות.
בקריפטוגרפיה, הצפנת סף (threshold cryptography) היא מערכת הצפנה המבוצעת בין שולחים או מקבלים מרובים התורמים במידה שווה למערכת, בניגוד למערכת הצפנה בין שולח יחיד למקבל יחיד.
סכמת הצפנה תקרא הצפנת-סף אם לצורך הצפנה או פענוח נדרשים לפחות משתפי פעולה מתוך מורשים כדי שההצפנה או פענוח יצליחו.
כאשר הוא מספר המורשים לשלוח או לקבל את המסר המוצפן ואילו נקרא "מספר סף" הקובע את כמות המשתתפים המינימלית הנחוצה ואילו פחות ממספר זה ההצפנה או הפענוח יכשלו כי אין מספיק מידע להשלמתם.
כמו כן ניתן להגדיר חתימה דיגיטלית עם סכמת סף, באופן שיידרשו לפחות חותמים מתוך מורשים כדי שהחתימה תהיה תקפה.
המטרה של הצפנת סף היא להגן על מידע (או חישוב רגיש) בצורה בטוחה ועמידה בפני תקלות, על ידי הפצת המידע או החישוב על פני מספר מחשבים המחלקים פעולה ביניהם.
מצד אחד מובטחת סודיות גבוהה כי החלק המצוי בידי כל אחד מהם בנפרד אינו מספיק כדי לגלות את המידע.
ומצד שני מובטחת אמינות גבוהה, גם אם חלק מהשרתים לא יהיו זמינים עקב תקלה, ניתן יהיה להשיג את המידע משיתוף פעולה של האחרים.
חלוקת סוד היא מקרה פרטי של הצפנת סף.
שיטת חלוקת סוד מאפשרת לחלק פיסת מידע סודי למספר משתתפים בדרך כזו שהדרישות הבאות מתקיימות:
אף קבוצה של מיעוט לא הגון (שמספרה נמוך ממספר הסף שנקבע מראש) לא תוכל לשתף פעולה כדי לחלץ את הסוד המשותף.
כאשר דרוש לגלות את הסוד, קבוצת מורשים כלשהי מתוך כלל המורשים, שמספרה גדול אפילו באחד ממספר הסף שנקבע תהיה מסוגלת לחלץ את הסוד.
הגדרה כללית של הצפנת סף מורחבת גם לחישוב פונקציה משותפת.
הרעיון הוא שפעולות רגישות מאוד כגון פענוח מידע קריטי או חתימה על מסמכים רגישים, ניתנים לביצוע על ידי קבוצת משתתפים שמספרה נקבע מראש ולא אחד פחות.
אם קבוצת משתתפים מינימלית משתפת פעולה הם יצליחו לבצע את החישוב.
אפילו אם האחרים מתנגדים הם לא יוכלו למנוע אותו.
רוב סכמות ההצפנה המודרניות מוגדרות בין שולח ומקבל.
אך ישנם מקרים שבהם נדרשים מספר משתתפים.
הדוגמה הראשונה למערכת כזו הופיעה בתקן EES של NIST שנקרא שבב קליפר (clipper chip).
במערכת זו צד שלישי מוסמך (במקרה זה ארגון ממשלתי כמו NSA) מקבל חלקים (shares) של מפתחות כל המשתמשים במערכת הצפנה מסוימת המיושמת בחומרה באופן כזה שבמידת הצורך רשויות החוק יכולים בצו שופט לקבל לידיהם את המפתח הזה ואיתו לפענח מידע ספציפי מבלי להדליף כל מידע אחר שאינו נחוץ במישרין.
רבים מביעים התנגדות לשיטה זו בטענה שהיא פוגעת בפרטיות המשתמשים ואינה משיגה את יעדה.
סכמת סף שימושית גם במקרים אחרים למשל; מסמכים הצריכים חתימה של מספר מורשים בארגון, מערכות קריטיות הדורשות אישור של מספר ממונים בעלי דרגה בכירה כדי להפעילן או תהליכים בהם נדרשת הכרעת רוב וכדומה.
מספר פסאודו אקראי לצורך מערכת הצפנה נוצר במשותף על ידי מספר משתמשים, כך שכל אחד מהם תורם תרומה שווה להכנתו.
פרוטוקול אפס ידיעה שבו מספר סף של משתתפים מוכיחים יחד ידיעת סוד מסוים מבלי להדליף מאומה למשתתפים האחרים או לכל אדם אחר כל מידע נוסף מלבד עצם ההוכחה.
זהו קוד אימות מסרים שבו נדרשים מספר סף של משתתפים כדי לייצר תג אימות למסמך מסוים.
בכל המקרים הפרוטוקולים הללו צריכים לעמוד בפני קריפטואנליזה, גם במקרה החמור כאשר אחד המשתתפים הלגיטימיים מבפנים מנסה לסייע לגורם חיצוני לפרוץ את המערכת.
בפעולות מקוונות ברשת כמו פעולה פיננסית, באופן כללי ההנחה היא שהשרת שאנו מתקשרים עמו פועל בהגינות, אך אי אפשר להוכיח זאת מעל לכל ספק, הדרך היחידה היא באמצעות חתימה דיגיטלית של צד שלישי שעליו אנו סומכים כמו רשות מאשרת (certification authority).
הצפנת סף מאפשרת לבנות מערכת אימון טובה יותר.
למשל רשות מאשרת היא שרת המנפיק תעודות המבטיחות שמפתח ציבורי מסוים שייך לבעליו המוצהר.
אם נסמוך רק על שרת אחד, במקרה של פריצה מוצלחת לשרת כל התעודות שהשרת הנפיק לא בטוחות.
אם מחלקים את הנפקת התעודות על פני כמה שרתים ממזערים את הסיכון שבפריצה לאחד מהם.
כי כעת המתקיף צריך לפרוץ לכל השרתים כדי להפיק תועלת מההתקפה שלו.
היות שתעודת מפתח ציבורי היא למעשה חתימה דיגיטלית, ליישום מערכת כזו נדרשת חתימה דיגיטלית עם סף.
קיימות שתי גישות עיקריות לבניית סכמת סף, האחת היא שימוש בתכונת הומומורפיזם של אלגוריתם ההצפנה.
הרבה סכמות הצפנה עונות על הגדרה זו באופן חלקי, כמו RSA, אל-גמאל, הצפנת פאיי ועוד.
לדוגמה אם נתונה הפונקציה המקבלת מפתח וקלט שבמקרה של הצפנה הוא טקסט-מוצפן המיועד לפענוח ובמקרה של חתימה דיגיטלית מסמך לחתימה.
כעת אם נתונה פונקציית מעטפת המקיימת אזי היא תקרא הומומורפית אם מתקיים:
כאשר ו- הם אלמנטים של חבורה אבלית .
לדוגמה הצפנת אל-גמאל מקיימת את התנאי האמור.
אפשר להפוך כל מערכת הצפנה להצפנה הומומורפית חלקית או מלאה וממנה לבנות סכמת סף.
כשהמטרה היא שהמערכת תהיה בטוחה לפחות כמו הסכמה המקורית.
הגישה השנייה היא חלוקת סוד כפלית כמו סכמת חלוקת סוד של עדי שמיר שמתאימה להרבה אלגוריתמים אסימטריים אך לא לכולם.
בסכמת חלוקת סוד מפתח הצופן פשוט מחולק בין המשתתפים באופן כזה שרק שיתוף פעולה של לפחות מהם מאפשר לשחזר את המפתח ואיתו לפענח את ההצפנה.
כאשר נדרשים לשחזר את הסוד, כל משתתף מוסר את השתף שלו לדילר מרכזי שתפקידו "להכפיל" את כל החלקים או הכמות המינימלית שלהם כדי לשחזר את הסוד.
באופן כללי משתמשי האינטרנט לא זקוקים לסכמת סף אלא בעיקר גופים גדולים המחזיקים במידע סודי בעל ערך רב.
אולם בשל ריבוי פריצות של האקרים לשרתים וגנבת סיסמאות נוטים כיום ארגונים קטנים יותר לנצל טכנולוגיות מתקדמות להגנה על סיסמאות.
חברת RSA פרסמה ב-2012 על כוונתה להפיץ טכניקה להגנה על סיסמאות המנצלת הצפנת סף, במטרה להילחם בתופעה.
הרעיון הוא שמפתח ההצפנה מפוצל לשני חלקים המאוחסנים במקומות שונים.
במצב זה האקר שמנסה לפרוץ למערכת כדי לגנוב ססמאות נדרש כעת לפרוץ לשתי מערכות מחשב שונות.
באופן כללי מצב כזה מקשה עליו את המלאכה.
כמובן שאפשר להרחיב את המערכת לנקודות חלוקה נוספות.
גישה יותר כללית של סכמת סף נקראת "מבנה גישה" (Access Structure).
נניח ש- הוא קבוצה של משתתפים מבנה גישה הוא תת-קבוצה של קבוצת החזקה .
כאשר כל אלמנט של נקרא "רשאי" כלומר יש לו גישה לסוד המשותף.
נקרא מונוטוני אם כאשר , אז .
מבנה יריב הוא המבנה המשלים המסומן .
הצפנה מקצה-לקצה היא מערכת תקשורת שבה רק הצדדים המשתתפים בשיחה יכולים לקרוא את ההודעות.
למעשה, נמנעת האזנה של צד שלישי וגורמים שאינם מהווים חלק מן השיחה - כגון: ספקי אינטרנט, ספקי תקשורת סלולרית, ואפילו מספק התקשורת עצמו, מלגשת למפתחות ההצפנה הדרושים כדי לפענח את השיחה.
מערכות אלו נועדו למנוע כל ניסיון של מעקב או שינוי של המידע המועבר משום שאף צד שלישי לא יכול לפענח את הנתונים שמועברים או מאוחסנים.
למשל, חברות שמיישמות הצפנה מקצה לקצה אינן יכולות למסור טקסטים של לקוחותיהם לרשויות.
במערכת הצפנה מקצה לקצה מפתחות ההצפנה חייבים להיות ידועים רק לצדדים המתקשרים.
כדי להשיג מטרה זו, מערכות הצפנה מקצה לקצה יכולות להצפין מידע באמצעות מחרוזות מידע הנקראים סוד משותף מראש (PGP), או סוד חד פעמי () הן גם יכולות לעשות שימוש בפרוטוקול דיפי-הלמן (OTR, סיגנל).
מספר דוגמאות למערכות שכוללות הצפנה מקצה לקצה כברירת מחדל כוללות את: PGP, OTR, וואטסאפ, iMessage ,סיגנל, FaceTime ועוד.
הצפנה מקצה לקצה נחשבת לבטוחה מכיוון שהיא מורידה את מספר הצדדים שיכולים להתערב או לפגום בהצפנה.
במקרה של מסרים מיידיים משתמשים יכולים להשתמש בתוכנת צד שלישי (כגון: פידג'ין) כדי ליישם מערכות הצפנה מקצה לקצה (כגון: OTR) על גבי פרוטוקול שאינו מאפשר הצפנה מקצה לקצה.
מספר מערכות שאינן מיישמות הצפנה מקצה לקצה, למשל: ו־ מתארות את עצמן ככאלה המציעות הצפנה "מקצה-לקצה" בשעה שהן לא מספקות הצפנה מקצה לקצה.
מערכות אחרות כגון: טלגרם ו־Google Allo בוקרו על כך שהן מציעות הצפנה מקצה לקצה אך לא מאפשרות אותה כברירת מחדל.
חברות עשויות מרצונן או שלא מרצונן להכניס דלת אחורית לתוכנה שלהן שתאפשר להן לגשת למפתחות ההצפנה וכך לעקוף את מערכת ההצפנה ולפענח את ההודעות לגמרי.
בשנת 2013 מידע שהודלף על ידי אדוארד סנודן, הראה שיש דלת אחורית בתוכנת סקייפ שמאפשרת לחברת מיקרוסופט לשלוח את כל תוכן הודעות המשתמשים לסוכנות לביטחון לאומי של ארצות הברית, למרות שתוכן ההודעות היה מוצפן מקצה לקצה מבחינה רשמית.
אם קיימים גיבויים למידע המוצפן, אם הם עצמם לא מוצפנים וניתנים לקריאה על ידי שירות הגיבויים, אפשר לגשת למידע בצורה הזאת וכך לעקוף את ההצפנה מקצה לקצה.
לדוגמה, הגיבוי של whatsapp, שנשמר בGoogle Drive או בiCloud לא מוצפן כברירת מחדל.
הצפנת תרמיל גב היא מערכת הצפנת מפתח ציבורי שביטחונה מבוסס על הקושי המשוער שבפתרון בעיית תרמיל הגב שהיא בעיה NP-קשה.
הצפנת תרמיל הגב הייתה הניסיון הראשון לבסס מערכת הצפנה על בעיה NP-קשה ואף על פי שהרעיון קיים כבר מאז 1978 רוב המערכות הקיימות שפותחו על בסיס זה נפרצו ולכן אינן בשימוש מעשי, אלא נחקרות לצורך אקדמי בלבד.
השיטה הראשונה והמפורסמת ביותר היא הצפנת תרמיל גב של מרקל והלמן שפותחה ב-1978 על ידי רלף מרקל ומרטין הלמן.
היא הייתה מערכת מפתח ציבורי מהראשונות שפותחו ופורסמה באותה שנה שבה פורסמה RSA.
מערכת זו נפרצה לחלוטין בכמה התקפות מפורסמות שהראשונה שבהן הייתה של שמיר, אחריו פיתחו אדלמן, אודליצקו ולגריאס בנפרד קריפטואנליזה הנקראת התקפת צפיפות נמוכה לשבירת הצפנת מרקל-הלמן בזמן פולינומי.
כל הגרסאות שהומצאו מאז כולל גרסת שור-ריבסט המכילה צפיפות גבוהה יחסית (הגדרה בהמשך), נמצאו לא בטוחות וניתנות לשבירה בזמן פולינומי או בזמן שהוא נמוך בהרבה מכוח גס עם הפרמטרים שהומלצו על ידי המפתחים.
במרבית המקרים שינוי הפרמטרים לא יועיל במידה ניכרת ולכן מערכות אילו לא נכנסו לשימוש מעשי כלל למעט מערכת חדשה יחסית של Nasako-Murakami מ-2006 שעדיין לא התגלתה קריפטואנליזה יעילה שלה.
העניין בהצפנת תרמיל הגב נובע מהעובדה שהיא נחשבת פוסט-קוונטית ולכן תהיה אטרקטיבית אם תמצא דרך בטוחה ליישמה.
אם תמצא דרך כזו הרי שהמערכת אמורה לספק ביטחון גם לנוכח איום קריפטואנליזה על מחשב קוונטי כאשר יהיה מעשי.
זאת בניגוד לשיטות כמו RSA ו-DSA המסתמכות על בעיית פירוק לגורמים ובעיית הלוגריתם הבדיד, אותם ניתן יהיה לשבור בקלות בהינתן מחשב קוונטי באמצעות אלגוריתם שור.
בעיית תרמיל הגב קשורה בקשר הדוק עם סריגים.
לאחר פרסום אלגוריתם LLL התברר שמערכת הצפנה מבוססת בעיית תרמיל הגב סובלת מבעיה מהותית.
באופן כללי אם כאשר הוא פרמטר ביטחון (מפורט בהמשך) אז אלגוריתם לצמצום סריגים (Lattice reduction algorithm) מאפשר לגלות את הטקסט המקורי מתוך הטקסט המוצפן ללא ידיעת המפתח בזמן פולינומי.
מאידך אם אז המפתחות מגיעים לממדים עצומים בערך 176KB למפתח מה שהופך את המערכת לבלתי יעילה.
בעיית תרמיל הגב הנקראת גם בעיית הסכומים החלקיים - מהיבט קריפטוגרפי מוגדרת כדלהלן:
נתונה הסדרה המכילה איברים שלמים, כאשר הוא פרמטר ביטחון (למשל ):
ונתון שלם חיובי הנקרא 'תרמיל גב'.
הבעיה היא לגלות האם קיימת תת-קבוצה של איברים ב- שסכומה הוא .
במילים אחרות המטרה היא לגלות את הווקטור המקיים:
אפשר לראות בניסוי וטעייה שהפתרון הוא תת-הסדרה וקל לראות שזהו הפתרון היחיד במקרה זה.
דרך אחרת להציג את הפתרון היא הווקטור (כלומר הווקטור מכיל אחדים בכניסות המתאימות לאיברים הנכללים בסכום התרמיל ובכל היתר אפסים) במילים אחרות, אם ממספרים את כל האיברים בסדרה משמאל לימין אז .
אפשר לפתור את הבעיה בכוח גס, פשוט על ידי ניסוי כל האפשרויות של הווקטור עד למציאת הווקטור הנכון.
סיבוכיות הפתרון היא מסדר גודל של , אולם אפשר לחתוך את סיבוכיות הפתרון בפקטור של שנים על ידי אלגוריתם ההתנגשות הבא.
אלגוריתם התנגשות לפתרון בעיית תרמיל הגב הכללית
אם נתונה בעיית תרמיל-גב עם הפרמטרים באורך ושלם אפשר לפעול כדלהלן:
מכינים קבוצת שלמים כך שמתקיים , כלומר קבוצת כל האיברים הנמוכים מחצי של וכן,
מכינים קבוצת שלמים כך שמתקיים ,
מחשבים את רשימת הערכים הבאים: כלומר רשימת כל הסכומים האפשריים ב-,
באותו אופן מחשבים את רשימת הערכים: ,
ממיינים את הקבוצות לפי סדר מספרי ומחפשים התאמה כך שתתקבלנה שתי תת-רשימות ו- המקיימות: .
רשימות אילו נותנות למעשה את הפתרון לבעיית תרמיל הגב כי
מספר האלמנטים ב- וב- הוא לכל היותר כל אחת ולכן זמן הריצה של האלגוריתם הוא כאשר הוא ערך קטן המייצג את התקורה הנוספת הנובעת מחישוב הרשימות ומיונן.
בעיקרון אם גדול הפתרון המתואר אינו יעיל ולכן הבעיה הכללית מוגדרת קשה, אולם אינה מתאימה לקריפטוגרפיה כיוון שלא קיימת "דלת צונחת", אותו מידע סודי שהופך את פתרון הבעיה לקל מאוד למי שמחזיק בו ואילו עבור כל האחרים שאינם יודעים מהו הבעיה נותרת קשה.
דרך אחת להכניס דלת צונחת היא להשתמש בבעיית תרמיל הגב עם תכונה מיוחדת שפתרונה קל.
הרעיון של מרקל והלמן היה להשתמש בתרמיל גב המורכב מסדרה מונוטונית עולה שבה כל איבר גדול לפחות פי שניים מקודמו.
בניסוח רשמי זוהי סדרה של איברים שלמים עם התכונה הבאה:
היא נקראת סופר-עולה (superincreasing) כיוון שעבור כל מתקיים:
במקרה זה פתרון בעיית תרמיל הגב קל מאוד לפי האלגוריתם הבא: מבצעים רקורסיה שמתחילה באיבר האחרון () כלפי מטה עד האיבר הראשון () ובודקים עבור כל : אם מציבים ומחסרים אחרת מציבים וממשיכים עד ש- (בהנחה שפתרון קיים).
לדוגמה הסדרה היא סופר עולה, נניח שנתון השלם מייצגים את כסכום איברים בסדרה כדלהלן: תחילה היות ש- לכן ומחליפים את ב-.
בשלב הבא היות ש- מציבים .
בשלב הבא רואים ש- לכן ו-.
היות ש- אנחנו יודעים ש- ולבסוף כי ועוצרים כי .
הצפנת תרמיל גב של מרקל והלמן
מרקל והלמן הציעו ב-1978 מערכת הצפנה המבוססת על בעיית תרמיל הגב עם סדרה סופר עולה שאותה מסתירים באמצעות שקילויות.
כדי לייצר מפתח פרטי ומפתח ציבורי אליס בוחרת סדרה סופר עולה בעלת איברים כך שעבור כל מתקיים וכן בוחרת שני שלמים גדולים ו- המקיימים:
וכן כאשר היא פונקציית מחלק משותף מקסימלי, בדרך זו מובטח של- יהיה הופכי כפלי מודולו .
אליס מכינה סדרה שאינה סופר עולה על ידי הכפלה ב- כך:
הסדרה היא המפתח הציבורי של אליס שהוסתר על ידי הכפל ב- מודולו ואילו המפתח הסודי כולל את הסדרה והשלמים ו- בגלל החשבון המודולרי לא קל לנחש את או מתוך המפתח הציבורי.
אם בוב רוצה להצפין את המסר עבור אליס הוא משתמש במפתח הציבורי שלה ומחשב את
את הטקסט המוצפן הוא שולח לאליס.
לפענוח אליס פועלת כדלהלן, תחילה מחשבת את דהיינו מכפילה את בהופכי הכפלי של מודולו ואז משתמשת בסדרה הסופר עולה כדי לפתור את בעיית תרמיל הגב עם .
הסיבה שהפענוח נכון היא בשל הזהות הבאה:
היות ש- מובטח לאליס שתקבל תוצאה מדויקת ולא רק שקילות כלשהי מודולו .
נניח שאליס בחרה סדרה סופר-עולה סודית מהדוגמה הקודמת וכן .
כעת הסדרה המוסוות שלה תהיה הכפלה של ב- כך שמתקבל:
שימו לב שגם אם ממיינים את איברי M בסדר עולה הסדרה שהתקבלה רחוקה מלהיות סופר-עולה ולכן יהיה קשה לפתור את בעיית תרמיל הגב בסדרה זו לעומת הסדרה .
כעת אם בוב מעוניין לשלוח לאליס את המסר , הוא מצפין אותו תחילה באמצעות הכפלה ב- כך שמתקבל:
כאשר אליס מקבלת את הטקסט המוצפן היא מכפילה אותו תחילה בהופכי של מודולו שהוא ומתקבל:
כעת נותר לאליס להשתמש באלגוריתם המתואר לעיל כדי לפתור את בעיית תרמיל הגב בסדרה עם הערך וכך מחלצת את הטקסט המקורי .
בעיית תרמיל הגב הכללית נחשבת ל-NP-קשה והיא מהווה מועמדת טובה לפונקציה חד-כיוונית.
אולם לצורך קריפטוגרפי יש צורך גם בדלת צונחת שהיא המידע הנסתר המאפשר למקבל הלגיטימי לפתור את הבעיה בזמן פולינומי.
הגרסה הראשונה של הצפנת תרמיל הגב שהסתמכה על סדרה סופר-עולה הכילה כמה חסרונות מהותיים שהעיקרית שבהן היא העובדה שתרמיל גב מכיל צפיפות נמוכה מדי מה שגורם לנקודת תורפה היות שבמקרה של תרמיל גב בעל תכונה זו קיימים אלגוריתמים יעילים לפתרון הבעיה.
במרוצת הזמן הוצעו מספר רב של גרסאות משופרות שנועדו להתמודד עם הבעיות הללו בין היתר על ידי שימוש בתרמילי גב מרובים או הסתרה של תרמיל הגב באמצעות חשבון מודולרי ואלגברה בחוג הפולינומים.
ב-1985 פורסם בנפרד על ידי בריקל, לגריאס ואודליצקו אלגוריתם LO המסתמך על אלגוריתם צמצום סריגים (LLL) שמצליח לפתור את הבעיה כמעט תמיד בזמן פולינומי בתנאי שצפיפות תרמיל הגב נמוכה מ-0.6463. צפיפות תרמיל הגב מוגדרת כדלהלן:
אלגוריתם CJLOSS משפר את החסם לגריאס-אודליצקו ל-.
היות שהאלגוריתמים האמורים מסתמכים על צפיפות תרמיל הגב הם נקראים באופן כללי "התקפת צפיפות נמוכה".
אולם הבעיה הכללית, דהיינו אם צפיפות תרמיל הגב גבוהה מהגבול האמור נותרה בעיה קשה.
הרעיון של אלגוריתם LO הוא להמיר את הבעיה לבעיה אחרת מתורת הסריגים הנקראת בעיית מציאת הווקטור הקצר ביותר (SVP) שהיא בעיה קשה מאוד.
אף על פי שלא קיים אלגוריתם פולינומי ל-SVP, מעשית אלגוריתם LLL של האחים לנסטרה ולובאז' מצליח לפתור את בעיית הווקטור הקצר בקירוב טוב, הרבה יותר ממה שמציע הגבול התאורטי.
האמור הוא אם מתבצעת קריאה אחת לאורקל SVP.
אולם במקרה של קריאות מרובות קיים שיפור שלו שנקרא אלגוריתם CJLOSS+ שמשפר את התוצאות האמורות מהיבט אסימפטוטי.
בקריפטוגרפיה, הצפנת אוקמוטו-אושיאמה המסומנת בקיצור OU, היא מערכת הצפנת מפתח ציבורי הומומורפית חלקית שהתגלתה ב-1998 על ידי Tatsuaki Okamoto ו-Shigenori Uchiyama מחברת ניפון טלגרף אנד טלפון (NTT).
היא שונה מ-RSA ומדיפי-הלמן בכך שזאת מערכת הצפנה מוכחת כבטוחה בהנחה שפירוק לגורמים היא בעיה קשה והיא פועלת מעל חבורת אוילר כאשר וכן ו- ראשוניים.
OU היא תמורה חד-כיוונית עם דלת צונחת כאשר הדלת הצונחת היא אלגוריתם יעיל לחישוב לוגריתמים בתת-חבורה ספציפית הנקראת חבורת p.
החד-כיווניות שלה נובעת מבעיית פירוק לגורמים של המודולוס וכן אפשר להוכיח שהטקסט המוצפן בטוח סמנטית כולו נגד יריב פסיבי.
כיוון ש-OU הסתברותית הטקסט המוצפן נראה אקראי, כי כל טקסט קריא יכול להיות מוצפן עם אותו מפתח באופן שונה בכל פעם.
הביטחון הסמנטי מסתמך על הקושי שבהבחנה בין לבין כאשר ו- אקראיים ובלתי תלויים ב-.
בעיה זו נחשבת לבעיה קשה והיא שקולה לבעיית השארית הריבועית וכן שארית מסדר גבוה יותר שנחשבות לבעיות קשות.
שיטת OU נחשבת ליעילה יותר בהשוואה ל-RSA להצפנה של ערכים קטנים כמו מפתח הצפנה והיא הומומורפית בגלל התכונה הבאה:
תכונה זו שימושית במקומות בהם נדרשת הצפנה אנונימית כמו בהצבעה דיגיטלית ובמטבע דיגיטלי.
החסרונות של שיטת OU הם: התנפחות הטקסט המוצפן וכן העובדה שהיא אינה בטוחה נגד יריב אקטיבי לפי מודל התקפת מוצפן-נבחר.
אפשר ליישם טכניקת ריפוד דומה לזו שנעשתה ב-RSA כדי לקבל ביטחון סמנטי במסגרת מודל אורקל אקראי.
כמו כן שיטה זו חשילה כי זה נובע מהתכונה הייחודית שלה.
לא ידוע אם הקושי שבפירוק שונה מהקושי שבפירוק לכן יכול להיות באורך זהה בשני המקרים (למשל 2046 סיביות כאשר כל ראשוני באורך 682 סיביות).
נתונה החבורה (כאשר וכן ו- ראשוניים), הפונקציה הלוגריתמית מוגדרת מעל -סילו - תת-חבורה של החבורה הכפלית .
היא חבורה ציקלית מסדר לכן .
הפונקציה עבור קלה לחישוב והיא:
הפונקציה נקראת "פונקציה לוגריתמית" של והביטוי שקול ל- מעל מודולו .
היא הומומורפית ביחס לפעולות הכפל והחיבור כי:
יהי פרמטר ביטחון (למשל ), בוחרים שני ראשוניים אקראיים ו- כאשר ומחשבים את .
בוחרים אלמנט אקראי כך שהסדר של הוא .
לא קשה למצוא איבר כזה כי וכן כאשר gcd היא פונקציית מחלק משותף מקסימלי (לכן כל מה שצריך זה לוודא ש-).
ניתן לחישוב בכל שלב מתוך ו- והוא נועד רק להקל על החישובים בצד המצפין, אין חובה לשלוח אותו.
בהינתן טקסט גלוי באורך סיביות לכל היותר.
בוחרים שלם אקראי ומחשבים את:
תחילה מחשבים את ואז הטקסט הגלוי מתקבל על ידי
דרך אחרת להציג זאת (הכפלה בהופכי כפלי במקום חילוק):
זה נכון כי לפי חוקי הלוגריתמים הוא במובן מסוים הלוגריתם של בבסיס , לפי זה אם נתון:
כל מה שצריך כדי לחלץ את זה לקחת לוגריתם בבסיס .
את זה אפשר לעשות על ידי מודולו .
יהי מייצר כאשר ו- ראשוניים.
בעיית הפירוק בהינתן למצוא את קשה אם עבור כל אלגוריתם פולינומי הסתברותי ועבור כל קבוע עם גדול מספיק מתקיים:
כמו כן בהינתן מייצר ו- מפתח ציבורי, הטקסט המוצפן, היפוך הפונקציה קשה אם עבור כל אלגוריתם פולינומי הסתברותי ועבור כל קבוע עם גדול מספיק מתקיים:
קיימת הוכחה ששתי הבעיות המתוארות שקולות.
אם מצליחים להפוך את פונקציית ההצפנה אז אפשר לפרק את לגורמים.
בכך מוכיחים שההצפנה בטוחה בהנחה שבעיית פירוק לגורמים קשה.