בכל הצפנה דטרמיניסטית, בהצפנה חוזרת של מסר נתון עם מפתח הצפנה זהה תמיד יתקבל טקסט מוצפן זהה. בשל עובדה זו היא אינה יכולה להחשב "בטוחה סמנטית", כי בעצם העובדה שכאשר מופיעים בלוקים מוצפנים זהים אפשר להסיק שהטקסטים המקוריים המתאימים להם היו זהים, מועבר ליריב פוטנציאלי מידע על סכימת ההצפנה שלא היה מושג בדרך אחרת, מה שמאפשר התקפת מוצפן-נבחר בתנאים מסוימים. מסיבה זו פונקציית הצפנה דטרמיניסטית כזו אינה ראויה לשימוש באופן ישיר אלא רק לאחר הכנת המסר על ידי סכימת ריפוד מתאימה הכוללת ערך אקראי כלשהו. הריפוד מבטיח שללא תלות במסר תמיד יתקבל בלוק שונה ועל כן תמיד יופק טקסט מוצפן שונה. תקן PKCS #1 גרסה v1.5 (הקודם) פירט שיטת ריפוד פשוטה כדלקמן: עבור מודולוס בגודל formula_1 סיביות, להצפנת המסר formula_2, בונים בלוק באורך formula_3 בתים (formula_3 נקרא כאן פרמטר ביטחון ונקבע על ידי פונקציית ההצפנה, למשל ב-RSA-1024 הוא formula_5). הבלוק המורכב על ידי שרשור הערכים לפי הסדר הבא: formula_6, כאשר formula_2 הוא המסר המקורי המיועד להצפנה. מתחילים בבית אפס לאחריו בית שמכיל את הערך '02', לאחריו מחרוזת אקראית של שמונה בתים לפחות שאינם '00' שצריכה להיות שונה עבור כל מסר אך לא חייבת להיות סודית, אחריה בית אפס נוסף ולבסוף מצמידים את המסר formula_2. את הבלוק שנוצר מצפינים לאחר מכן עם RSA כרגיל: formula_9. לאחר פענוח, המפענח מוודא תחילה שהבלוק בנוי בפורמט הנכון, כלומר הערכים מופיעים לפי הסדר האמור, אם לא הוא דוחה את המסר המוצפן ומחזיר הודעת שגיאה, אם כן, מפרק את הבלוק למחרוזות המקוריות ומחלץ את המסר המקורי formula_2.
בשיטה זו בידי המפענח יכולת בסיסית לאתר תקלות או שינויים זדוניים בטקסט המוצפן. היות שהתוצאה חייבת לעמוד בדרישות התקן, לא סביר שטקסט מוצפן שעבר "שיפוץ" בדרכו אל המקבל על ידי צד שלישי כלשהו (שהטקסט המקורי לא ידוע לו) יתקבל במבנה הנכון לאחר פענוח. על פניו נראה כאילו סכימת הריפוד הזו מספקת אימות עקיף והיא בטוחה סמנטית בשל תוספת האקראיות של formula_11, דהיינו בכל הצפנה יתקבל טקסט מוצפן אחר וכן לפי זה היא אמורה להיות חסינה מפני התקפת מוצפן-נבחר. אולם ב-1998 הראה דניאל בלייכנבכר ממעבדות בל ששיטת ריפוד זו אינה בטוחה כלל ואפשר לפרוץ אותה על ידי שליחה של כ־formula_12 טקסטים מוצפנים לכאורה בהתקפת מוצפן-נבחר אדפטיבית, בהסתמך על יכולת המתקיף לקבל משוב מהמערכת. כלומר כדי שההתקפה תצליח צריך שלמתקיף תהיה גישה לשרת הפענוח והוא יכול לבקש פענוח של כל טקסט כרצונו. אם הטקסט אינו תואם PKCS מהסיבה שאינו בנוי בפורמט המתואר הוא אמור לקבל הודעת שגיאה. הודעת השגיאה במקרה זה משרתת את המתקיף כ"אורקל פענוח" איתו הוא יכול לנחש את הטקסט המוצפן בשיטה האדפטיבית, כלומר כל בקשת פענוח מסתמכת על תוצאות קודמות כדי לצמצם את טווח החיפוש עדי כדי אפשרות יחידה. ההתקפה הייתה הרסנית במיוחד כיוון ש-SSL הסתמך על סכמת הריפוד הזו וכתוצאה מכך הפך ללא בטוח כלל.
בלום ומיקאלי הציעו שיטת "רדוקציה" להוכחת ביטחון, כלומר הצגת אלגוריתם אפקטיבי שיכול לקרוא תיגר על ההשערה הבסיסית כמו קושי בהיפוך RSA או קושי בפירוק לגורמים, שמכיל את הפרוטוקול עצמו כתת-שגרה. כלומר מראים שאם קיים אלגוריתם שיכול לפרוץ את הפרוטוקול, אזי בהכרח אפשר להמיר אותו לאלגוריתם שיכול לפתור את הבעיה המתמטית עליה הוא מבוסס. היות שההנחה היא שקשה לפתור את הבעיה המתמטית עליה הפרוטוקול מסתמך, זוהי הוכחת ביטחון טובה לחוזקו של הפרוטוקול מהיבט תאורטי. אך אינה פרקטית, מסתבר שקשה להגיע לביטחון פרקטי מוכח שהוא גם יעיל.
מודל אורקל אקראי.
בלייר ורוגווי פיתחו את מודל האורקל האקראי כפרדיגמה לבניית פרוטוקולים קריפטוגרפיים בטוחים המסתמך על פונקציה פסאודו-אקראית קריפטוגרפית מעשית כמו SHA-2. הרעיון שלהם לשלב ביטחון מוכח עם יעילות על ידי היוריסטיקה שהושאלה מרעיון של שמיר ופיאט. ההיוריסטיקה פועלת כך שמשערים לגבי אובייקט כמו פונקציית גיבוב שהוא מתנהג כביכול כאורקל אקראי אמיתי ומנסים להוכיח שהפרוטוקול נכון בהתבסס על כך. מובן שהוכחת ביטחון בשיטה זו אינה הוכחה חזקה במובן מתמטי טהור. על כל פנים בדרך זו אפשר לאשש במסגרת מודל אורקל אקראי, אם ההתקפה מספיק גנרית (כלומר בהנחה שהתוקף לא יכול לנצל חולשות ספיציפיות בפונקציית הגיבוב) שהפרוטוקול בטוח. בניסוח אחר, הרעיון מאפשר לקבל אינדיקציה טובה שהפרוטוקול אינו מכיל כשלים מבניים כלשהם ואם מישהו מצליח לפרוץ אותו, בהכרח היה חייב לנצל חולשות בפונקציית הגיבוב או בפונקציה החד-כיוונית מה שמפר את ההנחה הבסיסית שהן קשות לשבירה. גרסה זו מעט יותר מרוככת מביטחון מוכח אך פרקטית ויעילה יותר.
סכימת OAEP.
סכימת OAEP היא הסכימה הראשונה שמיישמת את מודל האורקל האקראי. היא יכולה לעבוד עם כל פונקציה חד-כיוונית עם דלת מלכודת (פונקציית הצפנה) formula_13 שמקבלת קלט ומחזירה פלט באורך formula_3 סיביות ופונקציית גיבוב בטוחה כלשהי שמקודדת כל formula_2 הקצר במעט מ-formula_3 ומשלבת אותו יחד עם ערך אקראי formula_11. השיטה מסתמכת בנוסף גם על חוזקה של פונקציית הגיבוב. לצורך יישומה בפועל יש להגדיר פרמטר שלם formula_18 ופרמטר formula_19 וכן שתי פונקציות כלליות: הראשונה מחולל אקראי formula_20 שמקבל מחרוזת באורך formula_21 ומחזיר מחרוזת אקראית באורך formula_22 ופונקציה נוספת formula_23 שמקבלת מחרוזת באורך formula_22 סיביות ומחזירה מחרוזת קצרה יותר באורך formula_21 (למשל אפשר להשתמש ב-formula_22 או formula_21 הסיביות הפחות משמעותיות של SHA-2 לפי הצורך). כדי לרפד את המסר formula_28 בוחרים שלם אקראי formula_11 באורך formula_21 סיביות ומחשבים את:
כאשר הסימן formula_32 מסמל שרשור מחרוזות והסמל formula_33 מייצג XOR. ההצפנה היא formula_34 והפענוח מבוצע בדרך דומה. הסכימה הבסיסית המתוארת הוכחה בטוחה על ידי בלייר ורוגווי בהנחה שפונקציית הגיבוב "אידיאלית". פירושו של דבר הוא שההנחה היא ש-formula_35 ו-formula_36 הן פונקציות רנדומליות המתנהגות כמו אורקל אקראי. כמובן שמעשית אי אפשר להניח כזו הנחה, אך הפונקציות הקיימות ידועות כמספיק חזקות כדי לבסס עליהן מערכת הצפנה מהיבט פרקטי. החסרון העיקרי בסכימה המתוארת שאינה "מודעת טקסט-מקור" (plaintext-aware). בהקשר של מודל אורקל אקראי "מודעות טקסט מקור" פירושה שכדי שתוקף יצליח לבנות טקסט מוצפן "תקף", דהיינו שהמקבל יצליח לפענחו במבנה הנכון לפי התקן עליו לדעת בהכרח טקסט מקור שמתאים לו. ניסיון לנחש מחרוזת סיביות כלשהי שלאחר פענוחה בפונקציית הפענוח עם מפתח הצפנה כלשהו, יתקבל טקסט מקור במבנה הנכון קשה לביצוע. ההשלכה היא שהסכימה הבסיסית אינה מוכחת כעמידה נגד התקפת מוצפן נבחר אדפטיבית (CCA2) אלא רק כנגד CCA1. בלייר ורוגווי הציעו גרסה נוספת (כמתואר בתרשים) שלטענתם "מודעת טקסט מקור" והיא פועלת כדלהלן:
כאשר formula_38 וכן formula_39 הוא פרמטר נוסף המקיים formula_40. כאן בנוסף משרשרים מחרוזת של formula_39 אפסים למסר. ההצפנה והפענוח באותו האופן. וריאציה של הסכימה האחרונה שולבה למעשה בתקן PKCS#2 כסכימת ריפוד מחייבת עבור הצפנה עם RSA.
OAEP נחשבה עמידה כנגד התקפת מוצפן נבחר מסוג 2 אם כי המחברים לא סיפקו הוכחה פורמלית. ויקטור שופ הוכיח על ידי דוגמה נגדית שתחת מודל אורקל אקראי זה לא תמיד נכון. הוא הראה שקיימת פונקציה חד-כיוונית formula_42 שבה קל חשב את formula_43 מתוך formula_44 ו-formula_45 מזה נובע שמבנה ריפוד OAEP אינו יכול להיות עמיד תמיד כנגד CCA2 עבור סתם פונקציה חד-כיוונית. מאידך הוא גם הוכיח כי עבור פונקציית RSA הסכימה שהוצעה טובה, וזאת רק בשל תכונה ספציפית ל-RSA (בהמשך).
סכימת OAEP+.
מהדוגמה שהובאה על ידי שופ נראה שכדי שהתקפה מסוג CCA2 תצליח, התוקף צריך להיות מסוגל לפחות חלקית להפוך את התמורה החד-כיוונית formula_13. העובדה שפונקציה חד-כיוונית אינה מעידה בהכרח שהיא חד-כיוונית חלקית (partial domain one-way). פוג'יסאקי ואחרים הוכיחו שאם הפונקציה formula_13 היא חד-כיוונית חלקית הרי שסכימת OAEP תהיה בטוחה כנגד CCA2. הגדרה זו של פונקציה חד-כיוונית חלקית חזקה יותר מהגדרה של פונקציה חד-כיוונית רגילה. מסתבר שבשל תכונת ההומומורפיות של RSA היא נחשבת חד-כיוונית חלקית בהנחה שהיא חד-כיוונית. כמו כן שופ הוכיח פורמלית שאם המעריך (מפתח ההצפנה) של RSA שווה 3 סכימת RSA-OAEP בטוחה כנגד התקפת מוצפן נבחר מכל סוג, אולם יש הסבורים שמעריך קטן מהווה חולשה בפני עצמה לכן שופ הציע אלטרנטיבה משלו לסכימת OAEP והוכיח פורמלית שהיא בטוחה סמנטית כנגד התקפת מוצפן נבחר בהנחה שהפונקציה חד-כיוונית. הסכימה משתמשת בפונקציית יתירות משתנה formula_48 במקום בקבוע המכיל אפסים ואחד בסוף. סכימת OAEP+ מורכבת מרשת פייסטל בשני סבבים עם שלוש פונקציות formula_49 כמתואר בתרשים:
וההצפנה היא formula_52. הפונקציות המוטמעות בסכימה הן: formula_53 וכן formula_54 וכן formula_55. הפונקציה formula_13 היא פונקציה חד-כיוונית שהיא תמורה הפועלת על formula_3 סיביות. הפרמטרים הנוספים מקיימים formula_40 וכן הערכים formula_59 ו-formula_60 צריכים להיות זניחים. המסר הוא לכל היותר באורך formula_22 סיביות כאשר formula_38.
סכימת SAEP.