הצפנת פליאיי

מתוך המכלול, האנציקלופדיה היהודית
(הופנה מהדף הצפנת פייליר)
קפיצה לניווט קפיצה לחיפוש

הצפנת פֵּלִיאֵיאנגלית: Paillier Encryption)[1] היא סכימת הצפנה אסימטרית הסתברותית הומומורפית וחתימה דיגיטלית שהומצאה ב-1999 על ידי פסקל פליאיי (Pascal Paillier) לשעבר מחברת GEMPLUS לוקסמבורג. הצפנת פליאיי הומצאה בהשראת סכימות הצפנה הסתברותית כמו בלום גולדווסר והיא מבוססת על פונקציה חד-כיוונית עם דלת צונחת שנגזרת מבעיה בתורת המספרים הנקראת בעיית השאריות הפריקות (Composite Residuosity Class Problem) מודולו n2 כאשר n מכונה "מספר RSA" (כפולה של שני ראשוניים שונים שווים בגודלם בקירוב).

רקע מתמטי

הבסיס התאורטי של המערכת הוא, בהינתן שלם n=pq כאשר p ו-q ראשוניים גדולים, שווים באורכם בקירוב והחבורה n×n*n2*, השלם z ייקרא שארית n-ית (ממעלה n) מודולו n2 אם קיים שלם yn2* המקיים

z=yn mod n2.

קבוצת השאריות ה-n-יות היא תת-חבורה כפלית n2*. לכל z כזה קיימים בדיוק n שורשים ממעלה n. בעיית ההכרעה האם שלם נתון הוא שארית n-ית או לא, המסומנת בקיצור CR[n] (קיצור של Composite Residuosity) נחשבת לבעיה קשה ולא ידוע על אלגוריתם יעיל שיכול לבצעה בזמן פולינומי. סדר החבורה n2* הוא nϕ(n) כאשר ϕ(n) היא פונקציית אוילר של n.

הפונקציה g(x,y) המוגדרת על ידי

(x,y)gxyn mod n2

עבור xn ו-yn* היא פונקציה חד-חד-ערכית ועל מעל החבורה n2* ביחס לבסיס g נתון. g הוא אלמנט מסדר αn עבור מחלק α כלשהו של ϕ. הקבוצה היא קבוצת כל האלמנטים מסדר nα עבור α=1,...,ϕ (לדוגמה אפשר לבחור g=n+1 כש-α=1).

אפשר לראות שהפונקציה w=g(x,y) הפיכה. כדי להפוך את הפונקציה מגדירים את L(u)=(u1)/n שהיא פונקציה מעל תת-חבורה כפלית של השלמים מודולו n2 המקיימים u1 mod n. שחזור הערכים x,y מתוך w=g(x,y) מתבצע על ידי

x=(L(wϕ mod n2)L(gϕ mod n2)) mod n
y=(wgx)1/n mod n

במקום ϕ של n אפשר לעבוד עם פונקציית קרמייקל שהיא λ(n)=lcm(p1,q1). זהו האקספוננט של חבורת אוילר ו-lcm היא כפולה משותפת מינימלית. שימו לב שלפי משפט קרמייקל עבור כל אלמנט wn2* מתקיים wλ1 mod n וכן wnλ1 mod n2. בהמשך ייעשה שימוש ב-λ בכל המקומות בהן הופיעה פונקציית אוילר.

דלת המלכודת היא הגורמים הראשוניים או λ. כאשר הגורמים הראשוניים של n לא ידועים שחזור x מתוך g(x,y) ואפילו להכריע האם x=0 ללא λ נחשבים לבעיה קשה תחת המודל הסטנדרטי של סיבוכיות חישובית, בהנחה שפירוק לגורמים של n אינו מעשי. האחרונה נקראת בעיית הכרעה של השאריות הפריקות ומסומנת בקיצור DCRA.

סכימות הצפנה וחתימה דיגיטלית

על בסיס הרעיון האמור הצפנת פליאיי פועלת כדלהלן. יהי n=pq ויהי g, אפשר למצוא ערך כזה על ידי בדיקה אם

gcd(L(gλ mod n2),n)=1. הפונקציה gcd מייצגת מחלק משותף מקסימלי.

הערכים n ו-g יהיו מפתחות ציבוריים ואילו p ו-q יהיו המפתחות הפרטיים (במקום המספרים הראשוניים אפשר לשמור את λ). בהינתן מסר m הנמוך מ-n להצפנה בוחרים שלם אקראי r<n ומבצעים:

c=gmrn mod n2

לפענוח:

m=L(cλ mod n2)L(gλ mod n2) mod n

או L(cλ mod n2)L(gλ mod n2)1 מודולו n. הסכימה נחשבת הסתברותית בגלל r והיא בטוחה סמנטית כנגד יריב פסיבי, בהנחה שבעיית CR[n] היא בעיה קשה ושקשה לפרק את n לגורמים. סיבוכיות ההצפנה היא מסדר גודל של O(|n|3) בקירוב.

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

