tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
זאת משיגים על ידי הוספת פסאודו-אקראיות לתהליך ההצפנה בדומה להצפנת בלום-גולדווסר.
על כל פנים ההגדרה תקפה רק במצב פסיבי ואינה מתמודדת עם איום אקטיבי שבו המתקיף יכול 'להזריק' הודעות, לחסום, לשכפל (replay) או לשנות את תוכנן.
ההגדרה של CCA כפי שהוצגה לראשונה על ידי ראקוף וסימון, ידועה כהגדרה החזקה ביותר של ההתקפה, היא ישימה כנגד כל סכמת הצפנה וכוללת גם איום אקטיבי.
המודל של ראקוף וסימון מניח לצורך הדיון שבאפשרות התוקף לפנות ל'אורקל פענוח' היפותטי.
אליו הוא יכול להפנות שאילתות פענוח מלא או חלקי של כל טקסט מוצפן לפי בחירתו מלבד הטקסט המותקף.
ההגדרה המחמירה מחייבת שהתוקף לא יוכל להשיג בדרך זו כל מידע מועיל שיעזור לו בפענוח הטקסט המותקף.
דולב, נאור ודוורק הציעו הגדרה מחמירה יותר כנגד התקפת מוצפן-נבחר אקטיבית הנקראת 'אי-חשילות', שבה התוקף מנסה להשתמש במידע הנוסף לא רק על מנת לפרוץ את הטקסט המוצפן אלא אפילו כדי ליצור טקסט מוצפן אחר כך שקיים יחס או קשר כלשהו בין הטקסט המקורי שלו והטקסט המקורי המותקף וזאת מבלי לפענחו.
בעיית הכרעת דיפי-הלמן ניתנת להצגה באופן הבא: נתונה חבורה מסדר ראשוני גדול.
ההתפלגות R של רביעיות אקראיות ,
ההתפלגות D של הרביעיות כאשר אקראיים ואילו וכן עבור אקראי כלשהו.
הבעיה היא להכריע בשאלה האם ניתן להבחין בהבדל סטטיסטי משמעותי כלשהו בין שתי ההתפלגויות המתוארות.
אם נחליף את הערכים הללו בערכים: , אפשר לצמצם את בעיית ההכרעה המתוארת לבעיית דיפי-הלמן בהינתן חשב את וכן לבעיית הלוגריתם הבדיד שהיא חישוב מתוך (מודולו ).
כאן לצורך הבעיה יכול להיות קבוע.
לכן בעיית הכרעת דיפי-הלמן שקולה לבעיה הכללית, כלומר במקרה הגרוע כאשר נתונים קשה להכריע עם שגיאה הסתברותית זניחה אם .
בעיית לוגריתם בדיד והגרסאות המנויות ידועות כבעיות קשות שטרם נמצא להם פתרון פולינומי יעיל.
קיים מודל המציע ביטחון סמנטי דומה, שיכול להיות מושתת על כל פונקציה חד-כיוונית עם דלת מלכודת.
בוחרים שלמים אקראיים וכן את הערכים האקראיים .
המפתח הפומבי הוא הסט: ופונקציית גיבוב ידועה ומוסכמת H.
והמפתח הפרטי הוא הסט: .
להצפנת המסר בוחרים שלם אקראי ומחשבים:
ממירים את תוצאת פונקציית הגיבוב לערך שלם ב-.
הטקסט המוצפן הוא הרביעייה: .
תחילה מחשבים את ערך הגיבוב
בודקים אם מתקיים , במידה שלא מחזירים הודעת שגיאה.
וכן לגבי ו- לכן הבדיקה בשורה 2 צריכה להחזיר אמת והטקסט הוא למעשה .
נניח שהראשוני והערכים האקראיים שנבחרו הם:
כעת להצפנת המסר תחילה נבחר
מחשבים את ואת ערך הגיבוב (כאן לצורך הדוגמה נלקח רק הבית הראשון של תוצאת פונקציית הגיבוב SHA-1).
הטקסט המוצפן לפי הסדר הוא: .
יש לציין שהמחיר לביטחון הסמנטי הוא התנפחות הצופן פי ארבעה מגודלו של .
הצפנת קריימר שופ היא מערכת מפתח ציבורי יעילה, הראשונה שהוכח לגביה שהיא בטוחה נגד התקפת מוצפן-נבחר בלי מודל אורקל אקראי, תוך שימוש במדדי סיבוכיות מקובלים.
הרעיון הבסיסי בהגדרת ביטחון מחמירה של מערכת מפתח ציבורי נקרא ביטחון סמנטי תחת התקפת מוצפן נבחר "אדפטיבית" המסומנת IND-CCA2. המושג הוטבע לראשונה על ידי סיימון וארקוף וההוכחה הראשונה שמערכת כזו קיימת ניתנה על ידי דני דולב ואחרים.
מעשית כבר היו קיימות מערכות בטוחות שמשתמשות במודל אורקל אקראי כמו OAEP של RSA המוכחות כבטוחות סמנטית לפי הגדרה זו.
אולם החידוש במערכת של קריימר ושופ שהיא אינה מנצלת את מודל האורקל האקראי.
קריימר ושופ הוכיחו שהמערכת שלהם בטוחה תחת הנחה שבעיית ההכרעה של דיפי-הלמן קשה וכן שהפונקציה חסינת התנגשויות.
אם קיים תוקף שמסוגל לשבור את המערכת תחת המודל IND-CCA2 הרי שאפשר לבנות אלגוריתם עם זמן ריצה דומה לתוקף שיוכל להכריע בבעיית דיפי-הלמן.
מכין זוג מפתחות פרטי וציבורי ושולח לתוקף את המפתח הציבורי, כעת הוא משתמש ברביעיית הערכים כדי לשלוח אתגר מוצפן לתוקף כדי שהוא יפענחו.
קריימר ושופ מראים שאם הרביעייה האמורה היא בעיית דיפי-הלמן אקראית הרי שהתוקף יצליח לפתור את הבעיה בהסתברות משמעותית.
לעומת זאת עם הרביעייה היא ערכים אקראיים ב- הרי שלתוקף יש יתרון אפס בסיכויי ההצלחה שלו לנצח במשחק.
ההבדל הזה בעצם מאפשר ל- לשבור את המערכת כיוון שהוא מפר את ההנחה היסודית של אי-יכולת הבחנה (IND) מכאן שהמערכת כולה בטוחה.
בעיקרון מערכת הצפנת קריימר-שופ יכולה להיות מוכחת כבטוחה בשתי דרכים.
הראשונה המתוארת לעיל שאינה עושה שימוש במודל אורקל אקראי והיא מוכחת תחת ההנחה שבעיית הכרעת דיפי-הלמן בקיצור DDH קשה וכן שפונקציית הגיבוב בטוחה והשנייה עם רעיון מודל אורקל אקראי.
התכונה המעניינת שלה היא שמודל האורקל האקראי מהווה מעין משוכה נוספת במקרה שההנחה הראשונה נכשלת.
לכן אפשר להוכיח את ביטחונה תחת הנחה קלה יותר כמו הקושי שבבעיית דיפי-הלמן החישובית.
הווריאציה שנקראת CS-Lite היא גרסה פשוטה יותר של מערכת קריימר-שופ ללא פונקציית גיבוב.
שהיא בטוחה לפי מודל פחות מחמיר שנקרא IND-CCA1. לפי מודל זה המערכת צריכה להיות בטוחה תחת התקפת מוצפן נבחר לא אדפטיבית שבה התוקף רשאי להגיש שאילתות לאורקל כל עוד לא קיבל לידיו את האתגר שהוא הטקסט המוצפן אותו הוא מעוניין לשבור.
מרגע שהגיע האתגר לידיו אין הוא רשאי יותר לפנות לאורקל.
ביטחון המערכת CS-Lite עונה להגדרה זו.
כמו קודם בוחרים אלמנטים אקראיים: כאשר ראשוני.
הפרמטרים הציבוריים של המערכת יהיו .
המפתח הפרטי הוא והמפתח הפומבי הוא .
בוחרים אלמנט אקראי חד פעמי .
הטקסט המוצפן הוא הצמד וכן ו-
הצפנה מרובה היא דרך להצפין מידע פעמים מרובות באמצעות מפתחות הצפנה שונים.
קַסְקָדָת (Cascade) הצפנה היא הצפנה מרובה באמצעות אלגוריתמים שונים (ומפתחות שונים).
הבחנה זו לא תמיד נעשית, לרוב מתייחסים להצפנה מרובה באופן כללי כאל קסקדה.
מקובל שהצפנה מרובה עם מפתח זהה לא רק שאינה מניבה ביטחון רב יותר אלא אף מחלישה אותו ברוב המקרים, משום שההצפנה השנייה עלולה לבטל את הראשונה חלקית או באופן מלא.
במיוחד בצפנים בהם ההצפנה והפענוח נעשים בפונקציה זהה.
בפנקס חד-פעמי למשל, הצפנה חוזרת עם אותו מפתח שקולה לפענוח וכן בכל צופן זרם.
יתרה מזו, סיבוכיות ההתקפה כנגד המערכת אינה עולה באופן ניכר, כיוון שהתוקף יודע שנעשה שימוש במפתח זהה (ההנחה היא תמיד שמספר ההצפנות, האלגוריתמים ששימשו להצפנה וכן סדר ההצפנה, ידועים לתוקף).
המסקנה היא שמפתחות ההצפנה צריכים להיבחר באופן שיהיו בלתי תלויים סטטיסטית.
כלומר לא תהיה דרך קלה להסיק מהו מפתח אחד בהינתן השני.
אחת הסיבות להצפנה מרובה היא הגברת ביטחון ללא צורך בפיתוח אלגוריתם חדש.
הטכניקה הזו נוצלה ב-DES משולש בשל העובדה שמפתח ההצפנה של DES קצר מאוד (רק 56 סיביות).
אולם יש להיזהר שהצירוף אינו גורם לאפקט הפוך מהמצופה.
יש לוודא שביטחון הצופן אכן השתפר וכי לא נוספו חולשות.
יש לציין כי הצפנים הסימטריים המודרניים כמו AES, מציעים ביטחון רב עם מפתח 256 סיביות לכן מהיבט של ביטחון, רק במקרים קיצוניים השקעה בהצפנה מרובה כדאית.
בהגדרה כללית כאשר מציינים 'צפנים' בלשון רבים, מתכוונים בעיקר להצפנה סימטרית או א-סימטרית חוזרת עם מפתחות הצפנה שונים, לא בהכרח עם אלגוריתמים שונים .
ישנן כמה תצורות עיקריות של הצפנה מרובה:
הצפנה עוקבת: בשיטה זו שנקראת גם קסקדה, פלט הצופן הראשון מהווה קלט לצופן השני והשני לשלישי וכן הלאה.
כאמור חובה על המפתחות להיות בלתי תלויים סטיסטית זה בזה.
המודל הזה אומץ על ידי הרשת החברתית האנונימית Tor, קיצור של The Onion Routing.
האנלוגיה ברורה, תהליך הפענוח דומה לקילוף בצל, כל שכבה מייצגת הצפנה אחת.
במקרה של TOR, המטרה אינה הגברת הביטחון אלא הסתרת זהות המשתמש על ידי הצפנת חבילת המידע ומקורה מספר פעמים באמצעות מפתחות הפומביים של השרתים האנונימיים.
תהליך הניתוב של חבילה עובר דרכם, כאשר כל אחד מהם מסיר שכבת הצפנה אחת בהתאם למפתח הפרטי שברשותו.
הצפנה מרוכבת (Product cipher): הוצעה לראשונה על ידי שאנון והיא בעצם הבסיס התאורטי לצפני בלוקים מודרניים.
הרעיון הוא שילוב לא ליניארי כלשהו של מספר טרנספורמציות לחיזוק הביטחון.
בשיטה זו אין מגבלה שמפתחות ההצפנה בין כל טרנספורמציה יהיו בלתי תלויים.
מעשית המפתחות שבשימוש כל טרנספורמציה, הן פונקציה, לפעמים פשוטה של מפתח אחר, בדרך כלל קטן.
הצפנה מקבילית: היא הצפנה של טקסט-המקור עם כל מפתח בנפרד ושילוב ביניהם באופן שיבטיח כי פענוח יצליח רק אם מפענחים את כל החלקים, כמו עם טרנספורמציית הכול או לא כלום, אפשר להשיג זאת עם חיבור ב-XOR כמו בפנקס חד-פעמי או על ידי סכמת חלוקת סוד.
הצפנה מרובה היברידית: אם משלבים בין השיטות השונות מתקבלת מערכת היברידית.
דרך אחת לבנות מודל כזה היא באמצעות עץ הצפנות.
שורש העץ הוא השכבה הראשונה של ההצפנה, הוספת שכבה מקבילית מרחיבה את העץ לרוחב, כלומר מוסיפה צמתים.
ואילו הוספת שכבה רציפה או עוקבת מעמיקה את העץ בפקטור שהוא פונקציה של מספר הצופנים המרכיבים את סדרה.
תוצאת הצפנת העץ היא פלט כל הצמתים שאין להם בנים.
התצורה הפשוטה ליישום הצפנה כפולה עוקבת היא להצפין את בלוק המידע פעמיים בזה אחר זה, עם מפתחות הצפנה שונים, כאשר פלט הצופן הראשון מהווה קלט לצופן השני, כדלהלן:
על פניו נראה כאילו הושג ביטחון כפול, אם אורך כל מפתח הוא סיביות, התקפת כוח גס על הצופן, כלומר ניסיון לנחש את המפתחות על ידי ניסוי כל המפתחות האפשריים, אמורה להיות מסדר גודל של .
לאור זאת אפשר לבצע התקפת גלוי-ידוע כדלהלן: תחילה משיג התוקף טקסט-מוצפן כלשהו אשר הוצפן על ידי זוג המפתחות (שאותם התוקף מנסה לחשוף) ואשר המקור שלו ידוע (סוג ההתקפה מניח שאפשר להשיג טקסטים-מוצפנים שמקורם ידוע).
לאחר מכן בונה טבלה שבה שומר את כל ההצפנות האפשריות של , דהיינו כאשר מייצג את כל המפתחות האפשריים.
גודל הטבלה בסיביות יהיה כאשר מייצג את גודל הבלוק של הצופן בסיביות (זו אמנם טבלה ענקית, ואף בלתי מעשית אם המפתח גדול, בכל אופן קיימות טכניקות לצמצום דרישות הזיכרון, ראו להלן).
לאחר מכן מנסה את עבור כל מפתח אפשרי ובודק אם התוצאה כבר קיימת בטבלה.
אם נמצאה התאמה, בסבירות גבוהה בידיו כעת ו- בהם הוצפן .
תיתכן תוצאה שגויה (false positive) כלומר אף על פי שהטקסט שהתקבל נכון המפתח אינו נכון דהיינו , ההסתברות שהתגלו המפתחות הנכונים היא , במקרה של DES מדובר על הסתברות של .
כדי להיות בטוח הוא יכול לנסות את התהליך עם זוג אחר, להצפין את עם ו- ולבדוק אם התקבל .
הכנת הטבלה והחיפוש בה אינם עולים על סיבוכיות כל אחד, כלומר סיבוכיות ההתקפה היא .
ייתכן שצריך להביא בחשבון גם את הזמן הדרוש למיון, שזה בערך .
בכל אופן הושג שיפור קל בלבד.
אם אלגוריתם ההצפנה מקיים תכונות של חבורה, אזי תמיד קיים מפתח שלישי המקיים .
הצפנים הקלאסיים כולל צופן ויז'נר מקיימים תכונה זו.
במקרה כזה ביטחון ההצפנה לא השתפר כלל, כי מציאת המפתח השלישי בכוח גס היא בסיבוכיות , כלומר כאילו התבצעה הצפנה אחת.
מצד שני הוכח (במאמר שפורסם על ידי קמפבל וויינר לגבי DES אך ניתן להשליכו גם לאחרים) שבאופן כללי צופן בלוקים סימטרי מודרני שעושה שימוש בטבלת תמורה, בדרך כלל אינו מהווה חבורה ואינו סגור מבחינה פונקציונלית.
לולא עובדה זו, התקפת 'נפגש באמצע' של הלמן ומרקל הייתה שוברת כל צופן בלוקים סימטרי בסיבוכיות של בקירוב שזה כחצי מהזמן הדרוש לכוח גס, במחיר של סיבוכיות מקום נוספת.
הדברים נכונים בדרך כלל גם לגבי אלגוריתמים א-סימטריים שמסתמכים על בעיות חישוביות מתורת המספרים.
תצורה יותר בטוחה של הצפנה-כפולה העמידה בפני ההתקפה האמורה, הומצאה על ידי דויס ופרייס.
זוהי וריאציה של מצב הפעלה CBC והיא מעין הצפנה מקבילית.
במקרה שמצפינים מספר בלוקים של מידע ברצף, כל בלוק טקסט-מקור מחובר ב-XOR עם תוצאת הצפנה קודמת עם מפתח אחר, לפני שהוא מוצפן.
בהצפנה משולשת מצפינים את המידע שלוש פעמים ברציפות עם מפתחות הצפנה שונים כדלהלן: .
או בקיצור EEE כלומר שלוש הצפנות עוקבות.
למעשה DES משולש שהוצע על ידי וולטר טאצ'מן שהיה ממפתחי DES, הוא מעין פשרה לשמירה על תאימות עם המערכות הקיימות תוך הגברת הביטחון.
בשיטה זו משתמשים רק בשני מפתחות.
מצפינים עם הראשון, מפענחים עם השני וחוזרים ומצפינים עם הראשון, כדלהלן:
הסימון המקוצר של השיטה הוא EDE, כלומר הצפנה/פענוח/הצפנה והיא עמידה קצת יותר כנגד התקפת נפגש באמצע של מרקל והלמן.
הבחירה במבנה הייחודי הזה לא מניבה ביטחון משולש (כיוון ששניים מהמפתחות זהים).
אך המבנה אומץ על ידי IBM בעיקר בשל שיקולי תאימות וכן אומץ על ידי תקן איזו ISO 8732. הסיבה היא שבדרך זו אפשר להשתמש באותה חומרה לביצוע הצפנה בשיטה הרגילה או המשולשת.
כיוון שאם קובעים מתקבלת הצפנה יחידה, אילו היו בוחרים בשלוש הצפנות עוקבות (EEE) התוצאה לא הייתה כזו.
אך יש לזכור שהצפנת DES משולש איטית פי שלושה בהשוואה להצפנה בודדת עם מפתח אחד ואף פי כמה יותר בהשוואה לאלגוריתמים מודרניים כמו AES.
מרקל והלמן פיתחו התקפת גלוי-נבחר עם ניסיונות בקרוב ובאותה סיבוכיות מקום כנגד הצפנה משולשת EDE, אולם הדרישה של מקורות ידועים בסגנון התקפת גלוי-ידוע לא מעשית.
התקפת נפגש באמצע שוכללה על ידי רבים, ביניהם הגרסה של פול ואן אורשוט ומיכאל ויינר, שעושה שימוש בטכניקה של חיפוש התנגשויות מקבילי לצמצום משמעותי של צריכת הזיכרון ובעקרון פרדוקס יום הולדת.
בהתקפה זו במחיר של טקסטים ידועים כאשר אפשר לפרוץ את מבנה EDE בתוך , במקרה של DES פירושו .
אם התקפה זו יעילה מכוח גס ובסיבוכיות מקום בסדר גודל של שהיא נמוכה בהרבה מ-.
המשמעות היא שבגרסת EDE מתקבל ביטחון של שתי הצפנות בקירוב במחיר של שלוש.
קיימים מספר דרכים ליישם סכמת הצפנה משולשת, במצבי הפעלה שונים.
למשל, במצב CBC-פנימי מצפינים בלוק אחד עם וקטור אתחול (IV) אחד, הפלט משמש קלט לשלב הבא בו מפענחים עם וקטור אתחול שני ושוב הפלט משמש כקלט להצפנה האחרונה עם וקטור אתחול שלישי וחוזר חלילה.
בגרסה אחרת משתמשים עם וקטור אתחול אחד במצב שנקרא CBC-חיצוני.
כלומר משתמשים עם וקטור אתחול אחד בלבד ומצפינים את כל הבלוקים בשיטה המשולשת, שלוש פעמים רצוף.
ההבדלים באים לידי ביטוי ביישום בחומרה, כאשר הראשון יעיל יותר.
אם מצפינים עם שלושה מפתחות שונים, התקפת כוח גס הטובה ביותר היא מסדר גודל בקירוב ובסיבוכיות מקום של , שזה מה שמצפים באופן נאיבי מהצפנה כפולה.
אך יש לזכור שאמנם התקפת נפגש באמצע אינה יעילה במקרה זה, קיימות התקפות אחרות טובות יותר, כמו התקפה דיפרנציאלית של שמיר וביהם.
ביהם הראה שנגד התקפה זו הווריאציות המנויות לא יותר בטוחות מהצפנה בודדת.
כנגד איום התקפה דיפרנציאלית פותחו וריאציות אחרות של הצפנה משולשת המנצלות טכניקה של הגדלה מלאכותית של גודל הבלוק על ידי ריפוד המידע במחרוזת אקראית כלשהי, הריפוד לא רק משבש את הקשר בין ההצפנות אלא גם גורם לחפיפה של בלוקים כמו לבנים.
או לחלופין אפשר לבצע הלבנה ב-XOR עם מחרוזת פסאודו-אקראית בטוחה ושילוב פרמוטציה ללא מפתח כלשהי.
גרסה אחת המשלבת את הרעיונות המנויים נחשבת כעמידה כנגד התקפה דיפרנציאלית.
היא כוללת (1) מעבר הלבנה עם תוצאת מחולל אקראי קריפטוגרפי להסתרת טקסט-המקור.
(2) שימוש כפול בפרמוטציה ללא מפתח.
(3) הצפנה אמצעית מרובה, המסומנת - דהיינו הצפנה מחזורית באמצעות אחד מתוך סדרה של הצפנות.
אמנם לא ידוע על התקפה מעשית כנגד המבנה הזה.
על כל פנים, מומחי הצפנה ממליצים להיזהר בשימוש בהצפנה מרובה.
ברוב המקרים המחיר עולה על התועלת.
ובנוסף יש הטוענים שככל שההצפנה מורכבת ומסובכת יותר 'שטח הפנים של ההצפנה גדל' דהיינו מספקים יותר 'חומר' להתקפה וכן מגבירים את הסיכויים לטעויות וחולשות נסתרות.
המונח קסקדה או אשד מתייחס להצפנה עם מספר אלגוריתמים שונים ועם מפתחות הצפנה שונים.
הרעיון הגיוני במקרים מסוימים כמו בסיטואציה שבה שני גורמים או ישויות ברשת מעוניינים לשתף ביניהם מידע סודי וכל אחד מהם סומך רק על אלגוריתם ההצפנה שבאמתחתו ואינו סומך על האלגוריתם השני, כי הוא חושש שתמצא דרך קלה לשבירתו בעתיד הקרוב.
כדי שהם יוכלו להתקשר בבטחה, טבעי הדבר לחפש דרך שבה יוכלו לשלב את ביטחון שניהם, כך שאם תתגלה התקפה מעשית טובה כנגד אחד מהם, ביטחון המידע יישען על האלגוריתם השני ולהפך.
בהנחה שלא סביר שימצאו בו זמנית דרכים קלות לשבירת כל האלגוריתמים המשתתפים בקסקדה.
במאמר משנת 1993 מצביע יואלי מאורר על חשיבות הצופן הראשון ברצף.
למעט פנקס חד-פעמי כל צופן ניתן לשבירה, עובדה זו משליכה כי בהכרח קיימים מאפיינים מסוימים בטקסט המוצפן שייחודיים להצפנה ספציפית.
בהצפנה מרובה, מאפיינים אילו עלולים לזלוג מהטקסט המוצפן הראשון לבאים אחריו ובכך להחלישם.
או אם קיימת אינטראקציה קלה בין האלגוריתמים כגון במקרים בהם הצופן הראשון מוסיף מחרוזת טקסט קבועה כלשהי לתוצאת ההצפנה.
פעולה נפוצה ביישומים מעשיים ונקראת מספר קסם, אזי הצופן השני יהיה פגיע להתקפת גלוי-ידוע.
כעת אם האלגוריתם הראשון חלש, משמעות הדבר שנוסף בידי התוקף מידע שמאפשר לפרוץ את הבא אחריו וכן הלאה.
כלומר הוכח שהתוצאה הכוללת לא תהיה חזקה יותר מהאלגוריתם הראשון.
המסקנה היא שהטענה שהצפנה מרובה תהיה חזקה לפחות כמרכיב החזק ברצף עשויה להיות שגויה.
מאורר הוכיח שקסקדה של אלגוריתמים עם מפתחות שונים ובלתי תלויים זה בזה סטטיסטית, חזקה לפחות כמו האלגוריתם הראשון - בתנאי שהאלגוריתמים המשתתפים בקסקדה קומוטטיביים ביחס זה לזה (כמו בצופני זרם אחדים).
כמו כן הוכיח שאפשר להגיע למבנה בטוח של סכמת הצפנה מרובה שבה הביטחון הכולל הוא לפחות כמו האלגוריתם החזק מביניהם.
מכאן שבמצב הפעלה OFB שמדמה תכונות צופן זרם אפשר לבנות הצפנה מרובה ממספר אלגוריתמים באופן שיניב ביטחון לפחות כמו החזק מביניהם.
למשל על ידי שילוב פנקס חד-פעמי ב-XOR.
ביטחון מערכת הצפנה מרובה תלוי גם בהנחה שכל מפתחות ההצפנה נותרים סודיים.
ייתכן שצריך מודל מחמיר יותר, כי צריך לענות על השאלה האם המערכת נותרת חזקה לפחות כהצפנה יחידה, במקרה שאחד המפתחות נחשף.
הגדרה זו של התקפת מוצפן נבחר מסומנת ME-CCA, בה נוסף מרכיב שנקרא 'אורקל חשיפת מפתח'.
דהיינו לפי המודל יוצאים מהנחה שהתוקף מוסגל לפנות לאורקל היפותטי ולבקש חשיפת מפתח כלשהו (אבל לא את כולם) והשאלה היא כמה יקל בידו הדבר לפרוץ את המערכת כולה.
פרויקט NESSIE פרסם בשנת 2003 המלצות לאלגוריתמים אסימטריים ובין היתר המליץ להגברת הביטחון, להשתמש בהצפנה מרובה עם אלגוריתמים שונים המבוססים על בעיות שונות מתורת המספרים.
למשל הצפנה עם RSA וגרסה כלשהי של דיפי-הלמן כמו ECC.
במאמר משנת 1984 הוכיחו שמעון אבן ועודד גולדרייך שחוזק קסקדה עוקבת (דהיינו פלט הצפנה א' משמש קלט להצפנה ב' וכו') כנגד התקפת גלוי-ידוע שווה לסכום גודל המפתחות, עבור הצפנות כל אחד עם מפתח בגודל החוזק הכולל יהיה .
הם מסכמים כי קסקדה של צופנים אקראיים אינה מהווה צופן אקראי, למרות זאת הקושי שבשבירת סכמה כזו אינו נופל מהקושי שבשבירת אחת מההצפנות.
כמו כן הבעיה של הצבת חסם תחתון לשבירת קסקדה ארוכה היא בעיה קשה, קיומו של חסם כזה מצביע על כך ש-.
קיימות כמה דרכים בטוחות לשילוב בין אלגוריתמים (גם סימטריים וגם א-סימטריים), תוך התחשבות באיומים המתוארים.
הרעיון הוא לערבב את המסר לפני ההצפנה עם פנקס חד-פעמי אחד או יותר באמצעות XOR ולהצפין גם את הפנקסים החד-פעמיים שהופכים להיות חלק מהטקסט המוצפן.
המחיר הוא שהטקסט המוצפן 'מתנפח' בפקטור של שנים או יותר תלוי בשיטה.
כמו כן ההנחה היא שמחולל המספרים האקראיים בטוח לשימוש מבחינה קריפטוגרפית, אפשר להרחיב את השיטה למספר גדול יותר של אלגוריתמים.
להלן סכמת הצפנה מרובה מקבילית עם פנקס חד-פעמי:
מכינים פנקס חד-פעמי באורך המסר המיועד להצפנה.
מכינים שני מפתחות הצפנה .
מצפינים את באמצעות האלגוריתם הראשון .
מצפינים את עם האלגוריתם השני .
הטקסט המוצפן הוא שתי התוצאות .
גרסה מקבילית נוספת של אסמוט ובלקלי משנת 1981 שניתן להרחיבה גם להצפנות נוספות וכן לאלגוריתמים שונים (גם א-סימטריים) עושה שימוש בשני פנקסים חד-פעמיים והיא כדלהלן :
מייצרים זוג פנקסים חד פעמיים באורך המסר המיועד להצפנה.
מצפינים את המספר האקראי הראשון:
מצפינים את המספר האקראי השני:
מערבבים את המסר ב-XOR אם שני המספרים האקראיים: .
שימו לב להתרחבות הצופן פי שלושה במקרה של הצפנה כפולה.
מבנה גנרי של הצפנה מרובה בשילוב סכמת חלוקת סוד
שיטה נוספת להצפנה מרובה שהוכחה כבטוחה כנגד התקפת מוצפן-נבחר לאלגוריתמים א-סימטריים בשילוב סכמת חלוקת סוד.
בהנחה שהאלגוריתמים המשתתפים עמידים בפני התקפת גלוי-נבחר (רוב האלגוריתמים המעשיים עונים להגדרה זו), היא כדלהלן, כאשר ו- הן פונקציות פסאודו-ראנדומליות בטוחות (בקיצור PRF):
מבנה בטוח של סכמת הצפנה מרובה מקבילית
מייצרים זוגות מפתחות הצפנה פומביים/פרטיים וכן .
כל זוג מתאים לאלגוריתמים בהתאמה.
להצפנה מחלקים את המסר ל- חלקים באמצעות סכמת חלוקה המבטיחה All Or Nothing בקיצור AONT.
(להלן דרכים ליישום טרנספורמציה כזו).
בוחרים מספרים אקראיים ועבור כל מספר אקראי כאשר מבצעים:
לפענוח מחשבים ואת עבור .
מאחדים בחזרה את התוצאות באמצעות טרנספורמציית AONT ההפוכה לקבלת .
טרנספורמציית הכול או לא כלום
טרנספורמציית AONT (הכול או לא כלום) ניתנת לביצוע בכמה דרכים.
דרך אחת של רונלד ריבסט כדלהלן: עבור בלוקים בוחרים מפתח אקראי כלשהו , תחילה מחשבים את עבור , מחשבים את עבור ואז .
הפונקציה היא אלגוריתם הצפנה כלשהו, המפתחות אינם סודיים כשהמפתח קבוע.
לשחזור מחשבים את ואז .
מבנה בטוח של סכמת הצפנה מרובה עוקבת
מייצרים זוגות מפתחות הצפנה ופענוח א-סימטריים כאשר מייצג את מספר ההצפנות.
כל זוג מתאים להצפנה אחת בהתאמה.
עבור כל מרכיב מייצרים סיבית רנדומלית ומחשבים את:
(תוצאת כל שלב היא ).
עבור כל הרכיבים מחשבים .
פלט הפענוח יהיה בתנאי ש- עבור כל .
סכמת הצפנה מאומתת או בקיצור AE, היא סכמת הצפנה של צופן סימטרי, שמטרתה לספק במקביל לסודיות שלמות ואימות המידע המוצפן.
באופן כללי יצירת סכימות הצפנה מאומתת היא משימה קשה יותר מיצירת סכמה שמקיימת את דרישה הבסיסית של סודיות בלבד.
אחת הדרכים ליצירת סכימת הצפנה מאומתת היא בעזרת הרכבה של שתי סכמות קריפטוגרפיות נפרדות: אלגוריתם הצפנה בטוח לפי מודל התקפת גלוי-נבחר וקוד אימות מסרים לפי מודל התקפת מסר נבחר.
תחילה השולח והמקבל צריכים להסכים ביניהם על מפתח הצפנה סודי.
המקבל מצידו משתמש במפתח הסודי שברשותו כדי לפענח את המידע וכן בודק את תג האימות שקיבל באמצעות המפתח הסודי שבו השתמש השולח.
אם המידע מאומת בהצלחה הוא מקבל אותו כמידע אותנטי שהגיע מהמקור שהוצהר, אחרת הוא דוחה אותו על הסף ומחזיר הודעת שגיאה מתאימה לשולח.
מעצם ההגדרה תג האימות מבטיח כי תוקף בעל יכולת חישוב סבירה לא יוכל לזייף מסר מוצפן ותג מתאים בלא ידיעת מפתח ההצפנה הסודי המשותף להם, כך שהמקבל לא יבחין בכך (כלומר, שפונקציית האימות של המקבל תחזיר "אמת" כאילו ההודעה התקבלה מהשולח האותנטי).
הצורך בהצפנה מאומתת עולה באופן טבעי לאור העובדה שמעצם ההגדרה צופן סימטרי אינו מבטיח שלמות ואותנטיות.
תמיד קיים חשש שתוקף זדוני יצליח ליירט מסר מוצפן, לשנותו או להחליפו באחר ולהעבירו ליעדו מבלי שלמקבל תהיה דרך להבחין בכך.
בשל כך פותחו שיטות לאימות שנועדו להבטיח את שלמות המסר באמצעים קריפטוגרפיים.
בעבר בשל ההפרדה בין שני היעדים, סודיות לעומת שלמות ובהיעדר תקן כלשהו נטו מפתחי מערכות אבטחה לפתור בעיה זו בשיטות אד הוק.
דרך אחת היא להוסיף יתירות מכוונת כמו ריפוד המסר במספר אקראי לפני ההצפנה, דרך אחרת היא שילוב קוד אימות מסרים יחד עם הצפנה (באופן שלא הוכח כבטוח מבחינה קריפטוגרפית).
התקפות אינטרנט ניצלו פרצות אלו.
הניסיון מלמד ששילוב הצפנה עם אימות מורכב ומועד לשגיאות.
שגיאה נפוצה אחת היא הניסיון להבטיח אימות בשיטות לא קריפטוגרפיות כמו שימוש בפונקציית גיבוב ללא מפתח או בקוד תיקון שגיאות.
פרוטוקול SSH גרסה 1.5 השתמש ב-CRC-32 לאימות במבנה CBC עובדה שנוצלה לשבירת הפרוטוקול.
טעות אחרת היא להשתמש במפתח הצפנה יחיד הן להצפנה והן לאימות שאינו מומלץ ואף עלול להוות פרצת אבטחה במקרים מסוימים.
בשל בעיות תאימות עם מערכות קיימות יש עדיפות לשימוש במפתח אחד.
בפועל מערכות הצפנה בטוחות משתמשות בטכניקה לגזירת מפתחות הצפנה נוספים ממפתח המאסטר באמצעות KDF בטוח.
גם במקרה שהמרכיבים כשלעצמם בטוחים יכול להיות שהמערכת כמכלול לא תהיה בטוחה.
הפרדיגמה הבסיסית כדי לספק סודיות ושלמות באופן בטוח היא, לקחת צופן סימטרי בטוח המספק סודיות בלבד ולשלבו במצב הפעלה CBC או מצב מונה עם אלגוריתם אימות מסרים בטוח המספק אימות בלבד.
עם מפתח סודי נפרד או עם מפתח שנגזר באופן בטוח מהמפתח הראשון.
מפתח האימות ומפתח ההצפנה חייבים להיות שונים ובלתי תלויים סטטיסטית, כלומר לא ניתן לנחש מפתח אחד בהינתן השני.
אפשר להישתמש בשני מפתחות סודיים האחד לצורך הצפנה והשני לצורך אימות.
אך לשיטה זו מספר חסרונות; יעילות נמוכה, אחסון מספר רב של מפתחות סודיים וכן בעיית תאימות עם מערכות קיימות.
דרך אחרת היא להפיק את מפתח האימות מתוך מפתח ההצפנה בדרך בטוחה כמו באמצעות פונקציה אקראית 'אוניברסלית'.
שיטות השילוב של הצפנה עם אימות מתחלקות לשני סוגים עיקריים; הרכבה גנרית, שבה הם נעשים בנפרד ללא קשר הדוק ביניהם, הרעיון נמצא בשימוש מעשי נרחב בסכמות רבות בין היתר HMAC, UMAC או CBC-MAC.
השיטות האחרות מנסות לשלב בין ההצפנה והאימות באופן יותר הדוק כדי להבטיח סודיות ואימות גבוהים ביותר האפשריים במחיר הנמוך ביותר מהיבט של יעילות.
קיימות מספר שיטות כאלו, ביניהן אפשר למנות את: OCB, CCM, EAX, GCM שהוצעו ונבחנו על ידי מומחים ואושרו בתקן איזו ובארגוני תקינה נוספים.
רעיון הצפנה מאומתת הועלה לראשונה על ידי בלייר ורוגווי ב-1995 והורחב לאחר מכן על ידי אחרים.
המושג מבוסס על רעיון אימות מסרים שהועלה לראשונה על ידי ווגמן וקרטר, הם הציעו לנצל צופן בלוקים כדי להשיג אימות במקום סודיות.
מטרת קוד אימות מסרים היא להבטיח שלמות טקסט-קריא (המסומן INT-PTXT קיצור של integrity of plaintext) או שלמות טקסט-מוצפן (שנקרא INT-CTXT קיצור של integrity of ciphertext), באופן כזה שבהינתן מסר ומפתח סודי, המקבל יוכל להבחין בכל שינוי במסר בהסתברות מאוד גבוהה.
בשונה מרעיון הבטחת סודיות בצופן סימטרי, כאן בהגדרה המסר יכול להישאר גלוי ואין דרישה לסודיות.
לצורך השוואה בין שתי הדרישות; סודיות מול אימות, מקובל שההגדרה האחרונה מקבילה לרעיון החלש של הבטחת סודיות שנקרא IND-CPA כלומר עמידות בפני התקפת גלוי-נבחר, הקיצור IND מתייחס לאי-יכולת הבחנה (indistinguishability).
או בהגדרה החזקה יותר הנקראת SUF-CMA כאשר SUF פירושו strongly unforgeable, שבה באותה סיטואציה יהיה קשה מבחינה חישובית ליריב למצוא כל זוג 'מסר+תג' כך שהתג יהיה תקף עבור המסר (גם אם המסר אינו בעל משמעות או שייכות כלשהי, כל עוד התג לא יוצר במקור מאותו מסר).
הוכח שכל פונקציה פסאודו-רנדומלית בטוחה יכולה להיות MAC בהגדרה החזקה.
רעיון הצפנה מאומתת 'גנרית' הוא הרכבה של הצפנה סימטרית כקופסה שחורה עם מנגנון אימות.
כלומר קיימת הפרדה בין האימות להצפנה כך שניתן יהיה להחליף את הצופן הסימטרי או את אלגוריתם האימות בכל שלב.
בהגדרה יש להבטיח שהרכבה כזו בטוחה כנגד התקפת גלוי-נבחר שבה התוקף אינו יכול הבחין בהבדל בין הצפנה של טקסט גלוי כלשהו לפי בחירתו לבין טקסט אקראי.
מסמנים זאת IND-CPA שהיא הגדרה חלשה יותר לעומת IND-CCA (קיצור של אי-יכולת הבחנה תחת התקפת מוצפן-נבחר).
באופן כללי מרבית האלגוריתמים המודרניים עומדים לפחות בהגדרה החלשה.
אימות אפשר להשיג באמצעות אלגוריתם קוד אימות מסרים בטוח.
במקרה כזה ההצפנה המאומתת מושגת בשני שלבים, ריצת הצפנה וריצת אימות.
נניח שפונקציית ההצפנה של הצופן הסימטרי נקראת והפענוח , פונקציית יצירת תג האימות , פונקציית בדיקת התג .
יהי מפתח סודי המשותף לשולח והמקבל, כאשר משמש להצפנה ו- לאימות.
קיימות שלוש דרכים נפוצות לשילוב הצפנה עם אימות:
הצפנה ואימות: בשיטה זו ההצפנה והאימות מבוצעים בנפרד.
בהינתן טקסט גלוי השולח מכין את ו- כדלהלן:
הוא הטקסט המוצפן ו- הוא תג האימות אותם הוא מעביר למקבל.
המקבל מצידו מפענח: ומוודא שהתג תקף, אם לא מתקבל הוא דוחה את המסר ומחזיר הודעת שגיאה.
פרוטוקול SSH אימץ גרסה דומה לזו.
אימות ואז הצפנה: בשיטה זו תחילה מייצרים תג אימות ואז מצפינים את המסר יחד עם תג האימות ושולחים רק את :
כאשר הסימן מייצג שרשור מחרוזות.
כאן תג האימות אינו נשלח בגלוי אלא הוא מוצפן יחד עם המסר.
המקבל מצידו תחילה מפענח את המסר ומקבל את ואת .
ואז בודק אם מתקבל .
אחרת הוא דוחה את המסר כולו ומחזיר הודעת שגיאה.
פרוטוקול SSL משתמש בווריאציה כזו.
הצפנה ואז אימות: בשיטה זו המסר תחילה מוצפן ואז מכינים מהטקסט המוצפן תג אימות ושולחים את שניהם:
המקבל מאמת תחילה את על לפני שהוא מפענח ורק אם האימות עבר בהצלחה הוא מפענח את ומקבל את .
פרוטוקול IPSec תומך בגרסה כזו.
כל אחת מהשיטות מניבה ביטחון שונה בהתאם למודלים של ביטחון שונים.
כאשר השיטה הראשונה הצפנה ואימות נפרדים, היא החלשה ביותר ואילו השיטה האחרונה אימות אחרי הצפנה, היא החזקה ביותר.
הנחת הבסיס היא שהצופן הסימטרי בטוח לפחות כנגד התקפת גלוי-נבחר בקיצור (CPA) ואלגוריתם האימות אינו ניתן לזיוף לפחות תחת CMA - התקפת מסר-נבחר.
הטבלה הבאה פורסמה ב-2007 על ידי Mihir Bellare מאוניברסיטת קליפורניה בסן דייגו שנחשב לאחד מהוגי הרעיון ו-Chanathip Namprempre באוניברסיטת תאמאסאט בתאילנד והיא מציגה את הקשר בין הגדרות הבטחת סודיות והבטחת אימות בהתאם למודלים שונים של ביטחון.
בשתי הטבלאות הבאות "כן" מתייחס לכך שהמבנה הוכח כבטוח תחת ההנחות המתוארות.
ו"לא" פירושו שקיים מבנה כזה שאינו עונה על כל הגדרות הביטחון - במקרים מסוימים (לא בכל המקרים).
שיטה פרטיות שלמות IND-CPA IND-CCA NM-CPA INT-PTXT IND-CTXT הצפנה ואימות לא לא לא כן לא אימות ואז הצפנה כן לא לא כן לא הצפנה ואז אימות כן לא לא כן לא
שיטה פרטיות שלמות IND-CPA IND-CCA NM-CPA INT-PTXT IND-CTXT הצפנה ואימות לא לא לא כן לא אימות ואז הצפנה כן לא לא כן לא הצפנה ואז אימות כן כן כן כן כן
שתי הטבלאות מציגות את תוצאות רמת הביטחון של שלושת המבנים המתוארים תחת מודלים שונים מהכבד אל הקל.
הטבלה העליונה מניחה שקוד אימות המסרים בטוח תחת ההגדרה המקלה של 'אי-זיוף' ואילו הטבלה התחתונה מתייחסת למקרה שבו קוד האימות עמיד כנגד ההתקפה האמורה בהגדרה החזקה שלה.
המושג NM-CPA מתייחס לאי-חשילות שהיא הגדרה חזקה יותר של ביטחון סמנטי.
הרכבה גנרית של הצפנה מאומתת סובלת מכמה חסרונות; יעילות נמוכה, התנפחות לא רצויה של הצופן וסיכון בטיחותי שנובע מהחשש שלמרות שכל אחד מהמרכיבים בטוח, השילוב ביניהם עלול להחדיר חולשות או פרצות בלתי ידועות.
ההעדפה היא לפתח מערכת ייעודית המקפלת בתוכה הצפנה עם אימות, עם ביטחון מוכח ובעדיפות לריצה אחת מסיבות של יעילות.
מסיבות של תאימות ויעילות רצוי שהאלגוריתם יקבל מפתח הצפנה יחיד, למרות שפנימית האלגוריתם עושה שימוש במפתח אימות נפרד הנגזר מהמפתח הראשי.
נושא נוסף שנשקל הוא זכויות יוצרים, ארגוני תקינה ויצרנים נמנעים באופן גורף משימוש באלגוריתמים המעוגנים בפטנטים ובזכויות יוצרים.
הצפנה מאומתת עם מידע נלווה
רוגווי הרחיב את המושג הצפנה מאומתת להגדרה של הצפנה מאומתת עם מידע נלווה (Authenticated Encryption with Associated Data בקיצור AEAD).
במודל זה המידע מחולק לשני חלקים טקסט-גלוי המיועד להצפנה וכותר (header) שמגיע יחד איתו.
השלמות במקרה זה מחויבת לגבי כל חלקי המידע אך הסודיות לא, כי הכותר משודר במצב גלוי.
בעיה זו של הבטחת שלמות המידע הנלווה מתעורר בעיקר בפרוטוקול העברת מפתח והיא נקראת גם אריזת מפתח הצפנה.
כלומר מציאת מנגנון בטוח להעברת המפתח והמידע הנלווה אליו בצורה בטוחה ומאומתת לצד השני.
וכן שהחלק הגלוי במידע לא יסכן את סודיות הפרוטוקול או שלמותו.
אפשר להשיג זאת על ידי שילוב המידע הנלווה בתהליך האימות.
דרך אחרת להשגת אימות או הבטחת שלימות היא "הצפנה עם יתירות".
כלומר ניסיון להשיג אימות על ידי קידוד המידע בדרך כלשהי כמו ריפוד במספר אקראי לפני ההצפנה.
הרעיון הוא שאם מרפדים את המסר היטב לפני ההצפנה אפשר להשיג אימות בחינם.
דוגמה טובה היא שיטת הריפוד OAEP.
על כל פנים מתוך הטבלה עולה שהשיטה שאומצה בפרוטוקול SSH פחות בטוחה מהאחרות.
עמידה בפני שימוש לא ראוי וכיבוד ייחודיות
בסכמות הצפנה המבוססות על וקטור אתחול או Nonce חובה שווקטור האתחול יהיה ייחודי וחד פעמי.
כלומר אין להשתמש בו שוב עם אותו מפתח להצפנת מסרים אחרים כיוון שקיים חשש שאם יימצא בלוק מידע שחוזר על עצמו הרי שהצפנה שלו תחת וקטור אתחול קבוע עם אותו מפתח סודי עלול לייצר בלוק מוצפן זהה, מסיבה זו יש להבטיח שווקטור האתחול או המפתח, לפחות אחד מהם יהיה שונה.
מגבלה זו היא באחריות המשתמש ומסתבר שקיימים היבטים מעשיים שמקשים על כיבודה בפועל.
מפתחי מערכות נטו בעבר להתעלם ממנה מה שהוביל למערכות פגומות שניתן לפרוץ בקלות.
הדוגמה הטובה ביותר היא פריצת פלייסטיישן 3 שנקראת Jailbreak.
מסיבה זו פותחו מספר מצבי הפעלה שמביאים בחשבון עובדה זו.
אם מבלי משים או במכוון המשתמש סיפק וקטור אתחול זהה, המערכת תהיה בטוחה (במגבלות מסוימות) ולא תהיה פרוצה לחלוטין, מערכת כזו נקראת Nonce Respecting או Misuse-resistance והיא תכונה חשובה בהצפנה מאומתת.
הגדרה קונקרטית של ביטחון סמנטי של הצפנה מאומתת היא על ידי מה שקרוי 'משחק' ו"יתרון" של "יריב" כאשר המושג "בטוח" אינו מוגדר פורמלית בהקשר זה, אלא פירושו שהיתרון של יריב מוגבל במקום ובזמן "זניח" בהתאם לפרמטר כלשהו שנתון לדיון.
בצפנים סימטריים כמו AES למשל לא קיימת הגדרה פורמלית.
היריב יחשב כמנצח אם יצליח בהסתברות גבוהה מחצי באחוז מסוים "שאינו זניח" לנחש נכונה בכל הניסויים שביצע.
בניסוח פורמלי ההגדרה תחת מודל CCA או CPA היא:
בהקשר של הצפנה מאומתת את רעיון השלמות או האימות אפשר להגדיר בדרך דומה:
הרעיון של 'אי-זיוף' מוגדר באופן דומה:
קודי אימות מסרים תיקניים כמו אילו המתוארים לעיל כמו HMAC ,PMAC או UMAC ודומיהם מוגדרים בטוחים SUF-CMA שהיא ההגדרה המחמירה שכוללת גם את WUF-CMA.
כמו כן ההגדרה של INT-PTXT חלשה מ-INT-CTXT.
להלן רשימה נבחרת של אלגוריתמים להצפנה מאומתת המבוססת על צופן בלוקים וצופן בלוקים בר-התאמה, עם מידע נלווה או ללא מידע נלווה.
כמה מהן סכמות מתקדמות בעלות מאפיינים נוספים כמו המאפיין של "הצפנה מאומתת דטרמיניסטית עם עמידות שימוש לא ראוי", שפירושה שסכמת ההצפנה תספק ביטחון סביר (במידת האפשר) גם אם השתמשו באותו וקטור אתחול פעמיים, ולא תקרוס לחלוטין.
קטגוריה מתקדמת נוספת היא "עמידות מעבר לגבול יום-הולדת", דהיינו שסכימת ההצפנה מספקת ביטחון אף מעבר לדרישה המינימלית הנובעת מפרדוקס יום ההולדת שהיא פקטור של מחצית מאורך המפתח.
הצפנת פֵּלִיאֵי היא סכימת הצפנה אסימטרית הסתברותית הומומורפית וחתימה דיגיטלית שהומצאה ב-1999 על ידי פסקל פליאיי (Pascal Paillier) לשעבר מחברת GEMPLUS לוקסמבורג.
הצפנת פליאיי הומצאה בהשראת סכימות הצפנה הסתברותית כמו בלום גולדווסר והיא מבוססת על פונקציה חד-כיוונית עם דלת צונחת שנגזרת מבעיה בתורת המספרים הנקראת בעיית השאריות הפריקות (Composite Residuosity Class Problem) מודולו כאשר מכונה "מספר RSA" (כפולה של שני ראשוניים שונים שווים בגודלם בקירוב).
הבסיס התאורטי של המערכת הוא, בהינתן שלם כאשר ו- ראשוניים גדולים, שווים באורכם בקירוב והחבורה , השלם ייקרא שארית -ית (ממעלה ) מודולו אם קיים שלם המקיים
קבוצת השאריות ה--יות היא תת-חבורה כפלית .
לכל כזה קיימים בדיוק שורשים ממעלה .
בעיית ההכרעה האם שלם נתון הוא שארית -ית או לא, המסומנת בקיצור (קיצור של Composite Residuosity) נחשבת לבעיה קשה ולא ידוע על אלגוריתם יעיל שיכול לבצעה בזמן פולינומי.
סדר החבורה הוא כאשר היא פונקציית אוילר של .
עבור ו- היא פונקציה חד-חד-ערכית ועל מעל החבורה ביחס לבסיס נתון.
הוא אלמנט מסדר עבור מחלק כלשהו של .
הקבוצה היא קבוצת כל האלמנטים מסדר עבור (לדוגמה אפשר לבחור כש-).
כדי להפוך את הפונקציה מגדירים את שהיא פונקציה מעל תת-חבורה כפלית של השלמים מודולו המקיימים .
שחזור הערכים מתוך מתבצע על ידי
במקום של אפשר לעבוד עם פונקציית קרמייקל שהיא .
זהו האקספוננט של חבורת אוילר ו- היא כפולה משותפת מינימלית.
שימו לב שלפי משפט קרמייקל עבור כל אלמנט מתקיים וכן .
בהמשך ייעשה שימוש ב- בכל המקומות בהן הופיעה פונקציית אוילר.
דלת המלכודת היא הגורמים הראשוניים או .
כאשר הגורמים הראשוניים של לא ידועים שחזור מתוך ואפילו להכריע האם ללא נחשבים לבעיה קשה תחת המודל הסטנדרטי של סיבוכיות חישובית, בהנחה שפירוק לגורמים של אינו מעשי.
האחרונה נקראת בעיית הכרעה של השאריות הפריקות ומסומנת בקיצור DCRA.
על בסיס הרעיון האמור הצפנת פליאיי פועלת כדלהלן.
יהי ויהי , אפשר למצוא ערך כזה על ידי בדיקה אם
הפונקציה מייצגת מחלק משותף מקסימלי.
הערכים ו- יהיו מפתחות ציבוריים ואילו ו- יהיו המפתחות הפרטיים (במקום המספרים הראשוניים אפשר לשמור את ).
בהינתן מסר הנמוך מ- להצפנה בוחרים שלם אקראי ומבצעים:
הסכימה נחשבת הסתברותית בגלל והיא בטוחה סמנטית כנגד יריב פסיבי, בהנחה שבעיית היא בעיה קשה ושקשה לפרק את לגורמים.
סיבוכיות ההצפנה היא מסדר גודל של בקירוב.
לצורך המחשה הראשוניים יהיו , .
לצורך הצפנת המסר בוחרים מספר אקראי נניח ואז מחשבים את .
הטקסט המוצפן הוא אם כן .
לפענוח תחילה מחשבים את וכן .
ההופכי הכפלי של מודולו הוא לכן .
פרמוטציה חד-כיוונית עם דלת מלכודת
להלן סכימה לא הסתברותית המבוססת חלקית על RSA שנקראת פרמוטציה חד כיוונית עם דלת מלכודת כאשר דלת המלכודת היא .
והיא מסתמכת על בעיית בהנחה שפירוק לגורמים של היא בעיה קשה.
למרות התלות ב-RSA הסכימה ראויה לציון בשל העובדה שפרמוטציות חד כיווניות עם דלת מלכודת (דוגמת RSA ורבין) הן אובייקטים נדירים וחשובים בקריפטוגרפיה מודרנית.
תחילה מפצלים את המסר המיועד להצפנה בדרך הפיכה כלשהי לשני חלקים .
אפשר להשתמש בכל תמורה פומבית מוסכמת שממפה את לערכים .
יש לשים לב שהסכימה הזו אינה הסתברותית, כלומר אינה מערבת שימוש במספר אקראי.
לצורך חתימה דיגיטלית תהי פונקציית גיבוב קריפטוגרפית של המסר שתסומן בקיצור .
עבור המסר החותם מחשב את החתימה כדלהלן:
מקבל החתימה יכול לוודא את תקפותה על ידי הבדיקה שמתקיים
סכימות כמו RSA סובלות מחסרון בכך שהפענוח דורש זמן ואינו יעיל במונחי מחשוב.
מסיבה זו מערכת הצפנה אסימטרית תהיה אטרקטיבית אם הפענוח יהיה מסדר גודל כמעט ריבועי ביחס ל-.
להלן גרסה שונה מעט שבה סיבוכיות הפענוח היא בסדר גודל של עבור קטן כלשהו.
הרעיון הוא להגביל את מרחב הטקסט המוצפן לתת קבוצה מסדר נמוך יותר.
מסיבות של ביטחון צריך להיות כפולה של ראשוני גדול.
בהינתן הבסיס עבור כלשהו, הסכימה היא כדלהלן.
בוחרים אלמנט אקראי הנמוך מ-.
הפעם דלת המלכודת מסתמכת על ידיעת כמפתח סודי במקום .
צוואר הבקבוק בפעולת הפענוח הוא הפעולה שסיבוכיותה היא בסדר גודל בלבד.
אם נבחר באופן כזה ש- אז כל תהליך הפענוח יתבצע עם פעולות בסיביות.
זהו מאפיין חשוב בהשוואה למערכת אסימטריות אחרות.
אולם יש לשים לב שבמקרה זה המערכת לא מסתמכת על בעיית כיוון שכעת ידוע שהטקסט המוצפן שייך לקבוצה .
הבעיה האחרונה, דהיינו לחשב את בהינתן נקראת בעיית הלוגריתם הבדיד 'חלקית' וגם היא משוערת כבעיה קשה.
הסכמות המתוארות הוכחו בטוחות מהיבט תאורטי תחת ההנחות הסטנדרטיות, אך לא הוכחו כבטוחות כנגד התקפת מוצפן-נבחר.
כדי להבטיח עמידות כנגד התקפות מוצפן נבחר יש לבצע שינויים נוספים.
אפשר להגיע לביטחון כזה לפחות תחת מודל אורקל אקראי.
לפי ההמלצות המקובלות הראשוניים ו- צריכים להיבחר באופן שיהיה קשה לפרק את לגורמים.
הבסיס יכול להיבחר באקראי (בגרסה המהירה יידרש טיפול שונה למשל להעלות אלמנט בחזקת ).
כדי לשפר ביצועים אפשר לאמץ את שיטת CRT כמו ב-RSA, כלומר כל החישובים יתבצעו מודולו ו- בהתאמה והתוצאה הסופית תהיה חישוב מערכת המשוואות המודולריות המתקבלת באמצעות משפט השאריות הסיני שהוא זניח יחסית לפעולה של העלאה בחזקה מודולרית.
אם בוחרים קטן (כמו ) כל עוד הוא מקיים את ההגדרות של הסכימה, יתקבל שיפור נוסף בביצועים בסדר גודל של .
יתרה מזו יכול להיות קבוע מה שמאפשר חישוב מוקדם כדי להאיץ ביצועים.
בכללות כל הערכים הקבועים וכן חישוב או יכולים להתבצע מראש.
בפענוח חישוב הפונקציה ניתן לביצוע במחיר פעולת כפל אחת מודולו על ידי חישוב מוקדם של הקבוע .
הקבועים או בגרסה המהירה ניתנים לחישוב מראש.
כדי לנצל את משפט השאריות הסיני (CRT) לשיפור ביצועים, יש להגדיר את הפונקציות ו- כדלהלן: וכן בהתאמה.
פענוח יתבצע כעת עם הקבועים הבאים אותם מחשבים מראש:
ואז תהליך הפענוח הוא כדלהלן:
כאשר CRT היא מימוש של פתרון מערכת הקונגרואנציות לפי משפט השאריות הסיני.
ובגרסה המהירה יש להחליף את ו- ב-.
הצפנת פליאיי הורחבה למספר כיוונים.
איוון דמגרד הציע גרסה שבה המודולוס הוא מהצורה במקום בחזקת 2. וכן הוצעה גרסה מבוזרת (סכמת סף - threshold cryptography) וכן הוצע מימוש ב-ECC.
סכימות ההצפנת פליאיי וכן , מודולו הן הומומורפיות מהחבורה הכפלית לחבורה החיבורית .
בניסוח פורמלי עבור כל ו-, פונקציית הצפנה ופונקציית פענוח בהתאמה, מתקיים
ההשלכה של מאפיין זה היא שהסכימה תהיה שימושית עבור מגוון פרוטוקולים קריפטוגרפיים כמו הצבעה ממוחשבת, סכימת סף, חלוקת סוד ומנגנון הגנת העתקה (Copy protection).
הסתרה עצמית (self blinding) היא התכונה שכל טקסט מוצפן ניתן לשינוי לטקסט מוצפן אחר מבלי שהשינוי ישפיע על הטקסט המקורי, בניסוח פורמלי עבור כל ו- מתקיים
בעיקרון התכונה הזו מאפשרת לבצע פעולות חישוב על ידי צד שלישי מבלי שהוא עצמו ידע מהו תוכן המידע עליו בוצעו החישובים.
לתכונה שימושים רבים בקריפטוגרפיה למשל חתימה עיוורת או מחשוב ענן.
הצפנת מקאליס היא מערכת הצפנה אסימטרית המבוססת על קוד תיקון שגיאות, שפותחה ב-1978 על ידי רוברט מקאליס (R.J.
הרעיון הכללי הוא; בהינתן מחרוזת של סיביות המקודדת למילת קוד בגודל סיביות על ידי מקודד ידוע לכול של קוד ליניארי בינארי באורך וממד , אזי הטקסט המוצפן מיוצר על ידי החדרת שגיאות אקראיות, כלומר הפיכת סיביות (Bit flipping) במיקומים אקראיים במילת הקוד.
אם קטן בחצי לפחות ממרחק המינג של הקוד הליניארי של טקסט מוצפן נתון קיים רק טקסט גלוי יחיד המתאים לו שניתן לשחזור באמצעות קוד תיקון השגיאות.
אך אם הפרמטרים גדולים חילוץ הטקסט הגלוי מהטקסט המוצפן באמצעות תיקון שגיאות אינו מעשי אלא אם כן נתון מידע נוסף לגבי מבנה הקוד.
ההבדל בפקטור העבודה בין קידוד מילת הקוד לבין תיקון השגיאות הוא הבסיס להצפנה האסימטרית שהציע מקאליס, המפתח הציבורי יהיה הקוד הליניארי והמפתח הפרטי יהיה המידע המאפשר את תיקון השגיאות בזמן פולינומי.
מקאליס המליץ על שימוש בקוד תיקון שגיאות שנקרא "קוד גוֹפַּא בינארי" על שם ממציאו וולרי גופא (Valerii Goppa) מפני כמה סיבות, לקוד זה קיים אלגוריתם פענוח פולינומי יעיל וכן העובדה שקוד גופא מהווה מועמד טוב לפונקציה חד-כיוונית - קל לייצר קוד כזה אך קשה מאוד לזהות אותו.
כדי להקים מערכת הצפנת מקאליס, אפשר לפעול כדלהלן:
בוחרים קוד גוֹפַּא שהוא פולינום שרירותי אי-פריק ממעלה מעל השדה ותת-קבוצה של עם הפרמטרים .
כדי לקבל מרחק מינימלי גדול ככל האפשר רצוי שמספר השורשים של יהיה שווה למעלה שלו (נקרא separable).
מכינים מטריצה יוצרת של קוד גופא מסדר .
לאחר מכן בוחרים מטריצה הפיכה (לא סינגולרית) אקראית מסדר , ומטריצת תמורה (מטריצה בינארית ריבועית המכילה בדיוק כניסה אחת שהיא '1' בכל שורה ואו בכל עמודה וכל היתר אפסים) מסדר ומחשבים את .
מפיצים את ואת כפרמטרים ציבוריים ושומרים בסוד את כל היתר.
אם מישהו רוצה להצפין מסר כלשהו באורך סיביות, הוא בוחר וקטור שגיאות באורך במשקל (שבו לכל היותר קואורדינטות שונות מאפס), וההצפנה של היא אותה הוא שולח למקבל.
המקבל יכול לחשב עם הפרמוטציה הסודית את:
עם אלגוריתם הפענוח של קוד גופא המקבל יכול לתקן את למילה על ידי חישוב .
כיוון שהמטריצה הפיכה אפשר לחלץ את המסר על ידי .
כדי שהמערכת האמורה תהיה בטוחה ההמלצה של מקאליס הייתה לפני 25 שנה שהפרמטרים יהיו והפולינום הוא פולינום אי פריק מסדר ובמקרה זה ו-.
אולם כדי לעמוד בהתקדמות הטכנולוגית שחלה ב-25 השנים האחרונות מומלץ כיום להשתמש בפרמטרים קצת יותר גדולים כמו ומספר השגיאות בין 30 ל-120 והממד במקרה זה נע בין 1,718 ל-728. לסיכום המערכת היא:
מפתח ציבורי מטריצה מותאמת מסדר
עם יכולת תיקון עד שגיאות מפתח סודי הפולינום ,
המטריצה היוצרת המקורית מסדר ,
כך שמתקיים המסר לקידוד הצפנה כאשר פענוח תחילה ,
לשם המחשה: אם נבחר השדה , הפולינום אי פריק ואז הוא אלמנט פרימיטיבי רק אם הוא מסדר 15. האלמנטים של תת-הקבוצה הם החזקות של כאשר הקבוצה המתקבלת היא .
קוד גופה מעל שדה זה יכול להיות
עבור קוד זה ו- צריך להיות .
בקיצור זהו קוד גופא בינארי עם הפרמטרים ואפשר לתקן איתו עד שתי שגיאות.
אם נבחר לדוגמה את המטריצות הבאות
והמסר להצפנה הוא תחילה מחשבים את
מוסיפים את וקטור השגיאה (שהוא וקטור המכיל אפסים למעט הפוזיציות השנייה והשלישית) ואז ההצפנה של היא
המקבל שרוצה לפענח את מתוך מחשב תחילה את מהמטריצה
כתוצאה מהפעולה האחרונה השגיאות עברו לפוזיציות הרביעית והעשירית אחרי תיקון מתקבל
ואז אפשר לפענח את הקוד על ידי כפל המטריצות הבא:
לכן והצעד האחרון הוא חישוב
יהי שלם חיובי ויהיו ו- שני פרמטרים כך שמתקיים וכן .
קוד גופה בינארי המסומן מוגדר על ידי תת-קבוצה סדורה של השדה מסדר שנקראת תמיכה (support) ועל ידי פולינום מתוקן אי פריק ממעלה ללא שורשים ב- הנקרא יוצר (generator).
הווקטור ייקרא קוד גופא אם מתקיים
הביטוי קיים מאחר ש- הוא שדה.
והמעלה של הפולינום מהווה גבול תחתון ליכולת תיקון השגיאות של הקוד.
הקוד המתואר ליניארי ולו ממד וכן מרחק מינימלי של לפחות לכן ניתן לשחזר עד שגיאות.
פענוח אלגברי של קוד גופה
אם הוא מילת קוד של ואם עם בעל מרחק המינג או פחות, המילים ו- ייחודיים בגלל .
קיים פולינום מתוקן יחיד ב- ממעלה לכל היותר המקיים
כאשר הוא פולינום ב- ממעלה לכל היותר .
לפולינום יש בדיוק שורשים ב- המתאימים לפוזיציות המכילות אחד בווקטור השגיאה .
תהליך הפענוח כולל את הפעולות הבאות:
ישנן כמה וריאציות לפתרון נוסחת המפתח האמורה ביניהן אלגוריתם אוקלידס.
ב-1986 הציע נידריטר (Niederreiter) מערכת דומה בביטחונה שנקראת גרסה דואלית.
גרסה נוספת שהוצעה מבוססת על קוד ריד-מולר.
מקאליס ציין שהמערכת שלו אינה מתאימה לחתימה דיגיטלית ב-2001 הומצאה חתימה דיגיטלית מבוססת מקאליס.
גודל המפתח הציבורי הוא כנראה חסרונה הגדול של המערכת והוא כאשר הוא אורך המידע המיועד להצפנה ו- הוא אורך הבלוק המוצפן.
למשל לפי הפרמטרים המקוריים שהוצעו על ידי מקאליס גודל המפתח הציבורי הוא 536,576 סיביות.
סנדריר הציע להפחית מגודל המפתח הציבורי בשיטה סיסטמטית.
כלומר כאשר הוא מטריצת היחידה ו- הוא מסדר .
כך גודל המפתח מצטמצם ל- סיביות כי יש צורך לאחסן רק את הצד הימני (), אך עדיין המפתח יהיה די גדול (בערך 262,000 סיביות).
הצפנת מקאליס מבוססת על שתי בעיות קשות בתורת הקודים האחת היא מקרה פרטי של בעיית "פענוח סינדרומי" שהוכח שהיא NP-שלמה; בהינתן מטריצה בינארית מסדר ו- מילות קוד כלשהן ב- הבעיה היא למצוא מילה ב- במשקל נמוך או שווה ל- כך שמתקיים כאשר הוא הסינדרום.
הוכח על ידי ברלקמפ, מקאליס וטילבורג שהבעיה NP-קשה.
והבעיה שנייה היא בעיית זיהוי 'קוד גופא', כלומר בהינתן מטריצה בינארית מסדר לענות על השאלה האם היא מטריצת גופה.
אפשר לתקוף את סכימת מקאליס בשתי דרכים.
אחת היא 'התקפה מבנית' בה מנסים לשחזר את המפענח של הקוד הנוצר על ידי המפתח הציבורי ומשם לשחזר את המפתח הפרטי , אם היא מצליחה המערכת נפרצת לחלוטין.
אפשר לסווג קודי שגיאות למחלקות שקילות, שני קודים באורך זהה ייקראו שקולים (שההפרש ביניהם הוא מילת קוד) אם קיימת בדיוק תמורה אחת באורך המשנה קוד אחד לשני לכן הקוד שנוצר על ידי והקוד הנוצר על ידי נקראים שקולים.
בהתקפה זו התוקף מנסה להשוות בין קודים כדי למצוא שקילות.
אם נמצאה שקילות אפשר לשחזר את התמורה ביניהם על ידי אלגוריתם פולינומי שנקרא Support Splitting Algorithm (של ניקולס סנדריר 1999).
תהליך זה הוא מעבר ליכולת הטכנולוגית הנוכחית עם הפרמטרים המקוריים של מקאליס כי התקפה מבנית מסוג זה דורשת בערך קודים כדי שתצליח.
בהתקפה השנייה שנקראת התקפת פענוח התוקף מנסה לנחש את פענוח הקוד מבלי לפרוץ את המערכת עצמה.
ההתקפה תלויה בפרמטרים של קוד תיקון השגיאות , אורכו, הממד שלו ויכולת תיקון השגיאות ().
לפי הפרמטרים המקוריים של מקאליס התקפה כזו תתבצע עם פעולות בינאריות.
מספר זה נמוך בהשוואה ליכולת הטכנולוגית הנוכחית אך הבעיה היא שכדי להעלות מספר זה יש צורך להגדיל את הפרמטרים וכיוון שהמפתח הציבורי מאוד גדול גם ככה זו בעיה.
המערכת מצד אחד בטוחה מאוד ויעילה.
יעילותה עולה על RSA כיוון שפעולות ההצפנה והפענוח דורשות פעולות ליניאריות בסיביות, דהיינו הכפלה של וקטור במטריצה בלבד, לעומת RSA שדורשת העלאה בחזקה מודולרית.
החסרונות העיקריים של הצפנת מקאליס הן בעובדה שהמפתח הציבורי גדול מאוד וכן בעובדה שתפוקת המערכת היא בשיעור 50 אחוז בערך.
מסיבות אילו האלגוריתם לא זכה לפופולריות רבה.
ההתעניינות המחודשת באלגוריתם באה בעקבות ההתעניינות הגוברת במערכות הצפנה עמידות נגד התקפות קוונטיות כאשר מחשב קוונטי יהיה מעשי.
מערכת מקאליס אטרקטיבית בשל העובדה שהיא נחשבת פוסט קוונטית, היא אינה מבוססת על הבעיות הידועות מתורת המספרים - פירוק לגורמים ולוגריתם דיסקרטי לכן אלגוריתם שור ואלגוריתמים קוונטיים אחרים לא יהיו אפקטיביים נגדה.
מסיבה זו המחקר בנושא כנראה יימשך ויהיו ממצאים נוספים.
הצפנה הסתברותית היא סכימת הצפנה סימטרית או אסימטרית שבה נוסף לתהליך ההצפנה אלמנט אקראי כך שהטקסט המוצפן המתקבל מאותו מסר יכול להיות שונה בכל הצפנה אפילו אם המפתח איתו הוצפן זהה, ואילו הפענוח תמיד דטרמיניסטי.
באופן תאורטי, זוהי מכונת טיורינג הסתברותית שמצפינה את המסר הגלוי בהטלת מטבע, בניגוד לסכימות הצפנה דטרמיניסטיות כמו RSA או רבין שבהן הטקסט המוצפן נותר ללא שינוי אם המסר הגלוי והמפתח קבועים.
המושג הוטבע לראשונה על ידי שפי גולדווסר וסילביו מיקאלי ב-1983 והדוגמאות המעשיות הראשונות הן הצפנת בלום גולדווסר וצופן אל-גמאל.
מאז הפך המושג לאחד מיסודות ההצפנה המודרנית וסכימות רבות הומצאו בהשראתו.
ידוע שכדי שסכימת הצפנה תחשב מוכחת כבטוחה סמנטית תחת מודל סיבוכיות סטנדרטי היא חייבת להיות הסתברותית, כיוון שבהצפנה דטרמיניסטית העובדה ששני טקסטים מוצפנים זהים משליכה בהכרח שטקסט המקור שלהם זהה, מכאן שמעט מידע מועבר ליריב ולכן אינה יכולה להיות בטוחה סמנטית.
הוספת הסתברותיות (פסאודו-אקראיות) פותרת בעיה זו, כיוון שבסבירות מאוד גבוהה הצפנה חוזרת של בלוק טקסט מקורי תניב תוצאות שונות לחלוטין.
אפשר להוסיף הסתברותיות גם לסכימות הצפנה דטרמיניסטיות כמו RSA על ידי ריפוד עם ביטחון תחת מודל אורקל אקראי (דוגמת OAEP).
הצורך בהצפנה הסתברותית נובע מבעיה מהותית שקיימת בכל סכימת הצפנה דטרמיניסטית המבוססת על פונקציה חד כיוונית עם דלת מלכודת.
למשל אם נתונה פונקציה חד-כיוונית כך שקל לחשב את אך קשה לחשב את הפונקציה ההופכית ללא דלת המלכודת:
אין הוכחה בהכרח שאם חד-כיוונית יהיה תמיד קשה להפוך אותה גם כאשר הוא בעל מבנה מיוחד.
הדוגמה הכי פשוטה היא בהינתן פונקציית RSA ידוע שקל לחשב ערכים קטנים של אם המעריך (מפתח ההצפנה) קטן, כך שהתוצאה אינה גדולה מהמודולוס.
העובדה ש- חד-כיוונית אינה מעידה בהכרח שלא ניתן לחלץ מידע חלקי לגבי .
לכן תמיד אפשר לדעת מהי הסיבית הפחות משמעותית של .
לסכימת הצפנה הסתברותית קשר למושג שנקרא סיבית קשה, הבעיה שהועלתה על ידי גילס ברסרד היא כיצד להצפין סיבית בודדת באמצעות סכימת הצפנה אסימטרית, אפשר לראות שסכימה דטרמיניסטית כמו RSA אינה מתאימה למטרה זו כיוון שאף על פי שהיא בטוחה, אפשר לחשב את הסיבית הפחות משמעותית.
ההצעה של גולדווסר ומיקלי פותרת בעיה זו.
הסכימה ההסתברותית הקונקרטית הראשונה, שהוצעה על ידי גולדווסר ומיקלי מסתמכת על בעיית השארית הריבועית מודולו מספר פריק שנחשבת לפונקציה חד-כיוונית קשה והיא למעשה הסכימה הראשונה שהוכחה כבעלת ביטחון סמנטי.
שיטה זו אינה יעילה ולכן אינה בשימוש מעשי, חשיבותה תאורטית בלבד.
הבעיה מוגדרת כדלהלן: נתון מודולוס שהוא כפולה של שני ראשוניים אם זר ל- אז הוא שארית ריבועית (quadratic residue) ביחס למודולוס אם למשוואה
יש פתרון שלם , אחרת אמרים ש- אינו שארית ריבועית (quadratic non-residue).
ללא ידיעת הגורמים הראשוניים קשה להכריע בשאלה.
הסכימה הבאה מנצלת עובדה זו למערכת הצפנה.
החיסרון שלה הוא שהטקסט המוצפן עבור כל סיבית מידע גדול (לפחות 1,024 סיביות).
בהינתן פרמטר ביטחון המשתמש A מכין את הפרמטרים הבאים:
בוחר באופן אקראי שני מספרים ראשוניים ו- באורך סיביות
בוחר שלם כך ש- אינו שארית ריבועית מודולו ולו סימן יעקובי .
המפתח הפרטי הוא המספרים הראשוניים ו-
המפתח הפומבי הוא הערכים ו-.
אם B רוצה להצפין עבור A מחרוזת סיביות של טקסט גלוי כלשהו באורך סיביות הוא מבצע:
לפענוח הטקסט המוצפן המשתמש A מחשב כדלהלן:
עבור כל סיבית מציב .
כאשר הוא אלגוריתם פולינומי שמכריע בשאלה האם שלם כלשהו הוא שארית ריבועית מודולו מספר פריק שהגורמים הראשוניים שלו ידועים, .
אם האלגוריתם מחזיר אמת הסיבית היא '1' אחרת '0'.
סיבוכיות ההצפנה היא בסדר גודל וסיבוכיות הפענוח היא כאשר הוא פרמטר הביטחון (אורך כל אחד מהמספרים הראשוניים בסיביות) ו- אורך המסר בסיביות.
אפשר לראות ש- הוא שארית ריבועית מודולו רק אם .
כיוון שקל לדעת אם מספר הוא שארית ריבועית מודולו מספר ראשוני אך קשה לעשות זאת מודולו מספר פריק, המשתמש הלגיטימי שהגורמים הראשוניים של ידועים לו יכול בקלות לחשב את ולגלות האם או .
בגלל אקראיות בכל פעם שתתבצע הצפנה של יתקבל ערך אחר כך שהתוקף אינו יכול ללמוד מאומה מהתבוננות בטקסט המוצפן.
הצפנה מבוססת סריג כוללת פונקציות קריפטוגרפיות (עם ביטחון מוכח) וקריפטואנליזה של פונקציות קריפטוגרפיות המבוססות על מבנה מתמטי שנקרא סריג.
הצפנת מפתח ציבורי מבוססת סריג נשענת על הקושי שבפתרון בעיית הסריג.
קריפטואנליזה של פונקציות אילו מבוססת על טכניקות רדוקציית סריג.
הצפנת סריג עדיין בראשית דרכה ונעשית אטרקטיבית לאחרונה בשל החיפוש אחר מערכות הצפנה עמידות כנגד קריפטואנליזה פוסט-קוונטית, כאשר מחשבים קוונטיים יהיו מעשיים.
ב-1996 גילה Ajtai תכונה חשובה של סריגים שמעניינת מהיבט קריפטוגרפי.
מאז נעשים מאמצים לפתח מערכות הצפנה מבוססות סריג שתהיינה גם בטוחות לפי המבנה המקורי שהוצע וגם שתהיינה יעילות מבחינה מעשית כמו ממצאיו של Micciancio שחסרונן העיקרי שהן חסרות דלת מלכודת ולא ניתן להשתמש בהן עם מפתח הצפנה (הן שימושיות כפונקציה חד-כיוונית חסרת מפתח).
ממצאים אחרים שיכולים להוביל לפיתוח מעשי של סכימות בטוחות מבוססות סריג הן של Micciancio ו-Vadhan שבהן אפשר לשתף סריג אחד על ידי משתמשים רבים והמפתח הציבורי של כל אחד יהיה מוכב מווקטור יחיד (המפתח הפרטי הוא הנקודה בסריג הקרובה ביותר לווקטור הציבורי) וכן הצפנת רגב.
סריגים נחקרו על ידי מתמטיקאים במשך עשורים והם שימושיים במספר סוגיות כמו תכנון ליניארי ופירוק לגורמים.
העניין בסריגים עלה בשל מאפיין שימושי במיוחד לתחום הקריפטוגרפיה שהתגלה על ידי Ajtai ב-1996 קרי רדוקציה מהמקרה הגרוע למקרה הממוצע.
הוא הוכיח שווריאציות מסוימות של בעיית התרמיל קשות לפתרון במקרה הממוצע לפחות כמו המקרה הגרוע של בעיות הסריג.
עניין נוסף עלה בעקבות גילוי אלגוריתם LLL על ידי Lenstra, Lenstra ו-Lovasz ב-1982.
למשל פתרון בעיית SVP (הווקטור הקצר ביותר) עד קירוב פולינומי.
בהנחה שלא קיים אלגוריתם פולינומי יעיל לחישוב SVP עד פקטור של כאשר הוא הממד של הסריג ו- הוא קבוע בלתי תלוי, אפשר לבנות על בסיסה פונקציה חד-כיוונית קריפטוגרפית דומה לתרמיל (knapsack) שכמעט תמיד בטוח קשה אם המפתח נבחר באקראי.
הצפנת סריג היא היחידה שקיימת הוכחה לגביה שהיא בטוחה כמו המקרה הגרוע אך זאת רק מנקודת ראות תאורטית, בעוד שמעשית החיסרון העיקרי של מערכת כזו הוא מפתח ההצפנה העצום.
בהשראת הרעיון של Ajtai פיתחו ב-1996 עודד גולדרייך, שי הלוי ושפי גולדווסר מערכת הצפנה מבוססת סריג (נקראת בקיצור GGH) עם יחס מקרה ממוצע/מקרה גרוע דומה, דהיינו פענוח אתגר אקראי נתון קשה לפחות כמקרה הגרוע של וריאציית SVP הנקראת uSVP (קיצור של unique SVP).
הבעיה נעשית קלה ככל שפקטור הקירוב גדל, השאלה היא מהו הגורם הקטן ביותר כך שאפשר יהיה לבנות פונקציה קריפטוגרפית הנחשבת קשה לפתרון לפחות כמו מציאת קירוב לבעיית הסריג.
Phong Nguyen פרסם והוכיח ב-1999 פגמים ב-GGH של גולדרייך, גולדווסר והלוי והציע דרכים לתיקון הבעיות שגילה.
מסקנותיו הם שהאלגוריתם אינו יעיל מעשית.
כדי שמערכת GGH תקרא בטוחה סדר גודל של מפתח ההצפנה צריך להיות ריבועי ביחס לפרמטר הביטחון , מעשית זה יכול להגיע לאלפי סיביות.
בימינו הממצאים הטובים ביותר הם פונקציית גיבוב חסינת התנגשויות של Micciancio המבוססת על אי-קירוב בטווח וכן הצפנת רגב המבוססת על אי קירוב של בעיית uSVP בטווח .
הבעיות שיש בהן עניין מנקודת ראות תאורטית הן בעיית הווקטור הקצר ביותר (בקיצור SVP) והכללה שלה שנקראת בעיית הווקטור הקרוב ביותר (CVP).
מצד אחד הודות לאלגוריתם LLL ניתן לבצע קירוב יעיל בפתרון הבעיות האמורות עד כדי פקטור מעריכי מסדר גודל כאשר הוא ממד הסריג ועם אקראיות אפשר להגיע לסדר גודל של .
מצד שני, עבור קבוע כלשהו ידוע שלא קיים אלגוריתם יעיל שיכול לבצע קירוב עד כדי אלא אם P=NP.
הממצאים הללו אומתו אחר מחקרים שנעשו בתחום זה על ידי רבים.
ב-1996 הציע Jeffrey Hoffstein אלגוריתם הצפנה אסימטרי פרקטי שנקרא NTRU שיכול להגיע עם מפתח הצפנה קטן (בסדר גודל של כמה מאות סיביות) על ידי שימוש במחלקה מיוחדת של סריגים שמאפשרת ייצוג קומפקטי.
האלגוריתם מבוסס על חוג פולינומי שנקרא קונבולוציה הפונקציה היא חישוב כפל וחיבור בפולינומיים מודולו .