לצורך המחשה הראשוניים יהיו q=331, p=149. לכן n=49319 ו-n2=243236376. הערך λ=lcm(148,330)=24420. הבסיס נקבע ל-g=n+1=49320.

מפתח ציבורי: 49319.
מפתח פרטי: 24420.

לצורך הצפנת המסר m=12345 בוחרים מספר אקראי נניח r=47026 ואז מחשבים את c=49320123454702649319 mod 2432363761=159515031.

הטקסט המוצפן הוא אם כן c=159515031.

לפענוח תחילה מחשבים את L(4932012345 mod 2432363761)=27172 וכן L(4702649319 mod 2432363761)=24420.

ההופכי הכפלי של 24420 מודולו 49319 הוא 27388 לכן m=2717227388 mod 49319=12345.

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

להלן סכימה לא הסתברותית המבוססת חלקית על RSA שנקראת פרמוטציה חד כיוונית עם דלת מלכודת כאשר דלת המלכודת היא λ. והיא מסתמכת על בעיית CR[n] בהנחה שפירוק לגורמים של n היא בעיה קשה. למרות התלות ב-RSA הסכימה ראויה לציון בשל העובדה שפרמוטציות חד כיווניות עם דלת מלכודת (דוגמת RSA ורבין) הן אובייקטים נדירים וחשובים בקריפטוגרפיה מודרנית.

להצפנה:

תחילה מפצלים את המסר המיועד להצפנה m בדרך הפיכה כלשהי לשני חלקים m1,m2. למשל m=m1+nm2.
מחשבים את c=gm1m2n mod n2

לפענוח:

תחילה m1=L(cλ mod n2)L(gλ mod n2)
מחשבים את ערך הביניים c=cgm1 mod n
m2=(c)n1 mod λ mod n
ואז המסר הוא m=m1+nm2.

אפשר להשתמש בכל תמורה פומבית מוסכמת שממפה את m לערכים m1,m2. יש לשים לב שהסכימה הזו אינה הסתברותית, כלומר אינה מערבת שימוש במספר אקראי.

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

לצורך חתימה דיגיטלית תהי h:{0,1}k פונקציית גיבוב קריפטוגרפית של המסר שתסומן בקיצור h(m). עבור המסר m החותם מחשב את החתימה (s1,s2) כדלהלן:

s1=L(h(m)λ mod n2)L(gλ mod n2) mod n
s2=(h(m)gs1)1/n mod λ mod n

מקבל החתימה יכול לוודא את תקפותה על ידי הבדיקה שמתקיים

h(m)=gs1s2n mod n2

הצפנה מהירה

סכימות כמו RSA סובלות מחסרון בכך שהפענוח דורש זמן ואינו יעיל במונחי מחשוב. מסיבה זו מערכת הצפנה אסימטרית תהיה אטרקטיבית אם הפענוח יהיה מסדר גודל כמעט ריבועי ביחס ל-n. להלן גרסה שונה מעט שבה סיבוכיות הפענוח היא בסדר גודל של O(|n|2+ϵ) עבור ϵ>0 קטן כלשהו. הרעיון הוא להגביל את מרחב הטקסט המוצפן n2* לתת קבוצה <g> מסדר נמוך יותר. מסיבות של ביטחון λ צריך להיות כפולה של ראשוני גדול. בהינתן הבסיס gα עבור 1αλ כלשהו, הסכימה היא כדלהלן.

הצפנה:

בוחרים אלמנט אקראי r הנמוך מ-n.
מחשבים את c=gm+rn mod n2

פענוח:

m=L(cα mod n2)L(gα mod n2) mod n

הפעם דלת המלכודת מסתמכת על ידיעת α כמפתח סודי במקום λ. צוואר הבקבוק בפעולת הפענוח הוא הפעולה cα mod n2 שסיבוכיותה היא בסדר גודל O(|n|2|α|) בלבד. אם g נבחר באופן כזה ש-|α|=Ω(|n|ϵ) אז כל תהליך הפענוח יתבצע עם O(|n|2+ϵ) פעולות בסיביות. זהו מאפיין חשוב בהשוואה למערכת אסימטריות אחרות. אולם יש לשים לב שבמקרה זה המערכת לא מסתמכת על בעיית CR[n] כיוון שכעת ידוע שהטקסט המוצפן שייך לקבוצה <g>. הבעיה האחרונה, דהיינו לחשב את x,y בהינתן w<g> נקראת בעיית הלוגריתם הבדיד 'חלקית' וגם היא משוערת כבעיה קשה.

ביטחון

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

יעילות

לפי ההמלצות המקובלות הראשוניים p ו-q צריכים להיבחר באופן שיהיה קשה לפרק את n לגורמים. הבסיס g יכול להיבחר באקראי (בגרסה המהירה יידרש טיפול שונה למשל להעלות אלמנט בחזקת λ/α). כדי לשפר ביצועים אפשר לאמץ את שיטת CRT כמו ב-RSA, כלומר כל החישובים יתבצעו מודולו p2 ו-q2 בהתאמה והתוצאה הסופית תהיה חישוב מערכת המשוואות המודולריות המתקבלת באמצעות משפט השאריות הסיני שהוא זניח יחסית לפעולה של העלאה בחזקה מודולרית. אם בוחרים g קטן (כמו g=2) כל עוד הוא מקיים את ההגדרות של הסכימה, יתקבל שיפור נוסף בביצועים בסדר גודל של 1/3. יתרה מזו g יכול להיות קבוע מה שמאפשר חישוב מוקדם כדי להאיץ ביצועים. בכללות כל הערכים הקבועים וכן חישוב rn או gnr יכולים להתבצע מראש. בפענוח חישוב הפונקציה L(u)=(u1)/n ניתן לביצוע במחיר פעולת כפל אחת מודולו 2|n| על ידי חישוב מוקדם של הקבוע n1 mod 2|n|. הקבועים L(gλ mod n2)1 mod n או L(gα mod n2)1 mod n בגרסה המהירה ניתנים לחישוב מראש.

כדי לנצל את משפט השאריות הסיני (CRT) לשיפור ביצועים, יש להגדיר את הפונקציות Lp ו-Lq כדלהלן: Lp(u)=(u1)/p וכן Lq(u)=(u1)/q בהתאמה. פענוח יתבצע כעת עם הקבועים הבאים אותם מחשבים מראש:

hp=Lp(gp1 mod p2)1 mod p
hq=Lq(gq1 mod q2)1 mod q

ואז תהליך הפענוח הוא כדלהלן:

mp=Lp(cp1 mod p2)hp mod p
mq=Lq(cq1 mod q2)hq mod q
m=CRT(mp,mq) mod n

כאשר CRT היא מימוש של פתרון מערכת הקונגרואנציות לפי משפט השאריות הסיני. ובגרסה המהירה יש להחליף את p1 ו-q1 ב-α.

מאפיינים והרחבות

הצפנת פליאיי הורחבה למספר כיוונים[2]. איוון דמגרד הציע[3] גרסה שבה המודולוס הוא מהצורה ns במקום בחזקת 2. וכן הוצעה גרסה מבוזרת (סכמת סף - threshold cryptography) וכן הוצע מימוש ב-ECC[4].

הומומורפיזם

סכימות ההצפנת פליאיי mgmrn וכן mgm+nr, מודולו n2 הן הומומורפיות מהחבורה הכפלית (n2*,×) לחבורה החיבורית (n,+). בניסוח פורמלי עבור כל m1,m2n ו-k, פונקציית הצפנה E ופונקציית פענוח D בהתאמה, מתקיים

D(E(m1)E(m2) mod n2)=m1+m2 mod n
D(E(m)k mod n2)=km mod n
D(E(m1)gm2 mod n2)=m1+m2 mod n

וכן הלאה. ההשלכה של מאפיין זה היא שהסכימה תהיה שימושית עבור מגוון פרוטוקולים קריפטוגרפיים כמו הצבעה ממוחשבת, סכימת סף, חלוקת סוד ומנגנון הגנת העתקה (Copy protection).

הסתרה עצמית

הסתרה עצמית (self blinding) היא התכונה שכל טקסט מוצפן ניתן לשינוי לטקסט מוצפן אחר מבלי שהשינוי ישפיע על הטקסט המקורי, בניסוח פורמלי עבור כל mn ו-r מתקיים

D(E(m)rn mod n2)=m
או
D(E(m)gnr mod n2)=m במקרה של ההצפנה המהירה.

בעיקרון התכונה הזו מאפשרת לבצע פעולות חישוב על ידי צד שלישי מבלי שהוא עצמו ידע מהו תוכן המידע עליו בוצעו החישובים. לתכונה שימושים רבים בקריפטוגרפיה למשל חתימה עיוורת או מחשוב ענן.

הערות שוליים

  1. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
  2. Catalano, Dario, Rosario Gennaro, Nick Howgrave-Graham, and Phong Q. Nguyen (2001). “Paillier’s cryptosystem revisited.” Proceedings of the 8th ACM conference on Computer and Communications Security ACM Press, New York, 206–214
  3. Damgard, Ivan and Mads Jurik (2001). “A generalization, a simplification and some applications of paillier’s probabilistic public-key system.” Public Key Cryptography—PKC 2001, Lecture Notes in Computer Science, vol. 1992, ed. K. Kim. Springer-Verlag, Berlin, 119–136.
  4. Galbraith, Steven D. (2002). “Elliptic curve paillier schemes.” Journal of Cryptology, 15 (2), 129–138.
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

הצפנת פליאיי37956692Q594646